New Algebraic Attacks on Grendel with the Strategy of Bypassing SPN Steps

QIAO Wenxiao; SUN Siwei; HU Lei

doi:10.23919/cje.2023.00.127

Article Contents

Article Navigation > Chinese Journal of Electronics > 2024 > Uncorrected proof

Wenxiao QIAO, Siwei SUN, and Lei HU, “New Algebraic Attacks on Grendel with the Strategy of Bypassing SPN Steps,” Chinese Journal of Electronics, vol. 33, no. 3, pp. 1–10, 2024 doi: 10.23919/cje.2023.00.127

Citation:

Wenxiao QIAO, Siwei SUN, and Lei HU, “New Algebraic Attacks on Grendel with the Strategy of Bypassing SPN Steps,” Chinese Journal of Electronics, vol. 33, no. 3, pp. 1–10, 2024 doi: 10.23919/cje.2023.00.127

Citation:

PDF( 3684 KB)

New Algebraic Attacks on Grendel with the Strategy of Bypassing SPN Steps

doi: 10.23919/cje.2023.00.127

QIAO Wenxiao^{1, 2
,},
SUN Siwei^{3, 4
,
,},
HU Lei^{1, 2
,}

1.
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100085, China
2.
School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China
3.
School of Cryptology, University of Chinese Academy of Sciences, Beijing 100049, China
4.
State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China

More Information

Author Bio:
Wenxiao QIAO is a Ph.D. candidate of Institute of Information Engineering, Chinese Academy of Sciences. Her research interests include Symmetric cryptanalysis and Design. (Email: qiaowenxiao@iie.ac.cn)

Siwei SUN received the Ph.D. degree from Chinese Academy of Sciences in 2013. He is a Professor in School of Cryptology, University of Chinese Academy of Sciences. His research interests include Symmetric cryptanalysis and Design. (Email: siweisun.isaac@gmail.com)

Lei HU received the Ph.D. degree from Chinese Academy of Sciences in 1994. He is a Professor in Institute of Information Engineering, Chinese Academy of Sciences. His research interests include basic theory of applications of pseudorandom sequences and arrays, analysis of cryptographic algorithms and theoretical cryptography. (Email: hulei@iie.ac.cn)
Corresponding author: Email: siweisun.isaac@gmail.com
Received Date: 2023-04-13
Accepted Date: 2023-08-07

Available Online: 2023-09-12

Abstract

Abstract

The rapid development of modern cryptographic applications such as zero-knowledge, secure multi-party computation, fully homomorphic encryption has motivated the design of new so-called arithmetization-oriented symmetric primitives. As designing ciphers in this domain is relatively new and not well-understood, the security of these new ciphers remains to be completely assessed. In this paper, we revisit the security analysis of arithmetization-oriented cipher Grendel. Grendel uses the Legendre symbol as a component, which is tailored specifically for the use in zero-knowledge and efficiently-varifiable proof systems. At FSE 2022, the first preimage attack on some original full GrendelHash instances was proposed. As a countermeasure, the designer adds this attack into the security analysis and updates the formula to derive the secure number of rounds. In our work, we present new algebraic attacks on GrendelHash. For the preimage attack, we can reduce the complexity or attack one more round than previous attacks for some instances. In addition, we present the first collision attack on some round-reduced instances by solving the constrained input/constrained output problem for the underlying permutations.
- Grendel,
- Solving univariate equation,
- Bypassing substitution-permutation networks (SPN) steps,
- Preimage attack,
- Collision attack

1It was published on November 1st 2021 at https://www.zkhashbounties.info/.

FullText(HTML)

References(28)

References

[1]	M. R. Albrecht, C. Rechberger, T. Schneider, et al., “Ciphers for MPC and FHE,” in Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, pp.430–454, 2015.
[2]	P. Méaux, A. Journault, F. X. Standaert, et al., “Towards stream ciphers for efficient FHE with low-noise ciphertexts,” in Proceedings of the 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, pp.311–343, 2016.
[3]	A. Canteaut, S. Carpov, C. Fontaine, et al., “Stream ciphers: A practical solution for efficient homomorphic-ciphertext compression,” Journal of Cryptology, vol. 31, no. 3, pp. 885–916, 2018. doi: 10.1007/s00145-017-9273-9
[4]	C. Dobraunig, M. Eichlseder, L. Grassi, et al., “Rasta: A cipher with low ANDdepth and few ANDs per bit,” in Proceedings of the 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, pp.662–692, 2018.
[5]	M. Albrecht, L. Grassi, C. Rechberger, et al., “MiMC: Efficient encryption and cryptographic hashing with minimal multiplicative complexity,” in Proceedings of the 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, pp.191–219, 2016.
[6]	M. R. Albrecht, L. Grassi, L. Perrin, et al., “Feistel structures for MPC, and more, ” in Proceedings of the 24th European Symposium on Research in Computer Security, Luxembourg, pp.151–171, 2019.
[7]	C. Dobraunig, L. Grassi, A. Guinet, et al., “CIMINION: Symmetric encryption based on toffoli-gates over large finite fields,” in Proceedings of the 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, pp. 3–34, 2021.
[8]	L. Grassi, D. Khovratovich, C. Rechberger, et al., “Poseidon: A new hash function for zero-knowledge proof systems,” in Proceedings of the 30th USENIX Security Symposium, online, pp.519–535, 2021.
[9]	L. Grassi, S. Onofri, M. Pedicini, et al., “Invertible quadratic non-linear layers for MPC-/FHE-/ZK-friendly schemes over $\mathbb{F}_p^n $: Application to poseidon,” IACR Transactions on Symmetric Cryptology, vol. 2022, no. 3, pp. 20–72, 2022. doi: 10.46586/tosc.v2022.i3.20-72
[10]	A. Aly, T. Ashur, E. Ben-Sasson, et al., “Design of symmetric-key primitives for advanced cryptographic protocols,” IACR Transactions on Symmetric Cryptology, vol. 2020, no. 3, pp. 1–45, 2020. doi: 10.13154/tosc.v2020.i3.1-45
[11]	A. Szepieniec, T. Ashur, and S. Dhooghe, “Rescue-prime: A standard specification (SoK),” Available at: https://eprint.iacr.org/2020/1143, 2020.)
[12]	A. Szepieniec, “On the use of the Legendre symbol in symmetric cipher design, ” Available at: https://eprint.iacr.org/2021/984, 2021.
[13]	C. Dobraunig, M. Eichlseder, and F. Mendel, “Higher-order cryptanalysis of LowMC,” in Proceedings of the 18th International Conference, Seoul, South Korea, pp. 87–101, 2016.
[14]	I. Dinur, Y. W. Liu, W. Meier, et al., “Optimized interpolation attacks on LowMC,” in Proceedings of the 21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, pp. 535–560, 2015.
[15]	C. Rechberger, H. Soleimany, and T. Tiessen, “Cryptanalysis of low-data instances of full LowMCv2,” IACR Transactions on Symmetric Cryptology, vol. 2018, no. 3, pp. 163–181, 2018. doi: 10.13154/tosc.v2018.i3.163-181
[16]	F. K. Liu, T. Isobe, and W. Meier, “Cryptanalysis of full LowMC and LowMC-M with algebraic techniques,” in Proceedings of the 41st Annual International Cryptology Conference, Virtual Event, pp.368–401, 2021.
[17]	I. Dinur, “Cryptanalytic applications of the polynomial method for solving multivariate equation systems over GF(2),” in Proceedings of the 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, pp. 374–403, 2021.
[18]	F. K. Liu, S. Sarkar, G. L. Wang, et al., “Algebraic meet-in-the-middle attack on LowMC,” in Proceedings of the 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, China, pp. 225–255, 2022.
[19]	F. K. Liu, W. Meier, S. Sarkar, et al., “New low-memory algebraic attacks on LowMC in the picnic setting,” IACR Transactions on Symmetric Cryptology, vol. 2022, no. 3, pp. 102–122, 2022. doi: 10.46586/tosc.v2022.i3.102-122
[20]	L. Grassi, D. Khovratovich, R. Lüftenegger, et al., “Reinforced concrete: A fast hash function for verifiable computation,” in Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, Los Angeles, CA, USA, pp. 1323–1335, 2022.
[21]	A. Bariant, C. Bouvier, G. Leurent, et al., “Algebraic attacks against some arithmetization-oriented primitives,” IACR Transactions on Symmetric Cryptology, vol. 2022, no. 3, pp. 73–101, 2022. doi: 10.46586/tosc.v2022.i3.73-101
[22]	G. Bertoni, J. Daemen, M. Peeters, et al., “Sponge functions,” Available at: https://keccak.team/files/SpongeFunctions.pdf, 2007.
[23]	G. Bertoni, J. Daemen, M. Peeters, et al., “On the indifferentiability of the sponge construction,” in Proceedings of the 27th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, pp.181–197, 2008.
[24]	G. Bertoni, J. Daemen, M. Peeters, et al., “Cryptographic sponge functions,” Available at: https://keccak.team/files/CSF-0.1.pdf, 2011-01-14.
[25]	L. Grassi, D. Khovratovich, S. Rønjom, et al., “The Legendre symbol and the modulo-2 operator in symmetric schemes over $\mathbb{F}_p^n $: Preimage Attack on Full Grendel,” IACR Transactions on Symmetric Cryptology, vol. 2022, no. 1, pp. 5–37, 2022. doi: 10.46586/tosc.v2022.i1.5-37
[26]	V. Rijmen, J. Daemen, B. Preneel, et al., “The cipher SHARK,” in Proceedings of the 3rd International Workshop on Fast Software Encryption, Cambridge, UK, pp.99–111, 1996.
[27]	J. von zur Gathen and J. Gerhard, Modern Computer Algebra, 3rd ed., Cambridge University Press, New York, NY, USA, pp.75-76, 2013.
[28]	R. P. Brent and P. Zimmermann, “An O(M(n)logn) algorithm for the Jacobi symbol,” in Proceedings of the 9th International Algorithmic Number Theory Symposium, Nancy, France, pp.83–95, 2010.