对强化MD结构杂凑函数的一个新的“牧群”攻击

A New Herding Attack on Hash Functions with Strengthening Merkle-Damagard (MD) Construction

该文构造了具有2k个起始点的变长"钻石树"结构的多碰撞,并据此提出了对强化MD结构杂凑函数的一个新的选择目标强制前缀且原像长度为2k+3块的原像攻击(即"牧群"攻击)。由于增大了攻击过程中可利用的中间链接值的数量,故当k≥n/4-1.05时,新的牧群攻击可将该攻击的计算复杂性由现有结果O(2n-2(k+1)+2n/2+k+5/2)降至O(2n-k/3+2n/2+k+2)。

This paper constructs a ＂diamond structure＂ multicollision with 2k initial values and variant lengths,which is used to propose a new chosen target forced prefix preimage attack （herding attack） on hash functions with Strengthening Merkle-Damagard （SMD） construction to find a preimage with 2k＋3 blocks.Since the number of the chaining values available in herding attack is increased,the computational complexity of herding attack is reduced to O （2n -k /3 ＋ 2n /2 ＋k ＋2） from O （2n -2 （ k＋1 ）＋ 2n /2 ＋ k＋5/2） for k ≥ n/ 4 - 1.05.