雜湊函式的安全性概念與我們目前看過的都不同：

  • 密碼保護資料的機密性，努力保證明碼傳送的資料無法被讀取。
  • 雜湊函式保護資料的完整性（integrity），努力保證資料——無論是明碼還是加密傳送——沒有被修改。

若一個雜湊函式是安全的，兩份相異的資料應該永遠有不同的雜湊值。

因此一個檔案的雜湊值可以作為它的識別碼。

為什麼數位簽章要簽雜湊#

以雜湊函式最常見的應用數位簽章為例：應用程式處理的是「待簽訊息的雜湊」而非訊息本身，雜湊扮演訊息的識別碼。

圖 6-2：數位簽章方案中的雜湊函式：雜湊作為訊息的代理

只要訊息中有一個位元被改動，訊息的雜湊就會完全不同，因此雜湊函式有助於確保訊息未被修改。

簽署訊息的雜湊與簽署訊息本身一樣安全，而簽署一個 256 位元的短雜湊，比簽署一則可能非常龐大的訊息快得多。

事實上，多數簽章演算法只能處理雜湊值這類短輸入。

不可預測性#

雜湊函式的全部密碼學強度，都源自其輸出的不可預測性。

以 NIST 標準雜湊函式 SHA-256 對 ASCII 字母 a、b、c 計算的 256 位元十六進位值為例。這三個輸入只差一兩個位元（a 是 01100001、b 是 01100010、c 是 01100011），但雜湊值完全不同：

SHA-256("a") = 87428fc522803d31065e7bce3cf03fe475096631e5e07bbd7a0fde60c4cf25c7
SHA-256("b") = a63d8014dba891345b30174df2b2a57efbb65b4f9f09b98f245d1b3192277ece
SHA-256("c") = edeaaff3f1774ad2888673770c6d64097e391bc362d7d6fb34982ddf00efd18cb

只給你這三個雜湊，你不可能預測 d 的 SHA-256 雜湊值、甚至它的任何一個位元。

安全雜湊函式的一般性理論定義是：它的行為要像一個真正的隨機函式（有時稱為 random oracle，隨機預言機）——它不該具有任何隨機函式所不會有的性質或樣式。

這個定義對理論家有用，但實務上我們需要更具體的概念：原像抗性與碰撞抗性。

原像抗性#

一個給定雜湊值 H 的原像（preimage），是任何滿足 Hash(M) = H 的訊息 M。

原像抗性（preimage resistance）描述的安全保證是：給定一個隨機雜湊值，攻擊者永遠找不到它的原像。這也是雜湊函式有時被稱為單向函式（one-way functions）的原因——你可以從訊息走到它的雜湊，反過來卻不行。

雜湊函式無法被「反轉」#

首先注意：即使給定無限的計算能力，雜湊函式也無法被反轉。

假設我用 SHA-256 雜湊某則訊息，得到這個 256 位元的雜湊值：

f67a58184cef99d6dfc3045f08645e844f2837ee4bfcc6c949c9f76743667adfd

即使有無限算力，你也永遠無法判定我挑的是哪則訊息——因為有很多訊息雜湊到同一個值。你會找到一些產生這個雜湊值的訊息（可能包含我挑的那則），但無法確定我用的是哪一則。

256 位元雜湊有 2^256 個可能值，但 1024 位元訊息有多得多的可能值（2^1024）。

因此平均而言，每個可能的 256 位元雜湊值會有 2^1024 / 2^256 = 2^768 個 1024 位元的原像。

第一原像與第二原像#

實務上我們必須確保：要找到任何一則映射到給定雜湊值的訊息都實際上不可能，而不只是找到當初用的那則——這才是原像抗性真正的意思。

  • 第一原像抗性（first-preimage resistance，或簡稱原像抗性）：實際上不可能找到雜湊到某給定值的訊息。
  • 第二原像抗性（second-preimage resistance）：給定訊息 M₁，實際上不可能找到另一則訊息 M₂，使其雜湊到與 M₁ 相同的值。

找原像的成本#

給定一個雜湊函式與一個雜湊值，你可以嘗試不同的訊息直到命中目標雜湊：

find-preimage(H) {
    repeat {
        M = random_message()
        if Hash(M) == H then return M
    }
}

若雜湊的位元長度 n 夠大，find-preimage() 永遠不會完成——因為找到一個原像平均要 2^n 次嘗試。

對 SHA-256、BLAKE2 這類現代雜湊的 n = 256 而言，這是絕望的處境。

為什麼第二原像抗性比較弱#

若你找得到第一原像，你也找得到第二原像（對同一個雜湊函式而言）。證明如下——若 solve-preimage() 能回傳給定雜湊值的原像，你就能這樣找出某訊息 M 的第二原像：

solve-second-preimage(M) {
    H = Hash(M)
    return solve-preimage(H)
}

也就是把第二原像問題視為原像問題，套用原像攻擊。

由此可知：任何具第二原像抗性的雜湊函式，也具原像抗性。

換句話說，我們能用來找第二原像的最佳攻擊，與找第一原像的最佳攻擊幾乎相同（除非該雜湊函式有某種缺陷允許更有效率的攻擊）。

原像搜尋攻擊本質上與對區塊密碼或串流密碼的金鑰還原攻擊是同一回事——都是對單一個魔法值的暴力搜尋。

碰撞抗性#

無論你選哪個雜湊函式，碰撞必然存在，這是鴿籠原理（pigeonhole principle）的結果：若你有 m 個洞、n 隻鴿子要放進去，且 n 大於 m，那麼至少有一個洞必須裝進超過一隻鴿子。

這可以推廣到其他物件與容器。例如美國憲法中任意 27 個字的序列，至少包含兩個以同一字母開頭的字。

在雜湊函式的世界裡，洞是雜湊值、鴿子是訊息。既然可能的訊息遠多於雜湊值，碰撞就必然存在。

然而儘管碰撞無可避免，一個雜湊函式要被視為碰撞抗性（collision resistant）的，找到碰撞就必須和找到原始訊息一樣困難——換句話說，攻擊者不該能找到兩則雜湊到同一值的相異訊息。

碰撞抗性與第二原像抗性有關：若你能為某雜湊函式找到第二原像，你也能找到碰撞：

solve-collision() {
    M = random_message()
    return (M, solve-second-preimage(M))
}

因此：任何具碰撞抗性的雜湊，也具第二原像抗性。

尋找碰撞#

找碰撞比找原像快——大約是 2^(n/2) 次而非 2^n 次運算，這要歸功於生日攻擊（birthday attack）。

核心想法是：給定 N 則訊息與同樣多的雜湊值，你可以考慮每一對雜湊值，總共產生 N × (N − 1) / 2 個潛在碰撞（與 N² 同一數量級）。

它叫生日攻擊，因為通常用所謂的生日悖論來說明——只要 23 個人的群體，就有 1/2 的機率存在兩人生日相同。

N × (N − 1) / 2 是相異訊息對的數量，除以 2 是因為我們把 (M₁, M₂) 與 (M₂, M₁) 視為同一對——順序無關緊要。

作為對照：原像搜尋時 N 則訊息只給你 N 個候選原像，而同樣的 N 則訊息卻能給你約 N² 個潛在碰撞。有了 N² 而非 N，我們說找到解的機會平方級地增加；搜尋的複雜度也就平方級地降低——找碰撞只需要 2^n 的平方根，也就是 2^(n/2) 則訊息。

天真的生日攻擊#

執行生日攻擊最簡單的方式：

  1. 計算 2^(n/2) 則任選訊息的 2^(n/2) 個雜湊，把所有「訊息／雜湊」對存進一份清單。
  2. 依雜湊值排序這份清單，讓相同的雜湊值彼此相鄰。
  3. 搜尋排序後的清單，找出兩個雜湊值相同的連續項目。

遺憾的是，這個方法需要大量記憶體（足以存放 2^(n/2) 個訊息／雜湊對），而且排序大量元素會拖慢搜尋——即使用快速排序，平均也需要約 n·2^n 次基本運算。

低記憶體碰撞搜尋：Rho 方法#

Rho 方法是一個找碰撞的演算法，與天真的生日攻擊不同，它只需要少量記憶體：

  1. 給定一個雜湊值為 n 位元的雜湊函式，挑一個隨機雜湊值 H₁，並定義 H₁ = H′₁。
  2. 計算 H₂ = Hash(H₁) 與 H′₂ = Hash(Hash(H′₁))——前者套用一次雜湊函式，後者套用兩次。
  3. 迭代這個過程，計算 H(i+1) = Hash(Hi) 與 H′(i+1) = Hash(Hash(H′i))，直到你到達某個 i 使得 H(i+1) = H′(i+1)。

Hi 的序列最終會進入一個循環（cycle），其形狀像希臘字母 rho（ρ）——一條尾巴接上一個圈。

圖 6-3：Rho 方法的結構：每個箭頭代表一次雜湊求值，循環對應一個碰撞

例如若循環從 H₅ 開始，它就對應到碰撞 Hash(H₄) = Hash(H₁₀) = H₅。上述演算法讓攻擊者能偵測循環的位置，從而找到碰撞。

進階的碰撞搜尋技巧先偵測循環的起點，再找出碰撞，不必在記憶體中存放大量值、也不必排序長清單。

Rho 方法大約需要 2^(n/2) 次運算才會成功：平均而言，循環與尾巴各包含約 2^(n/2) 個雜湊值（n 為雜湊值的位元長度），因此你需要至少 2^(n/2) + 2^(n/2) 次雜湊求值才能找到碰撞。

Backward 雜湊函式 建構雜湊函式 Forward