Encryption algorithm GOST 28147-89. Simple replacement method. - Archive WASM.RU

“While you are alive, do not die, take a look at this world.
Many here have a dead soul - they are dead inside.
But they walk and laugh, not knowing that they are not,
Don't rush your hour of death, ”she told me.

Aria, "High Up There"

2.1 Feistel networks.
2.2 Block cipher GOST 28147-89

3.1 Key information
3.2 The main step of the crypto transformation

3.3 Basic cycles:“ 32-Z” , “ 32-R” .

4.1 Implementation of the main step of the crypto transformation
4.2 Increasing the speed of the algorithm
5. Key information requirements
6. List of used literature
7. Acknowledgments.

Introduction.

This document is my attempt to describe a method of simply replacing the GOST 28147-89 encryption algorithm with the simplest, but, nevertheless, technically competent language. After reading the first six points, the reader will tell his opinion about how well I did it.

In order for my work to give more benefit, I recommend that you arm yourself with the works of the authors indicated in the list of used literature. It is also recommended that a calculator has a function for calculating the operation. XOR since reading the article assumes that the reader intended to study this encryption algorithm. Although it is also suitable as a reference, but I wrote this article precisely as a training one.

Preliminary information about block ciphers.

Before we start looking at the algorithm, we need to familiarize ourselves with the history of the creation of this kind of ciphers. The algorithm belongs to the category of block ciphers, in the architecture of which information is divided into a finite number of blocks, the final one naturally may not be complete. The encryption process takes place over complete blocks, which form the cipher. The final block, if it is incomplete, is supplemented with something (I will say about the nuances of completing it below) and is encrypted in the same way as full blocks. By a cipher, I mean the result of the encryption function acting on a certain amount of data that the user submitted for encryption. In other words, a cipher is the end result of encryption.

The history of the development of block ciphers is associated with the beginning of the 70s, when IBM, realizing the need to protect information when transmitting data through computer communication channels, embarked on its own research program devoted to the protection of information in electronic networks, including cryptography.

A group of researchers - developers from IBM, which began researching encryption systems with a symmetric key usage scheme, was headed by Dr. Horst Feistel.

2.1 Feistel networks

The architecture of the new encryption method proposed by Feistel in the classical literature is called "The Feistel Architecture", but at the moment in Russian and foreign literature a more established term is used - "Feistel's network" or Feistel`s NetWork. Subsequently, the cipher "Lucifer" was built on this architecture - which was later published and caused a new wave of interest in cryptography in general.

The idea of ​​the "Feistel network" architecture is as follows: the input stream of information is divided into blocks of n bits in size, where n is an even number. Each block is divided into two parts - L and R, then these parts are fed into an iterative block cipher, in which the result of the j-th stage is determined by the result of the previous stage j-1! This can be illustrated by an example:

Rice. 1

Where, function A is the main action of the block cipher. It can be a simple action, such as an XOR operation, or it can have a more complex form as a sequence of a series of simple actions - modulo addition, left shift, element replacement, etc., taken together, these simple actions form the so-called - the main step of the crypto transformation.

It should be noted that the key elements of the function's operation are the supply of key elements and the XOR operation, and from how well thought out the work of these operations, it speaks of the cryptographic strength of the cipher as a whole.

In order for the idea of ​​Feistel networks to be finally clear, consider the simplest case shown in rice. 1, where in function A - there will be operations “mod 2” (“xor”), but this simplest a case, in a more serious situation, for example, hiding information of national importance, function A may be more complex (as far as I have seen, function A is really very complex):

Initial data:

L = 1110b, R = 0101, K = 1111b

Get a cipher

1. (R + K) mod 2 4 = Smod, Smod = 0100b

2. (Smod + L) mod 2 = Sxor, Sxor = 1010b

3. L = R, R = Sxor

L = 0101b, R = 1010b

Let's explain our actions:

1. This operation is addition mod 2 4. In practice, such an operation is reduced to simple addition, where we must add two numbers and ignore the transfer to the 5th digit. Since, if we put down exponents above the digits of the binary representation of a number, there will be an exponent four above the fifth digit, let's take a look at the figure below, which shows the actions of our operation:

Rice. 2

Here I pointed to the exponents with an arrow, as you can see, the result should have been 10100, but since the transfer is ignored during the mod 2 4 operation, we get 0100.

2. This operation in the literature is called mod 2, in assembly language it is implemented by the command XOR... But its more correct name is mod 2 1. Without this unique operation, it is hardly possible to build a fast, easily implementable encryption algorithm, and at the same time, so that it is still quite cryptographically strong. The uniqueness of this operation lies in the fact that it is itself the opposite! For example, if the number A is XORed with the number B, as a result we will get B, in the future it is enough to reXOR the numbers B and C between each other to get the previous value of A!

In this operation, we got 1010 having the numbers 1110 and 0100, to get back 1110, it is enough to overXOR the numbers 0100 and 1010! More details about this operation can be found in the article, which is attached to the site. www.wasm.ru, « An elementary guide toCRC_ error detection algorithms»The author who Ross N. Williams... There is a point in this work - “ 5. Binary arithmetic without hyphenation". It is in this article that the operation is described. xor! I exclaim because in this article this operation is so scheduled that the reader not only understands how this operation works, he even starts it see, hear and feel!

3. This action is necessary so that the initial values ​​can be obtained from the encryption during decryption.

2.2 Block cipher GOST 28147-89

The encryption algorithm GOST 28147 - 89 belongs to the category of block ciphers operating according to the architecture of balanced Feistel networks, where two parts of the selected block of information are of equal size. The algorithm was developed in the depths of the eighth department of the KGB, now transformed into FAPSI and was enshrined as the encryption standard of the Russian Federation back in 1989 under the USSR.

For this method of the algorithm to work, it is necessary to split the information into blocks of 64 bits in size. Generate or enter into the encryption system the following key information: key and substitution table. The choice of the key and substitution table for encryption should be taken very seriously, because this is the foundation of the security of your information. For information on what requirements are imposed on the key, and the table of substitutions, see the item "Requirements for key information".

When considering the method, we will not focus on this, because this article, as I said above, was written with the aim of teaching the reader how to encrypt data by the method of simple replacement of this encryption algorithm, but we will definitely touch on this issue at the end of the article.

Theoretical minimum.

3.1 Key information

As I said above, the following are actively involved in data encryption:

3.1.1. A key is a sequence of eight elements, 32 bits each. In what follows, we will denote by the symbol K, and the elements of which it consists are k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Substitution table - a matrix of eight rows and sixteen columns, hereinafter - Hij. Each element at the intersection of row i and column j occupies 4 bits.

3.2 Basic step of crypto transformation

The main step in the encryption process is - the main step of the crypto transformation. This is nothing more than an action to encrypt data according to a certain algorithm, only the developers have introduced the name too cumbersome.

Before starting to encrypt, the block is split into two parts L and R, 32 bits each. The key element is selected and only then these two parts of the block, the key element, the substitution table, are fed into the function of the main step, the result of the main step is one iteration of the base cycle, which will be discussed in the next paragraph. The main step consists of the following:

1. Addition part of the block R is summed with the key element K mod 2 32. I described a similar operation above, here the same thing only the exponent is not "4", but "32" - the result of this operation will be denoted Smod in the future.
2. Divide the previously obtained result Smod into four-bit elements s7, s6, s5, s4, s3, s2, s1, s0 and feed it to the replacement function. The replacement is as follows: the element Smod - s i is selected, from the beginning we start with the lowest element, and we replace with the value from the table of replacements by i - the row and column pointed to by the value of the element s i. We pass to the s i +1 element and proceed in the same way and continue so until we change the value of the last element Smod - the result of this operation will be denoted as, Ssimple.
3. In this operation, we shift the Ssimple value cyclically to the left by 11 bits and get Srol.
4. We select the second part of the L block and add it mod 2 with Srol, as a result we have Sxor.
5. At this stage, the part of the block L becomes equal to the value of the part R, and the part R, in turn, is initialized with the result Sxor, and at this the function of the main step is completed!

3.3 Basic cycles: "32-З", "32-Р".

In order to encrypt information, it is necessary to split it into blocks of 64 bits in size, of course the last block can be less than 64 bits. This fact is the Achilles' heel of this "easy replacement" method. Since its addition to 64 bits is a very important task to increase the cryptographic strength of the cipher program and to this sensitive place, if it is present in the information array, but it may not exist (for example, a file of 512 bytes!), One should treat with a large responsibility!

After you have split the information into blocks, you should split the key into elements:

K = k1, k2, k3, k4, k5, k6, k7, k8

The encryption itself consists in the use of so-called basic cycles. Which, in turn, include the n-th number of basic steps of crypto-transformation.

Basic cycles are labeled, how to put it: n - m. Where n is the number of basic steps of the crypto transformation in the base cycle, and m is the "type" of the base cycle, i.e. what is it about, about "Z" encryption or "R" encryption of data.

Basic encryption cycle 32-З consists of 32 basic steps of crypto-transformation. A block N and an element of the key K are fed into the function that implements the actions of the step, and the first step occurs with k1, the second over the result obtained with the element k2, etc. according to the following scheme:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

The decryption process for 32-P occurs in a similar way, but the key elements are given in the reverse order:

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Practice.

4.1 Implementation of the main step of the crypto transformation

After we got acquainted with the theory of how to encrypt information, it was time to see how encryption works in practice.

Initial data:

Take a block of information N = 0102030405060708h, here the parts L and R are equal:

L = 01020304h, R = 05060708h, let's take the key:

K = ‘ as28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(these are ASCII - codes, in order to view the hexadecimal representation, you can open this file in view mode in Total Commander by pressing the key F3"And then the key" 3 "). In this key, the values ​​of the elements will be:

k1 = ‘as28’, k2 = ‘zw37’, k3 = ‘q839’, k4 = ‘7342’

k5 = ‘ui23’, k6 = ‘8e2t’, k7 = ‘wqm2’, k8 = ‘ewp1’

Also take the following substitution table:

Rice. 3

Here, rows are numbered from 0 to 7, columns from 0 to F.

A warning: All information, including the key with the substitution table, is taken as an example for considering the algorithm!

Using the "Initial data", it is necessary to obtain the result of the action of the main step of the crypto transformation.

1. Select the part R = 05060708h and the key element k1 = 'as28', in hexadecimal form the key element will look like this: 61733238h. Now we do the summation operation mod 2 32:

Rice. 4

As you can see in the figure, we did not have a transfer in 33 bits marked in red and with the exponent “ 32 ". And if we had other values ​​of R and the key element, this could well have happened, and then we would have ignored it, and further used only the bits marked in yellow.

I perform this operation with the assembler command add:

; eax = R, ebx = 'as28'

The result of this operation Smod = 66793940h

2. Now the most intricate operation, but if you look closely, it is no longer as terrible as it seems at first. Let's imagine Smod as follows:

Rice. 5

I tried to visualize the Smod elements in the figure, but I will explain anyway:

s0 = 0, s1 = 4, s2 = 9, etc.

Now, starting from the lowest element s0, we make the replacement. Remembering the paragraph “ 3.2 Basic step of crypto transformation»I - row, s i - column, look for the value in the zero row and zero column:

Fig. 6

So the current value of Smod is not 6679394 0 h, and 6679394 5 h.

We proceed to replace s1, i.e. four. Using the first row and fourth column (s1 = 4!). We look at the picture:

Rice. 7

Now already the value of Smod, not 667939 4 5h, 667939 2 5h. I assume that now the replacement algorithm is clear to the reader, and I can say that after the final result of Ssimple will have the following value - 11e10325h.

I will talk about how this is easiest to implement in the form of assembler commands later in the next paragraph, after I talk about the extended table.

1. We must shift the resulting Ssimple value 11 bits to the left.

Rice. eight

As you can see, this action is quite simple, and is implemented by one command of the assembly language - rol and the result of this Srol operation is 0819288Fh.

4. Now part L of our block of information is to be XORed with the Srol value. I take a calculator from w2k sp4 and get Sxor = 091b2b8bh.

5. This action is final and we simply assign, clean R, the value of the L part, and initialize the L part with the Sxor value.

Final result:

L = 091b2b8bh, R = 01020304h

4.2 Increasing the speed of the algorithm

Now let's talk about optimizing the algorithm for speed. In the process of implementing a project, one has to take into account that a program that works with registers more often than with memory works most quickly, and here this judgment is also very important, since over one block of information as many as 32 encryption actions!

When I implemented the encryption algorithm in my program, I did the following:

1. Selected part of the block L to the eax register, and R to edx.

2. In the esi register, initialized with the address of the extended key, more on that below.

3. In register ebx assigned the value of the address of the extended table of substitutions, more on this below

4. Transferred the information of items 1, 2, 3 to the function of the basic cycle 32 - З or 32 - Р, depending on the situation.

If you look at the flow diagram of the key elements in the paragraph " Basic cycles: "32-З", "32-Р"", Then our key for the base cycle 32 - 3 can be represented as follows:

K 32-Z =

‘As28’, ‘zw37’, ‘q839’, ‘7342’, ‘ui23’, ‘8e2t’, ‘wqm2’, ‘ewp1’,

‘As28’, ‘zw37’, ‘q839’, ‘7342’, ‘ui23’, ‘8e2t’, ‘wqm2’, ‘ewp1’,

‘Ewp1’, ‘wqm2’, ‘8e2t’, ‘ui23’, ‘7342’, ‘q839’, ‘zw37’, ‘as28’

Those. from the beginning there are k1, k2, k3, k4, k5, k6, k7, k8 - ‘ as28 ’,‘zw37 ’,’q839 ',' 7342 ','ui23 ',' 8e2t ’,‘wqm2 ’,’ewp1 ' this sequence is repeated three times. Then the elements go in reverse order, i.e .: k8, k7, k6, k5, k4, k3, k2, k1 - ‘Ewp1’, ‘wqm2’, ‘8e2t’, ‘ui23’, ‘7342’, ‘q839’, ‘zw37’, ‘as28’.

I arranged the elements in the array in advance in the order they should be fed in 32 - Z. Thus, I increased the memory required on a turnkey basis, but saved myself from some thinking processes that I did not need, and increased the speed of the algorithm, for by reducing the memory access time! Here I described only the key for 32 - З, for cycle 32 - Р I did the same, but using a different scheme of supplying elements, which I also described in the paragraph " Basic cycles: “32-Z”, “32-P».

Now is the time to describe the implementation of the replacement function, as I promised above. I could not describe earlier, because this requires the introduction of a new concept - an extended substitution table. I cannot explain to you what it is. Instead, I'll show you it, and you yourself formulate for yourself, what is it - an extended table of substitutions?

So, in order to understand what an extended substitution table is, we need a substitution table, for example, I'll take the one shown in Fig. 3.

For example, we needed to replace the number 66793940h. I will present it as follows:

Rice. nine

Now if we take the elements s1, s0, i.e. least significant byte, the result of the replacement function will be 25h! After reading the article by Andrey Vinokurov, which I cited in the paragraph " List of used literature", You actually find that if you take two lines you can get an array, allowing you to quickly find the replacement elements using the assembler command xlat. They say it can be done in another way faster, but Andrey Vinokurov spent about four years researching fast algorithms for the implementation of GOST! I don't think you should reinvent the wheel when you already have one.

So, about the array:

Let's take the first two lines zero and the first, create an array of 256 bytes. Now we observe one peculiarity that if it is necessary to transform 00h, then the result will be 75h (based on Fig. 3) - we put this value into the array at offset 00h. We take the value 01h, the result of the substitution function 79h, put it into the array at offset 01, and so on up to 0FFh, which will give us 0FCh, which we will put into the array at offset 0FFh. So we got an extended substitution table for the first group of rows: the first and zero. But there are still three groups: second page 2, page 3, third page 4, page 5, fourth page 6, page 7. We deal with these three groups in the same way as with the first. The result is an extended substitution table!

Now we can implement an algorithm that will perform the replacement. To do this, we take the source codes that Andrei Vinokurov posted on his page, see " Bibliography».

lea ebx, extented_table_simple

mov eax, [put the number to be replaced]

add ebx, 100h; jump to next two nodes

sub ebx, 300h; so that in the future ebx points to the table

Now one more feature, with the previous actions we not only replaced, but also shifted the number by 8 bits to the left! We just have to shift the number another 3 bits to the left:

and we get the result of the operation rol eax, 11!

I can't add anything more on optimization, the only thing I can emphasize is what I said above - use registers more often than memory access. I think these words are only for beginners, experienced and without my words understand it perfectly.

Requirements for key information.

As stated in the article by Andrey Vinokurov, the key is selected according to two criteria:

The criterion for the equiprobable distribution of bits between the values ​​1 and 0. Usually, the criterion for the equiprobable distribution of bits is the Pearson criterion ("chi-square").

This means a key, in principle, any number can. That is, when the next bit of the key is formed, the probability of its initialization by one or zero is 50/50!

Please note that the key consists of eight elements, each of 32 bits, so there are only 32 * 8 = 256 bits in the key and the number of possible keys is 2 256! Doesn't that strike you?

Series criterion.

If we look at our key, which I gave in the paragraph " 4.1 Implementation of the main step of the crypto transformation», Then you will notice that the following notation is valid:

Rice. ten

In one phrase, the value of k 1 should not be repeated not in k 2, not in any other element of the key.

That is, the key that we have chosen as the consideration of the encryption algorithm is consistent with the two above criteria.

Now about the choice of the table of substitutions:

Now let's talk about how to choose the right substitution table. The main requirement for the selection of replacement tables is the phenomenon of “non-repeatability” of elements, each of which is 4 bits in size. As you saw above, each row of the substitution table consists of the values ​​0h, 1h, 2h, 3h,…, 0fh. So the main requirement is that each line contains the values ​​0h, 1h, 2h, ..., 0fh and each such value in one copy. For example, the sequence:

1 2 3 4 5 6 7 8 9 A B C D E F

It fully complies with this requirement, but still! It is not recommended to select this sequence as a string. Since if you feed a value to the input of a function that relies on such a string, then you will get the same value at the output! Don't believe me? Then take the number 332DA43Fh and eight such lines as a substitution table. Perform the replacement operation, and I assure you, the output will be the number 332DA43Fh! That is, the same that you submitted to the input of the operation! And this is not a sign of good form in encryption, and was it?

This was one requirement, the next criterion says that - every bit of the output block must be statistically independent of every bit of the input block!

How does it look simpler? And here is how, for example, we have chosen from the above number the element s0 = 0Fh, 01111b. The probability that we will now replace the first bit with one or zero is 0.5! The probability of replacing the second, third and fourth bits, each bit, we consider separately, with ones or zeros is also 0, 5. When choosing s1 = 0Eh, the probability that we are a zero bit, and this is "0", will be replaced by a zero or one too equals - 0.5! Thus, according to this criterion, there is no regularity between the replacement of zero bits of elements s0, s1! Yes, you could substitute ones, but you could also substitute zeros.

To evaluate the table by this criterion, you can build a table of correlation coefficients calculated by the formula:

If p = 1, then the value of bit j at the output is equal to the value of bit i at the input for any combinations of bits at the input;

If p = -1, then the value of bit j at the output is always the inverse of the input bit i;

If p = 0, then the output bit j with equal probability takes the values ​​0 and 1 for any fixed value of the input bit i.

Let's take one line example:

Let's break it down into "components":

Let's calculate one coefficient according to the above formula. To make it easier to understand how this is done, I will explain in more detail:

We take the 0th bit of the 0th number (0) at the input and the 0th bit of the 0th number at the output (1) we perform the operation 0 XOR 1 = 1.

We take the 0th bit of the 1st number (1) at the input and the 0th bit of the 1st number at the output (1) we carry out the operation 1 XOR 1 = 0.

We take the 0th bit of the 2nd number (0) at the input and the 0th bit of the 2nd number at the output (0), we perform the operation 0 XOR 0 = 0.

We take the 0th bit of the 3rd number (1) at the input and the 0th bit of the 3rd number at the output (1) we carry out the operation 1 XOR 1 = 0.

Conducting successively XOR operations in this sequence, we count the number of all non-zero values, we get the value 6. Hence P 00 = 1- (6/2 4-1) = 0.25. So, it turned out that the value of bit 0 at the output is equal to the value of bit 0 at the input in 4 cases out of 16;

Final odds table:

As can be seen from the table of correlation coefficients, bit 3 at the input is inverted relative to bit 0 at the output in 14 cases out of 16, which is 87.5%. This is no longer acceptable for normal encryption systems. Let's take another example for a change:

The table of coefficients will be as follows (to whom it is not lazy to recalculate)

Well, in this table, things are even worse - bits 1 and 2 of the group remain unchanged! Cryptanalyst has where to turn around Taking into account all these requirements, a simple search ("head-on") was found permutation tables corresponding to the indicated theory (today - 1276 combinations) Here are some of them:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

List of used literature.

1. Article by Andrey Vinokurov:

Encryption algorithm GOST 28147-89, its use and implementation

for computers of the Intel x86 platform.

There are also the source codes for the implementation of the encryption algorithm.

1. Horst Feistel's article:

Cryptography and Computer Security.

(can be found at the same address as the previous article)

1. Ross N. Williams:

An Elementary Guide to CRC Error Detection Algorithms

Posted on the site www.wasm.ru.

Acknowledgments.

I would like to express my gratitude to all visitors of the www.wasm.ru forum. But I would especially like to thank ChS, who is currently known as SteelRat, he helped me understand things that I probably would never have understood, as well as help in writing the paragraph: “ Key information requirements”, The main part of this paragraph was written by him. I am also deeply grateful to the employee of the KSTU named after A.N. Tupolev Anikin Igor Vyacheslavovich and it would be a sin not to mention Chris Kaspersky for the fact that he is and Volodya / wasm.ru for his instructions. Oh, and I get it from him. I also want to note Sega-Zero / Callipso, but that brought some mathematical jungle to my mind.

This is, perhaps, all that I would like to tell you.

I would be grateful for any criticism or questions related to this article or just advice. My contact details: [email protected], ICQ - 337310594.

Best regards, Evil`s Interrupt.

P.S.: With this article, I did not try to outdo anyone. It was written with intention, to facilitate the study of GOST, and if you have difficulties, this does not mean that I am guilty of this. Be reasonable and have patience, all the best to you!

“While you are alive, do not die, take a look at this world.
Many here have a dead soul - they are dead inside.
But they walk and laugh, not knowing that they are not,
Don't rush your hour of death, ”she told me.

Aria, "High Up There"

1. Introduction

1. Preliminary information about block ciphers

2.1 Feistel networks.
2.2 Block cipher GOST 28147-89

1. Theoretical minimum

3.1 Key information
3.2 The main step of the crypto transformation

3.3 Basic cycles:“ 32-Z” , “ 32-R” .

1. Practice

4.1 Implementation of the main step of the crypto transformation
4.2 Increasing the speed of the algorithm
5.
6. List of used literature
7. Acknowledgments.

Introduction.

This document is my attempt to describe a method of simply replacing the GOST 28147-89 encryption algorithm with the simplest, but, nevertheless, technically competent language. After reading the first six points, the reader will tell his opinion about how well I did it.

In order for my work to give more benefit, I recommend that you arm yourself with the works of the authors indicated in the list of used literature. It is also recommended that a calculator has a function for calculating the operation. XOR since reading the article assumes that the reader intended to study this encryption algorithm. Although it is also suitable as a reference, but I wrote this article precisely as a training one.

Preliminary information about block ciphers.

Before we start looking at the algorithm, we need to familiarize ourselves with the history of the creation of this kind of ciphers. The algorithm belongs to the category of block ciphers, in the architecture of which information is divided into a finite number of blocks, the final one naturally may not be complete. The encryption process takes place over complete blocks, which form the cipher. The final block, if it is incomplete, is supplemented with something (I will say about the nuances of completing it below) and is encrypted in the same way as full blocks. By a cipher, I mean the result of the encryption function acting on a certain amount of data that the user submitted for encryption. In other words, a cipher is the end result of encryption.

The history of the development of block ciphers is associated with the beginning of the 70s, when IBM, realizing the need to protect information when transmitting data through computer communication channels, embarked on its own research program devoted to the protection of information in electronic networks, including cryptography.

A group of researchers - developers from IBM, which began researching encryption systems with a symmetric key usage scheme, was headed by Dr. Horst Feistel.

2.1 Feistel networks

The architecture of the new encryption method proposed by Feistel in the classical literature was called “The Feistel Architecture”, but at the moment in Russian and foreign literature a more established term is used - “Feistel's network” or Feistel`s NetWork. Subsequently, the cipher "Lucifer" was built on this architecture - which was later published and caused a new wave of interest in cryptography in general.

The idea of ​​the "Feistel network" architecture is as follows: the input stream of information is divided into blocks of n bits in size, where n is an even number. Each block is divided into two parts - L and R, then these parts are fed into an iterative block cipher, in which the result of the j-th stage is determined by the result of the previous stage j-1! This can be illustrated by an example:

Rice. 1

Where, function A is the main action of the block cipher. It can be a simple action, such as an XOR operation, or it can have a more complex form as a sequence of a series of simple actions - modulo addition, left shift, element replacement, etc., taken together, these simple actions form the so-called - the main step of the crypto transformation.

It should be noted that the key elements of the function's operation are the supply of key elements and the XOR operation, and from how well thought out the work of these operations, it speaks of the cryptographic strength of the cipher as a whole.

In order for the idea of ​​Feistel networks to be finally clear, consider the simplest case shown in rice. 1, where in function A - there will be operations “mod 2” (“xor”), but this simplest a case, in a more serious situation, for example, hiding information of national importance, function A may be more complex (as far as I have seen, function A is really very complex):

Initial data:

L = 1110b, R = 0101, K = 1111b

Get a cipher

1. (R + K) mod 2 4 = Smod, Smod = 0100b
2. (Smod + L) mod 2 = Sxor, Sxor = 1010b
3. L = R, R = Sxor

L = 0101b, R = 1010b

Let's explain our actions:

1. This operation is mod 2 4 addition. In practice, such an operation is reduced to simple addition, where we must add two numbers and ignore the transfer to the 5th digit. Since, if we put down exponents above the digits of the binary representation of a number, there will be an exponent four above the fifth digit, let's take a look at the figure below, which shows the actions of our operation:

Rice. 2

Here I pointed to the exponents with an arrow, as you can see, the result should have been 10100, but since the transfer is ignored during the mod 2 4 operation, we get 0100.

1. This operation in the literature is called mod 2, in assembly language it is implemented by the command XOR... But its more correct name is mod 2 1. Without this unique operation, it is hardly possible to build a fast, easily implementable encryption algorithm, and at the same time, so that it is still quite cryptographically strong. The uniqueness of this operation lies in the fact that it is itself the opposite! For example, if the number A is XORed with the number B, as a result we will get B, in the future it is enough to reXOR the numbers B and C between each other to get the previous value of A!

In this operation, we got 1010 having the numbers 1110 and 0100, to get back 1110, it is enough to overXOR the numbers 0100 and 1010! More details about this operation can be found in the article, which is attached to the site. www.wasm.ru, « An elementary guide toCRC_ error detection algorithms»The author who Ross N. Williams... There is a point in this work - “ 5. Binary arithmetic without hyphenation". It is in this article that the operation is described. xor! I exclaim because in this article this operation is so scheduled that the reader not only understands how this operation works, he even starts it see, hear and feel!

1. This action is necessary so that during decryption, the initial values ​​can be obtained from the cipher.

2.2 Block cipher GOST 28147-89

The encryption algorithm GOST 28147 - 89 belongs to the category of block ciphers operating according to the architecture of balanced Feistel networks, where two parts of the selected block of information are of equal size. The algorithm was developed in the depths of the eighth department of the KGB, now transformed into FAPSI and was enshrined as the encryption standard of the Russian Federation back in 1989 under the USSR.

For this method of the algorithm to work, it is necessary to split the information into blocks of 64 bits in size. Generate or enter into the encryption system the following key information: key and substitution table. The choice of the key and substitution table for encryption should be taken very seriously, because this is the foundation of the security of your information. For information on what requirements are imposed on the key, and the table of substitutions, see the item "Requirements for key information".

When considering the method, we will not focus on this, because this article, as I said above, was written with the aim of teaching the reader how to encrypt data by the method of simple replacement of this encryption algorithm, but we will definitely touch on this issue at the end of the article.

Theoretical minimum.

3.1 Key information

As I said above, the following are actively involved in data encryption:

3.1.1. A key is a sequence of eight elements, 32 bits each. In what follows, we will denote by the symbol K, and the elements of which it consists are k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Substitution table - a matrix of eight rows and sixteen columns, hereinafter - Hij. Each element at the intersection of row i and column j occupies 4 bits.

The main step in the encryption process is - the main step of the crypto transformation. This is nothing more than an action to encrypt data according to a certain algorithm, only the developers have introduced the name too cumbersome :).

Before starting to encrypt, the block is split into two parts L and R, 32 bits each. The key element is selected and only then these two parts of the block, the key element, the substitution table, are fed into the function of the main step, the result of the main step is one iteration of the base cycle, which will be discussed in the next paragraph. The main step consists of the following:

1. Addition part of the block R is summed with the key element K mod 2 32. I described a similar operation above, here the same thing only the exponent is not "4", but "32" - the result of this operation will be denoted Smod in the future.
2. Divide the previously obtained result Smod into four-bit elements s7, s6, s5, s4, s3, s2, s1, s0 and feed it to the replacement function. The replacement is as follows: the element Smod - s i is selected, we start from the beginning with the lowest element, and replace with the value from the table of replacements by i - the row and column pointed to by the value of the element s i. We pass to the s i +1 element and proceed in the same way and continue so until we change the value of the last element Smod - the result of this operation will be denoted as, Ssimple.
3. In this operation, we shift the Ssimple value cyclically to the left by 11 bits and get Srol.
4. We select the second part of the L block and add it mod 2 with Srol, as a result we have Sxor.
5. At this stage, the part of the block L becomes equal to the value of the part R, and the part R, in turn, is initialized with the result of Sxor, and at this the function of the main step is completed!

3.3 Basic cycles: "32-З", "32-Р".

In order to encrypt information, it is necessary to split it into blocks of 64 bits in size, of course the last block can be less than 64 bits. This fact is the Achilles' heel of this "easy replacement" method. Since its addition to 64 bits is a very important task to increase the cryptographic strength of the cipher program and to this sensitive place, if it is present in the information array, but it may not exist (for example, a file of 512 bytes!), One should treat with a large responsibility!

After you have split the information into blocks, you should split the key into elements:

K = k1, k2, k3, k4, k5, k6, k7, k8

The encryption itself consists in the use of so-called basic cycles. Which, in turn, include the n-th number of basic steps of crypto-transformation.

Basic cycles are labeled, how to put it: n - m. Where n is the number of basic steps of the crypto transformation in the base cycle, and m is the "type" of the base cycle, i.e. what is it about, about "Z" encryption or "R" encryption of data.

Basic encryption cycle 32-З consists of 32 basic steps of crypto-transformation. A block N and an element of the key K are fed into the function that implements the actions of the step, and the first step occurs with k1, the second over the result obtained with the element k2, etc. according to the following scheme:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

The decryption process for 32-P occurs in a similar way, but the key elements are given in the reverse order:

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Practice.

After we got acquainted with the theory of how to encrypt information, it was time to see how encryption works in practice.

Initial data:

Take a block of information N = 0102030405060708h, here the parts L and R are equal:

L = 01020304h, R = 05060708h, let's take the key:

K = ‘ as28 zw37 q839 7342ui23 8e2t wqm2 ewp1 '(these are ASCII - codes, in order to view the hexadecimal representation, you can open this file in view mode in Total Commander by pressing the key F3"And then the key" 3 "). In this key, the values ​​of the elements will be:

k1 = ‘as28’, k2 = ‘zw37’, k3 = ‘q839’, k4 = ‘7342’

k5 = ‘ui23’, k6 = ‘8e2t’, k7 = ‘wqm2’, k8 = ‘ewp1’

Also take the following substitution table:

Rice. 3

Here, rows are numbered from 0 to 7, columns from 0 to F.

A warning: All information, including the key with the substitution table, is taken as an example for considering the algorithm!

Using the "Initial data", it is necessary to obtain the result of the action of the main step of the crypto transformation.

1. We select the part R = 05060708h and the key element k1 = ‘as28’, in hexadecimal form the key element will look like this: 61733238h. Now we do the summation operation mod 2 32:

Rice. 4

As you can see in the figure, we did not have a transfer in 33 bits marked in red and with the exponent “ 32 ". And if we had other values ​​of R and the key element, this could well have happened, and then we would have ignored it, and further used only the bits marked in yellow.

I perform this operation with the assembler command add:

; eax = R, ebx = 'as28'

The result of this operation Smod = 66793940h

1. Now the most intricate operation, but if you look closely, it is no longer as terrible as it seems at first. Let's imagine Smod as follows:

FIGURE NOT SAVED

Rice. 5

I tried to visualize the Smod elements in the figure, but I will explain anyway:

s0 = 0, s1 = 4, s2 = 9, etc.

Now, starting from the lowest element s0, we make the replacement. Remembering the paragraph “ 3.2 Basic step of crypto transformation»I - row, s i - column, look for the value in the zero row and zero column:

Fig. 6

So the current value of Smod is not 6679394 0 h, and 6679394 5 h.

We proceed to replace s1, i.e. four. Using the first row and fourth column (s1 = 4!). We look at the picture:

Rice. 7

Now already the value of Smod, not 667939 4 5h, 667939 2 5h. I assume that now the replacement algorithm is clear to the reader, and I can say that after the final result of Ssimple will have the following value - 11e10325h.

I will talk about how this is easiest to implement in the form of assembler commands later in the next paragraph, after I talk about the extended table.

1. We must shift the resulting Ssimple value 11 bits to the left.

Rice. eight

As you can see, this action is quite simple, and is implemented by one command of the assembly language - rol and the result of this Srol operation is 0819288Fh.

1. Now it remains the L part of our block of information to be XORed with the Srol value. I take a calculator from w2k sp4 and get Sxor = 091b2b8bh.
2. This action is final and we simply assign, clean R, the value of the L part, and initialize the L part with the Sxor value.

Final result:

L = 091b2b8bh, R = 01020304h

4.2 Increasing the speed of the algorithm

Now let's talk about optimizing the algorithm for speed. In the process of implementing a project, one has to take into account that a program that works with registers more often than with memory works most quickly, and here this judgment is also very important, since over one block of information as many as 32 encryption actions!

When I implemented the encryption algorithm in my program, I did the following:

1. Selected part of the block L to the eax register, and R to edx.
2. In the esi register, initialized with the address of the extended key, more on that below.
3. In register ebx assigned the value of the address of the extended table of substitutions, more on this below
4. Transferred the information of items 1, 2, 3 to the function of the basic cycle 32 - З or 32 - Р, depending on the situation.

If you look at the flow diagram of the key elements in the paragraph " Basic cycles: "32-З", "32-Р"", Then our key for the base cycle 32 - 3 can be represented as follows:

K 32-Z =

‘As28’, ‘zw37’, ‘q839’, ‘7342’, ‘ui23’, ‘8e2t’, ‘wqm2’, ‘ewp1’,

‘As28’, ‘zw37’, ‘q839’, ‘7342’, ‘ui23’, ‘8e2t’, ‘wqm2’, ‘ewp1’,

‘Ewp1’, ‘wqm2’, ‘8e2t’, ‘ui23’, ‘7342’, ‘q839’, ‘zw37’, ‘as28’

Those. from the beginning there are k1, k2, k3, k4, k5, k6, k7, k8 - ‘ as28 ’,‘zw37 ’,’q839 ',' 7342 ','ui23 ',' 8e2t ’,‘wqm2 ’,’ewp1 ' this sequence is repeated three times. Then the elements go in reverse order, i.e .: k8, k7, k6, k5, k4, k3, k2, k1 - ‘Ewp1’, ‘wqm2’, ‘8e2t’, ‘ui23’, ‘7342’, ‘q839’, ‘zw37’, ‘as28’.

I arranged the elements in the array in advance in the order they should be fed in 32 - Z. Thus, I increased the memory required on a turnkey basis, but saved myself from some thinking processes that I did not need, and increased the speed of the algorithm, for by reducing the memory access time! Here I described only the key for 32 - З, for cycle 32 - Р I did the same, but using a different scheme of supplying elements, which I also described in the paragraph " Basic cycles: “32-Z”, “32-P».

Now is the time to describe the implementation of the replacement function, as I promised above. I could not describe earlier, because this requires the introduction of a new concept - an extended substitution table. I cannot explain to you what it is. Instead, I'll show you it, and you yourself formulate for yourself, what is it - an extended table of substitutions?

So, in order to understand what an extended substitution table is, we need a substitution table, for example, I'll take the one shown in Fig. 3.

For example, we needed to replace the number 66793940h. I will present it as follows:

FIGURE NOT SAVED

Rice. nine

Now if we take the elements s1, s0, i.e. least significant byte, the result of the replacement function will be 25h! After reading the article by Andrey Vinokurov, which I cited in the paragraph " List of used literature", You actually find that if you take two lines you can get an array, allowing you to quickly find the replacement elements using the assembler command xlat. They say it can be done in another way faster, but Andrey Vinokurov spent about four years researching fast algorithms for the implementation of GOST! I don't think you should reinvent the wheel when you already have one.

So, about the array:

Let's take the first two lines zero and the first, create an array of 256 bytes. Now we observe one peculiarity that if it is necessary to transform 00h, then the result will be 75h (based on Fig. 3) - we put this value into the array at offset 00h. We take the value 01h, the result of the substitution function 79h, put it into the array at offset 01, and so on up to 0FFh, which will give us 0FCh, which we will put into the array at offset 0FFh. So we got an extended substitution table for the first group of rows: the first and zero. But there are still three groups: second page 2, page 3, third page 4, page 5, fourth page 6, page 7. We deal with these three groups in the same way as with the first. The result is an extended substitution table!

Now we can implement an algorithm that will perform the replacement. To do this, we take the source codes that Andrei Vinokurov posted on his page, see " Bibliography».

lea ebx, extented_table_simple

mov eax, [put the number to be replaced]

add ebx, 100h; jump to next two nodes

sub ebx, 300h; so that in the future ebx points to the table

Now one more feature, with the previous actions we not only replaced, but also shifted the number by 8 bits to the left! We just have to shift the number another 3 bits to the left:

and we get the result of the operation rol eax, 11!

I can't add anything more on optimization, the only thing I can emphasize is what I said above - use registers more often than memory access. I think these words are only for beginners, experienced ones and without my words understand this perfectly :).

Requirements for key information.

As stated in the article by Andrey Vinokurov, the key is selected according to two criteria:

- a criterion for equiprobable distribution of bits between the values ​​1 and 0. Usually, the criterion for equiprobable distribution of bits is the Pearson criterion ("chi-square").

This means a key, in principle, any number can. That is, when the next bit of the key is formed, the probability of its initialization by one or zero is 50/50!

Please note that the key consists of eight elements, each of 32 bits, so there are only 32 * 8 = 256 bits in the key and the number of possible keys is 2 256! Doesn't that strike you? 🙂

- series criterion.

If we look at our key, which I gave in the paragraph " 4.1 Implementation of the main step of the crypto transformation», Then you will notice that the following notation is valid:

Rice. ten

In one phrase, the value of k 1 should not be repeated not in k 2, not in any other element of the key.

That is, the key that we have chosen as the consideration of the encryption algorithm is consistent with the two above criteria.

Now about the choice of the table of substitutions:

Now let's talk about how to choose the right substitution table. The main requirement for the selection of replacement tables is the phenomenon of “non-repeatability” of elements, each of which is 4 bits in size. As you saw above, each row of the substitution table consists of the values ​​0h, 1h, 2h, 3h,…, 0fh. So the main requirement is that each line contains the values ​​0h, 1h, 2h, ..., 0fh and each such value in one copy. For example, the sequence:

1 2 3 4 5 6 7 8 9 A B C D E F

It fully complies with this requirement, but still! It is not recommended to select this sequence as a string. Since if you feed a value to the input of a function that relies on such a string, then you will get the same value at the output! Don't believe me? Then take the number 332DA43Fh and eight such lines as a substitution table. Perform the replacement operation, and I assure you, the output will be the number 332DA43Fh! That is, the same that you submitted to the input of the operation! And this is not a sign of good form in encryption, and was it? 🙂

This was one requirement, the next criterion says that - every bit of the output block must be statistically independent of every bit of the input block!

How does it look simpler? And here is how, for example, we have chosen from the above number the element s0 = 0Fh, 01111b. The probability that we will now replace the first bit with one or zero is 0.5! The probability of replacing the second, third and fourth bits, each bit, we consider separately, with ones or zeros is also 0, 5. When choosing s1 = 0Eh, the probability that we are a zero bit, and this is "0", will be replaced by a zero or one too equals - 0.5! Thus, according to this criterion, there is no regularity between the replacement of zero bits of elements s0, s1! Yes, you could substitute ones, but you could also substitute zeros. 🙂

To evaluate the table by this criterion, you can build a table of correlation coefficients calculated by the formula:

- if p = 1, then the value of bit j at the output is equal to the value of bit i at the input for any combinations of bits at the input;

- if p = -1, then the value of bit j at the output is always the inverse of the input bit i;

- if p = 0, then the output bit j with equal probability takes the values ​​0 and 1 for any fixed value of the input bit i.

Let's take one line example:

D	B	4	1	3	F	5	9	0	A	E	7	6	8	2	C

Let's break it down into "components":

Let's calculate one coefficient according to the above formula. To make it easier to understand how this is done, I will explain in more detail:

- we take the 0th bit of the 0th number (0) at the input and the 0th bit of the 0th number at the output (1) we carry out the operation 0 XOR 1 = 1.

- we take the 0th bit of the 1st number (1) at the input and the 0th bit of the 1st number at the output (1) we carry out the operation 1 XOR 1 = 0.

- we take the 0th bit of the 2nd number (0) at the input and the 0th bit of the 2nd number at the output (0) we carry out the operation 0 XOR 0 = 0.

- we take the 0th bit of the 3rd number (1) at the input and the 0th bit of the 3rd number at the output (1) we carry out the operation 1 XOR 1 = 0.

Conducting successively XOR operations in this sequence, we count the number of all non-zero values, we get the value 6. Hence P 00 = 1- (6/2 4-1) = 0.25. So, it turned out that the value of bit 0 at the output is equal to the value of bit 0 at the input in 4 cases out of 16;

Final odds table:

The table of coefficients will be as follows (to whom it is not lazy to recalculate)

	entrance
Output		0	1	2	3
	0	-0,25	0,00	0,00	0,00
	1	0,00	1,00	0,00	0,00
	2	0,00	0,00	1,00	0,00
	3	0,00	0,00	0,00	-0,50

Well, in this table, things are even worse - bits 1 and 2 of the group remain unchanged! The cryptanalyst has where to turn 🙂 Taking into account all these requirements, a simple search ("head-on") found permutation tables corresponding to the indicated theory (today - 1276 combinations) Here are some of them:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

List of used literature.

1. Article by Andrey Vinokurov:

Encryption algorithm GOST 28147-89, its use and implementation

for computers of the Intel x86 platform.

(can be found at: http://www.enlight.ru/crypto/frame.htm).

There are also the source codes for the implementation of the encryption algorithm.

1. Horst Feistel's article:

Cryptography and Computer Security.

(can be found at the same address as the previous article)

1. Ross N. Williams:

An Elementary Guide to CRC Error Detection Algorithms

Posted on the site www.wasm.ru.

Acknowledgments.

I would like to express my gratitude to all visitors to the forum www.wasm.ru. But I would especially like to thank ChS, who is currently known as SteelRat, he helped me understand things that I probably would never have understood, as well as help in writing the paragraph: “ Key information requirements”, The main part of this paragraph was written by him. I am also deeply grateful to the employee of the KSTU named after A.N. Tupolev Anikin Igor Vyacheslavovich and it would be a sin not to mention Chris Kaspersky for the fact that he is and Volodya / wasm.ru for his instructions. Oh, and I get it from him :). I also want to note Sega-Zero / Callipso, but that brought some mathematical jungle to my mind.

This is, perhaps, all that I would like to tell you.

I would be grateful for any criticism or questions related to this article or just advice. My contact details: [email protected], ICQ - 337310594.

Best regards, Evil`s Interrupt.

P.S.: With this article, I did not try to outdo anyone. It was written with intention, to facilitate the study of GOST, and if you have difficulties, this does not mean that I am guilty of this. Be reasonable and have patience, all the best to you!

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

Algorithm description

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

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

with the sub-block value N2 (addition is performed modulo 2), then the sub-blocks are swapped. Such a transformation is performed for a certain number of rounds: 16 or 32, depending on the mode of operation of the algorithm (described below). In each round, the following operations are performed:

1. Key overlay. The content of the sub-block / VI is added modulo 2 32 with a 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, that is, the 256-bit encryption key is represented as a concatenation of 32-bit subkeys (Fig. 3.2):

SH ATI, AG2, YU, AG4, K5, KB, K7.

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

Rice. 3.1. Algorithm scheme GOST 28147-

Rice. 3.2. Algorithm encryption key GOST 28147-89

2. Tabular replacement. After the key is imposed, the sub-block / VI 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 sub-block. Substitution boxes (S-boxes) are often used in modern encryption algorithms, so it is worth considering them in more detail.

Tabular replacement is used in this way: a data block of a certain dimension (in this case, 4-bit) is fed 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 a 4-bit block "0100" come to the input, that is, the value 4. According to the table, the output value will be 15, that is. "1111" (0 is replaced by 4, 1 is replaced by 11, the value of 2 does not change, etc.).

As you can see, the algorithm scheme is very simple, which means that the largest data encryption load falls on the replacement tables. Unfortunately, the algorithm has the property that there are “weak” substitution tables, when using which the algorithm can be disclosed by cryptanalytic methods. The 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 left shift 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 production of simulators.

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 replace mode, the 32 rounds described above are simply performed to encrypt each 64-bit block of information. 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 the 25th to the 32nd.

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

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

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

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

Gamma mode

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

1. In registers N1 and N2 their initial filling is written - a 64-bit value, called "synchro-burst" (synchro-burst, in practice, is an analogue of the initialization vector in the CBC, CFB and OFB modes).

2. Encryption of the contents of registers / VI and N2 (in this case - sync messages) is performed in the 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 content of N2 is 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 registers / VI and N2 are output as a 64-bit cipher gamma block (ie, in this case / VI and N2 form the first gamma block).

6. If the next block of gamma is needed (ie, you need to continue encryption or decryption), you return to step 2.

For decryption, the gamma is generated in a similar way, then the XOR operation is again applied to the ciphertext and gamma bits.

To generate the same gamut of cipher, the user decrypting the cryptogram must have the same key and the same synchro-message value that were used to encrypt the information. Otherwise, it will not be possible to get 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 assume that the effective length of the algorithm key (256 bits) is increased by another 64 bits of the sync message, which can be considered as an additional key element.

Gamma mode with feedback

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

Rice. 3.4. Generation of the cipher gamma in the feedback gamma mode

Mode of production of a simulator

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

Generation of a simulator is performed as follows:

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

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

3. M and N2 are encrypted again in the reduced mode of simple replacement, and so on until the last block of information.

An imitator is the 64-bit resulting content of registers N1 and N2 or part of it. The most commonly used 32-bit prefix is ​​used, that is, half of the register contents. This is enough, since, like any checksum, the simulator is designed primarily to protect against accidental distortion of information. To protect against deliberate data modification, other cryptographic methods are used - first of all, an electronic digital signature (see section 1.1).

The imitator is used as follows:

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

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

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

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

An imitator is some analogue of the MAC message authentication code calculated in the CBC mode; the difference is that the sync message is not used in the computation of the prefix, whereas the initialization vector is used in the computation of the MAC.

Cryptographic strength of the algorithm

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

□ large key length - 256 bits; together with the secret sync message, the effective key length is increased to 320 bits;

□ 32 rounds of transformations; after 8 rounds, the full effect of dispersion of the input data is achieved: a change in one bit of the plaintext block will affect all the bits of the ciphertext block, and vice versa, that is, there is a multiple security margin.

Consider the results of cryptanalysis of the GOST 28147-89 algorithm.

Analysis of replacement tables

Since substitution tables are not given in the standard, a number of works (for example, c) suggest that a "competent organization" can produce both "good" and "bad" substitution 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 used replacement tables; accordingly, there are weak replacement tables (see an example above), the use of which can simplify the attack on the algorithm. Nevertheless, the possibility of using different substitution tables seems like a very worthy idea, in favor of which two facts from the history of the DES encryption standard can be cited (see section 3.15 for details):

□ 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 rigidly defined in the standard, respectively, the implementation of the algorithm probably does not support the ability to change tables to others.

In a number of works (for example, and) it is mistakenly concluded that the secret tables of substitutions of the GOST 28147-89 algorithm can be part of the key and increase its effective length (which is insignificant, since the algorithm has a very large 256-bit key). However, the work proved that secret substitution tables can be calculated using the following attack, which can be applied in practice:

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

2. Using the zero vector, the values ​​of the substitution 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:

□ the GOST-H algorithm, in which, relative to the original algorithm, the order of using the subkeys has been changed, namely, in rounds 25 to 32, the subkeys are used in direct order, that is, in the same way as in the previous rounds of the algorithm ;

□ 20-round GOST® algorithm, which uses XOR to apply the key instead of modulo 32 addition.

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 should be noted that in the part of GOST © cryptanalysis, the work repeats word for word the section devoted to the cryptanalysis of the GOST 28147-89 algorithm, published in 2000 by a well-known work (without any references to the original). This casts doubt on the professionalism of the authors of the work and the rest of its results.

A very interesting modification of the algorithm is proposed in the work: tables S \… Ss must be different; in each round of the algorithm, they must be rearranged according to a certain law. This permutation can be dependent on the encryption key, or it can be secret (that is, it can be part of the encryption key larger 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, which analyzes one of the possible methods for calculating substitution 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 attacks on the full-round GOST 28147-89 without any modifications. One of the first open papers analyzing the algorithm, a well-known paper, 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 linked keys, but only if weak substitution tables are used. The 24-round variant of the algorithm (which lacks the first 8 rounds) is opened in the same way for any substitution tables, but strong substitution tables (for example, shown in c) make such an attack completely impractical.

Domestic scientists A.G. Rostovtsev and E.B. Makhovenko in 2001 in their work proposed a fundamentally new method of cryptanalysis (according to the authors, much more effective than linear and differential cryptanalysis) by forming an objective function from a known plain text corresponding to it ciphertext and the desired key value and finding its extremum corresponding to the true key value. They also found a large class of weak keys of the GOST 28147-89 algorithm, which allow opening the algorithm using only 4 selected plain texts 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 with which, using differential cryptanalysis on linked keys, it is possible to obtain, with a 91.7% probability, 12 bits of the secret key. The attack requires 2 35 selected plaintexts and 2 36 encryption operations. As you can see, this attack is practically useless for a real attack on the algorithm.

Algorithm GOST 28147-89 and cipher "Magma" (GOST R 34.12-2015)

General scheme of the algorithm. The algorithm described by GOST 28147-89 “Information processing systems. Cryptographic protection. Cryptographic Transformation Algorithm ", is a domestic standard for symmetric encryption (before January 1, 2016) and is mandatory for implementation in certified cryptographic information protection tools used in state information systems and, in some cases, in commercial systems. Certification of means of cryptographic protection of information is required to protect information constituting a state secret of the Russian Federation, and information, the confidentiality of which is required to be ensured in accordance with the current legislation. Also in the Russian Federation, the use of the GOST 28147-89 algorithm is recommended for the protection of banking information systems.

The GOST 28147-89 algorithm (Fig. 2.21) is based on the Feistel scheme and encrypts information in blocks of 64 bits, which are split into two sub-blocks of 32 bits (I, and R). Subblock R, is processed by the round transformation function, after which its value is added to the value of the subblock Lj, then the subblocks are swapped. The algorithm has 16 or 32 rounds, depending on the encryption mode (calculation of the imitation insertion or other encryption modes).

Rice. 2.21.

In each round of the algorithm, the following transformations are performed.

1. Key overlay. Subblock content R i added modulo 2 32 with round key K. Kj is the 32-bit part of the original key used as the round one. The GOST 28147-89 ns algorithm uses a key expansion procedure, the original 256-bit encryption key is represented as a concatenation (concatenation) of eight 32-bit subkeys (Fig. 2.22): K 0, K (, K t K, K A, K 5, K 6, K 7.

The encryption process uses one of these subkeys TO

From 1st to 24th round - in direct order:

From the 25th to the 32nd round - in reverse order:

Rice. 2.22. The structure of the encryption key of the GOST 28147-89 algorithm

2. Tabular replacement. After the key has been applied, the subblock R i is divided into eight parts but 4 bits, the value of each of which is individually replaced in accordance with its replacement table (S-box). A total of eight S-boxes are used - S 0, S, S 2, S 3, S 4, S 5, S 6, S 7. Each S-block of the GOST 28147-89 algorithm is a vector (one-dimensional array) with ^ elements numbered from 0 to 15. The values ​​of the S-block are 4-bit numbers; integers from 0 to 15.

An element is taken from the S-box table, the sequence number of which coincides with the value that came to the substitution input.

Example 2.6.

Let there be an S-block of the following form:

Let the value 0100 2 = 4 be given to the input of this S-box. The output of the S-box will be the 4th element of the substitution table, ie. 15 = 1111 2 (elements are numbered starting from zero).

substitution persons are not defined by the standard, as is done, for example, in the DES cipher. Changeable values ​​of substitution tables complicate cryptanalysis of the algorithm significantly. At the same time, the robustness of the algorithm significantly depends on their correct choice.

Unfortunately, the GOST 28147-89 algorithm has “weak” substitution tables, when using which the algorithm can be easily revealed by cryptanalytic methods. Among the "weak" is, for example, a trivial table of substitutions, in which the input is equal to the output (Table 2.16).

Table 2.16

An example of a weak S-box

It is believed that the specific values ​​of the replacement tables should be kept secret and are a long-term key element, i.e. are valid for a much longer period than individual keys. However, the secret values ​​of the replacement tables are not part of the key and cannot increase its effective length.

Indeed, secret substitution tables can be calculated using the following attack, which can be applied in practice:

• a zero key is set and a search for a "zero vector" is performed, i. e. meaning z = F ( 0), where F - function of round transformation of the algorithm. This requires about 2 32 test encryption operations;
• using the zero vector, the values ​​of the substitution tables are calculated, which takes no more than 2 11 operations.

However, even if the confidentiality of the substitution tables is violated, the strength of the cipher remains extremely high and does not fall below the permissible limit.

It is also assumed that substitution tables are common for all encryption nodes within the same cryptographic protection system.

Improving the structure of S-boxes is one of the most intensively researched problems in the field of symmetric block ciphers. Basically, it is required that any changes to the inputs of the S-boxes spill out into random seemingly changing the output. On the one hand, the larger the S-boxes, the more resistant the algorithm is to the methods of linear and differential cryptanalysis. On the other hand, a large replacement table is more difficult to design.

In modern algorithms, S-boxes are usually a vector (one-dimensional array) containing 2 "t- bit elements. The block input defines the number of the element, the value of which serves as the output of the S-block.

A number of criteria have been put forward for the design of S-boxes. The substitution table must satisfy:

• strict avalanche criterion;
• bit independence criterion;
• non-linearity requirement from input values.

To fulfill the last requirement, it was proposed to specify a linear combination i bits ( i = 1, ..., T) substitution table values bent functions(eng, bent - deviating, in this case - from linear functions). Bent functions form a special class of Boolean functions characterized by the highest class of nonlinearity and compliance with the strict avalanche criterion.

In some works, for S-boxes, it is proposed to check the implementation of the guaranteed avalanche effect of order y - when one input bit changes, at least the output bits of the S-box change. The property of guaranteed avalanche effect of the order of y from 2 to 5 provides sufficiently good diffusion characteristics of S-boxes for any encryption algorithm.

When designing sufficiently large replacement tables, the following approaches can be used:

• random selection (for small S-boxes, it can lead to the creation of weak substitution tables);
• random selection followed by checking for compliance with various criteria and rejection of weak S-boxes;
• manual selection (too laborious for large S-blocks);
• mathematical approach, for example, generation using bent functions (this approach is applied in the CAST algorithm).

The following procedure for designing individual S-blocks of the GOST 28147-89 algorithm can be proposed:

• each S-box can be described by four logical functions, each of the functions must have four logical arguments;
• these functions need to be sophisticated enough. This complexity requirement cannot be formally expressed, however, as a necessary condition, it can be required that the corresponding logical functions, written in the minimum form (i.e., with the minimum possible expression length) using basic logical operations, should not be shorter than a certain required value;
• individual functions, even used in different substitution tables, must be sufficiently different from each other.

In 2011, a new attack “reflexive meeting in the middle” was proposed, which slightly reduces the resistance of GOST 28147-89 (from 2256 to 2225). The best result of cryptanalysis of the algorithm as of 2012 reduces its strength to 2,192, requiring a relatively large ciphertext size and a volume of pre-formed data. Despite the proposed attacks, GOST 28147-89 remains practically stable at the current level of development of computer technology.

Code "Magma" (GOST R 34.12-2015). The GOST 28147-89 standard has been in effect in Russia for over 25 years. During this time, it has shown sufficient durability and good efficiency of software and hardware implementations, including those on low-resource devices. Although cryptanalytic attacks have been proposed that reduce the estimates of its resistance (the best is to 2,192), they are far from being feasible. Therefore, it was decided to include the GOST 28147-89 algorithm in the newly developed symmetric encryption standard.

In the 2015 shop, two new national cryptographic standards were adopted: GOST R 34.12-2015 “Information technology. Cryptographic information protection. Block ciphers "and GOST R 34.13-2015" Information technology. Cryptographic information protection. Operating modes of block ciphers ", which come into effect on January 1, 2016.

The GOST R 34.12-2015 standard contains a description of two block ciphers with a block length of 128 and 64 bits. The GOST 28147-89 cipher with fixed nonlinear substitution blocks is included in the new GOST R 34.12-2015 as a 64-bit cipher called "Magma".

Below are the replacement blocks fixed in the standard:

The set of S-boxes given in the standard provides the best characteristics that determine the resistance of the cryptoalgorithm to differential and linear cryptanalysis.

According to the technical committee for standardization "Cryptographic information security" (TC 26), fixing nonlinear substitution blocks will make the GOST 28147-89 algorithm more unified and help eliminate the use of "weak" nonlinear substitution blocks. In addition, the fixation in the standard of all long-term parameters of the cipher meets the accepted international practice. The new standard GOST R 34.12-2015 is terminologically and conceptually linked to the international standards ISO / IEC 10116 “Information technology. Security methods. Operating modes for "-bit block ciphers" (ISO / IEC 10116: 2006 Information technology - Security techniques - Modes of operation for an n-bit block cipher) and the ISO / IEC 18033 series "Information technology. Methods and means of ensuring safety. Encryption algorithms ": ISO / IEC 18033-1: 2005" Part 1. General "(ISO / IEC 18033-1: 2005 Information technology - Security techniques - Encryption algorithms - Part 1: General) and ISO / IEC 18033-3: 2010 "Part 3. Block ciphers" (ISO / IEC 18033-3: 2010 (Information technology - Security techniques - Encryption algorithms - Part 3: Block ciphers)).

The GOST P 34.12-2015 standard also includes a new block cipher ("Grasshopper") with a block size of 128 bits. This cipher is expected to be robust against all block cipher attacks known today.

The modes of operation of block ciphers (simple replacement, gamma, gamma with output feedback, gamma with ciphertext feedback, simple replacement with engagement and the development of an imitation insert) are included in a separate standard GOST R 34.13-2015, which corresponds to the accepted international practice. These modes are applicable to both the Magma cipher and the new Grasshopper cipher.

• Bitwise circular left shift by 11 bits is performed. Decryption is carried out according to the same scheme, but with a different key usage schedule: from the 1st to the 8th round of decryption - in the direct order: from the 9th to 32nd round of decryption - in the reverse order: Compared to the DES cipher in GOST 28147-89 has the following advantages: a significantly longer key (256 bits versus 56 for the DES cipher), an attack on which by brute-force enumeration of the key set seems impossible at the moment; a simple schedule for using the key, which simplifies the implementation of the algorithm and increases the speed of computations. Design of S-blocks GOST 28147-89. It is obvious that the scheme of the GOST 28147-89 algorithm is very simple. This means that the greatest encryption load falls on the substitution tables. Tab values
• Panasepko S.P. Encryption algorithms: a special reference book. SPb .: BHV-Peter-burg, 2009.
• Kara O. Reflection Attacks on Product Ciphers. URL: http://eprint.iacr.org/2007/043.pdf
• Russian encryption standard: strength reduced. URL: http://cryptofaq.ru/index.php/2010-12-23-18-20-21/2010-12-23-18-22-09/90-2011-02-01-07-47- 27
• Achekseev E. K., Smyshlyaev S. V. GOST 28147-89: "Do not rush to bury him."

The well-known researcher, the founder of algebraic cryptanalysis, Nicolas Courtois, claims that the GOST block cipher, which was to become an international standard in the near future, has actually been cracked and is awaiting many publications in the future that should develop his ideas about the instability of this algorithm.

The following are brief excerpts from this work, which can be regarded as an alarmist attack in the midst of international standardization (the author was known for similar exaggerations in relation to AES, but his work then had a great theoretical influence on cryptanalysis, but has not led to a practical attacks on AES itself). But, perhaps, this is also a real warning about the beginning of the stage of the "aircraft diving into a tailspin", which may end with the collapse of the national encryption standard, as was the case with the SHA-1 hashing algorithm and the de facto MD5 hashing algorithm.

GOST 28147-89 was standardized in 1989 and became the official standard for the protection of confidential information for the first time, but the cipher specification remained closed. In 1994, the standard was declassified, published and translated into English. By analogy with AES (and unlike DES), GOST is allowed to protect classified information without restrictions, in accordance with the way it is specified in the Russian standard. That. GOST is not an analogue of DES, but a competitor to 3-DES with three independent keys or AES-256. Obviously, GOST is a fairly serious cipher that meets military criteria, created with the expectation of the most serious applications. At least two sets of GOST S-boxes have been identified based on applications used by Russian banks. These banks need to conduct secret communications with hundreds of branches and protect billions of dollars from fraudulent theft.

GOST is a block cipher with a simple Feistel structure, with a block size of 64 bits, a 256-bit key, and 32 rounds. Each round contains modulo 2 ^ 32 key addition, a set of eight 4-bit S-boxes, and a simple 11-bit cyclic shift. A feature of GOST is the ability to store S-blocks in secret, which can be represented as a second key that increases the effective key material to 610 bits. One set of S-boxes was published in 1994 as part of the GOST-R 34.11-94 hash function specification and, as Schneier wrote, was used by the Central Bank of the Russian Federation. It also became part of RFC4357 in the "id-GostR3411-94-CryptoProParamSet" part. There was a bug in the source code at the end of Schneier's book (in S-box order). The most accurate reference implementation of native Russian origin can now be found in the OpenSSL library. If secret S-boxes are used somewhere, then they can be extracted from software implementations and from microcircuits, in fact, the corresponding works were published.

GOST is a serious competitor

In addition to the very large key size, GOST has a significantly lower execution cost compared to AES and other similar encryption systems. In fact, it costs a lot less than AES, which requires four times as many hardware logic gates for the much lower claimed security level.

It is not surprising that GOST has become an Internet standard, in particular, it is included in many crypto libraries such as OpenSSL and Crypto ++, and is becoming more popular outside of its country of origin. In 2010, GOST was declared for ISO standardization as a worldwide encryption standard. An extremely small number of algorithms have been able to become international standards. ISO / IEC 18033-3: 2010 describes the following algorithms: four 64-bit ciphers - TDEA, MISTY1, CAST-128, HIGHT - and three 128-bit ciphers - AES, Camellia, SEED. GOST is proposed to be added to the same ISO / IEC 18033-3 standard.

For the first time in the history of industrial standardization, we are dealing with such a competitive algorithm in terms of the optimality between cost and level of security. GOST has 20 years of cryptanalysis efforts and until recently its military-grade security has not been questioned.

As the author recently learned from private correspondence, most countries opposed GOST at the ISO vote in Singapore, but the results of this vote will still be considered at the ISO SC27 plenary meeting, so GOST is still in the process of standardization at the time of publication of this work.

Expert opinions on GOST

Nothing from the available information and literature regarding GOST gives grounds to believe that the cipher may be unsafe. On the contrary, the large key size and the large number of rounds make GOST, at first glance, suitable for decades of use.

Anyone familiar with Moore's Law realizes that, in theory, 256-bit keys will remain secure for at least 200 years. GOST has been extensively studied by leading experts in the field of cryptography, known in the field of block cipher analysis, such as Schneier, Biryukov, Dankelman, Wagner, many Australian, Japanese and Russian scientists, cryptography experts from ISO, and all researchers have expressed that everything looks like this that he can be or should be safe. Although the opinion reached a broad understanding that the structure of GOST itself is extremely weak, for example, compared to DES, in particular, diffusion is not so good, however, this was always due to the fact that this should be compensated for by a large number of rounds (32), as well as an additional nonlinearity and diffusion provided by modulus addition.

Biryukov and Wagner wrote: "The large number of rounds (32) and the well-studied Feistel construction, combined with successive Shannon's permutations, provide a solid basis for GOST security." In the same work we read: "after a considerable investment of time and effort, no progress has been made in cryptanalysis of the standard in the open literature." Thus, there were no significant attacks that would allow decryption or key recovery in a realistic scenario where GOST is used in encryption with many different random keys. In contrast, there are a lot of works known on attacks on weak keys in GOST, attacks with associated keys, attacks on recovering secret S-boxes. At Crypto-2008, a hacking of a hash function based on this cipher was presented. In all attacks, the attacker has a significantly greater level of freedom than is usually allowed. In traditional applications of encryption using randomly selected keys, no serious cryptographic attacks on GOST have been found so far, which in 2010 was expressed by the final phrase: "despite the significant efforts of cryptanalysts over the past 20 years, GOST has not yet been cracked" (Axel Poschmann , San Ling, and Huaxiong Wang: 256 Bit Standardized Crypto for 650 GE GOST Revisited, In CHES 2010, LNCS 6225, pp. 219-233, 2010).

Linear and differential analysis GOST

In Schneier's well-known book, we read: "Against differential and linear cryptanalysis, GOST is probably more robust than DES." The main assessment of the security of GOST was given in 2000 by Gabidulin et al. Their results are very impressive: with a security level of 2 ^ 256 set, five rounds are enough to protect GOST from linear cryptanalysis. Moreover, even when replacing S-boxes with identical ones and the only nonlinear cipher operation - addition mod 2 ^ 32 - the cipher is still resistant to linear cryptanalysis after 6 rounds out of 32. GOST differential cryptanalysis looks relatively easier and attracts more attention. For a 2 ^ 128 security level, the researchers (Vitaly V. Shorin, Vadim V. Jelezniakov and Ernst M. Gabidulin: Linear and Differential Cryptanalysis of Russian GOST, Preprint submitted to Elsevier Preprint, 4 April 2001) assumed sufficient durability at 7 rounds. According to them, breaking GOST in more than five rounds is "extremely difficult." Moreover, two Japanese researchers have shown that a classic direct differential attack with one differential characteristic has an extremely low probability of going through a large number of rounds. Based on the fact of studying a sufficiently "good" iterative differential characteristic for a limited number of rounds (which itself has a probability of passing no better than 2-11.4 per round), the value of the set of suitable keys is less than half. For a full-round GOST, such an attack with a single characteristic will work only with a negligible part of keys of the order of 2-62 (and even in this small part it will have a probability of passing no more than 2-360).

More sophisticated attacks involve multiple differentials that follow certain patterns, such as using separate S-boxes that have zero differentials while other bits have nonzero ones. We are talking about discriminating attacks based on the poor diffusion properties of GOST. The best of these attacks works against 17 rounds of GOST, depends on the key and has an extremely weak discriminator from random data at the output itself, so that it can somehow be used to obtain information about the key.

Slip and deflect attacks

According to Biryukov and Wagner, the GOST structure, which includes the reverse order of the subkeys in the last rounds, makes it resistant to sliding attacks (the so-called "slide attacks"). However, due to the presence of a large self-similarity in the cipher, this allows key inversion attacks on combinations of fixed points and "reflection" properties (so-called "reflective attacks") for certain weak keys. The complexity of this attack is 2 ^ 192 and 2 ^ 32 matched plaintexts.

Latest results

New attacks also use reflection and actually broke GOST, which was presented at the FSE 2011 conference. These attacks were also discovered independently by the author of this paper. The attack requires 2 ^ 132 bytes of memory, which is actually worse than slower attacks with less memory requirements.

A variety of new self-similarity attacks work against all GOST keys and allow you to break a full-round GOST with a 256-bit key, not just for weak keys, as it was before. All of these attacks require significantly less memory and are significantly faster.

These new attacks can be seen as examples of a new general paradigm for cryptanalysis of block ciphers called "algebraic complexity reduction", which generalizes these attacks to many particular cases of attacks with known fixed points, slides, involutions and cycles. It is important that among the family of all these attacks there are those that allow cryptanalysis of GOST without any reflections and without any symmetric points that appear in the course of calculations. One example is a simple GOST hacking attack without reflection in this work.

Algebraic Cryptanalysis and Low Data Complexity Attacks on Reduced Rounds Ciphers

Algebraic attacks on block and stream ciphers can be represented as a problem of solving a large system of Boolean algebraic equations that follows the geometry and structure of a particular cryptographic scheme. The very idea goes back to Shannon. In practice, it was presented for DES (first presented by the author of this work) as a formal encoding method and can crack 6 rounds in just one known plaintext. Equation manipulation is based on XL algorithms, Gröbner bases, ElimLin method, SAT solvers.

In practice, algebraic attacks have been implemented against a very small number of rounds of block ciphers, but have already led to cracking of stream ciphers, and there are also successes in breaking ultra-light ciphers for micro-equipment. Because of the difficulties in memory size and computational cost estimates, they are combined with other attacks.

How to hack GOST?

An algebraic attack on a full-round GOST is presented in more detail in this publication. In a previous work, the author has already outlined 20 algebraic attacks on GOST and expects a large number of them in the near future. The attack proposed in this work is not the best of them, but it opens up an easy (at least for cryptographers' understanding) path for subsequent developments to create a specific methodology for cracking GOST.

The practical result is still modest: 2 ^ 64 known plaintext and 2 ^ 64 memory for storing plaintext / ciphertext pairs make it possible to crack GOST 2 ^ 8 faster than simple brute force. But in terms of cryptanalysis, this makes the statement that "GOST has been hacked" is completely fair.

conclusions

GOST is designed to provide a military level of security for 200 years to come. Most of the leading experts who have studied GOST have come to agree that "despite significant cryptanalytic efforts over 20 years, GOST has not yet been cracked." In 2010, GOST was promoted to ISO 18033 as the global encryption standard.

The foundation of ideas about algebraic cryptanalysis dates back over 60 years. But only in the last 10 years have been developed effective software tools for (partial) solution of many NP-complete problems. A number of stream ciphers have been cracked. Only one block cipher has been broken by this method - the weak KeeLoq itself. In this work, the author breaks an important, actually used GOST cipher. He notes that this is the first time in history that a standardized state cipher has been broken by algebraic cryptanalysis.

A simple attack "MITM with reflection" on GOST has already been presented at the FSE 2011 conference. In the work considered in this article, another attack is presented only to illustrate the fact how many attacks on GOST have already appeared now, many of which are faster, and an algebraic attack requires much less memory and opens up an almost inexhaustible space of possibilities for the adversary to attack the cipher in different ways. Also in this paper, it is shown that there is no need to use the reflection property for hacking.

The author claims that it is obvious that GOST has serious flaws and now does not provide the level of durability required by ISO. Many attacks on GOST are presented in the framework of the confirmation of the paradigm of reduction of algebraic complexity.

Finally, the researcher especially notes some facts that are not yet available to the reader, but are known to the researcher, which are important in the course of the ISO standardization process. This attack is not just a "certification" attack on GOST, which is faster than brute force brute force attack. In fact, standardizing GOST would now be extremely dangerous and irresponsible. This is because some of the attacks are feasible in practice. In practice, some GOST keys can even be decrypted, whether they are weak keys or keys from private real applications of GOST. In the previous work, the author gives a detailed consideration of the cases of the possibility of practical attacks. Significantly, "this is the first time in history that a serious standardized block cipher designed to protect military-grade secrets and designed to protect state secrets for governments, large banks and other organizations has been compromised by a mathematical attack."