大家應該聽說過生日悖論吧，聽說是怎麼個回事，當一個房間有23個人的話，就會兩個人相同概率生日相同的，這個概率很恐怖吧。
回顧一下，密碼學的上篇是完整性，完整性的保證是由一段定長的散列，俗稱tag來確定的。又因為tag是定長的，而需要確保完整性的內容種類卻可以認為是無限的。因此總有tag(mi)=tag(mj)，mi != mj，因此我們要引入抗碰撞性這個概念。
抗碰撞性：
抗碰撞性(Collision-Resistant)：找出任意兩個不同的x,x' \in X，使得h(x)=h(x')是困難的（計算不可行）；也稱強抗碰撞性（Strong Collision-Resistant ）。相對的，也有弱抗碰撞性（Weak Collision-Resistant ）這個概念。
弱抗碰撞性：當給定某條消息的散列值時，單向散列函數必須確保要找到和該條消息具有相同散列值的另外一條消息是非常困難的。
強抗碰撞性：是指要找到散列值相同的兩條不同的消息是非常困難的。
而針對碰撞性的攻擊，最主要的要數生日攻擊了：
生日攻擊（Birthday Attack）：
生日悖論（Birthday paradox）：
生日悖論是指，如果一個房間裡有23個或23個以上的人，那麼至少有兩個人的生日相同的概率要大於50%。這就意味著在一個典型的標準小學班級(30人)中，存在兩人生日相同的可能性更高。對於60或者更多的人，這種概率要大於99%。從引起邏輯矛盾的角度來說生日悖論並不是一種悖論，從這個數學事實與一般直覺相牴觸的意義上，它才稱得上是一個悖論。大多數人會認為，23人中有2人生日相同的概率應該遠遠小於50%。
證明：
在考慮所有人的生日都是獨立均勻隨機分佈在365內的話，
因為第二個人不能跟第一個人有相同的生日(概率是364/365),第三個人不能跟前兩個人生日相同(概率為363/365),依此類推。用階乘可以寫成如下形式：
由此可得，當n=23時，概率趨於50%，而人的出生率並不是均勻隨機的，因此23人實際概率應該大於50%。
生日攻擊原理：
由此我們可以將它用在碰撞，得到不同Message有著相同tag。
假設：取樣次數為N，M：M1-Mn，取值在tag：1-B中，並且假設分佈隨機均勻相互獨立。
取樣次數n與B的關係，n=1.2*B^0.5（這是生日悖論中最壞的情況。）
證明：M2不等於M1的概率為(B-1)/B，同理可得M3為(B-2)/B，M4為(B-3)/B...Mn為(B-n+1)/B。
因此，其中有碰撞的概率為：1-（1-1/B）(1-2/B）.....(1-(k-1)/B）>= (1-e)^(-n^2/2B)
因為n=1.2*B^0.5，因此(1-e)^(-n^2/2B)=1-e^-0.72=0.53>50%
結論，因此使用生日攻擊，我們只需2^(n/2)次尋找，就有50%概率能找到相同tag的兩個不同Message。
步驟：
1.隨機在2^(n/2)信息空間中尋找一個M
2.求出相應的tag
3.尋找是否有碰撞，沒有則返回步驟1
破解時間：
理論上而言，若抗碰撞性一直為2^n，而強抗碰撞性因為生日攻擊的原因會降至2^(n/2)時間。
由此可見，SHA-1已經越來越不安全了，數月或者數年後，2^80將不是一個無法逾越的計算時間。另外，因為計算機多為偽隨機，因此現在SHA-1理論上所需的抗碰撞時間僅為2^55時間，但好像並沒有人去證實過。
安全散列函數結構：
因為所需的安全散列長度越來越長，因此我們可以使用有限定義域上的散列函數（俗稱壓縮函數）通過迭代方式拓展為具有無限定義域的散列函數。而最為代表性的就Merkle-Damgard結構
Merkle-Damgard結構：
這個結構的好處是，如果壓縮函數是抗碰撞的，那經過此結構處理後的散列函數也是抗碰撞的。
SM3，HMAC就是基於這種結構，因為Merkle-Damgard結構並不能抵抗擴展攻擊，因此HMAC引入了Key。
閱讀更多 每天一份乾貨 的文章
