摘要：沒錯，年的破解就是證明了在碰撞上面不可靠，也就是可以通過某種方式快速的找到具有相同散列值的另一個信息。好，第二個不安全的誤區(qū)來了上述破解過程對于絕大多數(shù)散列函數(shù)來說，基本上都是一個道理。

轉(zhuǎn)載請注明出處 http://www.paraller.com
原文排版地址 點擊獲取更好閱讀體驗

轉(zhuǎn)載： http://blog.sina.com.cn/s/blog_77e8d1350100wfc7.html

這段時間諸多爆庫的新聞，里面有許多饒有趣味的事情。那些用簡單密碼，或者一個密碼走天下的笑話就不說了，咱說點有內(nèi)涵的。（這篇文章是給IT界的人看的，如果你看不懂，我會準(zhǔn)備一個簡單的“如何辨別密碼安全糟糕的網(wǎng)站”的方法給你，另文描述。）

爆庫之后哀鴻遍野，一大堆人都在里面嗷嗷亂叫，當(dāng)然也包括我在內(nèi)。但是當(dāng)我嗷了一陣子之后，發(fā)現(xiàn)我的G點和大家的居然不一樣，就靜下心來觀察。結(jié)果發(fā)現(xiàn)就連大多數(shù)IT界的人對密碼學(xué)這個玩意兒居然都是一無所知的狀態(tài)，各種人云亦云的笑話此起彼伏。當(dāng)然了，能看懂的也沒幾個。

就比如說MD5不安全這個笑話。

其實也不知道這怎么就跟爆庫的事情扯到一塊去了，但總歸那幾天就有一堆人上來恨恨地說：MD5不安全，現(xiàn)在還有人用來做密碼的散列……好吧，大概對于有些人來說有點深了，這個知識以后我補(bǔ)。咱接著說，“簡直是遜爆了”。當(dāng)然，原文不是如此，但也差不多了。

言下之意，就是他的知識告訴他MD5是不安全的，而用這些的人大概是沒知識的。而事實上是，這么說的人同樣沒有知識。為什么？首先要搞清楚所謂的“不安全”是指哪些問題？

2004年的國際密碼學(xué)會議（Crypto’2004）王小云證明了MD5可以被碰撞，至此，MD5不再安全。沒錯，確實不安全了，但是具體是什么意思呢？大概多數(shù)人根本搞不清楚，也就不知道這個不安全是在哪一個場景底下的了。

要說明這個問題，首先要搞懂MD5是一個什么概念。所謂的MD5實際上是一個散列函數(shù)，具體說特點如下：

無論多長多隨意的信息，最后都轉(zhuǎn)換成一個固定長度的散列值；

對于大量不同的信息，最后出來的散列值呈平均分布；

對于特定的一個信息，最后出來的散列值都是相同的。

根據(jù)上面的特點，人們通常可以得到下面的結(jié)論：

不可逆（用一個固定長度的數(shù)值，怎么可能表示任意長度的信息呢）；

難碰撞（假如散列值有效范圍是從0到9，那么對于已知的一個明文平均需要嘗試11 5次才能找到一個相同的信息，對于任意兩個隨機(jī)明文的碰撞概率大概是1/N，即1/10。但是，一般來說散列值有效范圍都在2的64次方以上，即0到18,446,744,073,709,551,616之間，甚至更多，你可以說是一個天文數(shù)字）；

可代表（既然不可逆，難碰撞，你用散列值是猜不出原來的信息，更不太可能偽造一個信息，其散列值完全相同。于是你出示一個散列值，就可以證明你持有某個有效信息，比如密碼）。

好，到這里你大概能發(fā)現(xiàn)，上面結(jié)論中的難碰撞貌似不對。沒錯，2004年的破解就是證明了MD5在碰撞上面不可靠，也就是可以通過某種方式快速的找到具有相同散列值的另一個信息。比方說：

已知原來的信息是aaaaaaaaaa，散列值是10；
通過某方法，能迅速的找到一個信息aaaXaaaXaa，散列值也是10。

那么這會造成什么影響呢？這就需要先說明一下，散列函數(shù)都可以用來做什么：

簽名認(rèn)證，證明某段信息沒有被修改；

密碼驗證，證明你確實知道某個密碼；

其他，比如用在哈希表的散列過程等（這一個場景在某一類稱之為(D)DOS攻擊的場景下有關(guān)，但跟密碼安全這種隱私/劫持相關(guān)的安全問題沒關(guān)系，咱就不討論了）。

簽名認(rèn)證。

所謂簽名認(rèn)證就是給出一個信息A，然后運(yùn)算H(A)=S，同時將A和S記錄起來。當(dāng)需要校驗信息A有沒有被篡改的時候，只要計算H(A)=S"，看S"是否等于S，就知道了。實際上過程比這個復(fù)雜，需要運(yùn)用非對稱加密才能保證安全。但總歸可以看出來，如果我知道A和S，就能快速推算出一個A"出來，使得H(A")=S，那么這個簽名認(rèn)證過程就失效了，或者說就可以偽裝沒有篡改了。

密碼驗證

就是給定一個密碼A，經(jīng)過散列運(yùn)算H(A)=S，此后，每一次用戶登錄的時候輸入A"，計算H(A")=S"，看看S"是否就是S。如果相等，那就說明用戶知道密碼A，否則就是不知道。在這種應(yīng)用里面，如果我知道正確的密碼A，我還需要費(fèi)半天功夫搞出個A"，使得H(A")=S嗎？完全沒必要。

換句話說，2004年那個MD5碰撞問題，對于密碼驗證來說，根本就沒多大干系。那些拿著這個來說MD5在密碼應(yīng)用上不安全的，壓根就沒搞懂MD5的碰撞不安全是怎么回事。下次有人再這么說的時候，你大可以嘲笑一下對方，哪怕你不知道我上面在說什么，你只要質(zhì)問一下“碰撞是什么意思，請不惜賜教”，多半就啞巴了。

另一個拿來說事的，就是MD5密碼庫如何如何大，比如包含了7.8萬億個密碼。可是……你曉得英文大小寫+數(shù)字+2標(biāo)點共計64種字符，長度是10個字符，總共會有多少個不同的密碼嗎？答案是1,152,921,504,606,846,976個，也就是1,152,921.5萬億個。那個7.8萬億個密碼的密碼庫，只占有這里面的百萬分之6.7。

可為什么大家的密碼還老是泄露呢？那是因為：
人的記性很差，所以總會選用比較好記的密碼，也就是弱密碼；
人的記性很差，所以總會選擇極有限的幾個密碼用在無窮多的網(wǎng)站上；
沒讀過書的人總是那么多，于是總用很差勁的方式來對待系統(tǒng)的安全部分，尤其是密碼部分。
先說弱密碼，因為你總傾向于記生日、人名、單詞，于是你的密碼通常會是：
4位純數(shù)字，總計1萬個不同的密碼；
6位純數(shù)字，總計100萬個不同的密碼；
8位以內(nèi)的小寫字母，而且還是某種拼音或者單詞，總計估計不超過1000萬個不同的密碼；
即便是8位小寫字母加數(shù)字，也就是時2.8萬億個不同組合。
所以，一個7.8萬億個密碼的密碼庫，足以覆蓋大部分用戶的弱密碼了。可是，問題沒那么簡單，如果密碼保存和驗證的過程正確，即便有一個7.8萬萬億的密碼庫，黑客也不會搞出你的密碼來——不是不能，而是沒有興趣。

為什么？那就先要搞清楚，密碼是怎么被破解的。假設(shè)明文成為P，密鑰為k，加密過程為E(P, k)，得到的密文是C，而解密過程為D(C, k)=P。那么破解的手段大致有如下幾種：

暴力窮舉：最笨最慢的方法，讓P"=0...X，找到E(P", k)=C；

算法分析：研究E()，找到其中的弱點，然后P"=0...Y，找到E(P", k)=C，Y

密文分析：根據(jù)C1,C2,...Cn，找到里面的蛛絲馬跡，直接找到能解密的 替代函數(shù)D"()，或者直接解出C的部分明文P"；

已知明文攻擊：有選擇的給出明文P1,P2,...Pn，讓對方用E(p, k)計算出C1, C2, ...Cn，通過分析找到k"，使得D(C, k")=P；

生日攻擊：有選擇的給出明文P1,P2,...Pn，然后直接用這些明文嘗試用戶U1, U2, ...Un，恰巧某些用戶Ux就是用的其中一個明文。這是后面要講的其中一個重點，所謂加鹽就是要解決類似的問題；

偷聽：監(jiān)聽鏈路，等用戶U給出P時即可直接獲得，或者用戶給出的是E(P,k)=C，則下次也可以用同樣的協(xié)議給出C，偽裝用戶U。什么QQ盜號木馬，就屬于這種形式；

整鍋端：通過后門漏洞等，直接拿到所有數(shù)據(jù)和程序，然后進(jìn)行上面的各種分析和攻擊。本次CSDN為開端的，多數(shù)是這種；

間諜（找到人，用各種賄賂，直接拿到E()、D()和k，甚至所有移植的C和P，或者自己拿著這些東西出去賣錢）。

上面的攻擊難度和耗費(fèi)時間和成本基本上是遞減的，其中整鍋端的這種攻擊，可以使得攻擊者可以選擇更簡單快速的攻擊方式，這取決于密碼保管方采用的什么保管策略和協(xié)議。如果做得好，那么能做的頂多就是已知明文攻擊，或者針對個別用戶做生日攻擊。如果做得不好，比如說像這次爆發(fā)的結(jié)果看，就直接拿到明文密碼了。

很顯然，如果用暴力破解，那么結(jié)果就是對每個用戶嘗試超過1,152,921萬億個不同的密碼，這是極其費(fèi)時而不現(xiàn)實的。所以，大多數(shù)情況下會選擇生日攻擊這種形式，因為大多數(shù)人會選擇那些比較好記的密碼，而這些密碼占總體密碼只是一個極有限的一部分。這就是為什么說7.6萬億個密碼的庫，就可以攪得大多數(shù)網(wǎng)站天翻地覆。那么這種攻擊具體是如何實施的呢？我來舉一個例子：

比如說大家可能很喜歡使用123456，那么經(jīng)過MD5散列之后就可以得到一個散列值，比如說是qwerty。于是乎當(dāng)我們拿到一個網(wǎng)站的數(shù)據(jù)庫，發(fā)現(xiàn)里面有為數(shù)不少的用戶，其密碼列保存的是qwerty。這說明幾個問題：

該站點密碼保存的方式不好，很可能是計算C=E(P)，保存C；

這些用戶的密碼很可能是相同的。

你只要嘗試一下用qwerty登錄其中一個用戶，發(fā)現(xiàn)登錄不了，就可以得出如下結(jié)論：

該站點不是使用明文保存密碼；

該站點使用的是MD5；

該用戶的密碼就是123456。

剩下來要做的事情，就是用那個7.6萬億的密碼庫，逐一比對每個用戶的密碼列了。

好，第二個MD5不安全的誤區(qū)來了：上述破解過程對于絕大多數(shù)散列函數(shù)來說，基本上都是一個道理。比如說SHA1，用同樣的密碼樣本，也可以制作出一個7.6萬億的密碼庫，然后接下來的事情就和MD5一樣了。那么當(dāng)大家用這個方法都不安全的時候，何來一個說法說MD5就不安全呢？

總結(jié)：如果有人跟你說7.6萬億個密碼的密碼庫，你大可以通過“你知道什么是生日攻擊或者碰撞攻擊嗎”來嘲笑他，哪怕上面那堆東西你看不懂一個字。

還有人會說MD5+salt（就是俗稱的加鹽）不安全，理由是MD5運(yùn)算很快云云。這樣說的人，肯定不知道MD5+salt要避免的問題是什么，或者說MD5+salt為什么就安全了，甚至大概連MD5+salt的salt是個什么東西，應(yīng)該怎么個加法都不知道。

要搞明白這些個問題，首先要了解兩個最基本的知識：

密碼學(xué)的理論安全，是建立在就算你知道了所有其他的信息包括E()、D()
的具體算法，整個加解密的協(xié)議，以及保存密文的方法，乃至所有程序源代碼、數(shù)據(jù)庫，你只要不知道密鑰k是什么，對于待破解的密文C是不能得到明文P的，甚至用任意其它明文P"計算出相應(yīng)的密文C"，你也得不到待破解密文C所對應(yīng)的明文P是什么；

密碼學(xué)的應(yīng)用安全，是建立在破解所要付出的成本遠(yuǎn)超出能得到的利益上的。

對于保存用戶密碼所用的散列函數(shù)來說，是沒有k這回事的。就算有那也是保存在服務(wù)端，一鍋端的時候就會拿到。所以要保證理論的安全，就必須要求算法本身不能通過密文C能得到明文P，這個散列算法本身就可以做到。另外一個要保證的事情，那就是通過各種可以公開讓大家知道的保存密碼方法，和驗證協(xié)議，做到不遭受包括生日攻擊在內(nèi)的各種攻擊。然而很不幸的是，這種保證實際上是做不到的，或者說無法在面對這種攻擊的時候，讓針對單個用戶的破解達(dá)到近似暴力破解所需時間的程度。關(guān)于這個問題舉一個例子：

據(jù)說現(xiàn)在隨便一臺好點的機(jī)器，每秒鐘可以計算700萬個密碼的MD5值。也就是說7.6萬億的密碼庫，需要運(yùn)算大概1百萬秒，也就是11天半。如果你被FBI，克格勃，或者國家安全局盯上的話，他們肯定會用性能強(qiáng)大萬倍以上的機(jī)器來對付你。也就是說，這個時間會縮短到大概2分鐘。

于是，實際上密碼保存的著眼點是應(yīng)用安全。還是上面的例子，比如說，如果黑客A花5000買了個機(jī)器，而這臺機(jī)器大概能用2年。如果他用11天半破解了你的賬號，那么成本大概就等于5000元/2年*11天半=79元。但如果拿到你的賬號密碼之后，里面能獲取的利益也就5毛，這個黑客A就虧了。虧本生意是不會有人去做的，就算做了，他的損失也比你大。所以應(yīng)用安全的重點就是提高破解的門檻，手段包括：

增加算法所需要的時間（比如那個宣稱散列一次至少0.3秒的bcrypt）；

前一種方法也不是不行，但是這種方法并不從根本上解決生日攻擊的問題?；蛘哒f，產(chǎn)生一個密碼庫的時間從1臺普通機(jī)器用11天半，增加到用一個超級計算機(jī)集群用1年，但是只要有了這個庫之后，對已有的密碼散列值進(jìn)行生日攻擊只要10秒鐘，那還是很劃算的。因為產(chǎn)生密碼庫的成本是一種沉沒成本，和用戶量有多少完全沒有關(guān)系。比如說，用這個密碼庫去對比一個瑞士銀行賬戶的密碼，只要有幾個沙特王子的密碼在這個密碼庫里面，你就可以買下幾百個超級計算機(jī)集群了。

增加破解所有人的總體時間

而后者，則是將生成密碼庫的沉沒成本變成邊際成本，也就是說：如果需要為每一個用戶生成一遍密碼庫，那整個破解的成本就會隨著用戶量的提高而急劇增加。比如生成一個用戶的密碼庫需要花11天半的時間，一共有1萬個用戶，全部破解就需要315年的時間。就算生成密碼庫的時間壓縮到10分鐘，全部破解也需要70天的時間。那怎么做到呢？方法就是加鹽，也就是那個誤區(qū)“md5+salt不安全”。

加鹽怎么加呢？方法如下：
針對每一個用戶U，生成一個隨機(jī)值Salt，并且在以后永遠(yuǎn)保持不變，任意兩個用戶的鹽不能相同。然后當(dāng)用戶設(shè)置密碼的時候，根據(jù)明文密碼P，計算MD5(P+Salt)=C。而登錄的時候用戶也給出明文密碼P"，服務(wù)器拿到之后同樣計算MD5(P"+Salt)=C"，看C"是否等于C。我們來看一下這樣是否就達(dá)到目的了：

假設(shè)有兩個用戶A和B，密碼都是123456，但鹽分別是aaaa和bbbb，于是MD5(123456+aaaa)=X8jv8o，而MD5(123456+bbbb)=8go489，而不再是標(biāo)準(zhǔn)的qwerty。這時候：
黑客拿到的只是：用戶A的鹽是aaaa，散列值是X8jv8o。用戶B的鹽是bbbb，散列值是8go489；
首先，標(biāo)準(zhǔn)的密碼庫失效了；
其次，每個用戶的散列值都不一樣，你無法根據(jù)相同散列值數(shù)量的多少得出哪些是弱密碼；
再次，鹽是aaaa，散列值是X8jv8o，是無法推導(dǎo)出密碼是123456，還是abcdef，還是別的什么東西，不像在簡單MD5的情況下，看到qwerty就知道那是123456；

于是，黑客剩下兩個選項：

針對每個用戶進(jìn)行暴力破解；

針對每一個用戶的鹽，比如aaaa，分別根據(jù)弱密碼明文庫，計算MD5(弱密碼明文+aaaa)=鹽aaaa對應(yīng)的散列值，然后再用這個密碼庫去對用戶A進(jìn)行生日攻擊。對用戶B還得重新根據(jù)新的鹽bbbb生成密碼庫……
看，這就是加鹽的作用。

總結(jié)：如果你要嘲笑這類人，你可以質(zhì)疑他 “你知道沉沒成本和邊際成本嗎”，或者“加鹽之后如何進(jìn)行生日攻擊或者碰撞攻擊”，即便上面寫的東西你都沒看懂。

嗯，其實在這個誤區(qū)下面還有一些有意思的分支誤區(qū)：

誤區(qū)三點一：加固定鹽。

說實話，什么叫做加固定鹽我一開始沒看懂，直到后來看到說給每個用戶加隨機(jī)鹽我才恍然大悟。那意思是說，給每一個用戶都用一樣的鹽，比如用戶A使用鹽aaaa，用戶B也使用aaaa，……用戶ZZZ還是使用aaaa。你如果看懂了上面我說的內(nèi)容，大概你就知道鹽是用來防止一個密碼碰撞庫可以用在所有用戶身上。這種“固定鹽”打一開始就違反了上述原則，根本就不是鹽。所以，在應(yīng)用密碼學(xué)的書里面壓根就沒有“固定鹽”這樣的說法。

之所以產(chǎn)生固定鹽的想法，大概源于不讓已有的簡單MD5碰撞庫能用在你身上，并且鹽是不會泄露的。鹽這種不是只有用戶自己才知道的東西，不是密鑰k，如果你的安全性就指望在沒人知道你的“固定鹽”是多少，那就違反了密碼學(xué)的準(zhǔn)則了，都不需要用腦袋想就知道這是不安全的。而且，人家連你的密碼庫都能拿到，鹽還不是輕而易舉的事情么？

還有說不知道我的算法是什么，老大，人家能攻破你的系統(tǒng)登進(jìn)來，把你的整套數(shù)據(jù)庫拿走，還差程序不成？告訴你，剩下的問題只是你的庫里面有多少價值而已。如果是一個不要說是銀行庫、淘寶庫，就算是一個社交庫，里面的價值（比如釣釣魚）都足夠請一個“安全專家”來審閱你的代碼了。不要把這個安全專家想象的太高級，隨便找個有點想象力的技術(shù)人員就可以了，比如這樣的思路：

我已經(jīng)有你的程序了；

找到生成密碼散列值的入口函數(shù)Fuck()；

拿一個明文密碼庫，在一個用戶賬號上面不停地改密碼，也就是用每一個P不斷地Fuck(P)；

好了，密碼碰撞庫就出來了。

固定鹽這種想法還不是最搞笑的，還有下面這一個：

誤區(qū)三點二：MD5、SHA1、……這些公開的算法都是不安全的，就算加了鹽也不安全，真正安全的只能是自己寫一個算法，然后再加鹽。

我都懶得說什么，這種說法除了暴露你的愚昧無知之外，還能有什么意義呢？這說明你不了解：
什么是MD5；
加鹽是干什么的；
密碼學(xué)的準(zhǔn)則之一是不能依賴于你的算法不被公開；
什么樣的算法是安全的，怎么樣算是安全。
有沒有高雅一點的誤區(qū)？也有：

誤區(qū)三點三：用bcrypt吧，可以隨意調(diào)節(jié)運(yùn)算需要的時間，比MD5慢千萬倍，每秒鐘只能算出3個密碼……

好吧，這也許管用，因為成本確實挺高的。但是：
單純的使用這種算法不加鹽，只不過增加了沉沒成本，邊際成本是不會變的，生日攻擊還是存在的；
1秒鐘算3個密碼，雖然破解時的成本大大增加了，但是你自己的系統(tǒng)的運(yùn)行成本也會大大的增加。比如說：原來用MD5時一臺服務(wù)器解決用戶登錄問題負(fù)載剛好100%，你用這個該死的bcrypt算法就需要該死的上萬臺服務(wù)器才能解決問題。
其實這回歸到一個簡單的問題上：你的庫里面價值幾何？如果你是銀行，興許值得。但對于大部分的站點來說，這么搞只會過度增加自己的成本，MD5加鹽就已經(jīng)可以讓大部分黑客完全喪失興趣了。

還有一些類似的說法，也是一樣的。比如說：MD5加鹽多算幾遍。其實這麼做無非就是增加了一些計算成本而已，和bcrypt思路無差異。（當(dāng)然，也有人以為這樣多算幾遍因為算法不標(biāo)準(zhǔn)，人家不知道，于是就安全了。請參見誤區(qū)三點一。）

其實，只要你加的是真正意義上的鹽——每個用戶都不相同、隨機(jī)的，那其余的手段基本上不是花拳繡腿，就是在表演如何自己砸自己的腳。當(dāng)然了，不排除有些真的很天才的想法，但大部分人的說法都不在這個范疇內(nèi)。

如果你沒讀過某個領(lǐng)域的至少一本書，最好別隨便發(fā)言，否則別人一眼就能看出你是個什么青年；

MD5+salt對于大部分中小網(wǎng)站來說已經(jīng)足夠安全了；

你實在信不過MD5，那就用點SHA1之流，在密碼驗證這種場景里面，已經(jīng)足夠了，除非你是開銀行或者開淘寶的；

身份驗證只是安全的其中一個環(huán)節(jié)，想想這些庫都是怎么被偷出來的，想想各種QQ木馬……

你在網(wǎng)絡(luò)上看到的大部分言論基本上屬于在此領(lǐng)域完全無知的人所想象出來的錯誤言論，比如說搜索“MD5不安全”，除了極少數(shù)個別的抄正規(guī)網(wǎng)站的報道外，以及個別真正的安全網(wǎng)站里面的信息外，幾乎都是各種笑話；

在安全這方面，只要你不是專家，你還是當(dāng)他不存在比較好。和食品安全一樣，在網(wǎng)絡(luò)安全方面，其實大部分網(wǎng)站這方面做得都很糟糕，你要知道了真實的情況，恐怕沒法用網(wǎng)絡(luò)上的東西了。

MD5的作用是 簽名驗證和密碼驗證

MD5的破解指的是 簽名驗證這一塊可以被偽造（但只是特定的）

了解沉沒成本，一次性生成密碼庫， 邊際成本，對于每個人都需要付出成本

只要MD5+隨機(jī)salt，針對一個用戶，基本沒有辦法破解，如果明文是十位的密碼，就是無解

對于MD5的密碼破解，只有一種辦法 生日彩虹表攻擊