BLAKE

BLAKE
设计者
Jean-Philippe Aumasson
Luca Henzen
Willi Meier
Raphael C.-W. Phan
首次发布
2008
类别
密码学哈希函数
输出长度
224/256/384/512 bit
结构
HAIFA
基础
ChaCha 流密码
竞赛结果
SHA-3 决赛五强
安全状态
安全（无已知攻击）

BLAKE 是 2008 年提交给 NIST SHA-3 竞赛的密码学哈希函数，由 Jean-Philippe Aumasson 等人设计。BLAKE 在 64 个参赛算法中脱颖而出，进入最终五强（BLAKE、Grøstl、JH、Keccak、Skein），但最终败给 Keccak。尽管如此，BLAKE 的设计理念和安全性表现极为出色，成为后续 BLAKE2 和 BLAKE3 的坚实基础。

设计背景

2007 年，NIST 发起 SHA-3 竞赛，旨在寻找 SHA-2 的替代算法。当时 SHA-2 虽然安全，但结构与 SHA-1 相似，业界担心一旦 SHA-2 被攻破，将没有备用方案。BLAKE 的设计目标是：

  • 高安全性：抵抗已知的所有哈希函数攻击（长度扩展、碰撞、原像等）
  • 高性能：在软件实现中达到或超过 SHA-2 的速度
  • 简洁性：基于已有的、经过充分分析的密码学原语
核心结构：HAIFA

BLAKE 使用 HAIFA（HAsh Iterative FrAmework）迭代结构，这是 Merkle-Damgård 结构的改进版本。HAIFA 由 Orr Dunkelman 和 Eli Biham 于 2006 年提出，解决了原始结构的两个关键问题：

Merkle-Damgård 的缺陷
  • 长度扩展攻击：知道 H(m) 和 m 的长度，可以计算 H(m || padding || extension)
  • 多碰撞攻击：Joux 的多碰撞攻击表明，找到 n 段消息的 2^n 碰撞的代价仅相当于 n 次找到单个碰撞
HAIFA 的改进

HAIFA 在压缩函数中引入两个额外参数：

  • 盐值（salt）：随机化压缩函数，抵抗多碰撞攻击
  • 计数器（counter）：记录已处理的比特数，抵抗长度扩展攻击
HAIFA 压缩函数调用： H_0 = IV H_{i+1} = compress(H_i, m_i, salt, counter_i) 其中： - H_i: 链接值（中间哈希状态） - m_i: 第 i 个消息块 - salt: 固定盐值（可选） - counter_i: 已处理的比特数
压缩函数：基于 ChaCha

BLAKE 的压缩函数基于 ChaCha 流密码的四分之一轮函数（quarter-round function）。ChaCha 由 Daniel J. Bernstein 于 2008 年设计，是 Salsa20 的改进版本，具有以下优势：

  • 高扩散性：每个输出位依赖于所有输入位
  • 高效实现：仅使用加法、异或和循环移位操作
  • 安全性证明：对差分攻击和线性攻击有可证明的安全界
压缩函数工作流程
compress(HashState h, message block m, salt s, counter t): # 1. 初始化 16 个 32/64 位工作变量 v[0..3] = h[0..3] # 链接值 v[4..7] = h[0..3] ^ s[0..3] # 链接值异或盐值 v[8..11] = IV[0..3] # 初始化向量 v[12..15] = t[0..1] ^ IV[4..5] # 计数器异或 IV # 2. 消息调度：将 16 字消息字重新排列 sigma = permutation_schedule(m) # 3. 执行轮函数（BLAKE-256: 14轮, BLAKE-512: 16轮） for round = 0 to R-1: G(v, 0, 4, 8, 12) # 列操作 G(v, 1, 5, 9, 13) G(v, 2, 6, 10, 14) G(v, 3, 7, 11, 15) G(v, 0, 5, 10, 15) # 对角线操作 G(v, 1, 6, 11, 12) G(v, 2, 7, 8, 13) G(v, 3, 4, 9, 14) # 4. 最终化：异或链接值 return h ^ v[0..7] ^ s[0..3]
G 函数：ChaCha 四分之一轮

G 函数是 BLAKE 的核心操作，每轮执行 8 次（4 次列操作 + 4 次对角线操作）。G 函数的设计保证了高度的非线性和扩散性：

G(v, a, b, c, d): # 操作 4 个状态变量 v[a] = v[a] + v[b] + m[sigma[r][2*i]] # 加法混合消息 v[d] = (v[d] ^ v[a]) >>> R1 # 异或 + 循环移位 v[c] = v[c] + v[d] # 加法 v[b] = (v[b] ^ v[c]) >>> R2 # 异或 + 循环移位 v[a] = v[a] + v[b] + m[sigma[r][2*i+1]] # 再次混合消息 v[d] = (v[d] ^ v[a]) >>> R3 v[c] = v[c] + v[d] v[b] = (v[b] ^ v[c]) >>> R4 其中： - R1, R2, R3, R4 是固定的循环移位常量 - sigma[r] 是第 r 轮的消息置换表 - m[sigma[r][2*i]] 是当前轮使用的消息字
关键设计思想：BLAKE 将 ChaCha 的核心操作用于哈希压缩函数，这是一种"密码学复用"策略。ChaCha 本身已经过广泛分析，将其用于哈希函数可以继承其安全性保证。
变体
变体字长轮数输出长度消息块大小应用场景
BLAKE-22432 bit14224 bit512 bitSHA-224 替代
BLAKE-25632 bit14256 bit512 bitSHA-256 替代
BLAKE-38464 bit16384 bit1024 bitSHA-384 替代
BLAKE-51264 bit16512 bit1024 bitSHA-512 替代

BLAKE-256 和 BLAKE-512 是两个主要变体。32 位版本适用于嵌入式设备和 32 位处理器，64 位版本在现代 64 位处理器上性能更优。

安全性分析

在 SHA-3 竞赛期间，BLAKE 经受了严格的公开分析：

  • 碰撞攻击：直到竞赛结束，未发现有效的碰撞攻击。最佳攻击仅能攻击到 2.5 轮（BLAKE-256 有 14 轮）
  • 原像攻击：无已知的原像攻击，安全性达到理论最优
  • 长度扩展：HAIFA 结构天然抵抗长度扩展攻击
  • 多碰撞：盐值机制有效抵抗 Joux 的多碰撞攻击
为何输掉 SHA-3 竞赛

尽管 BLAKE 安全性极高，但最终 Keccak 胜出，主要原因包括：

  • 结构差异：Keccak 使用海绵结构（sponge），与 SHA-2 的 Merkle-Damgård 结构完全不同，提供了更好的"算法多样性"
  • 硬件性能：Keccak 在硬件实现中表现优异，适合资源受限环境
  • 灵活性：Keccak 的海绵结构天然支持可扩展输出（XOF）

然而，BLAKE 在软件性能上的优势使其在后续发展中脱颖而出，BLAKE2 和 BLAKE3 的成功证明了这一点。

影响与遗产

BLAKE 虽然没有成为 SHA-3 标准，但其设计理念影响深远：

  • 启发了 BLAKE2（2012），成为最快的密码学哈希函数之一
  • 启发了 BLAKE3（2020），实现了真正的并行哈希
  • ChaCha 的安全性分析成果被广泛应用于 TLS 1.3、WireGuard 等协议
  • HAIFA 结构的设计思想影响了后续哈希函数的设计
参考文献
  1. Aumasson, J.-P., Henzen, L., Meier, W., Phan, R.C.-W. (2008). "SHA-3 proposal BLAKE". NIST SHA-3 Competition Submission.
  2. Aumasson, J.-P., Henzen, L., Meier, W., Phan, R.C.-W. (2010). "SHA-3 Submission: BLAKE, Specification and Analysis". NIST SHA-3 Competition, Round 2.
  3. Dunkelman, O., Biham, E. (2006). "A Framework for Iterative Hash Functions - HAIFA". Cryptology ePrint Archive.
  4. Bernstein, D.J. (2008). "ChaCha, a variant of Salsa20". Workshop Record of SASC.
哈希算法导航
CRC · MD5 · SHA · BLAKE · BLAKE2 · BLAKE3 · SM3 · xxHash · MurmurHash · RIPEMD · Whirlpool · SipHash · CityHash · Adler-32
分类：密码学 · 哈希函数 · SHA-3竞赛