CryptoDB
Automating Collision Attacks on RIPEMD-160
NOTE: imports for ToSC and TCHES are no longer functioning.
Authors: |
|
---|---|
Download: | |
Abstract: | 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. |
BibTeX
@article{tosc-2023-33684, title={Automating Collision Attacks on RIPEMD-160}, journal={IACR Transactions on Symmetric Cryptology}, publisher={Ruhr-Universität Bochum}, volume={023 No. 4}, pages={112-142}, url={https://tosc.iacr.org/index.php/ToSC/article/view/11282}, doi={10.46586/tosc.v2023.i4.112-142}, author={Yingxin Li and Fukang Liu and Gaoli Wang}, year=2023 }