**Structural Nonlinear Invariant Attacks on T-310: Attacking Arbitrary Boolean Functions**

*Nicolas T. Courtois*

**Abstract: **Recent papers show how to construct polynomial invariant attacks for block ciphers, however almost all such results are somewhat weak: invariants are simple and low degree and the Boolean functions tend by very simple if not degenerate. Is there a better more realistic attack, with invariants of higher degree and which is likely to work with stronger Boolean functions?
In this paper we show that such attacks exist and can be constructed explicitly through on the one side, the study of Fundamental Equation of eprint/2018/807, and on the other side, a study of the space of Annihilators of any given Boolean function. Our approach is suitable for backdooring a block cipher in presence of an arbitrarily strong Boolean function not chosen by the attacker. The attack is constructed using excessively simple paper and pencil maths. We also outline a potential application to Data Encryption Standard (DES).

**Category / Keywords: **secret-key cryptography / block ciphers, Boolean functions, non-linearity, ANF, Feistel ciphers, weak keys, backdoors, history of cryptography, T-310, DES, Generalized Linear Cryptanalysis, polynomial invariants, multivariate polynomials, annihilator space, algebraic cryptanalysis

**Date: **received 28 Dec 2018, last revised 21 Apr 2019

**Contact author: **n courtois at bettercrypto com

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

**Note: **The new version shows that exactly the same attack can also be applied to DES and GOST. A full proof of concept example of a working invariant attack on DES where P is a product of 12 linear polynomials is now provided.

**Version: **20190421:194509 (All versions of this report)

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

[ Cryptology ePrint archive ]