哈希函数总结¶

一、基本概念¶

哈希函数（Hash Function）把消息或数据压缩成摘要，使得数据量变小。

哈希函数模型

对于任何一个 hash 值，理论上存在若干个消息与之对应，即**碰撞**。

需求	描述
输入长度可变	Hash 函数可应用于任意长度的数据
输出长度固定	Hash 函数的输出长度固定
效率	对于任意消息 \(x\)，计算 \(H(x)\) 很容易
单向性	对于任意哈希值 \(h\)，找到满足 \(H(x) = h\) 的 \(x\) 在计算上不可行
抗弱碰撞性	对于任意消息 \(x\)，找到另一消息 \(y\) 满足 \(H(x) = H(y)\) 在计算上不可行
抗强碰撞性	找到任意一对满足 \(H(x) = H(y)\) 的消息 \(x\) 和 \(y\) 在计算上不可行
伪随机性	哈希函数的输出满足伪随机性测试标准

大多数 Hash 函数是迭代性的，使用同一个 hash 函数以不同的参数进行多次迭代运算。

32 位 MD5 去掉前 8 位和后 8 位即为 16 位 MD5。

若函数有以下四个初始化变量，可判断为 MD5：

Text Only

0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476

目前 MD5 已基本被攻破，常见的 MD5 碰撞均可在在线网站查询。可使用 fastcoll 生成指定前缀的 MD5 碰撞。

输入：任意长度的消息，分为 512 位长的分组。首先在消息右侧补 1，再补若干个 0，直到消息长度对 512 取模余 448，最后附上 64 位的原始消息长度。
输出：160 位的消息摘要。

Text Only

0x67452301
0xEFCDAB89
0x98BADCFE
0x10325476
0xC3D2E1F0

前四个与 MD5 相同，第五个是新增的。

SHA1 已不再安全，谷歌已公布两个 SHA1 值相同的 PDF 文件（shattered）。而且只要使用给定的前 320 字节，后面任意添加相同的字节，哈希值仍然相同。

不依赖算法细节，仅与 Hash 值长度有关：

生日攻击 (Birthday Attack)：不利用 Hash 函数结构而只依赖消息摘要长度。由生日悖论，对 \(n\) 位哈希值，大约需要 \(2^{n/2}\) 次尝试即可找到碰撞。
中点交会攻击 (Meet-In-The-Middle)：生日攻击的变形，不比较 Hash 值而是比较中间变量，适用于具有分组链结构的 Hash 方案。

常用工具：HashCat

适用条件： - 针对所有采用 \(H(key \parallel message)\) 构造的散列函数。 - MD5 和 SHA-1 等基于 Merkle–Damgård 构造的算法均对此脆弱。

攻击前提： - 已知 key 的长度（或可爆破）。 - 可控制 message 的值。 - 已知包含 key 的某消息的 hash 值。

原理：

基于 Merkle–Damgård 构造的哈希函数： 1. 消息填充方式：消息后添加 1，填充若干 0 至与 448 同余，再附上 64 位消息长度。 2. 每一块得到的链接变量作为下一次执行 hash 函数的初始向量 IV，最后一块的链接变量才转换为 hash 值。

设已知 \(hash(key + s)\) 的值（\(s\) 已知），则：

\[ now = key \parallel s \parallel padding \]

若在 \(now\) 后附加额外信息 \(extra\)：

\[ key \parallel s \parallel padding \parallel extra \]

计算 hash 时： 1. 对 \(extra\) 进行填充。 2. 先计算 \(now\) 对应的链接变量 \(IV_1\)（由已知 hash 值通过可逆算法得出）。 3. 以 \(IV_1\) 为初始向量对 \(extra\) 部分执行哈希算法。

由于 \(s\)、\(padding\)、\(extra\) 均可控，攻击者可以找到满足 \(x = hash(key \parallel message)\) 的 \((message, x)\) 对。

工具：HashPump