Automating Collision Attacks on RIPEMD-160
As an ISO/IEC standard, the hash function RIPEMD-160 has been used to generate the Bitcoin address with SHA-256. However, due to the complex doublebranch structure of RIPEMD-160, the best collision attack only reaches 36 out of 80 steps of RIPEMD-160, and the best semi-free-start (SFS) collision at...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2023-12-01
|
| Series: | IACR Transactions on Symmetric Cryptology |
| Subjects: | |
| Online Access: | https://tosc.iacr.org/index.php/ToSC/article/view/11282 |
| _version_ | 1797399534289027072 |
|---|---|
| author | Yingxin Li Fukang Liu Gaoli Wang |
| author_facet | Yingxin Li Fukang Liu Gaoli Wang |
| author_sort | Yingxin Li |
| collection | DOAJ |
| description |
As an ISO/IEC standard, the hash function RIPEMD-160 has been used to generate the Bitcoin address with SHA-256. However, due to the complex doublebranch structure of RIPEMD-160, the best collision attack only reaches 36 out of 80 steps of RIPEMD-160, and the best semi-free-start (SFS) collision attack only reaches 40 steps. To improve the 36-step collision attack proposed at EUROCRYPT 2023, we explored the possibility of using different message differences to increase the number of attacked steps, and we finally identified one choice allowing a 40-step collision attack. To find the corresponding 40-step differential characteristic, we re-implement the MILP-based method to search for signed differential characteristics with SAT/SMT. As a result, we can find a colliding message pair for 40-step RIPEMD-160 in practical time, which significantly improves the best collision attack on RIPEMD-160. For the best SFS collision attack published at ToSC 2019, we observe that the bottleneck is the probability of the right-branch differential characteristics as they are fully uncontrolled in the message modification. To address this issue, we utilize our SAT/SMT-based tool to search for high-probability differential characteristics for the right branch. Consequently, we can mount successful SFS collision attacks on 41, 42 and 43 steps of RIPEMD-160, thus significantly improving the SFS collision attacks. In addition, we also searched for a 44-step differential characteristic, but the differential probability is too low to allow a meaningful SFS collision attack.
|
| first_indexed | 2024-03-09T01:40:39Z |
| format | Article |
| id | doaj.art-f67e650e66ab4c6fa2450d7235c1016b |
| institution | Directory Open Access Journal |
| issn | 2519-173X |
| language | English |
| last_indexed | 2024-03-09T01:40:39Z |
| publishDate | 2023-12-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | IACR Transactions on Symmetric Cryptology |
| spelling | doaj.art-f67e650e66ab4c6fa2450d7235c1016b2023-12-08T16:13:26ZengRuhr-Universität BochumIACR Transactions on Symmetric Cryptology2519-173X2023-12-012023410.46586/tosc.v2023.i4.112-142Automating Collision Attacks on RIPEMD-160Yingxin Li0Fukang Liu1Gaoli Wang2Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai, ChinaTokyo Institute of Technology, Tokyo, JapanShanghai Key Laboratory of Trustworthy Computing, East China Normal University, Shanghai, China As an ISO/IEC standard, the hash function RIPEMD-160 has been used to generate the Bitcoin address with SHA-256. However, due to the complex doublebranch structure of RIPEMD-160, the best collision attack only reaches 36 out of 80 steps of RIPEMD-160, and the best semi-free-start (SFS) collision attack only reaches 40 steps. To improve the 36-step collision attack proposed at EUROCRYPT 2023, we explored the possibility of using different message differences to increase the number of attacked steps, and we finally identified one choice allowing a 40-step collision attack. To find the corresponding 40-step differential characteristic, we re-implement the MILP-based method to search for signed differential characteristics with SAT/SMT. As a result, we can find a colliding message pair for 40-step RIPEMD-160 in practical time, which significantly improves the best collision attack on RIPEMD-160. For the best SFS collision attack published at ToSC 2019, we observe that the bottleneck is the probability of the right-branch differential characteristics as they are fully uncontrolled in the message modification. To address this issue, we utilize our SAT/SMT-based tool to search for high-probability differential characteristics for the right branch. Consequently, we can mount successful SFS collision attacks on 41, 42 and 43 steps of RIPEMD-160, thus significantly improving the SFS collision attacks. In addition, we also searched for a 44-step differential characteristic, but the differential probability is too low to allow a meaningful SFS collision attack. https://tosc.iacr.org/index.php/ToSC/article/view/11282Semi-free-start collisioncollisionRIPEMD-160SAT/SMT |
| spellingShingle | Yingxin Li Fukang Liu Gaoli Wang Automating Collision Attacks on RIPEMD-160 IACR Transactions on Symmetric Cryptology Semi-free-start collision collision RIPEMD-160 SAT/SMT |
| title | Automating Collision Attacks on RIPEMD-160 |
| title_full | Automating Collision Attacks on RIPEMD-160 |
| title_fullStr | Automating Collision Attacks on RIPEMD-160 |
| title_full_unstemmed | Automating Collision Attacks on RIPEMD-160 |
| title_short | Automating Collision Attacks on RIPEMD-160 |
| title_sort | automating collision attacks on ripemd 160 |
| topic | Semi-free-start collision collision RIPEMD-160 SAT/SMT |
| url | https://tosc.iacr.org/index.php/ToSC/article/view/11282 |
| work_keys_str_mv | AT yingxinli automatingcollisionattacksonripemd160 AT fukangliu automatingcollisionattacksonripemd160 AT gaoliwang automatingcollisionattacksonripemd160 |