一次忘記密碼引發(fā)的算法思考

作者：Python編程時(shí)光 2018-12-27 09:09:35

服務(wù)器是不會(huì)明文存儲(chǔ)你的用戶(hù)密碼的，那么在數(shù)據(jù)庫(kù)存儲(chǔ)的到底是什么?它應(yīng)該是被某種算法加密過(guò)的密文，并且無(wú)法進(jìn)行反向破解，保證了被黑客拿到了也能保證數(shù)據(jù)的相對(duì)安全。而這個(gè)算法，就是我們接下來(lái)要介紹對(duì)哈希算法。

前兩天準(zhǔn)備登陸某網(wǎng)站的時(shí)候，在嘗試了幾次常用密碼失敗后，我點(diǎn)擊了“忘記密碼”，嫻熟地填入手機(jī)號(hào)碼，隨即就收到了一條來(lái)自陌生號(hào)碼的短信，里面包含著一個(gè)六個(gè)數(shù)字串，我將這個(gè)數(shù)字串填入網(wǎng)站提供的輸入框，就進(jìn)入了密碼重置流程。

[[253582]]

這里有一點(diǎn)細(xì)節(jié)，值得我們注意，為什么我忘記了密碼，你不直接把原密碼返回給我?而是給我一個(gè)不相關(guān)的口令來(lái)重置密碼?

前段時(shí)間，華住(某大型連鎖酒店)再次發(fā)生脫庫(kù)事件。由于內(nèi)部程序員失誤，將數(shù)據(jù)庫(kù)密碼公開(kāi)于Github上，讓人拿走了數(shù)億用戶(hù)的開(kāi)戶(hù)記錄和他們的登陸信息(包括密碼)。假如這些密碼用明文存儲(chǔ)，那不法分子盜取數(shù)據(jù)庫(kù)后，拿到明文密碼，就可以輕而易舉的拿郵箱和密碼去嘗試登陸你的各種社交網(wǎng)站，甚至各種金融帳戶(hù)。要知道有很多人其實(shí)對(duì)賬戶(hù)安全不夠重視，金融賬戶(hù)和社交賬號(hào)都使用同一個(gè)密碼。在如此數(shù)量級(jí)下(上億)的帳戶(hù)密碼泄露，對(duì)于互聯(lián)網(wǎng)安全將是一場(chǎng)巨大的浩劫。

如此看來(lái)，服務(wù)器是不會(huì)明文存儲(chǔ)你的用戶(hù)密碼的。這也就能解釋?zhuān)瑸槭裁床桓纱嘀苯訉⒃艽a返回給你了。因?yàn)榫瓦B他們也不知道。

那么問(wèn)題來(lái)了，在數(shù)據(jù)庫(kù)存儲(chǔ)的到底是什么?它應(yīng)該是被某種算法加密過(guò)的密文，并且無(wú)法進(jìn)行反向破解，保證了被黑客拿到了也能保證數(shù)據(jù)的相對(duì)安全。而這個(gè)算法，就是我們接下來(lái)要介紹對(duì)哈希算法。

哈希(Hash)算法，由于其不可反向破解的特性被廣泛用于私密信息的保護(hù)和校驗(yàn)。

哈希算法是一個(gè)比較泛的概念，他的具體實(shí)現(xiàn)有許多種，大家所熟知的有 MD5，SHA256等。

現(xiàn)在拿 MD5來(lái)舉例，MD5消息摘要算法(英語(yǔ)：MD5 Message-Digest Algorithm)，一種被廣泛使用的密碼散列函數(shù)，可以產(chǎn)生出一個(gè)128位(16字節(jié))的散列值(hash value)。

但是人類(lèi)實(shí)在看不慣二進(jìn)制，所以128位的二進(jìn)制通常會(huì)表示成32位的十六進(jìn)制(由0-9,a-f組成)，他們是等價(jià)的。

說(shuō)了那么多，這個(gè)散列值到底長(zhǎng)啥樣呢。

在 Python 中

import hashlib    
 
m1 = hashlib.md5()    
m1.update("hello")    
print(m1.hexdigest()) 
# 5d41402abc4b2a76b9719d911017c592

用 shell 就更簡(jiǎn)單了

echo -n hello | md5sum             
# 5d41402abc4b2a76b9719d911017c592  -

有不少人會(huì)將哈希(Hash) 和加密(Encrypt)混淆起來(lái)，其實(shí)它們是不一樣的：

哈希：將目標(biāo)文本轉(zhuǎn)換成具有相同長(zhǎng)度的、不可逆的字符串，也叫消息摘要，是一對(duì)多的映射關(guān)系(即多個(gè)明文可能對(duì)應(yīng)同一個(gè)哈希值)。
加密：將目標(biāo)文本轉(zhuǎn)換成具有不同長(zhǎng)度的、可逆的密文，是一對(duì)一的映射關(guān)系(即一個(gè)密文只能對(duì)應(yīng)一個(gè)明文)

由于哈希算法是一對(duì)多的映射，所以不同的輸入是有可能得到了同一個(gè)哈希值，這時(shí)候就發(fā)生了"哈希碰撞"(collision)。

哈希碰撞雖然發(fā)生概率小，但是一旦發(fā)生，就會(huì)產(chǎn)生嚴(yán)重的安全問(wèn)題：

案例一

很多網(wǎng)絡(luò)服務(wù)會(huì)使用哈希函數(shù)，產(chǎn)生一個(gè) token 用于標(biāo)識(shí)用戶(hù)的身份和權(quán)限。

如果兩個(gè)不同的用戶(hù)，得到了同樣的 token，就發(fā)生了哈希碰撞。服務(wù)器將把這兩個(gè)用戶(hù)視為同一個(gè)人，這意味著，用戶(hù) B 可以讀取和更改用戶(hù) A 的信息，這無(wú)疑帶來(lái)了很大的安全隱患。

案例二

我們都用過(guò)網(wǎng)絡(luò)支付工具，假如我現(xiàn)在從 A 帳戶(hù)轉(zhuǎn)給帳戶(hù) B 1000塊錢(qián)，交易信息在網(wǎng)絡(luò)中進(jìn)行傳輸，有可能被黑客給截持并篡改我們的數(shù)據(jù)，將目標(biāo)帳戶(hù)改成黑客自己的帳戶(hù)。如此一來(lái)，我們的金錢(qián)就被竊取了。

如果使用哈希算法，就可以在客戶(hù)端處，將轉(zhuǎn)賬的信息進(jìn)行處理，處理方法是，將要加密的數(shù)據(jù)加上一個(gè)約定好的字符串一起進(jìn)行哈希，生成一個(gè)信息摘要。

假如在網(wǎng)絡(luò)傳輸過(guò)程中不幸被黑客修改了目標(biāo)帳戶(hù)和轉(zhuǎn)帳金額，等到了支付平臺(tái)的服務(wù)器端，會(huì)將傳輸過(guò)來(lái)的信息和之前約定好的字符串再次進(jìn)行哈希。然后和之前那個(gè)哈希進(jìn)行比對(duì)，由于之前的數(shù)據(jù)已經(jīng)被篡改了，所以驗(yàn)證不通過(guò)，轉(zhuǎn)帳失敗。從而保證了我們的資金安全。

前面講到了許多哈希在實(shí)際生活中的應(yīng)用，可以發(fā)現(xiàn)，哈希被廣泛的應(yīng)用在安全領(lǐng)域。那哈希真的沒(méi)有辦法破解嗎?

當(dāng)然有，這里舉三個(gè)常見(jiàn)的例子。

1. 暴力窮舉法

暴力窮舉法，就是簡(jiǎn)單粗暴的枚舉出所有的原文，并計(jì)算其哈希值，然后將計(jì)算結(jié)果與目標(biāo)哈希值一一比對(duì)。由于原文的可能性有無(wú)數(shù)多種，所以這種方法時(shí)間復(fù)雜度高得離奇，極不可取。需要大量的計(jì)算，因此破解速度非常慢，以14位字母和數(shù)字的組合密碼為例，共有1.24×10^25種可能，即使電腦每秒鐘能進(jìn)行10億次運(yùn)算，也需要4億年才能破解。

就算有一天，真找到一個(gè)和目標(biāo)哈希值相等的原文，這個(gè)原文也不一定是答案，因?yàn)楣_突的存在，多個(gè)原文是有可能有著同一個(gè)哈希值。

2. 字典法

反思暴力枚舉法，它其實(shí)做了太多無(wú)用的計(jì)算。一般人的密碼都會(huì)取一些有特殊意義的字符，比如生日，名字縮寫(xiě)等。有人就會(huì)把這些常用的高頻率的密碼組合，試先計(jì)算并存儲(chǔ)起來(lái)。等到要用的時(shí)候，直接到數(shù)據(jù)庫(kù)里查詢(xún)對(duì)應(yīng)的哈希值就行了。

如果說(shuō)暴力枚舉法，是時(shí)間換空間，那字典法就是空間換時(shí)間。

需要海量的磁盤(pán)空間來(lái)儲(chǔ)存數(shù)據(jù)，仍以14位字母和數(shù)字的組合密碼為例，生成的密碼32位哈希串的對(duì)照表將占用2.64 * 10^14 TB 的存儲(chǔ)空間。如何增加密碼長(zhǎng)度或添加符號(hào)，需要的時(shí)間或磁盤(pán)空間將更加難以想象，顯然這兩種方法是難以讓人滿(mǎn)意的。

（62^14*192）/8/1024/1024/1024/1024=2.64 * 10^14 (GB)

3. 彩虹表法

暴力枚舉和字典法，都只適用于長(zhǎng)度較短，組合簡(jiǎn)單的密碼。

接下來(lái)為大家介紹一種高效的密碼攻擊方法：彩虹表。它可以用于復(fù)雜一點(diǎn)的密碼。

彩虹表實(shí)質(zhì)上還是屬于字典破解的一種，不過(guò)不再是簡(jiǎn)單的明文—密碼的對(duì)應(yīng)，為了節(jié)省字典存儲(chǔ)空間，彩虹表省去了能通過(guò)計(jì)算得出的數(shù)據(jù)，達(dá)到這點(diǎn)的關(guān)鍵在于設(shè)計(jì)出一個(gè)函數(shù)族Rk(k=1、2、3、4……)將hash密文空間映射回明文的字符空間。

彩虹表的存儲(chǔ)空間是字典法的 k 分之一，代價(jià)是運(yùn)算次數(shù)至少是原來(lái)的 k 倍。

彩虹表確實(shí)像它的名字一樣美好，至少黑客眼里是這樣。下表是7位以?xún)?nèi)密碼在不同字符集下構(gòu)造出的彩虹表的情況，彩虹表中哈希鏈的長(zhǎng)度和個(gè)數(shù)隨著字符集的增長(zhǎng)而增長(zhǎng)，彩虹表的大小和生成時(shí)間也隨之成倍增加。7位數(shù)字組合在彩虹表面前簡(jiǎn)直就是秒破，即使最復(fù)雜的7位密碼不到一個(gè)小時(shí)就能破解，如果采用普通的暴力攻擊，破解時(shí)間可能需要三周。