Differential Cryptanalysis Method

The differential cryptanalysis method (DFA) was proposed by E. Biham and A. Shamir in 1990. Differential cryptanalysis is an attempt to unlock the secret key of block ciphers, which are based on the repeated use of cryptographically weak digital encryption operation times.

When analyzing, it is assumed that each cycle uses its own encryption subkey. The RCA can use both selected and known plaintext. The success of such attempts to open the r-cyclic cipher depends on the existence of differentials of the (r-1) -th cycle, which have a high probability. The differential of the i-th cycle is defined as a pair (a, b) i such that a pair of different plaintext x, x * c difference a can lead to a pair of output texts y, y * after the i-th cycle having a difference b (for the corresponding concepts of difference). The probability of an i-cycle differential (a, b) i is the conditional probability P (D y (i) = b | D x = a) that the difference D y (i) of a pair of ciphertexts (y, y *) after i- This cycle is equal to b, provided that the pair of texts (x, x *) has the difference D x = a; plaintext x and connect the cycles to (1), to (2), ...., to (i) independent and equiprobable. The main procedure of the DCA r-cyclic cipher
using selected open texts may be the following:
1. At the precomputation stage, we look for the set of (r-1) -cyclic differentials (a 1, b 1) r-1, (a 2, b 2) r-1, .... (as, bs) r-1. We arrange this set of differentials according to their probability.
2. Select the plaintext x arbitrarily and calculate x * so that the difference between x and x * is equal to a 1. Texts x and x * are encrypted with the real key and after r cycles we get a pair of ciphertexts y (r), y * ( r). We assume that at the output of the penultimate (r-1) th cycle, the difference between the ciphertexts is the most probable: D y (r-1) = b 1. For a triple (D y (r-1), y (r), y * ( r)) we find every possible (if there are several) values ​​of the subkey of the last cycle to (r). Add it to the number of occurrences of each such value connected to (r).
3. Repeat step 2 until one or more values ​​of the subkey to (r) appear more often than others. We take this subkey or many such subkeys as a cryptographic solution for connecting to (r).
4. We repeat the PP.1-3 for the penultimate cycle, and the values ​​of y (r-1) are calculated by decrypting the ciphertext on the found connection of the last cycle to (r). Further we act similarly, until the keys of all encryption cycles are disclosed.

Proposed for the first time to analyze a specific cipher, DFA turned out to be applicable for analyzing a wide class of Markov ciphers. Markovsky is a cipher whose encryption equation on one cycle satisfies the condition: the probability of a differential does not depend on the choice of open texts. Then, if you connect loop-independent, then the sequence of differences after each cycle forms a Markov chain, where the next state is determined only by the previous one. Examples of Markov ciphers are DES and FEAL. It can be shown that a Markov r-cyclic cipher with independent subkeys is vulnerable to a DFA if and only if for one encryption cycle a key using a known triple (y, y *, D x) can be easily calculated and exists (r-1 ) -cycle differential (a, b) k-1 such that its probability satisfies the condition
P (D y (r-1) = b | D x = a) >> 2-n,
where n is the number of bits in the block of encrypted text.
The complexity of the disclosure of the key of the r-cyclic cipher Q (r) is defined as the number of encryptions used, followed by the calculation of the key:
Q (r) - 2 / (Pmax - 1 / (2n-1)),
where Pmax = max (a) max (b) (P (D y (r-1) = b | D x = a)). In particular, if Pmax 1 1 / (2n-1), then the attack will not be successful. Since the calculation of the subkey is a more laborious operation than encryption, the complexity unit is the difficulty of finding possible subkeys of one cycle using known (D y (r-1), y (r), y * (r)).
A distinctive feature of differential analysis is that it practically does not use the algebraic properties of the cipher (linearity, affinity, transitivity, closure, etc.), but is based only on the uneven distribution of the probability of differentials.