Variable elimination strategies and construction of nonlinear polynomial invariant attacks on T-310. Issue 1 (2nd January 2020)

• Record Type: Journal Article
• Authors: Courtois, Nicolas T.; Georgiou, Marios
• Is Part Of: Cryptologia. Volume 44:Issue 1(2020)
• Page Start: 20
• Page End: 38
• Publication Date: 2020-01-02
• Subjects: algebraic cryptanalysis -- ANF -- backdoors -- Boolean functions -- ciphertext-only attacks -- Cold War -- Feistel ciphers -- generalized linear cryptanalysis -- higher-order correlation attacks -- history -- I/O sums -- modern block ciphers -- multivariate polynomials -- partitioning cryptanalysis -- polynomial invariants -- T-310 -- weak keys; Cryptography -- Periodicals; 652.8
• DOI: 10.1080/01611194.2019.1650845
• Languages: English
• ISSNs: 0161-1194

Abstract

Abstract: One of the major open problems in symmetric cryptanalysis is to discover new specific types of invariant properties for block ciphers. In this article, we study nonlinear polynomial invariant attacks. The number of such attacks grows as 2 2 n and systematic exploration is not possible. The main question is HOW do we find such attacks? We have developed a constructive algebraic approach that is about making sure that a certain combination of polynomial equations is zero. We work by progressive elimination of specific variables in polynomial spaces and we show that one can totally eliminate big chunks of the cipher circuit. As an application, we present several new attacks on the historical T-310 block cipher that has particularly large hardware complexity and a very large number of rounds compared with modern ciphers, e.g., AES. However, all this complexity is not that useful if we are able to construct new types of polynomial invariant attacks that work for any number of rounds.