生日攻擊

生日攻擊是密碼學的一種破譯手段，利用了機率論中的生日問題，用於干擾兩個或以上群體之間的通訊。此攻擊是對固定的重新排列模式作隨機嘗試攻擊，仰賴較高的命中率（鴿籠原理）。生日攻擊可在${\textstyle {\sqrt {2^{n}}}=2^{n/2}}$等級的時間內找到雜湊碰撞，低於原像攻擊的 ${\textstyle 2^{n}}$。有研究給出一個籠統（但尚存爭議）的估計，表示量子電腦能夠進行生日攻擊，進而可以破解防雜湊碰撞的抵禦，並能把時間壓縮到 ${\textstyle {\sqrt[{3}]{2^{n}}}=2^{n/3}}$ 的等級。

理解問題

比較生日問題 (1) 和生日攻擊 (2)：

在（1）中，碰撞發生在同一組內，例如：24 位登月太空人中，276 組配對中有 3 組生日相同。

在（2）中，碰撞發生在兩組之間，例如：針對良性和惡意合約各16種變體，取其SHA-256雜湊值的第一個位元組，256組配對中找到1組碰撞。

主條目：生日問題

舉例來說，假設有一位老師帶著一個有30位學生（n = 30）的班級，老師詢問每位學生的生日（為了簡化計算，忽略閏年），想要確認是否有兩位學生的生日相同（這相當於稍後會提到的雜湊碰撞）。 直覺上，這個機率可能看起來很小。 但出乎意料的是，根據公式 $1-{\frac {365!}{(365-n)!\cdot 365^{n}}}$ 計算，至少有一位學生的生日與其他任一天的生日相同的機率（n = 30）約為70%。

如果老師挑選了一個特定的日期（例如 9 月 16 日），那麼至少有一位學生在該特定日期出生的機率是$1-(364/365)^{30}$，約7.9%。

在生日攻擊中，攻擊者會準備多個不同版本的良性和惡意合約，每個合約都有一個數位簽章。 目標是尋找一對具有相同簽章的良性和惡意合約。 在這個假設的例子中，假設字串的數位簽章是其SHA-256雜湊值的第一個位元組。 找到的組合將以綠色表示——需要注意的是，找到兩個良性合約（藍色）或兩個惡意合約（紅色）的配對是無效的的。 當受害者接受良性合約後，攻擊者會將其替換為惡意合約，並聲稱受害者已簽署該合約，因為數位簽章作為證據可以證明此。

數學

定函數$f$，攻擊目標是找到符合$f(x_{1})=f(x_{2})$的兩個不同輸入值$x_{1},x_{2}$。這一對$x_{1},x_{2}$被稱之為碰撞。找出一對碰撞的方法可以是隨機或偽隨機地輸入不同的數值，直到找出至少兩個相同的結果為止。但由於生日問題，這種方法的效率不高。明確的說，若函數$f(x)$所擁有的$H$的不同輸出有著相同可能性且$H$足夠大，要取得符合$f(x_{1})=f(x_{2})$的一對不同的自變數$x_{1}$和$x_{2}$，函數平均需要大約$1.25{\sqrt {H}}$個不同個自變數。

思考下面一個實驗。從下列的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))，公式由於有效位遺失對較小的$p$的計算精度不高。例如，當log1p（如C99中一樣）可用時，應直接使用可達到相同效果的表達式-log1p(-p)。 如果不這樣做，上表的第一列將被計算為零，而第二列中的幾項甚至沒有一個正確的有效數字。

原始碼範例

下列是能準確生成上方表格中大多數數值的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$。

為避免這種攻擊，用於簽章方案的雜湊函數的輸出長度應夠大以從計算角度防止生日攻擊。換言之，位數應為防止普通暴力破解所需位數的兩倍。

除了使用更大的位數長度外，簽章者（鮑勃）可以在簽章前做出一些隨機且無害的更改，並且在自己的手上留下一份合同副本以在法庭上展示出他的簽章與正常合同上的匹配，而不匹配偽造合同。

離散對數的波拉德ρ演算法是使用生日攻擊以計算離散對數的演算法。

另請參閱

• 碰撞攻擊
• 中途相遇攻擊

參考文獻

• 米希爾·貝拉爾，《等一下：雜湊函數平衡及其對生日攻擊的影響》（Tadayoshi Kohno: Hash Function Balance and Its Impact on Birthday Attacks） EUROCRYPT 2004: pp401–418
• 《應用密碼學》, 第二版。（Applied Cryptography, 2nd ed.） 布魯斯·施奈爾所著

外部連結

• "What is a digital signature and what is authentication?" 來自RSA安全加密的常見問題集。
• "Birthday Attack" （頁面存檔備份，存於網際網路檔案館） X5網路加密問答