Practical Preimage Attacks on 3-Round Keccak-256 and 4-Round Keccak[r=640, c=160]
Recently, linear structures and algebraic attacks have been widely used in preimage attacks on round-reduced Keccak. Inherited by pioneers’ work, we make some improvements for 3-round Keccak-256 and 4-round Keccak[r=640, c=160]. For 3-round Keccak-256, we introduce a three-stage model to deal with...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2025-03-01
|
| Series: | IACR Transactions on Symmetric Cryptology |
| Subjects: | |
| Online Access: | https://tosc.iacr.org/index.php/ToSC/article/view/12079 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850027984893771776 |
|---|---|
| author | Xiaoen Lin Le He Hongbo Yu |
| author_facet | Xiaoen Lin Le He Hongbo Yu |
| author_sort | Xiaoen Lin |
| collection | DOAJ |
| description |
Recently, linear structures and algebraic attacks have been widely used in preimage attacks on round-reduced Keccak. Inherited by pioneers’ work, we make some improvements for 3-round Keccak-256 and 4-round Keccak[r=640, c=160]. For 3-round Keccak-256, we introduce a three-stage model to deal with the unsatisfied restrictions while bringing more degrees of freedom at the same time. Besides, we show that guessing values for different variables will result in different complexity of solving time. With these techniques, the guessing times can be decreased to 252, and the solving time for each guess can be decreased to around 25.2 3-round Keccak calls. As a result, the complexity of finding a preimage for 3-round Keccak-256 can be decreased to around 257.2. For 4-round Keccak[r=640, c=160], an instance of the Crunchy Contest, we use some techniques to save degrees of freedom and make better linearization. Based on these techniques, we build an MILP model and obtain an attack with better complexity of around 260.9. The results of 3-round Keccak-256 and 4-round Keccak[r=640, c=160] are verified with real examples.
|
| format | Article |
| id | doaj-art-f96a68e071ef4da9840ad931c8d0e8da |
| institution | DOAJ |
| issn | 2519-173X |
| language | English |
| publishDate | 2025-03-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | IACR Transactions on Symmetric Cryptology |
| spelling | doaj-art-f96a68e071ef4da9840ad931c8d0e8da2025-08-20T02:59:57ZengRuhr-Universität BochumIACR Transactions on Symmetric Cryptology2519-173X2025-03-012025110.46586/tosc.v2025.i1.328-356Practical Preimage Attacks on 3-Round Keccak-256 and 4-Round Keccak[r=640, c=160]Xiaoen Lin0Le He1Hongbo Yu2Department of Computer Science and Technology, Tsinghua University, Beijing, 100084, People’s Republic of ChinaSchool of Cyber Engineering, Xidian University, Xi’an, 710126, People’s Republic of ChinaDepartment of Computer Science and Technology, Tsinghua University, Beijing, 100084, People’s Republic of China; Zhongguancun Laboratory, Beijing, People’s Republic of China; State Key Laboratory of Cryptography and Digital Economy Security, Tsinghua University, Beijing, 100084, People’s Republic of China Recently, linear structures and algebraic attacks have been widely used in preimage attacks on round-reduced Keccak. Inherited by pioneers’ work, we make some improvements for 3-round Keccak-256 and 4-round Keccak[r=640, c=160]. For 3-round Keccak-256, we introduce a three-stage model to deal with the unsatisfied restrictions while bringing more degrees of freedom at the same time. Besides, we show that guessing values for different variables will result in different complexity of solving time. With these techniques, the guessing times can be decreased to 252, and the solving time for each guess can be decreased to around 25.2 3-round Keccak calls. As a result, the complexity of finding a preimage for 3-round Keccak-256 can be decreased to around 257.2. For 4-round Keccak[r=640, c=160], an instance of the Crunchy Contest, we use some techniques to save degrees of freedom and make better linearization. Based on these techniques, we build an MILP model and obtain an attack with better complexity of around 260.9. The results of 3-round Keccak-256 and 4-round Keccak[r=640, c=160] are verified with real examples. https://tosc.iacr.org/index.php/ToSC/article/view/12079KeccakSHA-3Preimage attackLinear structure |
| spellingShingle | Xiaoen Lin Le He Hongbo Yu Practical Preimage Attacks on 3-Round Keccak-256 and 4-Round Keccak[r=640, c=160] IACR Transactions on Symmetric Cryptology Keccak SHA-3 Preimage attack Linear structure |
| title | Practical Preimage Attacks on 3-Round Keccak-256 and 4-Round Keccak[r=640, c=160] |
| title_full | Practical Preimage Attacks on 3-Round Keccak-256 and 4-Round Keccak[r=640, c=160] |
| title_fullStr | Practical Preimage Attacks on 3-Round Keccak-256 and 4-Round Keccak[r=640, c=160] |
| title_full_unstemmed | Practical Preimage Attacks on 3-Round Keccak-256 and 4-Round Keccak[r=640, c=160] |
| title_short | Practical Preimage Attacks on 3-Round Keccak-256 and 4-Round Keccak[r=640, c=160] |
| title_sort | practical preimage attacks on 3 round keccak 256 and 4 round keccak r 640 c 160 |
| topic | Keccak SHA-3 Preimage attack Linear structure |
| url | https://tosc.iacr.org/index.php/ToSC/article/view/12079 |
| work_keys_str_mv | AT xiaoenlin practicalpreimageattackson3roundkeccak256and4roundkeccakr640c160 AT lehe practicalpreimageattackson3roundkeccak256and4roundkeccakr640c160 AT hongboyu practicalpreimageattackson3roundkeccak256and4roundkeccakr640c160 |