生日攻擊

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

理解問題

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

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

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

主條目：生日問題

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

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

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

數學證明

定義函數${\displaystyle f}$，攻擊目標是找到符合${\displaystyle f(x_{1})=f(x_{2})}$的兩個不同輸入值${\displaystyle x_{1},x_{2}}$。這一對${\displaystyle x_{1},x_{2}}$被稱之為碰撞。找出一對碰撞值的方法可以是隨機（或偽隨機地）輸入不同的數值，直到找出至少兩個相同的結果為止。但根據生日問題所述，其實有著更為高效的方法。明確地說，若函數${\displaystyle f(x)}$所擁有的${\displaystyle H}$的不同輸出有著同等的可能性（即${\displaystyle P(H_{i})}$為常數）且${\displaystyle H}$足夠大，那麼，我們期望值找到${\displaystyle f(x_{1})=f(x_{2})}$的一對不同的自變數${\displaystyle x_{1}}$和${\displaystyle x_{2}}$，平均需要大約${\displaystyle 1.25{\sqrt {H}}}$個不同的自變數。

考慮以下的一個實驗；從下列的${\displaystyle H}$數集中均勻、隨機地選擇n個值，因此將允許重複。設p（n; H）為此實驗中至少一個值被選擇多於一次的機率。則該機率可以以下數學形式表達：

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

設n（p; H）為將選擇的最小數值，這種情況下找到碰撞的機率至少為 p。通過顛倒上方的表達式，可得到下列估算公式：

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

又將碰撞機率設為0.5，將得到

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

使Q（H）成為在尋找首次碰撞前所期望值的值的數量，則該量可通過下列公式進行估算：

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

舉例：若使用64位元雜湊，則估算將會有1.8 × 10¹⁹個不同的輸出。若這些輸出均可能發生（理想情況下），則攻擊者「僅僅」需要約50億次嘗試（5.38 × 10⁹）就能通過暴力攻擊生成碰撞。此值被稱為 生日界限（birthday bound）^[4]。而對於n位密碼則需要2^n/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)，且假設所有雜湊值均有同等的出現機率。為了方便比較，通常一塊硬碟的不可修正位元(bit)錯誤率設為10⁻¹⁸至10⁻¹⁵。^[6]理論上，使用128位元的MD5雜湊或通用唯一辨識碼將在8200億份文件時得到破解，即使它們的可能輸出要比那數大得多。

顯然而見，若函數的輸出不平均分布，則碰撞可能更快被找到。雜湊函數的「平衡」概念量化了其能抵禦生日攻擊（攻擊不平均的金鑰分布）的次數。然而，確定雜湊函數的平衡量將需要計算所有輸入，因此這種方法對於諸如MD及SHA系的流行雜湊函數是不切實際的。^[7] 當計算${\displaystyle n(p;H)}$中的子表達式${\displaystyle \ln {\frac {1}{1-p}}}$的常見程式設計語言的翻譯版本時，例如log(1/(1-p))，公式由於有效位遺失（英語：loss of significance），因而對於較小的${\displaystyle 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

簡約估算

一項經驗法則可適用於此關係中的心算流程

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

可改寫為

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

或

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

此公式在機率小於等於0.5時有效。

該近似方案在使用指數時可輕易使用。例如，假設構建32位元雜湊（${\displaystyle H=2^{32}}$）且希望碰撞機率為100萬分之一（${\displaystyle p\approx 2^{-20}}$），需要的文件數為

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

數字簽章敏感度

數位簽章可對生日攻擊十分敏感。設想一條被首次計算${\displaystyle f(m)}$（${\displaystyle f}$為密碼雜湊函數）所簽名的資訊，且隨後又使用了一些金鑰來簽名${\displaystyle f(m)}$。假設馬洛里想要使鮑勃簽上惡意合同；馬洛里準備了一份正常合同${\displaystyle m}$和一份偽造合同${\displaystyle m'}$。她隨後發現${\displaystyle m}$的一些位置可在不改變原意的情況下（如插入逗號、清空行、在句號後增加一兩個空格、同義詞替換等等）被更改。通過組合這些更改，她可新建諸多${\displaystyle m}$的變體且與該正常合同同義。

相似地，馬洛里也為偽造合同${\displaystyle m'}$新建了諸多變體。她隨後使用雜湊函數計算所有變體直到她找到與正常合同有著相同雜湊值${\displaystyle f(m)=f(m')}$的偽造合同版本。她隨後將正常合同該正常給鮑勃簽名。在鮑勃簽名後，馬洛里將該簽名複製至偽造合同上。該簽名「證實了」鮑勃簽署了該偽造合同。

在此例中，攻擊機率與原始的生日問題稍有不同，因為馬洛里在尋找兩份具有相同雜湊的正常合同與偽造合同時一無所獲。馬洛里是為了生成一對雜湊值相同的偽造和正常合同。生日問題公式適用於${\displaystyle n}$為合同對數的情況下。但馬洛里所生成的雜湊數實際上為${\displaystyle 2n}$。

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

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

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

另請參閱

• 碰撞攻擊（英語：Collision attack）
• 中途相遇攻擊