论文链接: https://doi.org/10.1007/978-3-319-63688-7_19.
论文给出了第一个SHA-1的实际碰撞.
攻击步骤
- 找到合适的扰动向量.
- 构造非线性部分差分路径.
- 确定每步的条件.
扰动向量选择
采用联合局部碰撞分析(JLCA)技术. 不考虑一条差分路径的概率, 而是考虑由特定状态输入差分、和消息差分经过特定步产生特定输出差分的概率.
扰动向量使用Ⅱ(\(K,b\)). \(DV_{K+1} = DV_{K+3} = 2^{b-1}\), \(DV_{K+15} = 2^b\), \(DV_{K+i} = 0, i \in \{0,2,4,5,\dots,14\}\).
构建非线性差分路径
两个分组分别构建. 第一个分组有额外自由度: 第一个分组初始状态值可自由选择; 第一个消息分组最终输出的差分形式可以有多个选择, 第二个分组输出差分要取消第一个分组的差分.
非线性部分的路径使用自动化搜索工具HashClash进行, 采用了类似中间相遇的算法. 还需要保证路径的可解性.
确定攻击条件
条件包括两部分:
- 消息上的条件. 在确定了扰动向量(消息异或差分)的情况下, 条件用于控制消息的模差分.
- 给定一个差分路径后, 内部状态比特某一特定步之前需要满足的条件. 包括某比特是否有差分以及差分的符号.
攻击中前23步用一条确定的路径, 之后使用JLCA寻找概率最大的路径. 确定的路径存在消息和状态的条件, 后面只有消息的条件. 使用JLCA会使条件数变少, 需要一些额外的条件来早停.
寻找额外条件
在21-25步中寻找消息和内部状态的额外条件. 生成直到31步的大量满足已有方程的解, 检测每一个可能成立的线性方程(至多包含4个状态和消息比特).
保证前几步的可解性
第二个消息分组的攻击, 初始内部状态没有自由度, 前几步条件很多, 很可能构建的非线性路径不可解. 采用SAT搜出一条可解的前8步路线.
消息修改技术
中性比特和Boomerang.