圖書館: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:密碼分析