哈希长度扩展攻击的常见攻击对象是 MD5 和 SHA1 这两个哈希算法，而它们的共同点是：都使用了 Merkle–Damgård 构造。改构造最初被设计为一种用于构建抗碰撞的哈希函数的方法，不过也由于该构造的特性，攻击者能够仅需已知哈希值和原始消息长度，就能计算出附加数据后的新哈希值。

Merkle-Damgård

Merkle–Damgård 构造利用填充函数将消息扩展为压缩函数能处理的固定长度的倍数，然后对其分块处理。该构造包括一个初始向量 iv 和一个压缩函数 f，该函数将当前的哈希值和下一个消息块作为输入，产生新的哈希值。

对于已经完成填充和分组的数据，其最终哈希值的计算过程大致可以如下表示:

1
2
3
4
5
6
7
       +---------+  +---------+     +---------+
       | Block 1 |  | Block 2 |     | Block n |
       +----+----+  +----+----+ ... +----+----+
            |           |                |
+----+    +-v-+        +-v-+           +-+-+   +------------+
| iv +----> f +--------> f +--> ... ---> f +---> Final Hash |
+----+    +---+        +---+           +---+   +------------+

很显然在此过程中，每一个分块计算完成后都会得到一个哈希值，然后参与下一个分块的计算，最终的哈希值则是最后一个分块的哈希值。这也就意味着，Merkle–Damgård 构造不能防止在已知消息的基础上进行后续哈希计算，因此可以实现长度扩展攻击。

Extension Attack

当我们拿到一个已知哈希值 Hash 和消息长度 len(Msg) 的哈希值时，我们可以大致复现出这个哈希值的计算过程。

1
2
3
4
5
6
7
    +------------+  +------------+     +----------------------+
    | Msg Part 1 |  | Msg Part 2 |     | Msg Part n + Padding |
    +------+-----+  +------+-----+ ... +----------+-----------+
           |               |                      |
+----+   +-v-+           +-v-+                  +-v-+   +------+
| iv +---> f +-----------> f +---> ... ---------> f +---> Hash |
+----+   +---+           +---+                  +---+   +------+

在这个过程中，因为知道 len(Msg) 所以可以计算出 Padding 的内容，那么可以确保补充的数据会在新的分块中，不会影响到原始的哈希值计算。这样我们就可以在已知的哈希值 Hash 的基础上，计算出附加数据后的新哈希值。

1
2
3
4
5
6
7
8
9
10
                          +--> Attacking Part
                          |
+----------------------+  |      +----------------+     +------------------------------+
| Msg Part n + Padding |  |      | New Msg Part 1 |     | New Msg Part n + New Padding |
+-----------+----------+  |      +--------+-------+ ... +------------+-----------------+
            |             |               |                          |
          +-v-+           v  +------+   +-v-+                      +-v-+   +----------+
   ... ---> f +--------------> Hash +---> f +-----> ... -----------> f +---> New Hash |
          +---+           ^  +------+   +---+                      +---+   +----------+
                          |

那么攻击所需的附加数据就是 Padding + New Msg (New Padding 会在计算过程中计算，不需要作为数据输入)。这样我们就可以在不知道原始消息内容的情况下，计算出附加数据后的新哈希值。

Proof of Concept

我参考了曾经使用过的攻击代码，在理解清楚原理后，我自己实现了一个简单的攻击脚本（顺带修补了它在面对过长 New Msg 时会失效的问题），具体代码公开在了 luoingly/attack-scripts 中。

代码首先做了了一个 MD5 的简单实现，然后实现了一个 attack 函数，该函数接受原始消息长度 len(Msg)、已知哈希值 Hash 和附加数据 New Msg，然后计算出附加数据以及新哈希值。

1
2
3
4
5
6
7
8
9
10
11
12
def attack(message_len: int, known_hash: str,
           append_str: bytes) -> tuple:
    # MD5 extension attack
    md5 = MD5()

    previous_text = md5.padding(b"*" * message_len)
    current_text = previous_text + append_str

    md5.A, md5.B, md5.C, md5.D = unpack("<IIII", bytes.fromhex(known_hash))
    md5.extend(md5.padding(current_text)[len(previous_text):])

    return current_text[message_len:], md5.digest().hex()

第一次写攻击原理相关的文章，如果有任何问题欢迎指正。

This article is authored by Luoingly and is licensed under CC BY-NC 4.0

Permalink: https://luoingly.top/post/md5-length-extension-attack/