1985 - 密碼學雜湊函數#

案件摘要#

1985 年前後，密碼學雜湊函數（MD 系列、SHA 系列）成為獨立的密碼學原語：任意長度輸入 → 固定長度「指紋」，要求單向（難找原像）與抗碰撞（難找兩個輸入同指紋）。雜湊函數成為密碼學的萬用膠水：簽章先雜湊、密碼儲存、訊息認證、區塊鏈。2004 年王小雲團隊破 MD5、2005 年破 SHA-1 的理論攻擊——催生了 SHA-2/SHA-3 與「抗碰撞結構」的科學化。

前因 -- 為什麼會有這個案子#

1980 年代密碼學的多個需求匯聚：

簽章先雜湊：RSA 簽章（見 1977-RSA.md）簽長文件太慢——先壓縮成固定長度摘要再簽
密碼儲存：Unix 系統的 /etc/passwd——不存密碼，存雜湊
訊息認證：Carter–Wegman 的 MAC（見 1979-CarterWegman通用雜湊.md）需要雜湊
Merkle 樹：Merkle（1988）的樹狀簽章——雜湊的層級結構

雜湊的數學要求： - 單向性（preimage resistance）：給定 \(h\) ，求 \(m\) 使 \(H(m) = h\) 難 - 第二原像抗性：給定 \(m\) ，求 \(m' \ne m\) 使 \(H(m') = H(m)\) 難 - 抗碰撞（collision resistance）：求任何 \(m \ne m'\) 使 \(H(m) = H(m')\) 難

線索與推理 -- 數學式、程式、理論#

Merkle–Damgård 結構#

雜湊的標準結構（Merkle 與 Damgård 1989 各自證明）：把長訊息切成區塊，迭代壓縮：

\[ h_0 = IV, \quad h_i = f(h_{i-1}, m_i), \quad H(m) = h_n \]

定理（Merkle–Damgård）：若壓縮函數 \(f\) 抗碰撞，則迭代雜湊 \(H\) 抗碰撞。

證明骨架：若 \(H(m) = H(m')\) 且 \(m \ne m'\) ，沿迭代回溯，必然在某輪出現 \(f(h, m_i) = f(h', m_i')\) 的碰撞——違反 \(f\) 的抗碰撞性。 \(\blacksquare\)

於是：設計抗碰撞的固定長度壓縮函數 \(f\) ，就能構造任意長度的抗碰撞雜湊——從小到大的構造定理。

生日攻擊：抗碰撞的下界#

生日悖論： \(n\) 個人中兩人生日相同的機率約 \(1 - e^{-n^2/2/365}\) 。雜湊的版本： \(2^{b/2}\) 個隨機輸入中，出現碰撞的機率約 1/2（ \(b\) 是雜湊長度）：

\[ P(\text{碰撞}) \approx 1 - e^{-2^b / 2^b} \implies \text{找碰撞需 } O(2^{b/2}) \text{ 次運算} \]

於是： \(b\) 位元雜湊的抗碰撞強度只有 \(2^{b/2}\) ——128 位元雜湊的碰撞強度 = 64 位元（不夠）。抗碰撞需要 256 位元以上——SHA-256 的由來。

程式碼：生日攻擊與雜湊#

import random, hashlib, math

# 生日攻擊：32 位元截斷雜湊的碰撞（O(2^16) 次即可找到）
def truncated_hash(msg, bits=32):
    return int.from_bytes(hashlib.md5(msg).digest(), 'big') % (2**bits)

random.seed(42)
seen = {}
collisions = 0
N = 100000
for i in range(N):
    h = truncated_hash(str(i).encode())
    if h in seen:
        collisions += 1
        if collisions == 1:
            print(f"碰撞：{seen[h]} 與 {i}（雜湊值 {h}）")
    seen[h] = i
print(f"N={N} 次中 {collisions} 次碰撞（生日悖論預測約 {N*N // 2**33} 次）")

# 完整 MD5（128 位元）與 SHA-256（256 位元）
print(hashlib.md5(b"hello").hexdigest())
print(hashlib.sha256(b"hello").hexdigest())

# 單向性：給定雜湊值，找原像需 O(2^128)——不可行

攻擊的歷史：王小雲的破譯#

2004 年，山東大學王小雲團隊發表MD5 的碰撞攻擊：構造兩個不同文件同 MD5 摘要——不是生日攻擊的 \(2^{64}\) ，而是分析性攻擊的 \(2^{39}\) 級（數小時電腦時間）。

推理（差分攻擊，Biham–Shamir 差分分析的延伸，見 1977-DES.md）：研究「輸入差異 → 內部狀態差異」的傳播路徑，選高機率差分特徵，修改訊息使差異被壓縮函數「吸收」——構造性碰撞。

2005 年：SHA-1 的理論攻擊（ \(2^{63}\) ，低於生日界 \(2^{80}\) ）。2017 年：Google 的 SHAttered 攻擊實際構造 SHA-1 碰撞。

對策： - SHA-2（2001）：更長輸出（256/512 位元）、更強的設計 - SHA-3（2015）：Keccak——海綿結構（sponge construction，非 Merkle–Damgård）：吸收與擠出兩階段，結構性免疫差分攻擊 - 抗碰撞的標準：256 位元以上、無已知分析攻擊

偵探筆記：王小雲的破譯是「差分攻擊的構造化」——不是隨機碰撞（生日攻擊），而是沿差分路徑構造碰撞。與 Enigma 破譯（見 1932-Rejewski破譯Enigma.md）同源：利用內部結構的代數/差分特性。雜湊函數的「結構洩漏」成為攻擊面——SHA-3 的海綿結構正是免疫這個攻擊面的結構性設計。

Merkle 樹：雜湊的層級結構#

Merkle（1988）的樹狀結構——區塊鏈的基礎（見 2016-區塊鏈密碼學.md）：

\[ \text{根} = H(H(m_1, m_2), H(m_3, m_4)) \]

性質：驗證 \(m_i\) 在樹中只需 \(O(\log n)\) 個兄弟雜湊——稀疏驗證。SPV（簡單支付驗證）、證據驗證、證明系統的基礎。

結案 -- 後果與影響#

密碼學的萬用膠水：簽章先雜湊、密碼儲存、HMAC、區塊鏈——雜湊是現代密碼學的基礎設施。
王小雲的破譯：MD5/SHA-1 的死亡——「分析性攻擊」證明 Merkle–Damgård 結構的脆弱面。
SHA-2/SHA-3：256 位元 + 海綿結構——抗碰撞的科學化。
生日攻擊的教訓：抗碰撞強度 \(2^{b/2}\) ——金鑰/雜湊長度的設計準則。
Merkle 樹：區塊鏈、SPV、零知識證明的層級結構基礎。
實戰陷阱：密碼儲存需要加鹽 + 慢雜湊（bcrypt、Argon2）——快速雜湊（SHA-256）反而易被字典攻擊。

關鍵人物與文獻#

Ralph Merkle：Merkle–Damgård 結構、Merkle 樹 (1988)
Ivan Damgård：Merkle–Damgård 定理 (1989)
王小雲（1966–）：MD5 破譯 (2004)、SHA-1 理論攻擊 (2005)
Biham & Shamir：差分分析 (1991)——王小雲攻擊的基礎
NIST：SHA-2 (2001)、SHA-3/Keccak (2015)
交叉參照：1977-RSA.md、1979-CarterWegman通用雜湊.md、2016-區塊鏈密碼學.md、1977-DES.md