1.寫在前面
網絡安全是一個非常重要的領域,今天和大家一起來學習和密碼相關的話題。
說到密碼大家肯定都不陌生,我們每個人都有一些列的密碼:郵箱密碼、社交網站密碼、各種App密碼等等,密碼就如同每個人網絡領域的一把鑰匙。
對于我們使用者來說,我們盡量避免使用一些爛大街的密碼比如:123qaz、qazwsx等、提高密碼的復雜度、避免使用生日等基礎信息作為密碼、另外要定期更換密碼等來確保個人信息安全。
對于功能服務提供商來說,妥善存儲保管密碼是一個很重要的環節,一旦造成密碼泄漏等事故造成的影響會很大,要嚴肅對待。
然而并不是所有的事情都如我們所期盼那樣,網上用戶敏感信息泄漏的事件比比皆是,國內外都有一些案例,可以自行搜索引擎搞起。
前面鋪墊了一下于是引出本文的主題:
通過本文你將了解到以下內容:
- 密碼交互基本過程
- 明文存儲密碼
- 單向無鹽哈希存儲
- 預計算哈希鏈集合和彩虹表原理
- 哈希+鹽存儲
- 專業密碼加密算法
2.密碼交互過程
密碼一般是用在用戶登陸認證環節的,完整的過程包括:用戶輸入密碼、客戶端加密、網絡傳輸、服務端驗證等。
從嚴格意義上來說每個環節都可能造成密碼的泄漏,過程越多出錯的概率就會越大,其中用戶登錄認證的基本步驟可以歸納為:
- 用戶填寫賬號、密碼以及驗證碼等信息;
- 在之前注冊時填寫的密碼經過加密儲存在數據庫中并做持久化備份,后續登錄做驗證;
- 服務端從數據庫獲取該用戶名下的加密密碼,并且將用戶輸入使用相同加密過程計算結果,二者進行對比;
- 二者相同則用戶被授權登錄,當然這里不考慮手機驗證碼之類的措施;
- 如果二者不同則提示失敗,并且對最大嘗試次數做限制;
本文主要介紹服務端如何安全存儲密碼。
3.密碼的明文存儲
這種明文存儲密碼的方法讓人覺得不可思議,但是實際上真的有這樣做的,就像這樣把密碼明文直接存儲在MySQL,如圖:
這種明文存儲的密碼數據一旦被拖庫,就會造成很大的問題,對于一些私人小站可能會存在這種情況,因此我們日常一定要注意鑒別,以為這些站點的防范意識不夠,后臺漏洞很容易被不法分子利用造成泄漏,當然也有少數知名站點明文存儲的案例,只能說有點無語了。
現在的密碼太多了,很多人不借助一定規律或者工具的前提下會將1-2個常用密碼用在很多站點,這樣就出現了木桶效應:只要一個站點的密碼被泄漏其他站點的密碼也就不安全了。
大錘就是密碼太多他記不住,索性就用一個密碼注冊登陸日常的很多app,有一天他為了玩游戲注冊了一個小破站點,后來密碼泄漏了,就這樣他的其他常用app就面臨著被盜的風險。
對于這種明文存儲的案例,網上有人說這是燈下黑...,讓我聽著有種網劇看多了的感覺,個人覺得主要原因就是意識不夠。
說起這個讓我想起,有次放假回老家,坐客運車途中要加油,正在加油的時候,車上有個人接打電話,沒過一會兒車上很多人不樂意了,開始嚷嚷他別打了,哈哈哈。
4. 單向無鹽哈希存儲
在談論單向無鹽哈希存儲之前,我們先來達到一個共識問題:我們常說的md5/sha其實都是摘要算法,并不是加密算法。
4.1 摘要算法和加密算法
加密算法和摘要算法之間有很大區別,雖然都是把明文進行變形處理,但是加密算法必然對應解密算法,也就是輸入值經過加密算法處理之后可以使用解密算法還原,但是摘要算法一般認為是單向不可逆的,沒辦法輕易還原原始輸入。
如圖展示了加解密可逆過程(注加密密文是我胡亂寫的):
如圖展示了摘要算法不可逆過程(注摘要密文是我胡亂寫的):
簡單了解了摘要算法和加密算法的區別與聯系之后,我們可以知道摘要算法是單向的,我只知道原始輸入A的摘要輸出是B,但是根據B很難推出來A。
就像你用一把鎖和一把鑰匙,但是你把鑰匙扔到了茫茫大海,在不損害箱子的前提下你只能一直暴力嘗試,在試了第20200404把鑰匙的時候發現打開了,恍然大悟原來是這把鑰匙啊!
4.2 哈希沖突和暴力破解
前面舉了用鑰匙開箱子的問題,最終還是被打開了,先別高興,原生鑰匙也不一定就是這把呢,因為有哈希沖突,巧了可以打開,來看個圖先:
圖中我們用m輸入進行摘要運算之后得到了相同的摘要值,也就是打開了箱子,但是真實的輸入卻是k。這里就引出了一個新問題:哈希沖突及其影響。
那么哈希沖突是什么?又為啥會沖突呢?
我們知道摘要算法生成的字符串的長度一般是固定的有128位 256位之類的,摘要算法的神奇之處在于可以把任意長度的數據轉化為固定長度的字符串。
換句話說哈希后的字符串長度有限,那么總的集合就有限,這是個組合的問題很容易想到,但是輸入是無限的呀!
極端一點你寫了個摘要算法長度是4的十六進制字符串,也就只有65536個空間,實際上輸入樣本數量根本不需要65536就幾乎必然出現沖突,因為不出現沖突的要求是非常高的,不信你看看生日悖論問題就知道了。
生日悖論是指在不少于 23 個人中至少有兩人生日相同的概率大于 50%。例如在一個 30 人的小學班級中,存在兩人生日相同的概率為 70%。對于 60 人的大班,這種概率要大于 99%。從引起邏輯矛盾的角度來說,生日悖論并不是一種 “悖論”。但這個數學事實十分反直覺,故稱之為一個悖論。
生日悖論的數學理論被應用于設計密碼學攻擊方法——生日攻擊。
想想也是如此,無限輸入樣本對有限摘要集合,存在沖突幾乎是必然的:
還是暈菜的話,你想想北京13號線的早高峰,車廂10個人不擁擠,瞬間來了200個人,你說擠不擠,沖突不沖突,如圖:
4.3 單向無鹽哈希存儲安全性
前面用了兩個小節闡述了摘要算法和加密算法的區別,以及哈希沖突,觀點都很中立,在了解這些必備知識之后,我們不禁要問:單向無鹽哈希存儲密碼安全嗎?
安全都是相對的,沒有絕對的安全,作為防守方只能讓攻擊方的時間和機器成本都高到無法接受,我們才是比較安全的。
換句話說攻擊方理論上可以破解我的密碼,但是需要300年又或者攻擊方要想在可接受的時間內破解那么就得找個天文數量級的存儲空間,作為防守方你怕啥?
怕啊!萬一有時間和空間都能接受的方案咋整!先賣個關子,后面重點討論這種可怕的Trade-Off方案。
4.3.1 在線加解密實驗
常見的摘要算法md5和sha1的長度分別為128位和160位,這里的位是二進制的,轉化為16進制之后長度分別為32位和40位,從長度上來說sha1相比md5沖突更小一些,那么我們就來試試sha1的破解速度吧!
筆者隨意找了一個在線sha1加解密的網站,這個網站的簡介看著還蠻厲害的,不過都是針對md5的,看來md5已經被如此嫌棄了:
本站專業針對md5等哈希算法進行在線解密,可上傳文件在線批量破解,最多可支持數萬個密碼。單單MD5就擁有64T的密碼數據庫,3萬多億條,本站支持十幾種常見的哈希算法在線解密,查詢時間不到0.1秒。
摩拳擦掌趕緊試驗一把:
加密很快完成,接著解密一下:
啊呀很快就出結果了,之前我跑了幾個解密,現在讓我登錄才展示,我懶得登錄,不過確實是解密成功了,0.01秒所言非虛。
這怎么可以,我再試個強密碼:
速度還是很快,生成了一個長度為40位的16進制小寫字符串,筆者還是很自信的,這么老長破解去吧!啊哈哈....
果然,它跪了,所以增加密碼強度多么重要!
4.3.2 國內外撞庫研究
我國著名的密碼學家山東大學的王小云教授先后對md5和sha1進行了深入研究并且在2004年左右取到了很大的進展,因此目前對于一些高安全要求的場合已經開始使用更高的摘要算法比如:sha224、sha256、sha384、sha512等算法,也就是長度更長了,集合空間更大撞庫可能更小,感受一下這個長度的變化(左右滑動):
明文輸入:1233445TGNVF
sha1密文:fc58f924f193654f6388cac13b6061e99c7dbabc
sha224密文:97cdfc11422a8311e812809711b3159c4530f5f183841f7fe111fd92
sha384密文:2de74b23f770126eb51ec328f591c2290fd3bed8756d0e4dffa32af9296006444c334288bd820b1297d8087977131f0f
sha512密文:96be48daec3779f6d83b991a4f281280884578b2b68a2cf5c481838e48c199c8795f89328a85f208d791465bad28acac440be3a1397eafb0bfefd60d6b9f8a9b
GPU在進行密碼破解領域有絕對的把控力,對于md5和sha1這些算法運算速度非常之快達到每秒x億次,如果再串聯多組GPU進行破譯那么速度將更快。
但是就目前而言sha224/256/385/512算法還是安全的,在2017年谷歌宣布其對sha1撞庫的最新研究,基于此呼吁全球相關機構公司進行算法升級,如圖展示了谷歌使用兩份不同的文件得到相同sha1的例子:
盡管獲得了撞庫進展,但是谷歌付出的成本也是巨大的:攻擊算法分為兩個階段,其中第一個階段如果使用單CPU需要6500年,第二階段使用單GPU需要110年,可謂成本之高。
所以我們如果采用單向無鹽哈希存儲密碼時要避免使用MD5/sha-1這些被大量研究過的短摘要,可以使用sha-256這種更安全的摘要算法,比特幣目前就有使用sha-256作為其相關算法。
4.3.3 算法升級的思考
更換更安全的摘要加密算法確實是有一定效果的,但是算力的進步是我們無法預測的,正如md5和sha-1剛被應用時也是當前的算力無法逾越的,但是隨著并行計算和量子計算的發展,諸如sha-256/512這些現在看來更安全的算法什么時候會被證明又不安全也不得而知。
但是如果我偏偏想把單車開出摩托的感覺咋辦?怎樣用md5這種弱摘要算法能不能實現一個強密碼存儲系統呢?
面對這個樸實的訴求,我們接著聊。
5.彩虹表攻擊
攻擊是為了更好的防守,相克相生。
5.1 暴力破解
暴力破解一般可以分為 計算暴力破解和查表暴力破解,如圖:
在說彩虹表Rainbow Table之前先說一下字典窮舉,這個比較好理解:比如某家網站的密碼構成是長度為12位含字母、數字、特殊符號,這樣我們就可以根據這個特征生成一個所有密碼的全排列集合,然后再進行比如md5摘要計算得到一個哈希值,然后把這個映射關系存儲下來。
使用字典法暴力破解時就如同一個巨大的hash表可以迅速降低時間,但是隨著加密算法的升級和密碼復雜度的提升,字典就會變得非常非常大,理論上無法存儲使用。
人們通過努力找了一種時間和空間折中的方案-彩虹表,它將單獨時間或者單獨空間的不可接受變為可接受,可以說是個非常有用的東西,第一次聽這個名字時詫異于為什么叫彩虹表。
5.2 空間存儲效率問題
在探究彩虹表之前,我們先思考這樣一個問題:如何用最少的存儲空間表達最多的信息量呢?
- C語言中的例子想一下在C語言中我們在傳結構體或者數組時一般只傳遞首地址,其他的元素可以根據這個首地址和偏移量來實現訪問,所以我們用一個地址就可以遍歷所有的變量,存儲效率很高。
- 二叉樹的例子二叉樹的鏈式存儲和順序存儲都可以借助于根節點,依據左右孩子節點的關系從而實現全樹的檢索和遍歷,這樣我們在對外傳輸二叉樹時只需要給出根節點即可,不必全部給定。
- 西游記的例子西游記主角是師徒5人,算了白龍馬的...,我們可以存儲這5個人的信息,但是覺得有點浪費啊,因為我們知道他們5個之間是有關系的,存儲一個就能找到另外四個了。
如圖展示了全量存儲5人信息的場景:
如圖展示了利用師徒之間的關系部分存儲:
簡單說明下:只存儲唐僧,唐僧為入口根據其大徒弟關系得到了孫悟空,從孫悟空依據師弟關系得到另外三人,這個很像數據庫的索引了...
畫外音:有時候很多元素內部是存在聯系的,我們不必全量展示和存儲這些信息,這樣會造成空間上的浪費,如果我們借助于這些內在聯系就可以用少量數據作為入口獲取到所有的數據,這是一種思想吧!
理解這個存儲效率問題對于認識彩虹表有很大的幫助。
試想字典窮舉是把建立所有明文和密文之間的映射,這樣就等價于唐僧師徒5人每個人都存儲,但是如果我們找到了某些明文之間的內在聯系,那么我是否可以只存儲少量明文就可以表達這些具備內在聯系的明文和密文的映射關系呢?
答案是肯定的,但是彩虹表對于明文的內在聯系是建立在數學的基礎上的,我們來繼續探討,彩虹表的H函數和R函數。
5.3 H函數和R函數
各位讀者坐穩扶好打起精神,H函數和R函數是理解彩虹表的關鍵所在。
先解釋一下H函數和R函數分別是什么及其內在聯系:
- H函數
H函數也就是哈希函數,實現明文到密文的單向不可逆轉換; - R函數
R函數理解為Reduction function,這里看到Reduction這個單詞,其實在之前P和NP問題的文章中,我們有接觸到這個單詞,歸約/約化的意思。 - H函數和R函數的關系
一句話概括:H函數的定義域是R函數的值域,H函數的值域是R函數的定義域,但是R并不是H的反函數,因為H函數是不可逆的。
舉個例子:
假如密碼范圍是長度在10個以內的字母數字組合,不區分大小寫,假設輸入明文為abcdfg,則存在如下關系:
// 哈希函數H實現明文向密文的映射
H(abcdfg)=AB8GFTYG
// 歸約函數R實現密文向'明文相同格式字符串'的映射
R(AB8GFTYG)=erfdtk
特別地,R函數將H函數的輸出作為輸入,也就是H的值域作為R的定義域,R函數生成了erfdtk,這個新明文字符串并不是原始輸入的明文,但是格式卻是相同的。
這里可以隱約感受到R函數的重要性,它可以將相同格式的明文生成的密文作為輸入,進而輸出相同格式的新明文,從而產生一個相同格式的明文的集合鏈條,也就是找到了一類有內在聯系的明文。
換句話說,我們可以只存儲一個明文,中間把多個H-R進行組合串聯起來,從而形成一個明文-密文的映射集合,也就是空間減少了但是信息量并沒有減少,這么看來R函數確實很cool。
畫外音:這里提到的R函數生成相同格式的新明文,"相同格式"這個詞語的理解不好拿捏,需要借助數學手段來實現,我們暫且簡單理解為長度和組合方式類似吧!
5.4 預計算哈希鏈和R沖突
在彩虹表出現之前有種預計算哈希鏈集合,就是多組哈希鏈組成的明文-密文集合,這里簡單提一下。
前面提到了一組H-R函數,實際上只有多組H-R函數才有實際意義,比如有2000組H-R組合,那么我們將有2000對明文-密文的映射,但是只需要存儲非常小的一部分即可,這也就是我們要說的哈希鏈,如圖為2組H-R函數組成的哈希鏈:
上圖展示的兩組H-R函數中的R都是相同的,由于哈希沖突的存在我們并不能表示全部獨立的明文,這樣空間存儲率就打折了,看下這個圖:
上面兩條哈希鏈EDEDED和FEDECE經過R函數計算分別得到222和333,222經過H函數得到FEDEFE,再經過R函數也得到了333,這樣兩條哈希鏈就存在重疊部分,也就是R函數出現了沖突。
// 哈希鏈中的R函數沖突
R(FEDECE)=333R(FEDEFE)=333
更重要的是這種沖突是不好被發現的!
為啥這么說呢,因為實際中只存儲哈希鏈中的首尾兩個明文,對于上圖中中間發生了R沖突,但是從重合起點看上面的鏈比下面的鏈位置更靠后,下面的鏈會繼續進行余下的H-R函數最終生成尾部明文是555,然而上面的鏈生成尾部明文是444,在實際存儲中是這樣的:
//哈希鏈1
111->444
//哈希鏈2
454->555
也就是假如你設計的k=2,也就是每組2個H-R函數,兩個哈希鏈可以表示8個明文,但是實際上333和444是存在重復的,從而只有6個有效不同的明文,由于尾部明文的不同,這種重疊是無法被檢測的。
這么看來擁有個分布均勻的R函數是多么重要,但是在幾千組H-R函數中要求完全沒有沖突是非常難的,于是出現了多組R函數的新形式。
畫外音:多組R函數的思路和布隆過濾器的多個hash函數的思想很相似
你可能會問為什么不考慮H函數的沖突情況,因為H函數就是我們需要破解的加密函數,它本身的沖突概率非常低要不然就不用費這么大勁搞彩虹表了。
5.5 彩虹表的基本原理
彩虹表針對哈希鏈集合的R函數沖突帶來的重疊引入了多組不同的R函數系列,從而一個鏈上每個位置的R函數都是不同的,如圖:
需要注意的是多個R函數的引入仍然不可避免沖突問題,但是這種情況下的沖突影響遠小于哈希鏈集合中單個R函數的影響,如圖展示了一種常見的彩虹表R函數沖突(黑色加重部分):
具體來說就是在不同位置出現了沖突:
// 不同輸入 不同R函數產生相同的明文
R1(FEDECE)=333
R2(FEDEFE)=333
但是很快在下一個不同的R函數,R3和R2的作用下就不再重疊了,可覆蓋的明文數量影響不大,也只有333出現了重疊后續是獨立的。
極端情況下相同位置的沖突由于每個位置的R函數相同所以最終尾部明文仍然是相同的,可以進行糾正刪除從而減少冗余數據,如圖:
綜上可知,彩虹表引入一組多個R函數確保了相同位置出現R沖突時的檢測刪除和不同位置出現R沖突的影響最小化,相比哈希鏈集合有一些優勢。
讀到這里我們對于為什么叫做彩虹表隱約有了一點感覺,大概意思就是每一組哈希鏈都有不同的R函數,就像這樣:
5.6 彩虹表的攻擊簡單過程
彩虹表涉及一個復雜的建表過程,并且不同格式長度的密碼和不同的哈希函數都會有不同的彩虹表,網上有一些現成的彩虹表,感興趣的讀者可以根據自己的現狀下載一些彩虹表數據進行驗證,一般來說在實用的彩虹表在100GB以上。
要增加破解的概率就需要完善的彩虹表數據作為支撐,彩虹表的意義就在于把計算暴力破解和空間枚舉結合起來。
來簡單說一下彩虹表的攻擊過程吧:
假設有K組H-R函數組合,彩虹表按照[head_string,tail_string]格式存儲,如圖:
- 假定給定的密文P位于最后一組H-R中,也就是第K個R函數存在R(P)=tail_string,如果tail_string存在于彩虹表中,則從head_string進行推算;
- 如果第K個R函數生成的結果不存在,則向前繼續搜索第K-1個R函數一直計算到最后獲取tail_string,再判斷是否存在;
- 最壞的結果是從第1個R函數推算到最后得到的tail_srting仍然不存在,則說明這條鏈匹配失敗;
到這里,我們基本上對彩虹表的原理和過程有了粗淺的認識,但是彩虹表也不是無敵的,因為它有個強大的對手【哈希+鹽】存儲。
6. 哈希+鹽組合加密存儲
一直在說無鹽單向哈希存儲,但什么是鹽呢?
簡單來說,鹽就是在用戶輸入密碼的基礎上增加的額外部分數據,這部分數據也參與計算哈希存儲密碼。
H(user_input_string+slat)=new_password
和做菜一樣,在存儲密碼中加鹽也是技術活,不由得要問:為什么加鹽就把單向哈希變得這么強大了呢?
其實很簡單,因為鹽不知道是怎么加的,也不知道加的什么!
如圖展示了一個使用彩虹表破解明文之后進行登陸仍然失敗的情況:
暴力破解得到的密碼是bnghuopyi99,輸入之后失敗,因為用戶輸入的明文是nghuopyi,鹽是b99,混合方式是取鹽的第一個字符放在用戶輸入最前面,剩下的追加在后面從而形成了bnghuopyi99。
隨機的鹽和不確定的添加方式,讓彩虹表不那么給力了,換句話說每個用戶可能有單獨的混合方式,破解成本大大增加。
到這里,仿佛哈希+鹽的方式還是不錯的,但是這仍然不是最優的解決方案,我們繼續來看。
7. 專業的密碼加密算法
前面我們學習的一些比如sha256這些算法本質上并不是為了存儲密碼設計的,相反這些摘要算法有其主要用途,那么不禁要問:有沒有專門為密碼設計的加密算法呢?
答案是肯定的。
我們都知道GPU的性能是十分恐怖的,計算速度非常快,試想我們把加密算法變慢,攻擊方也必然會被拖慢,比如加密算法需要200ms完成加密存儲,這個時間對于用戶而言是可以接受的,但是對于攻擊方來說時間成本就非常大了。
聽著有種故意把對手繞暈的感覺,本質上專業的密碼加密算法可以設置強度,來提高暴力破解的時間成本,比較常見的加密算法有以下幾種:
- bcrypt算法
bcrypt 是專門為密碼存儲而設計的算法,基于Blowfish 加密算法變形而來,由 Niels Provos 和 David Mazières 發表于 1999 年的 USENIX。bcrypt 的work factor參數, 可用于調整計算強度,而且 work factor 是包括在輸出的摘要中的,隨著攻擊者計算能力的提高,使用者可以逐步增大 work factor
- PBKDF2算法
PBKDF2(Password-Based Key Derivation Function) PBKDF2 就是將 salted hash 進行多次重復計算,這個次數是可以設定的,從而提高算法的加密時間。
目前這兩個算法都有Python和C/C++版本,感興趣的讀者可以試一下,從專業的角度來說,采用專業的密碼加密算法是最好的解決方案了。
8.寫在最后
本文通過大家熟悉的密碼交互場景作為出發點闡述了明文存儲密碼、單向無鹽哈希存儲、預計算哈希鏈集合、彩虹表、哈希+鹽存儲、專業密碼算法存儲等幾個方面的相關知識。
其中,單向無鹽哈希存儲、彩虹表、哈希+鹽存儲內容相對較多,由于其中涉及了較多的數學背景知識,篇幅以及本人水平所限并未深入展開,從實用的角度來說開發者建議采用專業的密碼加密算法,作為用戶也要增加密碼意識。