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

Nicolas T.  Courtois

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

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: block ciphers Boolean functions Algebraic Normal Form unbalanced Feistel ciphers weak key attacks backdoors history of cryptography T-310 Linear Cryptanalysis Generalized Linear Cryptanalysis partitioning cryptanalysis polynomial invariants triangular systems of equations I O sums multivariate polynomials symmetric polynomials algebraic cryptanalysis
Contact author(s): courtois @ minrank org
History: 2019-11-11: last of 5 revisions; 2018-09-06: received; See all versions
Short URL: https://ia.cr/2018/807
License: CC BY

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},
      url = {https://eprint.iacr.org/2018/807}
}