Differential cryptanalysis: Difference between revisions

Revision as of 19:38, 9 August 2016

Revision as of 09:11, 29 August 2016

Line 25:

The attack relies primarily on the fact that a given input/output difference pattern only occurs for certain values of inputs. Usually the attack is applied in essence to the non-linear components as if they were a solid component (usually they are in fact look-up tables or ''S-boxes''). Observing the desired output difference (between two chosen or known plaintext inputs) ''suggests'' possible key values.

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 xor⊕ K = 2, or 6 xor⊕ K = 4, meaning the key K is either K2 =or {2,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.