哈希长度拓展攻击(Hash Length Extension Attacks)

哈希长度拓展攻击(Hash Length Extension Attacks)

导语

　　通过CTF接触到哈希长度扩展攻击，本文将详细分析如何对一些比较弱的Message Authentication codes (MACs)进行这种攻击，最后也将结合CTF的题目对哈希长度扩展攻击的危害性及防御做一个总结。

原理

　　Message authentication codes (MACs)是用于验证信息真实性的。一般的MAC算法是这样的：服务器把secret和message连接到一起，然后用消息摘要算法如MD5或SHA1取摘要。研究发现MD4、MD5、RIPEMD-160、SHA-0、SHA-1、SHA-256、SHA-512、WHIRLPOOL等摘要算法受此攻击，但MD2、SHA-224和SHA-384不受此攻击。

　　哈希摘要算法，如MD5、SHA1、SHA2等，都是基于Merkle–Damgård结构。这类算法有一个很有意思的问题：当知道hash(secret + message)的值及secret长度的情况下，可以轻松推算出hash(secret + message||padding||m’)。在这里m’是任意数据，||是连接符，可以为空,padding是secret后的填充字节。hash的padding字节包含整个消息的长度，因此，为了能准确计算出padding的值，secret的长度我们也是需要知道的。

　　当我们填充后，服务器算出的原始hash值，正好与我们添加扩展字符串并覆盖初始链变量所计算出来的一样。这是因为攻击者的哈希计算过程，相当于从服务器计算过程的一半紧接着进行下去。提交此hash值便能通过验证了，这就是所谓的哈希长度拓展攻击(Hash Length Extension Attacks)。

算法简析

　　要深入理解哈希长度拓展攻击(Hash Length Extension Attacks)，就得先了解摘要算法的具体实现过程。本文以MD5为例做简析，其它算法类似。

　　这是一张MD5算法的流程图，根据这张图我们可以把MD5算法的流程，简单分为下面几步：

  1. 把消息分为n个消息块。
  2. 对最后一个消息块进行消息填充。
  3. 每个消息块会和一个输入量做运算，把运算结果作为下一个输入量。

　　下面说说MD5算法的实现：

  1. Append Padding Bits(填充bits)
  2. Append Length(填充长度)
  3. Initialize MD Buffer(初始化向量)
  4. Process Message in 16-Word Blocks(复杂的函数运算)

　　而要实现我们的攻击，我们只关心前三步，也就是不再再纠结复杂的算法运算。下面用例子来解释前三个流程也便于更加深入的理解哈希长度拓展攻击(Hash Length Extension Attacks)：

Append Padding Bits(填充bits)

　　MD5算法会对消息进行分组，每组64 byte（512bit），不足64 byte 的部分会用padding补位。MD5算法每组最后8 byte 表示的是补充前消息的长度，所以消息补位是使得其长度在对 512 取模后的值为 448（512-8*8）。也就是说，len(message) mod(512) == 448。补位二进制表示是在消息的后面加上一个1，后面跟着 n 个0，直到 len(message) mod (512) == 448。在 16 进制下，我们需要在消息后补80，就是 2 进制的10000000。我们把消息进行补位到 448 bit，也就是 56 byte。

Append Length(填充长度)

　　补位过后，第 57 个字节开始储存补位之前消息的长度。

　　长度是小端存储的，也就是说高字节放在高地址中。

　　如果消息的长度大于2 ^ 64，也就是大于2048PB。那么64bit无法存储消息的长度，则取低64bit。

　　下图是补位的示例，要进行哈希运算的消息是字符串"message"，"message"是7个字母，7 byte (56 bit )，换算成16进制位0x38，其后跟着7个字节的0x00，则：

Initialize MD Buffer(初始化向量)

　　计算消息摘要必须用补位已经补长度完成之后的消息来进行运算，拿出 512 bit 的消息（即64 byte ）。 计算消息摘要的时候，有一个初始的链变量，用来参与第一轮的运算。MD5 的初始链变量为：

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

　　无需关心计算细节，我们只需要知道经过一次消息再要后，上面的链变量将会被新的值覆盖，而最后一轮产生的链变量经过高低位互换（如：aabbccdd -> ddccbbaa）后就是我们计算出来的 md5 值。

哈希长度拓展攻击(Hash Length Extension Attacks)的实现

　　哈希长度拓展攻击(Hash Length Extension Attacks)的实现就是基于初始链变量的值被新的覆盖。

下面结合一个CTF的题目更加形象具体的分析其实现过程。

<?php
<html>
<body>

<pre>
$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);#exit()/die() 函数输出一条消息，并退出当前脚本
        }
        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
    }
}
    </pre>
<h1>Admins Only!</h1>
<p>If you have the correct credentials, log in below. If not, please LEAVE.</p>
<form method="POST">
    Username: <input type="text" name="username"> <br>
    Password: <input type="password" name="password"> <br>
    <button type="submit">Submit</button>
</form>

</body>
</html>

?>

这个核心的判断在第二个if的判断

if ($COOKIE["getmein"] === md5($secret . urldecode($username . $password)))

flag获取的要求是：传进一个cookie使getmein等于md5($secret . urldecode($username . $password))且后面部分不能为adminadmin,
也就是说需要构造getmein的cookie和他那串字符相同就可以。

已知$secret长度为15，先进行消息的填充，前面的A是随便写的，为了占15个字符。填充如下:


然后在后面跟加附加值，随便写什么：

然后去掉前面假的$secret:

adminadmin\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\xc8\x00\x00\x00\x00\x00\x00\x00dawn

urlencode之后为:

adminadmin%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%00%c8%00%00%00%00%00%00%00dawn

现在我们在不知道具体 $secret 的情况下，已经得知了md5(secert+adminadmin)的值为571580b26c65f306376d4f64e53cb5c7，以及$sercret的位数。而我们得到的 hash 值正是下一轮摘要经过高地位互换的链变量。

下一步就是对附加值进行MD5加密了：

我在网上找了一个Python的MD5实现。修改初始的链变量为经过高低位逆转的md5(secert+adminadmin)：

A=0xb2801557
B=0x06f3656c
C=0x644f6d37
D=0xc7b53ce5

my_md5.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Author：DshtAnger
# theory reference:
#   blog：
#       http://blog.csdn.net/adidala/article/details/28677393
#       http://blog.csdn.net/forgotaboutgirl/article/details/7258109
#       http://blog.sina.com.cn/s/blog_6fe0eb1901014cpl.html
#   RFC1321：
#       https://www.rfc-editor.org/rfc/pdfrfc/rfc1321.txt.pdf
##############################################################################
import sys
def genMsgLengthDescriptor(msg_bitsLenth):
    '''
    ---args:
            msg_bitsLenth : the bits length of raw message
    --return:
            16 hex-encoded string , i.e.64bits,8bytes which used to describe the bits length of raw message added after padding
    '''
    return __import__("struct").pack(">Q",msg_bitsLenth).encode("hex")

def reverse_hex_8bytes(hex_str):
    '''
    --args:
            hex_str: a hex-encoded string with length 16 , i.e.8bytes
    --return:
            transform raw message descriptor to little-endian 
    '''
    hex_str = "%016x"%int(hex_str,16)
    assert len(hex_str)==16    
    return __import__("struct").pack("<Q",int(hex_str,16)).encode("hex")

def reverse_hex_4bytes(hex_str):
    '''
    --args:
            hex_str: a hex-encoded string with length 8 , i.e.4bytes
    --return:
            transform 4 bytes message block to little-endian
    '''    
    hex_str = "%08x"%int(hex_str,16)
    assert len(hex_str)==8    
    return __import__("struct").pack("<L",int(hex_str,16)).encode("hex")

def deal_rawInputMsg(input_msg):
    '''
    --args:
            input_msg : inputed a ascii-encoded string
    --return:
            a hex-encoded string which can be inputed to mathematical transformation function.
    '''
    ascii_list = [x.encode("hex") for x in input_msg]
    length_msg_bytes = len(ascii_list)
    length_msg_bits = len(ascii_list)*8
    #padding
    ascii_list.append('80')  
    while (len(ascii_list)*8+64)%512 != 0:  
        ascii_list.append('00')
    #add Descriptor
    ascii_list.append(reverse_hex_8bytes(genMsgLengthDescriptor(length_msg_bits)))
    return "".join(ascii_list)



def getM16(hex_str,operatingBlockNum):
    '''
    --args:
            hex_str : a hex-encoded string with length in integral multiple of 512bits
            operatingBlockNum : message block number which is being operated , greater than 1
    --return:
            M : result of splited 64bytes into 4*16 message blocks with little-endian

    '''
    M = [int(reverse_hex_4bytes(hex_str[i:(i+8)]),16) for i in xrange(128*(operatingBlockNum-1),128*operatingBlockNum,8)]
    return M

#定义函数，用来产生常数T[i]，常数有可能超过32位，同样需要&0xffffffff操作。注意返回的是十进制的数
def T(i):
    result = (int(4294967296*abs(__import__("math").sin(i))))&0xffffffff
    return result   

#定义每轮中用到的函数
#RL为循环左移，注意左移之后可能会超过32位，所以要和0xffffffff做与运算，确保结果为32位
F = lambda x,y,z:((x&y)|((~x)&z))
G = lambda x,y,z:((x&z)|(y&(~z)))
H = lambda x,y,z:(x^y^z)
I = lambda x,y,z:(y^(x|(~z)))
RL = L = lambda x,n:(((x<<n)|(x>>(32-n)))&(0xffffffff))

def FF(a, b, c, d, x, s, ac):  
    a = (a+F ((b), (c), (d)) + (x) + (ac)&0xffffffff)&0xffffffff;  
    a = RL ((a), (s))&0xffffffff;  
    a = (a+b)&0xffffffff  
    return a  
def GG(a, b, c, d, x, s, ac):  
    a = (a+G ((b), (c), (d)) + (x) + (ac)&0xffffffff)&0xffffffff;  
    a = RL ((a), (s))&0xffffffff;  
    a = (a+b)&0xffffffff  
    return a  
def HH(a, b, c, d, x, s, ac):  
    a = (a+H ((b), (c), (d)) + (x) + (ac)&0xffffffff)&0xffffffff;  
    a = RL ((a), (s))&0xffffffff;  
    a = (a+b)&0xffffffff  
    return a  
def II(a, b, c, d, x, s, ac):  
    a = (a+I ((b), (c), (d)) + (x) + (ac)&0xffffffff)&0xffffffff;  
    a = RL ((a), (s))&0xffffffff;  
    a = (a+b)&0xffffffff  
    return a      

def show_md5(A,B,C,D):
    return "".join( [  "".join(__import__("re").findall(r"..","%08x"%i)[::-1]) for i in (A,B,C,D)  ]  )

def run_md5(A=0x67452301,B=0xefcdab89,C=0x98badcfe,D=0x10325476,readyMsg=""):

    a = A
    b = B
    c = C
    d = D

    for i in xrange(0,len(readyMsg)/128):
        M = getM16(readyMsg,i+1)
        for i in xrange(16):
            exec "M"+str(i)+"=M["+str(i)+"]"
        #First round
        a=FF(a,b,c,d,M0,7,0xd76aa478L)
        d=FF(d,a,b,c,M1,12,0xe8c7b756L)
        c=FF(c,d,a,b,M2,17,0x242070dbL)
        b=FF(b,c,d,a,M3,22,0xc1bdceeeL)
        a=FF(a,b,c,d,M4,7,0xf57c0fafL)
        d=FF(d,a,b,c,M5,12,0x4787c62aL)
        c=FF(c,d,a,b,M6,17,0xa8304613L)
        b=FF(b,c,d,a,M7,22,0xfd469501L)
        a=FF(a,b,c,d,M8,7,0x698098d8L)
        d=FF(d,a,b,c,M9,12,0x8b44f7afL)
        c=FF(c,d,a,b,M10,17,0xffff5bb1L)
        b=FF(b,c,d,a,M11,22,0x895cd7beL)
        a=FF(a,b,c,d,M12,7,0x6b901122L)
        d=FF(d,a,b,c,M13,12,0xfd987193L)
        c=FF(c,d,a,b,M14,17,0xa679438eL)
        b=FF(b,c,d,a,M15,22,0x49b40821L)
        #Second round
        a=GG(a,b,c,d,M1,5,0xf61e2562L)
        d=GG(d,a,b,c,M6,9,0xc040b340L)
        c=GG(c,d,a,b,M11,14,0x265e5a51L)
        b=GG(b,c,d,a,M0,20,0xe9b6c7aaL)
        a=GG(a,b,c,d,M5,5,0xd62f105dL)
        d=GG(d,a,b,c,M10,9,0x02441453L)
        c=GG(c,d,a,b,M15,14,0xd8a1e681L)
        b=GG(b,c,d,a,M4,20,0xe7d3fbc8L)
        a=GG(a,b,c,d,M9,5,0x21e1cde6L)
        d=GG(d,a,b,c,M14,9,0xc33707d6L)
        c=GG(c,d,a,b,M3,14,0xf4d50d87L)
        b=GG(b,c,d,a,M8,20,0x455a14edL)
        a=GG(a,b,c,d,M13,5,0xa9e3e905L)
        d=GG(d,a,b,c,M2,9,0xfcefa3f8L)
        c=GG(c,d,a,b,M7,14,0x676f02d9L)
        b=GG(b,c,d,a,M12,20,0x8d2a4c8aL)
        #Third round
        a=HH(a,b,c,d,M5,4,0xfffa3942L)
        d=HH(d,a,b,c,M8,11,0x8771f681L)
        c=HH(c,d,a,b,M11,16,0x6d9d6122L)
        b=HH(b,c,d,a,M14,23,0xfde5380c)
        a=HH(a,b,c,d,M1,4,0xa4beea44L)
        d=HH(d,a,b,c,M4,11,0x4bdecfa9L)
        c=HH(c,d,a,b,M7,16,0xf6bb4b60L)
        b=HH(b,c,d,a,M10,23,0xbebfbc70L)
        a=HH(a,b,c,d,M13,4,0x289b7ec6L)
        d=HH(d,a,b,c,M0,11,0xeaa127faL)
        c=HH(c,d,a,b,M3,16,0xd4ef3085L)
        b=HH(b,c,d,a,M6,23,0x04881d05L)
        a=HH(a,b,c,d,M9,4,0xd9d4d039L)
        d=HH(d,a,b,c,M12,11,0xe6db99e5L)
        c=HH(c,d,a,b,M15,16,0x1fa27cf8L)
        b=HH(b,c,d,a,M2,23,0xc4ac5665L)
        #Fourth round
        a=II(a,b,c,d,M0,6,0xf4292244L)
        d=II(d,a,b,c,M7,10,0x432aff97L)
        c=II(c,d,a,b,M14,15,0xab9423a7L)
        b=II(b,c,d,a,M5,21,0xfc93a039L)
        a=II(a,b,c,d,M12,6,0x655b59c3L)
        d=II(d,a,b,c,M3,10,0x8f0ccc92L)
        c=II(c,d,a,b,M10,15,0xffeff47dL)
        b=II(b,c,d,a,M1,21,0x85845dd1L)
        a=II(a,b,c,d,M8,6,0x6fa87e4fL)
        d=II(d,a,b,c,M15,10,0xfe2ce6e0L)
        c=II(c,d,a,b,M6,15,0xa3014314L)
        b=II(b,c,d,a,M13,21,0x4e0811a1L)
        a=II(a,b,c,d,M4,6,0xf7537e82L)
        d=II(d,a,b,c,M11,10,0xbd3af235L)
        c=II(c,d,a,b,M2,15,0x2ad7d2bbL)
        b=II(b,c,d,a,M9,21,0xeb86d391L)


        A += a
        B += b
        C += c
        D += d

        A = A&0xffffffff
        B = B&0xffffffff
        C = C&0xffffffff
        D = D&0xffffffff

        a = A
        b = B
        c = C
        d = D

    return show_md5(a,b,c,d)

exp.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import my_md5
samplehash="571580b26c65f306376d4f64e53cb5c7"
#将哈希值分为四段,并反转该四字节为小端序,作为64第二次循环的输入幻书
s1=0xb2801557
s2=0x06f3656c
s3=0x644f6d37
s4=0xc7b53ce5
#exp
secret = "A"*15
secret_admin = secret + 'adminadmin{padding}'
padding = '\x80{zero}\xc8\x00\x00\x00\x00\x00\x00\x00'.format(zero="\x00"*(64-15-10-1-8))
secret_admin = secret_admin.format(padding=padding) + 'dawn'
r = my_md5.deal_rawInputMsg(secret_admin)
inp = r[len(r)/2:] #我们需要截断的地方，也是我们需要控制的地方
print "getmein:"+my_md5.run_md5(s1,s2,s3,s4,inp)

　　最后输出为：
getmein:79717e731df8699d1476fab654763560

　　因为题目md5($secret . urldecode($username . $password))所以
将\x换成%手动url编码提交，get flag。

利用工具实现哈希长度拓展攻击

　　当然，此攻击已经有很多成熟的工具了，不用再这么麻烦的自己写脚本跑。下面介绍几款好用的工具：

  1. HashPump 这是pcat写的一篇"哈希长度扩展攻击的简介以及HashPump安装使用方法"
  2. Hexpand 还是pcat写的一篇"哈希长度扩展攻击(Hash Length Extension Attack)利用工具hexpand安装使用方法"
  3. hash_extender 一个外国人写的，感觉也挺不错。

　　下图就是用HashPump工具跑的，很快，很方便：

　　这里说一下个人想法：其实不需要message的内容，只需知道长度就可以正确填充了，而且hash摘要值也是不受影响的。比如md5，只要初始链变量确定了，md5的值只受64字节后添加的字符串的影响，secret||message的长度只是影响第57-64字节的填充。所以hashpump只要在Input Data 处输入任意字符但正确长度的字符串就OK了，也可以做到不知道message内容而正确填充的功能。

危害性

　　通过以上的分析，想必大家对此攻击有了更深入的认识。只要存在脆弱的（使用此类散列算法）Message authentication codes (MACs)用于验证信息真实性的地方就很可能受此攻击。

　　比如，我们发现了这样的一个下载文件的接口：/download?name=test.pdf&sig=6543109bb53887f7bb46fe424f26e24a sig可能是这个文件的某种校验签名，如果想通过这个接口下载其他文件就会失败，因为sig校验不过。同时还会发现md5(name) !== sig，很明显在校验算法中添加了盐，如果我们想下载任意的文件比如test.pdf%00/../../../../etc/passwd，正常情况下是没办法的，因为有盐，所以我们无法构造自己的签名值，但是如果服务端使用了类似if ($sig === md5($salt.$name))的校验代码，那么就会存在此攻击。

　　但在现实攻击环境中，攻击者无法获知密钥长度，需要对其长度进行猜测。继续之前的例子，假设当MAC验证失败时，这个存在漏洞的网站会返回一个错误信息（HTTP response code 或者response body中的错误消息之类）。当验证成功，但是文件不存在时，也会返回一个错误信息。如果这两个错误信息是不一样的，攻击者就可以计算不同的扩展值，每个对应着不同的密钥长度，然后分别发送给服务器。当服务器返回表明文件不存在的错误信息时，即说明存在长度扩展攻击，攻击者可以随意计算新的扩展值以下载服务器上未经许可的敏感文件。

　　所以说，此类攻击的危害性还是相当巨大的。

如何防御

　　那么如何抵御此攻击呢?

  1. 可以将消息摘要的值再进行消息摘要，这样就可以避免用户控制message了。也就是HMAC算法。该算法大概来说是这样：MAC =hash(secret + hash(secret + message))，而不是简单的对密钥连接message之后的值进行哈希摘要。具体HMAC的工作原理有些复杂，但你可以有个大概的了解。重点是，由于这种算法进行了双重摘要，密钥不再受本文中的长度扩展攻击影响。HMAC最先是在1996年被发表，之后几乎被添加到每一种编程语言的标准函数库中。
  2. 将secret放置在消息末尾也能防止这种攻击。比如 hash(m+secret)，希望推导出 hash(m + secret||padding||m')，由于自动附加secret在末尾的关系，会变成hash(m||padding||m'||secret)。现在的附加值可以看作是m'||secret，secret值不知道，从而导致附加字符串不可控，hash值也就不可控，因而防止了这种攻击。

写在最后

　　本文也是通过收集、整理网上的资料写的，如果有朋友想更深入了解哈希长度拓展攻击(Hash Length Extension Attacks)可以参考一篇外国人写的文章，此文章也详细生动的分析了此攻击，也介绍了Github上一个好用的攻击工具。也可以读读刺总的《白帽子讲web安全》中的"Understanding MD5 Length Extension Attack"一节。当然，我也非常乐意和朋友一起探讨和研究此攻击。

源链接

Hacking more

...