Birthday Attack for Hash Function Analysis

概述

生日攻击是一种密码学攻击手段，它常用于攻击弱散列函数，因为它不具有抗强碰撞性。生日攻击源于概率论中的生日问题。

生日悖论问题

生日悖论（Birthday Paradox）可以表述为：不少于 23 个人中至少有两人生日相同的概率大于 50%。这个数学事实非常反直觉，因为这个概率比人们想象的要高得多。

假设有 n 个人，那么至少有两个人生日相同的概率可以使用下面的公式计算：
$$ P(n) = 1 - \frac {365!} {(365-n)! * {365} ^ n} $$

这个公式可以通过计算逆问题得到：计算 n 个人中没有两个人生日相同的概率 P’。 P’ 的计算很容易使用排列组合公式获得：
$$ P’ = \frac { A_{365} ^ n } { 365 ^ n } = \frac {365!} {(365 - n)! * {365 ^ n}} $$

然后 $ P = 1 - P’ $。

当 n = 23 时，$ P \approx 50 % $
当 n = 30 时，$ P \approx 70 % $
当 n = 40 时，$ P \approx 90 % $
当 n = 50 时，$ P \approx 97 % $

生日悖论普遍应用于检测散列函数：N bit 的散列函数可能发生的碰撞测试次数不是 $ 2 ^ N $ 而是 $ 2 ^ {N / 2} $。

生日攻击

生日攻击一般应用在数字签名中。数字签名通常首先对消息明文计算 HASH ，然后对这个 HASH 进行签名。为了抵御生日攻击，需要规定签名方案所使用的散列函数的输出长度足够大，以使生日攻击在计算上不可行。

哈希碰撞

上节中的公式可以进一步推导成一般性的、便于计算的形式。
根据泰勒公式，指数函数 $ e^x $ 可以用多项式展开：
$$ e^x = \sum_{k=0}^\infty\frac{x^k}{k!} = 1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \frac{x^4}{24} + … $$

如果 x 是一个极小的值，那么可以得到下面的近似公式：
$$ e^x \approx 1 + x $$

现在将生日问题中的 $ \frac{1}{365} $ 代入: $ e^{-\frac{1}{365}} \approx 1 - \frac{1}{365} $

因此，生日问题的概率公式，可以转化为：
$$\begin{align}
P’ &\approx 1 \cdot e^{-\frac{1}{365}} \cdot e^{-\frac{2}{365}} … \cdot e^{-\frac{n-1}{365}} \\
&= e ^ {- \frac{n(n-1)/2}{365}} \\
&= e ^ {- \frac{n(n-1)}{730}}\\
\end{align}$$

所以：
$$ P = 1 - P’ \approx 1 - e ^ {- \frac{n(n-1)}{730}} $$

假设 d 为 取消空间（在生日问题中 d = 365），就可以得到一般化公式：
$$ P(n,d) \approx 1 - e ^ {- \frac{n(n-1)}{2d}} $$