Hash函数MD5攻击技术研究(19)
时间:2025-07-10
时间:2025-07-10
Hash函数MD5攻击技术研究
第三章MD5的碰撞攻击17
3.2比特跟踪技术
在MD5碰撞攻击的过程中,在差分引入之后,必须应用比特跟踪技术对差分进行比特级别的跟踪,以确保有效地控制差分路径,最终实现碰撞。
就MD5的第一轮而言,以四个连续步骤为例:
a=b+((a+F(b,C,d)+mi+ti)<<<si);
d=a+((d+F(a,b,c)+m“1+t“1)<<<s“1);
c=d+((c+F(d,a,b)+mi+2+ti+2)<<<si+2);
b=c+((b+F(c,d,a)+mi+3+t“3)<<<si+3);式(3.1)式(3.2)式(3-3)式(3.4)
在这每一步中,只有F函数的运算是位运算,除此以外的运算都是模232的加法运算。因此,在F函数中,其三个参数某一比特的变化,最终只会影响F函数的相应的比特位;F函数以外的运算,由于可能存在进位的问题,所以影响的可能不只是变化的那一比特,而且可能是影响其周围的一连串的比特位,影响的范围可能很大,这就需要依靠比特跟踪技术来监控。在整个运算过程中,第32比特位置特殊,其进位将会产生溢出,这个性质在比特跟踪过程中至关重要。下面将以文献f171为例,介绍比特跟踪技术在碰撞攻击中的应用。
3.2.1符号说明
1.M=(mo,m。,…,m。5)和M’=(mo’,m。’,…,m。,I)代表相对应的两个512比特的明文块,AM=(Am。,Aml,.一,Am。,)代表两个相对应的明文块的差分,其中每个m;为32比特的字。
2.ai,di,ci,bi分别代表第(4i.3)步,第(4i.2)步,第(4i.1)步,第4i步的输出,其中1≤i≤16;同样的方法定义a;’,b;’,ci',d;’。
3.ai,j,bi,j,ciJ,du分别代表ai,di,ci,bi的第j比特,其中,最高位为第32比特,最低位为第1比特。
4.西舻II/ij,分别表示mi和E的第j比特,其中中;表示第i步的逻辑函数,V;表示循环左移的整体的表达式。例如,第8步中,西7=F(c2,d2,a2)=(c2Ad2)V(-1c2^a2),1l,7=bl+F(c2,d2,a2)+m7+t7。
5.△Xi,j=x硒t.x硝=-1,这是表示第j比特的差分。如果值为1,说明xi’的第jLt特是1而X;的第j比特是0;如果值是0,说明xi7的第j比特是0而x;的第j比特是1,其中X可以是a,b,c,d,西,V。
6.Ax;[jl,j2,…,jl】=Xi[jl,j2,…'jl】-X;,表示x;的第jLj2,…,jl比特的变化。x;【j1,j2,…,jl】表示具体第j1,j2""jl的比特的变化,其中“+"表示该比特从O变成了1;“.”表示该比特从1变成了0。
上一篇:第二章_多项式练习