怎樣的Hash算法能對抗硬件破解？
一、前言
用過暴力破解工具 hashcat 的都知道，這款軟件的強大之處在于它能充分利用 GPU 計算，比起 CPU 要快很多。所以在破解諸如 WiFi 握手包、數據庫中的口令 Hash 值時，能大幅提高計算效率。
當然 GPU 仍屬于通用硬件，顯然還不是最優化的。要是為特定的算法打造特定的硬件，效率更是高出幾個量級。比特幣礦機就是很好的例子。
硬件仍在不斷進步，系統安全等級若不提高，暴力破解將會越來越容易。因此，一種能抵抗「硬件破解」的 Hash 算法，顯得很有必要。
二、時間成本
在探討如何對抗硬件之前，先來講解過去是如何對抗「暴力破解」的。
一些經典的 Hash 算法，例如 MD5、SHA256 等，計算速度是非常快的。如果口令 Hash 用了這類函數，將來攻擊者跑字典時，可達到非常高的速度。那些強度不高的口令，很容易被破解。
為了緩解這種狀況，密碼學家引入了「拉伸」的概念：反復 Hash 多次，從而增加計算時間。
例如 PBKDF2 算法就運用了這種思想。它的原理很簡單，對指定函數 F 反復進行 N 次：
- function PBKDF2(F, ..., N)
- ...
- for i = 0 to N
- ...
- x = F(x, ...)
- ...
- ...
- return x
這樣就能靈活設定 Hash 的時間成本了。例如設定 10000，對開發者來說，只是多了幾十毫秒的計算;但對于攻擊者，破解速度就降低了一萬倍!
1. 時間成本局限性
PBKDF2 確實有很大的效果，但對于硬件破解，卻無任何對抗措施。
因為 PBKDF2 只是對原函數簡單封裝，多執行幾次而已。如果原函數不能對抗硬件，那么套一層 PBKDF2 同樣也不能。
例如 WiFi 的 WPA2 協議，就是讓 HMAC-SHA1 重復執行 4096 次：
- DK = PBKDF2(HMAC−SHA1, Password, SSID, 4096, ...)
雖然相比單次 Hash 要慢上幾千倍，但這并不妨礙硬件破解。
硬件依然可發揮其「高并發」優勢，讓每個線程分別計算不同口令的 PBKDF2：
雖然耗時確實增加了很多倍，但并沒有影響到硬件的發揮。同樣的破解，效率仍然遠高于 CPU。
所以，時間成本并不能抵抗「硬件破解」。
2. 空間成本
單論計算性能，硬件是非常逆天的，但再綜合一些其他因素，或許就未必那么強大了。
假如某個硬件可開啟 100 個線程同時破解，但總內存卻只有 100M —— 這顯然是個很大的短板。
如果有種 PBKDF 算法空間復雜度為 2M，那將會有一半的線程，因內存不足而無法運行!
若再極端些，將空間復雜度提高到 100M，那么整個硬件只能開啟 1 個線程，99% 的算力都無法得到發揮!
這樣，即使硬件的計算性能再強勁，也終將卡在內存這個瓶頸上。
不過，怎樣才能讓算法消耗這么多內存，同時又不能被輕易繞過?這里舉個簡單的例子：
- function MemoryHard(..., M)
- int space[M]
- for i = 0 .. 10000
- x = Hash(x, ...)
- space[int(x) % M] ^= int(x)
- return Hash(space)
當然這個例子是隨意寫的，并不嚴謹。但主要思想是：
- 引入了空間成本 M，并申請相應的內存
- 利用經典 Hash 函數的結果，作為數組索引，對內存進行讀寫
- 每次內存讀寫，都會影響到最終結果
由于 Hash 函數的結果是不可預測的，因此事先無法知道哪些位置會被訪問。只有準備充足的內存，才能達到 O(1) 的訪問速度。
攻擊者要想達到同樣的速度，就不得不花費同樣多的內存!
3. 時空權衡
通常硬件的「計算資源」要比「存儲資源」充足得多，因此可考慮「時間換空間」的策略 —— 使用更復雜的存儲管理機制，從而減少空間分配，這樣就能開啟更多的線程。
比如犧牲 40% 的速度，換取 50% 的空間：
由于空間成本是之前的一半，因此可多啟動一倍的線程。算上折損，最終速度仍增加了 20%。
當然，如果 性能折損比例 > 空間壓縮比例，這個方案就沒有意義了。
4. 訪問瓶頸
事實上，內存除了容量外，訪問頻率也是有限制的。
就內存本身而言，每秒讀寫次數是有上限的。其次，計算單元和內存之間的交互，更是一大瓶頸。
像 MD5、SHA256 這類 Hash 函數，空間復雜度非常低。硬件破解時，每個計算單元光靠自身的寄存器以及高速緩存，就差不多夠用了，很少需要訪問內存。
但對于 Memory-Hard 函數，就沒那么順利了。它不僅很占內存，而且還十分頻繁地「隨機訪問」內存，因此很難命中高速緩存。這使得每次訪問，幾乎都會和內存進行交互，從而占用大量帶寬。
如果有多個計算單元頻繁訪問，那么內存帶寬就會成為瓶頸。這樣，也能起到抑制并發的效果!
例如 bcrypt 算法就運用了類似思想，它在計算過程中頻繁訪問 4KB 的內存空間，從而消耗帶寬資源。
不過隨著硬件發展，bcrypt 的優勢也在逐漸降低。為了能更靈活地設定內存大小，scrypt 算法出現了 —— 它既有時間成本，還有空間成本，這樣就能更持久地對抗。
當然，空間成本也不是絕對有效的。如果攻擊者不惜代價，制造出存儲「容量」和「帶寬」都很充足的硬件設備，那么仍能高效地進行破解。
三、并行維度
十幾年來，內存容量翻了好幾翻，但 CPU 主頻卻沒有很大提升。由于受到物理因素的制約，主頻已很難提升，只能朝著多核發展。
然而像 PBKDF2 這樣的算法，卻只能使用單線程計算 —— 因為它每次 Hash 都依賴上一次的 Hash 結果。這種串行的模式，是無法拆解成多個任務的，也就無法享受多線程的優勢。
這就意味著 —— 時間成本，終將達到一個瓶頸!
對此，多線程真的無能為力嗎?
盡管單次 PBKDF 不能被拆解，但可以要求多次 PBKDF，并且互相沒有依賴。這樣多線程就能派上用場了。
例如我們對 PBKDF 進行封裝，要求執行 4 次完全獨立的計算，最后再將結果融合到一起：
- function Parall(Password, Salt, ...)
- -- 該部分可被并行 --
- for i = 0 .. 4
- DK[i] = PBKDF(Password, Salt + i, ...)
- ------------------
- return Hash(DK)
這樣，我們即可開啟 4 個線程，同時計算這 4 個 PBKDF。
現在就能用 1 秒的時間，獲得之前 4 秒的強度!攻擊者破解時，成本就增加了 4 倍。
如今主流的口令 Hash 函數都支持「并行維度」。例如 scrypt 以及更先進的 argon2，都可通過參數 p 設定。
1. 線程開銷
現實中，「線程數」未必要和「并行維度」一樣多，因為還得考慮「空間成本」。
假設上述的 PBKDF 空間成本有 512MB，如果開啟 4 個線程，就得占用 2GB 的內存!若用戶只有 1.5 GB 的空閑內存，還不如只開 2 個線程，反而會更順暢。
當然，也可以開 3 個線程，但這樣會更快嗎?顯然不會!
因為 4 個任務分給 3 個線程，總有一個線程得做兩份，所以最終用時并沒有縮短。反而增加了線程創建、內存申請等開銷。
這里有個 scrypt 算法在線演示：https://etherdream.github.io/webscrypt/example/basic/
大家可體會下 時空成本(N)、并行維度(P)、線程數(Thread)對計算的影響。
四、小結
到此，我們講解了 3 個對抗破解的因素：
- 時間成本(迭代次數)
- 空間成本(內存容量、帶寬)
- 并行維度(多線程資源)
或許你已感悟到這其中的理念 —— 讓 Hash 算法牽涉更多的硬件能力。這樣，只有綜合性能高的硬件，才能順利運行;專為某個功能打造的硬件，就會出現瓶頸!
照這個思路，我們也可發揮想象：假如有個算法使用了不少條件分支指令，而 CPU 正好擁有強大的分支預測功能。這樣該算法在 CPU 上運行時，就能獲得很高的性能;而在其他精簡過的硬件上，就沒有這么好的效果了。
當然這里純屬想象，自創密碼學算法是不推薦的。現實中還是得用更權威的算法，例如 argon2、scrypt 等。
五、應用
本文提到的對抗方案，都是從硬件消耗上進行的。不過，這樣傷敵一千也會自損八百。
假如服務器每 Hash 一次口令，就得花 1 秒時間加 1GB 內存，那么一旦有幾十個人同時訪問，系統可能就支撐不住了。
有什么辦法，既能使用高成本的 Hash，又不耗費服務器資源?事實上，口令 Hash 完全可以在客戶端計算：
- DK = Client_PBKDF(Password, Username, Cost ...)
因為口令與 DK 的對應關系是唯一的。賬號注冊時，提交的就是 DK;登錄時，如果提交的 DK 相同，也就證明口令是相同的。
所以客戶端無需提供原始口令，服務端也能認證，這就是「零知識證明」。使用這種方案，還能進一步減少口令泄露的環節，例如網絡被竊聽、服務端惡意程序等。
當然，服務端收到 DK 后，還不能立即存儲。因為萬一 DK 泄露了，攻擊者還是能用它登上用戶的賬號 —— 盡管不知道口令。
因此，服務端需對 DK 再進行 Hash 處理。
不過這一次，只需快速的 Hash 函數即可。因為 DK 是無規律的數據(熵很高)，無法通過跑字典還原，所以用簡單的 Hash 就能保護。
這樣，服務器只需極小的計算開銷，就能實現高強度的口令安全了!
將來即使被拖庫，攻擊者也只能使用如下 Hash 函數跑字典：
- f(x) => server_hash( client_hash(x) )
因為其中用到了 client_hash，所以這個最終函數同樣能對抗硬件破解!
