1.寫(xiě)在前面

網(wǎng)絡(luò)安全是一個(gè)非常重要的領(lǐng)域，今天和大家一起來(lái)學(xué)習(xí)和密碼相關(guān)的話(huà)題。

說(shuō)到密碼大家肯定都不陌生，我們每個(gè)人都有一些列的密碼：郵箱密碼、社交網(wǎng)站密碼、各種app密碼等等，密碼就如同每個(gè)人網(wǎng)絡(luò)領(lǐng)域的一把鑰匙。

對(duì)于我們使用者來(lái)說(shuō)，我們盡量避免使用一些爛大街的密碼比如：123qaz、qazwsx等、提高密碼的復(fù)雜度、避免使用生日等基礎(chǔ)信息作為密碼、另外要定期更換密碼等來(lái)確保個(gè)人信息安全。

對(duì)于功能服務(wù)提供商來(lái)說(shuō)，妥善存儲(chǔ)保管密碼是一個(gè)很重要的環(huán)節(jié)，一旦造成密碼泄漏等事故造成的影響會(huì)很大，要嚴(yán)肅對(duì)待。

然而并不是所有的事情都如我們所期盼那樣，網(wǎng)上用戶(hù)敏感信息泄漏的事件比比皆是，國(guó)內(nèi)外都有一些案例，可以自行搜索引擎搞起。

前面鋪墊了一下于是引出本文的主題：

通過(guò)本文你將了解到以下內(nèi)容：

• 密碼交互基本過(guò)程
• 明文存儲(chǔ)密碼
• 單向無(wú)鹽哈希存儲(chǔ)
• 預(yù)計(jì)算哈希鏈集合和彩虹表原理
• 哈希+鹽存儲(chǔ)
• 專(zhuān)業(yè)密碼加密算法

2.密碼交互過(guò)程

密碼一般是用在用戶(hù)登陸認(rèn)證環(huán)節(jié)的，完整的過(guò)程包括：用戶(hù)輸入密碼、客戶(hù)端加密、網(wǎng)絡(luò)傳輸、服務(wù)端驗(yàn)證等。

從嚴(yán)格意義上來(lái)說(shuō)每個(gè)環(huán)節(jié)都可能造成密碼的泄漏，過(guò)程越多出錯(cuò)的概率就會(huì)越大，其中用戶(hù)登錄認(rèn)證的基本步驟可以歸納為：

• 用戶(hù)填寫(xiě)賬號(hào)、密碼以及驗(yàn)證碼等信息；
• 在之前注冊(cè)時(shí)填寫(xiě)的密碼經(jīng)過(guò)加密儲(chǔ)存在數(shù)據(jù)庫(kù)中并做持久化備份，后續(xù)登錄做驗(yàn)證；
• 服務(wù)端從數(shù)據(jù)庫(kù)獲取該用戶(hù)名下的加密密碼，并且將用戶(hù)輸入使用相同加密過(guò)程計(jì)算結(jié)果，二者進(jìn)行對(duì)比；
• 二者相同則用戶(hù)被授權(quán)登錄，當(dāng)然這里不考慮手機(jī)驗(yàn)證碼之類(lèi)的措施；
• 如果二者不同則提示失敗，并且對(duì)最大嘗試次數(shù)做限制；

本文主要介紹服務(wù)端如何安全存儲(chǔ)密碼。

3.密碼的明文存儲(chǔ)

這種明文存儲(chǔ)密碼的方法讓人覺(jué)得不可思議，但是實(shí)際上真的有這樣做的，就像這樣把密碼明文直接存儲(chǔ)在MySQL，如圖：

這種明文存儲(chǔ)的密碼數(shù)據(jù)一旦被拖庫(kù)，就會(huì)造成很大的問(wèn)題，對(duì)于一些私人小站可能會(huì)存在這種情況，因此我們?nèi)粘Ｒ欢ㄒ⒁忤b別，以為這些站點(diǎn)的防范意識(shí)不夠，后臺(tái)漏洞很容易被不法分子利用造成泄漏，當(dāng)然也有少數(shù)知名站點(diǎn)明文存儲(chǔ)的案例，只能說(shuō)有點(diǎn)無(wú)語(yǔ)了。

現(xiàn)在的密碼太多了，很多人不借助一定規(guī)律或者工具的前提下會(huì)將1-2個(gè)常用密碼用在很多站點(diǎn)，這樣就出現(xiàn)了木桶效應(yīng)：只要一個(gè)站點(diǎn)的密碼被泄漏其他站點(diǎn)的密碼也就不安全了。

大錘就是密碼太多他記不住，索性就用一個(gè)密碼注冊(cè)登陸日常的很多app，有一天他為了玩游戲注冊(cè)了一個(gè)小破站點(diǎn)，后來(lái)密碼泄漏了，就這樣他的其他常用app就面臨著被盜的風(fēng)險(xiǎn)。

對(duì)于這種明文存儲(chǔ)的案例，網(wǎng)上有人說(shuō)這是燈下黑...，讓我聽(tīng)著有種網(wǎng)劇看多了的感覺(jué)，個(gè)人覺(jué)得主要原因就是意識(shí)不夠。

說(shuō)起這個(gè)讓我想起，有次放假回老家，坐客運(yùn)車(chē)途中要加油，正在加油的時(shí)候，車(chē)上有個(gè)人接打電話(huà)，沒(méi)過(guò)一會(huì)兒車(chē)上很多人不樂(lè)意了，開(kāi)始嚷嚷他別打了，哈哈哈。

4. 單向無(wú)鹽哈希存儲(chǔ)

在談?wù)搯蜗驘o(wú)鹽哈希存儲(chǔ)之前，我們先來(lái)達(dá)到一個(gè)共識(shí)問(wèn)題：我們常說(shuō)的md5/sha其實(shí)都是摘要算法，并不是加密算法。

4.1 摘要算法和加密算法

加密算法和摘要算法之間有很大區(qū)別，雖然都是把明文進(jìn)行變形處理，但是加密算法必然對(duì)應(yīng)解密算法，也就是輸入值經(jīng)過(guò)加密算法處理之后可以使用解密算法還原，但是摘要算法一般認(rèn)為是單向不可逆的，沒(méi)辦法輕易還原原始輸入。

如圖展示了加解密可逆過(guò)程(注加密密文是我胡亂寫(xiě)的)：

如圖展示了摘要算法不可逆過(guò)程(注摘要密文是我胡亂寫(xiě)的)：

簡(jiǎn)單了解了摘要算法和加密算法的區(qū)別與聯(lián)系之后，我們可以知道摘要算法是單向的，我只知道原始輸入A的摘要輸出是B，但是根據(jù)B很難推出來(lái)A。

就像你用一把鎖和一把鑰匙，但是你把鑰匙扔到了茫茫大海，在不損害箱子的前提下你只能一直暴力嘗試，在試了第20200404把鑰匙的時(shí)候發(fā)現(xiàn)打開(kāi)了，恍然大悟原來(lái)是這把鑰匙?。?/span>

4.2 哈希沖突和暴力破解

前面舉了用鑰匙開(kāi)箱子的問(wèn)題，最終還是被打開(kāi)了，先別高興，原生鑰匙也不一定就是這把呢，因?yàn)橛泄_突，巧了可以打開(kāi)，來(lái)看個(gè)圖先：

圖中我們用m輸入進(jìn)行摘要運(yùn)算之后得到了相同的摘要值，也就是打開(kāi)了箱子，但是真實(shí)的輸入?yún)s是k。這里就引出了一個(gè)新問(wèn)題：哈希沖突及其影響。

那么哈希沖突是什么？又為啥會(huì)沖突呢？

我們知道摘要算法生成的字符串的長(zhǎng)度一般是固定的有128位 256位之類(lèi)的，摘要算法的神奇之處在于可以把任意長(zhǎng)度的數(shù)據(jù)轉(zhuǎn)化為固定長(zhǎng)度的字符串。

換句話(huà)說(shuō)哈希后的字符串長(zhǎng)度有限，那么總的集合就有限，這是個(gè)組合的問(wèn)題很容易想到，但是輸入是無(wú)限的呀！

極端一點(diǎn)你寫(xiě)了個(gè)摘要算法長(zhǎng)度是4的十六進(jìn)制字符串，也就只有65536個(gè)空間，實(shí)際上輸入樣本數(shù)量根本不需要65536就幾乎必然出現(xiàn)沖突，因?yàn)椴怀霈F(xiàn)沖突的要求是非常高的，不信你看看生日悖論問(wèn)題就知道了。

生日悖論是指在不少于 23 個(gè)人中至少有兩人生日相同的概率大于 50%。例如在一個(gè) 30 人的小學(xué)班級(jí)中，存在兩人生日相同的概率為 70%。對(duì)于 60 人的大班，這種概率要大于 99%。從引起邏輯矛盾的角度來(lái)說(shuō)，生日悖論并不是一種 “悖論”。但這個(gè)數(shù)學(xué)事實(shí)十分反直覺(jué)，故稱(chēng)之為一個(gè)悖論。

生日悖論的數(shù)學(xué)理論被應(yīng)用于設(shè)計(jì)密碼學(xué)攻擊方法——生日攻擊。

想想也是如此，無(wú)限輸入樣本對(duì)有限摘要集合，存在沖突幾乎是必然的：

還是暈菜的話(huà)，你想想北京13號(hào)線(xiàn)的早高峰，車(chē)廂10個(gè)人不擁擠，瞬間來(lái)了200個(gè)人，你說(shuō)擠不擠，沖突不沖突，如圖：

4.3 單向無(wú)鹽哈希存儲(chǔ)安全性

前面用了兩個(gè)小節(jié)闡述了摘要算法和加密算法的區(qū)別，以及哈希沖突，觀(guān)點(diǎn)都很中立，在了解這些必備知識(shí)之后，我們不禁要問(wèn)：單向無(wú)鹽哈希存儲(chǔ)密碼安全嗎？

安全都是相對(duì)的，沒(méi)有絕對(duì)的安全，作為防守方只能讓攻擊方的時(shí)間和機(jī)器成本都高到無(wú)法接受，我們才是比較安全的。

換句話(huà)說(shuō)攻擊方理論上可以破解我的密碼，但是需要300年又或者攻擊方要想在可接受的時(shí)間內(nèi)破解那么就得找個(gè)天文數(shù)量級(jí)的存儲(chǔ)空間，作為防守方你怕啥？

怕?。∪f(wàn)一有時(shí)間和空間都能接受的方案咋整！先賣(mài)個(gè)關(guān)子，后面重點(diǎn)討論這種可怕的Trade-Off方案。

4.3.1 在線(xiàn)加解密實(shí)驗(yàn)

常見(jiàn)的摘要算法md5和sha1的長(zhǎng)度分別為128位和160位，這里的位是二進(jìn)制的，轉(zhuǎn)化為16進(jìn)制之后長(zhǎng)度分別為32位和40位，從長(zhǎng)度上來(lái)說(shuō)sha1相比md5沖突更小一些，那么我們就來(lái)試試sha1的破解速度吧！

筆者隨意找了一個(gè)在線(xiàn)sha1加解密的網(wǎng)站，這個(gè)網(wǎng)站的簡(jiǎn)介看著還蠻厲害的，不過(guò)都是針對(duì)md5的，看來(lái)md5已經(jīng)被如此嫌棄了：

本站專(zhuān)業(yè)針對(duì)md5等哈希算法進(jìn)行在線(xiàn)解密，可上傳文件在線(xiàn)批量破解，最多可支持?jǐn)?shù)萬(wàn)個(gè)密碼。單單MD5就擁有64T的密碼數(shù)據(jù)庫(kù)，3萬(wàn)多億條，本站支持十幾種常見(jiàn)的哈希算法在線(xiàn)解密，查詢(xún)時(shí)間不到0.1秒。

摩拳擦掌趕緊試驗(yàn)一把：

加密很快完成，接著解密一下：

啊呀很快就出結(jié)果了，之前我跑了幾個(gè)解密，現(xiàn)在讓我登錄才展示，我懶得登錄，不過(guò)確實(shí)是解密成功了，0.01秒所言非虛。

這怎么可以，我再試個(gè)強(qiáng)密碼：

速度還是很快，生成了一個(gè)長(zhǎng)度為40位的16進(jìn)制小寫(xiě)字符串，筆者還是很自信的，這么老長(zhǎng)破解去吧！啊哈哈....

果然，它跪了，所以增加密碼強(qiáng)度多么重要！

4.3.2 國(guó)內(nèi)外撞庫(kù)研究

我國(guó)著名的密碼學(xué)家山東大學(xué)的王小云教授先后對(duì)md5和sha1進(jìn)行了深入研究并且在2004年左右取到了很大的進(jìn)展，因此目前對(duì)于一些高安全要求的場(chǎng)合已經(jīng)開(kāi)始使用更高的摘要算法比如：sha224、sha256、sha384、sha512等算法，也就是長(zhǎng)度更長(zhǎng)了，集合空間更大撞庫(kù)可能更小，感受一下這個(gè)長(zhǎng)度的變化(左右滑動(dòng))：

明文輸入：1233445TGNVF
sha1密文：fc58f924f193654f6388cac13b6061e99c7dbabc
sha224密文：97cdfc11422a8311e812809711b3159c4530f5f183841f7fe111fd92
sha384密文：2de74b23f770126eb51ec328f591c2290fd3bed8756d0e4dffa32af9296006444c334288bd820b1297d8087977131f0f
sha512密文：96be48daec3779f6d83b991a4f281280884578b2b68a2cf5c481838e48c199c8795f89328a85f208d791465bad28acac440be3a1397eafb0bfefd60d6b9f8a9b

GPU在進(jìn)行密碼破解領(lǐng)域有絕對(duì)的把控力，對(duì)于md5和sha1這些算法運(yùn)算速度非常之快達(dá)到每秒x億次，如果再串聯(lián)多組GPU進(jìn)行破譯那么速度將更快。

但是就目前而言sha224/256/385/512算法還是安全的，在2017年谷歌宣布其對(duì)sha1撞庫(kù)的最新研究，基于此呼吁全球相關(guān)機(jī)構(gòu)公司進(jìn)行算法升級(jí)，如圖展示了谷歌使用兩份不同的文件得到相同sha1的例子：

盡管獲得了撞庫(kù)進(jìn)展，但是谷歌付出的成本也是巨大的：攻擊算法分為兩個(gè)階段，其中第一個(gè)階段如果使用單CPU需要6500年，第二階段使用單GPU需要110年，可謂成本之高。

所以我們?nèi)绻捎脝蜗驘o(wú)鹽哈希存儲(chǔ)密碼時(shí)要避免使用MD5/sha-1這些被大量研究過(guò)的短摘要，可以使用sha-256這種更安全的摘要算法，比特幣目前就有使用sha-256作為其相關(guān)算法。

4.3.3 算法升級(jí)的思考

更換更安全的摘要加密算法確實(shí)是有一定效果的，但是算力的進(jìn)步是我們無(wú)法預(yù)測(cè)的，正如md5和sha-1剛被應(yīng)用時(shí)也是當(dāng)前的算力無(wú)法逾越的，但是隨著并行計(jì)算和量子計(jì)算的發(fā)展，諸如sha-256/512這些現(xiàn)在看來(lái)更安全的算法什么時(shí)候會(huì)被證明又不安全也不得而知。

但是如果我偏偏想把單車(chē)開(kāi)出摩托的感覺(jué)咋辦？怎樣用md5這種弱摘要算法能不能實(shí)現(xiàn)一個(gè)強(qiáng)密碼存儲(chǔ)系統(tǒng)呢？

面對(duì)這個(gè)樸實(shí)的訴求，我們接著聊。

5.彩虹表攻擊

攻擊是為了更好的防守，相克相生。

5.1 暴力破解

暴力破解一般可以分為 計(jì)算暴力破解和查表暴力破解，如圖：

在說(shuō)彩虹表Rainbow Table之前先說(shuō)一下字典窮舉，這個(gè)比較好理解：比如某家網(wǎng)站的密碼構(gòu)成是長(zhǎng)度為12位含字母、數(shù)字、特殊符號(hào)，這樣我們就可以根據(jù)這個(gè)特征生成一個(gè)所有密碼的全排列集合，然后再進(jìn)行比如md5摘要計(jì)算得到一個(gè)哈希值，然后把這個(gè)映射關(guān)系存儲(chǔ)下來(lái)。 

使用字典法暴力破解時(shí)就如同一個(gè)巨大的hash表可以迅速降低時(shí)間，但是隨著加密算法的升級(jí)和密碼復(fù)雜度的提升，字典就會(huì)變得非常非常大，理論上無(wú)法存儲(chǔ)使用。 

人們通過(guò)努力找了一種時(shí)間和空間折中的方案-彩虹表，它將單獨(dú)時(shí)間或者單獨(dú)空間的不可接受變?yōu)榭山邮埽梢哉f(shuō)是個(gè)非常有用的東西，第一次聽(tīng)這個(gè)名字時(shí)詫異于為什么叫彩虹表。

5.2 空間存儲(chǔ)效率問(wèn)題

在探究彩虹表之前，我們先思考這樣一個(gè)問(wèn)題：如何用最少的存儲(chǔ)空間表達(dá)最多的信息量呢？

• C語(yǔ)言中的例子
  想一下在C語(yǔ)言中我們?cè)趥鹘Y(jié)構(gòu)體或者數(shù)組時(shí)一般只傳遞首地址，其他的元素可以根據(jù)這個(gè)首地址和偏移量來(lái)實(shí)現(xiàn)訪(fǎng)問(wèn)，所以我們用一個(gè)地址就可以遍歷所有的變量，存儲(chǔ)效率很高。

• 二叉樹(shù)的例子
  二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)和順序存儲(chǔ)都可以借助于根節(jié)點(diǎn)，依據(jù)左右孩子節(jié)點(diǎn)的關(guān)系從而實(shí)現(xiàn)全樹(shù)的檢索和遍歷，這樣我們?cè)趯?duì)外傳輸二叉樹(shù)時(shí)只需要給出根節(jié)點(diǎn)即可，不必全部給定。
  

• 西游記的例子
  西游記主角是師徒5人，算了白龍馬的...,我們可以存儲(chǔ)這5個(gè)人的信息，但是覺(jué)得有點(diǎn)浪費(fèi)啊，因?yàn)槲覀冎浪麄?個(gè)之間是有關(guān)系的，存儲(chǔ)一個(gè)就能找到另外四個(gè)了。

如圖展示了全量存儲(chǔ)5人信息的場(chǎng)景：

如圖展示了利用師徒之間的關(guān)系部分存儲(chǔ)：

簡(jiǎn)單說(shuō)明下：只存儲(chǔ)唐僧，唐僧為入口根據(jù)其大徒弟關(guān)系得到了孫悟空，從孫悟空依據(jù)師弟關(guān)系得到另外三人，這個(gè)很像數(shù)據(jù)庫(kù)的索引了...

畫(huà)外音：有時(shí)候很多元素內(nèi)部是存在聯(lián)系的，我們不必全量展示和存儲(chǔ)這些信息，這樣會(huì)造成空間上的浪費(fèi)，如果我們借助于這些內(nèi)在聯(lián)系就可以用少量數(shù)據(jù)作為入口獲取到所有的數(shù)據(jù)，這是一種思想吧！

理解這個(gè)存儲(chǔ)效率問(wèn)題對(duì)于認(rèn)識(shí)彩虹表有很大的幫助。

試想字典窮舉是把建立所有明文和密文之間的映射，這樣就等價(jià)于唐僧師徒5人每個(gè)人都存儲(chǔ)，但是如果我們找到了某些明文之間的內(nèi)在聯(lián)系，那么我是否可以只存儲(chǔ)少量明文就可以表達(dá)這些具備內(nèi)在聯(lián)系的明文和密文的映射關(guān)系呢？

答案是肯定的，但是彩虹表對(duì)于明文的內(nèi)在聯(lián)系是建立在數(shù)學(xué)的基礎(chǔ)上的，我們來(lái)繼續(xù)探討，彩虹表的H函數(shù)和R函數(shù)。

5.3 H函數(shù)和R函數(shù)

各位讀者坐穩(wěn)扶好打起精神，H函數(shù)和R函數(shù)是理解彩虹表的關(guān)鍵所在。

先解釋一下H函數(shù)和R函數(shù)分別是什么及其內(nèi)在聯(lián)系：

• H函數(shù)
  H函數(shù)也就是哈希函數(shù)，實(shí)現(xiàn)明文到密文的單向不可逆轉(zhuǎn)換；
• R函數(shù)
  R函數(shù)理解為Reduction function，這里看到Reduction這個(gè)單詞，其實(shí)在之前P和NP問(wèn)題的文章中，我們有接觸到這個(gè)單詞，歸約/約化的意思。
• H函數(shù)和R函數(shù)的關(guān)系
  一句話(huà)概括：H函數(shù)的定義域是R函數(shù)的值域，H函數(shù)的值域是R函數(shù)的定義域，但是R并不是H的反函數(shù)，因?yàn)镠函數(shù)是不可逆的。

舉個(gè)例子：

假如密碼范圍是長(zhǎng)度在10個(gè)以?xún)?nèi)的字母數(shù)字組合，不區(qū)分大小寫(xiě)，假設(shè)輸入明文為abcdfg,則存在如下關(guān)系：

// 哈希函數(shù)H實(shí)現(xiàn)明文向密文的映射H(abcdfg)=AB8GFTYG// 歸約函數(shù)R實(shí)現(xiàn)密文向'明文相同格式字符串'的映射R(AB8GFTYG)=erfdtk

特別地，R函數(shù)將H函數(shù)的輸出作為輸入，也就是H的值域作為R的定義域，R函數(shù)生成了erfdtk，這個(gè)新明文字符串并不是原始輸入的明文，但是格式卻是相同的。

這里可以隱約感受到R函數(shù)的重要性，它可以將相同格式的明文生成的密文作為輸入，進(jìn)而輸出相同格式的新明文，從而產(chǎn)生一個(gè)相同格式的明文的集合鏈條，也就是找到了一類(lèi)有內(nèi)在聯(lián)系的明文。

換句話(huà)說(shuō)，我們可以只存儲(chǔ)一個(gè)明文，中間把多個(gè)H-R進(jìn)行組合串聯(lián)起來(lái)，從而形成一個(gè)明文-密文的映射集合，也就是空間減少了但是信息量并沒(méi)有減少，這么看來(lái)R函數(shù)確實(shí)很cool。

畫(huà)外音：這里提到的R函數(shù)生成相同格式的新明文，"相同格式"這個(gè)詞語(yǔ)的理解不好拿捏，需要借助數(shù)學(xué)手段來(lái)實(shí)現(xiàn)，我們暫且簡(jiǎn)單理解為長(zhǎng)度和組合方式類(lèi)似吧！

5.4 預(yù)計(jì)算哈希鏈和R沖突

在彩虹表出現(xiàn)之前有種預(yù)計(jì)算哈希鏈集合，就是多組哈希鏈組成的明文-密文集合，這里簡(jiǎn)單提一下。

前面提到了一組H-R函數(shù)，實(shí)際上只有多組H-R函數(shù)才有實(shí)際意義，比如有2000組H-R組合，那么我們將有2000對(duì)明文-密文的映射，但是只需要存儲(chǔ)非常小的一部分即可，這也就是我們要說(shuō)的哈希鏈，如圖為2組H-R函數(shù)組成的哈希鏈：

上圖展示的兩組H-R函數(shù)中的R都是相同的，由于哈希沖突的存在我們并不能表示全部獨(dú)立的明文，這樣空間存儲(chǔ)率就打折了，看下這個(gè)圖：

上面兩條哈希鏈EDEDED和FEDECE經(jīng)過(guò)R函數(shù)計(jì)算分別得到222和333，222經(jīng)過(guò)H函數(shù)得到FEDEFE，再經(jīng)過(guò)R函數(shù)也得到了333，這樣兩條哈希鏈就存在重疊部分，也就是R函數(shù)出現(xiàn)了沖突。

// 哈希鏈中的R函數(shù)沖突R(FEDECE)=333R(FEDEFE)=333

更重要的是這種沖突是不好被發(fā)現(xiàn)的！

為啥這么說(shuō)呢，因?yàn)閷?shí)際中只存儲(chǔ)哈希鏈中的首尾兩個(gè)明文，對(duì)于上圖中中間發(fā)生了R沖突，但是從重合起點(diǎn)看上面的鏈比下面的鏈位置更靠后，下面的鏈會(huì)繼續(xù)進(jìn)行余下的H-R函數(shù)最終生成尾部明文是555，然而上面的鏈生成尾部明文是444，在實(shí)際存儲(chǔ)中是這樣的：

//哈希鏈1111->444//哈希鏈2454->555

也就是假如你設(shè)計(jì)的k=2,也就是每組2個(gè)H-R函數(shù)，兩個(gè)哈希鏈可以表示8個(gè)明文，但是實(shí)際上333和444是存在重復(fù)的，從而只有6個(gè)有效不同的明文，由于尾部明文的不同，這種重疊是無(wú)法被檢測(cè)的。

這么看來(lái)?yè)碛袀€(gè)分布均勻的R函數(shù)是多么重要，但是在幾千組H-R函數(shù)中要求完全沒(méi)有沖突是非常難的，于是出現(xiàn)了多組R函數(shù)的新形式。

畫(huà)外音：多組R函數(shù)的思路和布隆過(guò)濾器的多個(gè)hash函數(shù)的思想很相似

你可能會(huì)問(wèn)為什么不考慮H函數(shù)的沖突情況，因?yàn)镠函數(shù)就是我們需要破解的加密函數(shù)，它本身的沖突概率非常低要不然就不用費(fèi)這么大勁搞彩虹表了。

5.5 彩虹表的基本原理

彩虹表針對(duì)哈希鏈集合的R函數(shù)沖突帶來(lái)的重疊引入了多組不同的R函數(shù)系列，從而一個(gè)鏈上每個(gè)位置的R函數(shù)都是不同的，如圖：

需要注意的是多個(gè)R函數(shù)的引入仍然不可避免沖突問(wèn)題，但是這種情況下的沖突影響遠(yuǎn)小于哈希鏈集合中單個(gè)R函數(shù)的影響，如圖展示了一種常見(jiàn)的彩虹表R函數(shù)沖突(黑色加重部分)：

具體來(lái)說(shuō)就是在不同位置出現(xiàn)了沖突：

// 不同s輸入 不同R函數(shù)產(chǎn)生x相同的明文R1(FEDECE)=333R2(FEDEFE)=333

但是很快在下一個(gè)不同的R函數(shù)，R3和R2的作用下就不再重疊了，可覆蓋的明文數(shù)量影響不大，也只有333出現(xiàn)了重疊后續(xù)是獨(dú)立的。

極端情況下相同位置的沖突由于每個(gè)位置的R函數(shù)相同所以最終尾部明文仍然是相同的，可以進(jìn)行糾正刪除從而減少冗余數(shù)據(jù)，如圖：

綜上可知，彩虹表引入一組多個(gè)R函數(shù)確保了相同位置出現(xiàn)R沖突時(shí)的檢測(cè)刪除和不同位置出現(xiàn)R沖突的影響最小化，相比哈希鏈集合有一些優(yōu)勢(shì)。

讀到這里我們對(duì)于為什么叫做彩虹表隱約有了一點(diǎn)感覺(jué)，大概意思就是每一組哈希鏈都有不同的R函數(shù)，就像這樣：

5.6 彩虹表的攻擊簡(jiǎn)單過(guò)程

彩虹表涉及一個(gè)復(fù)雜的建表過(guò)程，并且不同格式長(zhǎng)度的密碼和不同的哈希函數(shù)都會(huì)有不同的彩虹表，網(wǎng)上有一些現(xiàn)成的彩虹表，感興趣的讀者可以根據(jù)自己的現(xiàn)狀下載一些彩虹表數(shù)據(jù)進(jìn)行驗(yàn)證，一般來(lái)說(shuō)在實(shí)用的彩虹表在100GB以上。

要增加破解的概率就需要完善的彩虹表數(shù)據(jù)作為支撐，彩虹表的意義就在于把計(jì)算暴力破解和空間枚舉結(jié)合起來(lái)。

來(lái)簡(jiǎn)單說(shuō)一下彩虹表的攻擊過(guò)程吧：

假設(shè)有K組H-R函數(shù)組合，彩虹表按照[head_string,tail_string]格式存儲(chǔ)，如圖：

• 假定給定的密文P位于最后一組H-R中，也就是第K個(gè)R函數(shù)存在R(P)=tail_string,如果tail_string存在于彩虹表中，則從head_string進(jìn)行推算；
• 如果第K個(gè)R函數(shù)生成的結(jié)果不存在，則向前繼續(xù)搜索第K-1個(gè)R函數(shù)一直計(jì)算到最后獲取tail_string，再判斷是否存在；
• 最壞的結(jié)果是從第1個(gè)R函數(shù)推算到最后得到的tail_srting仍然不存在，則說(shuō)明這條鏈匹配失?。?

到這里，我們基本上對(duì)彩虹表的原理和過(guò)程有了粗淺的認(rèn)識(shí)，但是彩虹表也不是無(wú)敵的，因?yàn)樗袀€(gè)強(qiáng)大的對(duì)手【哈希+鹽】存儲(chǔ)。

6. 哈希+鹽組合加密存儲(chǔ)

一直在說(shuō)無(wú)鹽單向哈希存儲(chǔ)，但什么是鹽呢？

簡(jiǎn)單來(lái)說(shuō)，鹽就是在用戶(hù)輸入密碼的基礎(chǔ)上增加的額外部分?jǐn)?shù)據(jù)，這部分?jǐn)?shù)據(jù)也參與計(jì)算哈希存儲(chǔ)密碼。

H(user_input_string+slat)=new_password

和做菜一樣，在存儲(chǔ)密碼中加鹽也是技術(shù)活，不由得要問(wèn)：為什么加鹽就把單向哈希變得這么強(qiáng)大了呢？

其實(shí)很簡(jiǎn)單，因?yàn)辂}不知道是怎么加的，也不知道加的什么！

如圖展示了一個(gè)使用彩虹表破解明文之后進(jìn)行登陸仍然失敗的情況：

暴力破解得到的密碼是bnghuopyi99，輸入之后失敗，因?yàn)橛脩?hù)輸入的明文是nghuopyi，鹽是b99,混合方式是取鹽的第一個(gè)字符放在用戶(hù)輸入最前面，剩下的追加在后面從而形成了bnghuopyi99。

隨機(jī)的鹽和不確定的添加方式，讓彩虹表不那么給力了，換句話(huà)說(shuō)每個(gè)用戶(hù)可能有單獨(dú)的混合方式，破解成本大大增加。

到這里，仿佛哈希+鹽的方式還是不錯(cuò)的，但是這仍然不是最優(yōu)的解決方案，我們繼續(xù)來(lái)看。

7. 專(zhuān)業(yè)的密碼加密算法

前面我們學(xué)習(xí)的一些比如sha256這些算法本質(zhì)上并不是為了存儲(chǔ)密碼設(shè)計(jì)的，相反這些摘要算法有其主要用途，那么不禁要問(wèn)：有沒(méi)有專(zhuān)門(mén)為密碼設(shè)計(jì)的加密算法呢？

答案是肯定的。

我們都知道GPU的性能是十分恐怖的，計(jì)算速度非常快，試想我們把加密算法變慢，攻擊方也必然會(huì)被拖慢，比如加密算法需要200ms完成加密存儲(chǔ)，這個(gè)時(shí)間對(duì)于用戶(hù)而言是可以接受的，但是對(duì)于攻擊方來(lái)說(shuō)時(shí)間成本就非常大了。

聽(tīng)著有種故意把對(duì)手繞暈的感覺(jué)，本質(zhì)上專(zhuān)業(yè)的密碼加密算法可以設(shè)置強(qiáng)度，來(lái)提高暴力破解的時(shí)間成本，比較常見(jiàn)的加密算法有以下幾種：

• bcrypt算法

bcrypt 是專(zhuān)門(mén)為密碼存儲(chǔ)而設(shè)計(jì)的算法，基于Blowfish 加密算法變形而來(lái)，由 Niels Provos 和 David Mazières 發(fā)表于 1999 年的 USENIX。bcrypt 的work factor參數(shù), 可用于調(diào)整計(jì)算強(qiáng)度，而且 work factor 是包括在輸出的摘要中的，隨著攻擊者計(jì)算能力的提高，使用者可以逐步增大 work factor

• PBKDF2算法

PBKDF2(Password-Based Key Derivation Function) PBKDF2 就是將 salted hash 進(jìn)行多次重復(fù)計(jì)算，這個(gè)次數(shù)是可以設(shè)定的，從而提高算法的加密時(shí)間。

目前這兩個(gè)算法都有Python和C/C++版本，感興趣的讀者可以試一下，從專(zhuān)業(yè)的角度來(lái)說(shuō)，采用專(zhuān)業(yè)的密碼加密算法是最好的解決方案了。

8.寫(xiě)在最后

本文通過(guò)大家熟悉的密碼交互場(chǎng)景作為出發(fā)點(diǎn)闡述了明文存儲(chǔ)密碼、單向無(wú)鹽哈希存儲(chǔ)、預(yù)計(jì)算哈希鏈集合、彩虹表、哈希+鹽存儲(chǔ)、專(zhuān)業(yè)密碼算法存儲(chǔ)等幾個(gè)方面的相關(guān)知識(shí)。

其中，單向無(wú)鹽哈希存儲(chǔ)、彩虹表、哈希+鹽存儲(chǔ)內(nèi)容相對(duì)較多，由于其中涉及了較多的數(shù)學(xué)背景知識(shí)，篇幅以及本人水平所限并未深入展開(kāi)，從實(shí)用的角度來(lái)說(shuō)開(kāi)發(fā)者建議采用專(zhuān)業(yè)的密碼加密算法，作為用戶(hù)也要增加密碼意識(shí)。

若評(píng)論不自由，則贊美無(wú)意義。

如有問(wèn)題，請(qǐng)私信與我聯(lián)系。

最后，依然感謝各位讀者的耐心閱讀，完結(jié)。

9.巨人的肩膀

• https://zhuanlan.zhihu.com/p/29167729
• https://www.pressc.cn/853.html
• https://www.cnblogs.com/milantgh/p/3612318.html
• http://www.91ri.org/7593.html
• https://www.jianshu.com/p/732d9d960411