SHA-3 Keccak 海绵结构：从算法设计到安全性证明

概述

SHA-3（Secure Hash Algorithm 3）是美国国家标准与技术研究院（NIST）于 2015 年 8 月发布的 FIPS 202 标准，其核心算法为 Keccak（发音 /ˈkɛtʃæk/）。与之前的 SHA-1、SHA-2 系列采用的 Merkle-Damgård（MD）结构 根本不同，SHA-3 引入了 海绵结构（Sponge Construction），这是一种全新的哈希函数设计范式。

"海绵"隐喻：算法状态如同一块海绵——先"吸收"输入数据（absorb），再"挤压"输出哈希值（squeeze）。

Keccak 由比利时鲁汶大学的密码学团队设计：Guido Bertoni、Joan Daemen（AES 的共同设计者）、Michaël Peeters、Gilles Van Assche。它在 2012 年 NIST 举办的 SHA-3 竞赛（2007-2012）中从 64 个候选方案中胜出。

海绵结构的理论基础

两阶段模型

海绵结构定义了两个阶段：

阶段 1: 吸收阶段（Absorbing Phase）
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
输入消息 M（经填充后分为 r-bit 的块 P₁‖P₂‖...‖Pₙ）

         P₁         P₂         Pₙ
         │          │          │
         ▼          ▼          ▼
┌────┐      ┌────┐      ┌────┐      ┌────┐
│ S  │ ──▶  │ S  │ ──▶  │ S  │ ──▶  │ S  │
└────┘      └────┘      └────┘      └────┘
  状态₀      状态₁      状态状态ₙ₋₁    状态ₙ

其中: S = r-bit ‖ c-bit (总状态 b = r + c 位)
      ⊕ Pᵢ 仅影响 r-bit 部分                  
      每步后应用置换 f

阶段 2: 挤压阶段（Squeezing Phase）
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
输出 z₁‖z₂‖...（每步输出 r-bit，直到满足输出长度）

┌────┐      ┌────┐      ┌────┐
│ Sₙ │ ──▶  │ S  │ ──▶  │ S  │
└────┘      └────┘      └────┘
   z₁         z₂         z₃

关键参数：

填充规则

Keccak 使用 多速率填充（multi-rate padding）：对消息 M 追加 10*1 模式的填充，使长度为 r 的倍数。填充保证：

• 最后一个 1 总在最后一个块的最后一位
• 填充模式不可逆（不会与消息本身混淆）

安全边界

海绵结构的安全性基于以下定理：

定理（海绵结构安全性）：若底层置换 f 是随机置换（random permutation），则海绵结构抵抗碰撞攻击的安全性为该 min(c/2, 输出长度) 比特，抵抗原像攻击的安全性为 min(c, 输出长度) 比特。

Keccak-f[1600] 置换函数

状态表示

Keccak-f[b] 操作一个 b 位的状态。Keccak 的一个决定性设计选择是使用 b = 1600 位（即 25 个 64 位字：5 × 5 × 64 = 1600）。

状态被组织为一个 5 × 5 × w 的三维数组（w = lane 位数，Keccak 中 w = 64）：

x = 0    x = 1    x = 2    x = 3    x = 4
      ┌────────┬────────┬────────┬────────┬────────┐
y =  0│ Lane(0,0)│ Lane(0,1)│ Lane(0,2)│ Lane(0,3)│ Lane(0,4)│
      ├────────┼────────┼────────┼────────┼────────┤
y =  1│ Lane(1,0)│ Lane(1,1)│ Lane(1,2)│ Lane(1,3)│ Lane(1,4)│
      ├────────┼────────┼────────┼────────┼────────┤
y =  2│ Lane(2,0)│ Lane(2,1)│ Lane(2,2)│ Lane(2,3)│ Lane(2,4)│
      ├────────┼────────┼────────┼────────┼────────┤
y =  3│ Lane(3,0)│ Lane(3,1)│ Lane(3,2)│ Lane(3,3)│ Lane(3,4)│
      ├────────┼────────┼────────┼────────┼────────┤
y =  4│ Lane(4,0)│ Lane(4,1)│ Lane(4,2)│ Lane(4,3)│ Lane(4,4)│
      └────────┴────────┴────────┴────────┴────────┘

z 轴方向形成 lane（64 位），x 轴方向形成 row，y 轴方向形成 sheet， (x, y) 对形成 plane， (x, z) 对形成 slice。

五步轮函数

Keccak-f[b] 每轮由 5 个步骤顺序执行，每步都处理全部 1600 位状态。ARX（Add-Rotate-XOR）风格设计，无 S-box 表查找：

#### 步骤 1: θ（Theta）— 扩散

目的：在 lane 间实现扩散，使每个 bit 影响相邻列。

对每个 (x, z):
    C[x,z] = A[x,0,z] ⊕ A[x,1,z] ⊕ A[x,2,z] ⊕ A[x,3,z] ⊕ A[x,4,z]
    D[x,z] = C[x-1,z] ⊕ C[x+1, z-1]
    A'[x,y,z] = A[x,y,z] ⊕ D[x,z]

θ 是唯一一步跨越不同 y 值的步骤，使同一列的 5 个 lane 互相混合。"z−1" 偏移提供了 z 轴方向的扩散。

#### 步骤 2: ρ（Rho）— 位移

目的：在每个 lane 内部实现比特位移，避免同列中相同的 bit 位置被同时处理。

A'[x,y,z] = A[x,y, (z - (t+1)(t+2)/2) mod w]

其中 t 的范围为 0 到最大满足 (t+1)(t+2)/2 < w 的值。Keccak 的位移常数表保证每个 lane 的偏移量不同。

位移公式的几何意义：对每个 (x, y) 位置，lane 的 bit 右移（循环）一个特定的偏移量，偏移量由 x 和 y 的线性函数决定。这使得后续 χ 步骤作用于不同的 bit 位置。

#### 步骤 3: π（Pi）— 位置置换

目的：重新排列 25 个 lane 的位置，打破 y 方向上的对齐。

A'[x,y,z] = A[x', y', z]
其中 (x', y') = (x + 3y, x) mod 5

π 是一个 (x, y) → (x', y') 坐标变换，等价于 z 轴方向不变，但 5 × 5 平面进行了一个特定的旋转置换。

#### 步骤 4: χ（Chi）— 非线性

目的：Keccak 唯一的非线性来源。没有 χ，整个置换将退化为线性变换（用 GF(2)^b 上的矩阵乘法描述），安全性极大降低。

A'[x,y,z] = A[x,y,z] ⊕ ((¬A[x+1,y,z]) ∧ A[x+2,y,z])

χ 的真值表：

#### 步骤 5: ι（Iota）— 轮常数

目的：消除对称性（否则所有轮次将相同）。

A'[0,0,z] = A[0,0,z] ⊕ RC[i_r]

轮常数 RC[i_r] 仅加到 Lane(0,0) 上，具体值基于 GF(2^8) 上的线性反馈移位寄存器（LFSR）生成。每轮使用不同的轮常数，使得各轮之间不同构（non-isomorphic）。

24 轮迭代

完整的一轮 Keccak-f[1600] 为：Round_i = ι ∘ χ ∘ π ∘ ρ ∘ θ

完整 24 轮：Keccak-f1600 = Round_23 ∘ Round_22 ∘ ... ∘ Round_0 (S)

轮索引范围：0 到 23（共 24 轮）。选择 24 轮的核心目的是为安全提供足够余量：目前最优攻击在第 6-7 轮后开始出现，远高于实际使用的 24 轮。

SHA-3 家族参数

标准哈希输出

可扩展输出函数（XOF）

SHAKE128 和 SHAKE256 是"可扩展输出函数"（Extendable-Output Function, XOF），没有预设的输出长度限制：

填充区别：SHAKE 系列在块的最后追加 1111（而非 SHA-3 的 0110 0001）。

海绵结构的扩展与变体

认证加密

Keccak 团队提出 Ketje 和 Keyak 两个基于海绵的认证加密方案（曾在 CAESAR 竞赛中提交），通过关联数据 AAD（Additional Associated Data）来防止未授权修改。

cSHAKE — 定制化 SHAKE

cSHAKE（customizable SHAKE）通过函数名 N 和定制字符串 S 实现域分离（domain separation）：

cSHAKE128(M, L, N, S) = KECCAK[256](bytepad(encode_string(N) ‖ encode_string(S), 168) ‖ M ‖ 00, L)

NIST SP 800-185 定义了 cSHAKE、KMAC（基于 Keccak 的 MAC）、TupleHash、ParallelHash 等扩展函数。

KMAC

KMAC（KECCAK Message Authentication Code）是基于 Keccak 的 MAC：

KMAC128(K, X, L, S) = cSHAKE128(bytepad(encode_string(K), 168) ‖ X ‖ right_encode(L), L, "KMAC", S)

与 HMAC 不同，KMAC 不需要嵌套哈希，直接利用 Keccak 的单轮海绵结构。

Keccak 与 MD 结构的本质差异

SHA-256 易受此攻击：已知 H(M) 和 |M|，攻击者可以计算 H(M ‖ padding ‖ M')。

SHA-3 天然免疫：H(M) 只输出 r 位状态的一部分，攻击者无法从输出中恢复完整内部状态。

与 SM3 及国密哈希的对比

安全性分析

已知攻击结果

量子安全

• Grover 算法使原像攻击从 2^n 降至 2^(n/2)
• BHT 算法使碰撞攻击从 2^(n/2) 降至 2^(n/3)
• SHA3-256：量子原像安全性 ≈ 128 位，量子碰撞安全性 ≈ 85 位
• SHA3-512：量子原像安全性 ≈ 256 位，量子碰撞安全性 ≈ 171 位

实现与性能

软件性能参考

核心数据（Intel Skylake，优化 C 实现）：

ARM 平台上的实现

ARMv8 不提供 Keccak 原生指令，但现代处理器通过模 64 加法（adds）、循环移位（ror）、异或（eor）指令实现高效 Keccak：

// Keccak 轮函数中 θ 步骤的典型 C 实现（截取）
for (x = 0; x < 5; x++) {
    C[x] = A[x][0] ^ A[x][1] ^ A[x][2] ^ A[x][3] ^ A[x][4];
}
for (x = 0; x < 5; x++) {
    D[x] = C[(x+4)%5] ^ ROTL64(C[(x+1)%5], 1);
}
for (x = 0; x < 5; x++)
    for (y = 0; y < 5; y++)
        A[x][y] ^= D[x];

Python 参考

Python 3.6+ 的 hashlib 是安全的标准化实现：

import hashlib

# SHA3-256 哈希
digest = hashlib.sha3_256(b"Hello, SHA-3").hexdigest()
# SHAKE128（需要指定输出长度）
shake = hashlib.shake_128(b"Hello, SHA-3")
xof_output = shake.hexdigest(32)  # 输出 32 字节（64 个 hex 字符）

# 安全性验证
assert len(bytes.fromhex(digest)) == 32

注意：需注意区分 SHA3 与原始 Keccak。2015 年 NIST 标准化时对填充规则做了微小变更（追加 0110 0001 而非 01），使用 sha3 库可能得到不同结果，标准验证必须使用 hashlib.sha3_*。

总结

SHA-3（Keccak）的引入标志着哈希函数设计范式的根本转变——从迭代式 Merkle-Damgård 结构转向基于海绵结构的通用变换框架。其核心创新在于：

• 海绵结构的灵活性：同一个置换函数，通过调整 r 和 c 的比例，可无缝适配任意安全级别和输出长度
• 天然免疫长度扩展攻击：SHA2 的缺陷在新结构中不复存在
• ARX 设计：无 S-box 表查找，硬件友好，ARM/x86 皆可高效实现
• 对量子安全的容量保留：SHA3-512 在 Grover 算法下仍提供 256 位原像安全性

参考来源

• NIST. (2015). *FIPS 202: SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions*. https://doi.org/10.6028/NIST.FIPS.202
• Bertoni, G., Daemen, J., Peeters, M., Van Assche, G. (2013). *Cryptographic Sponge Functions*. https://keccak.team/files/Keccak-reference-3.0.pdf
• Dinur, I., Dunkelman, O., Shamir, A. (2013). *Collision Attacks on Up to 5 Rounds of SHA-3 Using Generalized Internal Differentials*. FSE 2013.
• NIST. (2020). *SP 800-185: Derived Functions Based on Keccak*. https://doi.org/10.6028/NIST.SP.800-185
• GM/T 0004-2012. 密码杂凑算法 SM3. 国家密码管理局.

相关实践

• SHA-3 SM3 哈希函数性能对比
• 密码学哈希函数基础（MD 构造至 SHA-2）
• HKDF 密钥派生函数原理