哈希长度扩展攻击

crypto 评论

​

哈希长度扩展攻击

原理

在密码学和计算机安全中，长度扩展攻击（Length extension attacks）是指针对某些允许包含额外信息的加密散列函数的攻击手段。 该攻击适用于在消息与密钥的长度已知的情形下，所有采取了 H(key||message) 此类构造的散列函数。MD5和SHA-1等基于Merkle–Damgård构造的算法均对此类攻击显示出脆弱性。

攻击的要点在于：

  • 攻击者可以控制message
  • 攻击者需要知道key的长度，如不知道可以考虑暴力破解
  • 攻击已经知道了包含key的一个消息的hash值
  • hash算法使用了Merkle–Damgård construction进行数据的压缩（比如MD5、SHA-1等）并采取 H(key||message) 构造

攻击可以达到的效果在于，如果知道一个原消息哈希值 H(key||M1) 及其 key||M1 长度，对于任意的字符串M2，攻击者可以计算出 H(pad(key||M1) + M2) 的值，而不需要知道是 key 及 M1 是多少。

以区块为单位操作数据（MD5, SHA1, SHA256的区块长度是512 bits，大多数message的长度不会刚好可以被哈希函数的区块长度整除。这样一来，message就必须被填充(padding)至区块长度的整数倍）。

每个消息块都会和一个输入向量做一个运算，把这个计算结果当成下个消息块的输入向量 ，初始化向量是定义好的，在最后一块的时候，才会将其对应的链接变量转换为hash值。

由已知的MD5值逆向得到对应的链接变量，利用得到的链接变量对填充后的新加的消息进行哈希算法，最后得到hash值。

步骤

MD5操作流程：

20180813125243-b731fe76-9eb4-1

用 md5 函数作为例子。 md5 算法在计算的时候会初始化四个寄存器 A、B、C、D，分别有自己的初始值：

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

md5 算法是以 512bit 为一个块进行迭代计算的，第一个块计算完后，四个寄存器的值就会被更新，如果还存在下一个块，就会在现在四个寄存器里面的数值的基础上继续迭代计算，等全部的块计算完成后，四个寄存器中的十六进制连接起来，就是最终的 MD5 值。换句话说，也就是当第一个块计算完成后，此时四个寄存器中存储的就是第一个块的 MD5 值，接着在这个基础上继续迭代计算下一个块。

如果当前的数据长度不满足对 512bit 求余为 448bit 的时候，需要补至满足这个条件，填充的方法如下：

  1. 首先补一个 1（二进制位上的一个 1，不是十进制的 1）

  2. 接着在后面补 0（同样是二进制位上的 0），直到满足比特长度对 512 求余为 448 这个条件。

  3. 接着补 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 算法中的补位的这部分，就是实现长度扩展攻击的关键。

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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。

工具

  • HashPump：https://github.com/bwall/HashPump

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    $ hashpump -h
    HashPump [-h help] [-t test] [-s signature] [-d data] [-a additional] [-k keylength]
        HashPump generates strings to exploit signatures vulnerable to the Hash Length Extension Attack.
        -h --help          Display this message.
        -t --test          Run tests to verify each algorithm is operating properly.
        -s --signature     The signature from known message.
        -d --data          The data from the known message.
        -a --additional    The information you would like to add to the known message.
        -k --keylength     The length in bytes of the key being used to sign the original message with.
        Version 1.2.0 with CRC32, MD5, SHA1, SHA256 and SHA512 support.
        <Developed by bwall(@botnet_hunter)>
        
    $ hashpump -s '6d5f807e23db210bc254a28be2d6759a0f5f5d99' --data 'count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo' -a '&waffle=liege' -k 14
    0e41270260895979317fff3898ab85668953aaa2
    count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\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\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\x02(&waffle=liege

  • hash_extender：https://github.com/iagox86/hash_extender

    1
    2
    3
    4
    5
    let secret = "secret"
    let data = "data"
    let H = md5()
    let signature = hash(secret || data) = 6036708eba0d11f6ef52ad44e8b74d5b
    let append = "append"
    1
    2
    3
    4
    5
    $ ./hash_extender --data data --secret 6 --append append --signature 6036708eba0d11f6ef52ad44e8b74d5b --format md5
    Type: md5
    Secret length: 6
    New signature: 6ee582a1669ce442f3719c47430dadee
    New string: 64617461800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000005000000000000000617070656e64

  • hexpand：https://github.com/amlweems/hexpand

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    Usage:
    	hexpand -t type -s signature -l length -m message
    	hexpand --test

    Options:
    	-t --type		the hash algorithm for expansion (md5, sha1, sha256, or sha512
    	-s --sig		the result of the original hash function
    	-l --length		the length of the original message
    	-m --message	the message to be appended
    	--test			runs a set of test cases
    	
     $ ./hexpand -t md5 -s cd9fb5c3a20e29b2b2846deaa845c426 -l 55 -m "\nP.S. Tell Eve our secret plan"
    Append (hex): 80b8010000000000005c6e502e532e2054656c6c20457665206f75722073656372657420706c616e2e
    Signature:    69b0e397b5588c86aa9751b56f2c6943

参考

哈希长度扩展攻击