生日攻击

生日攻击是密码学的一种破译手段，利用了概率论中的生日问题，用于干扰两个或以上群体之间的通信。此攻击是对固定的重新排列模式作随机尝试攻击，仰赖较高的命中率（鸽笼原理）。生日攻击可在${\textstyle {\sqrt {2^{n}}}=2^{n/2}}$等级的时间内找到散列碰撞，低于原像攻击的 ${\textstyle 2^{n}}$。有研究给出一个笼统（但尚存争议^[1]）的估计，表示量子电脑能够进行生日攻击，进而可以破解防散列碰撞的抵御，并能把时间压缩到 ${\textstyle {\sqrt[{3}]{2^{n}}}=2^{n/3}}$ 的等级。^[2]

理解问题

比较生日问题 (1) 和生日攻击 (2)：

在（1）中，碰撞发生在同一组内，例如：24 位登月太空人中，276 组配对中有 3 组生日相同。

在（2）中，碰撞发生在两组之间，例如：针对良性和恶意合约各16种变体，取其SHA-256散列值的第一个字节，256组配对中找到1组碰撞。

主条目：生日问题

举例来说，假设有一位老师带着一个有30位学生（n = 30）的班级，老师询问每位学生的生日（为了简化计算，忽略闰年），想要确认是否有两位学生的生日相同（这相当于稍后会提到的散列碰撞）。 直觉上，这个概率可能看起来很小。 但出乎意料的是，根据公式 ${\displaystyle 1-{\frac {365!}{(365-n)!\cdot 365^{n}}}}$ 计算，至少有一位学生的生日与其他任一天的生日相同的概率（n = 30）约为70%。 ^[3]

如果老师挑选了一个特定的日期（例如 9 月 16 日），那么至少有一位学生在该特定日期出生的概率是${\displaystyle 1-(364/365)^{30}}$，约7.9%。

在生日攻击中，攻击者会准备多个不同版本的良性和恶意合约，每个合约都有一个数字签名。 目标是查找一对具有相同签名的良性和恶意合约。 在这个假设的例子中，假设字符串的数字签名是其SHA-256散列值的第一个字节。 找到的组合将以绿色表示——需要注意的是，找到两个良性合约（蓝色）或两个恶意合约（红色）的配对是无效的的。 当受害者接受良性合约后，攻击者会将其替换为恶意合约，并声称受害者已签署该合约，因为数字签名可以作为证据。

数学证明

定义函数${\displaystyle f}$，攻击目标是找到符合${\displaystyle f(x_{1})=f(x_{2})}$的两个不同输入值${\displaystyle x_{1},x_{2}}$。这一对${\displaystyle x_{1},x_{2}}$被称之为碰撞。找出一对碰撞值的方法可以是随机（或伪随机地）输入不同的数值，直到找出至少两个相同的结果为止。但根据生日问题所述，其实有着更为高效的方法。明确地说，若函数${\displaystyle f(x)}$所拥有的${\displaystyle H}$的不同输出有着同等的可能性（即${\displaystyle P(H_{i})}$为常数）且${\displaystyle H}$足够大，那么，我们期望找到${\displaystyle f(x_{1})=f(x_{2})}$的一对不同的自变量${\displaystyle x_{1}}$和${\displaystyle x_{2}}$，平均需要大约${\displaystyle 1.25{\sqrt {H}}}$个不同的自变量。

考虑以下的一个实验；从下列的${\displaystyle H}$数集中均匀、随机地选择n个值，因此将允许重复。设p（n; H）为此实验中至少一个值被选择多于一次的概率。则该概率可以以下数学形式表达：

${\displaystyle p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)}}$

设n（p; H）为将选择的最小数值，这种情况下找到碰撞的概率至少为 p。通过颠倒上方的表达式，可得到下列估算公式：

${\displaystyle n(p;H)\approx {\sqrt {2H\ln {\frac {1}{1-p}}}}}$

又将碰撞概率设为0.5，将得到

${\displaystyle n(0.5;H)\approx 1.1774{\sqrt {H}}}$

使Q（H）成为在查找首次碰撞前所期望的值的数量，则该量可通过下列公式进行估算：

${\displaystyle Q(H)\approx {\sqrt {{\frac {\pi }{2}}H}}}$

举例：若使用64位哈希，则估算将会有1.8 × 10¹⁹个不同的输出。若这些输出均可能发生（理想情况下），则攻击者“仅仅”需要约50亿次尝试（5.38 × 10⁹）就能通过暴力攻击生成碰撞。此值被称为 生日界限（birthday bound）^[4]。而对于n位密码则需要2^n/2次；^[5]下面列出其他例子

位数	可能输出（H）	期望的随机碰撞可能性 （2安全系数）（p）
		10−18	10−15	10−12	10−9	10−6	0.1%	1%	25%	50%	75%
16	216 (~6.5 x 104)	<2	<2	<2	<2	<2	11	36	190	300	430
32	232 （~4.3 × 109）	<2	<2	<2	3	93	2900	9300	50,000	77,000	110,000
64	264 （~1.8 × 1019）	6	190	6100	190,000	6,100,000	1.9 × 108	6.1 × 108	3.3 × 109	5.1 × 109	7.2 × 109
128	2128 （~3.4 × 1038）	2.6 × 1010	8.2 × 1011	2.6 × 1013	8.2 × 1014	2.6 × 1016	8.3 × 1017	2.6 × 1018	1.4 × 1019	2.2 × 1019	3.1 × 1019
256	2256 （~1.2 × 1077）	4.8 × 1029	1.5 × 1031	4.8 × 1032	1.5 × 1034	4.8 × 1035	1.5 × 1037	4.8 × 1037	2.6 × 1038	4.0 × 1038	5.7 × 1038
384	2384 （~3.9 × 10115）	8.9 × 1048	2.8 × 1050	8.9 × 1051	2.8 × 1053	8.9 × 1054	2.8 × 1056	8.9 × 1056	4.8 × 1057	7.4 × 1057	1.0 × 1058
512	2512 （~1.3 × 10154）	1.6 × 1068	5.2 × 1069	1.6 × 1071	5.2 × 1072	1.6 × 1074	5.2 × 1075	1.6 × 1076	8.8 × 1076	1.4 × 1077	1.9 × 1077

上表展示了需要达到给定成功可能性的哈希数量n(p)，且假设所有哈希值均有同等的出现概率。为了方便比较，通常一块硬盘的不可修正比特(bit)错误率设为10⁻¹⁸至10⁻¹⁵。^[6]理论上，使用128位的MD5哈希或通用唯一识别码将在8200亿份文档时得到破解，即使它们的可能输出要比那数大得多。

显然而见，若函数的输出不平均分布，则碰撞可能更快被找到。哈希函数的“平衡”概念量化了其能抵御生日攻击（攻击不平均的密钥分布）的次数。然而，确定哈希函数的平衡量将需要计算所有输入，因此这种方法对于诸如MD及SHA系的流行哈希函数是不切实际的。^[7] 当计算${\displaystyle n(p;H)}$中的子表达式${\displaystyle \ln {\frac {1}{1-p}}}$的常见程序设计语言的翻译版本时，例如log(1/(1-p))，公式由于有效位丢失（英语：loss of significance），因而对于较小的${\displaystyle p}$的计算精度不高。例如，在log1p（如C99中一样）和-log1p(-p)均可用时，后者应被选择，而非较为不精确的前者。^[8] 如果不这样做，上表的第一列将被计算为零，而对于第二列中的某几项甚至没有一个正确的有效数字。

源码示例

下列是能准确（大概）生成上方表格中大多数数值的Python函数：

from math import log1p, sqrt

def birthday(probability_exponent, bits):
    probability = 10.0**probability_exponent
    outputs = 2.0**bits
    return sqrt(2.0*outputs*-log1p(-probability))

若代码保存在命名为birthday.py的文件中，用户可像下面的例子一样运行此程序：

$ python -i birthday.py
>>> birthday(-15, 128)
824963474247.1193
>>> birthday(-6, 32)
92.68192319417072

简约估算

一项经验法则可适用于此关系中的心算流程

${\displaystyle p(n)\approx {n^{2} \over 2H}}$

可改写为

${\displaystyle H\approx {n^{2} \over 2p(n)}}$.

或

${\displaystyle n\approx {\sqrt {2H\times p(n)}}}$.

此公式在概率小于等于0.5时有效。

该近似方案在使用指数时可轻易使用。例如，假设构建32位哈希（${\displaystyle H=2^{32}}$）且希望碰撞概率为100万分之一（${\displaystyle p\approx 2^{-20}}$），需要的文档数为

${\displaystyle n\approx {\sqrt {2\times 2^{32}\times 2^{-20}}}={\sqrt {2^{1+32-20}}}={\sqrt {2^{13}}}=2^{6.5}\approx 90.5}$

即与正确答案93次近似。

数字签名敏感度

数字签名可对生日攻击十分敏感。设想一条被首次计算${\displaystyle f(m)}$（${\displaystyle f}$为密码散列函数）所签名的信息，且随后又使用了一些密钥来签名${\displaystyle f(m)}$。假设马洛里想要使鲍勃签上恶意合同；马洛里准备了一份正常合同${\displaystyle m}$和一份伪造合同${\displaystyle m'}$。她随后发现${\displaystyle m}$的一些位置可在不改变原意的情况下（如插入逗号、清空行、在句号后增加一两个空格、同义词替换等等）被更改。通过组合这些更改，她可新建诸多${\displaystyle m}$的变体且与该正常合同同义。

相似地，马洛里也为伪造合同${\displaystyle m'}$新建了诸多变体。她随后使用哈希函数计算所有变体直到她找到与正常合同有着相同哈希值${\displaystyle f(m)=f(m')}$的伪造合同版本。她随后将正常合同该正常给鲍勃签名。在鲍勃签名后，马洛里将该签名复制至伪造合同上。该签名“证实了”鲍勃签署了该伪造合同。

在此例中，攻击概率与原始的生日问题稍有不同，因为马洛里在查找两份具有相同哈希的正常合同与伪造合同时一无所获。马洛里是为了生成一对哈希值相同的伪造和正常合同。生日问题公式适用于${\displaystyle n}$为合同对数的情况下。但马洛里所生成的哈希数实际上为${\displaystyle 2n}$。

为了避免这种攻击，用于签名方案的哈希函数的输出长度应够大以从数学上防止生日攻击。换言之，位数应为防止普通暴力破解所需位数的两倍。

除了使用更大的位数长度外，签名者（鲍勃）可以在签名前做出一些随机且无害的更改，并且在自己的手上留下一份合同副本以在法庭上展示出他的签名与正常合同上的匹配，而不匹配伪造合同。

离散对数的波拉德ρ算法是使用生日攻击以计算离散对数的算法。

另请参阅

• 碰撞攻击（英语：Collision attack）
• 中途相遇攻击