Poseidon and Neptune: Gröbner Basis Cryptanalysis Exploiting Subspace Trails
At the current state of the art, algebraic attacks are the most efficient method for finding preimages and collisions for arithmetization-oriented hash functions, such as the closely related primitives Poseidon/Poseidon2 and Neptune. In this paper, we revisit Gröbner basis (GB) attacks that exploit...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2025-06-01
|
| Series: | IACR Transactions on Symmetric Cryptology |
| Subjects: | |
| Online Access: | https://ojs.ub.rub.de/index.php/ToSC/article/view/12244 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850112110666711040 |
|---|---|
| author | Lorenzo Grassi Katharina Koschatko Christian Rechberger |
| author_facet | Lorenzo Grassi Katharina Koschatko Christian Rechberger |
| author_sort | Lorenzo Grassi |
| collection | DOAJ |
| description |
At the current state of the art, algebraic attacks are the most efficient method for finding preimages and collisions for arithmetization-oriented hash functions, such as the closely related primitives Poseidon/Poseidon2 and Neptune. In this paper, we revisit Gröbner basis (GB) attacks that exploit subspace trails to linearize some partial rounds, considering both sponge and compression modes.
Starting from Poseidon’s original security evaluation, we identified some inaccuracies in the model description that may lead to misestimated round requirements. Consequently, we reevaluate and improve the proposed attack strategy. We find that depending on the concrete instantiation, the original security analysis of Poseidon under- or overestimates the number of rounds needed for security. Moreover, we demonstrate that GB attacks leveraging subspace trails can outperform basic GB attacks for Poseidon/Poseidon2 and Neptune.
We propose a variant of the previous attack strategy that exploits a crucial difference between Poseidon/Poseidon2 and Neptune: while Poseidon’s inverse round functions have a high degree, Neptune’s inverse external rounds maintain the same degree as the forward rounds. Using this new model, we demonstrate that Neptune’s security in compression mode cannot be reduced to its security against the Constrained-Input-Constrained-Output (CICO) problem. To the best of our knowledge, this is the first time a concrete example has been provided where finding preimages is easier than solving the corresponding CICO problem.
Our results emphasize the importance of considering the mode of operation in security analysis while confirming the overall security of Poseidon/Poseidon2 and Neptune against the presented algebraic attacks.
|
| format | Article |
| id | doaj-art-b653a14b67694e5ebbefaa0db9b55175 |
| institution | OA Journals |
| issn | 2519-173X |
| language | English |
| publishDate | 2025-06-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | IACR Transactions on Symmetric Cryptology |
| spelling | doaj-art-b653a14b67694e5ebbefaa0db9b551752025-08-20T02:37:28ZengRuhr-Universität BochumIACR Transactions on Symmetric Cryptology2519-173X2025-06-012025210.46586/tosc.v2025.i2.34-86Poseidon and Neptune: Gröbner Basis Cryptanalysis Exploiting Subspace TrailsLorenzo Grassi0Katharina Koschatko1Christian Rechberger2Eindhoven University of Technology, Eindhoven, The Netherlands; Ponos Technology, Zug, SwitzerlandGraz University of Technology, Graz, AustriaGraz University of Technology, Graz, Austria At the current state of the art, algebraic attacks are the most efficient method for finding preimages and collisions for arithmetization-oriented hash functions, such as the closely related primitives Poseidon/Poseidon2 and Neptune. In this paper, we revisit Gröbner basis (GB) attacks that exploit subspace trails to linearize some partial rounds, considering both sponge and compression modes. Starting from Poseidon’s original security evaluation, we identified some inaccuracies in the model description that may lead to misestimated round requirements. Consequently, we reevaluate and improve the proposed attack strategy. We find that depending on the concrete instantiation, the original security analysis of Poseidon under- or overestimates the number of rounds needed for security. Moreover, we demonstrate that GB attacks leveraging subspace trails can outperform basic GB attacks for Poseidon/Poseidon2 and Neptune. We propose a variant of the previous attack strategy that exploits a crucial difference between Poseidon/Poseidon2 and Neptune: while Poseidon’s inverse round functions have a high degree, Neptune’s inverse external rounds maintain the same degree as the forward rounds. Using this new model, we demonstrate that Neptune’s security in compression mode cannot be reduced to its security against the Constrained-Input-Constrained-Output (CICO) problem. To the best of our knowledge, this is the first time a concrete example has been provided where finding preimages is easier than solving the corresponding CICO problem. Our results emphasize the importance of considering the mode of operation in security analysis while confirming the overall security of Poseidon/Poseidon2 and Neptune against the presented algebraic attacks. https://ojs.ub.rub.de/index.php/ToSC/article/view/12244Poseidon/Poseidon2NeptuneGröbner BasisSubspace TrailMode of OperationSponge (CICO) |
| spellingShingle | Lorenzo Grassi Katharina Koschatko Christian Rechberger Poseidon and Neptune: Gröbner Basis Cryptanalysis Exploiting Subspace Trails IACR Transactions on Symmetric Cryptology Poseidon/Poseidon2 Neptune Gröbner Basis Subspace Trail Mode of Operation Sponge (CICO) |
| title | Poseidon and Neptune: Gröbner Basis Cryptanalysis Exploiting Subspace Trails |
| title_full | Poseidon and Neptune: Gröbner Basis Cryptanalysis Exploiting Subspace Trails |
| title_fullStr | Poseidon and Neptune: Gröbner Basis Cryptanalysis Exploiting Subspace Trails |
| title_full_unstemmed | Poseidon and Neptune: Gröbner Basis Cryptanalysis Exploiting Subspace Trails |
| title_short | Poseidon and Neptune: Gröbner Basis Cryptanalysis Exploiting Subspace Trails |
| title_sort | poseidon and neptune grobner basis cryptanalysis exploiting subspace trails |
| topic | Poseidon/Poseidon2 Neptune Gröbner Basis Subspace Trail Mode of Operation Sponge (CICO) |
| url | https://ojs.ub.rub.de/index.php/ToSC/article/view/12244 |
| work_keys_str_mv | AT lorenzograssi poseidonandneptunegrobnerbasiscryptanalysisexploitingsubspacetrails AT katharinakoschatko poseidonandneptunegrobnerbasiscryptanalysisexploitingsubspacetrails AT christianrechberger poseidonandneptunegrobnerbasiscryptanalysisexploitingsubspacetrails |