Paper 2019/112

Variable Elimination - a Tool for Algebraic Cryptanalysis

Bjørn Greve, Øyvind Ytrehus, and Håvard Raddum

Abstract

Techniques for eliminating variables from a system of nonlinear equations are used to find solutions of the system. We discuss how these methods can be used to attack certain types of symmetric block ciphers, by solving sets of equations arising from known plain text attacks. The systems of equations corresponding to these block ciphers have the characteristics that the solution is determined by a small subset of the variables (i.e., the secret key), and also that it is known that there always exists at least one solution (again corresponding to the key which is actually used in the encryption). It turns out that some toy ciphers can be solved simpler than anticipated by this method, and that the method can take advantage of overdetermined systems.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
XLre-linearizationsystems of equationselimination of variablesblock ciphers
Contact author(s)
bjorn greve @ uib no
haavardr @ simula no
History
2019-02-06: received
Short URL
https://ia.cr/2019/112
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/112,
      author = {Bjørn Greve and Øyvind Ytrehus and Håvard Raddum},
      title = {Variable Elimination - a Tool for Algebraic Cryptanalysis},
      howpublished = {Cryptology ePrint Archive, Paper 2019/112},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/112}},
      url = {https://eprint.iacr.org/2019/112}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.