1980 年代，密碼學家意識到雜湊一則訊息最簡單的方式，就是把它切成片段，再用相似的演算法逐一處理每個片段。這個策略稱為迭代雜湊（iterative hashing），主要有兩種形式：

• 使用壓縮函式（把輸入變換成更小的輸出）的迭代雜湊——也就是 Merkle–Damgård 建構。
• 使用置換（把輸入變換成同樣大小的輸出，且任兩個不同輸入給出不同輸出）的迭代雜湊——這類函式稱為海綿函式（sponge functions）。

Merkle–Damgård 建構#

從 1980 年代到 2010 年代開發的所有雜湊函式，都基於 Merkle–Damgård（M–D）建構：MD4、MD5、SHA-1、SHA-2 家族，以及較少人知的 RIPEMD 與 Whirlpool。

M–D 建構並不完美，但它簡單，而且已證明對許多應用來說夠安全。

另外：MD4、MD5、RIPEMD 中的 MD 指的是 message digest，不是 Merkle–Damgård。

運作方式#

要雜湊一則訊息，M–D 建構把訊息切成同樣大小的區塊，再用一個壓縮函式把這些區塊與一個內部狀態混合：

M₁              M₂
 ↓               ↓
H₀ → Compress → H₁ → Compress → H₂ → ...

• H₀ 是內部狀態的初始值（IV）。
• H₁, H₂, ... 稱為鏈接值（chaining values）。
• 內部狀態的最終值就是訊息的雜湊值。

訊息區塊通常是 512 或 1024 位元，原則上可以是任何大小，但對某個給定的雜湊函式而言是固定的。例如 SHA-256 用 512 位元區塊，SHA-512 用 1024 位元區塊。

填充區塊#

若訊息無法切成一連串完整的區塊怎麼辦？例如區塊是 512 位元，而訊息是 520 位元——那就是一個 512 位元區塊加 8 位元。

M–D 建構這樣組成最後一個區塊：取剩下的位元 → 附加一個 1 位元 → 附加若干 0 位元 → 最後附加原始訊息的長度（以固定位元數編碼）。

這個填充技巧保證任兩則相異訊息都會給出相異的區塊序列，因而給出相異的雜湊值。

例如用 SHA-256（512 位元訊息區塊）雜湊 8 位元字串 10101010，第一個也是唯一的區塊會是：

10101010 1000000000000000 ... 0000000000001000
└─訊息─┘ └────────填充位元────────┘└──長度──┘

末尾的 1000 是訊息長度（8 的二進位）。

安全保證#

M–D 建構本質上是一種「把接收固定短輸入的安全壓縮函式，變成接收任意長度輸入的安全雜湊函式」的方法。

若壓縮函式具原像與碰撞抗性，則以 M–D 建構在其上構成的雜湊函式也具原像與碰撞抗性。

這是因為任何針對 M–D 雜湊的成功原像攻擊，都能轉換成針對該壓縮函式的成功原像攻擊——Merkle 與 Damgård 在 1989 年的論文中都證明了這點。碰撞也是同理：攻擊者若不先攻破底層壓縮函式的碰撞抗性，就無法攻破雜湊的碰撞抗性。

對鏈接值 X 與 Y（兩者都與 H₀ 相異）而言，碰撞 Compress(X, M₁) = Compress(Y, M₂) 不會給你雜湊的碰撞，因為你無法把這個碰撞插進雜湊的迭代鏈中——除非其中一個鏈接值恰好是 X、另一個恰好是 Y，而那不太可能發生。

多重碰撞#

多重碰撞（multicollision）指三則以上的訊息雜湊到同一個值。例如三元組 (X, Y, Z) 滿足 Hash(X) = Hash(Y) = Hash(Z)，稱為 3-碰撞。

理想上多重碰撞應該比單一碰撞難找得多，但有個簡單技巧能以幾乎相同的成本找到它們：

1. 找出第一個碰撞：Compress(H₀, M1.1) = Compress(H₀, M1.2) = H₁。現在你有一個 2-碰撞。
2. 以 H₁ 為起始鏈接值找出第二個碰撞：Compress(H₁, M2.1) = Compress(H₁, M2.2) = H₂。現在你有一個 4-碰撞——四則訊息 M1.1‖M2.1、M1.1‖M2.2、M1.2‖M2.1、M1.2‖M2.2 都雜湊到 H₂。
3. 重複 N 次，你就會有 2^N 則 N 區塊訊息雜湊到同一個值——一個 2^N-碰撞，成本「只有」約 N·2^N 次雜湊計算。

實務上這個技巧沒那麼實用，因為它一開始就要求你先找到一個基本的 2-碰撞。

Davies–Meyer 建構：用區塊密碼做壓縮函式#

SHA-256、BLAKE2 這類真實雜湊函式所用的壓縮函式，全都基於區塊密碼——因為那是建構壓縮函式最簡單的方式。最常見的是 Davies–Meyer 建構。

給定訊息區塊 Mᵢ 與前一個鏈接值 H(i−1)，Davies–Meyer 壓縮函式用區塊密碼 E 計算新的鏈接值：

Hᵢ = E(Mᵢ, H(i−1)) ⊕ H(i−1)

• 訊息區塊 Mᵢ 扮演區塊密碼的金鑰。
• 鏈接值 H(i−1) 扮演它的明文區塊。

只要區塊密碼是安全的，所得的壓縮函式也是安全的，並具備碰撞與原像抗性。

少了最後 XOR 前一個鏈接值（⊕ H(i−1)），Davies–Meyer 會不安全——你可以用區塊密碼的解密函式從新鏈接值反推回前一個，把它反轉。

Hᵢ = E(Mᵢ, H(i−1)) ⊕ H(i−1)
   = E(Mᵢ, D(Mᵢ, 0)) ⊕ D(Mᵢ, 0)
   = 0 ⊕ D(Mᵢ, 0)
   = D(Mᵢ, 0)
   = H(i−1)

除了 Davies–Meyer 之外還有許多基於區塊密碼的壓縮函式，但它們較不流行——因為更複雜，或是要求訊息區塊與鏈接值等長。

海綿函式：基於置換的雜湊#

經過數十年研究，密碼學家對基於區塊密碼的雜湊技巧已無所不知。但難道沒有更簡單的雜湊方式嗎？

既然雜湊函式不接收秘密金鑰，為什麼還要費事用區塊密碼這種吃金鑰的演算法？

何不用固定金鑰的區塊密碼——也就是單一個置換演算法——來建構雜湊函式？

這種更簡單的雜湊函式就是海綿函式（sponge functions）。它們用單一個置換取代了「壓縮函式 + 區塊密碼」的組合，而且不用區塊密碼把訊息位元與內部狀態混合，只做一次 XOR。

海綿函式不只比 Merkle–Damgård 函式簡單，還更多才多藝。

你會看到它們被用作雜湊函式，也被用作確定性隨機位元產生器、串流密碼、偽隨機函式（第 7 章）與鑑別式密碼（第 8 章）。

最著名的海綿函式是 Keccak，也就是 SHA-3。

運作方式#

1. 把第一個訊息區塊 M₁ 與 H₀（內部狀態的預定初始值，例如全零字串）XOR。訊息區塊全都同樣大小，且小於內部狀態。
2. 用置換 P 把內部狀態變換成同樣大小的另一個值。
3. XOR 區塊 M₂ 再套用 P，接著對 M₃、M₄……重複——這稱為吸收階段（absorbing phase）。
4. 注入完所有訊息區塊後，再套用一次 P，從狀態中抽出一段位元形成雜湊。（若需要更長的雜湊，再套用 P 並抽出一段。）這稱為擠壓階段（squeezing phase）。

安全性與容量#

海綿函式的安全性取決於其內部狀態長度與區塊長度。

若訊息區塊長 r 位元、內部狀態長 w 位元，則有 c = w − r 位元的內部狀態無法被訊息區塊修改。

例如要以 64 位元訊息區塊達到 256 位元安全性，內部狀態應為 w = 2 × 256 + 64 = 576 位元。

安全等級當然也取決於雜湊值的長度 n：

要安全，置換 P 的行為必須像一個隨機置換——沒有統計偏差，也沒有能讓攻擊者預測輸出的數學結構。

與基於壓縮函式的雜湊一樣，海綿函式也會填充訊息，但填充更簡單——因為不需要包含訊息長度。最後一個訊息位元後面只要接一個 1 位元與所需數量的 0 即可。