DES, the domestic encryption standard, is more convenient for software implementation.

Unlike the American DES, the domestic standard uses a longer key - 256 bits. In addition, the Russian standard suggests using 32 rounds of encryption, while DES only requires 16.

Thus, the main parameters of the GOST 28147-89 cryptographic data transformation algorithm are as follows: block size is 64 bits, key size is 256 bits, number of rounds is 32.

The algorithm is a classical Feishtel network. The encrypted data block is divided into two identical parts, right R and left L. The right part is added to the round subkey and, using some algorithm, encrypts the left part. Before the next round, the left and right parts are swapped. This structure allows the same algorithm to be used for both encryption and decryption of a block.

The encryption algorithm uses the following operations:

• addition of words modulo 2 32;
• cyclically shift the word to the left by the specified number of bits;
• bitwise addition modulo 2;
• replacement according to the table.

At different steps of GOST algorithms, the data they operate on is interpreted and used in different ways. In some cases, data elements are treated as arrays of independent bits, in other cases as an unsigned integer, in others as having a structure complex element, consisting of several simpler elements.

Round structure GOST 28147-89

The structure of one round of GOST 28147-89 is shown in Fig. 5.1.

The encrypted data block is split into two parts, which are then processed as separate 32-bit unsigned integers. First, the right half of the block and the subkey of the round are added modulo 2 32. Then block-by-block substitution is performed. The 32-bit value obtained in the previous step (let's call it S) is interpreted as an array of eight 4-bit code blocks: S=(S 0 ,S 1 ,S 2 ,S 3 ,S 4 ,S 5 ,S 6 ,S 7 ). Next, the value of each of the eight blocks is replaced with a new one, which is selected from the replacement table as follows: the value of the block S i is replaced by the S i -th element in order (numbering from zero) of the i-th replacement node (i.e., the i-th row replacement tables, numbering also from scratch). In other words, an element with a row number equal to the number of the block being replaced and a column number equal to the value of the block being replaced as a 4-bit non-negative integer is selected as a replacement for the value of the block. Each line of the replacement table contains numbers from 0 to 15 in random order without repetition. The values ​​of the substitution table elements are taken from 0 to 15, since the four bits that are substituted can contain an unsigned integer in the range from 0 to 15. For example, the first row of an S-box might contain the following values: 5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11 . In this case, the value of the block S 0 (the four least significant bits of the 32-bit number S) will be replaced by the number at the position whose number is equal to the value of the block being replaced. If S 0 = 0, then it will be replaced by 5, if S 0 = 1, then it will be replaced by 8, etc.

Rice. 5.1.

After substitution is performed, all 4-bit blocks are concatenated again into a single 32-bit word, which is then rotated 11 bits to the left. Finally, using the bitwise operation "sum modulo 2" the result is combined with the left half, resulting in a new right half of R i . The new left side L i is taken equal to the low part of the converted block: L i = R i-1 .

The resulting value of the converted block is considered as the result of one round of the encryption algorithm.

Encryption and decryption procedures

GOST 28147-89 is a block cipher, therefore data conversion carried out in blocks in the so-called basic cycles. Basic loops consist of repeated execution of the main round we discussed earlier for a data block, using different key elements and differ from each other in the order in which the key elements are used. Each round uses one of eight possible 32-bit subkeys.

Let's look at the process of creating round subkeys. In GOST this procedure is very simple, especially compared to DES. The 256-bit key K is divided into eight 32-bit subkeys, denoted K0, K1, K2,K3, K4, K5, K6, K7. The algorithm includes 32 rounds, so each subkey during encryption is used in four rounds in the sequence presented in table 5.1.

Table 5.1. Sequence of using subkeys during encryption

Round	1	2	3	4	5	6	7	8
Full construction	K 0	K 1	K2	K 3	K 4	K5	K 6	K 7
Round	9	10	11	12	13	14	15	16
Full construction	K 0	K 1	K2	K 3	K 4	K5	K 6	K 7
Round	17	18	19	20	21	22	23	24
Full construction	K 0	K 1	K2	K 3	K 4	K5	K 6	K 7
Round	25	26	27	28	29	30	31	32
Full construction	K 7	K 6	K5	K 4	K 3	K2	K 1	K 0

The decryption process is carried out using the same algorithm as encryption. The only difference is the order in which the K i subkeys are used. When decrypting, the subkeys must be used in reverse order, namely as indicated in

This algorithm is mandatory for use as an encryption algorithm in government organizations of the Russian Federation and a number of commercial ones.

Description of the algorithm

The algorithm diagram is shown in Fig. 3.1. As you can see, the design of this algorithm is quite simple, which clearly simplifies its software or hardware implementation.

The GOST 28147-89 algorithm encrypts information in blocks of 64 bits, which are divided into two subblocks of 32 bits (N1 and N2). Subblock N1 is processed in a certain way, after which its value is added up

with the value of subblock N2 (addition is performed modulo 2), then the subblocks are swapped. This transformation is performed in a certain number of rounds: 16 or 32, depending on the operating mode of the algorithm (described below). In each round the following operations are performed:

1. Key application. The contents of the /VI subblock are added modulo 2 32 with part of the Kx key.

The encryption key of the GOST 28147-89 algorithm has a dimension of 256 bits, and Kx is its 32-bit part, i.e. the 256-bit encryption key is represented as a concatenation of 32-bit subkeys (Fig. 3.2):

Shch ATI, AG2, Yu, AG4, K5, Kb, K7.

During the encryption process, one of these subkeys is used, depending on the round number and the operating mode of the algorithm.

Rice. 3.1. Algorithm diagram GOST 28147-

Rice. 3.2. Encryption key of the GOST 28147-89 algorithm

2. Table replacement. After keying, the /VI subblock is divided into 8 parts of 4 bits, the value of each of which is individually replaced in accordance with the replacement table for this part of the subblock. Table substitutions (Substitution box, S-box) are often used in modern encryption algorithms, so it is worth considering them in more detail.

Table substitution is used in this way: a block of data of a certain size (in this case, 4-bit) is supplied to the input, the numerical representation of which determines the number of the output value. For example, we have an S-box of the following form:

4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.

Let the 4-bit block “0100” come to the input, i.e. the value 4. According to the table, the output value will be equal to 15, i.e. “1111” (0 is replaced by 4, 1 by 11, the value of 2 remains unchanged, etc.).

As you can see, the algorithm design is very simple, which means that the greatest burden of data encryption falls on the replacement tables. Unfortunately, the algorithm has the property that there are “weak” replacement tables, using which the algorithm can be solved by cryptanalytic methods. Weak ones include, for example, a table in which the output is equal to the input:

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.

3. Bitwise cyclic shift to the left by 11 bits.

Algorithm operation modes

The GOST 28147-89 algorithm has 4 operating modes:

□ simple replacement mode;

□ gamma mode;

P gamma mode with feedback;

□ mode of development of imitation attachments.

These modes are somewhat different from the generally accepted ones (described in Section 1.4), so it is worth considering them in more detail.

These modes have different purposes, but use the same encryption transformation described above.

Easy replacement mode

In simple replacement mode, each 64-bit block of information is simply encrypted using the 32 rounds described above. 32-bit subkeys are used in the following sequence:

□ KO, Kl, K2, KZ, K4, K5, KB, AG7, KO, ATI, etc. - in rounds 1 to 24;

□ K1, Kb, K5, K4, KZ, K2, K\, KO - in rounds from 25 to 32.

Decryption in simple replacement mode is performed in exactly the same way, but with a slightly different sequence of using subkeys:

□ KO, K\, K2, KZ, K4, K5, Kb, KP - in rounds 1 to 8;

□ KP, Kb, K5, K4, KZ, K2, K\, KO, K1, Kb, etc. - in rounds from 9 to 32.

Similar to the standard ECB mode, due to the separate encryption of blocks, the simple replacement mode is strictly not recommended for encrypting the data itself; it should only be used to encrypt other encryption keys in multi-key schemes.

Gamma mode

In gamma mode (Fig. 3.3), each plaintext block is added bit by bit modulo 2 to a 64-bit cipher gamma block. The gamma cipher is a special sequence that is generated using the transformations described above as follows:

1. Their initial filling is written to registers N1 and N2 - a 64-bit value called the “sync message” (the sync message is practically an analogue of the initialization vector in the CBC, CFB and OFB modes).

2. The contents of the /VI and N2 registers (in this case, sync messages) are encrypted in simple replacement mode.

3. The contents of N1 are added modulo (2 32 – 1) with the constant CI = 2 24 + 2 16 + 2 8 + 4, the result of the addition is written to the /VI register.

4. The contents of N2 are added modulo 2 with the constant C2 = 2 24 + 2 16 + 2 8 +1, the result of the addition is written to register N2.

5. The contents of the /VI and N2 registers are output as a 64-bit cipher gamma block (i.e., in this case, /VI and N2 form the first gamma block).

6. If the next gamma block is needed (i.e., further encryption or decryption needs to be done), return to step 2.

For decryption, gamma is generated in a similar manner, then the ciphertext and gamma bits are again XORed.

To generate the same cipher range, the user decrypting the cryptogram must have the same key and the same synchronization message value that were used when encrypting the information. Otherwise, it will not be possible to obtain the original text from the encrypted one.

In most implementations of the GOST 28147-89 algorithm, the sync message is not a secret element, however, the sync message can be as secret as the encryption key. In this case, we can consider that the effective key length of the algorithm (256 bits) increases by another 64 bits of the synchronization message, which can be considered as an additional key element.

Gamma mode with feedback

In the gamma mode with feedback, the result of encrypting the previous block of plaintext is used to fill the /VI and L/2 registers, starting from the 2nd block, not the previous gamma block, but the result of encrypting the previous plaintext block (Fig. 3.4). The first block in this mode is generated completely similarly to the previous one.

Rice. 3.4. Generating a cipher gamma in the gamma mode with feedback

Imitation attachment production mode

A prefix is ​​a cryptographic checksum calculated using an encryption key and designed to verify the integrity of messages. To calculate it, there is a special mode of the GOST 28147-89 algorithm.

Generating an imitation prefix is ​​performed as follows:

1. The first 64-bit block of information for which the imitation prefix is ​​calculated is written to registers N1 and N2 and encrypted in the reduced simple replacement mode, in which the first 16 rounds out of 32 are performed.

2. The result obtained is summed modulo 2 with the next block of information, storing the result in N1 and N2.

3. M and N2 are encrypted again in the shortened simple replacement mode, etc. until the last block of information.

The imitation prefix is ​​considered to be the 64-bit resulting contents of registers N1 and N2 or part thereof. Most often, a 32-bit imitative prefix is ​​used, i.e. half the contents of the registers. This is enough, since, like any checksum, the imitation attachment is intended, first of all, to protect against accidental distortion of information. To protect against intentional modification of data, other cryptographic methods are used - primarily electronic digital signature(see section 1.1).

The imitation prefix is ​​used as follows:

1. When encrypting any information, the plaintext imitation prefix is ​​calculated and sent along with the ciphertext.

2. After decryption, the imitation prefix is ​​again calculated and compared with the one sent.

3. If the calculated and sent imitation prefixes do not match, the cipher text was distorted during transmission or incorrect keys were used during decryption.

The imitation prefix is ​​especially useful for checking the correct decryption of key information when using multi-key schemes.

The imitation prefix is ​​some analogue of the MAC message authentication code, calculated in the CBC mode; The difference is that when calculating the imitation prefix, the synchronization message is not used, whereas when calculating the MAC, the initialization vector is used.

Algorithm cryptographic strength

In 1994, the description of the GOST 28147-89 algorithm was translated into English and published; it was after this that the results of its analysis, carried out by foreign specialists, began to appear; however, no attacks approaching feasibility were found for a considerable time.

□ large key length - 256 bits; together with the secret synchronization message, the effective key length increases to 320 bits;

□ 32 rounds of transformations; already after 8 rounds the full effect of dispersion of the input data is achieved: changing one bit of the plaintext block will affect all bits of the ciphertext block, and vice versa, i.e. there is a multiple strength margin.

Let's consider the results of cryptanalysis of the GOST 28147-89 algorithm.

Analysis of substitution tables

Since replacement tables are not provided in the standard, a number of works (for example, in) suggest that a “competent organization” can issue both “good” and “bad” replacement tables. However, the famous expert Bruce Schneier calls such assumptions “rumors.” It is clear that the cryptographic strength of the algorithm largely depends on the properties of the replacement tables used; accordingly, there are weak replacement tables (see example above), the use of which can simplify the attack of the algorithm. Nevertheless, the possibility of using different replacement tables seems like a very worthy idea, in favor of which the following two facts from the history of the DES encryption standard can be cited (for details, see Section 3.15):

□ attacks using both linear and differential cryptanalysis of the DES algorithm use specific features of replacement tables; when using other tables, cryptanalysis will have to start over;

□ attempts have been made to strengthen DES against linear and differential cryptanalysis by using more robust substitution tables; such tables, which are indeed more robust, were proposed, for example, in the s 5 DES algorithm; but, alas, it was impossible to replace DES with s 5 DES, since the replacement tables are strictly defined in the standard, and accordingly, implementations of the algorithm probably do not support the ability to change tables to others.

A number of works (for example, , and ) erroneously conclude that the secret replacement tables of the GOST 28147-89 algorithm can be part of the key and increase its effective length (which is not significant, since the algorithm has a very large 256-bit key). However, the work proves that secret replacement tables can be calculated using the following attack, which can be used practically:

1. The zero key is set and the search for the “zero vector” is performed, i.e. the value z = /(0), where /() is the round function of the algorithm. This stage takes about 2 encryption operations.

2. Using the zero vector, the values ​​of the replacement tables are calculated, which takes no more than 2 11 operations.

Algorithm modifications and their analysis

The work carried out a cryptanalysis of modifications of the GOST 28147-89 algorithm:

□ GOST-H algorithm, in which, relative to the original algorithm, the order of using subkeys has been changed, namely in rounds from 25 to 32 subkeys are used in direct order, i.e. exactly the same as in previous rounds of the algorithm ;

□ 20-round GOST® algorithm, in which a round uses XOR instead of modulo-2 addition to overlay the key.

Based on the results of the analysis, it was concluded that GOST-H and GOST© are weaker than the original GOST 28147-89 algorithm, since both have classes of weak keys. It is worth noting that in terms of GOST© cryptanalysis, the work repeats word for word the section devoted to the cryptanalysis of the GOST 28147-89 algorithm, a well-known work published in 2000 (without any references to the original). This calls into question the professionalism of the authors of the work and its other results.

A very interesting modification of the algorithm was proposed in the work: tables S\…Ss must necessarily be different; in each round of the algorithm they must be rearranged according to a certain law. This permutation may be dependent on the encryption key, or it may also be secret (i.e., be part of a larger encryption key than the original 256-bit key). Both of these options, according to their authors, significantly increase the resistance of the algorithm against linear and differential cryptanalysis.

And one more modification related to substitution tables is given in the work, in which one of the possible methods calculation of replacement tables based on the encryption key. The authors of the work concluded that such a dependence weakens the algorithm, since it leads to the presence of weak keys and to some potential vulnerabilities of the algorithm.

Full-Round Algorithm Analysis

There are also attacks on full-round GOST 28147-89 without any modifications. One of the first open works, in which an analysis of the algorithm was carried out, a well-known work, is devoted to attacks that exploit the weaknesses of the key expansion procedure of a number of well-known encryption algorithms. In particular, the full-round GOST 28147-89 algorithm can be broken using differential cryptanalysis on related keys, but only if weak replacement tables are used. The 24-round version of the algorithm (in which the first 8 rounds are missing) is opened in a similar way with any replacement tables, but strong replacement tables (for example, the one given in) make such an attack completely impractical.

Domestic scientists A.G. Rostovtsev and E.B. Makhovenko in 2001 proposed in their work that new method cryptanalysis (according to the authors, significantly more effective than linear and differential cryptanalysis) by forming an objective function from a known plaintext, the corresponding ciphertext and the desired key value and finding its extremum corresponding to the true value of the key. They also found a large class of weak keys of the GOST 28147-89 algorithm, which make it possible to open the algorithm using only 4 selected plaintexts and the corresponding ciphertexts with a fairly low complexity. Cryptanalysis of the algorithm is continued in the work.

In 2004, a group of specialists from Korea proposed an attack that, using differential cryptanalysis on related keys, can obtain 12 bits of the secret key with a probability of 91.7%. The attack requires 2 35 selected plaintexts and 2 36 encryption operations. As you can see, this attack is practically useless for actually breaking the algorithm.

). At the same time, in the Russian media and blogs of Russian users, the number of notes about this algorithm is growing: both covering the results of attacks on the Russian standard with varying degrees of reliability, and containing opinions about its operational characteristics. The authors (and, consequently, readers) of these notes often get the impression that the domestic encryption algorithm is outdated, slow and has vulnerabilities that make it significantly more susceptible to attacks than foreign encryption algorithms with a similar key length. With this series of notes we would like to accessible form talk about the current state of affairs with the Russian standard. The first part will cover all attacks on GOST 28147-89 known to the international cryptographic community and current assessments of its strength. In future publications, we will also take a closer look at the properties of the standard from the point of view of the ability to build effective implementations.

Nicolas Courtois - "the great and terrible"

Let's start with a story about the activities of Nicolas Courtois, who is the author of a whole series of works devoted to the Russian block encryption standard ().

In October 2010, the process of considering the inclusion of the GOST 28147-89 algorithm in the international standard ISO/IEC 18033-3 began. Already in May 2011, an article by the famous cryptographer Nicolas Courtois appeared on the ePrint electronic archive, marked by a very ambiguous attitude towards him from the world cryptographic community. Courtois's publications are a sad example of the manipulation of concepts, which does not reveal any new properties of the object in question, but with a claim to sensation provokes the spread of erroneous opinions about its actual properties in an incompetent environment.

Algebraic method

Courtois's reasoning is built around two classes of cryptanalysis methods: algebraic methods and differential ones. Let's look at the first class of methods.

In a simplified way, the method of algebraic cryptanalysis can be described as the compilation and solution of a large system of equations, each of the solutions of which corresponds to the goal of the cryptanalyst (for example, if a system is compiled using one pair of plaintext and ciphertext, then all solutions of this system correspond to the keys at which this plaintext is converted into this one is encrypted). That is, in the case of the problem of cryptanalysis of a block cipher, the essence of the algebraic method of cryptanalysis is that the key is found as a result of solving a system of polynomial equations. The main difficulty is to be able to compose as many as possible, taking into account the characteristics of a particular cipher. simple system so that the process of solving it takes as little time as possible. Here the key role is played by the features of each specific cipher being analyzed.

The algebraic method used by Courtois can be briefly described as follows. At the first stage, such properties of GOST 28147-89 are used as the existence of a fixed point for part of the encryption transformation, as well as the so-called reflection point. Thanks to these properties, several pairs are selected from a sufficiently large number of plaintext-ciphertext pairs, which make it possible to consider transformations not at 32, but only at 8 rounds. The second stage is that, based on the results of 8 round transformations obtained at the first stage, a system of nonlinear equations is constructed, in which the key bits are unknowns. Next, this system is solved (this sounds simple, but in reality is the most time-consuming part of the method, since the system consists of non-linear equations).

As noted above, nowhere in the work is there a detailed description and analysis of the complexity of the second and main stage of determining the key. It is the complexity of the second stage that determines the complexity of the entire method as a whole. Instead, the author provides the notorious “facts” on the basis of which he makes estimates of labor intensity. These "facts" are said to be based on experimental results. An analysis of the “facts” from Courtois’s work as a whole is given in the work of domestic authors. The authors of this work note that many of Courtois’ “facts” presented without any evidence were found to be false during experimental testing. The authors of the article went further and, following Courtois, carried out an analysis of the complexity of the second stage using well-founded algorithms and estimates. The resulting complexity estimates show the complete inapplicability of the presented attack. In addition to domestic authors, the big problems that Courtois has with assessments and justification of his methods were also noted, for example, in the work.

Differential method

Let's consider the second Courtois method, which is based on differential cryptanalysis.

The general method of differential cryptanalysis is based on the exploitation of the properties of nonlinear mappings used in cryptographic primitives, associated with the influence of the key value on the dependencies between the differences between pairs of input and pairs of output values ​​of these mappings. Let us describe the main idea of ​​the differential method of cryptographic analysis of a block cipher. Typically, block ciphers transform the input data in stages using a number of so-called round transformations, and each round transformation does not use the entire key, but only some part of it. Let's consider a slightly “truncated” cipher, which differs from the original one in that it does not have the last round. Let us assume that it has been possible to establish that encrypting two plaintexts that differ in some fixed positions using such a “truncated” cipher will most likely result in ciphertexts that also differ in some fixed positions. This property shows that a “truncated” cipher most likely leaves a dependency between some plaintexts and the results of their encryption. In order to recover part of the key using this obvious flaw, it is necessary to be able to encrypt pre-selected plaintexts on the key we want to recover (the so-called “chosen plaintext attack”). At the beginning of the “key opening” procedure, a number of pairs of plaintexts are randomly generated, differing in those same fixed positions. All texts are encrypted using a “full” cipher. The resulting ciphertext pairs are used to recover those key bits that were used in the last round transformation, as follows. Using some randomly selected value of the desired key bits, a transformation inverse to the last round transformation is applied to all ciphertexts. In fact, if we guessed the desired value of the key bits, we will get the result of a “truncated” cipher, and if we didn’t guess, we will actually “encrypt the data even more,” which will only reduce the dependence between blocks noted above (the difference is in some fixed positions). In other words, if among the results of such “additional processing” of ciphertexts there were quite a lot of pairs that differ in the fixed positions known to us, then this means that we have guessed the required key bits. Otherwise, there will be significantly fewer such pairs. Since only part of the key is used in each round, there are not as many searched bits (that is, the key bits used in the last round) as there are bits in in full key and you can simply sort through them by repeating the above steps. In this case, we will definitely stumble upon the correct meaning someday.

From the above description it follows that the most important thing in the differential analysis method is the numbers of those very positions in plaintexts and ciphertexts, the differences in which play a key role in recovering the key bits. The fundamental presence of these positions, as well as the set of their numbers, directly depends on the properties of those nonlinear transformations that are used in any block cipher (usually all the “nonlinearity” is concentrated in the so-called S-boxes or replacement nodes).

Courtois uses a slightly modified version of the differential method. Let us immediately note that Courtois conducts his analysis for S-boxes that are different from the current ones and from those proposed in ISO. The work provides differential characteristics (those numbers in which the blocks should differ) for a small number of rounds. The justification for extending the characteristics for more rounds is, as usual, based on “facts”. Courtois expresses, again, with nothing other than his authority, an unsupported assumption that changing the S-boxes will not affect the resistance of GOST 28147-89 against his attack (while for unknown reasons, the S-boxes from the 1st working draft of the addition to the standard ISO/IEC 18033-3 was not considered). The analysis carried out by the authors of the article shows that even if we take Courtois’s unfounded “facts” on faith and analyze GOST 28147-89 with other S-blocks, the attack again turns out to be no better than a complete search.

A detailed analysis of Courtois’s works with a detailed substantiation of the groundlessness of all statements about the decrease in the resistance of the Russian standard was carried out in the works [,].

At the same time, even Courtois himself admits the absolute lack of accuracy in the calculations! The following slide is taken from Courtois' presentation at the FSE 2012 short notice section.

It should be noted that Courtois’s work has also been repeatedly criticized by foreign researchers. For example, his work on constructing attacks on the AES block encryption algorithm using the XSL method contained the same fundamental flaws as the work on the analysis of the Russian standard: most of the labor intensity estimates appear in the text completely unfounded and unsubstantiated - detailed criticism can be found, for example, in work. In addition, Courtois himself admits to widespread refusals to publish his work at major cryptography conferences and in established peer-reviewed journals, often leaving him only the opportunity to speak in the short announcement section. For example, you can read about this in section 3 of the work. Here are some quotes from Courtois himself relating to his work:

• “I think that the audiences of Asiacrypt will not feel it is interesting.” Asiacrypt 2011 reviewer.
• “… there is a big, big, big problem: this attack, which is the main contribution of the paper has already been published at FSE’11 (it was even the best paper), …”. Reviewer for Crypto 2011.

Thus, the professional part of the international cryptographic community regards the quality of Courtois’s work with no less doubt than, say, the statements of some Russian specialists about their ability to crack AES for 2,100, which are not confirmed by any consistent calculations, or the latest “evidence” of a two-page hypothesis on the inequality of complexity classes P and NP.

Attacks by Isobe and Dinur-Dankelman-Shamir

The general idea of ​​the Isobe () and Dinur-Dankelman-Shamir attacks (hereinafter: DDS attack) () is to construct for a certain (key-dependent) narrow set of plaintexts an equivalent transformation on this set, which has a structure simpler than the encryption transformation itself . In the case of the Isobe method, this is the set of 64-bit blocks x such that F 8 -1 (Swap(F 8 (z))) = z, where z = F 16 (x), through F 8 (x) and F 16 ( x) indicate the first 8 and first 16 rounds of GOST 28147-89 encryption, respectively, through Swap - the operation of swapping halves of a 64-byte word. If the plaintext is included in this set, the result of the full 32-round transformation of GOST 28147-89 coincides with the result of the 16-round one, which is what the author of the attack exploits. In the case of the DDS method, this is the set of x such that F 8 (x) = x (fixed point of the transformation F 8). For any plaintext from this set, the GOST 28147-89 transformation works exactly the same as its last 8 rounds, which simplifies the analysis.

The complexity of the Isobe attack is 2,224 encryption operations, the DDS attack is 2,192. However, all questions about whether the Isobe and DDS attacks introduce new restrictions on the conditions for using our algorithm are removed by assessing the requirements for the volume of material required to carry out each of the attacks: the Isobe method requires 2 32 pairs of plaintext and ciphertext, and for the DDS method - 2 64. Processing such volumes of material without changing the key is a priori unacceptable for any block cipher with a block length of 64: on material of volume 2 32 , taking into account the problem of birthdays (see, for example, ), the probability of occurrence of repeated blocks is close to 1/2, which will provide the attacker is able to draw certain conclusions about the plaintexts from the ciphertexts without determining the key. The presence of 2 64 pairs of plain and encrypted texts obtained on one key actually allows the enemy to carry out encryption and decryption operations without knowing this key at all. This is due to a purely combinatorial property: the enemy in this case has the entire encryption conversion table. This situation is absolutely unacceptable under any reasonable operating conditions. For example, in CryptoPro CSP There is a technical limitation on the volume of encrypted material (without key conversion) of 4 MB (see). Thus, a strict prohibition on using a key on material of such volume is inherent in any block cipher with a block length of 64 bits, and therefore, Isobe and DDS attacks in no way narrow the scope of use of the GOST 28147-89 algorithm while maintaining the maximum possible strength of 2,256.

Of course, it should be noted that researchers (Isobe and Dinur-Dankelman-Shamir) have shown that some properties of the GOST 28147-89 algorithm make it possible to find analysis paths that were not taken into account by the creators of the algorithm. The simple form of the key schedule, which significantly simplifies the task of constructing effective implementations, also allows for some rare cases of keys and plaintexts to construct more simple descriptions transformations performed by the algorithm.

The work demonstrates that this negative property of the algorithm can be easily eliminated with full preservation of operational characteristics, but, unfortunately, it is an integral part of the algorithm in its commonly used form.

Note that certain negligence in the estimates of average labor intensity is also present in the work of Dinur, Dunkelman and Shamir. Thus, when constructing an attack, due attention is not paid to the following point: for a significant proportion of keys, the set of plaintexts x, such that F 8 (x) = x, is empty: there may simply be no fixed points for 8 rounds of transformation. The existence of fixed points also depends on the choice of replacement nodes. Thus, the attack is only applicable for certain replacement nodes and keys.

It is also worth mentioning one more work with an attack on GOST 28147-89. In February 2012, the ePrint electronic archive of the international cryptographic association appeared updated version article (dated November 2011), which contained a new attack on GOST 28147-89. The characteristics of the presented attack are as follows: the volume of material is 2 32 (like Isobe), and the labor intensity is 2 192 (like DDS). Thus, this attack improved the time-record DDS attack in terms of material volume from 2 64 to 2 32. We note separately that the authors honestly presented all the calculations with justification for the complexity and volume of the material. After 9 months, a fundamental error was found in the above calculations, and since November 2012, the updated version of the article in the electronic archive no longer contains any results regarding the domestic algorithm.

Attacks assuming the attacker knows "something" about the keys

Finally, we note that in the literature there is also a number of works (see, for example, and ) devoted to attacks on GOST 28147-89 in the so-called linked key model. This model basically contains the assumption that an attacker can gain access for analysis not just to pairs of plaintext and encrypted using the desired key, but also to pairs of plaintext and ciphertext obtained using (also unknown) keys that differ from the sought one in a known regular way ( for example, at fixed bit positions). In this model, it is really possible to obtain interesting results about GOST 28147-89, however, in this model, no less strong results can be obtained about, for example, which is most widely used in modern networks common use AES standard (see, for example,). Note that the conditions for carrying out this type of attack arise when using a cipher in a certain protocol. It should be noted that results of this kind, although they are of undoubted academic interest from the point of view of studying the properties of cryptographic transformations, are actually not relevant to practice. For example, all cryptographic information protection tools certified by the FSB of Russia meet the strictest requirements for encryption key generation schemes (see, for example,). As indicated in the results of the analysis, if there are 18 associated keys and 2 10 pairs of plaintext and ciphertext blocks, the complexity of completely opening the private key, with a probability of success of 1-10 -4, is actually 2 26. However, if the above-mentioned requirements for the development of key material are met, the probability of finding such keys is 2 -4352, that is, 24096 times less than if you simply try to guess the secret key on the first try.

Works related to the model with linked keys also include work, which in 2010 caused a lot of noise in Russian electronic publications, which do not suffer from the habit of carefully checking the material in the race for sensations. The results presented in it were not supported by any rigorous justification, but they contained loud statements about the possibility of hacking the state standard Russian Federation on a weak laptop in a matter of seconds - in general, the article was written in the best traditions of Nicolas Courtois. But, despite the absolutely obvious groundlessness of the article to the reader who is more or less familiar with the basic principles of scientific publications, it was precisely to reassure the Russian public after the work that Rudsky wrote a detailed and thorough text containing a comprehensive analysis of this shortcoming. The article with the self-explanatory title “On the zero practical significance of the work “Key recovery attack on full GOST block cipher with zero time and memory”” provides justification that the average complexity of the method given in is no less than the complexity of a complete search.

Dry residue: what is durability in practice?

In conclusion, we present a table containing data on all the results of strictly described and justified attacks on GOST 28147-89 known to the international cryptographic community. Note that the complexity is given in the encryption operations of the GOST 28147-89 algorithm, and the memory and material are indicated in algorithm blocks (64 bits = 8 bytes).

Attack	Labor intensity	Memory	Required material
Isobe	2 224	2 64	2 32
Dinur-Dankelman-Shamir, FP, 2DMitM	2 192	2 36	2 64
Dinur-Dankelman-Shamir, FP, low-memory	2 204	2 19	2 64
	2 224	2 36	2 32
Dinur-Dankelman-Shamir, Reflection, 2DMitM	2 236	2 19	2 32
Complete search	2 256	1	4
Number of nanoseconds since the creation of the Universe	2 89

Despite a fairly large-scale cycle of research in the field of stability of the GOST 28147-89 algorithm, this moment There is not a single attack known that would be achievable under the operational requirements of a 64-bit block length. The restrictions on the volume of material that can be processed on one key resulting from the cipher parameters (key bit length, block bit length) are significantly stricter than the minimum volume required to carry out any currently known attack. Consequently, when meeting existing operational requirements, none of the cryptanalysis methods proposed to date GOST 28147-89 allows determining a key with a labor intensity less than exhaustive search.