生日攻击
![本页使用了标题或全文手工转换](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![]() |
此条目翻译品质不佳。 (2018年8月10日) |
生日攻击是密码学的一种破译手段,利用了概率论中的生日问题,用于干扰两个或以上群体之间的通信。此攻击是对固定的重新排列模式作随机尝试攻击,仰赖较高的命中率(鸽笼原理)。生日攻击可在等级的时间内找到散列碰撞,低于原像攻击的 。有研究给出一个笼统(但尚存争议[1])的估计,表示量子电脑能够进行生日攻击,进而可以破解防散列碰撞的抵御,并能把时间压缩到 的等级。[2]
理解问题
[编辑]![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/47/Birthday_attack_vs_paradox.svg/220px-Birthday_attack_vs_paradox.svg.png)
举例来说,假设有一位老师带着一个有30位学生(n = 30)的班级,老师询问每位学生的生日(为了简化计算,忽略闰年),想要确认是否有两位学生的生日相同(这相当于稍后会提到的散列碰撞)。 直觉上,这个概率可能看起来很小。 但出乎意料的是,根据公式 计算,至少有一位学生的生日与其他任一天的生日相同的概率(n = 30)约为70%。 [3]
如果老师挑选了一个特定的日期(例如 9 月 16 日),那么至少有一位学生在该特定日期出生的概率是,约7.9%。
在生日攻击中,攻击者会准备多个不同版本的良性和恶意合约,每个合约都有一个数字签名。 目标是查找一对具有相同签名的良性和恶意合约。 在这个假设的例子中,假设字符串的数字签名是其SHA-256散列值的第一个字节。 找到的组合将以绿色表示——需要注意的是,找到两个良性合约(蓝色)或两个恶意合约(红色)的配对是无效的的。 当受害者接受良性合约后,攻击者会将其替换为恶意合约,并声称受害者已签署该合约,因为数字签名作为证据可以证明此。
数学
[编辑]定函数,攻击目标是找到符合的两个不同输入值。这一对被称之为碰撞。找出一对碰撞的方法可以是随机或伪随机地输入不同的数值,直到找出至少两个相同的结果为止。但由于生日问题,这种方法的效率不高。明确的说,若函数所拥有的的不同输出有着相同可能性且足够大,要获取符合的一对不同的自变量和,函数平均需要大约个不同个自变量。
思考下面一个实验。从下列的H数集中随机均匀地选择n个值,因此将允许重复。使p(n; H)成为此实验中至少一个值被选择多于一次的概率。则概率可估计为
使n(p; H)为将选择的最小数值,这种情况下找到碰撞的概率至少为 p。通过颠倒上方的表达式,可得到了下列估计公式:
将碰撞概率设为0.5,将得到
使Q(H)成为在寻找首次碰撞前所期望的值的数量。此数量可通过下列公式进行估计:
举例:若使用64位哈希,则估计将有1.8 × 1019个不同的输出。若这些输出均可能发生(理想情况下),则攻击者“仅仅”需要约50亿次尝试(5.38 × 109)就能通过暴力攻击生成碰撞。此值被称为 生日界限(birthday bound)[4]而对于n位密码则需要2n/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),且假设所有哈希均有相同概率。为了比较,通常一块硬盘的不可修正比特错误率为10−18至10−15。[6]理论上说,使用128位的MD5哈希或通用唯一识别码将在8200亿份文档时得到破解,即使它们的可能输出还要更多。
显而易见,若函数的输出不平均分布,碰撞则可能将被更快找到。哈希函数的“平衡”概念量化了其能抵御生日攻击(攻击平均的密钥分布)的次数。然而,确定哈希函数的平衡将需要计算所有输入,因此这种方法对于诸如MD及SHA系的流行哈希函数是不切实际的。[7]
当计算中的子表达式翻译到常见的编程语言形式下时,例如log(1/(1-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
简单估计
[编辑]可改写为
- .
或
- .
此公式在概率小于等于0.5时有效。
此近似方案在使用指数时可轻易使用。例如,假设构建32位哈希()且希望碰撞概率为100万分之一(),需要的文档数为
即与正确答案93次近似。
数字签名敏感度
[编辑]数字签名可对生日攻击十分敏感。设想一条被首次计算(为密码散列函数)所签名的信息,且随后又使用了一些密钥来签名。假设爱丽丝与鲍伯牵涉到签名诈骗合同。马洛里准备了一份正常合同和一份伪造合同。马洛里随后发现所在的位置数可在不改变原意的情况下(如插入逗号、清空行、在句后增加一两个空格、替换同义词等等)被更改。通过结合这些更改,她可新建诸多的变体且均为正常合同。
相似情况下,马洛里也为伪造合同新建了诸多变体。她随后应用哈希函数到所有变体直到她找到与正常合同有着相同哈希值的伪造合同位置。她随后将正常合同带给鲍勃签名。在鲍勃签名完后,马洛里将签名取下并依附到伪造签名上。此签名“证实了”鲍勃签署了伪造合同。
此例中,攻击概率与原始的生日问题稍有不同,因为马洛里将在寻找两份具有相同哈希的正常合同与伪造合同时将一无所获。马洛里的策略是生成一份伪造和一份正常的合同。生日问题公式适用于为合同对数的情况下。但马洛里所生成的哈希数实际上为。
为避免这种攻击,用于签名方案的哈希函数的输出长度应够大以从计算角度防止生日攻击。换言之,位数应为防止普通暴力破解所需位数的两倍。
除了使用更大的位数长度外,签名者(鲍勃)可以在签名前做出一些随机且无害的更改,并且在自己的手上留下一份合同副本以在法庭上展示出他的签名与正常合同上的匹配,而不匹配伪造合同。
离散对数的波拉德ρ算法是使用生日攻击以计算离散对数的算法。
另请参阅
[编辑]脚注
[编辑]- ^ Daniel J. Bernstein. Cost analysis of hash collisions : Will quantum computers make SHARCS obsolete? (PDF). Cr.yp.to. [29 October 2017]. (原始内容存档 (PDF)于2017-08-25).
- ^ Brassard, Gilles; HØyer, Peter; Tapp, Alain. Quantum cryptanalysis of hash and claw-free functions. Springer, Berlin, Heidelberg: 163–169. 20 April 1998 [29 October 2017]. doi:10.1007/BFb0054319. (原始内容存档于2020-08-08).
- ^ Birthday Problem. Brilliant.org. Brilliant_(website). [28 July 2023].
- ^ 请参阅上界和下界。
- ^ Jacques Patarin, Audrey Montreuil. Benes and Butterfly schemes revisited (PostScript, 可移植文档格式). Université de Versailles. 2005 [2007-03-15]. (原始内容存档于2007-09-29).
- ^ Gray, Jim; van Ingen, Catharine. Empirical Measurements of Disk Failure Rates and Error Rates. 25 January 2007. arXiv:cs/0701166
.
- ^ Archived copy. [2006-05-02]. (原始内容存档于2008-02-23).
- ^ Compute log(1+x) accurately for small values of x. Mathworks.com. [29 October 2017]. (原始内容存档于2012-08-30).
参考文献
[编辑]- 米希尔·贝拉尔,《等一下:哈希函数平衡及其对生日攻击的影响》(Tadayoshi Kohno: Hash Function Balance and Its Impact on Birthday Attacks) EUROCRYPT 2004: pp401–418
- 《应用密码学》, 第二版。(Applied Cryptography, 2nd ed.) 布鲁斯·施奈尔所著