哈希函数 — SHA-256 状态机与海绵结构

日期: 2026-11-13 方向: 密码学 / 经典原语 阶段: Phase 4 - 经典密码学 (Day 195-208) 标签: #密码学 #哈希函数 #SHA256 #Keccak #MerkleDamgard

---

今日目标

---

一、哈希函数性质与设计目标

1.1 三大安全性质

生日攻击: 在 $\sqrt{2^n}$ 次查询有 50% 概率发现碰撞。SHA-256 的抗碰撞强度 = 128 bit（不是 256 bit）。

1.2 随机预言机模型 (ROM)

证明协议时常假设 $H$ 是真随机函数。理想但不可实例化（Canetti-Goldreich-Halevi 2004 ROM 不可证伪）。但 ROM 仍是密码学工程的实用启发式。

---

二、SHA-256 算法详解

2.1 高层结构 — Merkle-Damgård

M → 填充 → 切成 512-bit 块 M1, M2, ..., Mn
H0 = IV (8 个 32-bit 常量)
for i in 1..n:
    H_i = compress(H_{i-1}, M_i)
output = H_n

2.2 填充（Padding）

原始 M 长度 L (bit)
M' = M || 1 || 0...0 || L_64bit_BigEndian
长度: 是 512 的整数倍

填充至 $L \equiv 448 \pmod{512}$，再追加 64-bit 长度。

2.3 消息扩展 (Message Schedule)

每 512-bit 块切成 16 个 32-bit word $W_0..W_{15}$，扩展到 $W_0..W_{63}$:

$$W_t = \sigma_1(W_{t-2}) + W_{t-7} + \sigma_0(W_{t-15}) + W_{t-16} \pmod{2^{32}}$$

其中: $$\sigma_0(x) = \text{ROTR}^7(x) \oplus \text{ROTR}^{18}(x) \oplus \text{SHR}^3(x)$$ $$\sigma_1(x) = \text{ROTR}^{17}(x) \oplus \text{ROTR}^{19}(x) \oplus \text{SHR}^{10}(x)$$

2.4 压缩函数 (64 轮)

工作变量 $a, b, c, d, e, f, g, h \leftarrow H_0..H_7$.

每轮: $$T_1 = h + \Sigma_1(e) + \text{Ch}(e,f,g) + K_t + W_t$$ $$T_2 = \Sigma_0(a) + \text{Maj}(a,b,c)$$ $$h = g, g = f, f = e, e = d + T_1, d = c, c = b, b = a, a = T_1 + T_2$$

布尔函数:

• $\text{Ch}(x,y,z) = (x \land y) \oplus (\lnot x \land z)$ — 选择
• $\text{Maj}(x,y,z) = (x \land y) \oplus (x \land z) \oplus (y \land z)$ — 多数
• $\Sigma_0(x) = \text{ROTR}^2 \oplus \text{ROTR}^{13} \oplus \text{ROTR}^{22}$
• $\Sigma_1(x) = \text{ROTR}^6 \oplus \text{ROTR}^{11} \oplus \text{ROTR}^{25}$

常量: $K_0..K_{63}$ 是前 64 个素数立方根的小数部分 × $2^{32}$。$H_0..H_7$ 是前 8 个素数平方根的小数部分。

最后: $H_i = H_{i-1} + (a, b, ..., h) \pmod{2^{32}}$（Davies-Meyer 结构防止 fixed point）。

2.5 Davies-Meyer 反馈

压缩函数 $\text{compress}(H, M) = E_M(H) + H$，其中 $E_M$ 是用 $M$ 作密钥的"块加密"。这种 feedback 防止：若没有 $+H$，给定固定点 $E_M(H) = H$ 攻击者可任意延展消息。

---

三、Merkle-Damgård 的弱点 — 长度扩展攻击

3.1 攻击场景

服务器使用 $\text{MAC}(K, M) = H(K | M)$ 验证消息。攻击者知道 $\text{MAC}(K, M)$ 和 $|M|$（不需 $M$），可计算: $$H(K | M | \text{pad} | M') = \text{compress}(H(K|M), M' | \text{pad}_2)$$

即用泄漏的 $H(K|M)$ 作为内部状态继续压缩。

3.2 真实事件 — Flickr API (2009)

Flickr 用 $\text{md5}(\text{secret} | \text{params})$ 作签名。Slavin & Plumb 演示长度扩展攻击 → 任意 API 调用伪造。

3.3 防御

• HMAC: $\text{HMAC}(K, M) = H((K \oplus \text{opad}) | H((K \oplus \text{ipad}) | M))$ — 双层嵌套切断状态延展
• SHA-512/256, SHA-3: 截断或海绵结构天然抗长度扩展
• Keyed BLAKE2: 内置密钥模式

---

四、Keccak / SHA-3 — 海绵结构 (Sponge)

4.1 设计哲学

NIST 2007 SHA-3 竞赛，2012 选定 Keccak（Bertoni-Daemen-Peeters-Van Assche）。原因:

• 完全不同于 MD5/SHA-1/SHA-2 家族（设计多样性）
• 海绵结构无长度扩展
• 同一函数支持多输出长度（SHAKE）

4.2 海绵 (Sponge) 构造

状态宽度 b = r + c (rate + capacity)
吸收 (Absorb): for each m_i: state[:r] ^= m_i; state = f(state)
挤出 (Squeeze): for each output block: emit state[:r]; state = f(state)

安全 bound: 抗碰撞 $\min(2^{n/2}, 2^{c/2})$，抗原像 $\min(2^n, 2^c)$。

4.3 Keccak-f[1600] 置换

5×5×64 状态。每轮 5 步: $\theta, \rho, \pi, \chi, \iota$。共 24 轮。

SHA-3-256 参数: $r = 1088, c = 512, n = 256$。

4.4 Ethereum 中的 "Keccak-256" 不是 SHA3-256

• SHA3-256 (NIST): padding 0x06...0x80
• Keccak-256 (Ethereum): padding 0x01...0x80（SHA-3 标准前的草案版本）

以太坊在 SHA-3 标准化前已发布，Vitalik 决定保留 Keccak 原始 padding，导致 Solidity keccak256 与 NIST SHA-3 哈希不同。

---

五、Blake 家族

5.1 Blake2

设计目标: 比 MD5 快 + 比 SHA-3 简单。基于 ChaCha 轮函数。

• Blake2b: 64-bit 优化，输出最多 512 bit
• Blake2s: 32-bit 优化，输出最多 256 bit
• 内置 keyed 模式（无需 HMAC 包装）、个性化、并行树模式

5.2 Blake3 (2020)

• 树形并行：天然多线程加速
• 极限性能: ~7 GB/s 单核 (AVX-512)
• 构造可验证流（XOF）+ KDF + MAC 一体
• 用 Bao 协议实现增量验证

---

六、代码实现 — sha256.py

"""
sha256.py - 完整 SHA-256 实现（教学用）
- 不依赖 hashlib
- 完整状态机暴露
- 演示长度扩展攻击
"""
from __future__ import annotations
from typing import List

# SHA-256 常量
K = [
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
    0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
    0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
    0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
    0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
    0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
    0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
    0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2,
]

H0 = [
    0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a,
    0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19,
]

MASK = 0xffffffff

def rotr(x: int, n: int) -> int:
    return ((x >> n) | (x << (32 - n))) & MASK

def shr(x: int, n: int) -> int:
    return (x >> n) & MASK

def big_sigma0(x): return rotr(x, 2) ^ rotr(x, 13) ^ rotr(x, 22)
def big_sigma1(x): return rotr(x, 6) ^ rotr(x, 11) ^ rotr(x, 25)
def small_sigma0(x): return rotr(x, 7) ^ rotr(x, 18) ^ shr(x, 3)
def small_sigma1(x): return rotr(x, 17) ^ rotr(x, 19) ^ shr(x, 10)
def ch(x, y, z): return (x & y) ^ ((~x) & z) & MASK
def maj(x, y, z): return (x & y) ^ (x & z) ^ (y & z)

def pad(msg: bytes) -> bytes:
    L = len(msg) * 8
    msg = msg + b'\x80'
    while (len(msg) % 64) != 56:
        msg += b'\x00'
    msg += L.to_bytes(8, 'big')
    return msg

def compress(H: List[int], block: bytes) -> List[int]:
    """SHA-256 single-block compression. Davies-Meyer.
    Returns new H state.
    """
    assert len(block) == 64
    W = [int.from_bytes(block[i*4:(i+1)*4], 'big') for i in range(16)]
    for t in range(16, 64):
        w = (small_sigma1(W[t-2]) + W[t-7] + small_sigma0(W[t-15]) + W[t-16]) & MASK
        W.append(w)
    a, b, c, d, e, f, g, h = H
    for t in range(64):
        T1 = (h + big_sigma1(e) + ch(e, f, g) + K[t] + W[t]) & MASK
        T2 = (big_sigma0(a) + maj(a, b, c)) & MASK
        h = g
        g = f
        f = e
        e = (d + T1) & MASK
        d = c
        c = b
        b = a
        a = (T1 + T2) & MASK
    return [(x + y) & MASK for x, y in zip(H, [a, b, c, d, e, f, g, h])]

def sha256(msg: bytes) -> bytes:
    msg = pad(msg)
    H = list(H0)
    for i in range(0, len(msg), 64):
        H = compress(H, msg[i:i+64])
    return b''.join(h.to_bytes(4, 'big') for h in H)

# --------------------------- 长度扩展攻击 ---------------------------

def length_extension_attack(known_hash: bytes, known_msg_len: int, suffix: bytes) -> tuple[bytes, bytes]:
    """
    给定 H = sha256(secret || msg)，secret 长度已知，
    扩展 suffix → 计算 H' = sha256(secret || msg || pad || suffix) 而无需知道 secret。
    
    返回 (forged_msg_tail, forged_hash)，调用者把 secret||msg||forged_tail 提交给服务器。
    """
    # 1. 把已知 hash 当作压缩函数的中间状态
    H_state = [int.from_bytes(known_hash[i*4:(i+1)*4], 'big') for i in range(8)]

    # 2. 重建 secret||msg 的填充（攻击者只需要知道总长度）
    total_len_bits = known_msg_len * 8
    pad_bytes = b'\x80'
    while ((known_msg_len + len(pad_bytes)) % 64) != 56:
        pad_bytes += b'\x00'
    pad_bytes += total_len_bits.to_bytes(8, 'big')

    # 3. 现在以 H_state 作为初始状态，对 suffix 继续 SHA-256
    fake_msg_len = known_msg_len + len(pad_bytes) + len(suffix)
    suffix_padded = suffix + b'\x80'
    while ((fake_msg_len + (len(suffix_padded) - len(suffix))) % 64) != 56:
        suffix_padded += b'\x00'
    suffix_padded += (fake_msg_len * 8).to_bytes(8, 'big')

    H = H_state
    for i in range(0, len(suffix_padded), 64):
        H = compress(H, suffix_padded[i:i+64])

    forged_hash = b''.join(h.to_bytes(4, 'big') for h in H)
    forged_tail = pad_bytes + suffix  # 服务器看到的: secret || msg || forged_tail
    return forged_tail, forged_hash

# --------------------------- 自检 ---------------------------

if __name__ == "__main__":
    import hashlib

    # 1. NIST 测试向量
    assert sha256(b"abc").hex() == hashlib.sha256(b"abc").hexdigest()
    assert sha256(b"").hex() == hashlib.sha256(b"").hexdigest()
    long_msg = b"a" * 1000
    assert sha256(long_msg).hex() == hashlib.sha256(long_msg).hexdigest()
    print("SHA-256 test vectors: PASS")

    # 2. 演示长度扩展攻击
    secret = b"super_secret_key_42"
    msg = b"&action=read&user=alice"
    legit_mac = sha256(secret + msg)
    print(f"Legit MAC: {legit_mac.hex()}")

    # 攻击者只知道 legit_mac 和 |secret| = 19
    suffix = b"&action=delete&user=admin"
    forged_tail, forged_mac = length_extension_attack(legit_mac, len(secret) + len(msg), suffix)

    # 验证伪造的 MAC 确实有效
    full_msg = msg + forged_tail
    actual = sha256(secret + full_msg)
    assert actual == forged_mac
    print(f"Length-extension forgery succeeded! New MAC: {forged_mac.hex()}")
    print(f"This is why you must use HMAC, not H(K||M).")

---

七、真实漏洞 / 事件

---

八、协议应用 — Web3 中的哈希

为什么 Bitcoin 用双哈希 SHA-256(SHA-256(x)): Satoshi 担心潜在长度扩展攻击和已知 SHA-256 弱点。事实上对单数据双哈希仅是保险，并不严格必要。

为什么 ZK 项目用 Poseidon: SHA-256 在 R1CS 电路中需要 ~25,000 约束/哈希。Poseidon 仅需 ~200 约束 → ZK 证明速度提升 100×。

---

九、常见陷阱

1. H(K || M) 作 MAC → 长度扩展攻击。永远用 HMAC 或现代构造（KMAC/Blake2 keyed）
2. SHA-1 / MD5 仍出现在新代码中 — 已彻底破解，禁用
3. 混用 keccak256 与 SHA3-256 — Solidity 用前者，Python hashlib.sha3_256 用后者，相同输入输出不同
4. Padding ambiguity — 密码学协议中拼接两段输入要分隔/长度前缀，否则 $H(A | B) = H(A' | B')$ 可能成立
5. 截断的 hash — SHA-512/256 安全（Davies-Meyer + 截断），但 SHA-256 截断到 128 bit 抗碰撞强度仅 64 bit
6. 错误地用 hash 做 KDF — 单次 hash 不是 KDF。用 HKDF / scrypt / Argon2
7. 生日界限 — 在区块链上，UTXO ID 只用 96 bit 哈希 → $2^{48}$ 操作可碰撞，导致重组攻击

---

十、关键速查

哈希家族对比

哈希性质适用

---

十一、面试题

Q1: Solidity keccak256 和 Python hashlib.sha3_256 输出为什么不同？ A: 两者都是 Keccak-f[1600] 海绵，但填充字节不同：Keccak（以太坊采用）用 0x01...0x80，NIST SHA-3 标准化时改成 0x06...0x80。Vitalik 在以太坊发布前选定原始 Keccak，定型后没改。要在 Python 中复现 Solidity 哈希，用 pysha3 的 keccak_256 或 eth_utils.keccak。

Q2: 为什么 ZK 项目几乎都用 Poseidon 而不是 SHA-256？ A: ZK 电路中算力以"约束数"度量。SHA-256 含大量按位运算（XOR/AND/ROTR），在域算术电路中每个 bit-op ≈ 30+ 约束 → 单次 SHA-256 ~25k 约束。Poseidon 设计为域元素直接操作（power S-box + MDS 矩阵），仅 ~200 约束。Plonk/Halo2 中证明时间几乎与约束数线性相关。

Q3: 长度扩展攻击在 Web3 实际威胁吗？ A: 直接威胁低（Solidity keccak256 是 Sponge 结构，免疫）。但在跨链桥 / Oracle 签名中，若用 sha256(secret || msg) 作 commitment 可能引入。所有现代签名（ECDSA/EdDSA/BLS）内部用 hash-to-scalar，不直接受影响。

Q4: SHA-256 后量子安全吗？ A: Grover 算法把对称/哈希原像复杂度从 $2^n$ 减到 $2^{n/2}$ → SHA-256 抗原像后量子是 128 bit（仍安全）。抗碰撞仅有 $\sqrt[3]{2^n} = 2^{85}$ 的 Grover-BHT 加速，仍接近 80-128 bit 安全（足够）。NIST PQC 标准仍依赖 SHA-256/SHA-3。

Q5: BTC 用 SHA-256 双哈希的设计合理吗？ A: 防御长度扩展是误解（BTC TxID 的明文不可控）。真实理由：(1) 抗 birthday-by-extension 启发式安全余量；(2) 与早期 hashcash 设计兼容。对地址用 RIPEMD-160(SHA-256(.)) 是为缩短地址（160 bit vs 256 bit），双不同算法防"single algorithm break"。

---

十二、明日预告

Day 197: 哈希应用 — Merkle Tree（结构、证明、批量验证）、HMAC 严谨构造、密码哈希 Argon2/scrypt/bcrypt 的 memory-hard 设计、Sparse Merkle Tree 与 IMT (Indexed Merkle Tree) 在 ZK 协议中的应用。