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

前言

幾乎每隔一段時間，就會聽到“XX 網站被拖庫”的新聞。之后又會出現一些報道，分析該網站使用最多的密碼是什么、有多少等等。

眾所周知，密碼在數據庫中通常是以 Hash 值存儲的，并且還加了鹽。攻擊者即使知道具體的 Hash 算法，也只能暴力破解。照理說這是極其費勁的，然而現實中卻總有大量密碼被破解，是什么導致安全性如此脆弱？

究其原因，莫過于這兩點：口令密碼、算法成本。

[[217148]]

口令密碼

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

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

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

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

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

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

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

口令雖然方便，但缺陷也很明顯：因為它是有規律的，所以猜起來就容易多了。攻擊者只需測試常用單詞組合，沒準就能猜到了：

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

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

算法成本

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

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

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

然而不幸的是，常用的 Hash 函數都是很快的。因為它們生來就有多種用途，并非為口令處理而設計。例如計算一個大文件的校驗值，速度顯然很重要。

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

現實中，由于不少網站使用了“快函數”來處理口令，因此數據庫泄露后，大量口令被還原也就在所難免了。

增加成本

雖然 Hash 函數單次執行很快，但我們可以反復執行大量次數，這樣總體耗時就變長了。例如：

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

在密碼學中，這種方式叫做 拉伸。現實中有不少方案，例如 PBKDF2 —— 它沒有重頭設計一種新算法，而是對現有的函數進行封裝，從而更適合用于口令處理：

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

它有一個迭代參數，用于指定反復 Hash 的次數 —— 迭代次數越多，執行時間越長，破解也就越困難。

PBKDF（Password-Based Key Derivation Function，基于口令的密鑰導出函數），顧名思義，就是輸入“口令”（有規律的字串）輸出“密鑰”（無規律的長串）的函數，并且計算過程會消耗一定資源。本質上也是 Hash 函數，輸出結果稱之 DK（derived key）。

前端拉伸

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

服務端的計算量如此沉重，以至于不堪重負；而如今的客戶端，系統資源卻普遍過剩。能否讓用戶來分擔一些計算量？

聽起來似乎不可行。畢竟前端意味著公開，將密碼相關的算法公開，不會產生安全問題嗎。

先來回顧下，傳統網站是如何處理口令的 —— 前端通常什么都不做，僅僅用于提交，口令都是由后端處理的：

現在，我們嘗試對前端進行改造 —— 當用戶在注冊、登錄等頁面中提交時，不再發送原始口令，而是口令的 DK：

后端，則不做任何改動。（當然這會影響已有賬號的使用，這里暫時先不考慮，假設這是個新網站）

這樣，即使用戶的口令很簡單，但相應的 DK 卻仍是個毫無意義的長串。通過 DK 的 Hash 值，是極難還原出 DK 的。（在本文開頭就提到過了)

當然，攻擊者更感興趣的不是 DK，而是口令。這倒是可以破解的 —— 只需將前后端算法結合，形成一個新函數：

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

用這個最終函數 F 跑字典，還是可以猜口令的：

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

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

所以，我們需要：

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

這樣，就能將絕大多數的計算轉移到前端，后端只需極少的處理，即可實現一個高強度的密碼保護系統。

對抗預算

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

對于這種方式，就需要使用“加鹽”處理（事實上 PBKDF 本身就需要提供鹽參數）。例如，選擇用戶 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 也是不同的。攻擊者只能針對特定賬號生成字典，適用范圍就小多了。

更進一步，我們甚至可將“網站 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... 

這樣即使同樣的“賬號密碼”，在不同網站上生成的 DK 也是不一樣了！

思考題：ID 是公開的，能不能選個隱蔽的字段作為 client_hash 的鹽？

DK 泄露

DK 誕生于前端，后端對其 Hash 之后就不復存在了，所以它是個臨時值。理想情況下，它是不會泄露的。

但在某些場合，DK 還是有可能泄露的。例如服務器中毒、網絡傳輸被竊聽等，都能導致 DK 泄露。

DK 泄露后，攻擊者就能控制該賬號了，這是無法避免的。但幸運的是，DK 只是個無意義的長串而已，攻擊者并不知道其背后的那個有意義的“口令”是什么。因此其他使用類似口令的賬號，就幸免于難了！

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

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

額外意義

前端的拉伸計算，使得用戶登陸時會耗費一定的系統資源。這個副作用，事實上也能起到一定的防御效果。

對于普通用戶來說，登陸時額外花費幾秒時間，或許影響不大；但對于頻繁登錄的人來說，將是一個極大的開銷。有誰會極其頻繁的登錄？這很可能就是“撞庫攻擊者” —— 他們從其他地方弄到一堆賬號口令，然后來這里撞運氣，看看能成功登上多少。

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

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

優化體驗

事實上只要設計的合理，完全可以將“拉伸計算”的等待降到最小。例如，當用戶輸完賬號和密碼后，程序立即開始計算 DK，而不是等到提交時才開始計算。如果網站有驗證碼的話，即可在用戶輸入的同時進行計算。這樣就能大幅提升用戶體驗。

小結

兩種 Hash 函數：

• 快函數（MD5、SHA256 等，輸入數據“很長很沒規律”時使用）
• 慢函數（PBKDF2、bcrypt 等，輸入數據“容易猜到”時使用）

關于“前端 Hash”，其實算是 “零知識證明”（zero-knowledge proof）的一種。什么是零知識證明，這里套用一個經典的例子：

你擁有一個寶庫，可以通過念咒語來開門。有天你想在朋友面前證明你能打開寶庫，但又不想讓他聽到咒語。這該如何解決？

正好，他知道你的寶庫里有個獨一無二的寶物，如果能取出來給他看，自然就能證明你能打開。這樣就無需帶他到場，自己單獨打開取出寶物，然后拿給他看就行了。于是，就可以在不暴露咒語的同時，證明你能打開。

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

實際應用

“前端 Hash”的做法在“密碼管理插件”中很常見：用戶的口令不再發往后端，而是僅僅用于生成 DK。然后再根據 DK，給不同賬號生成不同的密碼。這樣就算遇到最壞的情況（例如服務器中毒、傳輸竊聽、后端明文存儲等）導致密碼泄露，也不會暴露你的口令。最多損失某個賬號，而不影響其他賬號！

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

Web 應用

不過現實中，天生內置了前端 KDF 計算的網站并不多。不像插件可以調用本地程序，性能高且穩定，瀏覽器則是良莠不齊，不同的版本性能差異很大，因此計算時間很不穩定。

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

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

更好的 KDF

當然，作為口令 Hash 函數，PBKDF2 還不是最好的，因為它只是簡單地套用了現有的 Hash 函數而已，而非針對性的進行設計。

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

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