Editing Data Encryption Standard (section)

=== Attacks faster than brute force ===
There are three attacks known that can break the full 16 rounds of DES with less complexity than a brute-force search: [[differential cryptanalysis]] (DC),<ref name=":0" /> [[linear cryptanalysis]] (LC),<ref name=":1" /> and [[Davies' attack]].<ref name=":2" /> However, the attacks are theoretical and are generally considered infeasible to mount in practice;<ref>{{Cite journal|last=Alanazi|first=Hamdan O.|display-authors=et al|date=2010|title=New Comparative Study Between DES, 3DES and AES within Nine Factors|arxiv=1003.4085|journal=Journal of Computing|volume=2|issue=3|bibcode=2010arXiv1003.4085A}}</ref> these types of attack are sometimes termed certificational weaknesses.

* [[Differential cryptanalysis]] was rediscovered in the late 1980s by [[Eli Biham]] and [[Adi Shamir]]; it was known earlier to both IBM and the NSA and kept secret. To break the full 16 rounds, differential cryptanalysis requires 2<sup>47</sup> [[chosen plaintext]]s.<ref name=":0">{{Cite book|url=https://link.springer.com/978-1-4613-9314-6|title=Differential cryptanalysis of the data encryption standard|last=Biham, E. & Shamir, A|date=1993|publisher=Springer-Verlag|others=Shamir, Adi.|isbn=978-0387979304|location=New York|pages=487–496|doi=10.1007/978-1-4613-9314-6|s2cid=6361693|oclc=27173465}}</ref> DES was designed to be resistant to DC.{{Citation needed|reason=Need a source that will help the reader find how DES was designed to be DC-resistant|date=August 2022}}
* [[Linear cryptanalysis]] was discovered by [[Mitsuru Matsui]], and needs 2<sup>43</sup> [[known plaintext]]s (Matsui, 1993);<ref name=":1">{{Cite book|last=Matsui|first=Mitsuru|title=Advances in Cryptology — EUROCRYPT '93 |chapter=Linear Cryptanalysis Method for DES Cipher |date=1993-05-23|volume=765|series=Lecture Notes in Computer Science|language=en|publisher=Springer, Berlin, Heidelberg|pages=386–397|doi=10.1007/3-540-48285-7_33|isbn=978-3540482857|doi-access=free}}</ref> the method was implemented (Matsui, 1994), and was the first experimental cryptanalysis of DES to be reported. There is no evidence that DES was tailored to be resistant to this type of attack. A generalization of LC—''multiple linear cryptanalysis''—was suggested in 1994 (Kaliski and Robshaw), and was further refined by Biryukov and others. (2004); their analysis suggests that multiple linear approximations could be used to reduce the data requirements of the attack by at least a factor of 4 (that is, 2<sup>41</sup> instead of 2<sup>43</sup>).<ref>{{Cite book|last1=Biryukov|first1=Alex|last2=Cannière|first2=Christophe De|last3=Quisquater|first3=Michaël|title=Advances in Cryptology – CRYPTO 2004 |chapter=On Multiple Linear Approximations |date=2004-08-15|series=Lecture Notes in Computer Science|volume=3152 |language=en|publisher=Springer, Berlin, Heidelberg|pages=1–22|doi=10.1007/978-3-540-28628-8_1|isbn=9783540226680}}</ref> A similar reduction in data complexity can be obtained in a chosen-plaintext variant of linear cryptanalysis (Knudsen and Mathiassen, 2000).<ref>{{Cite book|last1=Knudsen|first1=Lars R.|last2=Mathiassen|first2=John Erik|title=Fast Software Encryption |chapter=A Chosen-Plaintext Linear Attack on DES |date=2000-04-10|series=Lecture Notes in Computer Science|volume=1978 |language=en|publisher=Springer, Berlin, Heidelberg|pages=262–272|doi=10.1007/3-540-44706-7_18|isbn=978-3540447061}}</ref> Junod (2001) performed several experiments to determine the actual time complexity of linear cryptanalysis, and reported that it was somewhat faster than predicted, requiring time equivalent to 2<sup>39</sup>–2<sup>41</sup> DES evaluations.<ref>{{Cite book|last=Junod|first=Pascal|title=Selected Areas in Cryptography |chapter=On the Complexity of Matsui's Attack |date=2001-08-16|volume=2259|series=Lecture Notes in Computer Science|language=en|publisher=Springer, Berlin, Heidelberg|pages=199–211|doi=10.1007/3-540-45537-X_16|isbn=978-3540455370}}</ref>
* ''Improved Davies' attack'': while linear and differential cryptanalysis are general techniques and can be applied to a number of schemes, Davies' attack is a specialized technique for DES, first suggested by [[Donald Davies]] in the eighties,<ref name=":2">{{Cite journal|last=Davies|first=D. W.|date=1987|title=Investigation of a potential weakness in the DES algorithm, Private communications|url=https://scholar.google.com/scholar?q=D.%20W.%20Davies%2C%20Investigation%20of%20a%20potential%20weakness%20in%20the%20DES%20algorithm%2C%20Private%20communications%2C%201987.|journal=Private Communications}}</ref> and improved by Biham and [[Alex Biryukov|Biryukov]] (1997).<ref>{{Cite journal|last1=Biham|first1=Eli|last2=Biryukov|first2=Alex|date=1997-06-01|title=An improvement of Davies' attack on DES|journal=Journal of Cryptology|language=en|volume=10|issue=3|pages=195–205|doi=10.1007/s001459900027|s2cid=4070446|issn=0933-2790|doi-access=free}}</ref> The most powerful form of the attack requires 2<sup>50</sup> [[known plaintext]]s, has a computational complexity of 2<sup>50</sup>, and has a 51% success rate.

There have also been attacks proposed against reduced-round versions of the cipher, that is, versions of DES with fewer than 16 rounds. Such analysis gives an insight into how many rounds are needed for safety, and how much of a "security margin" the full version retains.

[[Differential-linear cryptanalysis]] was proposed by Langford and Hellman in 1994, and combines differential and linear cryptanalysis into a single attack.<ref>{{Cite book|last1=Langford|first1=Susan K.|last2=Hellman|first2=Martin E.|title=Advances in Cryptology — CRYPTO '94 |chapter=Differential-Linear Cryptanalysis |date=1994-08-21|series=Lecture Notes in Computer Science|volume=839 |language=en|publisher=Springer, Berlin, Heidelberg|pages=17–25|doi=10.1007/3-540-48658-5_3|isbn=978-3540486589}}</ref> An enhanced version of the attack can break 9-round DES with 2<sup>15.8</sup> chosen plaintexts and has a 2<sup>29.2</sup> time complexity (Biham and others, 2002).<ref>{{Cite book|last1=Biham|first1=Eli|last2=Dunkelman|first2=Orr|last3=Keller|first3=Nathan|title=Advances in Cryptology — ASIACRYPT 2002 |chapter=Enhancing Differential-Linear Cryptanalysis |date=2002-12-01|series=Lecture Notes in Computer Science|volume=2501 |language=en|publisher=Springer, Berlin, Heidelberg|pages=254–266|doi=10.1007/3-540-36178-2_16|isbn=978-3540361787}}</ref>