- Tutorial
Hi% username%!
Many people know that DES has long been considered the default standard for symmetric encryption. The first successful attack on this unkillable algorithm was published in 1993, 16 years after it was adopted as a standard. The method, which the author called linear cryptanalysis, in the presence of 247 pairs of open / cipher texts, allows to break the secret key of the DES cipher in 243 operations.
Under the cut I will try to summarize the main points of this attack.
Linear cryptanalysis
Linear cryptanalysis is a special type of attack on symmetric ciphers aimed at recovering an unknown encryption key from known open messages and their corresponding ciphertexts.In general, an attack based on linear cryptanalysis is reduced to the following conditions. The attacker possesses a large number of clear / ciphertext pairs obtained using the same encryption key K. The attacker's goal is to recover partially or completely the key K.
First of all, the attacker examines the cipher and finds the so-called. statistical analogue, i.e. equation of the following form, fulfilling with probability P ≠ 1/2 for an arbitrary open / closed text pair and a fixed key:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib \u003d K I1 ⊕ K I2 ⊕… ⊕ K Ic (1)
,
where P n, C n, K n are the n-th bits of the text, ciphertext and key.
After a similar equation is found, the attacker can recover 1 bit of information about the key using the following algorithm
Algorithm 1
Let T be the number of texts for which the left side of equation (1) equals 0, then
If T\u003e N / 2, where N is the number of known plaintexts.
Assume that K I1 ⊕ K I2 ⊕… ⊕ K Ic \u003d 0 (when P\u003e 1/2) or 1 (when P<1/2).
Otherwise
Assume that K I1 ⊕ K I2 ⊕… ⊕ K Ic \u003d 1 (when P\u003e 1/2) or 0 (when P<1/2).
Obviously, the success of the algorithm directly depends on the value of | P-1/2 | and on the number of available open / closed text pairs N. The more the probability P of equality (1) differs from 1/2, the less the number of open texts N is needed for the attack.
There are two problems that need to be addressed in order to successfully implement an attack:
- How to find an effective equation of the form (1).
- How to get more than one bit of information about a key using such an equation.
DES description
But first, let's briefly describe how the algorithm works. Enough has been said about DES. A full description of the cipher can be found on Wikipedia. However, to further explain the attack, we need a number of definitions that are best introduced in advance.So DES is a block cipher based on the Feistel network. The cipher has a block size of 64 bits and a key size of 56 bits. Let's consider the DES encryption scheme. 
As you can see from the figure, during encryption, the following operations are performed on the text:
- Initial bit permutation. At this stage, the bits of the input block are shuffled in a specific order.
- After that, the mixed bits are split into two halves, which are fed to the input of the Feistel function. For standard DES, the Feistel network includes 16 rounds, but there are other variants of the algorithm.
- The two blocks obtained in the last round of transformation are combined and another permutation is performed over the resulting block.
On each round of the Feistel network, the least significant 32 bits of the message pass through the function f: 
Consider the operations performed at this stage:
- The input block goes through the expansion function E, which converts a 32-bit block to a 48-bit block.
- The resulting block is added with the round key K i.
- The result of the previous step is split into 8 blocks of 6 bits each.
- Each of the received blocks B i goes through the S-Box i substitution function, which replaces the 6-bit sequence with a 4-bit block.
- The resulting 32-bit block goes through the permutation P and is returned as the result of f.
Of greatest interest, from the point of view of cryptanalysis of the cipher, for us are S blocks, designed to hide the connection between the input and output data of the function f. To successfully attack DES, we first build statistical analogs for each of the S-boxes, and then extend them to the entire cipher.
S block analysis
Each S-box accepts a 6-bit sequence as input, and a fixed 4-bit value is returned for each such sequence. Those. there are only 64 options for input and output data. Our task is to show the relationship between the input and output data of S blocks. For example, for the third S-block of the DES cipher, the 3rd bit of the input sequence is equal to the 3rd bit of the output sequence in 38 cases out of 64. Therefore, we found the following statistical analogue for the third S-block:S 3 (x) \u003d x, which is executed with probability P \u003d 38/64.
Both sides of the equation represent 1 bit of information. Therefore, if the left and right sides were independent of each other, the equation would have to be fulfilled with a probability equal to 1/2. Thus, we have just demonstrated the relationship between the inputs and outputs of the 3rd S-box of the DES algorithm.
Consider how you can find a statistical analogue of the S-box in the general case.
For S-box S a, 1 ≤ α ≤ 63 and 1 ≤ β ≤ 15, the value NS a (α, β) describes how many times out of 64 possible XOR input bits S a superimposed on α bits are equal to XOR output bits superimposed on bits β, i.e .:
where symbol is logical AND.
The α and β values \u200b\u200bfor which NS a (α, β) differs most from 32 describe the most efficient statistical analogue of the S-box S a.
The most effective analogue was found in the 5th S-block of the DES cipher for α \u003d 16 and β \u003d 15 NS 5 (16, 15) \u003d 12. This means that the following equation is true: Z \u003d Y ⊕ Y ⊕ Y ⊕ Y, where Z is the input sequence of the S-box and Y is the output sequence.
Or taking into account the fact that in the DES algorithm, before entering the S-block, data is added modulo 2 with a round key, i.e. Z \u003d X ⊕ K we obtain
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y \u003d K, where X and Y are the input and output data of the function f without regard to permutations.
The resulting equation is fulfilled in all rounds of the DES algorithm with the same probability P \u003d 12/64.
The following table provides a list of effective, i.e. having the largest deviation from P \u003d 1/2, statistical analogs for each s-block of the DES algorithm. 
Building statistical analogs for multiple DES rounds
Let us now show how we can combine the statistical analogs of several DES rounds and, as a result, obtain a statistical analog for the entire cipher.To do this, consider a three-round version of the algorithm:
Let us apply an efficient statistical analogue of the 5th s-box to calculate certain bits of the value of X (2).
We know that with probability 12/64 the f-function satisfies the equality X ⊕ Y ⊕ Y ⊕ Y ⊕ Y \u003d K, where X is the second input bit of the 5th S-box, it is essentially the 26th bit of the sequence obtained after expanding the input bits. Analyzing the extension function, we can establish that in place of the 26th bit there is the 17th bit of the X (1) sequence.
Similarly, Y, ..., Y are essentially the 17th, 18th, 19th and 20th bits of the sequence obtained before the permutation P. Having examined the permutation P, we get that the bits Y, ..., Y are actually bits Y (1), Y (1), Y (1), Y (1).
The bit of the key K involved in the equations is the 26th bit of the subkey of the first round K1 and then the statistical analogue takes the following form:
X (1) ⊕ Y (1) ⊕ Y (1) ⊕ Y1 ⊕ Y (1) \u003d K1.
Hence, X (1) ⊕ K1 \u003d Y (1) ⊕ Y (1) ⊕ Y (1) ⊕ Y (1)(2) with probability P \u003d 12/64.
Knowing 3, 8, 14, 25 bits of the Y (1) sequence, you can find 3, 8, 14, 25 bits of the X (2) sequence:
X (2) ⊕ X (2) ⊕ X (2) ⊕ X (2) \u003d PL ⊕ PL ⊕ PL ⊕ PL ⊕ Y (1) ⊕ Y (1) ⊕ Y (1) ⊕ Y (1)or taking into account equation (2)
X (2) ⊕ X (2) ⊕ X (2) ⊕ X (2) \u003d PL ⊕ PL ⊕ PL ⊕ PL ⊕ X (1) ⊕ K1 (3) with a probability of 12/64.
Let's find a similar expression using the last round. This time we have the equation
X (3) ⊕ K3 \u003d Y (3) ⊕ Y (3) ⊕ Y (3) ⊕ Y (3).
Because
X (2) ⊕ X (2) ⊕ X (2) ⊕ X (2) \u003d СL ⊕ СL ⊕ СL ⊕ СL ⊕ Y (3) ⊕ Y (3) ⊕ Y (3) ⊕ Y (3)
we get that
X (2) ⊕ X (2) ⊕ X (2) ⊕ X (2) \u003d CL ⊕ CL ⊕ CL ⊕ CL ⊕ X (3) ⊕ K3(4)
with a probability of 12/64.
Equating the right-hand sides of equations (3) and (4), we obtain
CL ⊕ CL ⊕ CL ⊕ CL ⊕ X (3) ⊕ K3 \u003d PL ⊕ PL ⊕ PL ⊕ PL ⊕ X (1) ⊕ K1 with probability (12/64) 2 + (1-12 / 64) 2.
Taking into account that X (1) \u003d PR and X (3) \u003d CR, we obtain a statistical analogue
СL ⊕ CR ⊕ PL ⊕ PR \u003d K1 ⊕ K3 (5)
,
which runs with probability (12/64) 2 + (1-12 / 64) 2 \u003d 0.7.
The statistical analogue described above can be represented graphically as follows (the bits in the figure are numbered from right to left and starting from zero): 
All the bits on the left side of the equation are known to the attacker, therefore he can apply Algorithm 1 and find out the value of K1 ⊕ K3. Let us show how, using this statistical analogue, it is possible to break not 1, but 12 bits of the encryption key K.
DES attack with known plaintext
Here is a method by which you can expand the attack and immediately get 6 bits of the subkey of the first round.Composing equation (5), we took into account the fact that we do not know the value of F1 (PR, K1). Therefore, we used its statistical analogue K1 ⊕ PR.
Instead of the expression K1 ⊕ PR, we return the value of F1 (PR, K1) and obtain the following equation:
CL ⊕ CR ⊕ PL ⊕ F1 (PR, K1) \u003d K3 (6) which will be executed with a probability of 12/64. The probability has changed since we left only the statistical analogue from the third round, all other values \u200b\u200bare fixed.
We have already determined above that the value of F1 (PR, K1) is influenced by the input bits of the 5th S-box, namely the bits of the K1 key and the bits of the PR block. Let us show how, having only a set of open / closed texts, you can restore the value of K1. To do this, we will use Algorithm 2.
Algorithm 2
Let N be the number of open / closed text pairs known before the attack. Then, to open the key, you need to do the following steps.
For (i \u003d 0; i<64; i++) do
{
For (j \u003d 0; j
if (CL j ⊕ CR j ⊕ PL j ⊕ F1 (PR j, i) \u003d 0) then
T i \u003d T i +1
}
}
As a probable sequence K1, such a value of i is taken for which the expression | T i -N / 2 | has a maximum value.
Given a sufficient number of known plaintexts, the algorithm will most likely return the correct value of the six bits of the first round K1 subkey. This is explained by the fact that if the variable i is not equal to K1, then the value of the function F1 (PR j, K) will be random and the number of equations for such a value of i at which the left side is equal to zero will tend to N / 2. If the subkey is guessed correctly, the left side will be equal to the fixed bit K3 with a probability of 12/64. Those. there will be a significant deviation from N / 2.
Having received 6 bits of the K1 subkey, you can open the 6 bits of the K3 subkey in the same way. All that is needed for this is to replace in equation (6) C by P and K1 by K3:
PL ⊕ PR ⊕ CL ⊕ F3 (CR, K3) \u003d K1.
Algorithm 2 will return the correct value K3 because the decryption process of the DES algorithm is identical to the encryption process, it just changes the sequence of keys. So on the first round of decryption, the key K3 is used, and on the last round the key is K1.
Having received 6 bits of subkeys K1 and K3, the attacker recovers 12 bits of the common key of the K cipher, since the round keys are the usual permutation of the key K. The number of plaintexts required for a successful attack depends on the probability of a statistical counterpart. To break the 12 bits of a 3-round DES key, 100 plaintext / privatetext pairs are sufficient. To break the 12 bits of a 16-round DES key, about 244 text pairs are required. The remaining 44 bits of the key are opened with a regular brute-force attack.
Algorithm DES
The main advantages of the DES algorithm:
· Only one key 56 bits long is used;
· Having encrypted a message with one package, you can use any other to decrypt;
· The relative simplicity of the algorithm provides a high speed of information processing;
· Sufficiently high stability of the algorithm.
DES encrypts 64-bit blocks of data using a 56-bit key. Decryption in DES is the reverse operation of encryption and is performed by repeating encryption operations in reverse order (despite the seeming obviousness, this is not always done. Later we will consider ciphers in which encryption and decryption are performed using different algorithms).
The encryption process consists of an initial bit swapping of a 64-bit block, sixteen encryption cycles, and finally, a reverse bit swap (Fig. 1).
It should be noted immediately that ALL tables given in this article are STANDARD, and therefore should be included in your implementation of the algorithm unchanged. All permutations and codes in the tables were selected by the developers in such a way as to make the decryption process as difficult as possible by guessing the key. The structure of the DES algorithm is shown in Figure 2.
Fig. 2. DES encryption algorithm structure
Let the next 8-byte block T be read from the file, which is transformed using the initial permutation IP matrix (Table 1) as follows: bit 58 of the T block becomes bit 1, bit 50 becomes bit 2, etc., which will result in : T (0) \u003d IP (T).
The resulting sequence of bits T (0) is divided into two sequences of 32 bits each: L (0) - left or most significant bits, R (0) - right or least significant bits.
Table 1: IP Initial Permutation Matrix
58 50 42 34 26 18 10 02
60 52 44 36 28 20 12 04
62 54 46 38 30 22 14 06
64 56 48 40 32 24 16 08
57 49 41 33 25 17 09 01
59 51 43 35 27 19 11 03
61 53 45 37 29 21 13 05
63 55 47 39 31 23 15 07
Then encryption is performed, consisting of 16 iterations. The result of the i-th iteration is described by the following formulas:
R (i) \u003d L (i-1) xor f (R (i-1), K (i)),
where xor is the EXCLUSIVE OR operation.
The function f is called the encryption function. Its arguments are the 32-bit sequence R (i-1) obtained at the (i-1) th iteration, and the 48-bit key K (i), which is the result of transforming the 64-bit key K. In detail, the encryption function and the algorithm for obtaining keys K (i) is described below.
At the 16th iteration, the sequences R (16) and L (16) (without permutation) are obtained, which are concatenated into a 64-bit sequence R (16) L (16).
Then the bit positions of this sequence are rearranged in accordance with the matrix IP -1 (Table 2).
Table 2: IP -1 reverse permutation matrix
40 08 48 16 56 24 64 32
39 07 47 15 55 23 63 31
38 06 46 14 54 22 62 30
37 05 45 13 53 21 61 29
36 04 44 12 52 20 60 28
35 03 43 11 51 19 59 27
34 02 42 10 50 18 58 26
33 01 41 09 49 17 57 25
The matrices IP -1 and IP are related as follows: the value of the 1st element of the IP -1 matrix is \u200b\u200b40, and the value of the 40th element of the IP matrix is \u200b\u200b1, the value of the 2nd element of the IP -1 matrix is \u200b\u200b8, and the value of the 8th the element of the IP matrix is \u200b\u200bequal to 2, etc.
The data decryption process is inverse to the encryption process. All steps must be performed in reverse order. This means that the decrypted data is first rearranged in accordance with the IP-1 matrix, and then the same actions are performed on the R (16) L (16) bit sequence as in the encryption process, but in reverse order.
The iterative decryption process can be described by the following formulas:
R (i-1) \u003d L (i), i \u003d 1, 2, ..., 16;
L (i-1) \u003d R (i) xor f (L (i), K (i)), i \u003d 1, 2, ..., 16.
At the 16th iteration, the sequences L (0) and R (0) are obtained, which are concatenated into a 64-bit sequence L (0) R (0).
The bit positions of this sequence are then rearranged according to the IP matrix. The result of this permutation is the original 64-bit sequence.
Now consider the encryption function f (R (i-1), K (i)). It is shown schematically in Fig. 3.
Fig. 3. Calculation of the function f (R (i-1), K (i))
The following matrix functions are used to calculate the value of the function f:
E - expansion of a 32-bit sequence to 48-bit,
S1, S2, ..., S8 - convert a 6-bit block to a 4-bit one,
P - permutation of bits in a 32-bit sequence.
The expansion function E is defined in Table 3. According to this table, the first 3 bits of E (R (i-1)) are bits 32, 1, and 2, and the last are 31, 32, and 1.
Table 3: Expansion function E
32 01 02 03 04 05
04 05 06 07 08 09
08 09 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 01
The result of the function E (R (i-1)) is a 48-bit sequence, which is added modulo 2 (operation xor) with a 48-bit key K (i). The result is a 48-bit sequence, which is split into eight 6-bit blocks B (1) B (2) B (3) B (4) B (5) B (6) B (7) B (8). I.e:
E (R (i-1)) xor K (i) \u003d B (1) B (2) ... B (8).
The functions S1, S2, ..., S8 are defined in Table 4.
Table 4
Table 4. further clarification is required. Let the 6-bit block B (j) \u003d b1b2b3b4b5b6 enter the input of the matrix function Sj, then the two-bit number b1b6 indicates the row number of the matrix, and b2b3b4b5 is the column number. The result of Sj (B (j)) is a 4-bit element located at the intersection of the specified row and column.
For example, B (1) \u003d 011011. Then S1 (B (1)) is located at the intersection of row 1 and column 13. Column 13 of row 1 is set to 5. So S1 (011011) \u003d 0101.
Applying the selection operation to each of the 6-bit blocks B (1), B (2), ..., B (8), we obtain a 32-bit sequence S1 (B (1)) S2 (B (2)) S3 ( B (3)) ... S8 (B (8)).
Finally, to get the result of the encryption function, the bits of this sequence must be swapped. For this, the permutation function P is used (Table 5). In the input sequence, the bits are swapped so that bit 16 becomes bit 1, bit 7 becomes bit 2, and so on.
Table 5: Transfer function P
In this way,
f (R (i-1), K (i)) \u003d P (S1 (B (1)), ... S8 (B (8)))
To complete the description of the data encryption algorithm, it remains to give an algorithm for obtaining 48-bit keys K (i), i \u003d 1 ... 16. At each iteration, a new key value K (i) is used, which is calculated from the initial key K. K is a 64-bit block with eight parity bits located at positions 8,16,24,32,40,48,56, 64.
To remove control bits and permute the rest, the function G of the initial key preparation is used (Table 6).
Table 6
Initial key preparation matrix G
57 49 41 33 25 17 09
01 58 50 42 34 26 18
10 02 59 51 43 35 27
19 11 03 60 52 44 36
63 55 47 39 31 23 15
07 62 54 46 38 30 22
14 06 61 53 45 37 29
21 13 05 28 20 12 04
The result of the transformation G (K) is divided into two 28-bit blocks C (0) and D (0), and C (0) will consist of bits 57, 49, ..., 44, 36 of the key K, and D (0 ) will consist of bits 63, 55, ..., 12, 4 of the key K. After defining C (0) and D (0), C (i) and D (i), i \u003d 1 ... 16, are recursively defined. To do this, apply a cyclic left shift by one or two bits, depending on the iteration number, as shown in Table 7.
Table 7
Shift table for calculating the key
| Iteration number | Shift (bit) |
| 01 | 1 |
| 02 | 1 |
| 03 | 2 |
| 04 | 2 |
| 05 | 2 |
| 06 | 2 |
| 07 | 2 |
| 08 | 2 |
| 09 | 1 |
| 10 | 2 |
| 11 | 2 |
| 12 | 2 |
| 13 | 2 |
| 14 | 2 |
| 15 | 2 |
| 16 | 1 |
The resulting value is again "mixed" in accordance with the matrix H (Table 8).
Table 8: Key Post-Processing Matrix H
14 17 11 24 01 05
03 28 15 06 21 10
23 19 12 04 26 08
16 07 27 20 13 02
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
Key K (i) will consist of bits 14, 17, ..., 29, 32 of the sequence C (i) D (i). In this way:
K (i) \u003d H (C (i) D (i))
The block diagram of the key calculation algorithm is shown in Fig. 4.
Fig. 4. Block diagram of the algorithm for calculating the key K (i)
Recovering the original text is carried out using this algorithm, but first you use the key
K (15), then K (14), and so on. Now it should be clear to you why the author strongly recommends using the given matrices. If you start self-righteous, you must get a very secret cipher, but you yourself will not be able to reveal it later!
DES operation modes
For the most complete satisfaction of all the requirements for commercial encryption systems, several modes of operation of the DES algorithm are implemented. The most widespread modes are:
· Electronic codebook (Electronic Codebook) - ECB;
A chain of digital blocks (Cipher Block Chaining) - CBC;
· Digital feedback (Cipher Feedback) - CFB;
· External feedback (Output Feedback) - OFB.
In this mode, the source file M is split into 64-bit blocks (8 bytes each): M \u003d M (1) M (2) ... M (n). Each of these blocks is encrypted independently using the same encryption key (Figure 5). The main advantage of this algorithm is its ease of implementation. The disadvantage is the relatively weak resistance against skilled cryptanalysts.
DES (Data Encryption Standart) - Symmetric encryption algorithm, in which one key is used for both encryption and decryption of data. DES was developed by IBM and approved by the US government in 1977 as an official standard (FTPS 46-3). DES has 64-bit blocks and a 16-round Feistel network structure; it uses a 56-bit key for encryption. The algorithm uses a combination of non-linear (S-boxes) and linear (permutations E, IP, IP-1) transformations. Several modes are recommended for DES:Block cipher
The input data for the block cipher are an n-bit block and a k-bit key. At the output, after applying the encryption transformation, an n-bit encrypted block is obtained, and insignificant differences in the input data usually lead to a significant change in the result. Block ciphers are implemented by repeatedly applying some basic transformations to blocks of source text.Basic conversions:
Feistel Network Transforms
This is a transformation over vectors (blocks) representing the left and right halves of the shift register. DES uses forward Feistel transform in encryption (see Figure 1) and reverse Feistel transform to decryption (see Figure 2).
DES encryption scheme
The original text is a block of 64 bits. The cipher text is a block of 64 bits.
The encryption process consists of an initial permutation, 16 encryption cycles, and a final permutation.
Let's consider a detailed diagram of the DES algorithm:
L i R i \u003d 1,2 \\ ldots. Left and right halves of a 64-bit block L i R i
k i - 48 bit keys
f - encryption function
IP - initial permutation
IP -1 is the final permutation. 
According to the table, the first 3 bits of the resulting IP (T) block after the initial permutation of IP are bits 58, 50, 42 of the input block T, and its last 3 bits are bits 23, 15, 7 of the input block. Further, the 64-bit IP (T) block participates in 16-cycles of the Feistel transform.
16 cycles of Feistel transform:
Split IP (T) into two parts L 0, R 0, where L 0, R 0 - 32 most significant bits and 32 least significant bits of the block T0 IP (T) \u003d L 0 R 0, respectively
Let T i -1 \u003d L i -1 R i -1 result of (i-1) iteration, then the result of the i-th iteration T i \u003d L i R i is determined:
L i \u003d R i - 1 The left half of L i is equal to the right half of the previous vector L i - 1 R i - 1. And the right half of R i is the bit addition of L i - 1 and f (R i - 1, k i) modulo 2.
In the 16-cycle Feistel transform, the function f plays the role of encryption. Let's consider the function f in detail.
The arguments to f are 32 bit vector R i - 1, 48 bit key k i, which are the result of transforming the 56 bit original cipher key k.
To calculate the function f, the expansion function E, the transformation S, consisting of 8 transformations of S-boxes, and the permutation P. are used.
Function E expands 32 bit vector R i - 1 to 48 bit vector E (R i - 1) by duplicating some of the bits from R i - 1, while the order of bits of vector E (R i - 1) is shown in Table 2. 
The first three bits of the vector E (R i - 1) are bits 32, 1, 2 of the vector R i -1. Table 2 shows that bits 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 are duplicated. The last 3 bits of vector E (Ri - 1) are bits 31, 32, 1 of vector R i - 1. The block E (R i -1) obtained after the permutation is added modulo 2 with the keys k i and then represented as eight consecutive blocks B 1, B 2, ... B 8.
E (R i - 1) \u003d B 1 B 2 ... B 8
Each B j is a 6-bit block. Further, each of the blocks B j is transformed into a 4-bit block B "j using transformations S j. The transformations S j are determined by Table 3. Suppose that B 3 \u003d 101111 and we want to find B" 3. The first and last bits of B 3 are binary notation of the number a, 0 The value of the function f (R i - 1, ki) (32 bits) is obtained by permutation P applied to 32 bit block B "1 B" 2 ... B "8. P is given by Table 4. 
f (R i - 1, k i) \u003d P (B "1 B" 2 ... B "8)
According to table 4, the first four bits of the resulting vector after the action of the function f are bits 16, 7, 20, 21 of the vector B "1 B" 2 ... B "8
Generating keys k i.
Keys k i are obtained from the initial key k (56 bits \u003d 7 bytes or 7 characters in ASCII) in this way. Eight bits found in positions 8, 16, 24, 32, 40, 48, 56, 64 are added to the key k so that each byte contains an odd number of ones. This is used to detect errors in key exchange and storage. Then permute the extended key (except for the added bits 8, 16, 24, 32, 40, 48, 56, 64). This permutation is defined as in Table 5. 
This permutation is defined by two blocks C 0 and D 0 of 28 bits each. The first 3 bits of C 0 are bits 57, 49, 41 of the extended key. And the first three bits of D 0 are bits 63, 55, 47 of the extended key. C i, D i i \u003d 1,2,3 ... are obtained from C i - 1, D i - 1 by one or two left cyclic shifts according to table 6. 
Key k i, i \u003d 1, ... 16 consists of 48 bits selected from the bits of the vector C i D i (56 bits) according to Table 7. The first and second bits k i are bits 14, 17 of the vector C i D i 
The final permutation IP - 1 acts on T 16 and is used to restore position. It is the reverse of IP permutation. The final permutation is determined by Table 8. 
DES usage modes DES can be used in four modes.
The Data Encryption Standard (DES) is a data encryption standard invented in the United States in the 1980s. Among the ciphers, he is rightfully considered a "retired", while remaining the workhorse of cryptography. DES ceased to be useful in the conditions of ultra-fast technology and large amounts of data due to the limitations of 56 bits per key and 64 bits for data. However, it is still in use.
What are block ciphers?
DES is a block cipher algorithm. Over the past 20-30 years, many block ciphers have been created, but creating a good cipher that is secure is a difficult task. It is important that the cipher has characteristics that will allow it to function in many areas and industries.
Block ciphers consist of several iterations of using some cipher in turn. Each iteration is called a round. As practice shows, even some of the primitive algorithms, when used sequentially, are capable of creating reliable ciphers. DES is an example that has remained reliable and unbreakable for 20 years.
This approach to the development of ciphers greatly facilitates the process and simplifies security analysis. So, for example, a test attack on a block cipher begins with a minimum number of rounds and methodically continues with an increase in the number of rounds.
Using DES
Although DES is considered obsolete and not up to date, it can be used, for example, in the form of 3DES, when the cipher is applied three times in a row. This approach removes the limitation on the key size, but the block of encrypted data remains the same. At one time, DES was a fairly fast and crypto-strong cipher. Now this is not the case, and 3DES is actually three times slower. Despite this DES is still used in a number of systems, but its use in new projects is prohibited.
DES was the official cipher algorithm in the United States until 1998. In 1997, the creation of a new standard began, which was called System), and although cryptanalysis shows that an attempt to break DES leads to many systems of nonlinear equations, analytical methods cannot help solve the problem - its weak point is the small set of possible keys. Their number is 2 56 and all options can be enumerated using modern technologies in a relatively short time.
One round in the algorithm
For clarity of presentation and description of the DES algorithm, we use Figure (line diagram of calculations) 4.1, showing the structure of one round.
Each rectangle in a line chart represents some kind of calculation, and an arrow outgoing from it indicates where the results of the block will be transferred. The plus sign enclosed in a circle denotes an "exclusive or" operation, known in programming as XOR. The operation is also called "bitwise addition" or "addition without carry". On the net you can find the DES algorithm in C and study it for a better understanding.
DES accepts a 64-bit text block. It goes through the initial permutation according to a certain principle. When analyzing the algorithm, it turned out that there is little sense in this permutation, since it does not give any cryptographic effect. The text block is split into 2 equal parts: right (R) and left (L). Then the encrypted parts are swapped and merged, and at the end of the round, a 64-bit data block is obtained, only encrypted.
General algorithm
The DES algorithm includes 16 rounds, performed according to the scheme described above. All rounds are numbered through i, where i \u003d (1; 16). Each i-th round from a pair (Li-1, Ri-1) gets a new pair (Li, Ri) using the Ki key. The main transformations occur inside the function F.
Algorithm of the function F
As you can see from Figure 4.1, R goes through the Expand operation. This block duplicates a number of bits from R and supplements it with them, getting a 48-bit value. The resulting result goes through a bitwise addition with a 48-bit Ki key. And the result of this operation is transferred to block S. Block S contains 8 small permutation matrices, which are selected in a special way.
Each matrix receives 6 bits of information as input and outputs a 4-bit value. As a result, block S receives 48-bit data at the input, and at the output it represents the result as a 32-bit value.
This 32-bit value goes through one more permutation operation, after which it is summed by the xor operation with L. Finally, the right and left sides are swapped and the round ends. As mentioned earlier, the algorithm makes 16 such rounds.
Here we will not overload the article with examples that take up a lot of space. DES operation and examples can be viewed on the net.
Feistel cipher
DES is based on the Feistel cipher. Its idea is quite elegant. On each round, the L part is added with the value of F (R, Ki) and L changes position with R. The key feature of the Feistel algorithm is that decryption and encryption consist of the same steps: the L and R parts are swapped, and then the addition operation L is performed and F (R, Ki). This makes encryption and decryption procedures simple and straightforward.
One interesting change is often introduced in Feistel ciphers - the abolition of the permutation of L and R in the last iteration. This makes the encryption and decryption algorithms completely symmetric. The only difference is in the order of using the Ki keys. This principle turned out to be extremely convenient for use at the software level, since encryption and decryption are performed by means of one function. For example, a laconic implementation of the DES encryption algorithm in C.
Encryption Keys
DES uses sixteen 48-bit keys to encrypt data. One key per round. Each key is created by sampling 48 bits from a 56-bit master key. Key generation for a given round is determined by a mechanism detailed in the DES documentation.
Briefly, the algorithm for fetching the i key is as follows. Bits are added to the main key at positions 8, 16, 24, 32, 40, 48, 56, 64. This is done in such a way that each byte contains an odd number of ones. Compliance with the rule helps in detecting key exchange errors. Thereafter, using special tables, the padded key undergoes permutations and shifts, except for the bits that have been added. Thus, the required key is obtained.
DES components
Each component of the DES algorithm solves a specific problem:
- Feistel's Algorithm simplifies encryption and decryption while ensuring that both halves of the text are mixed.
- The bitwise summation of parts of the text with keys mixes the public data with the key and encrypts it.
- S-box and lookup tables make the algorithm non-linear, making it more resistant to various attacks.
- Expansion, S-box and permutations provide diffusion of the algorithm - avalanche effect. In other words, if at least 1 bit in the input data of the function F changes, then this will cause a change in many bits at once. If no avalanche effect is observed in the cipher, then changes in open data will lead to equivalent changes in encrypted form, which can be tracked and used for cracking. In cryptography, there is a criterion for the avalanche effect. The algorithm satisfies it if at least half of the encrypted data changes when 1 bit of open data changes. The DES algorithm satisfies it starting from round 4. Bottom line - changing 1 bit of open data in the DES cipher will change 29 bits.
Security issues in DES
The obvious problem with DES is fetching encryption keys from a public key. What happens if zero value is chosen as the key (all bits of the key are equal to 0)? This will lead to the fact that the sample of all keys for encryption in each round will be the same, and all keys will be equal to zero. Not only will 16 encryptions pass with one key, but due to the fact that DES encryption and decryption algorithms differ only in the order in which the keys are used, they will be exactly the same. The whole point of encryption will be lost.
DES has 4 keys, which are called weak keys, leading to the described effect. DES has 12 semi-weak and 48 pseudo-weak keys, which limit the variation of generated keys in rounds. In other words, there is a possibility that in the course of encryption in 16 rounds, not 16 different keys will be used, but 8, 4 or even 2.
A less obvious disadvantage of DES is the complementarity property. It means that if you use plaintext complement and key complement for encryption, you end up with a value that is the complement of the ciphertext. This ridiculous property can lead to successful attacks on projects that use DES for security.
Encryption key problem
It is fundamental to DES and is considered the main reason why it should be abandoned. Since the key size in DES is 56 bits, to iterate over all the keys, you will need to look through 2 56 options. Is it that much?
If we carry out 10 million key checks per second, then the verification will take about 2000 years. The algorithm seems to be quite robust. It was like that in the last century, when building a computer of this power was an almost impossible task from both a technical and financial point of view.
If you create a computer with a million chips, it will take 20 hours to iterate through the entire set of DES keys. The first computer of this kind for decryption using the DES algorithm appeared back in 1998, which coped with the task in 56 hours. Modern technologies of networks and parallel processes can reduce this time even more.
Cryptanalysis and DES
It can be said without exaggeration that DES gave rise to an applied science called "Cryptographic Analysis". From the very beginning of the appearance of DES, attempts were made to crack it, scientific work was carried out to study it. All this led to the birth of such areas of mathematics as:
- linear cryptanalysis - the study and identification of the relationship between plain text and cipher text;
- differential cryptanalysis - the study and analysis of dependencies between several open texts and their encrypted versions;
- cryptanalysis on linked keys - the study of the dependencies between cipher texts obtained on the primary key, and the keys associated with the primary in any way.
DES has withstood 20 years of worldwide cryptanalysis and attacks, but remains a strong cipher. But he who seeks will always find ...
- Biham and Shamir, scientists from Israel, showed in 1991 using differential cryptanalysis that DES can be attacked in which the key is calculated, provided that the attacker has 2,47 specially matched pairs of plain and ciphertext.
- The Japanese scientist Mitsuru Matsui showed in 1993 that the key can be calculated using linear cryptanalysis. To do this, you just need to know 2,47 pairs of plaintext and the corresponding encrypted version.
Later, these hacking methods were slightly improved, improved and simplified, and a number of new hacking methods appeared. But they remain too complex, against their background, a complete enumeration of all key variants looks like the most adequate attack on DES.
Annotation: One of the best known private key cryptographic systems is DES - Data Encryption Standard. This system was the first to receive the status of a state standard in the field of data encryption. And although the old American standard DES has now lost its official status, this algorithm still deserves attention when studying cryptography. In addition, this chapter explains what double DES is, a meet-in-the-middle attack, and how to fix it. The same lecture briefly discusses the new US standard for block ciphers, the Rijndael algorithm.
The purpose of the lecture: Introduce the student to the basics of the DES encryption algorithm.
Basic information
One of the more well-known private key cryptographic systems is DES - Data Encryption Standard... This system was the first to receive the status of a state standard for data encryption. It was developed by specialists of the IBM firm and entered into force in the USA in 1977. Algorithm DES widely used for storing and transferring data between various computing systems; in postal systems, in electronic drawing systems and in electronic exchange commercial information... Standard DES implemented both software and hardware. Enterprises from different countries have launched a mass production of digital devices using DES to encrypt data. All devices have passed mandatory certification for compliance with the standard.
Despite the fact that for some time this system has not had the status of a state standard, it is still widely used and deserves attention when studying block ciphers with a private key.
Key length in the algorithm DES is 56 bits. It is with this fact that the main controversy regarding the ability DES resist various attacks. As you know, any block cipher with a private key can be broken by trying all possible key combinations. With a key length of 56 bits, 2 56 different keys are possible. If a computer enumerates 1,000,000 keys in one second (which is approximately equal to 2 20), then it will take 2 36 seconds to iterate over all 2 56 keys, or a little over two thousand years, which, of course, is unacceptable for intruders.
However, more expensive and faster computing systems are possible than personal Computer... For example, if you have the ability to combine a million processors for parallel computing, then the maximum key selection time is reduced to about 18 hours. This time is not too long, and a cryptanalyst equipped with such an expensive technique may well perform a DES-encrypted attack in a reasonable time.
At the same time, it can be noted that the system DES may well be used in small to medium-sized applications for encrypting data with little value. For encryption of data of national importance or significant commercial value system DES currently, of course, should not be used. In 2001, after a specially announced competition in the United States, a new standard for a block cipher was adopted, called AES (Advanced Encryption Standard), which was based on the cipher Rijndaeldeveloped by Belgian specialists. This cipher is discussed at the end of the lecture.
main parameters DES: block size 64 bits, key length 56 bits, number of rounds - 16. DES is a classic Feistel net with two branches. The algorithm converts a 64-bit input block of data into a 64-bit output block in several rounds. Standard DES built on the combined use of permutation, substitution and gamming. The encrypted data must be in binary form.
Encryption
General structure DES shown in Fig. 4.1. The encryption process for each 64-bit block of source data can be divided into three stages:
- initial preparation of the data block;
- 16 rounds of the "main cycle";
- final processing of the data block.
At the first stage, initial permutation A 64-bit source block of text, during which the bits are reordered in a certain way.
At the next (main) stage, the block is divided into two parts (branches), 32 bits each. The right branch is transformed using some function F and the corresponding partial keyobtained from the main encryption key using a special key conversion algorithm. Then data is exchanged between the left and right branches of the block. This is repeated 16 times in a loop.
Finally, at the third stage, the result obtained after sixteen steps of the main loop is rearranged. This permutation is the opposite of the initial permutation.
Figure: 4.1.
Let's consider in more detail all the stages of cryptographic transformation according to the standard DES.
In the first step, the 64-bit block of original data is subjected to an initial permutation. In the literature, this operation is sometimes called "whitening". At the initial permutation, the bits of the data block are reordered in a certain way. This operation gives some "randomness" to the original message, reducing the possibility of using cryptanalysis by statistical methods.
Simultaneously with the initial permutation of the data block, an initial permutation of 56 bits of the key is performed. Fig. 4.1. it can be seen that in each of the rounds the corresponding 48-bit partial key K i is used. Keys K i are obtained according to a certain algorithm, using each of the bits of the initial key several times. Each round, the 56-bit key is split into two 28-bit halves. Then the halves are shifted to the left by one or two bits, depending on the round number. After the shift, 48 out of 56 bits are selected in a certain way. Since this not only selects a subset of the bits, but also changes their order, this operation is called "permutation with compression". The result is a set of 48 bits. On average, each bit of the original 56-bit key is used in 14 out of 16 subkeys, although not all bits are used the same number of times.
Next, the main transformation cycle is carried out, organized according to the Feistel network and consisting of 16 identical rounds. In this case, in each round (Fig. 4.2) an intermediate 64-bit value is obtained, which is then processed in the next round.
Figure: 4.2.
The left and right branches of each intermediate value are treated as separate 32-bit values, denoted by L and R.
First, the right side of the block R i is expanded to 48 bits using a table that defines the permutation plus the 16 bit extension. This operation resizes the right half to match the key size for the XOR operation. In addition, due to this operation, the dependence of all the bits of the result on the bits of the original data and the key increases faster (this is called the "avalanche effect"). The stronger the avalanche effect is when using one or another encryption algorithm, the better.
After performing the permutation with expansion, the resulting 48-bit value is XORed with the 48-bit subkey K i. Then the resulting 48-bit value is fed to the input of the substitution block S (from the English. Substitution - substitution), the result which is a 32-bit value. Substitution is performed in eight substitution boxes or eight S-boxes. When doing this DES on paper looks quite complicated, let alone its software implementation! Develop a correctly and optimally functioning program completely in accordance with DES, probably, only experienced programmers can do it. Some difficulties arise in software implementation, such as the initial permutation or the expansion permutation. These difficulties are associated with the fact that it was originally planned to implement DES hardware only. All operations used in the standard are easily performed by hardware units, and no implementation difficulties arise. However, some time after the publication of the standard, software developers decided not to stand aside and also take up the creation of encryption systems. Further DES implemented both in hardware and software.
