生日攻擊

生日攻擊是密碼學的一種破譯手段，利用了機率論中的生日問題，用於干擾兩個或以上群體之間的通訊。此攻擊是對固定的重新排列模式作隨機嘗試攻擊，仰賴較高的命中率（鴿籠原理）。生日攻擊可在${\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$的不同輸出有着同等的可能性（即$P(H_{i})$為常數）且$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)，且假設所有哈希值均有同等的出現概率。為了方便比較，通常一塊硬盤的不可修正位元(bit)錯誤率設為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網絡加密問答