Differential cryptanalysis: Difference between revisions

Revision as of 19:13, 21 April 2023

Revision as of 14:29, 11 July 2023

Line 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^{−(''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.<ref>{{Cite journal |lastlast1=Indesteege |firstfirst1=Sebastiaan |last2=Preneel |first2=Bart |date=2009 |editor-last=Dunkelman |editor-first=Orr |title=Practical Collisions for EnRUPT |url=https://link.springer.com/chapter/10.1007/978-3-642-03317-9_15 |journal=Fast Software Encryption |series=Lecture Notes in Computer Science |volume=5665 |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]⁵⁰. 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⁻²⁰⁰.

Line 53:

* {{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 | titlechapter = The Block Cipher Companion | publisherseries = SpringerInformation Security and Cryptography | date publisher = 2011Springer | chapterdate = Differential Cryptanalysis: The Idea2011 | pages = 109-126109–126 | doi = 10.1007/978-3-642-17342-4 | isbn = 978-3-642-17341-7 }}

== External links ==