Paper 2021/336

On Closed-Cycle Loops and Applicability of Nonlinear Product Attacks to DES

Nicolas T. Courtois, Matteo Abbondati, Hamy Ratoanina, and Marek Grajek

Abstract

In this article we look at the question of the security of Data Encryption Standard (DES) against non-linear polynomial invariant attacks. Is this sort of attack also possible for DES? We present a simple proof of concept attack on DES where a product of 5 polynomials is an invariant for 2 rounds of DES. Furthermore we present numerous additional examples of invariants with higher degrees. We analyse the success probability when the Boolean functions are chosen at random and compare to DES S-boxes. For more complex higher degree attacks the difficulties disappear progressively and up to 100 % of all Boolean functions in 6 variables are potentially vulnerable. A major limitation for all our attacks, is that they work only for a fraction of the key space. However in some cases, this fraction of the key space is very large for the full 16-round DES.

Note: A student paper which was considerably revised and improved.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
block ciphersFeistel ciphersDESweak keyshistory of cryptographyalgebraic cryptanalysisgeneralized linear cryptanalysispolynomial invariantsannihilator spaceBoolean functionsk-normality
Contact author(s)
courtois @ minrank org
History
2021-03-17: received
Short URL
https://ia.cr/2021/336
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/336,
      author = {Nicolas T.  Courtois and Matteo Abbondati and Hamy Ratoanina and Marek Grajek},
      title = {On Closed-Cycle Loops and Applicability of Nonlinear Product Attacks to DES},
      howpublished = {Cryptology ePrint Archive, Paper 2021/336},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/336}},
      url = {https://eprint.iacr.org/2021/336}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.