哈希扩展长度攻击
===

本文写于2017年12月5日

弄了2天才弄出来

0x00 起于一道CTF

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

首先是改包能够看到源码

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位

脚本如下

### 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才知道不是自己的问题