哈希扩展长度攻击

哈希扩展长度攻击

0x00 起于一道CTF

这是一道好题！学了一种新的攻击方法，顺带知道了hash的实现。只不过现在这种攻击方法也只活在ctf中了

首先是改包能够看到源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
flag = “XXXXXXXXXXXXXXXXXXXXXXX”;

$secret = “XXXXXXXXXXXXXXX”; // This secret is 15 characters long for security!

$username = $_POST[“username”];

$password = $_POST[“password”];

if (!empty($_COOKIE[“getmein”])) {

if (urldecode($username) === “admin” && urldecode($password) != “admin”) {

if ($COOKIE[“getmein”] === md5($secret . urldecode($username . $password))) {echo “Congratulations! You are a registered user.\n”;

die (“The flag is “. $flag);}

else {

die (“Your cookies don’t match up! STOP HACKING THIS SITE.”);

}}

else {

die (“You are not an admin! LEAVE.”);}}

setcookie(“sample-hash”, md5($secret . urldecode(“admin” . “admin”)), time() + (60 * 60 * 24 * 7));

if (empty($_COOKIE[“source”])) {

setcookie(“source”, 0, time() + (60 * 60 * 24 * 7));}

else {

if ($_COOKIE[“source”] != 0) {

echo “”; // This source code is outputted here}}

要显示出flag就得要通过这个逻辑：$COOKIE[“getmein”] === md5($secret . urldecode($username . $password)

问题在于不知道secret的值是多少，爆破几乎是不可能的，这里就要用到哈希扩展长度攻击

0x01什么是哈希扩展长度攻击

已知：salt的MD5值，但是不知道str1本身的值

我们可以知道salt+padding+任意字符 的md5值

因为md5的实现中64轮变换每次都是用的上次变换的结果，通过md5可以反向算出最后一次变换的四个值，之后加入到变换函数中，在后面添加任意数据。这样在不知道salt本身值的情况下也能算出salt+padding+任意数据的md5值了

我们需要知道md5的实现过程才能理解这种攻击方式

hash的实现

首先对消息进行分组，每组64个字节，不足64个字节的部分用padding补齐，其中，第一个补充的字节是0x80，之后的都是0x00，padding的最后8个字节用来表示需要哈希的消息长度

defpadding(self,n,sz=None):

ifszisNone:

sz=n

pre=64–8

sz=struct.pack(“Q”,sz*8)

pad=‘\x80‘

n+=1

ifn%64<=pre:

pad+=‘\x00‘*(pre–n%64)

pad+=sz

else:

pad+=‘\x00‘*(pre+64–n%64)

pad+=sz

returnpad

#最后八个字节为数据长度

defpad(self,msg):

returnmsg+self.padding(len(msg))

。

之后开始对每组消息进行压缩，经过64轮的数学变换（位运算的与或非异或、按位左移右移、按位无符号左移右移、进制转换、sin、和0xFF、0xFFFFFFF做与运算保证位数不变等等）每一次变换压缩的结果被当成下一轮变换压缩的初始值。最开始的初始值是由文档规定好的。最后的结果拼在一起就是128位的md5值

四个定义好的变换函数：

F(X,Y,Z) =(X&Y)|((~X)&Z)

G(X,Y,Z) =(X&Z)|(Y&(~Z))

H(X,Y,Z) =X^Y^Z

I(X,Y,Z)=Y^(X|(~Z))

（&是与，|是或，~是非，^是异或）

四个定义好的初始值：

A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210。

变换函数

defXX(func,a,b,c,d,x,s,ac):

res=0L

res=res+a+func(b,c,d)

res=res+x

res=res+ac

res=res&0xffffffffL

res=_rotateLeft(res,s)

res=res&0xffffffffL

res=res+b

returnres&0xffffffffL

defmd5_compress(self,buf):

iflen(buf)!=64:

raiseValueError,“Invalidbufferoflength%d:%s”%(len(buf),repr(buf))

inp=struct.unpack(“I”*16,buf)

a,b,c,d=self.A,self.B,self.C,self.D

#开始进行64轮数学变换,四大轮，每轮16次

#Round1.

S11,S12,S13,S14=7,12,17,22

a=XX(F,a,b,c,d,inp[0],S11,0xD76AA478L)#1

d=XX(F,d,a,b,c,inp[1],S12,0xE8C7B756L)#2

c=XX(F,c,d,a,b,inp[2],S13,0x242070DBL)#3

b=XX(F,b,c,d,a,inp[3],S14,0xC1BDCEEEL)#4

a=XX(F,a,b,c,d,inp[4],S11,0xF57C0FAFL)#5

d=XX(F,d,a,b,c,inp[5],S12,0x4787C62AL)#6

c=XX(F,c,d,a,b,inp[6],S13,0xA8304613L)#7

b=XX(F,b,c,d,a,inp[7],S14,0xFD469501L)#8

a=XX(F,a,b,c,d,inp[8],S11,0x698098D8L)#9

d=XX(F,d,a,b,c,inp[9],S12,0x8B44F7AFL)#10

c=XX(F,c,d,a,b,inp[10],S13,0xFFFF5BB1L)#11

b=XX(F,b,c,d,a,inp[11],S14,0x895CD7BEL)#12

a=XX(F,a,b,c,d,inp[12],S11,0x6B901122L)#13

d=XX(F,d,a,b,c,inp[13],S12,0xFD987193L)#14

c=XX(F,c,d,a,b,inp[14],S13,0xA679438EL)#15

b=XX(F,b,c,d,a,inp[15],S14,0x49B40821L)#16

#Round2.

S21,S22,S23,S24=5,9,14,20

a=XX(G,a,b,c,d,inp[1],S21,0xF61E2562L)#17

d=XX(G,d,a,b,c,inp[6],S22,0xC040B340L)#18

c=XX(G,c,d,a,b,inp[11],S23,0x265E5A51L)#19

b=XX(G,b,c,d,a,inp[0],S24,0xE9B6C7AAL)#20

a=XX(G,a,b,c,d,inp[5],S21,0xD62F105DL)#21

d=XX(G,d,a,b,c,inp[10],S22,0x02441453L)#22

c=XX(G,c,d,a,b,inp[15],S23,0xD8A1E681L)#23

b=XX(G,b,c,d,a,inp[4],S24,0xE7D3FBC8L)#24

a=XX(G,a,b,c,d,inp[9],S21,0x21E1CDE6L)#25

d=XX(G,d,a,b,c,inp[14],S22,0xC33707D6L)#26

c=XX(G,c,d,a,b,inp[3],S23,0xF4D50D87L)#27

b=XX(G,b,c,d,a,inp[8],S24,0x455A14EDL)#28

a=XX(G,a,b,c,d,inp[13],S21,0xA9E3E905L)#29

d=XX(G,d,a,b,c,inp[2],S22,0xFCEFA3F8L)#30

c=XX(G,c,d,a,b,inp[7],S23,0x676F02D9L)#31

b=XX(G,b,c,d,a,inp[12],S24,0x8D2A4C8AL)#32

#Round3.

S31,S32,S33,S34=4,11,16,23

a=XX(H,a,b,c,d,inp[5],S31,0xFFFA3942L)#33

d=XX(H,d,a,b,c,inp[8],S32,0x8771F681L)#34

c=XX(H,c,d,a,b,inp[11],S33,0x6D9D6122L)#35

b=XX(H,b,c,d,a,inp[14],S34,0xFDE5380CL)#36

a=XX(H,a,b,c,d,inp[1],S31,0xA4BEEA44L)#37

d=XX(H,d,a,b,c,inp[4],S32,0x4BDECFA9L)#38

c=XX(H,c,d,a,b,inp[7],S33,0xF6BB4B60L)#39

b=XX(H,b,c,d,a,inp[10],S34,0xBEBFBC70L)#40

a=XX(H,a,b,c,d,inp[13],S31,0x289B7EC6L)#41

d=XX(H,d,a,b,c,inp[0],S32,0xEAA127FAL)#42

c=XX(H,c,d,a,b,inp[3],S33,0xD4EF3085L)#43

b=XX(H,b,c,d,a,inp[6],S34,0x04881D05L)#44

a=XX(H,a,b,c,d,inp[9],S31,0xD9D4D039L)#45

d=XX(H,d,a,b,c,inp[12],S32,0xE6DB99E5L)#46

c=XX(H,c,d,a,b,inp[15],S33,0x1FA27CF8L)#47

b=XX(H,b,c,d,a,inp[2],S34,0xC4AC5665L)#48

#Round4.

S41,S42,S43,S44=6,10,15,21

a=XX(I,a,b,c,d,inp[0],S41,0xF4292244L)#49

d=XX(I,d,a,b,c,inp[7],S42,0x432AFF97L)#50

c=XX(I,c,d,a,b,inp[14],S43,0xAB9423A7L)#51

b=XX(I,b,c,d,a,inp[5],S44,0xFC93A039L)#52

a=XX(I,a,b,c,d,inp[12],S41,0x655B59C3L)#53

d=XX(I,d,a,b,c,inp[3],S42,0x8F0CCC92L)#54

c=XX(I,c,d,a,b,inp[10],S43,0xFFEFF47DL)#55

b=XX(I,b,c,d,a,inp[1],S44,0x85845DD1L)#56

a=XX(I,a,b,c,d,inp[8],S41,0x6FA87E4FL)#57

d=XX(I,d,a,b,c,inp[15],S42,0xFE2CE6E0L)#58

c=XX(I,c,d,a,b,inp[6],S43,0xA3014314L)#59

b=XX(I,b,c,d,a,inp[13],S44,0x4E0811A1L)#60

a=XX(I,a,b,c,d,inp[4],S41,0xF7537E82L)#61

d=XX(I,d,a,b,c,inp[11],S42,0xBD3AF235L)#62

c=XX(I,c,d,a,b,inp[2],S43,0x2AD7D2BBL)#63

b=XX(I,b,c,d,a,inp[9],S44,0xEB86D391L)#64

self.A=(self.A+a)&0xffffffffL

self.B=(self.B+b)&0xffffffffL

self.C=(self.C+c)&0xffffffffL

self.D=(self.D+d)&0xffffffffL

0x02回到题目

这个时候我们通过脚本构造payload，padding的值得是64位

脚本如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
# coding:utf-8
#这是个哈希扩展攻击的payload生成脚本
#python 本文件名字.py salt的md5 附加的值 salt的长度

import sys
import struct
import hashlib
import binascii

#每轮中用到的数学变换函数。L为循环左移，
def F(x, y, z):
    return (x & y) | ((~x) & z)
def G(x, y, z):
    return (x & z) | (y & (~z))
def H(x, y, z):
    return x ^ y ^ z
def I(x, y, z):
    return y ^ (x | (~z))

#注意左移之后可能会超过32位，所以要和0xffffffff做与运算，确保结果为32位。
def _rotateLeft(x, n):
    return (x << n) | (x >> (32 - n))
#变换函数
def XX(func, a, b, c, d, x, s, ac):
    res = 0L
    res = res + a + func(b, c, d)
    res = res + x
    res = res + ac
    res = res & 0xffffffffL
    res = _rotateLeft(res, s)
    res = res & 0xffffffffL
    res = res + b

    return res & 0xffffffffL

# 主类
class md5():
    #初始化向量，这是标准里定死的
    def __init__(self):
        self.A, self.B, self.C, self.D = (0x67452301L, 0xefcdab89L, 0x98badcfeL, 0x10325476L)

    def md5_compress(self, buf):
        if len(buf) != 64:
            raise ValueError, "Invalid buffer of length %d: %s" % (len(buf), repr(buf))
        inp = struct.unpack("I" * 16, buf)
        a, b, c, d = self.A, self.B, self.C, self.D

        #开始进行64轮数学变换,四大轮，每轮16次
        # Round 1.
        S11, S12, S13, S14 = 7, 12, 17, 22

        a = XX(F, a, b, c, d, inp[0], S11, 0xD76AA478L)  # 1
        d = XX(F, d, a, b, c, inp[1], S12, 0xE8C7B756L)  # 2
        c = XX(F, c, d, a, b, inp[2], S13, 0x242070DBL)  # 3
        b = XX(F, b, c, d, a, inp[3], S14, 0xC1BDCEEEL)  # 4
        a = XX(F, a, b, c, d, inp[4], S11, 0xF57C0FAFL)  # 5
        d = XX(F, d, a, b, c, inp[5], S12, 0x4787C62AL)  # 6
        c = XX(F, c, d, a, b, inp[6], S13, 0xA8304613L)  # 7
        b = XX(F, b, c, d, a, inp[7], S14, 0xFD469501L)  # 8
        a = XX(F, a, b, c, d, inp[8], S11, 0x698098D8L)  # 9
        d = XX(F, d, a, b, c, inp[9], S12, 0x8B44F7AFL)  # 10
        c = XX(F, c, d, a, b, inp[10], S13, 0xFFFF5BB1L)  # 11
        b = XX(F, b, c, d, a, inp[11], S14, 0x895CD7BEL)  # 12
        a = XX(F, a, b, c, d, inp[12], S11, 0x6B901122L)  # 13
        d = XX(F, d, a, b, c, inp[13], S12, 0xFD987193L)  # 14
        c = XX(F, c, d, a, b, inp[14], S13, 0xA679438EL)  # 15
        b = XX(F, b, c, d, a, inp[15], S14, 0x49B40821L)  # 16

        # Round 2.
        S21, S22, S23, S24 = 5, 9, 14, 20

        a = XX(G, a, b, c, d, inp[1], S21, 0xF61E2562L)  # 17
        d = XX(G, d, a, b, c, inp[6], S22, 0xC040B340L)  # 18
        c = XX(G, c, d, a, b, inp[11], S23, 0x265E5A51L)  # 19
        b = XX(G, b, c, d, a, inp[0], S24, 0xE9B6C7AAL)  # 20
        a = XX(G, a, b, c, d, inp[5], S21, 0xD62F105DL)  # 21
        d = XX(G, d, a, b, c, inp[10], S22, 0x02441453L)  # 22
        c = XX(G, c, d, a, b, inp[15], S23, 0xD8A1E681L)  # 23
        b = XX(G, b, c, d, a, inp[4], S24, 0xE7D3FBC8L)  # 24
        a = XX(G, a, b, c, d, inp[9], S21, 0x21E1CDE6L)  # 25
        d = XX(G, d, a, b, c, inp[14], S22, 0xC33707D6L)  # 26
        c = XX(G, c, d, a, b, inp[3], S23, 0xF4D50D87L)  # 27
        b = XX(G, b, c, d, a, inp[8], S24, 0x455A14EDL)  # 28
        a = XX(G, a, b, c, d, inp[13], S21, 0xA9E3E905L)  # 29
        d = XX(G, d, a, b, c, inp[2], S22, 0xFCEFA3F8L)  # 30
        c = XX(G, c, d, a, b, inp[7], S23, 0x676F02D9L)  # 31
        b = XX(G, b, c, d, a, inp[12], S24, 0x8D2A4C8AL)  # 32

        # Round 3.
        S31, S32, S33, S34 = 4, 11, 16, 23

        a = XX(H, a, b, c, d, inp[5], S31, 0xFFFA3942L)  # 33
        d = XX(H, d, a, b, c, inp[8], S32, 0x8771F681L)  # 34
        c = XX(H, c, d, a, b, inp[11], S33, 0x6D9D6122L)  # 35
        b = XX(H, b, c, d, a, inp[14], S34, 0xFDE5380CL)  # 36
        a = XX(H, a, b, c, d, inp[1], S31, 0xA4BEEA44L)  # 37
        d = XX(H, d, a, b, c, inp[4], S32, 0x4BDECFA9L)  # 38
        c = XX(H, c, d, a, b, inp[7], S33, 0xF6BB4B60L)  # 39
        b = XX(H, b, c, d, a, inp[10], S34, 0xBEBFBC70L)  # 40
        a = XX(H, a, b, c, d, inp[13], S31, 0x289B7EC6L)  # 41
        d = XX(H, d, a, b, c, inp[0], S32, 0xEAA127FAL)  # 42
        c = XX(H, c, d, a, b, inp[3], S33, 0xD4EF3085L)  # 43
        b = XX(H, b, c, d, a, inp[6], S34, 0x04881D05L)  # 44
        a = XX(H, a, b, c, d, inp[9], S31, 0xD9D4D039L)  # 45
        d = XX(H, d, a, b, c, inp[12], S32, 0xE6DB99E5L)  # 46
        c = XX(H, c, d, a, b, inp[15], S33, 0x1FA27CF8L)  # 47
        b = XX(H, b, c, d, a, inp[2], S34, 0xC4AC5665L)  # 48

        # Round 4.
        S41, S42, S43, S44 = 6, 10, 15, 21

        a = XX(I, a, b, c, d, inp[0], S41, 0xF4292244L)  # 49
        d = XX(I, d, a, b, c, inp[7], S42, 0x432AFF97L)  # 50
        c = XX(I, c, d, a, b, inp[14], S43, 0xAB9423A7L)  # 51
        b = XX(I, b, c, d, a, inp[5], S44, 0xFC93A039L)  # 52
        a = XX(I, a, b, c, d, inp[12], S41, 0x655B59C3L)  # 53
        d = XX(I, d, a, b, c, inp[3], S42, 0x8F0CCC92L)  # 54
        c = XX(I, c, d, a, b, inp[10], S43, 0xFFEFF47DL)  # 55
        b = XX(I, b, c, d, a, inp[1], S44, 0x85845DD1L)  # 56
        a = XX(I, a, b, c, d, inp[8], S41, 0x6FA87E4FL)  # 57
        d = XX(I, d, a, b, c, inp[15], S42, 0xFE2CE6E0L)  # 58
        c = XX(I, c, d, a, b, inp[6], S43, 0xA3014314L)  # 59
        b = XX(I, b, c, d, a, inp[13], S44, 0x4E0811A1L)  # 60
        a = XX(I, a, b, c, d, inp[4], S41, 0xF7537E82L)  # 61
        d = XX(I, d, a, b, c, inp[11], S42, 0xBD3AF235L)  # 62
        c = XX(I, c, d, a, b, inp[2], S43, 0x2AD7D2BBL)  # 63
        b = XX(I, b, c, d, a, inp[9], S44, 0xEB86D391L)  # 64

        self.A = (self.A + a) & 0xffffffffL
        self.B = (self.B + b) & 0xffffffffL
        self.C = (self.C + c) & 0xffffffffL
        self.D = (self.D + d) & 0xffffffffL
        # print 'A=%s\nB=%s\nC=%s\nD=%s\n' % (hex(self.A), hex(self.B), hex(self.C), hex(self.D))

    #padding，即补位:首字节为\x80
    def padding(self, n, sz = None):
        if sz is None:
            sz = n
        pre = 64 - 8
        sz = struct.pack("Q", sz * 8)
        pad = '\x80'
        n += 1
        if n % 64 <= pre:
            pad += '\x00' * (pre - n % 64)
            pad += sz
        else:
            pad += '\x00' * (pre + 64 - n % 64)
            pad += sz
        return pad
    #最后八个字节为数据长度
    def pad(self, msg):
        return msg + self.padding(len(msg))

    def md5_iter(self, padding_msg):
        assert len(padding_msg) % 64 == 0
        for i in range(0, len(padding_msg), 64):
            block = padding_msg[i:i + 64]
            self.md5_compress(padding_msg[i:i + 64])

    def digest(self):
        return struct.pack('<IIII', self.A, self.B, self.C, self.D)

    def hexdigest(self):
        return binascii.hexlify(self.digest()).decode()

    def my_md5(self, msg):
        padding_msg = self.pad(msg)
        self.md5_iter(padding_msg)
        return self.hexdigest()  # 通过md5值，逆向算出最后一轮的magic number

    def compute_magic_number(self, md5str):
        self.A = struct.unpack("I", md5str[0:8].decode('hex'))[0]
        self.B = struct.unpack("I", md5str[8:16].decode('hex'))[0]
        self.C = struct.unpack("I", md5str[16:24].decode('hex'))[0]
        self.D = struct.unpack("I", md5str[24:32].decode('hex'))[0]
        # print '\nA=%s\nB=%s\nC=%s\nD=%s\n' % (hex(self.A), hex(self.B), hex(self.C), hex(self.D))

    def extension_attack(self, md5str, str_append, lenth):
        self.compute_magic_number(md5str)
        p = self.padding(lenth)
        padding_msg = self.padding( len(str_append), lenth + len(p) + len(str_append) )
        # url = repr(padding_msg.replace(' ', ''))
        # print 'padding:%r' % (padding_msg)
        self.md5_iter(str_append + padding_msg)
        return self.hexdigest()

if __name__ == "__main__":
    m = md5()
    if 1:
        lenth = int(raw_input(u'salt的hash长度：'))
        md5 = raw_input(u'salt的hash值：')
        value = raw_input(u'附加值：')
        print u'md5(salt + padding + 附加值):' + m.extension_attack(md5, value, lenth)
        #这个是padding的值，得看情况，实在不行就手动算。salt长度 + padding = 64
        print ur'padding+附加值:' + r'%08' + r'%00' * (64 - 1 - lenth - 8) + r'%' + str(hex(lenth * 8)).replace(r'0x','') + r'%00' * 7 + value

    else:
        print m.my_md5("123456")
        src = m.pad(sys.argv[1]) + sys.argv[2]
        print 'md5 padding ->', m.my_md5(src)
还有一个python扩展hashpumpy，但是我折腾好一阵都安装不上，那个更好用，自己写也是无奈之举

根据源代码，username必须是admin，这样的话password必须是admin+padding+附加值

这样的话post上去的就是

username=admin&password=admin%80%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%c8%00%00%00%00%00%00%00asd

在数据包里设置cookies:getmein=bf3b234ff0410ee4ec09b470e314d8c9

就成功绕过验证了

这里面直接给出的salt的MD5值其实是secret+adminadmin的MD5，所以salt的长度得是25，最后补位的时候要注意，实在不行自己手动构造padding。但是salt+padding+附加值的MD5没问题

0x03后记

中途也是踩了好多坑

首先是MD5的实现过程和漏洞原理，看了好一阵才明白，还好

之后就是脚本的实现，hashpumpy到最后都没装上，只能自己写。MD5的python实现是从网上找的，也花了不少时间改。

最后是payload的问题，忘了题目给的MD5是secret+adminadmin的md5，结果脚本跑的是secret本身，和它的不一致，有歧义。当时太晚了神志不太清醒还以为是脚本写错了，卡了好长时间，最后手动padding才知道不是自己的问题

发布于 
tags:
  • { 加密 }
  • { 哈希 }