Analysis of RIPEMD-160: New Collision Attacks and Finding Characteristics with MILP
Analysis of RIPEMD-160: New Collision Attacks and Finding Characteristics with MILP
复制标题
DOI：
10.1007/978-3-031-30634-1_7
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Fukang Liu;Gaoli Wang;Santanu Sarkar;Ravi Anand;W. Meier;Yingxin Li;Takanori Isobe
中科院分区：
文献类型：
--
作者：
Fukang Liu;Gaoli Wang;Santanu Sarkar;Ravi Anand;W. Meier;Yingxin Li;Takanori Isobe
哈希函数 RIPEMD-160 是 ISO/IEC 标准，与 SHA-256 一起用于生成比特币地址。尽管 MD-SHA 哈希家族中的许多哈希函数已被破坏，但 RIPEMD-160 仍然是安全的，并且最佳碰撞攻击只能达到 80 轮中的 34 轮，这一点已在 CRYPTO 2019 上发布。在本文中，我们提出了一种针对 RIPEMD-160 的新碰撞攻击，其时间复杂度最高可达 36 轮。这种新的攻击是通过选择消息差异的新策略和同时处理两个分支上的差异条件的新技术来促进的。此外，与之前关于 RIPEMD-160 的所有工作不同，我们利用基于 MILP 的方法来搜索差分特征，其中我们构建了一个模型，通过其轮函数准确地描述有符号差分转换。据我们所知，这是第一个针对 MD-SHA 哈希系列的有符号差转换的模型。事实上，我们更有动力设计这个模型，因为许多搜索这种差异特征的自动工具不是公开可用的，并且从头开始实现它们太耗时且困难。因此，我们期望这可以成为未来研究的替代简单工具，只需要写下一些简单的线性不等式。
The hash function RIPEMD-160 is an ISO/IEC standard and is being used to generate the bitcoin address together with SHA-256. Despite the fact that many hash functions in the MD-SHA hash family have been broken, RIPEMD-160 remains secure and the best collision attack could only reach up to 34 out of 80 rounds, which was published at CRYPTO 2019. In this paper, we propose a new collision attack on RIPEMD-160 that can reach up to 36 rounds with time complexity. This new attack is facilitated by a new strategy to choose the message differences and new techniques to simultaneously handle the differential conditions on both branches. Moreover, different from all the previous work on RIPEMD-160, we utilize a MILP-based method to search for differential characteristics, where we construct a model to accurately describe the signed difference transitions through its round function. As far as we know, this is the first model targeting the signed difference transitions for the MD-SHA hash family. Indeed, we are more motivated to design this model by the fact that many automatic tools to search for such differential characteristics are not publicly available and implementing them from scratch is too time-consuming and difficult. Hence, we expect that this can be an alternative easy tool for future research, which only requires to write down some simple linear inequalities.