首页 > 代码库 > Md5扩展攻击的原理和应用
Md5扩展攻击的原理和应用
*本文原创作者:Guilty and Innocent,本文属FreeBuf原创奖励计划,未经许可禁止转载
做CTF题目的过程中遇到了md5扩展攻击,参考了几篇文章,感觉写的都有些小缺陷,再发一篇文章,理解md5扩展攻击首先需要了解md5的工作原理。
1)md5的工作原理
具体参考这两篇文章
http://blog.csdn.net/adidala/article/details/28677393,算法实现有误
https://www.rfc-editor.org/rfc/pdfrfc/rfc1321.txt.pdf,算法正确
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[6]+T[