杂凑函数的安全性分析概述
杂凑函数的通用攻击
设
杂凑函数不使用秘密密钥。攻击者知道全部算法，并可自行计算任意消息的杂凑值。主要目标是：
| 目标 | 预先给定 | 需要找到 |
|---|---|---|
| 原像 | 一个目标值 \(y\) | \(M\)，使 \(H(M)=y\) |
| 第二原像 | 一条消息 \(M\) | \(M'\ne M\)，使 \(H(M')=H(M)\) |
| 碰撞 | 无固定目标消息 | 不同的 \(M,M'\)，使 \(H(M)=H(M')\) |
在理想随机函数模型与经典计算模型下，原像、第二原像的通用搜索量级为 \(2^n\)，碰撞为 \(2^{n/2}\)。这里的通用攻击不利用具体压缩函数结构。
碰撞一定存在，因为输入空间大于输出空间；抗碰撞性要求的是难以找到，而不是不存在。
生日攻击与广义生日攻击
生日界
计算 \(q\) 条不同消息的杂凑值。在独立均匀输出近似下，碰撞概率为
取 \(q\approx\sqrt{2\ln2}\,2^{n/2}\) 时，碰撞概率约为 \(1/2\)。用哈希表保存已见输出，时间与存储都约为 \(O(2^{n/2})\)。
通过合适的迭代映射和循环检测，Pollard rho 型方法可将工作存储降得很低，但还需回溯恢复两个不同输入，并处理落入退化周期等情况。不能只找到“两个迭代状态相等”就直接当作两个不同消息的碰撞。
广义生日问题
给定 \(k\) 个随机列表 \(L_1,\ldots,L_k\)，寻找
以 \(k=4\)、\(3\mid n\) 为例，每个列表取约 \(2^{n/3}\) 个元素。
1) 将 \(L_1,L_2\) 配对，只保留异或值的低 \(n/3\) 比特为零的组合，期望保留 \(2^{n/3}\) 项。
2) 对 \(L_3,L_4\) 同样处理。
3) 两张新表的低位都为零，再匹配剩余 \(2n/3\) 位。两表各有 \(2^{n/3}\) 项，期望得到常数个完整匹配。
用排序或分桶实现低位匹配，避免直接枚举全部二元组合，可获得约 \(2^{n/3}\) 量级的列表处理成本，忽略多项式因子。
对 \(k=2^a\)，适当参数下 Wagner 树方法的列表规模约为 \(2^{n/(a+1)}\)，总成本还包含列表数因子 \(k\)。
这不意味着任意杂凑函数的普通碰撞复杂度都能降到 \(2^{n/3}\)。必须先证明目标算法的攻击条件确实可以化为相应的多列表求和问题。
杂凑函数的常见结构
Merkle-Damgård 迭代
将填充后的消息分为 \(M_1,\ldots,M_\ell\)，逐块计算
通常使用包含原消息长度的无歧义填充。压缩函数的抗碰撞性质在适当条件下可以传递到完整迭代结构，但这种结构仍可能存在长度扩展等其他性质。
长度扩展：若摘要完整暴露最终链接状态，并且已知或可猜测消息长度，则可以从 \(H(M)\) 继续计算
这不是恢复 \(M\)，也不是找到碰撞；它是从公开链接状态继续运行压缩函数。
基于分组密码的压缩函数
例如 Davies-Meyer 形式
这里消息块充当分组密码的密钥，链接状态充当明文。反馈项使压缩函数不再只是一个易逆的分组密码调用。
它也有特殊的固定点结构：取 \(h=E_M^{-1}(0)\)，就有 \(F(h,M)=h\)。这是在可选择链接状态下的性质，不表示从规定 IV 出发已经找到了完整杂凑的原像。
海绵结构
海绵维护宽度 \(b=r+c\) 的状态，其中 \(r\) 为速率、\(c\) 为容量。吸收阶段把消息块异或到速率部分，再应用公开置换；挤出阶段输出速率部分，必要时继续置换。
摘要一般不暴露完整内部状态，因此不能直接套用普通 MD 的长度扩展方法。安全性同时受输出长度、容量、查询总量与域分离规则约束，不能只看置换状态有多少比特。
原像攻击
给定 \(y\)，普通穷举每次命中概率为 \(2^{-n}\)。结构化原像攻击则尝试拆分计算，利用中间相遇、可逆步骤或消息自由度减少搜索。
要特别区分：
- 原像：固定标准 IV，寻找消息使最终摘要等于目标。
- 伪原像：允许选择初始链接状态，寻找 \((h,M)\) 使 \(F(h,M)\) 等于目标。
伪原像往往更容易，但还需把选出的状态与标准 IV 连接起来，才能形成完整原像攻击。连接阶段不能从总复杂度中省略。
对减步 MD4、MD5 等算法，中间相遇常需要按消息字的依赖划分两端。消息字在多个步骤中重复使用，不能将它们当作独立轮密钥随意猜测。
第二原像攻击
普通第二原像攻击固定一条消息，不能像碰撞攻击那样同时选择两端。但对很长的 MD 消息，可以利用大量已知中间链接状态。
设目标消息约有 \(2^k\) 个分组，链接状态长为 \(n\)。若能从某个状态搜索到目标链中的任一可用状态，随机命中概率约为 \(2^{k-n}\)，桥接成本约为 \(2^{n-k}\)。
困难是拼接后必须保持消息总长度，以便最终长度填充也一致。可扩展消息解决这个问题：构造多种长度不同、终点状态相同的前缀，然后根据桥接位置选择合适长度。
典型构造在第 \(i\) 层准备一条短路径和一条多 \(2^i\) 个分组的长路径，使二者到达同一状态。经过 \(k\) 层，可组合出一段连续长度范围。其主要碰撞搜索成本约为 \(O(k2^{n/2})\)，还要计入长路径生成、目标消息处理和桥接成本。
于是常见的概略估计为
最后一项提醒我们：读取和处理长目标消息也有成本。此类长消息攻击不等于普通短消息的第二原像只需生日复杂度。
碰撞攻击
多碰撞
对 \(n\) 比特链接状态的 MD 结构，在同一初态上先找一对等长单块碰撞；再从共同终点找下一对，重复 \(k\) 次。
每层任选一个消息块，共得到 \(2^k\) 条不同消息，但终点相同。主要成本约为
而不是分别寻找 \(2^k\) 条消息的公共摘要。这利用了迭代结构，可用于分析级联杂凑等构造。
差分碰撞
针对具体算法，先选择消息差分，设计内部状态差分路线，再寻找满足路线条件的消息对。
- 若初始链接状态必须是标准 IV，才是相应完整杂凑的通常碰撞问题。
- 若允许选择同一个任意初始状态，是半自由起始碰撞问题。
- 若允许两边初始状态不同，模型更宽，应明确称为自由起始类结果。
不同文献命名细节可能略有差异，最可靠的做法是直接写明哪些输入和状态可由攻击者控制。
反弹攻击与消息修改
反弹攻击
反弹攻击把路线分成中间的 inbound 和两侧的 outbound。
中间阶段利用可选择状态的自由度，主动构造满足较昂贵 S 盒差分条件的状态对；外侧阶段再向两端传播，接受剩余条件的概率损失。
它与普通从头随机试整条路线不同：困难的中间部分不是纯靠碰运气，而是通过局部求解满足。Whirlpool 类大状态、AES 型结构提供了相应的操作空间。
最终结果可能是区分器、近碰撞、自由起始碰撞或完整碰撞，取决于外侧能否连接规定的输入和反馈条件。必须把 inbound 的构造成本与 outbound 的成功概率一起计算。
消息修改
在 MD4、MD5 等结构中，若某步写为
运算按模 \(2^{32}\) 进行，则选定希望的 \(Q'\) 后，可反解
这使攻击者可以主动满足早期路线条件，而不是等待随机消息满足。若具体算法还有额外加法或变量重命名，需要相应调整公式。
同一个 \(M_j\) 会在后续步骤重用，因此修改它可能破坏之前或之后的条件。多步消息修改需要补偿机制；中立比特则尝试寻找不破坏已有条件的小范围修改自由度。
对模加算法，还要区分异或差分与模减差分，并显式处理进位。两种差分不能在推导中随意互换。
本章总结
原像、第二原像与碰撞的可选自由度不同；压缩函数结果、自由起始结果和完整杂凑结果也不同。生日方法提供通用基准，迭代结构与具体差分路线则可能产生更有效的攻击。
MD4、MD5 已不应承担抗碰撞安全用途，但碰撞突破不等于能反推出任意消息。密码杂凑也不能代替专用的带盐、可调成本密码存储方案。
参考：王美琴主编，《密码分析学》，第 13 章。结构参数见算法附录。
完
评论