生日攻擊是什麼，有什麼用？

12-06

百度上搜索了不是很明白求大神通俗解釋

謝邀（來知乎第一次被邀請誒
題主所說的生日攻擊是一個密碼學的術語廣泛用於計算機領域它來自於概率統計中的生日問題。

要通俗的理解生日攻擊，我們可以先來看一下什麼是生日問題：
生日問題：在n個人中隨機選取k個人，當k為多大時能保證k個人中有兩個人的生日是相同的？

你可能會說答案是366，因為一年有365天（除去閏年），根據鴿籠原理（pigeon hole principle)，如果有366個人，那麼其中兩個人必定會在同一天過生日。
但其實，用統計學的方法來考慮生日問題之後，我們會驚訝地發現，所需要的人數k遠小於366。
只要k=70，隨機選取70個人，這其中兩個人有相同生日的可能性就是99.9%，可能性已經非常大了！在k=100時，小於366的三分之一，這個概率能達到99.99997%；而在k=200時，可能性已經是99.9999999999999999999999999998%了！啊！多麼的！吃驚！（數據來自wikipedia）
那麼是怎麼得到這個結果的呢？
假設至少有兩個人同一天生日的概率為P，
那麼P的否定（我們寫做1-P）就是沒有任何兩個人在同一天過生日的概率。
假設我們有k個人，
那麼這k個人中沒有任何兩個人在同一天過生日的概率就是：

最後解出來，當k=70的時候，P=99.9%
這就是生日問題。
那麼會到題主所問的生日攻擊，我們來看一個計算機領域中經常用到的東西：Hash functions（中文好像是散列演算法/哈希演算法我也不清楚）簡而言之就是用來把一樣東西經過特定運算轉換成另一樣東西，輸出的結果類型一定是相同的，更加嚴謹一點，長度也是相同的。這有點像密碼，把你要傳遞的信息通過一些辦法變成密碼，無論信息是多是少，最後得到的密文一定是同一種類型的。
比如fn x = x就是一個hash function，但是它沒什麼用，因為給它什麼它還是照原樣吐出來。
更高級的hash function有比如java中給字元串加密用的迭代方程

（我隨便編的數字）得到一個連它媽媽都不認識它的一個數字。
一個hash function的好壞，就在於它是否能夠使輸出的值盡量分散，減少輸出值的碰撞(collision)，這樣就能避免兩樣東西得到同樣的輸出，比如fn x=0就是一個非常不好的hash function，因為所有東西都被輸出成了0；
在安全性方面，hash function必須做到夠複雜，讓人不能夠通過簡單的幾組輸入輸出結果猜出來這個hash function用的是什麼樣的演算法，比如給你f(2)=4, f(3)=6, f(17361)=34722，是不是很容易猜出這個f是什麼？

說了這麼多，其實生日攻擊就是寫出好的hash function最大的絆腳石。如果你把hash function的每個輸入值想成是n個人中的一個，再把輸出值想成是每個人的生日，那麼生日問題就告訴我們，只需要很少的輸入值，就會有很大的可能性有至少兩個輸出值完全相同，也就違反了hash function的條件之一。
這就是生日攻擊。
（注意這裡並不是給定一個輸出值和輸入值尋找另一個能夠得到相同輸出值的輸入值所需的次數，而是隨意嘗試幾個輸入值，能在其中得到相同輸出值的總次數。）
再深入一點的話，可以把hash function看作是一種mapping（投影？）輸入值就是定義域，輸出是值域。注意hash function不一定是一一映射(1-to-1)的，因為定義域和值域的大小不一定相同。大多數情況，為了得到更高的效率和可操作性，hash function的值域都會遠小於定義域。在這樣的值域當中，碰撞就是必然的。可以想像成把復活節的彩蛋放進籃子里，各式各樣的彩蛋只能放進5個有編號的不同籃子里，必定有多個彩蛋在同一個籃子里。這裡彩蛋是定義域，籃子是值域。
生日攻擊能夠奏效就是因為這個值域太小，像我們的生日問題中值域只有365，所以只要70個人就能夠找到相同生日的兩個人。

題主還可以了解一下一些類似的有趣問題，比如Monty-Hall Problem之類的:)
另外感謝@HT.zou和@八里土人的評論！;D

生日攻擊其實在我看來和雙向廣搜，中途相遇（meet-in-the-middle attack）差不多的以空間換時間的方法，科普向
基本的模型是非常清楚的，任意一群人，由於一年有365天（不算閏年）,當人群數量大於23個人時，有超過50%的概率有兩個人生日相同，這個通過古典概型可以很容易算出來。有意義的是23小於365

對於更一般的情況，即一年有N天的時候，當人群數量大於1.17*sqrt{N} 的時候有超過50%的概率有兩個人生日相同。

生日攻擊，一般是指對hash的攻擊。hash的話例如常見的MD5，SHA1，或是字元串hash，又或者是直接模N，可以發現都是把數量為無線的數據、字元串、文件映射成有限長的hash，因此這個映射一定不是單射，這樣的hash函數肯定存在兩個數據M1， M2，使得HASH(M1) = HASH(M2)我們稱之為碰撞，因此對於hash的破解和對cipher的破解不一樣，並不意味著對於一串密文和密鑰能夠得到明文，而是找到一個碰撞
在實際用途上，hash經常被用來驗證數據是否被修改，例如下載文件的時候時常會有一個文件的MD5，當下載下來後自己電腦上計算出來的文件的MD5和官網上的不同後，可以很輕易的得出文件被修改過的結論、

但如果出現一個強碰撞，使得一個惡意可執行文件的MD5和官網的這個MD5發生碰撞，那麼你會以為這個就是官網的版本而信任的執行它，這個時候就不好了。

又或者，我說我能預測下屆世界盃冠軍是誰，可我不說出來，我公布一串HASH，等到世界盃結果出來，我把下面的文字公布出來「中國會奪得世界盃冠軍」，並聲稱我成功預測了世界盃，不信？把這文字計算HASH後和我之前發布的HASH比較一下。trick很簡單，假設HASH(「中國會奪得世界盃冠軍」)和HASH("巴西贏")和HASH(「德國必勝」)值是相同的，到最後我只要看結果是啥，公布這些HASH相同的字元串即可

是不是很可怕？所以怎麼找到一組碰撞呢？假設我有一組字元串"巴西(會|能)(奪|奪得)本(次|屆)世界盃(冠軍|第一)"很容易開出，替換括弧里的兩個詞，我近能生成2^4個意義相同的不同的字元串，因此很容易通過替換近義詞之類的方法，生成指數級別的不同的但意義相同的字元串。
這個時候，如果我們把「中國奪冠」和生成的這些字元串的HASH進行比較，那麼生成的字元串的數量需要多大呢？這個相當於問你，你走到一個班級，需要班級至少存在多少人，才會有非常大的概率有一個人和你的生日相同？可以利用遞推非常容易的計算這個概率,可以發現的是，人數比之前那種情況大得多
p_1 = frac{1}{365}
p_n = p_{n-1} +(1-p_{n-1})*frac{1}{365}

那有沒有好一點的辦法呢？有的，對於「中國奪冠」，我同樣生成一個意思相同的字元串的集合，以MD5為例子，它有128位，在原模型中，相當於有2^128天，於是我只需要生成根號2^128也就是2^64的字元串的集合，就有50%以上的概率有兩個字元串的MD5值相同，大大的減少了運算

可以看到的是，生日攻擊並沒有利用任何HASH函數的性質，是對任何HASH都適用的普適的攻擊方法，應對方法也很簡單，增加HASH的長度，例如MD5 2^64仍然是個天文數字，而SHA1消息長度是160位，也就是需要生成2^80次方的字元串才能攻擊成功，這更是不可能

# -1. 吐槽與說明

這篇是在公司用markdown寫的，沒人看就不轉成HTML了，有人看我再轉下。
嚴格意義上，第#4節與#5節說的是生日攻擊相關內容，往前為背景，往後為應用。
涉及理論與推導部分難免有些枯燥，不喜歡可以跳過。

# 0. 前言

當我們需要識別一個圖片、文檔或一大段文字的唯一性時，最簡單的辦法是直接比較兩份數據是否完全一致。但這樣做不僅效率低下，而且不方便(索引)查找。

所以一般情況，我們會使用消息摘要演算法得到一個定長的壓縮數據，來代表源文件。

我們平時最常用的MD5就是一種消息摘要演算法，同時也是一種哈希演算法。那麼，什麼是消息摘要，什麼是哈希，兩者又有什麼區別呢？更重要的是，MD5的值是唯一的么，會不會兩個文件對應同一個MD5呢？

# 1. 消息摘要

### 1.1 什麼是消息摘要？

消息摘要（Message Digest）又稱為數字摘要(Digital Digest)。它是一個唯一對應一個消息或文本的固定長度的值，它由一個單向Hash加密函數對消息進行作用而產生。它有固定的長度，且不同的明文摘要成密文，其結果總是不同的，而同樣的明文其摘要必定一致。這樣這串摘要便可成為驗證明文是否是"真身"的"指紋"了。

# 2. 哈希

### 2.1 什麼是哈希？

哈希就是把任意長度的輸入，通過散列演算法，變換成固定長度的輸出。

這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

哈希演算法也叫散列演算法，一般來說滿足這樣的關係：f(data)=key，輸入任意長度的data數據，經過哈希演算法處理後輸出一個定長的數據key。同時這個過程是不可逆的，無法由key逆推出data。

一個好哈希演算法，必須具備均勻的真正隨機輸出。

### 2.2 最簡單常用的哈希演算法

* 直接取余
* 乘法取整
* 平方取中

而對於這幾種哈希演算法，產生哈希碰撞是非常容易的，比如取余。

### 2.3 哈希與消息摘要

由於信息摘要要求唯一性，所以以上簡單粗暴的哈希演算法並不能作為消息息摘要演算法來使用。

消息摘要是哈希演算法的一種應用，而消息摘要演算法是一種碰撞要求極其嚴格的哈希演算法。

目前常用的消息摘要演算法有：

* MD5
* SHA（SHA-1、SHA-256、SHA-512等）

這些信息摘要演算法通常散列都十分均勻，且不容易產生哈希碰撞。

# 3. 哈希碰撞

### 3.1 什麼是哈希碰撞？產生哈希碰撞的原因是什麼？

兩個不同的輸入，經過哈希演算法後，得到了同樣的哈希值，就叫做哈希碰撞。

由於通常的哈希演算法中，哈希值的空間遠小於輸入的空間，這就意味著信息熵有丟失。

一個空間較大的集合(輸入)通過哈希演算法映射到一個空間較小的集合(哈希值)，必然會造成多個輸入映射到一個哈希值上，這就是所謂的哈希碰撞。

這就是說當輸入的可能性被完全枚舉時，一定會產生哈希碰撞。那麼輸入是完全枚舉集合的子集時呢？

舉一個最簡單的例子，輸入範圍是數字0-9，通過取餘3的哈希函數進行映射，如果輸入集合是{0,1,2,3,4,5,6,7,8,9}，那麼必然會產生哈希衝突；如果輸入集合只有兩個數字，哈希值未必衝突。

### 3.2 如何避免哈希碰撞？

根據以上場景可以看得出來：在哈希函數足夠均勻的情況下，是否會產生哈希碰撞是由輸入集合的大小(size)與哈希值的大小(length)共同決定的。

所以當選取了一個足夠均勻的消息摘要演算法時，是否產生哈希碰撞主要是由輸入樣本的數量決定的，而不是單個輸入樣本的大小。

避免哈希碰撞的主要手段是，根據輸入集合的數量級，選取輸出合適哈希值長度的哈希函數，將哈希碰撞的概率降為「幾乎不可能」。

那麼，如何判斷計算產生哈希碰撞的概率，並選取合適的消息摘要演算法呢？我們先看來看一個故事……

# 4. 生日悖論

### 4.1 什麼是生日悖論？

23個人里有兩個生日相同的人的幾率有多大呢？

居然有50%

生日悖論：如果一個房間里有23個或23個以上的人，那麼至少有兩個人的生日相同的概率要大於50%。對於60人以上，這種概率要大於99%。

嚴格意義上，這並不是一個悖論，稱之為悖論是由於跟人們的常識相悖。

### 4.2 計算過程

所以所有人生日都不相同的概率是：

那麼，n個人中有至少兩個人生日相同的概率就是：

所以當n=23的時候，概率為0.507；

當n=100的時候，概率為0.999999692751072。

在哈希演算法中，將人數對應為輸入樣本數量，將一年365天對應為哈希值的位數。
由此可以看出，產生哈希衝突所需的輸入樣本數量，遠低於所有可能哈希值的全集數量。

以此為基礎，就產生了一個基於哈希碰撞的安全攻擊方式，叫做生日攻擊。

# 5. 生日攻擊

### 5.1 什麼是生日攻擊？

不好意思，生日攻擊當然不是指這個……

生日攻擊是以概率論中的生日問題為數據基礎的一種密碼學攻擊方法。

### 5.2 生日攻擊舉例

根據生日悖論，如果哈希值的位數過短，很容易可以找到一組(兩個)哈希值相同的輸入，這就是一種最常用的生日攻擊的應用。

使用一個64位的哈希函數，大約有 1.8 × 10^19 個不同的哈希值。
如果產生每個哈希值的可能性是相同的，那麼只需大約 5.1 x 10^9 次(51億次)暴力嘗試就可以得到一次哈希碰撞。

51億次叫做birthday bound (生日邊界)。那麼51億次是如何得出的呢？

### 5.3 參考數據

根據生日悖論(公式推導略)，n位的哈希值預計產生一次碰撞需要2^(n/2)次嘗試。

下表展示了不同位數的哈希值，如果想要達到某個碰撞概率，需要嘗試多少次。
將上面例子對應到下表為，64Bits那一行的倒數第二列。

根據此表，就可以計算平時使用的哈希值位數在哪個數量級下是安全的。
SATA硬碟一個bit位出現數據錯誤的概率在 10^-18 到 10^-15 之間。作為比較，我們將哈希碰撞的概率控制在 10^-15 範圍內已經相對來說非常安全了。

!!!此處為數據結論!!!
理論上，128位的MD5哈希演算法，輸入數據保持在8.2x10^11(8200億)個以內是非常安全的，基本不會產生哈希碰撞。
同樣，SHA-256的輸入樣本需要保持在1.5x10^31個以內；
SHA-512的輸入樣本需要保持在5.2x10^69個以內。

但是！只控制輸入樣本集大小就可以足夠安全，高枕無憂了嗎？這還不夠。
某些情況下，還要考慮哈希演算法是否有主動碰撞的風險？主動碰撞是否對業務有致命傷害？

# 6. 主動碰撞簡介

王小雲教授帶領的研究小組於2004年、2005年先後破解了被廣泛應用於計算機安全系統的MD5和SHA-1兩大密碼演算法。

MD5、HAVAL-128、MD4、RIPEMD、SHA-1演算法可以主動製造兩個不同的文件，而哈希值相同。

需要注意的是，這些演算法仍然是不可逆的。破解僅限於主動製造兩個文件。

所以在使用MD5和SHA-1，一定要注意主動製造兩個哈希值相同的不同文件是否會造成致命傷害。

如果業務對這種情況零容忍，解決辦法也很簡單：加鹽（SALT）。
簡單說就是在輸入數據上額外加一些數據(SALT)後，再進行哈希。

主動碰撞與加鹽這裡不詳細解釋了，有人看的話再補充上來～

# 7. 總結

這更多是一片技術文，在實際應用中，參考5.3一節中的數據，並且考慮下是否需要加鹽就可以了。

我們團隊所負責的某個（脫敏）應用，目前輸入樣本存量已經達到了千億（脫敏）級別，已經接近了128位哈希演算法(例如MD5)的碰撞臨界值。
所以考慮到數據增長率以及安全性，計算圖片指紋時採用了SHA-512。

MD5為16位元組，速度最快；
SHA-1是20位元組，速度比MD5慢20%；
SHA-256時32位元組，速度比MD5慢60%。

性能不是極為苛刻時，採用SHA-256或SHA-512相對於MD5與SHA-1會帶來更好的穩定性與安全性。

以上部分內容為個人觀點，如有不嚴謹或錯誤之處，歡迎批評指教。感謝。

謝邀
生日攻擊，也稱作平方根攻擊，屬於暴力碰撞的一種。
其一個簡單的例子就是一個班 60 個同學，出現其中至少兩個同學生日相同的概率大於 99%；而更苛刻一點，只要 23 個同學就能使得概率接近 50%。
這種違背錯覺的問題，也被稱為生日悖論，並非真正的「悖論問題」

回到生日攻擊。
由於是屬於暴力窮舉的一種，所以它能對任何類型的散列函數進行攻擊。
比如對於一個散列函數 $f$ 其散列長度為 $2^{n}$ ，我們要對其進行碰撞攻擊，也就是找到一組 $x_1,x_2$ ，使得 $f(x_1)=f(x_2)$ ，最暴力的方法就是分別枚舉 $x_1,x_2$ ，這時候的複雜度是 $2^{2n}$ .
而如果利用生日攻擊的理論，我們只需要枚舉出 $sqrt{2^n}$ 個 $x$ ，就有 $frac{1}{2}$ 的概率獲得一組碰撞，複雜度大大降低。

當然應對的辦法很簡單，讓 $2^n$ 儘可能大，這樣即使生日攻擊也是一個天文數字。

-----------------------------
雖說 md5 的範圍有 $2^{128}$ ，然而還是不安全，下面給出兩張利用「構造前綴碰撞攻擊」構造的圖片，二進位文件不同，但 md5 完全一樣
http://ww2.sinaimg.cn/large/a15b4afegw1fblft9lnobj204g04gjrg
http://ww2.sinaimg.cn/large/a15b4afegw1fblfxyhb17j204g04gjrg

首先要理解什麼叫哈希碰撞。
比如你有一個映射，能把任意一串字元串映射到一個32位的字元串上。即輸入字元串，輸出定長字元串。我們把這個映射成為哈希函數。理想狀態下，我們總是希望不同的輸入對應不同的輸出。但這是不可能的，因為這個函數的定義域是無限的(任意一個字元串)，值域卻是有限的(所有32位字元串)。所以一定會出現「兩串輸入的字元串不同，但哈希函數的輸出相同」的情況。
這也就是所謂的哈希碰撞：某兩個字元串不同，但是它倆經過哈希函數映射之後的字元串相同，我們稱它倆發生了碰撞。
生日攻擊則是說，把人看成映射的輸入，他的生日看成輸出。那麼只要遠少於366次輸入（比如隨便找70個人），就可以有很高的概率發生如下事件：這些人里至少有兩個人生日相同，也就是發生了哈希碰撞。

什麼？生日攻擊不是這個嗎

舉個例子。你現在要大學畢業了。畢業證有一個MD5值驗證你這個畢業證是不是真的。然後有一個人沒有讀大學，但是他也想作弊混個畢業證，但是MD5值不對啊。那怎麼辦呢。
於是你生成了一大堆的真畢業證，只不過有細微區別比如。加一些空格和製表符。
然後MD5就不相同了。
然後對假的畢業證也去這麼做。於是你有了一批真的畢業證MD5和假的MD5.
然後因為MD5的位數是有限的，說不定就撞上了。
這樣你就得到了一個能夠通過驗證但其實是假的的畢業證。
那麼這麼做的原理是什麼呢。原理就是考慮要有多少個人就能讓至少存在一對人同一天生日。

以下是電腦暴力破解生日密碼的攻擊方法和上面幾位大神說的數學只是有些關係，本文主要預防弱密碼。

假如某一個人用生日密碼這個密碼是8位或6位的純數字密碼的話，就會有針對他的365+365=730個這樣的數字密碼（當然有366天）：
19990101
19990012
.......
990101
990102
......發果他當真用純數字密碼，上邊730個密碼必中。

假如某一群人用生日密碼，這一百年的8位或6位純數字密碼就會有（365+365）*100=73000
七萬三的密碼，這個世界用生日密碼的絕對有。
19200101-20200101

如果只是本地單機破解一個文件，用的不管是這100年那一天的密碼，一分鐘內必破。
不管你用的是99-01-01還是1999/01/01隻要是有規律可尋的，對於破解來說只是多等幾秒而已。

把多個密碼放在一個文件里，這個文件叫做密碼字典，上邊的就是生日密碼字典。想要就百度「萬能字典工具」。網上還有比這更方便的方法，因為還有更多的弱密碼比如：lloveyou 123123123 qwertyuiop 名字名字123 123456 12345678 等等太多破解方法。想要就百度「弱密碼字典」，生日密碼也是弱密碼的一種。

當然前些時間某63郵箱或更早的社交網站漏洞泄露明文密碼，導致百萬用戶名密碼泄露，百度「用戶密碼信息泄露」（網上有各種以往各網站泄露的下載的用戶名密碼包，嚇人！），不管你的密碼多麼強壯，多麼長，多麼...額....什麼英文數字混合的一樣被別人下載。我查了不常登陸的某63郵箱，我的郵箱天南海北各種全中國各省地區IP登陸。跑題了。

本文通俗易懂，富含微生物甲乙丙丁，如有一天你站在鐵窗內請不要想起我。

-------------------------

不想記太多太長密碼怎麼辦？怎樣預防？
1，記一個複雜的密碼用於支付寶等金融網站(反正也沒錢)，8位的英文加數字不分大小寫的話，（10+26）^8=2 821 109 907 456個密碼組合。現在最快計算機是10億億次秒，呵呵......分分鐘的事，所以16位的密碼是很重要的事情，已現有的科技暴力破解幾乎沒有任何希望。
2，一般社交網站用一個中等密碼的。
3，一般小網站不怕隱私泄露的用弱密碼。
4，保佑第一條網站不被黑客漏洞攻擊。
總結：你只需要三個密碼輕鬆搞定，但亂下載東西的這種方法也保護不了你。