UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Systematic Construction of Nonlinear Product Attacks on Block Ciphers

Courtois, NT; Abbondati, M; Ratoanina, H; Grajek, M; (2020) Systematic Construction of Nonlinear Product Attacks on Block Ciphers. In: Information Security and Cryptology – ICISC 2019. (pp. pp. 20-51). Springer: Cham, Switzerland. Green open access

[thumbnail of Courtois_gen_constr_loops.pdf]
Preview
Text
Courtois_gen_constr_loops.pdf - Accepted Version

Download (2MB) | Preview

Abstract

A major open problem in block cipher cryptanalysis is discovery of new invariant properties of complex type. Recent papers show that this can be achieved for SCREAM, Midori64, MANTIS-4, T-310 or for DES with modified S-boxes. Until now such attacks are hard to find and seem to happen by some sort of incredible coincidence. In this paper we abstract the attack from any particular block cipher. We study these attacks in terms of transformations on multivariate polynomials. We shall demonstrate how numerous variables including key variables may sometimes be eliminated and at the end two very complex Boolean polynomials will become equal. We present a general construction of an attack where multiply all the polynomials lying on one or several cycles. Then under suitable conditions the non-linear functions involved will be eliminated totally. We obtain a periodic invariant property holding for any number of rounds. A major difficulty with invariant attacks is that they typically work only for some keys. In T-310 our attack works for any key and also in spite of the presence of round constants.

Type: Proceedings paper
Title: Systematic Construction of Nonlinear Product Attacks on Block Ciphers
Event: International Conference on Information Security and Cryptology - ICISC 2019
ISBN-13: 9783030409203
Open access status: An open access version is available from UCL Discovery
DOI: 10.1007/978-3-030-40921-0_2
Publisher version: https://doi.org/10.1007/978-3-030-40921-0_2
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: Block ciphers, Boolean functions, Feistel ciphers, Weak keys, DES, Generalized linear cryptanalysis, Polynomial invariants, Multivariate polynomials, Annihilator space, Algebraic cryptanalysis, Polynomial rings, Invariant theory
UCL classification: UCL
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10134213
Downloads since deposit
73Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item