生日攻击

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

 

## 理解問題

舉個例子，想像一位老師問一個有 30 名學生的班級（n = 30）每個人的生日在哪一天（為簡便，此處省略閏年）以確定是否有兩個學生同一天生日（對應碰撞 ）。從直覺角度考慮，機率看起來很小。若老師選擇特定日期（例如 9 月 16 日），則至少有一名學生在那天出生的概率是 $1-(364/365)^{30}$ ，約為 7.9%。但是，與我們的直覺相反的是，至少一名學生和另外_任意_一名學生有著相同生日的概率大約為 70.63%（n = 30 時），從方程 $1-{\frac {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 × 1019 個不同的輸出。若這些輸出均可能發生（理想情況下），則攻擊者「僅僅」需要約 50 億次嘗試（5.38 × 109）就能通過暴力攻擊生成碰撞。此值被稱為 **生日界限**（birthday bound）而對於 _n_ 位密碼則需要 2n/2 次。下列舉出其他例子

　
:

　
: 表格展示了需要達到給定成功可能性的雜湊數量 _n_(_p_)，且假設所有雜湊均有相同概率。為了比較，通常一塊硬碟的不可修正位元錯誤率為 10−18 至 10−15。理論上說，使用 128 位元的 MD5 雜湊或通用唯一辨識碼將在 8200 億份文件時得到破解，即使它們的可能輸出還要更多。

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

若代碼儲存在命名為 `birthday.py` 的檔案中，您可和下面的例子一樣互動執行此程式：

### 簡單估計

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

　
: $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 網路加密問答