Content deleted Content added
Citation bot (talk | contribs) Alter: title, template type, pages. Add: chapter-url, volume, series, chapter, authors 1-1. Removed or converted URL. Removed parameters. Formatted dashes. Some additions/deletions were parameter name changes. | Use this bot. Report bugs. | Suggested by Whoop whoop pull up | #UCB_webform 750/895 |
m link to block cipher article |
||
| (5 intermediate revisions by 5 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==
Line 16:
(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.
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''.
Line 32:
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==
| |||