生日攻击(Birthday Attack)

生日攻击(Birthday Attack)是一类针对密码学哈希函数的碰撞攻击,其名称与理论依据来自概率论中的生日悖论。它揭示了找到哈希碰撞所需的工作量,远比穷举整个输出空间要小得多。

概述

生日悖论指出,在一个仅23人的房间里,存在两人生日相同的概率就超过50%,这一结果常令人意外。类比到哈希函数,若输出为n位,攻击者平均只需尝试约2的n/2次方个输入,就有较大概率找到两个哈希值相同的不同输入,而非需要2的n次方次。

核心原理

• 碰撞抗性关注的是找到任意一对输入产生相同摘要,而非匹配某个指定摘要。
• 由于配对数量随样本数呈平方增长,碰撞出现得比直觉快得多。
• 因此,一个256位哈希对生日攻击的有效安全强度约为128位。

这也是为什么密码学哈希函数需要足够长的输出:例如128位摘要面对生日攻击仅有约64位安全强度,在现代算力下已不够安全,故推荐使用SHA-256等更长输出的算法。

应用场景

生日攻击的思想被用于评估数字签名、消息认证码和证书系统的安全边界。历史上,针对MD5和SHA-1的实际碰撞攻击就利用了这一原理,导致伪造证书等安全事件,促使业界淘汰这些弱哈希算法。

常见问题

问:生日攻击是否意味着哈希函数不安全?答:不是。只要哈希输出足够长(如256位),生日攻击所需的计算量仍高得不可行。它只是提醒设计者输出位数要留出安全余量。

问:如何防御生日攻击?答:选用输出更长、抗碰撞性经过验证的现代哈希算法,避免使用MD5、SHA-1等已被攻破的旧算法即可有效防御。