Paper 2018/807

On the Existence of Non-Linear Invariants and Algebraic Polynomial Constructive Approach to Backdoors in Block Ciphers

Nicolas T. Courtois

Abstract

In this paper we study cryptanalysis with non-linear polynomials cf. Eurocrypt’95 (adapted to Feistel ciphers at Crypto 2004). Previously researchers had serious difficulties in making such attacks work. Even though this is less general than a general space partitioning attack (FSE’97), a polynomial algebraic approach has enormous advantages. Properties are more intelligible and algebraic computational methods can be applied in order to discover or construct the suitable properties. In this paper we show how round invariants can be found for more or less any block cipher, by solving a certain surprisingly simple single algebraic equation (or two). Then if our equation has solutions, which is far from being obvious, it will guarantee that some polynomial invariant will work for an arbitrarily large number of encryption rounds. This paper is a proof of concept showing that it IS possible, for at least one specific quite complex real-life cipher to construct in a systematic way, a non-linear component and a variety of non-linear polynomial invariants holding with probability 1 for any number of rounds and any key/IV. Thus we are able to weaken a block cipher in a permanent and pervasive way. An example of a layered attack with two stages is also shown. Moreover we show that sometimes our equation reduces to zero, and this leads to yet stronger invariants, which work for any Boolean function including the original historical one used in 1970-1990.

Note: new version contains several new examples of invariants of higher degrees

BibTeX

@misc{cryptoeprint:2018/807,
      author = {Nicolas T.  Courtois},
      title = {On the Existence of Non-Linear Invariants and Algebraic Polynomial Constructive Approach to Backdoors in Block Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2018/807},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/807}},
      url = {https://eprint.iacr.org/2018/807}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.