生日攻击与碰撞攻击

在 23 人的群体中，至少两人同一天生日的概率超过 50%。当人数达到 70 人时，该概率超过 99.9%。从数学上看，在大小为 N 的集合中，抽取约 √N 个样本后，发生碰撞的概率就会超过 50%。这就是生日界。

对于 n 位哈希函数，可以通过约 2^{n/2} 次随机尝试找到碰撞（H(m1) = H(m2)，m1 ≠ m2）。对于 SHA-256（256 位），找到碰撞需要约 2^{128} 的工作量，在计算上不可行。对于 MD5（128 位），需要约 2^{64} 的工作量，已接近可行。

通用碰撞查找：生成 2^{n/2} 条随机消息，计算哈希值，按哈希值排序，然后查找重复项。内存复杂度为 O(2^{n/2})。Rho 算法（Floyd 的循环查找算法）可以在相同的时间成本下将内存需求降至 O(1)。van Oorschot-Wiener 并行碰撞搜索则可以借助硬件降低时间成本。

Wang 等人在 2004 年使用差分密码分析发现了 MD5 的实际碰撞，而不是生日攻击。两条不同的 1024 位消息可以在数秒内产生相同的 MD5 哈希。Hertzbleed/选择前缀碰撞可以实现证书碰撞。MD5 在抗碰撞性方面已经彻底失效。

这种攻击更加强大：给定两个任意前缀 P1、P2，找出后缀 S1、S2，使得 H(P1||S1) = H(P2||S2)。Stevens 等人在 2017 年发现了选择前缀的 MD5 碰撞。该方法曾被用于创建带有有效 MD5 签名的恶意 CA 证书，并使 MD5 退出证书使用。

Google 的 SHAttered（2017 年）是首次实际可行的 SHA-1 碰撞：两个不同的 PDF 文件具有相同的 SHA-1 哈希。该攻击需要 2^{63.1} 次 SHA-1 压缩运算，相当于 6,500 个 CPU 年和 110 个 GPU 年，成本约为 110,000 美元。浏览器在 2017 年弃用了 SHA-1 证书。

对于 Merkle-Damgard 哈希函数（MD5、SHA-1、SHA-2）：如果您知道 H(m)，就可以在不知道 m 的情况下计算 H(m||padding||m')。这会破坏 H(secret||message) 这类 MAC 构造。修复方法：使用 HMAC（采用内层和外层填充），或使用 SHA-3（海绵构造，不受长度扩展影响）。

抗碰撞性：寻找任意两条不同的消息，使它们具有相同的哈希值（需要 2^{n/2} 的工作量）。抗第二原像性：给定 m，寻找满足 m' ≠ m 且具有相同哈希值的消息（需要 2^n 的工作量）。抗原像性：针对给定的哈希值寻找任意消息（需要 2^n 的工作量）。抗碰撞性始终是最弱的。

如果 MAC 使用了易受碰撞攻击的哈希函数，能够在 H 中找到碰撞的攻击者就可能伪造 MAC。尽管 MD5 存在碰撞，HMAC-MD5 仍被认为是安全的，因为 HMAC 的构造要求进行原像攻击，而不仅仅是碰撞攻击。不过，对于新系统，请不要继续使用 HMAC-MD5。

Joux（2004）指出：对于 Merkle-Damgard 哈希，寻找 2^k 路碰撞（具有相同哈希值的 2^k 条消息）只需要寻找一次碰撞所需工作量的 k 倍，而不是 2^k 倍。这会加剧级联哈希中的漏洞（H1(m)||H2(m) 并不像您想象的那么强）。

对于需要抗碰撞性的哈希，请使用 SHA-256 或 SHA-3。不要将 MD5 和 SHA-1 用于任何安全用途。对于 MAC：使用 HMAC-SHA-256 或 HMAC-SHA-3。对于密码哈希：使用 Argon2，而不是直接使用 SHA-2。需要抵抗长度扩展攻击时，请始终使用 SHA-3。

在 n 位哈希函数中寻找碰撞，大约需要计算多少次哈希？

生日攻击只需 2^{n/2} 的工作量就能找到哈希碰撞。MD5 已存在实际可行的选择前缀碰撞；SHA-1 在 2017 年被攻破。长度扩展攻击会攻破简单的 H(key||msg) MAC。请使用 SHA-256 或 SHA-3，并使用 HMAC 进行消息认证。下一节：中间相遇攻击。