Differential cryptanalysis: Difference between revisions

Revision as of 17:33, 9 October 2016

Revision as of 17:34, 9 October 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://www.research.ibm.com/journal/rd/383/coppersmith.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 -->

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://www.research.ibm.com/journal/rd/383/coppersmith.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.

Line 27 ⟶ 23:

For example, if a differential of 1 => 1 (implying a difference in the [[least significant bit]] (LSB) of the input leads to an output difference in the LSB) occurs with probability of 4/256 (possible with the non-linear function in the [[AES cipher]] for instance) then for only 4 values (or 2 pairs) of inputs is that differential possible. Suppose we have a non-linear function where the key is XOR'ed before evaluation and the values that allow the differential are {2,3} and {4,5}. If the attacker sends in the values of {6, 7} and observes the correct output difference it means the key is either 6 ⊕ K = 2, or 6 ⊕ K = 4, meaning the key K is either 2 or 4.

In essence, for an n-bit non-linear function one would ideally seek as close to 2^{−(''n-'' − 1)} as possible to achieve ''differential uniformity''. When this happens, the differential attack requires as much work to determine the key as simply brute forcing the key.

The AES non-linear function has a maximum differential probability of 4/256 (most entries however are either 0 or 2). Meaning that in theory one could determine the key with half as much work as brute force, however, the high branch of AES prevents any high probability trails from existing over multiple rounds. In fact, the AES cipher would be just as immune to differential and linear attacks with a much ''weaker'' non-linear function. The incredibly high branch (active S-box count) of 25 over 4R means that over 8 rounds no attack involves fewer than 50 non-linear transforms, meaning that the probability of success does not exceed Pr[attack] ≤ Pr[best attack on S-box]⁵⁰. For example, with the current S-box AES emits no fixed differential with a probability higher than (4/256)⁵⁰ or 2⁻³⁰⁰ which is far lower than the required threshold of 2⁻¹²⁸ for a 128-bit block cipher. This would have allowed room for a more efficient S-box, even if it is 16-uniform the probability of attack would have still been 2⁻²⁰⁰.