0 概述

哈希函数RIPEMD-160^[1]基于Markle-Damgard^[2-3]结构, 是RIPEMD家族中的重要算法, 同时也是ISO/IEC国际标准之一。RIPEMD家族的压缩函数采用双分支操作, 由于RIPEMD算法2个分支操作很相似, 因此降低了攻击难度。其中, RIPEMD-160的2个分支操作使用了不同的常数、移位值、消息字顺序和布尔函数, 增强了安全性, 其在文件校验、数字签名中被广泛应用。

目前对于RIPEMD-160算法的碰撞攻击、原像攻击和区分攻击研究有:文献[4]提出一种对36步RIPEMD-160算法(从第2轮开始)的半自由起始碰撞攻击方案; 文献[5]提出一种自动搜索RIPEMD-160差分路线的改进方案, 建立了48步(从第2轮开始)和36步算法(从第1轮开始)的差分路线, 并在此基础上分别给出42步和36步RIPEMD-160算法的半自由起始碰撞攻击方案; 文献[6]给出保证RIPEMD-160算法差分路线的模减差分成立的充分条件, 通过消息修改技术使模减差分成立的概率为1, 同时给出了针对前30步RIPEMD-160算法的碰撞攻击, 并改进前36步RIPEMD-160算法的半自由起始碰撞攻击结果; 文献[7]给出一种48步RIPEMD-160算法的半自由起始碰撞攻击方案; 文献[8]给出一种31步RIPEMD-160的原像攻击方案; 文献[9]给出了RIPEMD-160的31步~34步的原像攻击方案(从第1轮开始)和35步的原像攻击(从第2轮开始); 文献[10]给出一种51步RIPEMD-160算法的区分攻击方案。

文献[11]提出对分组密码算法的boomerang攻击方法。在此基础上, 文献[12-13]将这个方法应用到哈希函数的区分攻击中, 文献[10]利用基于boomerang区分器的2-dimension sums方法, 给出51步RIPEMD-160算法的区分攻击方法, 复杂度为2¹⁵⁸, 通过构建RIPEMD-160压缩函数左右操作的差分路线, 并使用消息修改技术使左右操作差分路线的前半部分(左操作的17步~25步, 右操作的17步~22步)以1的概率成立。然而由于RIPEMD-160的步操作不是一个标准的T函数(第i位输出只依赖于前i位的输入), 并且文献[10]在使用消息修改技术时没有考虑模减差分对差分路线的影响, 因此不能保证在消息修改之后左右操作前半部分成立的概率为1, 由此可知文献[10]中得到的区分攻击复杂度是有误的。

针对上述问题, 本文给出保证RIPEMD-160算法差分路线模减差分成立的充分条件, 通过消息修改技术使差分路线前半部分成立的概率为1, 以降低区分攻击的复杂度, 同时在评估差分路线后半部分的概率时考虑差分路线的模减差分, 通过实验测试得到后半部分差分路线成立的概率。

1 预备知识 1.1 基本符号说明

本文用到的符号说明如下:

1) M=(m₀, m₁, …, m₁₅)和M′=(m′₀, m′₁, …, m′₁₅)分别代表512 bit的消息字。

2) X_i和X′_i分别代表左分支压缩函数处理消息字M和M′在第i(1≤i≤80)步产生的输出值, 其中X_i和X′_i都为32 bit。

3) Y_i和Y′_i分别代表右分支压缩函数处理消息字M和M′在第i(1≤i≤80)步产生的输出值, 其中Y_i和Y′_i都为32 bit。

4) +和－分别表示模2³²加运算和模2³²减运算。

5) x<<<s表示x向左循环移动s位, x>>>s表示x向右循环移动s位。

6) Δx_i=x′_i－x_i表示x′_i和x_i之间的模减差分。

7) Δx_i=[j]表示x_{i, j}=0, x′_{i, j}=1, x_{i, k}=x′_{i, k}, 0≤k≤31, k≠j。

8) Δx_i=[－j]表示x_{i, j}=1, x′_{i, j}=0, x_{i, k}=x′_{i, k}, 0≤k≤31, k≠j。

9) C(i~j)表示C的第i位到第j位的值0≤j≤i≤31。

1.2 RIPEMD-160算法

哈希函数RIPEMD-160将任意长度的消息(小于2⁶⁴)压缩为160 bit的哈希值。首先将填充之后的消息分块, 每个消息块的长度为512 bit, 然后压缩函数将每一个512 bit的消息块压缩成160 bit的输出。RIPEMD-160的压缩函数包含2个分支, 分别记为左分支和右分支, 每个分支包含5轮运算, 每轮包含16步操作, 具体描述如下:

将160 bit的输入链变量cv记为5个字cv_i(i=0, 1, 2, 3, 4), 其中cv_i的长度是32 bit。首先对左右分支的160 bit的内部状态进行初始化:

$ \begin{align} & {{X}_{-4}}={{Y}_{-4}}=c{{v}_{0}}>>>10, {{X}_{-3}}={{Y}_{-3}}=c{{v}_{4}}>>>10 \\ & {{X}_{-2}}={{Y}_{-2}}=c{{v}_{3}}>>>10, {{X}_{-1}}={{Y}_{-1}}=c{{v}_{2}}, {{X}_{0}}={{Y}_{0}}=c{{v}_{1}} \\ \end{align} $

在第j轮(1≤j≤5), 左右操作的链接变量X_i和Y_i(1≤i≤80)的更新操作分别为:

$ \begin{array}{*{35}{l}} {{X}_{i}}=\left( {{X}_{i-4}}<<<10 \right)+\left( \left( {{X}_{i-5}}<<<10 \right)+{{F}_{j}}\left( {{X}_{i-1}}, \\{{X}_{i-2}}, \left( {{X}_{i-3}}<<<10 \right) \right)+{{m}_{{{\pi }^{l}}(i)}}+{{k}_{j}^{l}} \right)<<<{{s}_{i}^{l}} \\ {{Y}_{i}}=\left( {{Y}_{i-4}}<<<10 \right)+\left( \left( {{Y}_{i-5}}<<<10 \right)+{{G}_{j}}\left( {{Y}_{i-1}}, \\{{Y}_{i-2}}, \left( {{Y}_{i-3}}<<<10 \right) \right)+{{m}_{{{\pi }^{r}}(i)}}+{{k}_{j}^{r}} \right)<<<{{s}_{i}^{r}} \\ \end{array} $

其中, 布尔函数F_j和G_j、轮常数k_j^l和k_j^r都依赖于轮数j(1≤j≤5)和左右分支, 布尔函数F_j和G_j参照表 1, 轮常数k_j^l和k_j^r的取值参照表 2, 消息字m_π^l(i)和m_π^r(i)的顺序以及对应的移位值s_i^l和s_i^r参照表 3。

1.3 模减差分及其概率计算

对于已知差分路线的RIPEMD-128算法, 容易推导出保证差分路线成立的充分条件, 并利用消息修改技术使得差分路线成立。由于RIPEMD-160的步操作不是标准的T函数, 在计算差分路线的概率时不能忽略模减差分的影响, 因此在计算差分路线中任意一步成立的概率时, 既要考虑比特条件成立的概率, 也要考虑模减差分成立的概率。文献[6]推导得到保证RIPEMD-160算法差分路线的模减差分成立的充分条件, 通过消息修改技术^[14]使模减差分成立的概率为1, 同时给出前30步RIPEMD-160算法的碰撞攻击, 并优化前36步RIPEMD-160算法的半自由起始碰撞攻击结果。下文介绍模减差分修改中用到的表达式以及修改方法。

令Δ=X′_i－X_i, Δ_i－5=(X′_i－5<<<10)－(X_i－5<<<10), Δ_i－4=(X′_i－4<<<10)－(X_i－4<<<10), ΔF=φ_j^r(X_i－1^r, X′_i－2, X′_i－3<<<10)－φ_j^r(X_i－1, X_i－2, X_i－3<<<10), 则根据计算X_i步操作的表达式可知模减差分成立的概率为Pr(v)=Pr[Δ=Δ_i－4+(Δ_i－5+ΔF+Δm_π(i)+T)<<<s_i－(T<<<s_i)], 其中, T=(X_i－5<<<10)+F_i(X_i－1, X_i－2, (X_i－3<<<10))+m_π^l(i)+k_j^l。

令:C₀=Δ_i－5+ΔF+Δm_π(i), C₁=Δ－Δ_i－4, 则模减差分成立的概率转换为:Pr(v)=Pr[(T+C₀)<<<s_i=(T<<<s_i)+C₁]。因为对于给定的差分路线, C₀和C₁的值是确定的, 所以可以通过在T上添加条件来保证Pr(v)=1。又根据X_i的表达式知, T=(X_i－(X_i－4<<<10))>>>s_i, 因此, 在T上的条件可以转化为在X_i和X_i－4上的条件, 即通过在X_i和X_i－4上添加条件, 可以使得X_i和X′_i模减差分成立的概率为1。具体添加条件的过程参见文献[6]。

2 文献[10]对RIPEMD-160的区分攻击分析

本节介绍文献[10]中3种构建RIPEMD-160区分器的方法, 重点研究本文讨论的2-dimension sums方法, 并分析其原理和实现方式。文献[10]提出的3种区分器, 分别为4-sum、2-dimension sums和n-dimension sums。

4-sum属性是4个不同的输入(I₀, I₁, I₂, I₃)对应输出的异或和为0, 即CF(I₀)⊕CF(I₁)⊕CF(I₂)⊕CF(I₃)=0, 其中, CF为RIPEMD-160的压缩函数。构建4-sum区分器的一般复杂度为2^n/3, 其中n为哈希值的长度。

通过对4-sum属性的输入∇添加约束, 扩展出2-dimension sums属性, 目的是寻找4个不同的输入(I₀, I₁, I₂, I₃)满足I₁=I₀⊕Δ, I₂=I₀⊕∇, I₃=I₀⊕Δ⊕∇, 并且输出满足CF(I₀)⊕CF(I₁)⊕CF(I₂)⊕CF(I₃)=0(Δ和∇分别代表RIPEMD-160左右分支的输入差分)。构建2-dimension sums区分器的一般复杂度是2ⁿ, 此方法适合用于构造双分支结构哈希函数的区分器。

n-dimension sums区分器是2-dimension sums区分器的扩展, 适用于构造n分支结构哈希函数的区分器。下文详细介绍2-dimension sums区分器。

如图 1所示, 文献[10]首先构建RIPEMD-160算法左右分支操作的差分路线, 然后寻找输入链接变量H和消息M, 使得(M, H)和(M+Δ_M, H+Δ_H)之间以及(M+∇_M, H+∇_H)和(M+Δ_M+∇_M, H+Δ_H+∇_H)之间遵循左分支操作的差分路线, 并且(M, H)和(M+∇_M, H+∇_H)之间以及(M+Δ_M, H+Δ_H)和(M+Δ_M+∇_M, H+Δ_H+∇_H)之间遵循右分支操作的差分路线。对于这样的(M, H), 可以保证以下的关系式成立:

$ \begin{align} & F\left( M+{{\mathit{\Delta} }_{M}}+{{\mathit{\nabla} }_{M}}, H+{{\mathit{\Delta} }_{H}}+{{\mathit{\nabla} }_{H}} \right)=CF\left( M, H \right)+\text{ } \\ & \ \ \ \ \ \ \ \ \ \ \ CCF\left( M+{{\mathit{\Delta} }_{M}}, H+{{\mathit{\Delta} }_{H}} \right)+CF(M+{{\mathit{\nabla} }_{M}}, H+{{\mathit{\nabla} }_{H}}) \\ \end{align} $

3 51步RIPEMD-160区分攻击分析

本节给出保证差分路线中模减差分成立的充分条件, 并使用消息修改技术使左右操作差分路线的前半部分成立的概率为1, 改进了文献[10]中区分攻击的复杂度。本节修改了文献[10]中差分路线的错误, 并通过实验测试给出差分路线后半部分的概率, 最终给出51步RIPEMD-160区分攻击的正确复杂度。

3.1 差分路线中模减差分成立的充分条件

下文将通过一个实例说明如何在T上添加条件, 使得在消息修改^[14-16]后, 该步的模减差分成立的概率为1。本节使用的差分路线如表 4和表 5所示, 其中*表示取正号或负号均可。可以看出, 从第2轮开始, 差分路线与文献[10]略有不同, 左分支第56步、59步、60步和63步为控制差分扩散进行了修改, 第67步则修改了差分值。

本例考虑右分支的第17步操作(Y₁₇), 根据2.3节结论可知, Y₁₇和Y′₁₇的模减差分以1的概率成立, 当且仅当(T+C₀)<<<s_i=(T<<<s_i)+C₁成立。根据C₀和C₁的计算公式可得C₀=0xfc200000, C₁=0x3ffffff8, 同时从表 2可知s₁₇^r=9。C₀和C₁的二进制表示如表 6和表 7所示, 其中t_i表示T的第i(0≤i≤31)位的值。

由表 6和表 7可知, C₀(31~23)=C₁(8~0), C₀(22~0)=C₁(31~9)+1。

为使(T+C₀)<<<9=(T<<<9)+C₁成立, 需要在T上添加条件, 过程如下:

首先, 考虑(T<<<9)+C₁的第0位, 为使t₂₃+C_{0, 23}+进位=t₂₃+C_{1, 0}成立, 即为了让t₂₃+0+进位=t₂₃+0成立, 需要在计算(T+C₀)时, 第22位向第23位不能有进位。又根据C_{0, 22}=0可知, 添加条件t₂₂=0后, 就可保证在计算(T+C₀)时第22位向第23位没有进位。

其次, 考虑(T<<<9)+C₁的第9位, 为使t₀+C_{0, 0}=t₀+C_{1, 9}+进位成立, 即为使t₀+0=t₀+1+进位成立, 需要在计算(T<<<9)+C₁时, 第8位向第9位有进位。又根据C_{1, 8}=1知, 添加条件t₃₁=1, 就可保证在计算(T<<<9)+C₁时第8位向第9位有进位。

由RIPEMD-160算法可知:T=(Y₁₇－(Y₁₃<<<10))>>>9, 因此, 添加在t₂₂和t₃₁上的条件可转化为添加在Y₁₇和Y₁₃上。此时, 需要结合Y₁₇和Y₁₃现有的比特条件(推导差分路线时添加的), 在剩下没有条件的位置上加条件, 如果出现了与已有条件矛盾的情况, 还可以对公式T=(Y₁₂<<<10)+F_i(Y₁₆, Y₁₅, (Y₁₄<<<10))+m_π^r(i)+k_j^r中的Y₁₂、Y₁₆、Y₁₅、Y₁₄中的任意一个链接变量加条件, 使得T上的条件满足。所以, 本例添加的条件是:Y_{17, 31}=0, Y_{17, 30}=0, Y_{17, 8}=1, Y_{17, 7}=1, Y_{13, 30}=0, Y_{13, 29}=0。再使用消息修改技术, 让这些条件满足, 从而可以保证右分支第17步的模减差分以1的概率成立。程序测试结果表明添加条件后的该步模减差分成立的概率始终为1。

3.2 与文献[10]分析结果的对比

本文通过对左右差分路线前面部分的每一步都采用3.1节方法添加条件, 且在消息修改后保证每一步的模减差分成立的概率都为1。文献[10]中的消息修改没有保证差分路线的模减差分以1的概率成立, 表 8和表 9分别比较了本文方法和文献[10]方法左右分支的差分路线前半部分模减差分成立的概率以及相应需要添加的条件, 这部分成立的概率会增加区分攻击的复杂度。由于文献[10]在评估复杂度时对此没有考虑, 因此其给出的复杂度比实际正确的复杂度要低。

3.3 51步RIPEMD-160区分攻击的复杂度

文献[10]中使用2-dimension sums的方法计算出51步的RIPEMD-160区分攻击的复杂度为2¹⁵⁸, 但忽略了差分路线前面部分的模减差分的影响, 认为消息修改之后的差分路线前面部分成立的概率为1, 然而表 8和表 9的实验结果表明, 左右分支的差分路线前半部分成立的概率为2^-7.717。另一方面, 文献[10]通过统计比特条件的数量, 计算出差分路线后面部分的复杂度为2¹⁵⁸, 按照其计算方法, 51步RIPEMD-160区分攻击的复杂度应为2¹⁵⁸×2^15.434=2^173.434, 该结果超出2¹⁶⁰, 因此, 该文给出的51步RIPEMD-160的区分攻击不成立。

本文考虑差分路线前面部分的模减差分, 添加了保证模减差分成立的充分条件, 并通过消息修改技术让这些条件成立, 从而保证差分路线前面部分成立的概率为1, 所以, 在计算区分攻击的复杂度时, 前半部分的复杂度可以忽略。同时本文也考虑了差分路线后面部分的模减差分, 通过程序测试出差分路线后面部分成立的概率。实验结果表明, 51步RIPEMD-160区分攻击的复杂度为2^152.672; 52步RIPEMD-160区分攻击的复杂度为2^161.995, 该结果大于2¹⁶⁰。因此, 对51步RIPEMD-160算法的2-dimension sums最优的区分攻击复杂度为2^152.672。

4 结束语

本文考虑RIPEMD-160算法差分路线的模减差分, 通过在链接变量上添加条件并使用消息修改技术, 使差分路线中模减差分成立的概率为1, 从而降低51步RIPEMD-160区分攻击的复杂度。分析结果表明, 对51步RIPEMD-160区分攻击的复杂度为2^152.672, 该结果为正确计算RIPEMD-160算法其他区分攻击的复杂度提供了参考。下一步将对左右分支消息字的选择进行比较, 通过推理和编程找到最合适的消息字, 再借助于模减差分技术得到更好的攻击方法。