Finding Collisions against 4-Round SHA-3-384 in Practical Time
The Keccak sponge function family, designed by Bertoni et al. in 2007, was selected by the U.S. National Institute of Standards and Technology (NIST) in 2012 as the next generation of Secure Hash Algorithm (SHA-3). Due to its theoretical and practical importance, cryptanalysis of SHA-3 has attracte...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2022-09-01
|
| Series: | IACR Transactions on Symmetric Cryptology |
| Subjects: | |
| Online Access: | https://tosc.iacr.org/index.php/ToSC/article/view/9857 |
| _version_ | 1828413163882676224 |
|---|---|
| author | Senyang Huang Orna Agmon Ben-Yehuda Orr Dunkelman Alexander Maximov |
| author_facet | Senyang Huang Orna Agmon Ben-Yehuda Orr Dunkelman Alexander Maximov |
| author_sort | Senyang Huang |
| collection | DOAJ |
| description |
The Keccak sponge function family, designed by Bertoni et al. in 2007, was selected by the U.S. National Institute of Standards and Technology (NIST) in 2012 as the next generation of Secure Hash Algorithm (SHA-3). Due to its theoretical and practical importance, cryptanalysis of SHA-3 has attracted a lot of attention. Currently, the most powerful collision attack on SHA-3 is Jian Guo et al.’s linearisation technique. However, this technique is infeasible for variants with a
smaller input space, such as SHA-3-384.
In this work we improve upon previous results by utilising three ideas which were not used in previous works on collision attacks against SHA-3. First, we use 2-block messages instead of 1-block messages, to reduce constraints and increase flexibility in our solutions. Second, we reduce the connectivity problem into a satisfiability (SAT) problem, instead of applying the linearisation technique. Finally, we propose an efficient deduce-and-sieve algorithm on the basis of two new non-random properties
of the Keccak non-linear layer.
The resulting collision-finding algorithm on 4-round SHA-3-384 has a practical time complexity of 259.64 (and a memory complexity of 245.94). This greatly improves upon the best known collision attack so far: Dinur et al. achieved an impractical 2147 time complexity. Our attack does not threaten the security margin of the SHA-3 hash function. However, the tools developed in this paper could be used to analyse other cryptographic primitives as well as to develop new and faster SAT solvers.
|
| first_indexed | 2024-12-10T13:02:35Z |
| format | Article |
| id | doaj.art-bf271320c8604a4a9e452770be027787 |
| institution | Directory Open Access Journal |
| issn | 2519-173X |
| language | English |
| last_indexed | 2024-12-10T13:02:35Z |
| publishDate | 2022-09-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | IACR Transactions on Symmetric Cryptology |
| spelling | doaj.art-bf271320c8604a4a9e452770be0277872022-12-22T01:47:55ZengRuhr-Universität BochumIACR Transactions on Symmetric Cryptology2519-173X2022-09-012022310.46586/tosc.v2022.i3.239-270Finding Collisions against 4-Round SHA-3-384 in Practical TimeSenyang Huang0Orna Agmon Ben-Yehuda1Orr Dunkelman2Alexander Maximov3Department of Electrical and Information Technology, Lund University, Lund, Sweden; Department of Computer Science, University of Haifa, Haifa, IsraelCaesarea Rothschild Institute for Interdisciplinary Applications of Computer Science (CRI), University of Haifa, Haifa, IsraelDepartment of Computer Science, University of Haifa, Haifa, IsraelEricsson Research, Lund, Sweden The Keccak sponge function family, designed by Bertoni et al. in 2007, was selected by the U.S. National Institute of Standards and Technology (NIST) in 2012 as the next generation of Secure Hash Algorithm (SHA-3). Due to its theoretical and practical importance, cryptanalysis of SHA-3 has attracted a lot of attention. Currently, the most powerful collision attack on SHA-3 is Jian Guo et al.’s linearisation technique. However, this technique is infeasible for variants with a smaller input space, such as SHA-3-384. In this work we improve upon previous results by utilising three ideas which were not used in previous works on collision attacks against SHA-3. First, we use 2-block messages instead of 1-block messages, to reduce constraints and increase flexibility in our solutions. Second, we reduce the connectivity problem into a satisfiability (SAT) problem, instead of applying the linearisation technique. Finally, we propose an efficient deduce-and-sieve algorithm on the basis of two new non-random properties of the Keccak non-linear layer. The resulting collision-finding algorithm on 4-round SHA-3-384 has a practical time complexity of 259.64 (and a memory complexity of 245.94). This greatly improves upon the best known collision attack so far: Dinur et al. achieved an impractical 2147 time complexity. Our attack does not threaten the security margin of the SHA-3 hash function. However, the tools developed in this paper could be used to analyse other cryptographic primitives as well as to develop new and faster SAT solvers. https://tosc.iacr.org/index.php/ToSC/article/view/9857SHA-3 hash functioncollision attackdeduce-and-sieve algorithmSAT solver |
| spellingShingle | Senyang Huang Orna Agmon Ben-Yehuda Orr Dunkelman Alexander Maximov Finding Collisions against 4-Round SHA-3-384 in Practical Time IACR Transactions on Symmetric Cryptology SHA-3 hash function collision attack deduce-and-sieve algorithm SAT solver |
| title | Finding Collisions against 4-Round SHA-3-384 in Practical Time |
| title_full | Finding Collisions against 4-Round SHA-3-384 in Practical Time |
| title_fullStr | Finding Collisions against 4-Round SHA-3-384 in Practical Time |
| title_full_unstemmed | Finding Collisions against 4-Round SHA-3-384 in Practical Time |
| title_short | Finding Collisions against 4-Round SHA-3-384 in Practical Time |
| title_sort | finding collisions against 4 round sha 3 384 in practical time |
| topic | SHA-3 hash function collision attack deduce-and-sieve algorithm SAT solver |
| url | https://tosc.iacr.org/index.php/ToSC/article/view/9857 |
| work_keys_str_mv | AT senyanghuang findingcollisionsagainst4roundsha3384inpracticaltime AT ornaagmonbenyehuda findingcollisionsagainst4roundsha3384inpracticaltime AT orrdunkelman findingcollisionsagainst4roundsha3384inpracticaltime AT alexandermaximov findingcollisionsagainst4roundsha3384inpracticaltime |