Construction of a polynomial invariant annihilation attack of degree 7 for T-310. Issue 4 (3rd July 2020)

• Record Type: Journal Article
• Authors: Courtois, Nicolas T.; Patrick, Aidan; Abbondati, Matteo
• Is Part Of: Cryptologia. Volume 44:Issue 4(2020)
• Page Start: 289
• Page End: 314
• Publication Date: 2020-07-03
• Subjects: algebraic cryptanalysis -- ANF -- annihilator space -- backdoors -- Boolean functions -- Cold War -- Feistel ciphers -- Generalised Linear Cryptanalysis -- modern block ciphers -- multivariate polynomials -- polynomial invariants -- polynomial rings -- T-310 -- unique factorisation -- weak keys; Cryptography -- Periodicals; 652.8
• DOI: 10.1080/01611194.2019.1706062
• Languages: English
• ISSNs: 0161-1194

Abstract

Abstract: Cryptographic attacks are typically constructed by black-box methods and combinations of simpler properties, for example in [Generalised] Linear Cryptanalysis. In this article, we work with a more recent white-box algebraic-constructive methodology. Polynomial invariant attacks on a block cipher are constructed explicitly through the study of the space of Boolean polynomials which does not have a unique factorisation and solving the so-called Fundamental Equation (FE). Some recent invariant attacks are quite symmetric and exhibit some sort of clear structure, or work only when the Boolean function is degenerate. As a proof of concept, we construct an attack where a highly irregular product of seven polynomials is an invariant for any number of rounds for T-310 under certain conditions on the long term key and for any key and any IV. A key feature of our attack is that it works for any Boolean function which satisfies a specific annihilation property. We evaluate very precisely the probability that our attack works when the Boolean function is chosen uniformly at random.