跳轉到

5.3 Merkle-Damgård 結構與長度延伸攻擊#

概念說明#

MD5、SHA-1、SHA-2 皆採 Merkle–Damgård（MD）結構：把訊息切成固定大小區塊，以一個小的壓縮函數 f 反覆摺疊：

H_0 = IV（固定初始值）
H_i = f(H_{i-1}, M_i)     對每個訊息區塊
H(M) = H_n（最後區塊含長度填充 padding）

填充規則：補上 1、若干個 0、最後一個 64 位元原始長度，使總長為區塊的倍數。

MD 結構的美妙之處在 Merkle–Damgård 證明：若壓縮函數 f 抗碰撞，則整體雜湊抗碰撞——把「構造整個抗碰撞雜湊」化約為「構造一個抗碰撞的小函數」。其代價是輸出「中間狀態可直接當作鏈的接續點」，這正是長度延伸攻擊的根源。

長度延伸攻擊（length extension attack）#

攻擊場景：某 API 用 MAC = H(secret || message) 驗證請求（看似安全：不知道 secret 就無法算 MAC）。

攻擊：知道 H(secret || msg) 與 len(secret) || len(msg) 的攻擊者，可以不須知道 secret，把已有的雜湊內部狀態當成 H_0，接著計算：

H(secret || msg || padding || 追加資料)   ← 延伸後的合法 MAC

因為 MD 填充後的中間狀態就是「繼續雜湊的起點」。攻擊者可任意追加 &admin=true 之類內容並附上有效 MAC，伺服器會照單全收。MD5、SHA-1、SHA-256 皆受影響。

防禦：不要用 H(secret || msg)；改用 HMAC（6.1 節），其雙層結構（H(K⊕opad || H(K⊕ipad || msg))）切斷了「狀態可外接」的通路。

Python 實作#

import hashlib

SECRET = b"top-secret-key"

# 受害伺服器的驗證邏輯（有漏洞）
def mac(msg): return hashlib.sha256(SECRET + msg).digest()

msg = b"user=guest"
tag = mac(msg)

# --- 概念示範：MD 填充讓狀態可以「外接」 ---
def md_pad(msg: bytes) -> bytes:
    """SHA-256 的填充：0x80、零、最後 8 bytes 為位元長度"""
    return msg + b"\x80" + b"\x00" * ((55 - len(msg)) % 64) \
           + (len(msg) * 8).to_bytes(8, "big")

h = hashlib.sha256(SECRET + msg)          # 伺服器算出合法 MAC
print("合法 MAC:", h.hexdigest()[:32])

# 攻擊者雖不知 SECRET，但只要知道 len(SECRET)，
# 就能算出 msg 後的填充，並把「延伸訊息」交給伺服器：
extension = md_pad(b"?" * len(SECRET) + msg) + b"&admin=true"
print("延伸訊息結構:", extension[6:] if len(SECRET) == 6 else extension)
print("攻擊工具（hashpumpy）可對延伸部分計算出接續的合法 MAC")

# --- 正確做法：HMAC ---
import hmac
good = hmac.new(SECRET, msg, hashlib.sha256).digest()
print("HMAC:", good.hex()[:32])
assert hmac.compare_digest(good, hmac.new(SECRET, msg, hashlib.sha256).digest())

（完整攻擊可用 hashpumpy 套件實作：它從既有 (message, mac) 與猜測的 secret 長度，產生延伸訊息與新 MAC——建議在本地測試環境練習。）

安全性分析#

  • MD 結構的其他副作用：多碰撞攻擊（找 2^k 個碰撞比想像便宜）、Joux 的串接削弱（串接 MD5+SHA1 的安全度只略高於單一較弱者，低於直覺）。
  • 結構性解法：SHA-3 的海綿結構天生免疫於長度延伸；HMAC 對任何底層迭代雜湊都有嚴格證明的安全性。
  • 工程教訓（呼應 9.3 節）：漏洞往往不在演算法本身，而在「把原語組合起來」的方式。H(secret||msg) 在密碼學直覺上「好像可以」，實際上是可遠程利用的 Web 漏洞（多個 CTF 與真實滲透案例）。

練習#

  1. 手動計算：長度 55 位元組的訊息在 SHA-256 下的填充（1、幾個 0、64 位元長度），並解釋為何 55 是「剛好裝滿最後一個區塊前」的臨界長度。
  2. 安裝 hashpumpy（或手寫延伸邏輯），在本機對一個用 sha256(SECRET||msg) 的模擬 API 執行長度延伸攻擊，追加 &admin=true，觀察驗證通過。
  3. 解釋為什麼 HMAC 的結構（外層先雜湊 opad）使長度延伸失效——攻擊者拿不到哪個中間狀態？