小生归一（五）md5扩展长度攻击

Power7089

发布于 2020-07-27 16:47:24

1.2K0

发布于 2020-07-27 16:47:24

文章被收录于专栏：闪石星曜CyberSecurity闪石星曜CyberSecurity

此文章为原创连载文章，关注公众号，持续更新。

欢迎投稿及转载，标明来源作者即可。

1、md5加密原理

原python与安全系列续

又到了小生归一的笔记分享~有人期待嘛~

1、MD5加密过程中512比特（64字节）为一组，属于分组加密，而且在运算的过程中，将512比特分为32bit*16块，分块运算。(先把需要加密的进行ASCII16进制编码)

2、我们关键利用的是MD5的填充，对加密的字符串进行填充(比特第一位为1其余比特为0)，使之(二进制)补到448模512同余，即长度为512的倍数减64，最后的64位再补充为原来字符串的长度，这样刚好补满512位的倍数，如果当前明文正好是512bit倍数则再加上一个512bit的一组。

3、这里每一个512位称为一个分组，又将每一个512位分为16个32位，称为一个子分组（M0~M15）。之后进行4轮运算，每一轮进行16次操作，分别针对这16个子分组。原消息有几个分组就进行几次循环。

MD5不管怎么加密，每一次循环加密得到的密文作为下一次加密的初始向量IV，这一点很关键！！！第一次循环是128位序列初始向量位4个32(十六进制)位向量：A=01234567h;B=89abcdefh;C=fedcba98h;D=76543210h。注意这些变量在内存中的顺序是低值存放低字节，所以在程序中应该是：A=0x67452301;B=0xefcdab89;C=0x98badcfe;D=0x10325476.最后结果再次反转到正常顺序后输出即可。

2、一次循环运算过程

这四轮运算需要用到一个常数表，这些常数T[i]（i=1~64）等于4294967296*abs(sin(i))所得结果的整数部分，其中i用弧度表示。这样做是为了通过正弦函数和幂函数来进一步消除变换中的线性。

首先我们保存A,B,C,D。

INPUT_A=A

INPUT_B=B

INPUT_C=C

INPUT_D=D

第一轮

（注：公式中的<<<表示循环左移）

用到的函数：F(X,Y,Z)=(X&Y)|((~X)&Z)

A= B+((A+F(B,C,D)+M[0]+T[1])<<<7)

D= A+((D+F(A,B,C)+M[1]+T[2])<<<12)

C= D+((C+F(D,A,B)+M[2]+T[3])<<<17)

B= C+((B+F(C,D,A)+M[3]+T[4])<<<22)

A= B+((A+F(B,C,D)+M[4]+T[5])<<<7)

D= A+((D+F(A,B,C)+M[5]+T[6])<<<12)

C= D+((C+F(D,A,B)+M[6]+T[7])<<<17)

B= C+((B+F(C,D,A)+M[7]+T[8])<<<22)

A= B+((A+F(B,C,D)+M[8]+T[9])<<<7)

D= A+((D+F(A,B,C)+M[9]+T[10])<<<12)

C= D+((C+F(D,A,B)+M[10]+T[11])<<<17)

B= C+((B+F(C,D,A)+M[11]+T[12])<<<22)

A= B+((A+F(B,C,D)+M[12]+T[13])<<<7)

D= A+((D+F(A,B,C)+M[13]+T[14])<<<12)

C= D+((C+F(D,A,B)+M[14]+T[15])<<<17)

B= C+((B+F(C,D,A)+M[15]+T[16])<<<22)

第二轮

用到的函数：G(X,Y,Z)=(X&Z)|(Y&(~Z))

A= B+((A+G(B,C,D)+M[1]+T[17])<<<5)

D= A+((D+G(A,B,C)+M[6]+T[18])<<<9)

C= D+((C+G(D,A,B)+M[11]+T[19])<<<14)

B= C+((B+G(C,D,A)+M[0]+T[20])<<<20)

A= B+((A+G(B,C,D)+M[5]+T[21])<<<5)

D= A+((D+G(A,B,C)+M[10]+T[22])<<<9)

C= D+((C+G(D,A,B)+M[15]+T[23])<<<14)

B= C+((B+G(C,D,A)+M[4]+T[24])<<<20)

A= B+((A+G(B,C,D)+M[9]+T[25])<<<5)

D= A+((D+G(A,B,C)+M[14]+T[26])<<<9)

C= D+((C+G(D,A,B)+M[3]+T[27])<<<14)

B= C+((B+G(C,D,A)+M[8]+T[28])<<<20)

A= B+((A+G(B,C,D)+M[13]+T[29])<<<5)

D= A+((D+G(A,B,C)+M[2]+T[30])<<<9)

C= D+((C+G(D,A,B)+M[7]+T[31])<<<14)

B= C+((B+G(C,D,A)+M[12]+T[32])<<<20)

第三轮

用到的函数：H(X,Y,Z)=X^Y^Z

A= B+((A+H(B,C,D)+M[5]+T[33])<<<4)

D= A+((D+H(A,B,C)+M[8]+T[34])<<<11)

C= D+((C+H(D,A,B)+M[11]+T[35])<<<16)

B= C+((B+H(C,D,A)+M[14]+T[36])<<<23)

A= B+((A+H(B,C,D)+M[1]+T[37])<<<4)

D= A+((D+H(A,B,C)+M[4]+T[38])<<<11)

C= D+((C+H(D,A,B)+M[7]+T[39])<<<16)

B= C+((B+H(C,D,A)+M[10]+T[40])<<<23)

A= B+((A+H(B,C,D)+M[13]+T[41])<<<4)

D= A+((D+H(A,B,C)+M[0]+T[42])<<<11)

C= D+((C+H(D,A,B)+M[3]+T[43])<<<16)

B= C+((B+H(C,D,A)+M[6]+T[44])<<<23)

A= B+((A+H(B,C,D)+M[9]+T[45])<<<4)

D= A+((D+H(A,B,C)+M[12]+T[46])<<<11)

C= D+((C+H(D,A,B)+M[15]+T[47])<<<16)

B= C+((B+H(C,D,A)+M[2]+T[48])<<<23)

第四轮

用到的函数：I(X,Y,Z)=Y^(X|(~Z))

A= B+((A+I(B,C,D)+M[0]+T[33])<<<6)

D= A+((D+I(A,B,C)+M[7]+T[34])<<<10)

C= D+((C+I(D,A,B)+M[14]+T[35])<<<15)

B= C+((B+I(C,D,A)+M[5]+T[36])<<<21)

A= B+((A+I(B,C,D)+M[12]+T[37])<<<6)

D= A+((D+I(A,B,C)+M[3]+T[38])<<<10)

C= D+((C+I(D,A,B)+M[10]+T[39])<<<15)

B= C+((B+I(C,D,A)+M[1]+T[40])<<<21)

A= B+((A+I(B,C,D)+M[8]+T[41])<<<6)

D= A+((D+I(A,B,C)+M[15]+T[42])<<<10)

C= D+((C+I(D,A,B)+M[6]+T[43])<<<15)

B= C+((B+I(C,D,A)+M[13]+T[44])<<<21)

A= B+((A+I(B,C,D)+M[4]+T[45])<<<6)

D= A+((D+I(A,B,C)+M[11]+T[46])<<<10)

C= D+((C+I(D,A,B)+M[2]+T[47])<<<15)

B= C+((B+I(C,D,A)+M[9]+T[48])<<<21)

四轮运算完成后，将此时的ABCD与原始输入分别相加。

a= A + INPUT_A

b= B + INPUT_B

c= C + INPUT_C

d= D + INPUT_D

最终得到的a,b,c,d以为下次循环运算的初始向量或最终输出的雏形。

这里

(https://github.com/shrewdnoob/webCTF/blob/master/md5encode.py)是自己写的

python3版的md5加密脚本，可以更好的理解md5加密过程。由于太长了，就没有贴出来。

3、攻击原理

假如我们有md5($key+$data)==md5(‘secrettest’)的值：

cb08e6781ef34c8ecb06e1be269a6bdc

$key=secret
$data=test

‘secrettest’分组填充后为

\x73\x65\x63\x72\x65\x74\x74\x65\x73\x74\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x50\x00\x00\x00\x00\x00\x00\x00

我们可以得到填充的

$padding=’\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x50\x00\x00\x00\x00\x00\x00\x00’

md5加密后得到的最后四个向量为

['0x78e608cb','0x8e4cf31e', '0xbee106cb', '0xdc6b9a26']

我们知道所有的md5加密初始向量为

A=0x67452301;B=0xefcdab89;C=0x98badcfe;D=0x10325476

假设我们需要扩展添加的字符串为$add=’aadd’

实现md5扩展长度攻击就是把初始向量改成md5(key+data)得到的最后四个向量：

A=0x78e608cb;B=0x8e4cf31e;C=0xbee106cb;D=0xdc6b9a26

用我前面给的脚本，把ABCD改成上面的，

不过最后64位填充字符串长度时候，字符串的长度不是len($add),而是len($key+$data+$padding+$add)。

所以在我们不知道$key的时候，但是知道

加密结果’cb08e6781ef34c8ecb06e1be269a6bdc’

$key长度和$data

我们就可以进行md5扩展长度攻击

4.攻击利用

我不知道如果你是第一次是否和我一样，看着别人的教程还是很糊涂。

其实上面的过程很简单的理解就是，初始向量不变，还是：

A=0x67452301;B=0xefcdab89;C=0x98badcfe;D=0x10325476

key+data==‘secrettest’分组填充后为

‘\x73\x65\x63\x72\x65\x74\x74\x65\x73\x74\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x50\x00\x00\x00\x00\x00\x00\x00’

直接在后面加个$add=’aadd’就是

‘\x73\x65\x63\x72\x65\x74\x74\x65\x73\x74\x80\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x50\x00\x00\x00\x00\x00\x00\x00aadd’

然后我们就可以用上面的MD5加密得到扩展后的值。