Paper 2022/134

Functional Cryptanalysis: Application to reduced-round Xoodoo

Emanuele Bellini and Rusydi H. Makarim


This paper proposes functional cryptanalysis, a flexible and versatile approach to analyse symmetric-key primitives with two primary features. Firstly, it is a generalization of multiple attacks including (but not limited to) differential, rotational and rotational-xor cryptanalysis. Secondly, it is a theoretical framework that unifies all of the aforementioned cryptanalysis techniques and at the same time opens up possibilities for the development of new cryptanalytic approaches. The main idea of functional cryptanalysis is the usage of binary relations in the form of functions, hence the name functional, instead of binary operations like in a classical settings of "differential"-like cryptanalysis. We establish the theoretical foundations of functional cryptanalysis from standard terminologies. This work also presents an interpretation of functional cryptanalysis from the point of view of commutative algebra. In particular, we exhibit an algorithm to compute the functional probability (hence differential, rotational, and rotational-xor probability) using Grobner bases. We demonstrate the applicability of functional cryptanalysis against reduced-round Xoodoo and compare it against the best differential. To avoid dealing with invalid differential trails, we propose a method to construct a valid differential trail using Satisfiability Modulo Theory (SMT). To the best of our knowledge, this is the first time the SMT model is used to construct a valid differential while previous approaches rely on Mixed-Integer Linear Programming (MILP) model. Lastly, we remark that the use of non-translation functionals shares analogous advantages and limitations with the use of nonlinear approximations in linear cryptanalysis.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Functional CryptanalysisDifferential CryptanalysisRotational CryptanalysisRotational-XOR CryptanalysisXoodooSMTGrobner bases
Contact author(s)
rusydi hasan @ gmail com
2022-02-09: received
Short URL
Creative Commons Attribution


      author = {Emanuele Bellini and Rusydi H.  Makarim},
      title = {Functional Cryptanalysis: Application to reduced-round Xoodoo},
      howpublished = {Cryptology ePrint Archive, Paper 2022/134},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.