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. The main contribution of this paper is that to show that the product attack'' where the invariant polynomial is a product of simpler polynomials is interesting and quite powerful. 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).

Note: The new version shows that exactly the same "product attack" can also be applied to DES. We provide a proof of concept example of a working invariant attack on DES where P is a product of 10 linear polynomials together with a mathematical proof showing that this attack actually works.

Available format(s)
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
block ciphersBoolean functionsnon-linearityANFFeistel ciphersweak keysbackdoorshistory of cryptographyT-310DESGeneralized Linear Cryptanalysispolynomial invariantsmultivariate polynomialsannihilator spacealgebraic cryptanalysis
Contact author(s)
n courtois @ bettercrypto com
History
2019-09-12: last of 7 revisions
See all versions
Short URL
https://ia.cr/2018/1242

CC BY

BibTeX

@misc{cryptoeprint:2018/1242,
author = {Nicolas T.  Courtois},
title = {Structural Nonlinear Invariant Attacks on T-310: Attacking Arbitrary Boolean Functions},
howpublished = {Cryptology ePrint Archive, Paper 2018/1242},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/1242}},
url = {https://eprint.iacr.org/2018/1242}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.