生日攻击：为什么哈希碰撞比你想的快

题目

哈希函数输出 $n$ 位（共 $2^n$ 种可能）。攻击者想找到两个不同输入产生相同哈希（碰撞）。大约需要尝试多少个输入，命中概率才过半？

直觉可能觉得要试约 $2^{n-1}$ 个。其实少得多。

答案与解析

这是生日攻击（Birthday Attack），直接用生日悖论：

选 $k$ 个随机值，两两配对共 $\binom{k}{2}\approx k^2/2$ 对。当对数接近总可能数 $2^n$ 时，出现碰撞的概率激增。令 $\frac{k^2}{2}\approx 2^n \quad\Rightarrow\quad k\approx 2^{n/2}$

所以只需约 $2^{n/2}$ 次尝试，碰撞概率就约 50%——比直觉的 $2^{n-1}$ 少了一半的指数！例如 128 位哈希，理论上抗穷举要 $2^{128}$ 次，但抗碰撞只需约 $2^{64}$ 次。

背后的数学

它量化了“碰撞抵抗”与“原像抵抗”的天壤之别：找碰撞是生日问题（平方级），找指定原像是穷举（线性级）。现代哈希（SHA-256 等）因此把输出做得足够长，让 $2^{n/2}$ 也遥不可及。安全协议设计的第一课，就是别被“生日”骗了。