经典哈希算法分析

MD 系列

MD5

MD5（Message Digest Algorithm 5）由 Ronald Rivest 于 1991 年设计，输出 128 位摘要。

结构：Merkle-Damgård 结构，将输入分 512 位块处理，经过 4 轮、每轮 16 步运算。

轮函数：使用四个非线性函数 F, G, H, I（基于位操作 AND, OR, NOT, XOR），每步还涉及模 2³² 加法和循环左移。

安全性现状：已被彻底攻破。

2004 年王小云团队发现了高效的碰撞攻击，复杂度降至约 2³⁹（远低于生日攻击的 2⁶⁴）
2008 年出现了伪造 CA 证书的实际攻击
2012 年 Flame 恶意软件利用 MD5 碰撞伪造了微软的代码签名证书

仍可用于：非安全目的的校验（如文件完整性快速比对），但绝不应用于安全场景。

SHA-1

由 NSA 设计，1995 年发布，输出 160 位摘要。结构与 MD5 类似但更复杂（5 个寄存器，80 步）。

安全性：

2005 年王小云团队理论碰撞攻击复杂度 2⁶⁹
2017 年 Google/CWI Amsterdam 执行了 SHAttered 攻击，首次实际碰撞，花费约 6500 CPU 年

已被弃用：各大浏览器和 CA 已停止接受 SHA-1 证书。

SHA-2 家族

由 NSA 设计，2001 年发布。包括 SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256。

SHA-256

最广泛使用的哈希算法，输出 256 位。

结构：Merkle-Damgård 结构，512 位输入块，64 轮处理。

内部状态：8 个 32 位寄存器 (a, b, c, d, e, f, g, h)，初始化为前 8 个素数平方根的小数部分。

轮函数：每轮涉及 Ch(e,f,g)、Maj(a,b,c)、Σ₀(a)、Σ₁(e) 四个逻辑函数，加上消息调度字 W_t 和轮常数 K_t。

消息调度：将 16 个 32 位消息字扩展为 64 个，使用 σ₀ 和 σ₁ 函数。

安全性：目前被认为是安全的。碰撞安全强度 128 位，实际攻击远未达到理论边界。

SHA-512

与 SHA-256 结构相似但使用 64 位字，1024 位输入块，80 轮处理。在 64 位平台上性能更好。

SHA-3（Keccak）

2012 年 NIST SHA-3 竞赛胜出者，由 Guido Bertoni, Joan Daemen, Michaël Peeters, Gilles Van Assche 设计。

与 SHA-2 的根本区别

SHA-3 不使用 Merkle-Damgård 结构，而是使用海绵结构（Sponge Construction）。

海绵结构

状态为 b = r + c 位（r 为比特率/吸收率，c 为容量）：

吸收阶段（Absorbing）：将消息分成 r 位块，逐块与状态的前 r 位异或后进行置换 f
挤出阶段（Squeezing）：从状态中取出 r 位输出，需要更多输出则再置换再取

安全强度由容量 c 决定：碰撞安全 = c/2，原像安全 = c。

Keccak-f 置换

核心是一个 b 位的置换函数，由 24 轮组成，每轮包含 θ, ρ, π, χ, ι 五个步骤：

θ（Theta）：列奇偶校验扩散
ρ（Rho）：位旋转
π（Pi）：片内位置置换
χ（Chi）：唯一的非线性操作（NOT-AND）
ι（Iota）：轮常数异或

SHA-3 的优势：结构简单、安全性证明更充分、可变长度输出、对长度扩展攻击天然免疫。

其他重要哈希函数

BLAKE2

基于 BLAKE（SHA-3 竞赛决赛选手）的改进。BLAKE2s（256 位）和 BLAKE2b（512 位）。速度比 SHA-2 和 SHA-3 快，在软件实现中特别高效，被广泛用于密码学库中。

RIPEMD-160

欧洲项目开发，输出 160 位。使用两条并行处理路径。在比特币中用于生成地址（SHA-256 后再 RIPEMD-160）。

Whirlpool

基于 AES 设计思想的哈希函数，输出 512 位。使用与 AES 相同的 S 盒，但采用类似 Merkle-Damgård 的结构。

Open Clock