Welcome to the resource topic for 2018/807
Title:
On the Existence of Non-Linear Invariants and Algebraic Polynomial Constructive Approach to Backdoors in Block Ciphers
Authors: 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.
ePrint: https://eprint.iacr.org/2018/807
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .