对简化版RIPEMD-160的差分攻击

### 对简化版RIPEMD - 160的差分攻击 #### 1. 攻击概述 RIPEMD - 160由两个采用不同消息字排列的流组成，因此在攻击时需要同时考虑这两个流。攻击的第一步是确定那些可能包含差异的消息字，以引发局部碰撞。为了使整个攻击能够高效进行，对于这些局部碰撞有一些约束条件。 #### 2. 选择消息字差异 在RIPEMD - 160中构造稀疏局部碰撞有多种选择： - **单消息字差异**：通过在单个消息字中设置差异来构造RIPEMD - 160第1轮和第2轮之间的局部碰撞。如果仅考虑单个消息字的差异，当局部碰撞在两个流中尽早结束时，可在第二轮获得稀疏差分特征。以W7为例，可以构造在左流和右流第二轮的第1步和第4步结束的局部碰撞。以下是能构造在第二轮前半部分结束的局部碰撞的候选消息字： | 消息字 | 左流局部碰撞长度 | 右流局部碰撞长度 | | ---- | ---- | ---- | | W7 | 9步（第7步到第16步） | 17步（第2步到第19步） | | W6 | 15步（第6步到第21步） | 7步（第9步到第16步） | | W10 | 10步（第10步到第20步） | 10步（第13步到第23步） | 不过，很难为第一轮找到对应的差分特征。由于左流第一轮使用了异或函数且局部碰撞较短（9步），未能成功找到对应的差分特征。但由于RIPEMD - 160消息扩展中的重复模式，可跳过第一轮，使用消息字W3在第2轮和第3轮之间构造相同长度和位置的局部碰撞，此设置用于主要攻击。 - **多消息字差异**： - **三个消息字**：可以轻松构造单个5步的局部碰撞。由于两个流第二轮的布尔函数可以吸收差异，三个消息字足以构造5步局部碰撞。但由于消息排列的原因，无法同时在两个流的第二轮构造5步局部碰撞。以下是第二轮的最短局部碰撞以及第一轮的相应局部碰撞： | 消息字三元组 | 左流第一轮局部碰撞长度 | 左流第二轮局部碰撞长度 | 右流第一轮局部碰撞长度 | 右流第二轮局部碰撞长度 | | ---- | ---- | ---- | ---- | ---- | | (W4, W10, W12) | 8步（第4步 - 第12步） | 7步（第17步 - 第24步） | 8步（第7步 - 第15步） | 5步（第23步 - 第28步） | | (W5, W9, W15) | 10步（第5步 - 第15步） | 5步（第22步 - 第27步） | 10步（第0步 - 第10步） | 7步（第22步 - 第29步） | | (W4, W10, W12) | 20步（第4步 - 第24步） | | 8步（第7步 - 第15步） | 5步（第23步 - 第28步） | - **两个消息字**：只有三对消息字可以同时在两个流的第二轮构造6步局部碰撞，并在第一轮构造合适的局部碰撞。在这种6步局部碰撞中，两个状态变量必须包含差异。由于旋转值不同以及状态更新过程中的额外模加运算，无法同时在两个状态变量中使用单个比特差异。此外，需要长进位扩展来消除模加运算中的差异，这导致特征不够稀疏。 | 消息字对 | 左流第一轮局部碰撞长度 | 左流第二轮局部碰撞长度 | 右流第一轮局部碰撞长度 | 右流第二轮局部碰撞长度 | | ---- | ---- | ---- | ---- | ---- | | (W0, W8) | 8步（第0步 - 第8步） | 6步（第25步 - 第31步） | 8步（第3步 - 第11步） | 6步（第20步 - 第26步） | | (W7, W15) | 8步（第7步 - 第15步） | 6步（第16步 - 第22步） | 8步（第2步 - 第10步） | 6步（第19步 - 第25步） | | (W3, W14) | 11步（第3步 - 第14步） | 6步（第23步 - 第29步） | 13步（第1步 - 第14步） | 6步（第18步 - 第24步） | | (W12, W13) | 12步（第12步 - 第24步） | 7步（第8步 - 第15步） | 6步（第21步 - 第27步） | | | (W7, W15) | 15步（第7步 - 第22步） | | 8步（第2步 - 第10步） | 6步（第19步 - 第25步） | | (W9, W10) | 17步（第9步 - 第26步） | 9步（第4步 - 第13步） | 6步（第23步 - 第29步） | | #### 3. 碰撞攻击 使用自动搜索工具来寻找RIPEMD - 160的48步半自由启动近碰撞和36步半自由启动碰撞，结果通过RIPEMD - 160的中间3轮和消息字W3中的单个比特差异获得。 - **自动搜索工具**：为了找到差分特征和确认输入，需要先进的技术和工具。由于RIPEMD - 160比RIPEMD更复杂，手动寻找好的（高概率）差分特征几乎不可能。因此使用了一个自动工具，它基于Mendel等人的方法，可用于寻找复杂的非线性差分特征以及解决涉及状态字和消息字条件的非线性方程。 - **广义条件**：该工具考虑使用广义条件对成对的比特施加任意条件。广义条件受带符号比特差异的启发，考虑了一对比特的所有16种可能条件。以下是这些可能条件的表示： | (Xi, Xi∗) | (0, 0) | (1, 0) | (0, 1) | (1, 1) | | ---- | ---- | ---- | ---- | ---- | |? | ✓ | ✓ | ✓ | ✓ | | - | ✓ | - | - | ✓ | | x | - | ✓ | ✓ | - | | 0 | ✓ | - | - | - | | u | - | ✓ | - | - | | n | - | - | ✓ | - | | 1 | - | - | - | ✓ | | # | - | - | - | - | | (Xi, X∗i) | (0, 0) | (1, 0) | (0, 1) | (1, 1) | | 3 | ✓ | ✓ | - | - | | 5 | ✓ | - | ✓ | - | | 7 | ✓ | ✓ | ✓ | - | | A | - | ✓ | - | ✓ | | B | ✓ | ✓ | - | ✓ | | C | - | - | ✓ | ✓ | | D | ✓ | - | ✓ | ✓ | | E | - | ✓ | ✓ | ✓ | - **搜索算法**：通过按位切片的方式考虑这些广义条件的传播，可以高效地构造差分特征。搜索算法的基本思想是从具有预定义条件的比特位置集合中随机选择一个比特，施加更严格的条件，并计算新条件如何传播，重复此过程直到发现不一致或消除集合中所有无约束的比特。 - **寻找非线性特征的搜索策略**： 1. 定义一组无约束比特（?）和差异（x）。 2. 从集合中随机选择一个比特。 3. 对无约束比特（?）施加零差异（-），或为差异（x）随机选择一个符号（u或n）。 4. 检查新条件如何传播。 5. 如果出现不一致，记住最后一个比特并回溯，直到该比特可以被约束而不导致矛盾。 6. 从步骤2重复，直到集合中的所有比特都被约束。 - **寻找符合条件的消息对**：使用相同的策略来寻找给定差分特征的符合输入对。不同的是，选择无差异的未确定比特（-）并随机分配一个值（0或1），直到找到解决方案： 1. 定义一组无差异的未确定比特（-）。 2. 从集合中随机选择一个比特。 3. 随机选择该比特的值（0或1）。 4. 检查新条件如何传播。 5. 如果出现不一致，记住最后一个比特并回溯，直到该比特可以被约束而不导致矛盾。 6. 从步骤2重复，直到集合中的所有比特都被约束。 在RIPEMD - 160中，一次状态更新中有两个模加运算（由旋转操作分隔），可能会出现两种不同的进位扩展。仅在搜索中随机选择Bi和B′i的比特时，条件传播非常缓慢。因此，还考虑第一个模加运算的输出比特，并对这些条件施加更多限制，这样可以更早地检测到矛盾，显著提高搜索效率。 以下是寻找非线性特征和符合条件的消息对的流程： ```mermaid graph LR classDef startend fill:#F5EBFF,stroke:#BE8FED,stroke-width:2px; classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; classDef decision fill:#FFF6CC,stroke:#FFBC52,stroke-width:2px; A([开始]):::startend --> B(定义无约束比特和差异):::process B --> C(随机选择一个比特):::process C --> D{选择操作}:::decision D -->|无约束比特| E(施加零差异):::process D -->|差异| F(随机选择符号):::process E --> G(检查条件传播):::process F --> G G --> H{是否一致}:::decision H -->|否| I(记住最后一个比特并回溯):::process I --> C H -->|是| J{所有比特是否被约束}:::decision J -->|否| C J -->|是| K([结束]):::startend ``` - **寻找差分特征**：搜索工具寻找48步半自由启动近碰撞的起点如下表所示。在搜索前不固定消息差异，以便工具找到更好的解决方案。为了获得低攻击复杂度的差分特征，目标是消息字中具有低汉明重量差异，从而在第16步（即第32步之后）状态字中也具有低汉明重量差异。因此，首先在这个区域搜索好的特征。 | i | ∇Bi | ∇B′i | j | ∇Wj | | ---- | ---- | ---- | ---- | ---- | | -5 | -------------------------------- | | | | | -4 | -------------------------------- | | | | | -3 | -------------------------------- | | | | | -2 | -------------------------------- | | | | | -1 | -------------------------------- | | | | | 16 | -------------------------------- | -------------------------------- | 0 | | | 17 | -------------------------------- | -------------------------------- | 1 | | | 18 | -------------------------------- | ???????????????????????????????? | 2 | | | 19 | -------------------------------- | ???????????????????????????????? | 3 | | | 20 | -------------------------------- | ???????????????????????????????? | 4 | | | 21 | -------------------------------- | ???????????????????????????????? | 5 | | | 22 | -------------------------------- | ???????????????????????????????? | 6 | | | 23 | ???????????????????????????????? | ???????????????????????????????? | 7 | | | 24 | ???????????????????????????????? | ???????????????????????????????? | 8 | | | 25 | ???????????????????????????????? | ???????????????????????????????? | 9 | | | 26 | ???????????????????????????????? | ???????????????????????????????? | 10 | | | 27 | ???????????????????????????????? | ???????????????????????????????? | 11 | | | 28 | -------------------------------- | ???????????????????????????????? | 12 | | | 29 | -------------------------------- | ???????????????????????????????? | 13 | | | 30 | -------------------------------- | ???????????????????????????????? | 14 | | | 31 | -------------------------------- | -------------------------------- | 15 | | | 32 | -------------------------------- | -------------------------------- | | | | 33 | -------------------------------- | -------------------------------- | | | | 34 | -------------------------------- | -------------------------------- | | | | 35 | -------------------------------- | -------------------------------- | | | | 36 | -------------------------------- | -------------------------------- | | | | 37 | -------------------------------- | -------------------------------- | | | | 38 | -------------------------------- | -------------------------------- | | | | 39 | -------------------------------- | -------------------------------- | | | | 40 | -------------------------------- | -------------------------------- | | | | 41 | -------------------------------- | -------------------------------- | | | | 42 | -------------------------------- | -------------------------------- | | | | 43 | -------------------------------- | -------------------------------- | | | | 44 | -------------------------------- | -------------------------------- | | | | 45 | -------------------------------- | -------------------------------- | | | | 46 | -------------------------------- | -------------------------------- | | | | 47 | -------------------------------- | -------------------------------- | | | | 48 | -------------------------------- | -------------------------------- | | | | 49 | -------------------------------- | -------------------------------- | | | | 50 | -------------------------------- | -------------------------------- | | | | 51 | -------------------------------- | -------------------------------- | | | | 52 | -------------------------------- | ???????????????????????????????? | | | | 53 | -------------------------------- | ???????????????????????????????? | | | | 54 | -------------------------------- | ???????????????????????????????? | | | | 55 | -------------------------------- | ???????????????????????????????? | | | | 56 | -------------------------------- | ???????????????????????????????? | | | | 57 | ???????????????????????????????? | ???????????????????????????????? | | | | 58 | ???????????????????????????????? | ???????????????????????????????? | | | | 59 | ???????????????????????????????? | ???????????????????????????????? | | | | 60 | ???????????????????????????????? | ???????????????????????????????? | | | | 61 | ???????????????????????????????? | ???????????????????????????????? | | | | 62 | ???????????????????????????????? | ???????????????????????????????? | | | | 63 | ???????????????????????????????? | ???????????????????????????????? | | | 首先在右流的状态字B′24和B′30中搜索稀疏差分特征，这样一方面可以显著减少搜索空间，另一方面可以使右流第24步之后的差分特征更稀疏，从而简化后续寻找符合输入的过程。能够找到消息字W3中具有单个比特差异的差分特征，并且在第32步之后只有很少的条件，从而实现整体较低的攻击复杂度。然后继续搜索差分特征的其余部分，使用搜索工具可以为左流和右流找到许多差分特征。以下是RIPEMD - 160第2 - 4轮（48步）的差分特征： | i | ∇Bi | ∇B′i | j | ∇Wj | | ---- | ---- | ---- | ---- | ---- | | -5 | -------------------------------- | | | | | -4 | -------------------------------- | | | | | -3 | -------------------------------- | | | | | -2 | --------1000000----------------- | | | | | -1 | -------------------------------- | | | | | 16 | -------------------------------- | 00000000000000000000000000000000 | 0 | | | 17 | -------------------------------- | 00001010111111-11111000100011111 | 1 | | | 18 | -------------------------------- | uuuu1uuuuuuuuuuuuuuuuuuuuuuuuuuu | 2 | | | 19 | -------------------------------- | 01-01101001110101001100011-100-- | 3 | | | 20 | ---000-------------------------- | nu-nu01000uuuu0u0u01101011-unn-- | 4 | | | 21 | -------------1------------------ | 11-000u0uu10--u1-111-11--10-00nn | 5 | | | 22 | ---0---------------------------- | uu-0nu01------11-11n110--n1-10uu | 6 | | | 23 | ---nu--------------------------- | ----1-01---u-0-1-0n01111-1uuuu10 | 7 | | | 24 | ---00-------nuuuuuuuuuuuu000u--- | -1--nu0u0---n011-00n0000--01---- | 8 | | | 25 | 000-----10--111111111111111-0000 | -10un-0-00-------011000---101u-0 | 9 | | | 26 | --101101nu111111--1111111------- | --1---0u0111-----100--1n-00100-- | 10 | | | 27 | --------00----unnnnnnnnnnnnnnn-- | -------n11--u--1---1--0--10-n0-- | 11 | | | 28 | --------------100010000000000011 | -------0----------un--1------u-- | 12 | | | 29 | ----0000000001111111------------ | -------00---n-----1----------1-- | 13 | | | 30 | -------------------------------0 | --1-----1--------------------u-- | 14 | | | 31 | -------------------------------- | --0--------------------------0-- | 15 | | | 32 | -------------------------------- | | | | | 33 | -------------------------------- | | | | | 34 | -------------------------------- | | | | | 35 | -------------------------------- | | | | | 36 | -------------------------------- | | | | | 37 | -------------------------------- | | | | | 38 | -------------------------------- | | | | | 39 | -------------------------------- | | | | | 40 | -------------------------------- | | | | | 41 | -------------------------------- | | | | | 42 | -------------------------------- | | | | | 43 | -------------------------------- | | | | | 44 | -------------------------------- | | | | | 45 | -------------------------------- | | | | | 46 | -------------------------------- | | | | | 47 | -------------------------------- | | | | | 48 | -------------------------------- | | | | | 49 | -------------------------------- | | | | | 50 | -------------------------------- | | | | | 51 | -------------------------------- | | | | | 52 | -------------------------------- | -----x-------------------------- | | | | 53 | -------------------------------- | | | | | 54 | -------------------------------- | | | | | 55 | -------------------------------- | | | | | 56 | -------------------------------- | ---------------------------x---- | | | | 57 | -----x-------------------------- | | | | | 58 | -------------------------------- | | | | | 59 | -------------------------------- | | | | | 60 | -------------------------------- | -----------------x-------------- | | | | 61 | ---------------------------x---- | | | | | 62 | ----------------------x--------- | | | | | 63 | -------------------------------- | | | | - **寻找确认消息对**：为了满足差分特征在前16步（第16 - 31步）施加的所有条件，需要应用消息修改技术。由于左流和右流的前几步有很多条件，这可能不是一件容易的事情。然而，使用工具和广义条件，可以相当高效地对前16步进行消息修改。 1. 由于右流的前几步非常密集，首先猜测状态字B′16到B′22中剩余的自由比特，这将确定消息字W5和W13。 2. 然后猜测左流的状态字B26到B16，这将确定B−1、B−2、B−3和大多数消息字，除了W4、W11以及W2、W8的大部分。 3. 最后，猜测剩余消息字中的所有自由比特，以确定剩余的状态变量并找到确认消息对。 以下是寻找确认消息对的流程： ```mermaid graph LR classDef startend fill:#F5EBFF,stroke:#BE8FED,stroke-width:2px; classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; classDef decision fill:#FFF6CC,stroke:#FFBC52,stroke-width:2px; A([开始]):::startend --> B(猜测B′16到B′22的自由比特):::process B --> C(确定W5和W13):::process C --> D(猜测B26到B16的状态字):::process D --> E(确定B−1、B−2、B−3和大部分消息字):::process E --> F(猜测剩余消息字的自由比特):::process F --> G(确定剩余状态变量):::process G --> H(找到确认消息对):::process H --> I([结束]):::startend ``` 最终得到RIPEMD - 160三轮（第16 - 63步）的半自由启动近碰撞如下表所示。相同的输入也会导致RIPEMD - 160 36步的碰撞。此外，可以将两个半自由启动近碰撞组合起来，构造RIPEMD - 160 48步的二阶差分碰撞（4 - 和），比之前的结果提高了8步。 | | 值 | | ---- | ---- | | H0 | b23f78a3 7775d378 20806ef8 8d6b662d 4f669598 | | M1 | 2e3d54df e568a9cd d5e45e10 52f4e41a bb1bcda9 ffd073a6 ffe9b7f6 bfe436a9 <br> 1273b786 b4ce0002 254a969e 359b7260 817f9eda ef3fff6d bc5068f5 2c3fc390 | | M ∗1 | 2e3d54df e568a9cd d5e45e10 52f4f41a bb1bcda9 ffd073a6 ffe9b7f6 bfe436a9 <br> 1273b786 b4ce0002 254a969e 359b7260 817f9eda ef3fff6d bc5068f5 2c3fc390 | | ΔM1 | 00000000 00000000 00000000 00001000 00000000 00000000 00000000 00000000 <br> 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 | | H1 | d98051ed e2a12c89 a16b3753 e8764785 1cb36d97 | | H∗1 | d98053ed e3a16c89 a16b3753 e8764785 1cb36d97 | | ΔH1 | 00000200 01004000 00000000 00000000 00000000 | 综上所述，通过上述方法可以对RIPEMD - 160进行有效的碰撞攻击，为密码分析提供了重要的参考。同时，这些技术和思想也可能应用于其他哈希函数的攻击中。 ### 对简化版RIPEMD - 160的差分攻击 #### 4. 总结与展望 通过上述一系列方法，成功地对RIPEMD - 160进行了碰撞攻击，获得了48步半自由启动近碰撞和36步半自由启动碰撞的结果。这些结果在多个方面改进了以往的研究： - **增加碰撞步数**：提高了RIPEMD - 160压缩函数能够找到（近）碰撞的步数。 - **降低攻击复杂度**：攻击具有很低的复杂度，并且能够给出实际的例子。 然而，在攻击过程中也遇到了一些困难。例如，很难找到包含RIPEMD - 160第一轮的类似攻击。由于左流第一轮使用了异或函数，未能成功找到对应的差分特征。未来的工作可以聚焦在以下几个方面： - **扩展到第一轮**：尝试将攻击应用到第1 - 3轮，这可能需要对自动工具进行大量改进。 - **固定链接值的攻击**：为了找到RIPEMD - 160简化哈希函数（固定链接值）的（近）碰撞，需要构造更稀疏的局部碰撞，并拥有更多的自由度来进行消息修改。 此外，本文所使用的思想和技术还可能应用于其他哈希函数的攻击，例如那些使用单个消息字更新更多状态变量的哈希函数，像SHA - 2或SHA - 3候选算法Blake和Skein等。 #### 5. 关键技术回顾 为了更清晰地理解整个攻击过程，下面对一些关键技术进行回顾总结： ##### 5.1 消息字差异选择 消息字差异的选择是攻击的基础，不同的选择会影响局部碰撞的构造和攻击的复杂度。具体选择方式总结如下表： | 消息字差异情况 | 特点 | 示例消息字 | 局部碰撞效果 | | ---- | ---- | ---- | ---- | | 单消息字差异 | 可在特定轮次构造局部碰撞，但为第一轮找对应差分特征困难 | W7、W6、W10 | 不同轮次和流有不同长度的局部碰撞 | | 三个消息字差异 | 能构造5步局部碰撞，但受消息排列限制，无法同时在两轮构造 | (W4, W10, W12)、(W5, W9, W15) | 不同轮次和流有不同长度的局部碰撞 | | 两个消息字差异 | 部分消息字对可同时在两轮构造6步局部碰撞，但特征不够稀疏 | (W0, W8)、(W7, W15)、(W3, W14) | 不同轮次和流有不同长度的局部碰撞 | ##### 5.2 自动搜索工具 自动搜索工具是寻找差分特征和确认消息对的核心，其主要基于广义条件和搜索算法： - **广义条件**：考虑一对比特的16种可能条件，通过按位切片的方式传播条件，高效构造差分特征。 - **搜索算法**：包括寻找非线性特征和符合条件的消息对的策略，通过随机选择比特、施加条件、检查传播和回溯等步骤，逐步约束所有比特。 以下是自动搜索工具的主要步骤总结： 1. **定义条件集合**：定义无约束比特、差异或无差异的未确定比特集合。 2. **随机选择比特**：从集合中随机选择一个比特。 3. **施加条件**：根据比特类型施加相应条件（零差异、符号选择或比特值选择）。 4. **检查传播**：检查新条件的传播情况。 5. **处理不一致**：若出现不一致，回溯并重新选择。 6. **完成约束**：重复上述步骤直到所有比特被约束。 ##### 5.3 差分特征与确认消息对寻找 - **差分特征寻找**：不固定消息差异，先在特定区域搜索稀疏特征，逐步扩展到整个过程，以获得低攻击复杂度的结果。 - **确认消息对寻找**：应用消息修改技术，通过猜测状态字和消息字的自由比特，满足差分特征在前16步施加的条件。 整个攻击过程的关键步骤流程图如下： ```mermaid graph LR classDef startend fill:#F5EBFF,stroke:#BE8FED,stroke-width:2px; classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; classDef decision fill:#FFF6CC,stroke:#FFBC52,stroke-width:2px; A([开始]):::startend --> B(选择消息字差异):::process B --> C(使用自动搜索工具):::process C --> D(寻找差分特征):::process D --> E(寻找确认消息对):::process E --> F(获得碰撞结果):::process F --> G{是否满足要求}:::decision G -->|否| B G -->|是| H([结束]):::startend ``` 通过对RIPEMD - 160的差分攻击研究，不仅深入了解了该哈希函数的安全性，还为密码分析领域提供了新的思路和方法。未来随着技术的发展，相信会有更多关于哈希函数安全性的研究成果出现，进一步推动密码学的发展。