Differential cryptanalysis: Difference between revisions

Revision as of 05:28, 19 November 2016

Revision as of 10:48, 16 December 2016

Line 5:

The discovery of differential cryptanalysis is generally attributed to [[Eli Biham]] and [[Adi Shamir]] in the late 1980s, who published a number of attacks against various block ciphers and hash functions, including a theoretical weakness in the [[Data Encryption Standard]] (DES). It was noted by Biham and Shamir that DES is surprisingly resistant to differential cryptanalysis but small modifications to the algorithm would make it much more susceptible.<ref>Biham and Shamir, 1993, pp. 8-9</ref>

In 1994, a member of the original IBM DES team, [[Don Coppersmith]], published a paper stating that differential cryptanalysis was known to IBM as early as 1974, and that defending against differential cryptanalysis had been a design goal.<ref name="coppersmith">{{cite journal |doi = 10.1147/rd.383.0243 |last = Coppersmith |first = Don |date=May 1994 |title = The Data Encryption Standard (DES) and its strength against attacks |journal = IBM Journal of Research and Development |volume = 38 |issue = 3 |pages = 243 |url = http://wwwsimson.research.ibm.com/journalnet/rdref/3831994/coppersmithcoppersmith94.pdf |format = PDF }} (subscription required)</ref> According to author [[Steven Levy]], IBM had discovered differential cryptanalysis on its own, and the [[NSA]] was apparently well aware of the technique.<ref>{{cite book |last = Levy |first = Steven |authorlink = Steven Levy |title = Crypto: How the Code Rebels Beat the Government — Saving Privacy in the Digital Age |publisher = [[Penguin Books]] |year = 2001 |isbn = 0-14-024432-8 |pages = 55–56 }}</ref> IBM kept some secrets, as Coppersmith explains: "After discussions with NSA, it was decided that disclosure of the design considerations would reveal the technique of differential cryptanalysis, a powerful technique that could be used against many ciphers. This in turn would weaken the competitive advantage the United States enjoyed over other countries in the field of cryptography."<ref name="coppersmith"/> Within IBM, differential cryptanalysis was known as the "T-attack"<ref name="coppersmith"/> or "Tickle attack".<ref>Matt Blaze, [[sci.crypt]], 15 August 1996, [https://groups.google.com/group/sci.crypt/msg/5cd14a329372cc5a?dmode=source Re: Reverse engineering and the Clipper chip"]</ref><!-- not the solidest of cites -->

While DES was designed with resistance to differential cryptanalysis in mind, other contemporary ciphers proved to be vulnerable. An early target for the attack was the [[FEAL]] block cipher. The original proposed version with four rounds (FEAL-4) can be broken using only eight [[Chosen-plaintext attack|chosen plaintexts]], and even a 31-round version of FEAL is susceptible to the attack. In contrast, the scheme can successfully cryptanalyze DES with an effort on the order 2⁴⁷ chosen plaintexts.