Md5扩展攻击的原理和应用

鱼柒

1）md5的工作原理

具体参考这两篇文章

http://www.xiaobaigw.cn/thread-1399-1-1.html，算法实现有误

rfc1321.txt.pdf (23.82 KB, 下载次数: 1)

2017-6-16 08:27 上传

点击文件名下载附件
下载查看

，算法正确

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中的算法是错误的，正确的算法是

1. 定义其中几个子算法
   
2. 
   
3. F = lambda x,y,z:((x&y)|((~x)&z))
   
4. 
   
5. G = lambda x,y,z:((x&z)|(y&(~z)))
   
6. 
   
7. H = lambda x,y,z:(x^y^z)
   
8. 
   
9. I = lambda x,y,z:(y^(x|(~z)))
   
10. 
    
11. def shift(a, count):
    
12. 
    
13.         return (((a << count) | (a >> (32 -count)))&0xffffffff)
    
14. 
    
15. 常量表：
    
16. 
    
17. T_func = lambda i: int(4294967296*abs(math.sin(i))) & 0xffffffff
    
18. 
    
19. T = [T_func(i) for i in xrange(1, 65)]
    
20. 
    
21. T.insert(0 , 0)
    
22. 
    
23. 复杂算法为
    
24. 
    
25.         INPUT_A = A
    
26. 
    
27.         INPUT_B = B
    
28. 
    
29.         INPUT_C = C
    
30. 
    
31.         INPUT_D = D
    
32. 
    
33.         M = [ (myord[i * 64 + j + 3] <<24) +  (myord[i * 64 + j + 2] << 16 )+ (myord[i * 64 + j + 1] << 8) + (myord[i * 64 + j + 0] )\
    
34. 
    
35.              for j in xrange(0, 64, 4)]
    
36. 
    
37.         def shift(a, count):
    
38. 
    
39.             return (((a << count) | (a >> (32 -count)))&0xffffffff)
    
40. 
    
41.         #第一轮
    
42. 
    
43.         A = (B+ shift((A+F(B,C,D)+M[0]+T[1]) &0xffffffff,7) ) & 0xffffffff
    
44. 
    
45.         D = (A+shift((D+F(A,B,C)+M[1]+T[2]) &0xffffffff ,12) )& 0xffffffff
    
46. 
    
47.         C = (D+shift((C+F(D,A,B)+M[2]+T[3]) &0xffffffff,17) ) &0xffffffff
    
48. 
    
49.         B = (C+shift((B+F(C,D,A)+M[3]+T[4]) &0xffffffff,22) )&0xffffffff
    
50. 
    
51.         A = (B+shift((A+F(B,C,D)+M[4]+T[5]) &0xffffffff,7) )&0xffffffff
    
52. 
    
53.         D = (A+shift((D+F(A,B,C)+M[5]+T[6])&0xffffffff,12) )&0xffffffff
    
54. 
    
55.         C = (D+shift((C+F(D,A,B)+M[6]+T[7]) &0xffffffff,17) )&0xffffffff
    
56. 
    
57.         B = (C+shift((B+F(C,D,A)+M[7]+T[8]) &0xffffffff,22) )&0xffffffff
    
58. 
    
59.         A = (B+shift((A+F(B,C,D)+M[8]+T[9])&0xffffffff,7) )&0xffffffff
    
60. 
    
61.         D = (A+shift((D+F(A,B,C)+M[9]+T[10])&0xffffffff,12) )&0xffffffff
    
62. 
    
63.         C = (D+shift((C+F(D,A,B)+M[10]+T[11])&0xffffffff,17) )&0xffffffff
    
64. 
    
65.         B = (C+shift((B+F(C,D,A)+M[11]+T[12])&0xffffffff,22) )&0xffffffff
    
66. 
    
67.         A = (B+shift((A+F(B,C,D)+M[12]+T[13])&0xffffffff,7) )&0xffffffff
    
68. 
    
69.         D = (A+shift((D+F(A,B,C)+M[13]+T[14])&0xffffffff,12) )&0xffffffff
    
70. 
    
71.         C = (D+shift((C+F(D,A,B)+M[14]+T[15])&0xffffffff,17) )&0xffffffff
    
72. 
    
73.         B = (C+shift((B+F(C,D,A)+M[15]+T[16])&0xffffffff,22) )&0xffffffff
    
74. 
    
75.         #第二轮
    
76. 
    
77.         A = (B+shift((A+G(B,C,D)+M[1]+T[17])&0xffffffff,5) )&0xffffffff
    
78. 
    
79.         D = (A+shift((D+G(A,B,C)+M[6]+T[18]) &0xffffffff,9) )&0xffffffff
    
80. 
    
81.         C = (D+shift((C+G(D,A,B)+M[11]+T[19])&0xffffffff,14) )&0xffffffff
    
82. 
    
83.         B = (C+shift((B+G(C,D,A)+M[0]+T[20])&0xffffffff,20) )&0xffffffff
    
84. 
    
85.         A = (B+shift((A+G(B,C,D)+M[5]+T[21])&0xffffffff,5) )&0xffffffff
    
86. 
    
87.         D = (A+shift((D+G(A,B,C)+M[10]+T[22])&0xffffffff,9) )&0xffffffff
    
88. 
    
89.         C = (D+shift((C+G(D,A,B)+M[15]+T[23])&0xffffffff,14) )&0xffffffff
    
90. 
    
91.         B = (C+shift((B+G(C,D,A)+M[4]+T[24])&0xffffffff,20) )&0xffffffff
    
92. 
    
93.         A = (B+shift((A+G(B,C,D)+M[9]+T[25])&0xffffffff,5) )&0xffffffff
    
94. 
    
95.         D = (A+shift((D+G(A,B,C)+M[14]+T[26])&0xffffffff,9) )&0xffffffff
    
96. 
    
97.         C = (D+shift((C+G(D,A,B)+M[3]+T[27])&0xffffffff,14) )&0xffffffff
    
98. 
    
99.         B = (C+shift((B+G(C,D,A)+M[8]+T[28])&0xffffffff,20) )&0xffffffff
    
100. 
     
101.         A = (B+shift((A+G(B,C,D)+M[13]+T[29])&0xffffffff,5) )&0xffffffff
     
102. 
     
103.         D = (A+shift((D+G(A,B,C)+M[2]+T[30])&0xffffffff,9) )&0xffffffff
     
104. 
     
105.         C = (D+shift((C+G(D,A,B)+M[7]+T[31])&0xffffffff,14) )&0xffffffff
     
106. 
     
107.         B = (C+shift((B+G(C,D,A)+M[12]+T[32])&0xffffffff,20))&0xffffffff
     
108. 
     
109.         #第三轮
     
110. 
     
111.         A = (B+shift((A+H(B,C,D)+M[5]+T[33])&0xffffffff,4) )&0xffffffff
     
112. 
     
113.         D = (A+shift((D+H(A,B,C)+M[8]+T[34])&0xffffffff,11) )&0xffffffff
     
114. 
     
115.         C = (D+shift((C+H(D,A,B)+M[11]+T[35])&0xffffffff,16) )&0xffffffff
     
116. 
     
117.         B = (C+shift((B+H(C,D,A)+M[14]+T[36])&0xffffffff,23) )&0xffffffff
     
118. 
     
119.         A = (B+shift((A+H(B,C,D)+M[1]+T[37])&0xffffffff,4) )&0xffffffff
     
120. 
     
121.         D = (A+shift((D+H(A,B,C)+M[4]+T[38])&0xffffffff,11) )&0xffffffff
     
122. 
     
123.         C = (D+shift((C+H(D,A,B)+M[7]+T[39])&0xffffffff,16) )&0xffffffff
     
124. 
     
125.         B = (C+shift((B+H(C,D,A)+M[10]+T[40])&0xffffffff,23) )&0xffffffff
     
126. 
     
127.         A = (B+shift((A+H(B,C,D)+M[13]+T[41])&0xffffffff,4) )&0xffffffff
     
128. 
     
129.         D = (A+shift((D+H(A,B,C)+M[0]+T[42])&0xffffffff,11) )&0xffffffff
     
130. 
     
131.         C = (D+shift((C+H(D,A,B)+M[3]+T[43])&0xffffffff,16) )&0xffffffff
     
132. 
     
133.         B = (C+shift((B+H(C,D,A)+M[6]+T[44])&0xffffffff,23) )&0xffffffff
     
134. 
     
135.         A = (B+shift((A+H(B,C,D)+M[9]+T[45])&0xffffffff,4) )&0xffffffff
     
136. 
     
137.         D = (A+shift((D+H(A,B,C)+M[12]+T[46])&0xffffffff,11) )&0xffffffff
     
138. 
     
139.         C = (D+shift((C+H(D,A,B)+M[15]+T[47])&0xffffffff,16) )&0xffffffff
     
140. 
     
141.         B = (C+shift((B+H(C,D,A)+M[2]+T[48])&0xffffffff,23))&0xffffffff
     
142. 
     
143.         #第四轮
     
144. 
     
145.         A = (B+shift((A+I(B,C,D)+M[0]+T[49])&0xffffffff,6) )&0xffffffff
     
146. 
     
147.         D = (A+shift((D+I(A,B,C)+M[7]+T[50])&0xffffffff,10) )&0xffffffff
     
148. 
     
149.         C = (D+shift((C+I(D,A,B)+M[14]+T[51])&0xffffffff,15) )&0xffffffff
     
150. 
     
151.         B = (C+shift((B+I(C,D,A)+M[5]+T[52])&0xffffffff,21) )&0xffffffff
     
152. 
     
153.         A = (B+shift((A+I(B,C,D)+M[12]+T[53])&0xffffffff,6) )&0xffffffff
     
154. 
     
155.         D = (A+shift((D+I(A,B,C)+M[3]+T[54])&0xffffffff,10) )&0xffffffff
     
156. 
     
157.         C = (D+shift((C+I(D,A,B)+M[10]+T[55])&0xffffffff,15) )&0xffffffff
     
158. 
     
159.         B = (C+shift((B+I(C,D,A)+M[1]+T[56])&0xffffffff,21) )&0xffffffff
     
160. 
     
161.         A = (B+shift((A+I(B,C,D)+M[8]+T[57])&0xffffffff,6) )&0xffffffff
     
162. 
     
163.         D = (A+shift((D+I(A,B,C)+M[15]+T[58])&0xffffffff,10) )&0xffffffff
     
164. 
     
165.         C = (D+shift((C+I(D,A,B)+M[6]+T[59])&0xffffffff,15) )&0xffffffff
     
166. 
     
167.         B = (C+shift((B+I(C,D,A)+M[13]+T[60])&0xffffffff,21) )&0xffffffff
     
168. 
     
169.         A = (B+shift((A+I(B,C,D)+M[4]+T[61])&0xffffffff,6) )&0xffffffff
     
170. 
     
171.         D = (A+shift((D+I(A,B,C)+M[11]+T[62])&0xffffffff,10) )&0xffffffff
     
172. 
     
173.         C = (D+shift((C+I(D,A,B)+M[2]+T[63])&0xffffffff,15) )&0xffffffff
     
174. 
     
175.         B = (C+shift((B+I(C,D,A)+M[9]+T[64])&0xffffffff,21))&0xffffffff
     
176. 
     
177.         A = (A + INPUT_A) & 0xffffffff
     
178. 
     
179.         B = (B + INPUT_B) & 0xffffffff
     
180. 
     
181.         C = (C + INPUT_C) & 0xffffffff
     
182. 
     
183.         D = (D + INPUT_D) & 0xffffffff

复制代码

Md5算法实现python版本见第三节的中的my_md5>函数实现

理解的md5算法的原理，下面开始讲解md5扩展攻击

2）Md5攻击扩展攻击

首先可以参考这篇文章

深入理解hash长度扩展攻击.pdf (329.5 KB, 下载次数: 2)

2017-6-16 08:42 上传

点击文件名下载附件

，本文将对这篇文章进行补充说明。

从md5算法原理可以知道，每一轮次计算的ABCD将作为下一轮次计算的初始值，假设我们已知一个数字x的md5值为y，其中x为未知量，即y=md5（x），同时已知x的长度，那么我们就能进行md5扩展攻击，因为我们知道y为md5（x）计算完毕后的ABCD值的简单组合，通过md5的算法可知y = f（x + x的填充值），如果我们增加x1，计算y’=f( (x + x的填充值+x1 ) +  (x + x的填充值+x1 ) 的填充值 )则变得可能，应为y’可以使用y转化的AB

CD值同(x1 + (x + x的填充值+x1 ) 的填充值)再进行一轮次的计算既可以得出。

下图阐述了上述算法原理

其中标号1为原始数据x，标号2位原始数据x的填充长度，标号3表示新增加的数据，标号4为标号1,2,3的填充和长度。如果我们已知一个计算出来的hash值，同时知道明文的长度，则我们可以构造标号2的数据，标号3，计算未知数md5值的函数（如服务器端的程序），拿到我们构造的标号2和标号3的数据，会自动添加标号4的数据，计算完标号1和和标号2产生ABCD，接着会产生hash值，这时这个hash值就是可以预测。

攻击者可以计算出标号3和标号4，以ABCD作为输入进行计算本地产出的hash值和服务端计算出的hash值是一致的。

攻击者的视角如下图所示。

1、攻击者提供标号2，标号3，标号4的数据

2、服务端计算到标号2的位置刚好为ABCD这个已知数据

3、攻击者在本地根据标号3和标号4的数据和ABCD值计算hash值攻击成功

而服务端的视角是，攻击者提供了标号2和标号3的数据，服务端计算了标号4的数据，同时服务端产出ABCD，发现没有计算完成，接着运行md5算法，计算出的新的hash值和攻击者一致。

综上所述要想进行此类攻击需要知道两个条件

1、标号1数据的长度。

2、标号1数据的md5值。

最后总结一下攻击步骤

第一步：根据标号1的长度计算标号2的数据，提供标号3的数据，本地计算标号4 的数据，并计算加上标号3和标号4数据后的hash值。

第二步：发送计算出来的hash，和标号2，标号3的数据，攻击成功。

3）程序展示

展示python编写的MD5程序和md5扩展攻击的程序

1. 
   
2. #-*- coding=utf-8 -*-
   
3. import math
   
4. 
   
5. def my_md5_extend(salt_hash,  salt_length, added_message):
   
6.     #计算需要填充的数据
   
7.     added_data = [0x80];
   
8.     x = salt_length + 1;
   
9.     while (x + 8) % 64 != 0:
   
10.         x += 1;
    
11.         added_data.append(0x00);
    
12.     salt_length *= 8;
    
13.     salt_length = salt_length  % (2 ** 64);
    
14.     salt_length = hex(salt_length);
    
15.     salt_length = salt_length[2:len(salt_length)-1].rjust(16, '0');
    
16.     salt_length = [int(format(salt_length[i:i+2]), 16) for i in xrange(0, len(salt_length), 2)][::-1]
    
17.     #下面的数据用于加在payload后面
    
18.     added_data.extend(salt_length); #important
    
19.     #打印payload
    
20.     print ''.join(['%' + hex(item).replace('0x', '').rjust(2,'0') for item in added_data])
    
21.    
    
22.     #增加新加的数据，然后使用已经md5的数据进行扩展计算，计算出来一个新的hash值
    
23.     myord = map(ord, added_message);
    
24.     myord.append(0x80);
    
25.     added_length = (x + 8 + len(added_message)) ;
    
26.     y = x + 8 + len(added_message) + 1;
    
27.     while (y + 8) % 64 != 0:
    
28.         y += 1;
    
29.         myord.append(0x00);
    
30.         
    
31.     added_length *= 8;
    
32.     added_length = added_length  % (2 ** 64);
    
33.     added_length = hex(added_length);
    
34.     added_length = added_length[2:len(added_length)-1].rjust(16, '0');
    
35.     added_length = [int(format(added_length[i:i+2]), 16) for i in xrange(0, len(added_length), 2)][::-1]
    
36.     myord.extend(added_length);
    
37.    
    
38.     #使用已经计算出来的hash
    
39.     myA, myB, myC, myD = ( int(salt_hash[i +6: i + 8] +salt_hash[i + 4: i + 6] +salt_hash[i + 2:i + 4] +salt_hash[i + 0 : i + 2], 16)  for i in xrange(0, len(salt_hash), 8));
    
40.    
    
41.     A = myA;
    
42.     B = myB;
    
43.     C = myC;
    
44.     D = myD;
    
45.    
    
46.     F = lambda x,y,z:((x&y)|((~x)&z))  
    
47.     G = lambda x,y,z:((x&z)|(y&(~z)))  
    
48.     H = lambda x,y,z:(x^y^z)  
    
49.     I = lambda x,y,z:(y^(x|(~z)))  
    
50. 
    
51.     T_func = lambda i: int(4294967296*abs(math.sin(i))) & 0xffffffff
    
52. 
    
53.     T = [T_func(i) for i in xrange(1, 65)]
    
54.     T.insert(0 , 0)
    
55.     #进行hash计算
    
56.     for i in xrange(0, len(myord) / 64):
    
57.         INPUT_A = A
    
58.         INPUT_B = B
    
59.         INPUT_C = C
    
60.         INPUT_D = D
    
61.         
    
62.         M = [ (myord[i * 64 + j + 3] <<24) +  (myord[i * 64 + j + 2] << 16 )+ (myord[i * 64 + j + 1] << 8) + (myord[i * 64 + j + 0] )\
    
63.              for j in xrange(0, 64, 4)]
    
64. 
    
65.         def shift(a, count):
    
66.             return (((a << count) | (a >> (32 -count)))&0xffffffff)
    
67.         
    
68.         #第一轮
    
69.         A = (B+ shift((A+F(B,C,D)+M[0]+T[1]) &0xffffffff,7) ) & 0xffffffff
    
70.         D = (A+shift((D+F(A,B,C)+M[1]+T[2]) &0xffffffff ,12) )& 0xffffffff
    
71.         C = (D+shift((C+F(D,A,B)+M[2]+T[3]) &0xffffffff,17) ) &0xffffffff
    
72. 
    
73.         B = (C+shift((B+F(C,D,A)+M[3]+T[4]) &0xffffffff,22) )&0xffffffff
    
74. 
    
75.         A = (B+shift((A+F(B,C,D)+M[4]+T[5]) &0xffffffff,7) )&0xffffffff
    
76. 
    
77.         D = (A+shift((D+F(A,B,C)+M[5]+T[6])&0xffffffff,12) )&0xffffffff
    
78. 
    
79.         C = (D+shift((C+F(D,A,B)+M[6]+T[7]) &0xffffffff,17) )&0xffffffff
    
80. 
    
81.         B = (C+shift((B+F(C,D,A)+M[7]+T[8]) &0xffffffff,22) )&0xffffffff
    
82.         A = (B+shift((A+F(B,C,D)+M[8]+T[9])&0xffffffff,7) )&0xffffffff
    
83. 
    
84.         D = (A+shift((D+F(A,B,C)+M[9]+T[10])&0xffffffff,12) )&0xffffffff
    
85.         C = (D+shift((C+F(D,A,B)+M[10]+T[11])&0xffffffff,17) )&0xffffffff
    
86. 
    
87.         B = (C+shift((B+F(C,D,A)+M[11]+T[12])&0xffffffff,22) )&0xffffffff
    
88.         A = (B+shift((A+F(B,C,D)+M[12]+T[13])&0xffffffff,7) )&0xffffffff
    
89. 
    
90.         D = (A+shift((D+F(A,B,C)+M[13]+T[14])&0xffffffff,12) )&0xffffffff
    
91. 
    
92.         C = (D+shift((C+F(D,A,B)+M[14]+T[15])&0xffffffff,17) )&0xffffffff
    
93. 
    
94.         B = (C+shift((B+F(C,D,A)+M[15]+T[16])&0xffffffff,22) )&0xffffffff
    
95. 
    
96.         #第二轮
    
97.         A = (B+shift((A+G(B,C,D)+M[1]+T[17])&0xffffffff,5) )&0xffffffff
    
98. 
    
99.         D = (A+shift((D+G(A,B,C)+M[6]+T[18]) &0xffffffff,9) )&0xffffffff
    
100. 
     
101.         C = (D+shift((C+G(D,A,B)+M[11]+T[19])&0xffffffff,14) )&0xffffffff
     
102. 
     
103.         B = (C+shift((B+G(C,D,A)+M[0]+T[20])&0xffffffff,20) )&0xffffffff
     
104. 
     
105.         A = (B+shift((A+G(B,C,D)+M[5]+T[21])&0xffffffff,5) )&0xffffffff
     
106. 
     
107.         D = (A+shift((D+G(A,B,C)+M[10]+T[22])&0xffffffff,9) )&0xffffffff
     
108. 
     
109.         C = (D+shift((C+G(D,A,B)+M[15]+T[23])&0xffffffff,14) )&0xffffffff
     
110. 
     
111.         B = (C+shift((B+G(C,D,A)+M[4]+T[24])&0xffffffff,20) )&0xffffffff
     
112. 
     
113.         A = (B+shift((A+G(B,C,D)+M[9]+T[25])&0xffffffff,5) )&0xffffffff
     
114. 
     
115.         D = (A+shift((D+G(A,B,C)+M[14]+T[26])&0xffffffff,9) )&0xffffffff
     
116. 
     
117.         C = (D+shift((C+G(D,A,B)+M[3]+T[27])&0xffffffff,14) )&0xffffffff
     
118. 
     
119.         B = (C+shift((B+G(C,D,A)+M[8]+T[28])&0xffffffff,20) )&0xffffffff
     
120. 
     
121.         A = (B+shift((A+G(B,C,D)+M[13]+T[29])&0xffffffff,5) )&0xffffffff
     
122. 
     
123.         D = (A+shift((D+G(A,B,C)+M[2]+T[30])&0xffffffff,9) )&0xffffffff
     
124. 
     
125.         C = (D+shift((C+G(D,A,B)+M[7]+T[31])&0xffffffff,14) )&0xffffffff
     
126. 
     
127.         B = (C+shift((B+G(C,D,A)+M[12]+T[32])&0xffffffff,20))&0xffffffff
     
128. 
     
129.         #第三轮
     
130.         A = (B+shift((A+H(B,C,D)+M[5]+T[33])&0xffffffff,4) )&0xffffffff
     
131. 
     
132.         D = (A+shift((D+H(A,B,C)+M[8]+T[34])&0xffffffff,11) )&0xffffffff
     
133. 
     
134.         C = (D+shift((C+H(D,A,B)+M[11]+T[35])&0xffffffff,16) )&0xffffffff
     
135. 
     
136.         B = (C+shift((B+H(C,D,A)+M[14]+T[36])&0xffffffff,23) )&0xffffffff
     
137. 
     
138.         A = (B+shift((A+H(B,C,D)+M[1]+T[37])&0xffffffff,4) )&0xffffffff
     
139. 
     
140.         D = (A+shift((D+H(A,B,C)+M[4]+T[38])&0xffffffff,11) )&0xffffffff
     
141. 
     
142.         C = (D+shift((C+H(D,A,B)+M[7]+T[39])&0xffffffff,16) )&0xffffffff
     
143. 
     
144.         B = (C+shift((B+H(C,D,A)+M[10]+T[40])&0xffffffff,23) )&0xffffffff
     
145. 
     
146.         A = (B+shift((A+H(B,C,D)+M[13]+T[41])&0xffffffff,4) )&0xffffffff
     
147. 
     
148.         D = (A+shift((D+H(A,B,C)+M[0]+T[42])&0xffffffff,11) )&0xffffffff
     
149. 
     
150.         C = (D+shift((C+H(D,A,B)+M[3]+T[43])&0xffffffff,16) )&0xffffffff
     
151. 
     
152.         B = (C+shift((B+H(C,D,A)+M[6]+T[44])&0xffffffff,23) )&0xffffffff
     
153. 
     
154.         A = (B+shift((A+H(B,C,D)+M[9]+T[45])&0xffffffff,4) )&0xffffffff
     
155. 
     
156.         D = (A+shift((D+H(A,B,C)+M[12]+T[46])&0xffffffff,11) )&0xffffffff
     
157. 
     
158.         C = (D+shift((C+H(D,A,B)+M[15]+T[47])&0xffffffff,16) )&0xffffffff
     
159. 
     
160.         B = (C+shift((B+H(C,D,A)+M[2]+T[48])&0xffffffff,23))&0xffffffff
     
161. 
     
162.         #第四轮
     
163. 
     
164.         A = (B+shift((A+I(B,C,D)+M[0]+T[49])&0xffffffff,6) )&0xffffffff
     
165. 
     
166.         D = (A+shift((D+I(A,B,C)+M[7]+T[50])&0xffffffff,10) )&0xffffffff
     
167. 
     
168.         C = (D+shift((C+I(D,A,B)+M[14]+T[51])&0xffffffff,15) )&0xffffffff
     
169. 
     
170.         B = (C+shift((B+I(C,D,A)+M[5]+T[52])&0xffffffff,21) )&0xffffffff
     
171. 
     
172.         A = (B+shift((A+I(B,C,D)+M[12]+T[53])&0xffffffff,6) )&0xffffffff
     
173. 
     
174.         D = (A+shift((D+I(A,B,C)+M[3]+T[54])&0xffffffff,10) )&0xffffffff
     
175. 
     
176.         C = (D+shift((C+I(D,A,B)+M[10]+T[55])&0xffffffff,15) )&0xffffffff
     
177. 
     
178.         B = (C+shift((B+I(C,D,A)+M[1]+T[56])&0xffffffff,21) )&0xffffffff
     
179. 
     
180.         A = (B+shift((A+I(B,C,D)+M[8]+T[57])&0xffffffff,6) )&0xffffffff
     
181. 
     
182.         D = (A+shift((D+I(A,B,C)+M[15]+T[58])&0xffffffff,10) )&0xffffffff
     
183. 
     
184.         C = (D+shift((C+I(D,A,B)+M[6]+T[59])&0xffffffff,15) )&0xffffffff
     
185. 
     
186.         B = (C+shift((B+I(C,D,A)+M[13]+T[60])&0xffffffff,21) )&0xffffffff
     
187. 
     
188.         A = (B+shift((A+I(B,C,D)+M[4]+T[61])&0xffffffff,6) )&0xffffffff
     
189. 
     
190.         D = (A+shift((D+I(A,B,C)+M[11]+T[62])&0xffffffff,10) )&0xffffffff
     
191. 
     
192.         C = (D+shift((C+I(D,A,B)+M[2]+T[63])&0xffffffff,15) )&0xffffffff
     
193. 
     
194.         B = (C+shift((B+I(C,D,A)+M[9]+T[64])&0xffffffff,21))&0xffffffff
     
195.         A = (A + INPUT_A) & 0xffffffff
     
196.         B = (B + INPUT_B) & 0xffffffff
     
197.         C = (C + INPUT_C) & 0xffffffff
     
198.         D = (D + INPUT_D) & 0xffffffff
     
199.         
     
200.     def show_result(A, B, C, D):
     
201.         result = "";
     
202.         mya = [hex(A)[2:len(hex(A)[2:]) if hex(A).find('L') == -1 else -1].rjust(8, '0')[k:k+2] for k in xrange(0, 8, 2)][::-1]
     
203.         myb = [hex(B)[2:len(hex(B)[2:]) if hex(B).find('L') == -1 else -1].rjust(8, '0')[k:k+2] for k in xrange(0, 8, 2)][::-1]
     
204.         myc = [hex(C)[2:len(hex(C)[2:]) if hex(C).find('L') == -1 else -1].rjust(8, '0')[k:k+2] for k in xrange(0, 8, 2)][::-1]
     
205.         myd = [hex(D)[2:len(hex(D)[2:]) if hex(D).find('L') == -1 else -1].rjust(8, '0')[k:k+2] for k in xrange(0, 8, 2)][::-1]
     
206.         return ''.join(mya + myb + myc + myd)
     
207.     return show_result(A, B, C, D);
     
208.    
     
209.         
     
210. 
     
211. 
     
212. 
     
213. print my_md5_extend('571580b26c65f306376d4f64e53cb5c7', 15 + len('adminadmin'), 'nb');
     
214. 
     
215. 
     
216. def my_md5(mystring):
     
217.     #第一步填充
     
218.     #mystring = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
     
219.     myord =map(ord, mystring);#转化成为16进制的array
     
220.     myord_length = len(myord) * 8;
     
221.     myord.append(0x80);
     
222. 
     
223.     while (len(myord) * 8 + 64 )% 512 != 0:
     
224.         myord.append(0x00);
     
225. 
     
226. 
     
227.     #第二步增加长度
     
228.     myord_length = myord_length % (2 ** 64);
     
229.    
     
230.     myord_length = hex(myord_length);
     
231.    
     
232.     myord_length = myord_length[2:len(myord_length)-1].rjust(16, '0');
     
233.    
     
234.     myord_length = [int(format(myord_length[i:i+2]), 16) for i in xrange(0, len(myord_length), 2)][::-1]
     
235.    
     
236.     myord.extend(myord_length)
     
237. 
     
238. 
     
239.     #对每一个512位做处理
     
240.     A = 0x67452301
     
241.     B = 0xefcdab89
     
242.     C = 0x98badcfe
     
243.     D = 0x10325476
     
244. 
     
245.     F = lambda x,y,z:((x&y)|((~x)&z))  
     
246.     G = lambda x,y,z:((x&z)|(y&(~z)))  
     
247.     H = lambda x,y,z:(x^y^z)  
     
248.     I = lambda x,y,z:(y^(x|(~z)))  
     
249. 
     
250.     T_func = lambda i: int(4294967296*abs(math.sin(i))) & 0xffffffff
     
251. 
     
252.     T = [T_func(i) for i in xrange(1, 65)]
     
253.     T.insert(0 , 0)#错误的位置
     
254. 
     
255.     for i in xrange(0, len(myord) / 64):
     
256.         INPUT_A = A
     
257.         INPUT_B = B
     
258.         INPUT_C = C
     
259.         INPUT_D = D
     
260.         
     
261.         M = [ (myord[i * 64 + j + 3] <<24) +  (myord[i * 64 + j + 2] << 16 )+ (myord[i * 64 + j + 1] << 8) + (myord[i * 64 + j + 0] )\
     
262.              for j in xrange(0, 64, 4)]
     
263. 
     
264.         def shift(a, count):
     
265.             return (((a << count) | (a >> (32 -count)))&0xffffffff)
     
266.         
     
267.         #第一轮
     
268.         A = (B+ shift((A+F(B,C,D)+M[0]+T[1]) &0xffffffff,7) ) & 0xffffffff
     
269.         D = (A+shift((D+F(A,B,C)+M[1]+T[2]) &0xffffffff ,12) )& 0xffffffff
     
270.         C = (D+shift((C+F(D,A,B)+M[2]+T[3]) &0xffffffff,17) ) &0xffffffff
     
271. 
     
272.         B = (C+shift((B+F(C,D,A)+M[3]+T[4]) &0xffffffff,22) )&0xffffffff
     
273. 
     
274.         A = (B+shift((A+F(B,C,D)+M[4]+T[5]) &0xffffffff,7) )&0xffffffff
     
275. 
     
276.         D = (A+shift((D+F(A,B,C)+M[5]+T[6])&0xffffffff,12) )&0xffffffff
     
277. 
     
278.         C = (D+shift((C+F(D,A,B)+M[6]+T[7]) &0xffffffff,17) )&0xffffffff
     
279. 
     
280.         B = (C+shift((B+F(C,D,A)+M[7]+T[8]) &0xffffffff,22) )&0xffffffff
     
281.         A = (B+shift((A+F(B,C,D)+M[8]+T[9])&0xffffffff,7) )&0xffffffff
     
282. 
     
283.         D = (A+shift((D+F(A,B,C)+M[9]+T[10])&0xffffffff,12) )&0xffffffff
     
284.         C = (D+shift((C+F(D,A,B)+M[10]+T[11])&0xffffffff,17) )&0xffffffff
     
285. 
     
286.         B = (C+shift((B+F(C,D,A)+M[11]+T[12])&0xffffffff,22) )&0xffffffff
     
287.         A = (B+shift((A+F(B,C,D)+M[12]+T[13])&0xffffffff,7) )&0xffffffff
     
288. 
     
289.         D = (A+shift((D+F(A,B,C)+M[13]+T[14])&0xffffffff,12) )&0xffffffff
     
290. 
     
291.         C = (D+shift((C+F(D,A,B)+M[14]+T[15])&0xffffffff,17) )&0xffffffff
     
292. 
     
293.         B = (C+shift((B+F(C,D,A)+M[15]+T[16])&0xffffffff,22) )&0xffffffff
     
294. 
     
295.         #第二轮
     
296.         A = (B+shift((A+G(B,C,D)+M[1]+T[17])&0xffffffff,5) )&0xffffffff
     
297. 
     
298.         D = (A+shift((D+G(A,B,C)+M[6]+T[18]) &0xffffffff,9) )&0xffffffff
     
299. 
     
300.         C = (D+shift((C+G(D,A,B)+M[11]+T[19])&0xffffffff,14) )&0xffffffff
     
301. 
     
302.         B = (C+shift((B+G(C,D,A)+M[0]+T[20])&0xffffffff,20) )&0xffffffff
     
303. 
     
304.         A = (B+shift((A+G(B,C,D)+M[5]+T[21])&0xffffffff,5) )&0xffffffff
     
305. 
     
306.         D = (A+shift((D+G(A,B,C)+M[10]+T[22])&0xffffffff,9) )&0xffffffff
     
307. 
     
308.         C = (D+shift((C+G(D,A,B)+M[15]+T[23])&0xffffffff,14) )&0xffffffff
     
309. 
     
310.         B = (C+shift((B+G(C,D,A)+M[4]+T[24])&0xffffffff,20) )&0xffffffff
     
311. 
     
312.         A = (B+shift((A+G(B,C,D)+M[9]+T[25])&0xffffffff,5) )&0xffffffff
     
313. 
     
314.         D = (A+shift((D+G(A,B,C)+M[14]+T[26])&0xffffffff,9) )&0xffffffff
     
315. 
     
316.         C = (D+shift((C+G(D,A,B)+M[3]+T[27])&0xffffffff,14) )&0xffffffff
     
317. 
     
318.         B = (C+shift((B+G(C,D,A)+M[8]+T[28])&0xffffffff,20) )&0xffffffff
     
319. 
     
320.         A = (B+shift((A+G(B,C,D)+M[13]+T[29])&0xffffffff,5) )&0xffffffff
     
321. 
     
322.         D = (A+shift((D+G(A,B,C)+M[2]+T[30])&0xffffffff,9) )&0xffffffff
     
323. 
     
324.         C = (D+shift((C+G(D,A,B)+M[7]+T[31])&0xffffffff,14) )&0xffffffff
     
325. 
     
326.         B = (C+shift((B+G(C,D,A)+M[12]+T[32])&0xffffffff,20))&0xffffffff
     
327. 
     
328.         #第三轮
     
329.         A = (B+shift((A+H(B,C,D)+M[5]+T[33])&0xffffffff,4) )&0xffffffff
     
330. 
     
331.         D = (A+shift((D+H(A,B,C)+M[8]+T[34])&0xffffffff,11) )&0xffffffff
     
332. 
     
333.         C = (D+shift((C+H(D,A,B)+M[11]+T[35])&0xffffffff,16) )&0xffffffff
     
334. 
     
335.         B = (C+shift((B+H(C,D,A)+M[14]+T[36])&0xffffffff,23) )&0xffffffff
     
336. 
     
337.         A = (B+shift((A+H(B,C,D)+M[1]+T[37])&0xffffffff,4) )&0xffffffff
     
338. 
     
339.         D = (A+shift((D+H(A,B,C)+M[4]+T[38])&0xffffffff,11) )&0xffffffff
     
340. 
     
341.         C = (D+shift((C+H(D,A,B)+M[7]+T[39])&0xffffffff,16) )&0xffffffff
     
342. 
     
343.         B = (C+shift((B+H(C,D,A)+M[10]+T[40])&0xffffffff,23) )&0xffffffff
     
344. 
     
345.         A = (B+shift((A+H(B,C,D)+M[13]+T[41])&0xffffffff,4) )&0xffffffff
     
346. 
     
347.         D = (A+shift((D+H(A,B,C)+M[0]+T[42])&0xffffffff,11) )&0xffffffff
     
348. 
     
349.         C = (D+shift((C+H(D,A,B)+M[3]+T[43])&0xffffffff,16) )&0xffffffff
     
350. 
     
351.         B = (C+shift((B+H(C,D,A)+M[6]+T[44])&0xffffffff,23) )&0xffffffff
     
352. 
     
353.         A = (B+shift((A+H(B,C,D)+M[9]+T[45])&0xffffffff,4) )&0xffffffff
     
354. 
     
355.         D = (A+shift((D+H(A,B,C)+M[12]+T[46])&0xffffffff,11) )&0xffffffff
     
356. 
     
357.         C = (D+shift((C+H(D,A,B)+M[15]+T[47])&0xffffffff,16) )&0xffffffff
     
358. 
     
359.         B = (C+shift((B+H(C,D,A)+M[2]+T[48])&0xffffffff,23))&0xffffffff
     
360. 
     
361.         #第四轮
     
362. 
     
363.         A = (B+shift((A+I(B,C,D)+M[0]+T[49])&0xffffffff,6) )&0xffffffff
     
364.         D = (A+shift((D+I(A,B,C)+M[7]+T[50])&0xffffffff,10) )&0xffffffff
     
365.         C = (D+shift((C+I(D,A,B)+M[14]+T[51])&0xffffffff,15) )&0xffffffff
     
366.         B = (C+shift((B+I(C,D,A)+M[5]+T[52])&0xffffffff,21) )&0xffffffff
     
367.         A = (B+shift((A+I(B,C,D)+M[12]+T[53])&0xffffffff,6) )&0xffffffff
     
368.         D = (A+shift((D+I(A,B,C)+M[3]+T[54])&0xffffffff,10) )&0xffffffff
     
369.         C = (D+shift((C+I(D,A,B)+M[10]+T[55])&0xffffffff,15) )&0xffffffff
     
370.         B = (C+shift((B+I(C,D,A)+M[1]+T[56])&0xffffffff,21) )&0xffffffff
     
371.         A = (B+shift((A+I(B,C,D)+M[8]+T[57])&0xffffffff,6) )&0xffffffff
     
372.         D = (A+shift((D+I(A,B,C)+M[15]+T[58])&0xffffffff,10) )&0xffffffff
     
373.         C = (D+shift((C+I(D,A,B)+M[6]+T[59])&0xffffffff,15) )&0xffffffff
     
374.         B = (C+shift((B+I(C,D,A)+M[13]+T[60])&0xffffffff,21) )&0xffffffff
     
375.         A = (B+shift((A+I(B,C,D)+M[4]+T[61])&0xffffffff,6) )&0xffffffff
     
376.         D = (A+shift((D+I(A,B,C)+M[11]+T[62])&0xffffffff,10) )&0xffffffff
     
377.         C = (D+shift((C+I(D,A,B)+M[2]+T[63])&0xffffffff,15) )&0xffffffff
     
378.         B = (C+shift((B+I(C,D,A)+M[9]+T[64])&0xffffffff,21))&0xffffffff
     
379.         A = (A + INPUT_A) & 0xffffffff
     
380.         B = (B + INPUT_B) & 0xffffffff
     
381.         C = (C + INPUT_C) & 0xffffffff
     
382.         D = (D + INPUT_D) & 0xffffffff
     
383.         
     
384.     def show_result(A, B, C, D):
     
385.         result = "";
     
386.         mya = [hex(A)[2:len(hex(A)[2:]) if hex(A).find('L') == -1 else -1].rjust(8, '0')[k:k+2] for k in xrange(0, 8, 2)][::-1]
     
387.         myb = [hex(B)[2:len(hex(B)[2:]) if hex(B).find('L') == -1 else -1].rjust(8, '0')[k:k+2] for k in xrange(0, 8, 2)][::-1]
     
388.         myc = [hex(C)[2:len(hex(C)[2:]) if hex(C).find('L') == -1 else -1].rjust(8, '0')[k:k+2] for k in xrange(0, 8, 2)][::-1]
     
389.         myd = [hex(D)[2:len(hex(D)[2:]) if hex(D).find('L') == -1 else -1].rjust(8, '0')[k:k+2] for k in xrange(0, 8, 2)][::-1]
     
390.         return ''.join(mya + myb + myc + myd)
     
391.     return show_result(A, B, C, D);

复制代码

4）结语

在做ctf题目的时候加强对原理的理解，和动手实践，文字总结的方式可以帮助记忆。