生日攻擊

生日攻擊

原圖鏈接

中文名: 生日攻擊 別 名: 平方根攻擊

生日攻擊是一種密碼學攻擊手段，所利用的是概率論中生日問題的數學原理。這種攻擊手段可用於濫用兩個或多個集團之間的通信。此攻擊依賴於在隨機攻擊中的高碰撞概率和固定置換次數（鴿巢原理）。

目錄

簡介

生日攻擊是一種密碼學攻擊手段，所利用的是概率論中生日問題的數學原理。這種攻擊手段可用於濫用兩個或多個集團之間的通信。此攻擊依賴於在隨機攻擊中的高碰撞概率和固定置換次數（鴿巢原理）。使用生日攻擊，攻擊者可在中找到散列函數碰撞，為原像抗性安全性。然而，量子計算機可在

內進行生日攻擊（雖然飽受爭論）。

理解問題

主條目：生日問題

舉個例子，想象一位老師問一個有30名學生的班級（n = 30）每個人的生日在哪一天（為簡便，此處省略閏年）以確定是否有兩個學生同一天生日（對應碰撞 ）。從直覺角度考慮，機率看起來很小。若老師選擇特定日期（例如9月16日），則至少有一名學生在那天出生的幾率是中可看出。

數字簽名敏感度

數位簽章可對生日攻擊十分敏感。設想一條被首次計算。假設愛麗絲與鮑伯牽涉到簽名詐騙合同。馬洛里準備了一份正常合同m和一份偽造合同m'。她隨後發現m所在的位置數可在不改變原意的情況下（如插入逗號、清空行、在句後增加一兩個空格、替換同義詞等等）被更改。通過結合這些更改，她可新建諸多m的變體且均為正常合同。

相似情況下，馬洛里也為偽造合同m'新建了諸多變體。她隨後應用哈希函數到所有變體直到她找到與正常合同有着相同哈希值

的偽造合同位置。她隨後將正常合同帶給鮑勃簽名。在鮑勃簽名完後，馬洛里將簽名取下並依附到偽造簽名上。此簽名「證實了」鮑勃簽署了偽造合同。

此例中，攻擊概率與原始的生日問題稍有不同，因為馬洛里將在尋找兩份具有相同哈希的正常合同與偽造合同時將一無所獲。馬洛里的策略是生成一份偽造和一份正常的合同。生日問題公式適用於n為合同對數的情況下。但馬洛里所生成的哈希數實際上為2n。

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

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

離散對數 Pollard Rho 算法是一項使用生日攻擊以計算離散對數的算法。

生日攻擊其實是一個概率論的問題，也就是說一個看起來很難發生的事情，事實上它發生的概率卻很大。這種主觀上和事實上的概率差距，讓隨機攻擊成功的幾率變的更高，這樣的攻擊就叫做生日攻擊。

生日問題的由來

生日問題也叫做生日悖論，它是這樣這樣描述的。

假如隨機選擇n個人，那麼這個n個人中有兩個人的生日相同的概率是多少。如果要想概率是100%，那麼只需要選擇367個人就夠了。因為只有366個生日日期（包括2月29日）。

如果想要概率達到99.9% ，那麼只需要70個人就夠了。50%的概率只需要23個人。

對於現在的幼兒園小朋友來說，一個班上差不多有30人，那麼將會有大於50%的幾率，班上有兩個人的生日是一樣的。

聽起來是不是很神奇？跟我們第一映像中的基數是不是要少很多。

生日問題的衍生

生日問題的取值範圍是在一年的365天之內，也就是說生日只可能有365種可能性。

我們將這個問題擴展一下到一般的情況，假設有一個函數f，它的輸出範圍是H，那麼我們的攻擊就是找到兩個不同的x，y，讓f(x)=f(y)。

這時候，我們可以稱x和y發生了碰撞。

生日攻擊的應用

生日攻擊一般應用在數字簽名中。一般來說為了對機密消息進行簽名，因為加密的限制，如果消息很大的情況下，不可能對所有的消息進行簽名，通常會對消息計算hash值，然後對這個hash值進行簽名。

比如有人想做一個欺詐性的合同，那麼會在原合同的基礎上進行修改，不斷的進行嘗試，從而找到一個修改後的合同，讓合同和之前合同的hash是一樣的，從而導致兩者的簽名也是一樣的。

怎麼抵禦這種攻擊呢？根據我們生日攻擊的公式，當然是將簽名方案使用的哈希函數的輸出長度選擇得足夠大，以使生日攻擊在計算上變得不可行。

另請參閱

碰撞攻擊

中途相遇攻擊