Skip to main navigation menu Skip to main content Skip to site footer

Vol. 51 No. 3–4 (2025)
Serdica Mathematical Journal

Articles

Algebraic cryptanalysis of symmetric ciphers: modeling and multistep solving strategies

https://doi.org/10.55630/serdica.2025.51.419-442

Published 23-12-2025

  • Roberto La Scala
    • ,
  • Sharwan Tiwari

Roberto La Scala
Università degli Studi di Bari “Aldo Moro”

Sharwan Tiwari
Technology Innovation Institute, Abu Dhabi

Abstract

This paper presents a systematized study of algebraic cryptanalysis for symmetric ciphers. It explains how encryption algorithms can be expressed as systems of polynomial equations over finite fields and analyzed using algebraic and logical solvers. The study begins
by detailing block and stream ciphers through the lens of difference algebra, interpreting state updates and key additions as polynomial mappings. It then outlines the main solving strategies used in algebraic cryptanalysis, starting from Gröbner-basis and SAT approaches and progressing to hybrid solving. It next focuses on multistep and oracle-based strategies, which adjust variable guessing according to the hardness of each instance. These strategies extend classical hybrid attacks and make the solving process more  efficient. Four case studies on Bluetooth E0, Bivium, Trivium, and Aradi illustrate these ideas. Each example shows how algebraic  modeling and adaptive solving reveal structural properties and solvability thresholds in the cipher design. The results show that multistep reasoning reduces computational effort compared with static hybrids and provides a unified way to understand algebraic complexity in both stream and block ciphers.

2020 Mathematics Subject Classification:

94A60, 68W30, 13P10

Keywords

algebraic cryptanalysis, Gröbner bases, hybrid and multistep strategies, stream and block ciphers

Full text

Author Details

Roberto La Scala

Dipartimento di Matematica
Università degli Studi di Bari “Aldo Moro”
Via Orabona 4, 70125 Bari, Italy
e-mail: roberto.lascala@uniba.it

Sharwan Tiwari

Cryptography Research Centre
Technology Innovation Institute
Abu Dhabi, United Arab Emirates
e-mail: sharwan.tiwari@tii.ae

References

  1. W. W. Adams, P. Loustaunau. An introduction to Gröbner bases. Grad. Stud. Math., vol. 3. Providence, RI, American Mathematical Society, 1994.
  2. G. V. Bard. Algebraic Cryptanalysis. Dordrecht, Springer, 2009.
  3. L. Bettale, J.-C. Faugère, L. Perret. Hybrid approach for solving multivariate systems over finite fields. J. Math. Cryptol. 3, 3 (2009), 177–197.
  4. Bluetooth Special Interest Group (SIG). Bluetooth Core Specification, Revision 5.2, 2019. Available at: https://www.bluetooth.com/specifications/bluetooth-core-specification.
  5. E. Bellini, M. Rachidi, R. Rohit, S. K. Tiwari. On the structural properties of Toffoli gate composition in Aradi: implications for algebraic distinguishers. Lecture Notes in Comput. Sci., vol. 15826. Cham, Springer, 2025, 400–425.
  6. E. Bellini, M. Rachidi, R. Rohit, S. K. Tiwari. Mind the Composition of Toffoli Gates: Structural Algebraic Distinguishers of Aradi. Cryptology ePrint Archive, Paper 2024/1559, 2024, https://eprint.iacr.org/2024/
  7. E. Bellini, M. Formenti, D. G´erault et al. CLAASPing ARADI: Automated Analysis of the ARADI Block Cipher. In: Progress in Cryptology – INDOCRYPT 2024, Part II. Lecture Notes in Comput. Sci., vol 15496. Cham, Springer, 2025, 90–113, https://doi.org/10.1007/978-3-031-80311-6_5.
  8. L. Bettale, J.-C. Faug´ere, L. Perret. Solving polynomial systems over finite fields: improved analysis of the hybrid approach. ISSAC 2012—Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation. New York, Association for Computing Machinery (ACM), 2012, 67–74.
  9. W. Bosma, J. J. Cannon, C. Playoust. The Magma algebra system. I. The user language. J. Symbolic Comput. 24, 3–4 (1997), 235–265.
  10. R. M. Cohn. Difference Algebra. New York–London–Sydney, Interscience Publishers, John Wiley & Sons, 1965.
  11. N. Courtois, A. Klimov, J. Patarin, A. Shamir. Efficient algorithms for solving overdefined systems of multivariate polynomial equations. Advances in Cryptology—EUROCRYPT 2000 (Bruges). Lecture Notes in Comput. Sci., Vol. 1807. Berlin, Springer-Verlag, 2000, 392–407.
  12. N. T. Courtois, G. V. Bard. Algebraic Cryptanalysis of the data encryption standard. Cryptography and Coding, Lecture Notes in Comput. Sci., Vol. 4887. Berlin, Springer, 2007, 152–169.
  13. N. T. Courtois, J. Pieprzyk. Cryptanalysis of block ciphers with overdefined systems of equations. Advances in cryptology—ASIACRYPT 2002. Lecture Notes in Comput. Sci., Vol. 2501. Berlin, Springer-Verlag, 2002, 267–287
  14. C. De Cannière, B. Preneel. Trivium Specifications. eSTREAM – ECRYPT Stream Cipher Project. Available at: https://www.ecrypt.eu.org/stream/triviumpf.html.
  15. T. Eibach, G. Völkel, E. Pilz. Optimising Gr¨obner Bases on Bivium. Math. Comput. Sci. 3, 2 (2010), 159–172.
  16. J.-C. Faugère. A new efficient algorithm for computing Gröbner bases (F4). J. Pure Appl. Algebra 139, 1–3 (1999), 61–88.
  17. J.-C. Faugère. A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation. New York, Association for Computing Machinery (ACM), 2002, 75–83.
  18. M. R. Garey, D. S. Johnson. Computers and intractability: A guide to the theory of NP-completeness. Ser. Books Math. Sci. San Francisco, CA, W. H. Freeman and Co., 1979.
  19. V. Gerdt, R. La Scala. Noetherian quotients of the algebra of partial difference polynomials and Gröbner bases of symmetric ideals. J. Algebra 423 (2015), 1233–1261.
  20. P. Greene, M. Motley, B. Weeks. ARADI and LLAMA: Low-Latency Cryptography for Memory Encryption. Cryptology ePrint Archive, Paper 2024/1240, 2024, https://eprint.iacr.org/2024/1240
  21. A. Klein. Stream Ciphers. London, Springer, 2013.
  22. R. La Scala, S. K. Tiwari. Stream/block ciphers, difference equations and algebraic attacks. J. Symbolic Comput. 109 (2022), 177–198.
  23. R. La Scala, S. Polese, S. K. Tiwari, A. Visconti. An algebraic attack to the Bluetooth stream cipher E0. Finite Fields Appl. 84 (2022), Paper No. 102102, 29 pp.
  24. R. La Scala, F. Pintore, S. K. Tiwari, A. Visconti. A multistep strategy for polynomial system solving over finite fields and a new algebraic attack on the stream cipher Trivium. Finite Fields Appl. 98 (2024), Paper No. 102452, 33 pp.
  25. R. La Scala, S. K. Tiwari. Oracle-Based Multistep Strategy for Solving Polynomial Systems Over Finite Fields and Algebraic Cryptanalysis of the Aradi Cipher. Cryptology ePrint Archive, Paper 2025/1097, 2025, https://eprint.iacr.org/2025/1097
  26. R. La Scala, A. N. Zubkov. Donkin–Koppinen filtration for general linear supergroups. Algebr. Represent. Theory 15, 5 (2012), 883–899.
  27. F. Massacci, L. Marraro. Logical cryptanalysis as a SAT problem. J. Automat. Reason. 24, 1–2 (2000), 165–203.
  28. S. Ramos-Calderer, C. Bravo-Prieto, R. Lin et al. Solving systems of Boolean multivariate equations with quantum annealing. Physical Review Research, 4, 1 (2022), paper No. 013096, 9 pp. https://doi.org/10.1103/PhysRevResearch.4.013096.
  29. J. F. Ritt, H. W. Raudenbush. Ideal theory and algebraic difference equations. Trans. Amer. Math. Soc. 46 (1939), 445–452.
  30. Y. Shaked, A. Wool. Cryptanalysis of the Bluetooth E0 Cipher Using OBDDs. In: Information Security. ISC 2006. Lecture Notes in Comput. Sci., vol 4176. Berlin, Heidelberg, Springer, 2006, 187–202, https://doi.org/10.1007/11836810_14.
  31. C. E. Shannon. Communication theory of secrecy systems. Bell System Tech. J. 28 (1949), 656–715.
  32. W. Decker, G.-M. Greuel, G. Pfister, H. Schönemann. Singular 4-1-2 — A computer algebra system for polynomial computations, 2019, http://www.singular.uni-kl.de.
  33. M. Soos M. CryptoMiniSat 5: An Advanced SAT Solver, 2021. Available at: https://www.msoos.org/cryptominisat5.