Linear Cryptanalysis of DES with Asymmetries

Andrey Bogdanov, Philip Søgaard Vejre

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

246 Downloads (Pure)


Linear cryptanalysis of DES, proposed by Matsui in 1993, has had a seminal impact on symmetric-key cryptography, having seen massive research efforts over the past two decades. It has spawned many variants, including multidimensional and zero-correlation linear cryptanalysis. These variants can claim best attacks on several ciphers, including present, Serpent, and CLEFIA. For DES, none of these variants have improved upon Matsui's original linear cryptanalysis, which has been the best known-plaintext key-recovery attack on the cipher ever since. In a revisit, Junod concluded that when using 2 43 known plain-texts, this attack has a complexity of 2 41 DES evaluations. His analysis relies on the standard assumptions of right-key equivalence and wrong-key randomisation.In this paper, we first investigate the validity of these fundamental assumptions when applied to DES. For the right key, we observe that strong linear approximations of DES have more than just one dominant trail and, thus, that the right keys are in fact inequivalent with respect to linear correlation. We therefore develop a new right-key model using Gaussian mixtures for approximations with several dominant trails. For the wrong key, we observe that the correlation of a strong approximation after the partial decryption with a wrong key still shows much non-randomness. To remedy this, we propose a novel wrong-key model that expresses the wrong-key linear correlation using a version of DES with more rounds. We extend the two models to the general case of multiple approximations, propose a likelihood-ratio classifier based on this generalisation, and show that it performs better than the classical Bayesian classifier.On the practical side, we find that the distributions of right-key correlations for multiple linear approximations of DES exhibit exploitable asymmetries. In particular, not all sign combinations in the correlation values are possible. This results in our improved multiple linear attack on DES using 4 linear approximations at a time. The lowest computational complexity of 2(38.86) DES evaluations is achieved when using 2(42.78) known plaintexts. Alternatively, using 2(41) plaintexts results in a computational complexity of 2(49.75) DES evaluations. We perform practical experiments to confirm our model. To our knowledge, this is the best attack on DES.
Original languageEnglish
Title of host publicationASIACRYPT 2017: Advances in Cryptology – ASIACRYPT 2017
EditorsTsuyoshi Takagi , Thomas Peyrin
Number of pages30
Publication date2017
ISBN (Print)978-3-319-70693-1
ISBN (Electronic)978-3-319-70694-8
Publication statusPublished - 2017
Event23rd International Conference on the Theory and Applications of Cryptology and Information Security - Hong Kong, China
Duration: 3 Dec 20177 Dec 2017
Conference number: 23


Conference23rd International Conference on the Theory and Applications of Cryptology and Information Security
CityHong Kong
SeriesLecture Notes in Computer Science


Dive into the research topics of 'Linear Cryptanalysis of DES with Asymmetries'. Together they form a unique fingerprint.

Cite this