密码学哈希函数

最后更新: 2024-02-07 23:45:50 +0800 +0800
tags: Cryptography | Hashing
原文以英文撰写。您正在阅读AI翻译版本。

密码学哈希函数将任意字节串归约为固定大小的摘要。协议依赖的是特定的抗攻击性质，而不只是哈希这一行为本身，因为快速的无密钥摘要既不能提供消息认证，也不能安全地存储密码。

哈希函数 #

哈希函数将任意大的输入域映射到有限的输出域，输出通常是固定长度的比特串：

text 
H: {0, 1}* -> {0, 1}^n

这个定义本身并不推出任何安全性质。例如，对所有输入都满足 f(x) = 0 的函数也是哈希函数。它不适合哈希表，因为所有条目都落入同一个桶；不过其结果是性能不佳，而不是密码学失败。

密码学用途提出了更强的要求。数据库不应仅因为可能被泄露，就保留用户的明文密码。数据库中存储的密码验证值必须使离线猜测攻击成本高昂；单纯的通用哈希无法达到这一目标。同样，摘要可以检测意外损坏，但能够替换消息的攻击者也能够替换其摘要。普通哈希既不能提供来源认证，也不能提供针对主动攻击者的完整性保护。

由于输入域大于摘要域，所有固定长度哈希都存在碰撞：不同输入具有相同摘要。因此，密码学关注的是攻击者能否利用可行资源找到有用的碰撞，或找到对应指定摘要的输入。

生日界 #

生日悖论有两种等价的表述。在随机选择的人群中，仅有23个人时，两个人生日相同的概率就超过50%。反过来，如果可以逐人查询生日，只需出乎意料地少的查询次数，就有相当大的概率找到匹配的一对。在365天模型下，考察366个人后，根据鸽巢原理必然存在一对匹配者。

第二种表述对哈希更有用。哈希输入不必来自有界的人口：攻击者可以持续选择新输入并计算公开函数。对于具有 N 个等可能输出值的理想哈希，在采样 q 个输出后，至少出现一次重复输出的概率近似为

text 
1 - exp(-q(q - 1) / (2N)).

该近似可以通过考察补事件得到。第一个输出不受限制；下一个输出必须避开一个已占用的值，再下一个必须避开两个，以此类推。将这些概率相乘，会得到一个近似按上述指数函数下降的乘积。因此，要达到固定的碰撞概率，需要约 sqrt(N) 次计算。对于 N = 2^n 的 n 位摘要，通用碰撞成本约为 2^(n/2)。

均匀输出分布是理想模型中的假设。偏差或结构性弱点会使碰撞更容易，而 f(x) = 0 之类的函数会立即发生碰撞。不过，生日界仍然描述了理想固定输出哈希不可避免的限制；扩大输入空间无法改善这一限制。生日攻击就是这种通用碰撞搜索：保留先前的摘要，直到出现重复值。

例如，理想的32位哈希在大约9,300次试验后达到约1%的碰撞概率，在大约77,000次试验后达到约50%的概率。当碰撞抗性重要时，这种摘要是不够的。生日界针对的是输入的任意一对，而不是恢复某个特定输入。

密码学哈希函数的安全性质 #

密码学哈希函数是旨在抵抗特定攻击的无密钥哈希。“密码学哈希函数”并不是一个形式化的安全游戏；其含义取决于协议所需的性质。对于哈希 H，值 y 的原像是任意满足 H(m) = y 的消息 m。

以下游戏在攻击者接收的内容和可以选择的内容方面有所不同：

  1. 原像抗性： 给定目标摘要 y，找到任意满足 H(m) = y 的 m。
  2. 第二原像抗性： 给定特定消息 m1，找到不同的 m2，使得 H(m1) = H(m2)。
  3. 碰撞抗性： 找到不同的 m1、m2，使得 H(m1) = H(m2)。
  4. 选择前缀碰撞抗性： 给定两个不同的前缀 p1 和 p2，找到后缀 s1 和 s2，使得 H(p1 || s1) = H(p2 || s2)。

碰撞攻击允许攻击者同时选择两条消息，而第二原像游戏固定其中一条消息。原像游戏则固定摘要。不能将这些游戏归结为一个普遍的强弱顺序：在特定分布和模型下，性质之间可能存在形式上的蕴含，但弱点也可能与目标相关。协议必须选择与攻击者可控输入相匹配的性质。

对于理想的 n 位哈希，通用原像搜索和第二原像搜索需要约 2^n 的工作量，而生日方法约以 2^(n/2) 的工作量找到碰撞。碰撞抗性意味着不存在能够实质性降低通用生日成本的攻击，而不是不存在碰撞。

选择前缀碰撞比一对互不相关的碰撞文件更强。攻击者可以从两个有意义且不同的前缀开始，例如两种文档格式的标头和初始内容，然后生成使摘要相同的后缀。针对MD5的实际选择前缀碰撞表明，碰撞可以嵌入语义不同的工件中，包括伪造的证书相关材料。这类攻击使MD5在对碰撞敏感的用途中的使用不可接受。

无密钥哈希不使用秘密密钥。接受密钥的构造属于消息认证码、某些术语中的带密钥哈希，或其他原语；其安全要求必须单独评估。

哈希设计与构造 #

有效的密码学设计会将输入中的微小变化广泛扩散到输出中，这种效果称为雪崩效应。雪崩行为是有用的诊断指标，但不能证明原像抗性、第二原像抗性或碰撞抗性。这些性质关注的是攻击者能够采用的最佳算法。

许多迭代哈希从压缩函数开始。压缩函数接收一个链值和一个固定大小的消息块，生成相同宽度的新链值：

text 
C: {0, 1}^n x {0, 1}^b -> {0, 1}^n

“压缩”指的是总输入比输出更长；它不表示该函数可逆。安全分析会针对这个组件寻找适当的单向性和抗碰撞性质。经典构造可以从分组密码构建压缩函数，但现代标准化哈希族使用专门设计。

Merkle–Damgård 构造 #

Merkle–Damgård构造将固定输入压缩函数转换为可变长度哈希。它从初始链值开始，将消息填充为多个块，并将每个块与当前链值一起输入压缩函数。最终链值就是摘要。

Merkle–Damgård强化会在填充中追加原始消息长度的编码。在满足其条件时，具有碰撞抗性的压缩函数可以产生具有碰撞抗性的可变长度哈希：没有强化时，填充输入可能因为消息边界不明确而发生碰撞。MD5、SHA-1和SHA-2都使用这一广义构造；它们的实际安全性由各自的压缩函数和摘要长度决定。

长度编码并不能阻止相关的长度扩展性质。对于传统的Merkle–Damgård哈希，m 的摘要会暴露处理 m 及其填充后的链值。知道摘要和 m 的长度后，攻击者通常可以在不知道 m 的情况下，计算 m || padding(m) || extension 的有效摘要。当系统按如下方式认证数据时，该结果很重要：

text 
SHA-256(secret || message)

如果能够猜测秘密值的长度，攻击者就可以扩展 message 并计算相应的摘要。不要将裸Merkle–Damgård哈希用作秘密前缀MAC。应使用HMAC：

text 
HMAC(K, m) = H((K XOR opad) || H((K XOR ipad) || m))

HMAC的嵌套带密钥构造能够抵抗长度扩展；与SHA-256等当前哈希一起使用时，适合进行消息认证。不过，协议仍必须定义密钥生成、截断、消息编码和密钥分离。

域分离与加盐 #

一个哈希函数经常在协议中承担多个角色。域分离可以防止一个角色中的值被另一个角色接受。标准化构造可以在前面添加固定的函数标识符，将上下文字符串放入专用字段，或为每个角色派生独立密钥。编码必须无歧义：在没有长度信息或指定序列化方式的情况下连接可变长度值，可能会使不同的字段序列映射到相同的字节串。

应使用协议或原语定义的域分离机制。更改前缀或自行设计编码会改变协议，因此需要单独分析。SHA-3函数、可定制的cSHAKE函数和密钥派生协议公开了不同的分离机制，因此它们的输入不可互换。

盐解决的是另一个问题。密码验证值为每个凭据使用唯一的随机盐，使相同密码不会产生相同的存储值，并使攻击者无法将一个预计算表摊销到多个账户上。盐与验证值一起存储，并不保密。盐不会增加密码熵，不会认证消息，也不能替代域分离。

密码哈希还必须施加可配置的时间成本和内存成本。在可用时，应根据RFC 9106使用Argon2id；平台和合规约束可能要求使用scrypt、bcrypt或PBKDF2。应存储算法标识符、参数、盐和派生输出，以便在登录成功后升级参数。

哈希算法的选择 #

根据适用标准、互操作性需求和协议，使用SHA-256、SHA-512/256、SHA-3或BLAKE2等现代通用哈希。SHA-256提供256位摘要，理想通用碰撞工作因子为128位。SHA-512/256是基于SHA-512的独立算法，输出为256位；它不是对SHA-512进行非正式截断得到的算法。

MD5的碰撞抗性已经被攻破，不得在碰撞敏感的安全应用中选用。SHA-1存在实际碰撞攻击和选择前缀碰撞攻击，同样不应再用于数字签名、证书及类似用途。遗留验证可能需要识别这些算法，但新设计不得创建MD5或SHA-1签名。迁移需要明确的算法标识符、对新生成数据的允许列表、移除遗留验证的期限，以及防止降级到过时算法的保护措施。

参考资料 #

评论

在 GitHub 上阅读或评论（发表评论需要登录）