Des modes. Data Encryption Standard (DES)

Algorithm DES

The main advantages of the DES algorithm:

· only one key with a length of 56 bits is used;

· having encrypted a message using one package, you can use any other to decrypt it;

· the relative simplicity of the algorithm ensures high speed 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 apparent obviousness, this is not always done. Later we will look at ciphers in which encryption and decryption are carried out using different algorithms).

The encryption process consists of an initial permutation of the bits of a 64-bit block, sixteen encryption cycles and, finally, a reverse permutation of the bits (Fig. 1).

It should be immediately noted 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 are selected by the developers in such a way as to make the decryption process as difficult as possible by selecting a key. The structure of the DES algorithm is shown in Fig. 2.

Fig.2. Structure of the DES encryption algorithm

Let the next 8-byte block T be read from the file, which is transformed using the initial permutation matrix IP (Table 1) as follows: bit 58 of block T becomes bit 1, bit 50 becomes bit 2, etc., which will result in : T(0) = IP(T).

The resulting bit sequence T(0) is divided into two sequences of 32 bits each: L(0) - left or high-order bits, R(0) - right or low-order 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. Result i iteration is described by the following formulas:

R(i) = 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 converting 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 positions of the bits of this sequence are rearranged in accordance with the matrix IP -1 (Table 2).

Table 2: Inverse permutation matrix IP -1

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 IP -1 and IP matrices are related as follows: the value of the 1st element of the IP -1 matrix is 40, and the value of the 40th element of the IP matrix is 1, the value of the 2nd element of the IP -1 matrix is 8, and the value of the 8th IP matrix element is equal to 2, etc.

The process of data decryption is inverse to the encryption process. All actions must be performed in reverse order. This means that the decrypted data is first rearranged according to the IP-1 matrix, and then the same actions are performed on the sequence of bits R(16)L(16) as in the encryption process, but in reverse order.

The iterative decryption process can be described by the following formulas:

R(i-1) = L(i), i = 1, 2, ..., 16;

L(i-1) = R(i) xor f(L(i), K(i)), i = 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 such a 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 function f(R(i-1), K(i))

To calculate the value of the function f, the following matrix functions are used:

E - extension of a 32-bit sequence to 48-bit,

S1, S2, ..., S8 - conversion of a 6-bit block into 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: Extension 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 that is added modulo 2 (xor operation) with the 48-bit key K(i). The resulting 48-bit sequence is divided into eight 6-bit blocks B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8). That is:

E(R(i-1)) xor K(i) = B(1)B(2)...B(8) .

Functions S1, S2, ..., S8 are defined in Table 4.

Table 4

To Table 4. further clarification is required. Let the input of the matrix function Sj be a 6-bit block B(j) = b1b2b3b4b5b6, then the two-bit number b1b6 indicates the row number of the matrix, and b2b3b4b5 the column number. The result of Sj(B(j)) will be a 4-bit element located at the intersection of the specified row and column.

For example, B(1)=011011. Then S1(B(1)) is located at the intersection of row 1 and column 13. In column 13 of row 1 the value is 5. This means S1(011011)=0101.

Applying the selection operation to each of the 6-bit blocks B(1), B(2), ..., B(8), we obtain the 32-bit sequence S1(B(1))S2(B(2))S3( B(3))...S8(B(8)).

Finally, to obtain the result of the encryption function, the bits of this sequence must be rearranged. For this purpose, the permutation function P is used (Table 5). In the input sequence, the bits are rearranged so that bit 16 becomes bit 1, bit 7 becomes bit 2, and so on.

Table 5:Permutation function P

Thus,

f(R(i-1), K(i)) = P(S1(B(1)),...S8(B(8)))

To complete the description of the data encryption algorithm, it remains to present the algorithm for obtaining 48-bit keys K(i), i=1...16. At each iteration, a new key value K(i) is used, which is calculated from 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 rearrange the rest, function G of the initial key preparation is used (Table 6).

Table 6

Matrix G of initial key preparation

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 key K. After defining C(0) and D(0), C(i) and D(i), i=1...16, are recursively determined. To do this, apply a cyclic shift to the left by one or two bits, depending on the iteration number, as shown in Table 7.

Table 7

Shift table for key calculation

Iteration number	Shift (bits)
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 Completion 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

The key K(i) will consist of bits 14, 17, ..., 29, 32 of the sequence C(i)D(i). Thus:

K(i) = 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)

Recovery source text is carried out according to this algorithm, but first you use the key

K(15), then K(14) and so on. Now you should understand why the author insistently recommends using the given matrices. If you go rogue, you might end up with a very secret code, but you won't be able to crack it yourself!

Operating modes of the DES algorithm

To most fully meet all the requirements for commercial encryption systems, several modes of operation of the DES algorithm are implemented. The most widely used modes are:

· electronic codebook (Electronic Codebook) - ECB;

· chain of digital blocks (Cipher Block Chaining) - CBC;

· digital feedback (Cipher Feedback) - CFB;

· external feedback (Output Feedback) - OFB.

In this mode original file M is divided into 64-bit blocks (8 bytes each): M = M(1)M(2)...M(n). Each of these blocks is encrypted independently using the same encryption key (Fig. 5). The main advantage of this algorithm is its ease of implementation. The disadvantage is that it is relatively weak against skilled cryptanalysts.

The DES standard is designed to protect against unauthorized access to sensitive but unclassified information in US government and commercial organizations. The algorithm underlying the standard spread quite quickly, and already in 1980 it was approved National Institute US standards and technologies. From this moment on, DES becomes a standard not only in name, but also in fact. Appear software and specialized microcomputers designed to encrypt and decrypt information in data networks.

To date, DES is the most common algorithm used in security systems commercial information. Moreover, the implementation of the DES algorithm in such systems becomes a sign of good form.

The main advantages of the DES algorithm:

· only one key with a length of 56 bits is used;

· having encrypted a message using one package, you can use any other to decrypt it;

· the relative simplicity of the algorithm ensures high speed of information processing;

· sufficiently high stability of the algorithm.

The encryption process consists of an initial bit permutation of a 64-bit block, sixteen encryption cycles, and finally a reverse bit permutation (Figure 1).

Rice. 2.

The resulting bit sequence T(0) is divided into two sequences of 32 bits each: L(0) - left or high-order bits, R(0) - right or low-order 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) = L (i-1) xor f (R(i-1), K(i)),

where xor is the EXCLUSIVE OR operation.

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 IP -1 matrix (Table 2).

Table 2: Inverse permutation matrix IP -1

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 process of data decryption is inverse to the encryption process. All steps must be performed in reverse order. This means that the data to be decrypted is first rearranged according to the IP-1 matrix, and then the same actions are performed on the sequence of bits R(16) L(16) as in the encryption process, but in reverse order.

The iterative decryption process can be described by the following formulas:

R (i-1) = L(i), i = 1, 2,…, 16;

L (i-1) = R(i) xor f (L(i), K(i)), i = 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 such a 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.

Rice. 3.

To calculate the value of the function f, the following matrix functions are used:

E - extension of a 32-bit sequence to 48-bit,

S1, S2,…, S8 - conversion of a 6-bit block into a 4-bit one,

P - permutation of bits in a 32-bit sequence.

The expansion function E is determined by 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: Extension 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 function E (R(i-1)) is a 48-bit sequence that is added modulo 2 (xor operation) with the 48-bit key K(i). The resulting 48-bit sequence is divided into eight 6-bit blocks B(1) B(2) B(3) B(4) B(5) B(6) B(7) B(8). That is:

E (R(i-1)) xor K(i) = B(1) B(2)… B(8).

Functions S1, S2,…, S8 are defined in table. 4.

Table 4

To table 4. Additional clarification is required. Let the input of the matrix function Sj be a 6-bit block B(j) = b1b2b3b4b5b6, then the two-bit number b1b6 indicates the row number of the matrix, and b2b3b4b5 the column number. The result of Sj (B(j)) will be a 4-bit element located at the intersection of the specified row and column.

For example, B(1)=011011. Then S1 (B(1)) is located at the intersection of row 1 and column 13. In column 13 of row 1 the value is 5. This means S1 (011011)=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)).

Table 5: Permutation function P

Thus,

f (R(i-1), K(i)) = P (S1 (B(1)),… S8 (B(8)))

To complete the description of the data encryption algorithm, it remains to present the algorithm for obtaining 48-bit keys K(i), i=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 rearrange the rest, function G of the initial key preparation is used (Table 6).

Table 6

Matrix G of initial key preparation

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 be consist of bits 63, 55,…, 12, 4 keys K. After determining C(0) and D(0), C(i) and D(i), i=1…16, are recursively determined. To do this, apply a cyclic shift to the left by one or two bits, depending on the iteration number, as shown in table. 7.

Table 7. Shift table for key calculation

Iteration number	Shift (bits)

The resulting value is again “mixed” in accordance with the matrix H (Table 8).

Table 8: Key Completion 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

The key K(i) will consist of bits 14, 17,…, 29, 32 of the sequence C(i) D(i). Thus:

K(i) = H (C(i) D(i))

The block diagram of the key calculation algorithm is shown in Fig. 4.

Rice. 4.

Restoring the original text is carried out using this algorithm, but first you use the key K(15), then K(14) and so on. Now you should understand why the author insistently recommends using the given matrices. If you go rogue, you might end up with a very secret code, but you won't be able to crack it yourself!

More than 30 years have passed since the adoption of the DES algorithm as the US encryption standard. DES is an encryption algorithm with the richest and most interesting history.

History of the creation of the algorithm

One of the most famous cryptologists in the world, Bruce Schneier, in his famous book “Applied Cryptography” described the problems of users of information security tools in the early 70s. XX century (naturally we're talking about about users on the other side of the Iron Curtain):

There was neither a generally accepted standard for data encryption nor simply widely used information security algorithms, so compatibility between different software or hardware encryption tools was out of the question;

Almost any encryption tool was a “black box” with rather unclear contents: what encryption algorithm is used, how cryptographically strong it is, whether it is implemented correctly, whether encryption keys are correctly created, stored, used, whether there are any inserted by the developers in the tool undocumented features etc. - all this is very important information for the vast majority of buyers cryptographic means was unavailable.

The National Bureau of Standards (NBS) of the USA was concerned with this problem. As a result, in 1973, the first ever open competition for an encryption standard was announced. NBS was willing to examine candidate algorithms that met the following criteria in order to select a standard:

The algorithm must be cryptographically strong;

The algorithm must be fast;

The structure of the algorithm must be clear and precise;

The strength of encryption should depend only on the key; the algorithm itself should not be secret;

The algorithm should be easily applicable for various purposes;

The algorithm should be easily implemented in hardware using existing hardware components.

It was assumed that interested organizations or specialists would send to NBS detailed specifications of algorithms sufficient for their implementation, i.e., without any “blind spots.” It was also assumed that the algorithm would be certified by the NBS for general use, and all patent and export restrictions would be removed from it, as a result of which such a standard would have to solve all encryption compatibility problems. In addition, NBS took on the functions of certifying encryption tools - that is, “black boxes” should have become a thing of the past.

In fact, there was only one candidate algorithm: it was the Lucifer encryption algorithm developed by ShM (see section 3.31). Over the course of two years, the algorithm was refined:

Firstly, NBS, together with the National Security Agency (NSA, National Security Agency) of the United States, carried out a thorough analysis of the algorithm, which resulted in its fairly significant revision;

Secondly, comments and criticisms from all interested organizations and individuals were taken into account.

As a result joint activities IBM, NBS and NSA in January 1977 DES was published as a US standard ( latest version of this standard - in the document) on the data encryption algorithm (except for information of a high degree of secrecy). The DES algorithm was patented by YuM, but NBS received, in fact, a free and unlimited license to use of this algorithm. An alternative, but less commonly used name for the algorithm is DEA (Data Encryption Algorithm).

Main characteristics and structure of the algorithm

The DES algorithm encrypts information in 64-bit blocks using a 64-bit encryption key that uses only 56 bits (the key expansion procedure is described in detail below).

Encryption of information is performed as follows (Fig. 3.56):

1. An initial permutation is performed on a 64-bit data block according to table. 3.16.

Table 3.16

The table is interpreted as follows: the value of input bit 58 (hereinafter all bits are numbered from left to right, starting from 1) is placed in output bit 1, the value of bit 50 is placed in bit 2, etc.

2. The result of the previous operation is divided into 2 subblocks of 32 bits (per

rice. 3.56 marked A 0 and B 0), over which 16 rounds are performed

the following transformations:

As mentioned above, from a 64-bit encryption key DES algorithm uses only 56 bits. Every 8th bit is discarded and is not used in any way in the algorithm, and the use of the remaining bits of the encryption key in implementations of the DES algorithm is in no way limited by the standard. The procedure for extracting the 56 significant bits of a 64-bit key in Fig. 3.59 is designated as E. In addition to extraction, this procedure also performs permutation of key bits according to table. 3.19 and 3.20.

Table 3.19

Table 3.20

As a result of the permutation, two 28-bit values C and D are formed. Table 3.19 defines the selection of key bits for C, table. 3.20 - for D.

Then 16 rounds of transformations are performed, each yielding one of the round keys K t . In each round of the key expansion procedure, the following actions are performed:

1. Current values of C and D cyclically shifted left by a variable number of bits P. For rounds 1, 2, 9 and 16 P= 1, in the remaining rounds a cyclic shift of 2 bits is performed.

2. C and D are combined into a 56-bit value, to which the compression permutation CP is applied, the result of which is a 48-bit round key K (. The compression permutation is performed according to Table 3.21.

Table 3.21

When decrypting data, you can use the same key expansion procedure, but apply the round keys in reverse order. There is another option: in each round of the key expansion procedure, instead of a cyclic shift to the left, perform a cyclic shift to the right by n bits, where rc' = 0 for the first round, u' = 1 for rounds 2, 9, 16 and n = 2 for the remaining rounds . This key expansion procedure will immediately provide the round keys needed for decryption.

It is worth saying that the ability to perform key expansion “on the fly” (especially if this possibility exists both during encryption and decryption) is considered an advantage of encryption algorithms, since in this case the key expansion can be performed in parallel with encryption and not waste memory on storing the keys of others rounds other than the current one.

The DES algorithm is quite suitable for both encryption and authentication of data. It allows 64-bit plaintext input to be directly converted to 64-bit ciphertext output, but the data is rarely limited to 64 bits.

To use the DES algorithm to solve a variety of cryptographic problems, four operating modes have been developed:

· electronic code book ECB (Electronic Code Book);

· concatenation of CBC cipher blocks (Cipher Block Chaining);

· CFB (Cipher Feed Back) ciphertext feedback;

· feedback on the output OFB (Output Feed Back).

"Electronic code book" mode

Long file are divided into 64-bit segments (blocks) of 8 bytes. Each of these blocks is encrypted independently using the same encryption key (Fig. 3.6).

The main advantage is ease of implementation. Disadvantage: Relatively weak resistance against skilled cryptanalysts. Due to the fixed nature of encryption, with a limited block length of 64 bits, "dictionary" cryptanalysis is possible. A block of this size may be repeated in a message due to the high redundancy in natural language text.

Figure 3.6 – Scheme of the DES algorithm in electronic codebook mode

This causes identical blocks of plaintext in a message to be represented by identical blocks of ciphertext, giving the cryptanalyst some information about the contents of the message.

"Chaining Cipher Blocks" mode

In this mode, the source file M is divided into 64-bit blocks: M = M 1 M 2 ...M n. The first block M 1 is added modulo 2 with a 64-bit initial vector IV, which changes daily and is kept secret (Fig. 3.7). The received amount is then encrypted using a DES key known to both the sender and recipient of the information. The resulting 64-bit cipher C 1 is added modulo 2 with the second block of text, the result is encrypted and a second 64-bit cipher C 2 is obtained, etc. The procedure is repeated until all blocks of text have been processed.

Thus, for all i = 1…n (n is the number of blocks), the encryption result C i is determined as follows: C i =

DES (M i  C i –1), where C 0 = IV – initial value cipher, equal to the initial vector (initialization vector).

Obviously, the last 64-bit ciphertext block is a function of the secret key, the seed vector, and each bit

Figure 3.7 – Scheme of the DES algorithm in cipher block chaining mode

plaintext regardless of its length. This block of ciphertext is called a message authentication code (MAC).

The CAS code can be easily verified by the recipient, who has the secret key and the seed vector, by repeating the procedure performed by the sender. An outsider, however, cannot generate a UAS that is perceived as genuine by the recipient to add to a false message, or separate the UAS from a true message for use with a modified or false message.

Dignity this mode is that it does not allow errors to accumulate during transmission.

Block M i is a function of only C i –1 and C i . Therefore, a transmission error will result in the loss of only two blocks of source text.

"Cypher feedback" mode

In this mode, the block size may differ from 64 bits (Fig. 3.8). The file to be encrypted (decrypted) is read in successive blocks of k bits in length (k=1...64).

The input block (64-bit shift register) first contains a right-aligned initialization vector.

Suppose that as a result of dividing into blocks, we received n blocks of length k bits each (the remainder is appended with zeros or spaces). Then for any i=1…n ciphertext block

С i = M i  P i –1 ,

where P i–1 denotes the k most significant bits of the previous encrypted block.

The shift register is updated by removing its highest k bits and writing C i to the register. Recovering encrypted data is also relatively simple: P i –1 and C i are calculated in a similar way and

М i = С i  Р i –1 .

Figure 3.8 – Scheme of the DES algorithm in mode feedback by ciphertext

Output feedback mode

This mode also uses variable block size and shift register, initialized in the same way as in CFB mode, namely, the input block first contains the initialization vector IV, aligned to the right (Fig. 3.9). In this case, for each data encryption session, it is necessary to use a new initial state of the register, which must be sent over the channel in clear text.

M = M 1 M 2 ... M n.

For all i = 1… n

C i = M i  P i ,

where Р i are the highest k bits of the DES operation (С i –1).

The difference from the ciphertext feedback mode is the method of updating the shift register.

This is done by discarding the highest k bits and adding P i to the right.

Figure 3.9 – Scheme of the DES algorithm in output feedback mode

3.3. Areas of application of the DES algorithm

Each of the considered modes (ECB, CBC, CFB, OFB) has its own advantages and disadvantages, which determines the areas of their application.

ECB mode is well suited for key encryption: CFB mode, as a rule, is intended for encryption of individual characters, and the OFB mode is often used for encryption in satellite systems communications.

The CBC and CFB modes are suitable for data authentication. These modes allow you to use the DES algorithm to:

· interactive encryption when exchanging data between the terminal and the host computer;

· encryption cryptographic key in the practice of automated key distribution;

· file encryption, postal items, satellite data and other practical problems.

Initially, the DES standard was intended for encryption and decryption of computer data. However, its application has been generalized to authentication.

In systems automatic processing data, a person is not able to review the data to determine whether any changes have been made to it. With huge amounts of data passing through modern systems processing, viewing would take too long. In addition, data redundancy may not be sufficient to detect errors. Even in cases where human review is possible, the data may be changed in ways that make it very difficult for humans to detect the changes. For example, “do” can be replaced with “do not”, “$1900” with “$9100”. Without additional information a person viewing it can easily mistake the altered data for genuine data. Such dangers may exist even when data encryption is used. Therefore it is advisable to have automatic tool detecting intentional and unintentional data changes.

Ordinary codes that detect errors are unsuitable, since if the algorithm for generating the code is known, the enemy can develop correct code after making changes to the data. However, using the DES algorithm it is possible to form a cryptographic checksum, which can protect against both accidental and deliberate but unauthorized changes to data.

This process describes the standard for computer data authentication (FIPS 113). The essence of the standard is that data is encrypted in ciphertext feedback mode (CFB mode) or in cipher block concatenation mode (CBC mode), resulting in a final cipher block that is a function of all the plaintext bits. The message, which contains the plaintext, can then be transmitted using the calculated final cipher block, which serves as a cryptographic checksum.

The same data can be protected using both encryption and authentication. Data is protected from access by encryption, and changes are detected through authentication. The authentication algorithm can be applied to both plaintext and ciphertext. In financial transactions, where in most cases both encryption and authentication are implemented, the latter also applies to open

mu text.

Encryption and authentication are used to protect data stored in a computer. In many computers, passwords are encrypted irreversibly and stored in the machine's memory. When a user accesses the computer and enters a password, the latter is encrypted and compared with the stored value. If both encrypted values are the same, the user gains access to the machine, otherwise it is denied.

Often, an encrypted password is generated using the DES algorithm, with the key equal to the password and the plaintext equal to the user identification code.

Using the DES algorithm, you can also encrypt computer files for storage.

One of most important applications algorithm DES is message protection electronic system payments (ESP) for transactions with a wide clientele and between banks.

The DES algorithm is implemented in ATMs, terminals in retail outlets, automated workstations and mainframe computers. The range of data it protects is very wide - from payments of $50 to transfers of many millions of dollars. The flexibility of the core DES algorithm allows it to be used in a wide variety of electronic payment system applications.

Tutorial

Hello %username%!
Many people know that the default standard in the field symmetric encryption for a long time The DES algorithm was considered. 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 2 47 pairs of plain/ciphertexts, makes it possible to crack The secret key DES cipher in 2 43 operations.
Below the cut I will try to briefly outline 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 case An attack based on linear cryptanalysis boils down to the following conditions. The attacker has big amount plaintext/ciphertext pairs obtained using the same encryption key K. The attacker's goal is to recover part or all of the key K.

First of all, the attacker examines the cipher and finds the so-called statistical analogue, i.e. the equation the following type, which executes with probability P ≠ 1/2 for an arbitrary public/private text pair and a fixed key:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib = 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.
Once such an equation is found, the attacker can recover 1 bit of key information using the following algorithm

Algorithm 1
Let T be the number of texts for which left side equation (1) equals 0, then
If T>N/2, where N is the number of known plaintexts.
Assume that K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (when P>1/2) or 1 (when P<1/2).
Otherwise
Assume that K I1 ⊕ K I2 ⊕… ⊕ K Ic = 1 (when P>1/2) or 0 (when P<1/2).
It is obvious that 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 number of open texts N is needed for the attack.

There are two problems that need to be solved for the attack to be successful:

How to find an effective equation of the form (1).
How to use this equation to get more than one bit of information about the key.

Let's consider the solution to these issues using the DES cipher as an example.

Description of DES

But first, let's briefly describe how the algorithm works. Enough has already been said about DES. A full description of the cipher can be found on Wikipedia. However, to further explain the attack we will 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 encryption scheme of the DES algorithm.

As can be seen from the figure, when encrypting text, the following operations are performed:

Initial bit permutation. At this stage, the bits of the input block are shuffled in a certain order.
After this, 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 other variants of the algorithm exist.
The two blocks obtained in the last round of transformation are combined and another permutation is performed on the resulting block.

In each round of the Feistel network, the least significant 32 bits of the message are passed through the function f:

Let's look at the operations performed at this stage:

The input block is passed through the extension function E, which converts a 32-bit block into a 48-bit block.
The resulting block is added to the round key K i .
The result of the previous step is divided into 8 blocks of 6 bits each.
Each of the received blocks B i is passed through the substitution function S-Box i , which replaces the 6-bit sequence with a 4-bit block.
The resulting 32-bit block is passed through the permutation P and returned as the result of function f.

Of greatest interest to us from the point of view of cipher cryptanalysis are S blocks, designed to hide the connection between the input and output data of the function f. To successfully attack DES, we will first construct statistical analogues for each of the S-boxes, and then extend them to the entire cipher.

S block analysis

Each S-box takes a 6-bit sequence as input, and for each such sequence a fixed 4-bit value is returned. Those. there are a total of 64 input and output options. Our task is to show the relationship between the input and output data of S blocks. For example, for the third S-box of the DES cipher, the 3rd bit of the input sequence is equal to the 3rd bit of the output sequence in 38 out of 64 cases. Therefore, we found the following statistical analogue for the third S-box:
S 3 (x) = x, which is fulfilled with probability P=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 satisfied with a probability of 1/2. Thus, we have just demonstrated the relationship between the input and output of the 3rd S-box of the DES algorithm.

Let's consider how we can find a statistical analogue of the S-box in the general case.

For an 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 the α bits are equal to the XOR output bits superimposed on the α bits β, i.e.:
where the symbol is logical AND.
The values of α and β for which NS a (α, β) is most different from 32 describe the most efficient statistical analogue of the S-box S a .

The most effective analogue was found in the 5th S-box of the DES cipher for α = 16 and β = 15 NS 5 (16, 15) = 12. This means that the following equation holds: Z=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-box, the data is added modulo 2 with a round key, i.e. Z = X ⊕ K we get
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, where X and Y are the input and output data of the function f without taking into account permutations.
The resulting equation is executed on all rounds of the DES algorithm with the same probability P=12/64.
The following table shows a list of effective ones, i.e. having the greatest deviation from P=1/2, statistical analogues for each s-block of the DES algorithm.

Constructing statistical analogues for multiple rounds of DES

Let us now show how we can combine the statistical analogues of several rounds of DES and ultimately obtain a statistical analogue for the entire cipher.
To do this, consider a three-round version of the algorithm:

Let's use an efficient statistical analogue of the 5th s-box to calculate certain bits of the X(2) value.
We know that with probability 12/64 the equality holds in the f-function X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = 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. By analyzing the expansion function, we can establish that the 26th bit is replaced by 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. Examining the permutation P, we find that the bits Y,..., Y are actually bits Y(1), Y(1), Y(1), Y(1).
The key bit K involved in the equations is the 26th bit of the first round subkey K1 and then the statistical analogue takes the following form:
X(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y1 ⊕ Y(1) = K1.
Hence, X(1) ⊕ K1 = Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1)(2) with probability P=12/64.
Knowing 3, 8, 14, 25 bits of the sequence Y(1), you can find 3, 8, 14, 25 bits of the sequence X(2):
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = 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) = 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 = Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3).
Because
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
we get that
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = 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 = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 with probability (12/64) 2 +(1-12/64) 2 .
Taking into account the fact that X(1) = PR and X(3) = CR we obtain a statistical analogue
СL ⊕ CR ⊕ PL ⊕ PR = K1 ⊕ K3 (5) ,
which is executed with probability (12/64) 2 + (1-12/64) 2 =0.7.
The statistical analogue described above can be represented graphically as follows (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, so he can apply Algorithm 1 and find out the value of K1 ⊕ K3. Let's show how, using this statistical analogue, you can open not 1, but 12 bits of the encryption key K.

Attack on DES with Known Plaintext

Let us present a method by which you can expand the attack and immediately obtain 6 bits of the first round connect.
When 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 analog K1 ⊕ PR.
Let us return the value F1(PR, K1) instead of the expression K1 ⊕ PR and obtain the following equation:
СL ⊕ CR ⊕ PL ⊕ F1(PR, K1) = K3 (6) , which will be executed with probability 12/64. The probability has changed since we left only the statistical analogue from the third round, all other values are 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 key bits K1 and the bits of the PR block. Let's 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 take the following steps.
For (i=0; i<64; i++) do
{
For(j=0; j {
if(СL j ⊕ CR j ⊕ PL j ⊕ F1(PR j , i)=0) then
T i =T i +1
}
}
As a probable sequence K1, a value of i is taken such that the expression |T i -N/2| has the maximum value.

Given a sufficient number of known plaintexts, the algorithm will have a high probability of returning the correct value of the six bits of the first round subkey K1. 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 for 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 probability 12/64. Those. there will be a significant deviation from N/2.

Having received 6 bits of subkey K1, you can similarly open 6 bits of subkey K3. All you need to do is replace C with P and K1 with K3 in equation (6):
PL ⊕ PR ⊕ CL ⊕ F3(CR, K3) = K1.
Algorithm 2 will return the correct K3 value because the decryption process of the DES algorithm is identical to the encryption process, just the key sequence is reversed. So in the first round of decryption the key K3 is used, and in the last round the key K1 is used.

Having received 6 bits of subkeys K1 and K3, the attacker recovers 12 bits of the common key of the cipher K, because round keys are the usual permutation of the key K. The number of plaintexts required for a successful attack depends on the probability of the statistical analogue. To crack a 12-bit 3-round DES key, 100 public/private text pairs are sufficient. To open 12 bits of a 16-round DES key, about 2 44 pairs of texts will be required. The remaining 44 bits of the key are opened using normal brute force.