**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.

**Category / Keywords: **secret-key cryptography / 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

**Date: **received 1 Sep 2018, last revised 10 Nov 2019

**Contact author: **courtois at minrank org

**Available format(s): **PDF | BibTeX Citation

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

**Version: **20191111:063021 (All versions of this report)

**Short URL: **ia.cr/2018/807

[ Cryptology ePrint archive ]