图书馆:Draft:生日攻击

Bluedeck Library 图书馆卡

Bluedeck Library 图书馆卡

本页面为“Draft:生日攻击”的存档，该页面已遭删除，本页面仅供参考用。

存档UTC时间	2018年8月10日 07:13
存档编者	ThirdThink
当前版本号	50803177

取得正常维基源码

{{d|G10}}

生日攻击是一种密码学攻击手段，所利用的是概率论中生日问题的数学原理。这种攻击手段可用于滥用两个或多个集团之间的通信。此攻击依赖于在随机攻击中的高碰撞概率和固定置换次数（鸽巢原理）。使用生日攻击，攻击者可在${\textstyle {\sqrt {2^{n}}}=2^{n/2}}$中找到散列函数碰撞，${\textstyle 2^{n}}$为{{tsl|en|preimage resistance|原像抗性|原像抗性}}安全性。然而，量子计算机可在${\textstyle {\sqrt[{3}]{2^{n}}}=2^{n/3}}$内进行生日攻击（虽然饱受争论）。

理解问题

{{Main article|生日问题}} 举个例子，想象一位老师问一个有30名学生的班级（n = 30）每个人的生日在哪一天（为简便，此处省略闰年）以确定是否有两个学生同一天生日（对应碰撞 ）。从直觉角度考虑，几率看起来很小。若老师选择特定日期（例如9月16日），则至少有一名学生在那天出生的几率是$1-(364/365)^{30}$，约为7.9%。但是，与我们的直觉相反的是，至少一名学生和另外任意一名学生有着相同生日的几率大约为700%（n = 30时），从方程$1-365!/((365-n)!\cdot 365^{n})$中可看出。

数学

给定函数$f$，攻击目标是找到符合$f(x_{1})=f(x_{2})$的两个不同输入$x_{1},x_{2}$。这一对$x_{1},x_{2}$被称之为碰撞。用于找到一对碰撞的方法仅需要评估函数$f$的随机或伪随机选择的不同输入值，直到攻击者找到相同的结果至少两次为止。由于生日问题，这种方法的效率不高。明确的说，若函数$f(x)$所拥有的$H$的不同输出有着相同可能性且$H$足够大的话，我们将期望在评估函数平均大约$1.25{\sqrt {H}}$个不同个自变量后才能得到符合$f(x_{1})=f(x_{2})$的不同一对自变量$x_{1}$和$x_{2}$。

思考下面一个实验。从下列的H数集中我们将随机均匀地选择n个值，因此将允许重复。使p（n; H）成为此实验中至少一个值被选择一次的概率。则几率可估计为

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

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

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

将碰撞几率设为0.5我们将得到

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

使Q（H）成为我们在寻找首次碰撞前所期望的值的数量。此数量可通过下列公式进行估计：

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

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

位数	可能输出（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），且假设所有哈希均有相同几率。为了比较，通常一块硬盘的不可修正比特错误率为10⁻¹⁸至10⁻¹⁵。理论上说，使用128位的MD5哈希或通用唯一识别码将在8200亿份文档时得到破解，即使它们的可能输出还要更多。

显而易见，若函数的输出不平均分布，碰撞则可能将被更快找到。哈希函数的“平衡”概念量化了其能抵御生日攻击（攻击平均的密钥分布）的次数。然而，确定哈希函数的平衡将需要计算所有输入，因此这种方法对于诸如MD及SHA系的流行哈希函数是不切实际的。 当计算$n(p;H)$中的子表达式$\ln {\frac {1}{1-p}}$翻译到常见的编程语言如log(1/(1-p))下，公式由于{{tsl|en|loss of significance|有效位丢失|有效位丢失}}对较小的$p$的计算精度不高。例如，当log1p（如{{tsl|en|C99||C99}}中一样）可用时，应直接使用可达到相同效果的表达式-log1p(-p)。 If this is not done, the first column of the above table is computed as zero, and several items in the second column do not have even one correct significant digit.

源码示例

下列是能准确生成上方表格中大多数数值的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

简单估计

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

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

可改写为

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

或

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

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

此近似方案在使用指数时可轻易使用。例如，假设您正构建32位哈希（$H=2^{32}$）且希望碰撞几率为100万分之一（$p\approx 2^{-20}$），则最多我们需要多少份文档？

$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次近似。

数字签名敏感度

数位签章可对生日攻击十分敏感。设想一条被首次计算$f(m)$（$f$为密码杂凑函数）所签名的信息，且随后又使用了一些密钥来签名$f(m)$。假设爱丽丝与鲍伯牵涉到签名诈骗合同。马洛里准备了一份正常合同$m$和一份伪造合同$m'$。她随后发现$m$所在的位置数可在不改变原意的情况下（如插入逗号、清空行、在句后增加一两个空格、替换同义词等等）被更改。通过结合这些更改，她可新建诸多$m$的变体且均为正常合同。

相似情况下，马洛里也为伪造合同$m'$新建了诸多变体。她随后应用哈希函数到所有变体直到她找到与正常合同有着相同哈希值$f(m)=f(m')$的伪造合同位置。她随后将正常合同带给鲍勃签名。在鲍勃签名完后，马洛里将签名取下并依附到伪造签名上。此签名“证实了”鲍勃签署了伪造合同。

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

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

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

离散对数 Pollard Rho 算法是一项使用生日攻击以计算离散对数的算法。

另请参阅

• {{tsl|en|Collision attack||碰撞攻击}}
• 中途相遇攻击

脚注

{{Reflist}}

参考文献

• {{tsl|en|Mihir Bellare||米希尔·贝拉尔}}，《等一下：哈希函数平衡及其对生日攻击的影响》（Tadayoshi Kohno: Hash Function Balance and Its Impact on Birthday Attacks） {{tsl|en|EUROCRYPT||EUROCRYPT}} 2004: pp401–418
• 《应用密码学》, 第二版。（Applied Cryptography, 2nd ed.） 布鲁斯·施奈尔所著

外部链接

• "What is a digital signature and what is authentication?" 来自{{tsl|en|RSA (security firm)||RSA安全}}加密的常见问题集。
• "Birthday Attack" X5网络加密问答

{{cryptography navbox | hash}}

Category:密码分析