2.3.4. Cryptanalysis block ciphers

Methods of cryptanalysis were improved along with the development of the block ciphers themselves. The simplest method of cryptanalysis is frequency analysis, which is applicable for simple replacement ciphers. Consider the principle of frequency cryptanalysis based on Caesar's cipher. In Caesar’s cipher, each letter of the original message is replaced by a letter k characters to the right modulo the number of letters in the alphabet:

Frequency analysis uses the property of the cipher text that the frequency of occurrence of characters in it coincides with the frequency of occurrence of the corresponding characters in the clear text. If we take into account that the frequency of occurrence of different characters in the texts of the corresponding language is unevenly distributed (for example, the relative frequency of occurrence of the letter “A” in the texts in Russian is 0.069, and the letter “F” is 0.003), then, counting the relative frequency of occurrence of letters in the ciphertext, it can be assumed that the symbol most often found in the ciphertext corresponds to the symbol most often found in texts in the corresponding language, and thus find the key k . Such a method of cryptanalysis is applicable only to mono-alphabetic cryptoalgorithms, and for its successful work large texts are required.

For modern cryptoalgorithms, more advanced methods of cryptanalysis are used: differential, linear, and power attack.

The differential method of cryptanalysis was proposed by E. Biham and A. Shamir in 1990. Differential cryptanalysis is an attack based on a selective ciphertext. As a material for the analysis, a change in the measure of dissimilarity of two open texts is used during their passage through the main stages of crypto-transformation. As a measure of the dissimilarity of two binary vectors, the Hamming distance is used - the number of bits in which these vectors differ from each other.

The success of attempts to open an r-cyclic cipher depends on the existence of differentials of the (r-1) -th cycle with a higher 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 Hamming distance a can lead to a pair of output texts y, y * after the i-th cycle, having Hamming distance b . Probability of i-cycle differential ( a , b   )   _i   is the conditional probability P (   D   _y ( i ) = b | D   _x ( i ) = a   )   that the Hamming distance of a pair of ciphertexts (y, y *) after the i-th cycle is equal to b , provided that the pair of texts (x, x *) has a distance a .

The differential cryptanalysis algorithm includes the following steps:

1. At the preliminary stage, by repeatedly encrypting various texts, we accumulate statistics for the set of (r-1) -cyclic differentials ( a 1, b 1 ) _{r -1} ,

  ( a2, b2 ) _r-1 , .... ( as, bs ) _r-1   . We arrange this set of differentials according to their probability.

2. Select the plaintext x in an arbitrary way and select x * so that the Hamming distance between x and x * is equal to a1. Texts x and x * are encrypted in a genuine key and after r cycles we get a pair of ciphertext y, y *. 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 three ( D   _y ( r -1 ) , y , y * )   find each possible value of the subkey of the last cycle to ( r ). Add it to the number of occurrences of each such value is connected to ( r ).

3. Repeat step 2 until one or more values ​​of the subkey to ( r ) appear more often than others. We use 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, while the values ​​of y ( r -1 ) are calculated by decrypting the ciphertexts on the found connection of the last cycle to ( r ). Further we act similarly, until the keys of all encryption cycles are disclosed.

For the successful implementation of differential cryptanalysis, it is necessary to have a large set of plaintext / ciphertext pairs (up to 2 ⁴⁷ similar pairs for an attack on 16 DES rounds). Increasing the cipher's resistance to differential cryptanalysis is possible by increasing the number of rounds: for the DES algorithm, with 17 rounds of encryption, differential cryptanalysis is no more effective than a force attack.

The linear method of cryptanalysis was proposed by the Japanese mathematician Matsui in 1993. The method is also an attack based on a selective ciphertext. The method uses linear approximations, which assume with a certain probability that there is a linear relationship between some bits of plaintext, ciphertext and key:

m _i1 Å m _i2 Å ... Å m _ir Å with _j1 Å with _j2 Å ... Å with _js = k _t1 Å k _t2 Å ... Å k _tn , (2.1)

where i1..ir, j1..js, t1..tn are the positions of some plaintext bits m , ciphertext c, and key k .

Let p be the probability that (2.1) holds for randomly chosen m and c . Then it is necessary that p ¹ 1/2 and the quantity | p -1/2 | should be as much as possible. If | p   -1/2 | is sufficiently large and a sufficient number of pairs of open and corresponding encrypted texts are known to the cryptanalyst, then the sum modulo 2 bits of the key at the corresponding position on the right side of (2.1) is the most likely value of the sum modulo 2 corresponding bits of the open and encrypted texts on the left side. If p > 1/2, then the sum of the key bits in the right part of (2.1) is zero, if the sum of the bits in the left part is zero more than for half of the pairs of encrypted texts, and the sum of the key bits in the right part (2.1) is one, if the sum of the bits on the left side is one greater than half the texts. If p <1/2, then vice versa, the sum of the key bits in the right-hand side of (2.1) is zero, if the sum of the bits in the left-hand side equals one more than for half of the pairs of open and encrypted texts, and the sum of the key bits in the right-hand side (2.1 ) is equal to one, if the sum of bits in the left part is zero more than for half of the texts. Thus, a system of linear equations is formed, in which the key bits are unknown, and the task of further analysis is to find a solution to this system. To increase the algorithm's resistance to linear cryptanalysis, nonlinear transformation functions (for example, table substitutions) are introduced into its composition.

A power attack on block ciphers implies a complete enumeration of all possible encryption keys, and its effectiveness depends on the size of the key cipher space. So, if the encryption key has a size of 56 bits, it is possible to use 2 ⁵⁶ keys, which, as already noted, does not constitute a computational difficulty for the cryptanalyst, especially if you consider that the task of brute-forcing keys is easily parallelizable. So, when conducted by RSA Data Security inc. in the Internet of the contest for breaking the RC5 cipher, the number of computers simultaneously participating in the attack reached 4,500 units, and the peak performance - 440 million keys per second [11]. According to estimates by leading experts in the field of cryptography, the length of the encryption key, which guarantees cryptographic resistance to a power attack, should be from 75 to 90 bits.