Content deleted Content added
m punctuation |
m link to block cipher article |
||
| (18 intermediate revisions by 16 users not shown) | |||
Line 1:
{{short description|General form of cryptanalysis applicable primarily to block ciphers}}
'''[[Differential (mathematics)|Differential]] cryptanalysis''' is a general form of [[cryptanalysis]] applicable primarily to [[Block cipher|block ciphers]], but also to stream ciphers and cryptographic hash functions. In the broadest sense, it is the study of how differences in information input can affect the resultant difference at the output. In the case of a [[block cipher]], it refers to a set of techniques for tracing differences through the network of transformation, discovering where the cipher exhibits [[non-randomness|non-random behavior]], and exploiting such properties to recover the secret key (cryptography key).
==History==
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 was surprisingly resistant to differential cryptanalysis, but small modifications to the algorithm would make it much more susceptible.<ref name = "Biham_1993">{{cite book | vauthors = Biham
</ref>{{rp|8-9}}
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 |
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 of 2<sup>47</sup> chosen plaintexts.
Line 11 ⟶ 12:
==Attack mechanics==
{{Unreferenced section|date=July 2021}}
Differential cryptanalysis is usually a [[chosen plaintext attack]], meaning that the attacker must be able to obtain [[Encryption|ciphertexts]] for some set of [[plaintext]]s of their choosing. There are, however, extensions that would allow a [[known plaintext attack|known plaintext]] or even a [[ciphertext-only attack]]. The basic method uses pairs of
<math display=block>\Delta_y = S(x \oplus \Delta_x) \oplus S(x)</math>
(and ⊕ denotes exclusive or) for each such S-box ''S''. In the basic attack, one particular ciphertext difference is expected to be especially frequent. In this way, the [[cipher]] can be distinguished from [[randomness|random]]. More sophisticated variations allow the key to be recovered faster than [[Brute force attack|an exhaustive search]].
In the most basic form of key recovery through differential cryptanalysis, an attacker requests the ciphertexts for a large number of plaintext pairs, then assumes that the differential holds for at least ''r'' − 1 rounds, where ''r'' is the total number of rounds.{{fact|date=February 2025}} The attacker then deduces which round keys (for the final round) are possible, assuming the difference between the blocks before the final round is fixed. When round keys are short, this can be achieved by simply exhaustively decrypting the ciphertext pairs one round with each possible round key. When one round key has been deemed a potential round key considerably more often than any other key, it is assumed to be the correct round key.
For any particular cipher, the input difference must be carefully selected for the attack to be successful. An analysis of the algorithm's internals is undertaken; the standard method is to trace a path of highly probable differences through the various stages of encryption, termed a ''differential characteristic''.
Since differential cryptanalysis became public knowledge, it has become a basic concern of cipher designers. New designs are expected to be accompanied by evidence that the algorithm is resistant to this attack and many including the [[Advanced Encryption Standard]], have been [[Mathematical proof|proven]] secure against the attack.<ref>{{
==Attack in detail==
Line 27 ⟶ 28:
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, to protect a cipher from the attack, for an n-bit non-linear function one would ideally seek as close to 2<sup>−(''n'' − 1)</sup> 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.<ref>{{Cite book |last1=Indesteege |first1=Sebastiaan |last2=Preneel |first2=Bart |title=Fast Software Encryption |chapter=Practical Collisions for EnRUPT |series=Lecture Notes in Computer Science |date=2009 |volume=5665 |editor-last=Dunkelman |editor-first=Orr |chapter-url=https://link.springer.com/chapter/10.1007/978-3-642-03317-9_15 |language=en |___location=Berlin, Heidelberg |publisher=Springer |pages=246–259 |doi=10.1007/978-3-642-03317-9_15 |isbn=978-3-642-03317-9}}</ref>
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]<sup>50</sup>. For example, with the current S-box AES emits no fixed differential with a probability higher than (4/256)<sup>50</sup> or 2<sup>−300</sup> which is far lower than the required threshold of 2<sup>−128</sup> 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<sup>−200</sup>.
There exist no bijections for even sized inputs/outputs with 2-uniformity. They exist in odd fields (such as GF(2<sup>7</sup>)) using either cubing or inversion (there are other exponents that can be used as well). For instance, S(x) = x<sup>3</sup> in any odd binary field is immune to differential and linear cryptanalysis. This is in part why the [[MISTY]] designs use 7- and 9-bit functions in the 16-bit non-linear function. What these functions gain in immunity to differential and linear attacks, they lose to algebraic attacks.
==Specialized types==
Line 39 ⟶ 40:
* [[Boomerang attack]]
== See also ==
* [[Cryptography]]
* [[Integral cryptanalysis]]
Line 45 ⟶ 46:
*[[Differential equations of addition]]
== References ==
{{Reflist|30em}}
== Further reading ==
{{Refbegin}}
* {{cite journal | vauthors = Biham E, Shamir A | title = Differential cryptanalysis of DES-like cryptosystems. | journal = Journal of Cryptology | date = January 1991 | volume = 4 | issue = 1 | pages = 3–72 | doi = 10.1007/BF00630563 | s2cid = 33202054 }}
* {{cite book | vauthors = Biham E, Shamir A | chapter = Differential cryptanalysis of the full 16-round DES. | title = Annual International Cryptology Conference | date = August 1992 | pages = 487–496 | publisher = Springer | ___location = Berlin, Heidelberg | doi = 10.1007/3-540-48071-4_34 | series = Lecture Notes in Computer Science | volume = 740 | isbn = 978-3-540-57340-1 | s2cid = 6188138 | archive-url = https://web.archive.org/web/20050405183302/http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1991/CS/CS0708.ps | archive-date = 2005-04-05 | chapter-url = http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1991/CS/CS0708.ps }}
* {{cite book | vauthors = Knudsen LR, Robshaw M | title = The Block Cipher Companion | publisher = Springer | date = 2011 | chapter = Differential Cryptanalysis: The Idea | series = Information Security and Cryptography | pages = 109–126 | doi = 10.1007/978-3-642-17342-4 | isbn = 978-3-642-17341-7 }}
{{refend}}
== External links ==
* [http://www.engr.mun.ca/~howard/Research/Papers/ldc_tutorial.html A tutorial on differential (and linear) cryptanalysis]
* [https://web.archive.org/web/20090129170430/http://research.cyber.ee/~lipmaa/crypto/link/block/dc.php Helger Lipmaa's links on differential cryptanalysis]
| |||