*本文原创作者:Guilty and Innocent,本文属FreeBuf原创奖励计划,未经许可禁止转载
做CTF题目的过程中遇到了md5扩展攻击,参考了几篇文章,感觉写的都有些小缺陷,再发一篇文章,理解md5扩展攻击首先需要了解md5的工作原理。
1)md5的工作原理
具体参考这两篇文章
,算法实现有误
,算法正确
md5的算法原理如下图所示
Md5的算法步骤是
1、填充
将数据进行填充,首先添加0×80,接着添加0×00使得 (数据字节数 + 8)%64 = 0
2、增加长度
将数据的长度放入8字节的数组中,把低字节放到前面,例如长度为1,8字节的数据长度表示为00 00 00 00 00 00 00 01,把这个长度值转化为低字节在前面变成了01 00 00 00 00 00 00 00,将这个数据加入到整体的数据中。
3、进行轮次变换
以64个字节为1组进行轮次变换,这一组中以4字节为1个单位分成16个数字。
首先准备A,B,C,D四个32位的字符,其中, A = 0×67452301,B = 0xefcdab89
,C = 0x98badcfe,D = 0×10325476, 将ABCD作为种子,与16个数字进行一种复杂的运算(运算方式见后文),运算结果为A1 B1 C1 D1,以A1 B1 C1 D1为种子然后重复这个过程计算最后得到AnBnCnDn
4、输出hash值
将An进行类似于第二步的低字节顺序的排列An’,同理对Bn,Cn,Dn进行同样变换,An’,Bn’,Cn’,Dn’的简单拼接就是最后结果。
注:这里简单记录一下正确的复杂算法
文献1中的算法是错误的,正确的算法是
定义其中几个子算法F = lambda x,y,z:((x&y)|((~x)&z))G = lambda x,y,z:((x&z)|(y&(~z))) H = lambda x,y,z:(x^y^z) I = lambda x,y,z:(y^(x|(~z))) def shift(a, count): return (((a << count) | (a >> (32 -count)))&0xffffffff) 常量表: T_func = lambda i: int(4294967296*abs(math.sin(i))) & 0xffffffff T = [T_func(i) for i in xrange(1, 65)] T.insert(0 , 0) 复杂算法为 INPUT_A = A INPUT_B = B INPUT_C = C INPUT_D = D M = [ (myord[i * 64 + j + 3] <<24) + (myord[i * 64 + j + 2] << 16 )+ (myord[i * 64 + j + 1] << 8) + (myord[i * 64 + j + 0] )\ for j in xrange(0, 64, 4)] def shift(a, count): return (((a << count) | (a >> (32 -count)))&0xffffffff) #第一轮 A = (B+ shift((A+F(B,C,D)+M[0]+T[1]) &0xffffffff,7) ) & 0xffffffff D = (A+shift((D+F(A,B,C)+M[1]+T[2]) &0xffffffff ,12) )& 0xffffffff C = (D+shift((C+F(D,A,B)+M[2]+T[3]) &0xffffffff,17) ) &0xffffffff B = (C+shift((B+F(C,D,A)+M[3]+T[4]) &0xffffffff,22) )&0xffffffff A = (B+shift((A+F(B,C,D)+M[4]+T[5]) &0xffffffff,7) )&0xffffffff D = (A+shift((D+F(A,B,C)+M[5]+T[6])&0xffffffff,12) )&0xffffffff C = (D+shift((C+F(D,A,B)+M[