Featured image of post 雜湊函數的抗碰撞性與 SHA-3 (Keccak)
電腦科學 Algorithm

雜湊函數的抗碰撞性與 SHA-3 (Keccak)

海綿結構：一種新的密碼學雜湊機制。

現代數位社會中，「密碼學雜湊函數」被廣泛應用，作為確認資料未遭篡改、以及確保通訊對象為真實意圖對象的基礎技術。從密碼的儲存、數位簽章、區塊鏈，到 SSL/TLS 的加密通訊，其應用範圍十分廣泛。本文將從密碼學雜湊函數所需具備的要件開始，深入探討過去曾是標準的 MD5 與 SHA-1 是如何被攻破的、目前主流 SHA-2 的結構性問題，以及經過 NIST 競賽後成為新世代標準的 SHA-3 (Keccak) 所帶來的劃時代「海綿結構」並深入解說。

什麼是密碼學雜湊函數？

雜湊函數是一種將任意長度的資料（訊息）作為輸入，並輸出固定長度資料（雜湊值、訊息摘要）的函數。用於密碼學用途的雜湊函數，主要必須具備以下三種強大的特性：

  1. 抗原像性 (Pre-image Resistance) 當給定一個雜湊值 $h$ 時，要找到滿足 $H(m) = h$ 的原始訊息 $m$ 是極度困難的。如果不滿足這一點，例如被雜湊化的密碼就能夠被反推出原始密碼。
  2. 抗第二原像性 (Second Pre-image Resistance) 當給定一個訊息 $m_1$ 時，要找到另一個滿足 $H(m_1) = H(m_2)$ 且 $m_1 \neq m_2$ 的訊息 $m_2$ 是困難的。
  3. 抗碰撞性 (Collision Resistance) 要找到任意兩個不同的訊息 $m_1, m_2$，使得 $H(m_1) = H(m_2)$ 是困難的。這是為了防止惡意攻擊者同時建立擁有相同雜湊值的「無害檔案」與「惡意檔案」並進行掉包攻擊（例如偽造數位簽章）所不可或缺的特性。

由於一種稱為生日攻擊 (Birthday Attack) 的數學性質，要找到輸出為 $N$ 位元的雜湊函數的碰撞，其計算量與 $2^{N/2}$ 成正比。因此，為了維持實用上的抗碰撞性，需要有足夠長度的雜湊輸出。

MD5 與 SHA-1 的崩壞：為什麼過去的雜湊函數會被攻破？

過去在網際網路上最被廣泛使用的雜湊函數，包含了由 Ronald Rivest 設計的 MD5（128 位元輸出），以及由 NSA（美國國家安全局）設計並由 NIST 標準化的 SHA-1（160 位元輸出）。然而，現在它們已被標示為「不安全」並遭棄用。

MD5 在 2004 年被中國研究人員發表了可在實用時間內發現碰撞的攻擊手法，實質上已經崩壞。此外，關於 SHA-1，在 2005 年也被指出了理論上的脆弱性，而到了 2017 年，Google 與 CWI Amsterdam 的研究團隊更公開了名為「SHAttered」的實際碰撞案例。他們成功產生了兩個具有完全相同 SHA-1 雜湊值的不同 PDF 檔案。

這些演算法被攻破的根本原因，在於其內部所使用的壓縮函數設計存在弱點（例如：訊息的差異容易在內部狀態中相互抵消的結構）。這使得攻擊者能夠以比暴力破解少得多的計算量來找出碰撞。

SHA-2 與 Merkle-Damgård 結構的極限

在 MD5 與 SHA-1 遭到危及之後，輸出長度更長（256 位元、512 位元等）且結構獲得強化的 SHA-2 成為了現在的主流。然而，SHA-2 在設計上存在著潛在的隱憂。那就是它採用了與 MD5 及 SHA-1 相同的 Merkle-Damgård 結構。

在 Merkle-Damgård 結構中，會將輸入訊息分割成固定大小的區塊，並將初始值 (IV) 與第一個區塊輸入壓縮函數中以產生中間狀態。之後，再將該中間狀態與下一個區塊再次輸入壓縮函數，如此連鎖地重複進行處理。

  graph LR
    IV["初始值 (IV)"] --> F1["壓縮函數"]
    M1["訊息區塊 1"] --> F1
    F1 --> F2["壓縮函數"]
    M2["訊息區塊 2"] --> F2
    F2 --> F3["壓縮函數"]
    M3["訊息區塊 3"] --> F3
    F3 --> Out["雜湊值"]

這種結構雖然多年來備受信任，但存在著被稱為「長度延伸攻擊 (Length Extension Attack)」的已知漏洞。這是指當攻擊者知道某個訊息 $M$ 的雜湊值 $H(M)$ 以及 $M$ 的長度時，即使不知道 $M$ 的內容，也能輕易計算出在附加了額外資料 $X$ 後的 $M || X$ 的雜湊值 $H(M || X)$。這個問題在訊息鑑別碼 (MAC) 的簡單構造中會帶來嚴重的安全風險（為了防止這種情況，後來設計出了 HMAC 等機制）。

SHA-3 競賽與 Keccak 的勝利

由於對 SHA-2 安全性的擔憂（主要是因為結構上的相似性）日益增加，NIST 在 2007 年展開了公開競賽，以制定新世代的雜湊函數標準「SHA-3」。來自世界各地的 64 件投稿，經過數年嚴格的密碼分析考驗與效能評估後，在 2012 年由 Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche 等人所設計的 Keccak 脫穎而出，成為最終勝出者。

Keccak 能被選為 SHA-3 的最大理由，在於它採用了一種名為 「海綿結構 (Sponge Construction)」 的全新典範，這與 MD5、SHA-1、SHA-2 所依賴的 Merkle-Damgård 結構截然不同。

海綿結構的數學與設計革新性

海綿結構，顧名思義，是由「吸收 (Absorbing)」與「擠出 (Squeezing)」兩個階段所構成。

內部狀態的構成：位元率 (r) 與容量 (c)

Keccak 的內部狀態被表示為一個巨大的位元陣列（在 SHA-3 中為 1600 位元）。這個內部狀態被分割為用於資料輸入輸出的 位元率 (Rate, $r$) 部分，以及絕對不會直接暴露於外部的 容量 (Capacity, $c$) 部分（總狀態長度 $b = r + c$）。

容量 $c$ 作為擔綱安全核心的「秘密黑盒子」來運作。防止輸出碰撞的安全強度，大致上取決於 $c / 2$。例如，在 SHA-3-256 中設定了 $c = 512 位元，提供了 256 位元的安全層級。

吸收階段 (Absorbing Phase)

  1. 將輸入訊息分割為每塊 $r$ 位元的區塊（包含填充）。
  2. 將第一個訊息區塊與內部狀態的 $r$ 位元部分進行 XOR（互斥或）運算。
  3. 對整體（$r + c$ 位元）套用非線性的 置換函數 (Permutation Function $f$)，劇烈地攪拌內部狀態。
  4. 再將下一個訊息區塊與 $r$ 位元部分進行 XOR 運算，並套用函數 $f$。重複此步驟直到所有訊息區塊處理完畢。

擠出階段 (Squeezing Phase)

  1. 吸收完成後，取出內部狀態的 $r$ 位元部分作為輸出的一部分。
  2. 若需要更多輸出，則再次套用函數 $f$ 以更新內部狀態，並取出新的 $r$ 位元。重複此步驟直到達到所需的輸出長度（例如 256 位元或 512 位元）。
  graph LR
    subgraph 吸收階段
    M1["訊息區塊 1 (r bit)"] --> XOR1("XOR")
    XOR1 --> F1["置換函數 f"]
    M2["訊息區塊 2 (r bit)"] --> XOR2("XOR")
    F1 --> XOR2
    XOR2 --> F2["置換函數 f"]
    end
    
    subgraph 擠出階段
    F2 --> Out1["輸出 1 (r bit)"]
    F2 --> F3["置換函數 f"]
    F3 --> Out2["輸出 2 (r bit)"]
    end

為什麼海綿結構更為優越？

  1. 對長度延伸攻擊的抗性: 由於內部狀態的一部分（容量 $c$）始終被隱藏，攻擊者無法還原整個內部狀態，從根本上讓 Merkle-Damgård 結構中脆弱的長度延伸攻擊失效。
  2. 高度的彈性: 藉由改變 $r$ 與 $c$ 的比例，可以動態調整效能（增大 $r$）與安全性（增大 $c$）。此外，只要持續進行擠出階段，就能無限產生亂數序列，因此 SHA-3 不僅僅是一個雜湊函數，它還具備作為偽亂數產生器 (PRNG)、串流密碼、訊息鑑別碼 (MAC) 等各種密碼學基元來應用的泛用性。
  3. 硬體實作的效率性: Keccak 的置換函數 $f$ 僅由位元等級的邏輯運算 (XOR, AND, NOT) 與旋轉所構成，不需要複雜的算術運算（如加法等）。這帶來了巨大的優勢，特別是在硬體（ASIC 或 FPGA）實作上，能以極高的速度且低功耗的方式運作。

總結

雜湊函數的歷史，就是一部與密碼分析不斷對抗的歷史。MD5 與 SHA-1 的落敗，可以說是內部壓縮函數的弱點與計算機效能演進所帶來的必然結果。儘管 SHA-2 目前仍被安全地使用著，但它背負著起因於 Merkle-Damgård 結構的設計限制。

作為對這些問題的根本解答而登場的 SHA-3 (Keccak) 與海綿結構，並非只是單純的演算法更新，而是重新定義了密碼學雜湊架構本身的重大突破。其彈性且堅固的設計，從未來的 IoT 裝置到放眼量子電腦時代的先進密碼系統，將會持續作為確保數位信任的重要基石而運作。

comments powered by Disqus