實用密碼學工具——KDF

有些人說，一邊儲存一下密碼，另一邊把密碼發過去，比對一下就好了嘛！我相信很多人依然這麼想當然。

值得慶幸的是，這個提問者沒有這麼想，他問道：「用戶登錄時驗證，是對輸入的密碼從新加密一次，然後對比資料庫已加密的字元是否一致來判斷是否放行嗎？ 」而且，他對這個想法依然覺得似乎哪裡有問題，所以才來提問。

我本來只是在下面留言，讓他看KDF去。他表示中文資料少，那就幫忙幫到底，順便在這個系列裡面專門說一下KDF是什麼，它又是怎麼解決密碼驗證的問題的。

在登錄密碼這個典型案例中，我們都知道，密碼是雙方共享的，密碼如果在一端明文儲存，則一旦這一端被攻擊，另一端的秘密也就同時被泄漏了。特別是Unix這種一切基於文件的系統，密碼就直接寫在了/etc/passwd文件中，那麼，一旦/etc/passwd被讀出，秘密就不存在了。實際上在現代Unix系統中，密碼早就不是明文儲存，而是經過hash函數處理，保存在/etc/shadow中。這就意味著，攻擊者如果拿到了shadow文件，知道了密碼的hash，他依然無法知道密碼，依然無法在不改變驗證邏輯的前提下通過驗證。

不要覺得獲得密碼儲存很難，就可以放心大膽的使用明文密碼，歷史會不斷地打臉。國內知名技術論壇CSDN曾經就爆過醜聞，就是儲存的明文密碼被大規模泄漏。相關新聞至今都能非常方便搜索到（CSDN詳解600萬用戶密碼泄露始末：暫關閉登錄）。

然而，hash函數是用來做「向指定大小的空間映射的一個工具」。不管密碼有多長，最終都被映射到了一個固定大小的空間中。由於映射是一一對應的，如果來源空間遠遠小於目標空間，那麼實際會出現在目標空間的，只會是很小一部分值。比如說原空間有10種可能，目標空間有100種可能，那麼根據hash函數的特性，目標空間最多只可能出現10種可能——分別一一同原空間對應——而不是原來期望的100種可能。由於人能記住的密碼往往很短，單純地用一個hash函數處理，出現的可能性也只有不多的幾種。攻擊者可以不斷收集人類產生的密碼，計算它的hash，從而建立起hash到密碼的反向查詢表（彩虹表）。

所以，單純地對密碼做一次hash也沒有那麼安全。於是有人想當然的覺得：一次不行就兩次！

呵呵，兩次三次什麼，對於彩虹表來說，根本不算什麼事嘛！根本的原因在於，輸入的密碼複雜度過低，來源空間的可能性太小。解決的辦法很簡單，加點料（salt）就是了。

密碼雖然複雜度不高，但是加的salt可以隨機生成，只要最終計算hash時，使用salt和密碼的結合，即可充分利用目標空間。這樣，彩虹表就失效了，因為salt的可能性非常多。理論上，salt的空間需要大於hash空間，才能有效覆蓋目標空間。當然，這個salt自然是需要明文讀取的。

一旦驗證端資料庫被攻破，salt很可能也就知道了，雖然彩虹表沒有效了，但是由於密碼本身複雜度不高，攻擊者依然可以暴力破解密碼。為了增加攻擊者暴力破解的難度，hash函數被設計成很佔用資源的方式。比如說PBKDF2常用的設置里有成千上萬次迭代，來消耗CPU資源，但是被最近的GPU計算，FPGA計算大大地削弱了防護能力。Linux系統密碼採用的bcrypt，Litecoin使用的scrypt則消耗大量內存資源，可以用來對抗GPU計算。而最新的Argon2，則可以同時消耗大量內存和大量CPU。

說道這裡，KDF（Key Derivation Function）基本也就說完了：

• KDF是hash函數，通常用來將短密碼變成長密碼

• KDF是密碼學安全的，詳見（實用密碼學工具——Hash）
• KDF需要加salt，用於防彩虹表，salt長度至少要大於hash長度
• KDF需要有能力消耗大量計算資源，用於防暴力破解

推薦閱讀：