本文前半部分科普 PBKDF 函數(shù)的意義，后半部分探討在前端計(jì)算的可行性。

前言

幾乎每隔一段時(shí)間，就會(huì)聽(tīng)到“XX 網(wǎng)站被拖庫(kù)”的新聞。之后又會(huì)出現(xiàn)一些報(bào)道，分析該網(wǎng)站使用最多的密碼是什么、有多少等等。

眾所周知，密碼在數(shù)據(jù)庫(kù)中通常是以 Hash 值存儲(chǔ)的，并且還加了鹽。攻擊者即使知道具體的 Hash 算法，也只能暴力破解。照理說(shuō)這是極其費(fèi)勁的，然而現(xiàn)實(shí)中卻總有大量密碼被破解，是什么導(dǎo)致安全性如此脆弱？

究其原因，莫過(guò)于這兩點(diǎn)：口令密碼、算法成本。

[[217148]]

口令密碼

密碼可以記在很多地方。最常見(jiàn)的，就是記在自己腦袋里。當(dāng)然還可以記在屬于你的物品上，例如小本子、卡片等等，反正不用腦子記，不如設(shè)置的很長(zhǎng)很亂，例如：

QQ:     n5Py 2r8W qGyg 4tU6 
GMail:  3TkS mVwQ hUrs wtmA 
... 

這種無(wú)意義的長(zhǎng)串作密碼，是很安全的。即使它們的 Hash 值以及算法泄露，攻擊者想得到明文，只能暴力窮舉所有組合：

泄露的值是 BF656DEC5DD8BA0B，泄露的算法是 f(x)。開(kāi)始窮舉... 
 
嘗試組合                f(x)               結(jié)果 
aaaa aaaa aaaa aaaa    02F49B3EA5592B14   × 
aaaa aaaa aaaa aaab    BD4E960D990DA3F3   × 
...           
n5Py 2r8W qGyg 4tU5    4CEA28A904326A26   × 
n5Py 2r8W qGyg 4tU6    BF656DEC5DD8BA0B   √ 

就算只有字母和數(shù)字，也要近 10^28 次才猜到。這是個(gè)天文數(shù)字，幾乎不可行。所以，這種類型的密碼還是很安全的。

然而現(xiàn)實(shí)中這么做的并不多。物品需要隨身攜帶，非常不便，要是弄丟或者被偷，就更麻煩了。除非把它們都背下來(lái)，但這不又回到“記在腦袋里”這種方式了！

腦袋確實(shí)很安全，但容量也很有限。像上面那種毫無(wú)規(guī)律的字串，背一句都難，更別說(shuō)多個(gè)了。所以，大家多少都會(huì)選些有意義、有規(guī)律的字串作為密碼，例如 iloveyou2016、qwert12345，或是手機(jī)號(hào)、生日等組合。這種不用死記硬背的字串，就是口令（pass word）。

口令雖然方便，但缺陷也很明顯：因?yàn)樗怯幸?guī)律的，所以猜起來(lái)就容易多了。攻擊者只需測(cè)試常用單詞組合，沒(méi)準(zhǔn)就能猜到了：

泄露的值是 2B649D47C4546A3E，泄露的算法是 f(x)。開(kāi)始跑字典... 
 
嘗試組合         f(x)               結(jié)果 
... 
qwert yuiop     52708233CFFD6BFD   × 
qwert asdfg     CD07933880702B97   × 
qwert zxcvb     343F78782D73AB3A   × 
qwert 12345     2B649D47C4546A3E   √ 

這個(gè)過(guò)程，就是所謂的“跑字典”。一本好的字典，可以極大的提升猜中幾率。

算法成本

在字典相同的情況下，速度就顯得尤為重要了。每秒可以猜多少次？這得看具體的算法。

例如 MD5 函數(shù)，每次調(diào)用大約需要 1 微秒，這意味著每秒可以猜 100 萬(wàn)次！（而且這還只是單線程的速度，用上多并發(fā)更是恐怖）

由此可見(jiàn)，算法越快，對(duì)破解者就越有利。假如每次調(diào)用需要 10 毫秒，那么每秒只能猜 100 次，這樣就足足慢了一萬(wàn)倍！

然而不幸的是，常用的 Hash 函數(shù)都是很快的。因?yàn)樗鼈兩鷣?lái)就有多種用途，并非為口令處理而設(shè)計(jì)。例如計(jì)算一個(gè)大文件的校驗(yàn)值，速度顯然很重要。

所以，用 MD5、SHA256 之類的“快函數(shù)”處理口令，是不合理的。包括一些簡(jiǎn)單的變種，例如 MD5(SHA256(x))，仍然屬于“快函數(shù)”。一旦 Hash 值和算法泄露，很容易被“跑字典”破解。

現(xiàn)實(shí)中，由于不少網(wǎng)站使用了“快函數(shù)”來(lái)處理口令，因此數(shù)據(jù)庫(kù)泄露后，大量口令被還原也就在所難免了。

增加成本

雖然 Hash 函數(shù)單次執(zhí)行很快，但我們可以反復(fù)執(zhí)行大量次數(shù)，這樣總體耗時(shí)就變長(zhǎng)了。例如：

function slow_sha256(x) 
    for i = 0 to 100000 
        x = sha256(x) 
    end 
    return x 
end 

在密碼學(xué)中，這種方式叫做 拉伸。現(xiàn)實(shí)中有不少方案，例如 PBKDF2 —— 它沒(méi)有重頭設(shè)計(jì)一種新算法，而是對(duì)現(xiàn)有的函數(shù)進(jìn)行封裝，從而更適合用于口令處理：

function pbkdf2(fn, ..., iter) 
    ... 
    for i = 0 to iter 
        ... 
        x = fn(x, ...) 
        ... 
    end 
    ... 
    return x 
end 

它有一個(gè)迭代參數(shù)，用于指定反復(fù) Hash 的次數(shù) —— 迭代次數(shù)越多，執(zhí)行時(shí)間越長(zhǎng)，破解也就越困難。

PBKDF（Password-Based Key Derivation Function，基于口令的密鑰導(dǎo)出函數(shù)），顧名思義，就是輸入“口令”（有規(guī)律的字串）輸出“密鑰”（無(wú)規(guī)律的長(zhǎng)串）的函數(shù)，并且計(jì)算過(guò)程會(huì)消耗一定資源。本質(zhì)上也是 Hash 函數(shù)，輸出結(jié)果稱之 DK（derived key）。

前端拉伸

拉伸次數(shù)越多雖然越安全，但這是以消耗服務(wù)端大量計(jì)算資源為代價(jià)的！為了能在安全和性能之間折衷，通常只選擇幾十到幾百毫秒的計(jì)算時(shí)間。

服務(wù)端的計(jì)算量如此沉重，以至于不堪重負(fù)；而如今的客戶端，系統(tǒng)資源卻普遍過(guò)剩。能否讓用戶來(lái)分擔(dān)一些計(jì)算量？

聽(tīng)起來(lái)似乎不可行。畢竟前端意味著公開(kāi)，將密碼相關(guān)的算法公開(kāi)，不會(huì)產(chǎn)生安全問(wèn)題嗎。

先來(lái)回顧下，傳統(tǒng)網(wǎng)站是如何處理口令的 —— 前端通常什么都不做，僅僅用于提交，口令都是由后端處理的：

現(xiàn)在，我們嘗試對(duì)前端進(jìn)行改造 —— 當(dāng)用戶在注冊(cè)、登錄等頁(yè)面中提交時(shí)，不再發(fā)送原始口令，而是口令的 DK：

后端，則不做任何改動(dòng)。（當(dāng)然這會(huì)影響已有賬號(hào)的使用，這里暫時(shí)先不考慮，假設(shè)這是個(gè)新網(wǎng)站）

這樣，即使用戶的口令很簡(jiǎn)單，但相應(yīng)的 DK 卻仍是個(gè)毫無(wú)意義的長(zhǎng)串。通過(guò) DK 的 Hash 值，是極難還原出 DK 的。（在本文開(kāi)頭就提到過(guò)了)

當(dāng)然，攻擊者更感興趣的不是 DK，而是口令。這倒是可以破解的 —— 只需將前后端算法結(jié)合，形成一個(gè)新函數(shù)：

F(x) = server_hash(client_hash(x)) 

用這個(gè)最終函數(shù) F 跑字典，還是可以猜口令的：

嘗試組合       耗時(shí)  F(x)               結(jié)果 
... 
qwert yuiop   1s   1C525DC73898A8EF   × 
qwert asdfg   1s   F9C0A131F43F1969   × 
qwert zxcvb   1s   08F026D689D26746   × 
... 

只不過(guò)其中有 client_hash 這道障礙，破解速度就大幅降低了！

所以，我們需要：

• 一個(gè)緩慢的 client_hash，增加跑字典的成本
• 一個(gè)快速的 server_hash，防止 DK 泄露

這樣，就能將絕大多數(shù)的計(jì)算轉(zhuǎn)移到前端，后端只需極少的處理，即可實(shí)現(xiàn)一個(gè)高強(qiáng)度的密碼保護(hù)系統(tǒng)。

對(duì)抗預(yù)算

由于前端的一切都是公開(kāi)的，所以 client_hash 的算法大家都知道。攻擊者可以把常用口令的 DK 提前算出來(lái)，編成一個(gè)新字典。將來(lái)拖庫(kù)后，直接跑這個(gè)“新字典”，就能節(jié)省大量時(shí)間了。

對(duì)于這種方式，就需要使用“加鹽”處理（事實(shí)上 PBKDF 本身就需要提供鹽參數(shù)）。例如，選擇用戶 ID 作為鹽：

function client_hash(password, salt) { 
    return pbkdf2(sha256, password, salt, 1000000); 
} 
 
client_hash('888888', 'tom@163.com');  // b80c97beaa7ca316... 
client_hash('888888', 'jack@qq.com');  // 465e26b9d899b05f... 

這樣即使口令相同，但用戶不同，生成的 DK 也是不同的。攻擊者只能針對(duì)特定賬號(hào)生成字典，適用范圍就小多了。

更進(jìn)一步，我們甚至可將“網(wǎng)站 ID”也摻入鹽中：

function client_hash(password, salt) { 
    return pbkdf2(sha256, password, salt, 1000000); 
} 
 
client_hash('888888', 'jack@qq.com/www.site-a.com');  // 77a1b139aa93ac8b... 
client_hash('888888', 'jack@qq.com/www.site-b.com');  // fab6b82e6a1d17d7... 

這樣即使同樣的“賬號(hào)密碼”，在不同網(wǎng)站上生成的 DK 也是不一樣了！

思考題：ID 是公開(kāi)的，能不能選個(gè)隱蔽的字段作為 client_hash 的鹽？

DK 泄露

DK 誕生于前端，后端對(duì)其 Hash 之后就不復(fù)存在了，所以它是個(gè)臨時(shí)值。理想情況下，它是不會(huì)泄露的。

但在某些場(chǎng)合，DK 還是有可能泄露的。例如服務(wù)器中毒、網(wǎng)絡(luò)傳輸被竊聽(tīng)等，都能導(dǎo)致 DK 泄露。

DK 泄露后，攻擊者就能控制該賬號(hào)了，這是無(wú)法避免的。但幸運(yùn)的是，DK 只是個(gè)無(wú)意義的長(zhǎng)串而已，攻擊者并不知道其背后的那個(gè)有意義的“口令”是什么。因此其他使用類似口令的賬號(hào)，就幸免于難了！

攻擊者若要通過(guò) DK 還原口令，就得用 client_hash 算法跑字典 —— 這個(gè)成本依然很大。相比之前的“最終函數(shù) F”，只是少算一次 server_hash 而已。（server_hash 本來(lái)就很快，可以忽略不計(jì)）。所以即使 DK 泄露，破解口令難度基本沒(méi)降低。

“賬號(hào)被盜，口令拿不到”，這就是“前端 Hash”的意義。

額外意義

前端的拉伸計(jì)算，使得用戶登陸時(shí)會(huì)耗費(fèi)一定的系統(tǒng)資源。這個(gè)副作用，事實(shí)上也能起到一定的防御效果。

對(duì)于普通用戶來(lái)說(shuō)，登陸時(shí)額外花費(fèi)幾秒時(shí)間，或許影響不大；但對(duì)于頻繁登錄的人來(lái)說(shuō)，將是一個(gè)極大的開(kāi)銷。有誰(shuí)會(huì)極其頻繁的登錄？這很可能就是“撞庫(kù)攻擊者” —— 他們從其他地方弄到一堆賬號(hào)口令，然后來(lái)這里撞運(yùn)氣，看看能成功登上多少。

由于我們是用 DK 登錄的，因此攻擊者也必須將待測(cè)的口令，先算出 DK 再提交，于是會(huì)增加不少計(jì)算成本。這和上一篇的 Proof-of-Work 有點(diǎn)類似。

如同拉伸彈簧需要付出能量，拉伸 Hash 同樣需要投入實(shí)實(shí)在在的算力。

優(yōu)化體驗(yàn)

事實(shí)上只要設(shè)計(jì)的合理，完全可以將“拉伸計(jì)算”的等待降到最小。例如，當(dāng)用戶輸完賬號(hào)和密碼后，程序立即開(kāi)始計(jì)算 DK，而不是等到提交時(shí)才開(kāi)始計(jì)算。如果網(wǎng)站有驗(yàn)證碼的話，即可在用戶輸入的同時(shí)進(jìn)行計(jì)算。這樣就能大幅提升用戶體驗(yàn)。

小結(jié)

兩種 Hash 函數(shù)：

• 快函數(shù)（MD5、SHA256 等，輸入數(shù)據(jù)“很長(zhǎng)很沒(méi)規(guī)律”時(shí)使用）
• 慢函數(shù)（PBKDF2、bcrypt 等，輸入數(shù)據(jù)“容易猜到”時(shí)使用）

關(guān)于“前端 Hash”，其實(shí)算是 “零知識(shí)證明”（zero-knowledge proof）的一種。什么是零知識(shí)證明，這里套用一個(gè)經(jīng)典的例子：

你擁有一個(gè)寶庫(kù)，可以通過(guò)念咒語(yǔ)來(lái)開(kāi)門。有天你想在朋友面前證明你能打開(kāi)寶庫(kù)，但又不想讓他聽(tīng)到咒語(yǔ)。這該如何解決？

正好，他知道你的寶庫(kù)里有個(gè)獨(dú)一無(wú)二的寶物，如果能取出來(lái)給他看，自然就能證明你能打開(kāi)。這樣就無(wú)需帶他到場(chǎng)，自己?jiǎn)为?dú)打開(kāi)取出寶物，然后拿給他看就行了。于是，就可以在不暴露咒語(yǔ)的同時(shí)，證明你能打開(kāi)。

這就是零知識(shí)證明 —— 證明者在不透露“任何有用信息”的情況下，使驗(yàn)證者相信某個(gè)論斷是正確的。

實(shí)際應(yīng)用

“前端 Hash”的做法在“密碼管理插件”中很常見(jiàn)：用戶的口令不再發(fā)往后端，而是僅僅用于生成 DK。然后再根據(jù) DK，給不同賬號(hào)生成不同的密碼。這樣就算遇到最壞的情況（例如服務(wù)器中毒、傳輸竊聽(tīng)、后端明文存儲(chǔ)等）導(dǎo)致密碼泄露，也不會(huì)暴露你的口令。最多損失某個(gè)賬號(hào)，而不影響其他賬號(hào)！

（另外，口令也不再填寫于原先的文本框中，而是填在插件的界面上，插件算出 DK 后自動(dòng)填到原先的文本框。這樣可以降低口令泄露的風(fēng)險(xiǎn)，例如網(wǎng)頁(yè)中可能潛伏著惡意腳本）

Web 應(yīng)用

不過(guò)現(xiàn)實(shí)中，天生內(nèi)置了前端 KDF 計(jì)算的網(wǎng)站并不多。不像插件可以調(diào)用本地程序，性能高且穩(wěn)定，瀏覽器則是良莠不齊，不同的版本性能差異很大，因此計(jì)算時(shí)間很不穩(wěn)定。

另外，在曾經(jīng)很長(zhǎng)一段時(shí)間里（IE 時(shí)代），瀏覽器的計(jì)算力都十分低下，以至于大家都保留了前端計(jì)算意義不大、“一切都由后端計(jì)算”的觀念。不過(guò)如今主流瀏覽器的性能已得到大幅提升，甚至 HTML5 還引入了 WebCrypto 規(guī)范，JS 可直接調(diào)用瀏覽器內(nèi)置的密碼學(xué)算法庫(kù)，其中就包括了 PBKDF2。由于是原生實(shí)現(xiàn)的，因此性能非常的高。這里有個(gè)簡(jiǎn)單的演示：

https://etherdream.github.io/FunnyScript/pbkdf2/test.html

更好的 KDF

當(dāng)然，作為口令 Hash 函數(shù)，PBKDF2 還不是最好的，因?yàn)樗皇呛?jiǎn)單地套用了現(xiàn)有的 Hash 函數(shù)而已，而非針對(duì)性的進(jìn)行設(shè)計(jì)。

2015 年 Password Hashing Competition 的勝出者 —— argon2，就非常先進(jìn)了。它不僅可設(shè)置時(shí)間成本（迭代次數(shù)），還能設(shè)置空間成本（內(nèi)存占用），使得算法重度依賴內(nèi)存，這樣對(duì)于一些計(jì)算力很強(qiáng)但存儲(chǔ)性能一般的設(shè)備（例如 GPU、ASIC 等）破解優(yōu)勢(shì)就大幅降低了。同時(shí)它還支持多線程計(jì)算，因此同樣的時(shí)間里可投入更多的工作量用于 Hash 計(jì)算，這讓破解成本也增加數(shù)倍。

當(dāng)然 argon2 還太新，目前尚未收錄到 WebCrypto 里。不過(guò)已有人將其移植成 JavaScrpt 版本，不妨值得一試。