密碼學(xué)是理論計(jì)算機(jī)的一個(gè)很大的方向。之前準(zhǔn)備先寫(xiě)密碼學(xué)概論再提在hash函數(shù)破解上做出重大貢獻(xiàn)的王小云教授的工作，不過(guò)前兩天王小云獲得求是杰出科學(xué)家獎(jiǎng)以及100萬(wàn)獎(jiǎng)金，在媒體上又掀起了一輪宣傳狂潮，但是有些報(bào)道極端弱智，錯(cuò)誤百出，所以我趁機(jī)糾正一下，并介紹密碼學(xué)的一個(gè)組成部分——hash函數(shù)，以及王小云在這上面的工作。
王小云的主要工作是關(guān)于hash函數(shù)的破解工作。她在2005一個(gè)密碼學(xué)會(huì)議上宣布破解了SHA-1，震驚了全世界。所以要介紹和理解她的工作，先看一下hash函數(shù)具體是怎么回事。
簡(jiǎn)單的說(shuō)，hash函數(shù)就是把任意長(zhǎng)的輸入字符串變化成固定長(zhǎng)的輸出字符串的一種函數(shù)。通俗得說(shuō)，hash函數(shù)用來(lái)生成信息的摘要。輸出字符串的長(zhǎng)度稱(chēng)為hash函數(shù)的位數(shù)。
目前應(yīng)用最為廣泛的hash函數(shù)是SHA-1和MD5，大多是128位和更長(zhǎng)。
hash函數(shù)在現(xiàn)實(shí)生活中應(yīng)用十分廣泛。很多下載網(wǎng)站都提供下載文件的MD5碼校驗(yàn)，可以用來(lái)判別文件是否完整。另外，比如在WordPress的數(shù)據(jù)庫(kù)，所有密碼都是保存的MD5碼，這樣即使數(shù)據(jù)庫(kù)的管理員也無(wú)法知道用戶(hù)的原始密碼，避免隱私泄露（很多人在不同地方都是用的同一個(gè)密碼）。
如果兩個(gè)輸入串的hash函數(shù)的值一樣，則稱(chēng)這兩個(gè)串是一個(gè)碰撞(Collision)。既然是把任意長(zhǎng)度的字符串變成固定長(zhǎng)度的字符串，所以，必有一個(gè)輸出串對(duì)應(yīng)無(wú)窮多個(gè)輸入串，碰撞是必然存在的。
一個(gè)“優(yōu)良”的hash函數(shù) f 應(yīng)當(dāng)滿(mǎn)足以下三個(gè)條件：
- 任意y，找x，使得f(x)=y，非常困難。
- 給定x1，找x2，使得f(x1)=f(x2)，非常困難。
- 找x1，x2，使得f(x1)=f(x2)，非常困難。
上面的“非常困難”的意思是除了枚舉外不可能有別的更快的方法。比如第3條，根據(jù)生日定理，要想找到這樣的x1，x2，理論上需要大約2^(n/2)的枚舉次數(shù)。
幾乎所有的hash函數(shù)的破解，都是指的破壞上面的第三條性質(zhì)，即找到一個(gè)碰撞（前兩條都能被破壞的hash函數(shù)也太弱了點(diǎn)，早就被人拋棄了）。在密碼學(xué)上還有一個(gè)概念是理論破解，指的是提出一個(gè)算法，使得可以用低于理論值得枚舉次數(shù)找到碰撞。
王小云的主要工作是給出了MD5，SHA-0的碰撞，以及SHA-1的理論破解，她證明了160位SHA-1，只需要大約2^69次計(jì)算就能找出來(lái)，而理論值是2^80次。她的尋找MD5碰撞的方法是極端高效的。傳說(shuō)王小云當(dāng)時(shí)在會(huì)議上把碰撞寫(xiě)出來(lái)，結(jié)果被下面的人驗(yàn)證發(fā)現(xiàn)不對(duì)，原來(lái)她把MD5算法的一個(gè)步驟弄錯(cuò)了。但是她立馬聯(lián)系她的當(dāng)時(shí)留在中國(guó)的學(xué)生，修正算法，并找到一個(gè)新的碰撞。這一個(gè)是對(duì)的。
看到這里，那些認(rèn)為中國(guó)國(guó)安局應(yīng)該將這些結(jié)果封存作為秘密武器甚至幻想用這些成果來(lái)襲擊美國(guó)之徒可以停住你們的YY了。這種形式上的破解，在大多數(shù)情況下沒(méi)有實(shí)際性的作用。更別提MD5早就被美國(guó)人拋棄了。
但是，說(shuō)這種破解一點(diǎn)實(shí)際意義都沒(méi)有，那就侮辱了廣大密碼學(xué)家的智商，密碼學(xué)家不會(huì)無(wú)緣無(wú)故的弄出碰撞這么一個(gè)概念來(lái)。下面簡(jiǎn)單的介紹一下在特定情況下，怎么利用給定的碰撞來(lái)做壞事(翻譯自Attacking Hash Functions)：
Caesar給實(shí)習(xí)生Alice叫寫(xiě)了一封推薦信(letter)。同一天，Alice叫Caesar在推薦信上數(shù)字簽名，并提供了一份推薦信的電子板。Caesar打開(kāi)文件，發(fā)現(xiàn)和原件一模一樣。所以他在文件上簽了名。
幾個(gè)月后，Caesar發(fā)現(xiàn)他的秘密文件被非法察看。這到底是怎么回事呢？
a25f7f0b 29ee0b39 68c86073 8533a4b9
事實(shí)上，Alice要求Caesar簽名的文件letter已經(jīng)被Alice做了手腳，準(zhǔn)確地說(shuō)，Alice還準(zhǔn)備了另外一個(gè)文件order，它們的MD5碼完全一致。而Caesar的數(shù)字簽名還依賴(lài)于MD5算法，所以Alice用order文件替換Letter文件之后，Caesar的數(shù)字簽名依然有效。那封order給Alice提供了察看秘密文件的權(quán)限。
具體的實(shí)現(xiàn)方法可見(jiàn)Hash Functions and the Blind Passenger Attack。我在這里簡(jiǎn)單的解釋一下(只是大致思路，具體實(shí)現(xiàn)方式，需要對(duì)文件結(jié)構(gòu)信息有所了解)：
letter文件的內(nèi)容是：
if(x1==x1) show "letter" else show "order"
order文件的內(nèi)容是：
if(x2==x1) show "letter" else show "order"
其中字符串"letter"和"order"代表兩封信實(shí)際顯示的內(nèi)容。x1，x2是一個(gè)MD5的碰撞。
上面的方法，只供參考和學(xué)術(shù)用途，實(shí)際使用所引起的后果概不負(fù)責(zé)。
參考：
PS：我跟王小云老師的接觸很少，上過(guò)倆次她的討論班而已，亦感覺(jué)到王小云老師的嚴(yán)謹(jǐn)和耐心。在去年一個(gè)Turing獎(jiǎng)獲得者的演講上，王小云提問(wèn)的時(shí)候竟口而出“I ask who”的中式英語(yǔ)，在引起哄笑的同時(shí)，我也極端佩服她的勇氣。也許只有這樣才能做出非常好的工作吧。
PS2: wikipedia在國(guó)內(nèi)可以通過(guò)free_door瀏覽。