雜湊函式——例如 MD5、SHA-1、SHA-256、SHA-3 與 BLAKE2——是密碼學家的瑞士刀：它們被用在數位簽章、公鑰加密、完整性驗證、訊息鑑別、密碼保護、金鑰協商協定，以及許多其他密碼協定中。

無論你是在加密一封電子郵件、用手機傳訊息、連上 HTTPS 網站，或透過 IPSec、SSH 連到遠端機器，引擎蓋下的某處一定有一個雜湊函式。

雜湊函式是所有密碼演算法中最多才多藝、也最無所不在的。

真實世界的例子：

• 雲端儲存系統用它們識別相同的檔案、偵測被修改的檔案。
• Git 版本控制系統用它們識別 repository 中的檔案。
• 主機型入侵偵測系統（HIDS）用它們偵測被修改的檔案。
• 網路型入侵偵測系統（NIDS）用雜湊偵測通過網路的已知惡意資料。
• 數位鑑識分析者用雜湊值證明數位證物未被修改。
• 比特幣在其工作量證明系統中使用雜湊函式。

與串流密碼「從短輸出產生長輸出」相反，雜湊函式接收長輸入、產生短輸出，該輸出稱為雜湊值或摘要（digest），通常是 256 或 512 位元的固定長度。

別把密碼學雜湊函式與非密碼學的搞混。

非密碼學雜湊函式用於雜湊表這類資料結構，或用來偵測意外錯誤，完全不提供任何安全性。例如循環冗餘檢查（CRC）就是用來偵測檔案意外修改的非密碼學雜湊。

本章脈絡#

1. 安全雜湊函式——原像抗性與碰撞抗性，以及生日攻擊與 Rho 方法。
2. 建構雜湊函式——Merkle–Damgård 建構、Davies–Meyer 壓縮函式、海綿函式。
3. SHA 家族——SHA-1（已破解）、SHA-2、SHA-3 競賽與 Keccak。
4. BLAKE2——今日最快的安全雜湊。

常見錯誤#

儘管看似簡單，雜湊函式若用錯地方或用錯方式，會造成重大的安全麻煩——例如在透過網路傳輸資料的應用中，用 CRC 這類弱校驗和演算法而非密碼學雜湊來檢查檔案完整性。

但這種弱點與下面兩個相比還算小事——後者能讓看似安全的雜湊函式完全失守。

長度延伸攻擊#

長度延伸攻擊（length-extension attack）是 Merkle–Damgård 建構的主要威脅。

基本上，若你知道某則未知訊息 M（由區塊 M₁ 與 M₂ 組成，經填充後）的 Hash(M)，你就能對任意區塊 M₃ 算出 Hash(M₁ ‖ M₂ ‖ M₃)。

因為 M₁ ‖ M₂ 的雜湊，正是緊接在 M₂ 之後的那個鏈接值，所以即使你不知道被雜湊的資料是什麼，你也能往被雜湊的訊息後面再加一個區塊 M₃。

而且這個技巧可推廣到未知訊息或後綴中的任意數量區塊。

長度延伸攻擊不會影響雜湊函式的多數應用，但若雜湊被「創意」地使用，它就可能危及安全。

遺憾的是，SHA-2 系列易受長度延伸攻擊——儘管 NSA 設計、NIST 標準化它們時，雙方都很清楚這個瑕疵。

這個瑕疵本來只要讓最後一次壓縮函式呼叫與其他所有呼叫不同就能避免（例如額外傳入一個 1 位元，而先前的呼叫傳入 0 位元）。

而這正是 BLAKE2 的做法。

欺騙儲存證明協定#

雲端運算應用在儲存證明協定（proof-of-storage protocols）中使用雜湊函式——也就是伺服器（雲端供應商）向客戶端（雲端儲存服務的使用者）證明它確實代客戶端儲存了應該儲存的檔案。

2007 年 Ramakrishna Kotla、Lorenzo Alvisi 與 Mike Dahlin 的論文〈SafeStore: A Durable and Practical Storage System〉提出一個驗證某檔案 M 之儲存的協定：

1. 客戶端挑一個隨機值 C 作為挑戰。
2. 伺服器計算 Hash(M ‖ C) 作為回應，把結果送給客戶端。
3. 客戶端也計算 Hash(M ‖ C)，檢查它是否與從伺服器收到的值相符。

該論文的前提是：伺服器若不知道 M，就猜不出 Hash(M ‖ C)，因此無法欺騙客戶端。

但有個陷阱：現實中 Hash 是一個迭代雜湊，它逐區塊處理輸入，在區塊之間計算中間鏈接值。

假設 Hash 是 SHA-256、M 長 512 位元（SHA-256 一個區塊的大小），伺服器就能作弊：

1. 第一次收到 M 時，伺服器計算 H₁ = Compress(H₀, M₁)——從 SHA-256 的初始值 H₀ 與 512 位元的 M 得到的鏈接值。
2. 它把 H₁ 記在記憶體中，然後丟棄 M——此刻它已不再儲存 M。
3. 當客戶端送來隨機值 C，伺服器對 C 補上填充湊成完整區塊，計算 Compress(H₁, C)，把結果當成 Hash(M ‖ C) 回傳。

客戶端於是相信伺服器持有完整訊息——但如你所見，它可能並沒有。

這個技巧對 SHA-1、SHA-2，以及 SHA-3 與 BLAKE2 都有效。

解法很簡單：改要求 Hash(C ‖ M) 而非 Hash(M ‖ C)。

延伸閱讀#

• 1980、90 年代的經典：Ralph Merkle 的〈One Way Hash Functions and DES〉、Ivan Damgård 的〈A Design Principle for Hash Functions〉，以及第一份對基於區塊密碼之雜湊的徹底研究——Preneel、Govaerts 與 Vandewalle 的〈Hash Functions Based on Block Ciphers: A Synthetic Approach〉。
• 碰撞搜尋：van Oorschot 與 Wiener 於 1997 年的〈Parallel Collision Search with Cryptanalytic Applications〉。想深入了解支撐原像抗性、碰撞抗性與長度延伸攻擊的理論安全概念，可搜尋 indifferentiability。
• 較近期的研究：SHA-3 競賽的檔案庫，包含所有不同演算法與它們如何被攻破。可查閱 SHA-3 Zoo（http://ehash.iaik.tugraz.at/wiki/The_SHA-3_Zoo ^↗）與 NIST 的頁面（http://csrc.nist.gov/groups/ST/hash/sha-3/ ^↗）。
• Keccak 與海綿函式：Keccak 設計者的官方頁面 http://keccak.noekeon.org/ ^↗ 與 http://sponge.noekeon.org/ ^↗。

最後但同樣重要——研究這兩個真實世界中對弱雜湊函式的利用案例：

• 國家級惡意軟體 Flame 利用一個 MD5 碰撞偽造憑證，讓自己看起來像一個合法的軟體。
• Xbox 遊戲主機用一個弱區塊密碼（稱為 TEA）來建構雜湊函式，這被用來破解主機並在其上執行任意程式碼。