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

轉載： http://blog.sina.com.cn/s/blog_77e8d1350100wfc7.html

沒知識真可怕——應用密碼學的笑話之MD5+Salt不安全

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

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

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

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

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

誤區一：MD5被破解啦

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

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

• 無論多長多隨意的信息，最后都轉換成一個固定長度的散列值；
• 對于大量不同的信息，最后出來的散列值呈平均分布；
• 對于特定的一個信息，最后出來的散列值都是相同的。

根據上面的特點，人們通常可以得到下面的結論：

• 不可逆（用一個固定長度的數值，怎么可能表示任意長度的信息呢）；
• 難碰撞（假如散列值有效范圍是從0到9，那么對于已知的一個明文平均需要嘗試11 5次才能找到一個相同的信息，對于任意兩個隨機明文的碰撞概率大概是1/N，即1/10。但是，一般來說散列值有效范圍都在2的64次方以上，即0到18,446,744,073,709,551,616之間，甚至更多，你可以說是一個天文數字）；
• 可代表（既然不可逆，難碰撞，你用散列值是猜不出原來的信息，更不太可能偽造一個信息，其散列值完全相同。于是你出示一個散列值，就可以證明你持有某個有效信息，比如密碼）。

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

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

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

• 簽名認證，證明某段信息沒有被修改；
• 密碼驗證，證明你確實知道某個密碼；
• 其他，比如用在哈希表的散列過程等（這一個場景在某一類稱之為(D)DOS攻擊的場景下有關，但跟密碼安全這種隱私/劫持相關的安全問題沒關系，咱就不討論了）。

簽名認證。

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

密碼驗證

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

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

誤區二：已經有很大的MD5密碼（碰撞）庫，有7.8萬億個密碼呢！

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

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

為什么？那就先要搞清楚，密碼是怎么被破解的。假設明文成為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
• 密文分析：根據C1,C2,...Cn，找到里面的蛛絲馬跡，直接找到能解密的 替代函數D'()，或者直接解出C的部分明文P'；
• 已知明文攻擊：有選擇的給出明文P1,P2,...Pn，讓對方用E(p, k)計算出C1, C2, ...Cn，通過分析找到k'，使得D(C, k')=P；
• 生日攻擊：有選擇的給出明文P1,P2,...Pn，然后直接用這些明文嘗試用戶U1, U2, ...Un，恰巧某些用戶Ux就是用的其中一個明文。這是后面要講的其中一個重點，所謂加鹽就是要解決類似的問題；
• 偷聽：監聽鏈路，等用戶U給出P時即可直接獲得，或者用戶給出的是E(P,k)=C，則下次也可以用同樣的協議給出C，偽裝用戶U。什么QQ盜號木馬，就屬于這種形式；
• 整鍋端：通過后門漏洞等，直接拿到所有數據和程序，然后進行上面的各種分析和攻擊。本次CSDN為開端的，多數是這種；
• 間諜（找到人，用各種賄賂，直接拿到E()、D()和k，甚至所有移植的C和P，或者自己拿著這些東西出去賣錢）。

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

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

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

• 該站點密碼保存的方式不好，很可能是計算C=E(P)，保存C；
• 這些用戶的密碼很可能是相同的。

你只要嘗試一下用qwerty登錄其中一個用戶，發現登錄不了，就可以得出如下結論：

• 該站點不是使用明文保存密碼；
• 該站點使用的是MD5；
• 該用戶的密碼就是123456。

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

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

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

誤區三：MD5加鹽不安全！

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

誤區三點一：加固定鹽。

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

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

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

• 我已經有你的程序了；
• 找到生成密碼散列值的入口函數Fuck()；
• 拿一個明文密碼庫，在一個用戶賬號上面不停地改密碼，也就是用每一個P不斷地Fuck(P)；

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

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

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

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

誤區三點三：用bcrypt吧，可以隨意調節運算需要的時間，比MD5慢千萬倍，每秒鐘只能算出3個密碼……

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

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

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

總結陳詞

• 如果你沒讀過某個領域的至少一本書，最好別隨便發言，否則別人一眼就能看出你是個什么青年；
• MD5+salt對于大部分中小網站來說已經足夠安全了；
• 你實在信不過MD5，那就用點SHA1之流，在密碼驗證這種場景里面，已經足夠了，除非你是開銀行或者開淘寶的；
• 身份驗證只是安全的其中一個環節，想想這些庫都是怎么被偷出來的，想想各種QQ木馬……
• 你在網絡上看到的大部分言論基本上屬于在此領域完全無知的人所想象出來的錯誤言論，比如說搜索“MD5不安全”，除了極少數個別的抄正規網站的報道外，以及個別真正的安全網站里面的信息外，幾乎都是各種笑話；
• 在安全這方面，只要你不是專家，你還是當他不存在比較好。和食品安全一樣，在網絡安全方面，其實大部分網站這方面做得都很糟糕，你要知道了真實的情況，恐怕沒法用網絡上的東西了。

文章核心

• MD5的作用是 簽名驗證和密碼驗證
• MD5的破解指的是 簽名驗證這一塊可以被偽造（但只是特定的）
• 了解沉沒成本，一次性生成密碼庫， 邊際成本，對于每個人都需要付出成本
• 只要MD5+隨機salt，針對一個用戶，基本沒有辦法破解，如果明文是十位的密碼，就是無解
• 對于MD5的密碼破解，只有一種辦法 生日彩虹表攻擊

總結

以上是生活随笔為你收集整理的[转]MD5(1)-安全性与原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。