摘要
目前,在非平衡环境下的r-碰撞问题还没有得到有效的解决.本文提出了一种新的高效算法来对r个不同的非平衡函数寻找对应的r-碰撞.新算法是将现有的r-碰撞算法、并行碰撞搜索算法与非平衡中间相遇攻击技术进行有机结合.具体攻击过程如下所示:首先,攻击者把r个函数分成左右两个集合,当r为偶数时,其对应的左右集合分别为■和■,并需要在左右集合中对应位置的两个非平衡函数fli和■之间寻找碰撞.以第i对为例,攻击者在碰撞-收集阶段可以采用PCS算法收集两个非平衡函数fli和fti的2mi个碰撞.注意到,攻击者需要对左右集合中?r/2?个位置对重复上述寻找碰撞的操作.如果r是奇数,攻击者还需要对剩下的函数f收集2m0个函数值.在碰撞-收集阶段之后,攻击者采用中间相遇攻击在r-?r/2?个列表中寻找r-碰撞.新算法的主要结果是:(1)与现有的r-碰撞算法不同,新算法的时间复杂度是由所需存储量和所选择的分组方法决定的.(2)在存储足够的情况下,新的r-碰撞算法的时间复杂度公式为:当r=2k时,时间复杂度为■;当r=2k+1时,时间复杂度为■,其中Rlj表示左集合中实现代价最大的函数的实现代价,Rc表示未配对函数的实现代价,■表示右集合中各函数实现代价.对于r=2k(或r=2k+1),攻击者首先需要找到■(或■,从而求出该情况下的最佳分组方法和最佳时间复杂度.(3)在存储有限的情况下,如果不知道所有分组方法所需的时间复杂度,攻击者就无法得到最佳的时间复杂度.
At present,the problem of r-collision in the unbalanced environment has not yet been effectively solved.In this paper,a new efficient algorithm is proposed to find an unbalanced r-collision of r different and unbalanced functions.The new algorithm adopts the techniques from the previous 3-collision algorithm,the parallel collision search(PCS)algorithm and the unbalanced meet-in-the-middle(UMitM)attack.The attack process of the new algorithm can be described as follows:First,the attacker divides r functions into left and right sets.When r is even,the corresponding left and right sets are{fl1,fl2,…,f[r/2]}and{ft1,ft2,…,[tr/2]}respectively,and it is necessary to find collisions between two unbalanced functions fli and fti(for 1≤i≤[r/2])at corresponding positions in the left and right sets.Take the i-th function for example,the attacker adopts the PCS algorithm to collect 2mi collisions of two unbalanced functions fli and fti.Note that the attacker needs to repeat the collection-collision operation for[r/2]pairs of positions in the left and right sets.If r is odd,the attacker also needs to collect 2m0 images of the left function.After the collision-collection phase,the attacker adopts the MitM attack to find a r-collision between these r-[r/2]lists.The main results of the new algorithm are:(1)The time complexity of the new algorithm is determined by the memory and the chosen grouping methods,which is different from the previous r-collision algorithm.(2)With sufficient storage,the time complexity formula of the new r-collision algorithm is as follows:when r=2k,the time complexity is O(■).When r=2k+1,the time complexity is■,where Rlj is the implementation cost of the function with the highest implementation cost in the left set,Rc is the implementation cost of the unpaired function,and Rtx(1≤x≤(r-1)/2)is the implementation cost of each function in the right set.The attacker first needs to find min■for r=2k(or min(■ for r=2k+1)so as to find the best grouping method and the best time complexity in thi
作者
邹剑
李金春
董乐
李灵琛
ZOU Jian;LI Jin-Chun;DONG Le;LI Ling-Chen(College of Computer and Data Science,Fuzhou University,Fuzhou 350108,China;Key Lab of Information Security of Network Systems,Fuzhou University,Fuzhou 350108,China;College of Mathematics and Information Science,Henan Normal University,Xinxiang 453000,China;Guilin University of Electronic Technology,Guilin 541004,China)
出处
《密码学报》
CSCD
2023年第3期574-587,共14页
Journal of Cryptologic Research
基金
国家自然科学基金(61902073)
福建省自然科学基金(2021J01623)。
关键词
r-碰撞算法
并行碰撞搜索算法
非平衡中间相遇攻击
r-collision algorithm
parallel collision search algorithm
unbalanced meet-in-the-middle attack
