Efficient Collision Attack Frameworks for RIPEMD-160
Efficient Collision Attack Frameworks for RIPEMD-160
复制标题
DOI：
10.1007/978-3-030-26951-7_5
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
F. Liu
中科院分区：
文献类型：
--
作者：
F. Liu
RIPEMD-160是一个ISO/IEC标准，并已被应用于使用SHA-256生成比特币地址。由于复杂的双流结构，Liu，Mendel和Wang在Asiacrypt 2017上提出的简化RIPEMD-160的第一次碰撞攻击只有30步，时间复杂度为。除此之外，已经发表了几个半自由启动碰撞攻击减少RIPEMD-160从中间开始的方法。受这种从中间开始的结构的启发，我们提出了两个新的有效的碰撞攻击框架减少RIPEMD-160充分利用其消息扩展的弱点。这两个框架被称为密集左和稀疏右（DLSR）框架和稀疏左和密集右（SLDR）框架。事实证明，DLSR框架比SLDR框架更有效，因为多了一个步骤可以完全控制，尽管有额外的内存复杂性。为了构造DLSR框架的最佳差分特性，我们仔细构建特性的线性化部分，然后使用猜测和确定方法求解相应的非线性部分。基于新发现的差分特征，我们提供了碰撞消息对的第一个实际的碰撞攻击的30和31（80）步骤的RIPEMD-160的时间复杂度分别为和。另外，由于采用了部分计算，我们可以分别对RIPEMD-160的33步和34步进行攻击，时间复杂度分别为和。当将SLDR框架应用于Asiacrypt 2017论文中使用的差分特征时，我们将时间复杂度显著提高了一个因子。然而，它仍然无法与从DLSR框架获得的结果竞争。据我们所知，这些是对简化的RIPEMD-160的最佳碰撞攻击，就步骤数而言，包括RIPEMD-160的30和31步骤的第一个碰撞消息对。
RIPEMD-160 is an ISO/IEC standard and has been applied to generate the Bitcoin address with SHA-256. Due to the complex dual-stream structure, the first collision attack on reduced RIPEMD-160 presented by Liu, Mendel and Wang at Asiacrypt 2017 only reaches 30 steps, having a time complexity of. Apart from that, several semi-free-start collision attacks have been published for reduced RIPEMD-160 with the start-from-the-middle method. Inspired from such start-from-the middle structures, we propose two novel efficient collision attack frameworks for reduced RIPEMD-160 by making full use of the weakness of its message expansion. Those two frameworks are called dense-left-and-sparse-right (DLSR) framework and sparse-left-and-dense-right (SLDR) framework. As it turns out, the DLSR framework is more efficient than SLDR framework since one more step can be fully controlled, though with extramemory complexity. To construct the best differential characteristics for the DLSR framework, we carefully build the linearized part of the characteristics and then solve the corresponding nonlinear part using a guess-and-determine approach. Based on the newly discovered differential characteristics, we provide colliding messages pairs for the first practical collision attacks on 30 and 31 (out of 80) steps of RIPEMD-160 with time complexityandrespectively. In addition, benefiting from the partial calculation, we can attack 33 and 34 (out of 80) steps of RIPEMD-160 with time complexityandrespectively. When applying the SLDR framework to the differential characteristic used in the Asiacrypt 2017 paper, we significantly improve the time complexity by a factor of. However, it still cannot compete with the results obtained from the DLSR framework. To the best of our knowledge, these are the best collision attacks on reduced RIPEMD-160 with respect to the number of steps, including the first colliding message pairs for 30 and 31 steps of RIPEMD-160.