Chosen-Prefix Collisions on AES-like Hashing
Chosen-prefix collision (CPC) attack was first presented by Stevens, Lenstra and de Weger on MD5 at Eurocrypt 2007. A CPC attack finds a collision for any two chosen prefixes, which is a stronger variant of collision attack. CPCs are naturally harder to construct but have larger practical impact th...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2024-12-01
|
| Series: | IACR Transactions on Symmetric Cryptology |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/ToSC/article/view/11951 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1846116546750971904 |
|---|---|
| author | Shiyao Chen Xiaoyang Dong Jian Guo Tianyu Zhang |
| author_facet | Shiyao Chen Xiaoyang Dong Jian Guo Tianyu Zhang |
| author_sort | Shiyao Chen |
| collection | DOAJ |
| description |
Chosen-prefix collision (CPC) attack was first presented by Stevens, Lenstra and de Weger on MD5 at Eurocrypt 2007. A CPC attack finds a collision for any two chosen prefixes, which is a stronger variant of collision attack. CPCs are naturally harder to construct but have larger practical impact than (identical-prefix) collisions, as seen from the series of previous works on MD5 by Stevens et al. and SHA-1 by Leurent and Peyrin. Despite its significance, the resistance of CPC attacks has not been studied on AES-like hashing.
In this work, we explore CPC attacks on AES-like hashing following the framework practiced on MD5 and SHA-1. Instead of the message modification technique developed for MD-SHA family, we opt for related-key rebound attack to construct collisions for AES-like hashing in view of its effectiveness. We also note that the CPC attack framework can be exploited to convert a specific class of one-block free-start collisions into two-block collisions, which sheds light on the importance of free-start collisions. As a result, we present the first CPC attacks on reduced Whirlpool, Saturnin-hash and AES-MMO/MP in classic and quantum settings, and extend the collision attack on Saturnin-hash from 5 to 6 rounds in the classic setting. As an independent contribution, we improve the memoryless algorithm of solving 3-round inbound phase by Hosoyamada and Sasaki at Eurocrpyt 2020, which leads to improved quantum attacks on Whirlpool. Notably, we find the first 6-round memoryless quantum collision attack on Whirlpool better than generic CNS collision finding algorithm when exponential-size qRAM is not available but exponential-size classic memory is available.
|
| format | Article |
| id | doaj-art-d9d7f312a0c24382baf70b587b2a49c4 |
| institution | Kabale University |
| issn | 2519-173X |
| language | English |
| publishDate | 2024-12-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | IACR Transactions on Symmetric Cryptology |
| spelling | doaj-art-d9d7f312a0c24382baf70b587b2a49c42024-12-18T16:49:37ZengRuhr-Universität BochumIACR Transactions on Symmetric Cryptology2519-173X2024-12-012024410.46586/tosc.v2024.i4.64-96Chosen-Prefix Collisions on AES-like HashingShiyao Chen0Xiaoyang Dong1Jian Guo2Tianyu Zhang3Digital Trust Centre, Nanyang Technological University, Singapore, SingaporeState Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, People’s Republic of China; Institute for Network Sciences and Cyberspace, BNRist, Tsinghua University, Beijing, People’s Republic of China; Zhongguancun Laboratory, Beijing, People’s Republic of ChinaDivision of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, SingaporeDivision of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore Chosen-prefix collision (CPC) attack was first presented by Stevens, Lenstra and de Weger on MD5 at Eurocrypt 2007. A CPC attack finds a collision for any two chosen prefixes, which is a stronger variant of collision attack. CPCs are naturally harder to construct but have larger practical impact than (identical-prefix) collisions, as seen from the series of previous works on MD5 by Stevens et al. and SHA-1 by Leurent and Peyrin. Despite its significance, the resistance of CPC attacks has not been studied on AES-like hashing. In this work, we explore CPC attacks on AES-like hashing following the framework practiced on MD5 and SHA-1. Instead of the message modification technique developed for MD-SHA family, we opt for related-key rebound attack to construct collisions for AES-like hashing in view of its effectiveness. We also note that the CPC attack framework can be exploited to convert a specific class of one-block free-start collisions into two-block collisions, which sheds light on the importance of free-start collisions. As a result, we present the first CPC attacks on reduced Whirlpool, Saturnin-hash and AES-MMO/MP in classic and quantum settings, and extend the collision attack on Saturnin-hash from 5 to 6 rounds in the classic setting. As an independent contribution, we improve the memoryless algorithm of solving 3-round inbound phase by Hosoyamada and Sasaki at Eurocrpyt 2020, which leads to improved quantum attacks on Whirlpool. Notably, we find the first 6-round memoryless quantum collision attack on Whirlpool better than generic CNS collision finding algorithm when exponential-size qRAM is not available but exponential-size classic memory is available. https://tches.iacr.org/index.php/ToSC/article/view/11951Chosen-Prefix CollisionRelated-Key Rebound AttackQuantum CryptanalysisWhirlpoolSaturnin-hashAES-MMO/MP |
| spellingShingle | Shiyao Chen Xiaoyang Dong Jian Guo Tianyu Zhang Chosen-Prefix Collisions on AES-like Hashing IACR Transactions on Symmetric Cryptology Chosen-Prefix Collision Related-Key Rebound Attack Quantum Cryptanalysis Whirlpool Saturnin-hash AES-MMO/MP |
| title | Chosen-Prefix Collisions on AES-like Hashing |
| title_full | Chosen-Prefix Collisions on AES-like Hashing |
| title_fullStr | Chosen-Prefix Collisions on AES-like Hashing |
| title_full_unstemmed | Chosen-Prefix Collisions on AES-like Hashing |
| title_short | Chosen-Prefix Collisions on AES-like Hashing |
| title_sort | chosen prefix collisions on aes like hashing |
| topic | Chosen-Prefix Collision Related-Key Rebound Attack Quantum Cryptanalysis Whirlpool Saturnin-hash AES-MMO/MP |
| url | https://tches.iacr.org/index.php/ToSC/article/view/11951 |
| work_keys_str_mv | AT shiyaochen chosenprefixcollisionsonaeslikehashing AT xiaoyangdong chosenprefixcollisionsonaeslikehashing AT jianguo chosenprefixcollisionsonaeslikehashing AT tianyuzhang chosenprefixcollisionsonaeslikehashing |