Domestic data encryption standard. Domestic data encryption standard Cryptographic transformation algorithm GOST 28147 89

Encryption algorithm GOST 28147-89, its use and software implementation for computers intel Platforms x86.

Andrei Vinokurov

Description of the algorithm.

Terms and designations.

The description of the Encryption Standard of the Russian Federation is contained in a very interesting document entitled "Algorithm for the cryptographic transformation of GOST 28147-89". The fact that in his title instead of the term "encryption" appears more general concept " cryptographic transformation "Is not at all by chance. In addition to several closely related encryption procedures, the document describes one built on the general principles with them to develop algorithms. imitovka . The latter is nothing more than a cryptographic control combination, that is, the code generated from the source data using the secret key to imitovashchy , or data protection from making unauthorized changes.

At various steps of the GOST algorithms, the data they operate are interpreted and are used in different ways. In some cases, data elements are processed as arrays of independent bits, in other cases - as an integer without a sign, in third, as having a structure complex element consisting of several simpler elements. Therefore, in order to avoid confusion, an agreement should be agreed.

Elements of data in this article are indicated by capital latin letters with inclined drawing (for example, X.). Through | X.| denotes the size of the data element X. in bits. Thus, if you interpret the data item X.as a whole non-negative number, you can record the following inequality:.

If the data item consists of several smaller elements, then this fact is indicated in the following way: X.=(X. 0 ,X. 1 ,…,X N. –1)=X. 0 ||X. 1 ||…||X N. -one . The procedure for combining several data elements to one is called concatentation data and denotes the "||" symbol. Naturally, the following ratio must be performed for the sizes of data items: | X.|=|X. 0 |+|X. 1 |+…+|X N. -1 |. When specifying complex data elements and concatenation operations, the components of the data elements are listed in ascending order of seniority. In other words, if you interpret the composite element and all the data elements included in it as integers without a sign, you can record the following equality:

In the algorithm, the data element can be interpreted as an array of individual bits, in this case the bits indicate the same letter as an array, but in the lower case, as shown in the following example:

X.=(x. 0 ,x. 1 ,…,x N. –1)=x. 0 +2 1 · x. 1 +…+2 n.-one · x N. –1 .

Thus, if you paid attention to the GOST adopted the so-called. "LITTLE-ENDIAN" numbering of discharges, i.e. Inside the multi-digit words of these, individual binary discharges and their groups with smaller numbers are less significant. This is referred to in paragraph 1.3 of the standard: "When adding and cyclic shift of binary vectors with older discharges, discharges of drives with large numbers are considered." Further, the items of Standard 1.4, 2.1.1 and others prescribe to start filling out the storage register registers of a virtual encryption device with younger, i.e. Less significant discharges. Exactly the same numbering procedure is accepted in the microprocessor architecture of Intel X86, which is why, with the software implementation of the cipher on this architecture, there are no additional permutations of discharges within word data.

If a certain operation that has a logical meaning is performed above the data elements, it is assumed that this operation is performed above the corresponding bits of the elements. In other words A. B.=(a. 0 b. 0 ,a. 1 b. 1 ,…,a N. –1 b N. -1) where n.=|A.|=|B.|, and the symbol "" is denoted by an arbitrary binary logical operation; as a rule, refers to the operation excluding or , It is also a summation operation 2:

The logic of constructing cipher and the structure of the key information of the GOST.

If you carefully examine the original GOST 28147-89, it can be noted that it contains a description of the algorithms of several levels. At the top of the top there are practical algorithms designed to encrypt data arrays and developing imitava for them. All of them rely on the three low-level algorithm, called the GOST text. cycles . These fundamental algorithms are mentioned in this article as basic cycles To distinguish them from all other cycles. They have the following names and designations, the latter are in brackets and the meaning will be explained later:

• cycle encryption (32-s);
• cycle of decryption (32-P);
• the development cycle of the imitancy (16-s).

In turn, each of the basic cycles is a multiple repetition of one single procedure called for certainty further in the present work. the main step of cryptocremia .

So, to figure out the Guest, you need to understand the following things:

• what the main step cryptoprera formation;
• as the basic steps are the basic cycles;
• like three basic cycles all practical GOST algorithms are consigned.

Before proceeding to the study of these issues, you should talk about key information used by the GOST algorithms. In accordance with the principle of Kirchhoff, which is satisfied with all the modern well-known social ciphers, it is its secrecy that provides the secrecy of the encrypted message. In Guest, key information consists of two data structures. In addition to actually key necessary for all ciphers, it also contains table replacement . Below are the main characteristics of the key structures of the GOST.

The main step of cryptocremia.

The main step of cryptocremia is inherently operator determining the conversion of a 64-bit data block. An additional parameter of this operator is a 32-bit unit, which is used by any key element. The scheme of the main step algorithm is shown in Figure 1.

Figure 1. Scheme of the main step of cryptoprera formation Algorithm GOST 28147-89.

Below are explained to the algorithm of the main step:

Step 0.

• N. - the transformed 64-bit data block, during the execution of the step of its younger ( N. 1) and the eldest ( N. 2) parts are processed as separate 32-bit integers without a sign. So you can record N \u003d(N. 1 ,N. 2).
• X. - 32-bit key element;

Step 1

Completion with the key. The youngest half of the converted block is folded by module 2 32 with the key element used in step, the result is transmitted to the next step;

Step 2.

Patch replacement. The 32-bit value obtained in the previous step is interpreted as an array of eight 4-bit code blocks: S \u003d.(S. 0 , S. 1 , S. 2 , S. 3 , S. 4 , S. 5 , S. 6 , S. 7), and S. 0 contains 4 of the youngest, and S. 7 - 4 highest bits S..

Next, the value of each of the eight blocks is replaced by the new one, which is selected by the table of replacements as follows: Block value S I.changing on S I.- in order item (numbering from scratch) i.The replacement node (i.e. i.- The row of the replacement table, numbering also from zero). In other words, it is selected as a replacement for the block value of the unit from the line of replacement number, equal to the number of the block being replaced, and the column number equal to the value of the block being replaced as a 4-bit integer non-negative number. From here it becomes clear the size of the replacement table: the number of rows in it is equal to the number of 4-bit elements in a 32-bit data block, that is, eight, and the number of columns is equal to the number of different values \u200b\u200bof the 4-bit data block equal to 2 4, sixteen.

Step 3.

Cyclic shift by 11 bits left. The result of the previous step is shifted cyclically by 11 bits in the direction of high-level discharges and is transmitted to the next step. The diagram of the algorithm symbol indicates the function of the cyclic shift of its argument by 11 bits to the left, i.e. in the direction of senior discharges.

Step 4.

Bottled addition: the value obtained in step 3 is blocked by module 2 with a senior half of the converted unit.

Step 5.

Chain shift: The youngest part of the converted block is shifted to the place of the elder, and the result of the previous step is placed in its place.

Step 6.

The obtained value of the transformed block is returned as the result of the implementation of the algorithm of the main step of cryptocremia.

Basic cryptographic transformation cycles.

As noted at the beginning of this article, GOST refers to the class of block ciphers, that is, the information processing unit in it is a data block. Therefore, it is quite logical to expect that algorithms for cryptographic transformations will be defined, that is, to encrypt, decrypt and "accounting" in the control combination of one data block. These algorithms are called basic cycles GOST, which emphasizes their fundamental importance to build this cipher.

Basic cycles are built from basic steps cryptographic transformation considered in the previous section. In the process of performing the main step, only one 32-bit key element is used, while the GOST key contains eight such elements. Therefore, that the key is completely used, each of the basic cycles must repeatedly perform the main step with different elements. At the same time, it seems quite natural that in each basic cycle, all the key elements should be used the same number of times, for considerations of the cipher resistance, this number should be greater than one.

All the above assumptions, relying just for common sense, were true. Basic cycles are concluded in multiple execution. main step using different key items and differ from each other only by the number of step repetition and the order of using key elements. Below is this order for different cycles.

Cycle encryption 32-s:

K. 0 ,K. 1 ,K. 2 ,K. 3 ,K. 4 ,K. 5 ,K. 6 ,K. 7 ,K. 0 ,K. 1 ,K. 2 ,K. 3 ,K. 4 ,K. 5 ,K. 6 ,K. 7 ,K. 0 ,K. 1 ,K. 2 ,K. 3 ,K. 4 ,K. 5 ,K. 6 ,K. 7 ,K. 7 ,K. 6 ,K. 5 ,K. 4 ,K. 3 ,K. 2 ,K. 1 ,K. 0 .

Figure 2a. Cycle circuit 32-s

Cycle of decryption 32-p:

K. 0 ,K. 1 ,K. 2 ,K. 3 ,K. 4 ,K. 5 ,K. 6 ,K. 7 ,K. 7 ,K. 6 ,K. 5 ,K. 4 ,K. 3 ,K. 2 ,K. 1 ,K. 0 ,K. 7 ,K. 6 ,K. 5 ,K. 4 ,K. 3 ,K. 2 ,K. 1 ,K. 0 ,K. 7 ,K. 6 ,K. 5 ,K. 4 ,K. 3 ,K. 2 ,K. 1 ,K. 0 .

Figure 2B. Diagram Cycle decryption 32-p

The development cycle of the imitancy of 16-s:

K. 0 ,K. 1 ,K. 2 ,K. 3 ,K. 4 ,K. 5 ,K. 6 ,K. 7 ,K. 0 ,K. 1 ,K. 2 ,K. 3 ,K. 4 ,K. 5 ,K. 6 ,K. 7 .

Figure 2B. The scheme of the development cycle of the imitancy of 16-s.

Each of the cycles has its own alphanumeric designation corresponding to the template " n-X "where the first designation element ( n.), sets the number of repetitions of the main step in the cycle, and the second element of the designation ( X.), Letter, sets the order of encryption ("s") or decryption ("P") to use key elements. This order needs additional explanation:

The decryption cycle must be a reverse encryption cycle, that is, the sequential use of these two cycles to an arbitrary block should be as a result of the initial block, which is reflected in the following ratio: C. 32-P ( C. 32-s ( T.))\u003d T.where T.- arbitrary 64-bit data block, C. X ( T.) - the result of the execution of the cycle X. above the data block T.. To perform this condition for algorithms similar to GOST, it is necessary that the order to use key elements by the corresponding cycles was mutually reverse. In the justice of the recorded condition for the case under consideration it is easy to ensure that comparing the above sequences for the cycles of 32-s and 32-p. One interesting consequence implies from the above: the cycle property of being a reverse other cycle is mutual, that is, the cycle 32-s is reverse with respect to the cycle 32-p. In other words, the encryption of the data block can theoretically be performed using the decryption cycle, in this case the decryption of the data block must be performed by the encryption cycle. Of the two mutually reverse cycles, anyone can be used to encrypt, then the second must be used to decrypt data, but the standard GOST28147-89 fixes the roles behind the cycles and does not provide the user with the right to choose in this matter.

The developing cycle of the imitavar is twice the encryption cycles, the order of using key elements in it is the same as in the first 16 stages of the encryption cycle, which is not difficult to verify, considering the above sequences, so this order in the designation of the cycle is encoded by the same letter "s".

The schemes of basic cycles are shown in Figures 2A-B. Each of them accepts as an argument and returns a 64-bit data block as a result, indicated in diagrams. N.. Symbol step ( N.,X.) Indicates the execution of the main step of cryptoprera formation for the data block N. using a key element X.. There is one more difference between the encryption and calculating cycles, which is not mentioned above: at the end of the basic encryption cycles, the older and the youngest part of the result block change places, it is necessary for their mutual reversibility.

The main encryption modes.

GOST 28147-89 provides three following data encryption modes:

• simple replacement
• gamming
• feedback gamming,

and one additional mode of imitancy production.

In any of these modes, the data is processed by 64 bits blocks, which is divided by an array subjected to cryptographic transformation, which is why GOST refers to block ciphers. However, in two gammmation modes, it is possible to process an incomplete block of data size less than 8 bytes, which is essential when encrypting data arrays with an arbitrary size, which may not be multiple 8 bytes.

Before proceeding to the consideration of specific cryptographic transformation algorithms, it is necessary to explain the designations used in the diagrams in the following sections:

T. about, T. W - arrays of respectively open and encrypted data;

, – i.In order of 64-bit blocks of respectively open and encrypted data: , , the last block may be incomplete:;

n. - the number of 64-bit blocks in the data array;

C. X is the function of converting a 64-bit data block for the algorithm of the base cycle "X".

Now we describe the main encryption modes:

Simple replacement.

Encryption in this mode is to use the cycle 32-s to the open data blocks, decryption - the cycle of 32-p to blocks of encrypted data. This is the easiest of the modes, 64-bit data blocks are processed in it independently of each other. Schemes of encryption algorithms and decryption in simple replacement mode are shown in Figures 3A and B, respectively, they are trivial and do not need comments.

Picture. 3a. Algorithm for data encryption in simple replacement mode

Picture. 3b. Algorithm of data decryption in simple replacement mode

The size of an array of open or encrypted data subjected to respectively encryption or decryption must be Katten 64 bits: | T. About | \u003d | T. w | \u003d 64 · n. After performing the operation, the size of the resulting data array does not change.

The encryption mode is simple replacement has the following features:

• Since the data blocks are encrypted independently from each other and from their position in the data array, when the two identical open text blocks are encrypted, the same ciphertext blocks are obtained and vice versa. The marked property will allow cryptoanalitics to make a conclusion about the identity of the blocks of source data, if in an array of encrypted data, it was met by identical blocks, which is invalid for a serious cipher.
• If the length of the encrypted data array is not multiple 8 bytes or 64 bits, the problem occurs than and how to supplement the last incomplete data block of the array to the full 64 bits. This task is not so simple, as it seems at first glance. Obvious solutions like "add an incomplete block by zero bits" or, more generally, "add an incomplete block of a fixed combination of zero and unit bits" can be given in the hands of cryptanalitics the possibility of interactive methods to determine the contents of this incomplete block, and this fact means reduced resistance cipher. In addition, the length of the ciphertext will change, having increased to the nearest whole, multiple 64 bits, which is often undesirable.

At first glance, the above features make it almost impossible to use a simple replacement mode, because it can only be used to encrypt data arrays with a size of multiple 64 bits that do not contain duplicate 64-bit blocks. It seems that for any real data, it is impossible to ensure the execution of these conditions. It is almost the case, but there is one very important exception: remember that the key size is 32 bytes, and the size of the replacement table is 64 bytes. In addition, the presence of repeating 8-byte blocks in the key or the replacement table will talk about their very poor quality, so there can be no such repetition in real key elements. Thus, we found out that the simple replacement mode is quite suitable for encrypting key information, especially since other modes for this purpose are less convenient, since they require an additional synchronizing data element - syncropters (see the next section). Our guess is true, GOST prescribes using a simple replacement mode solely to encrypt key data.

Haming.

How can you get rid of the shortcomings of a simple replacement mode? To do this, it is necessary to make it possible to encrypt blocks with a size of less than 64 bits and ensure the dependence of the ciphertext block from its number, in other words, randomize encryption process. In Guest, this is achieved in two different ways in two encryption modes involving hamming . Hamming - This is an overlay (removal) to open (encrypted) data of the cryptographic range, that is, the sequences of data elements produced using a certain cryptographic algorithm to obtain encrypted (open) data. To overlay the gamma when encrypting and removing it, mutually reverse binary operations should be used, for example, addition and subtraction of module 2 64 for 64-bit data blocks. In GUT, for this purpose, the operation of the beaten addition of module 2 is used, since it is the back of itself and, moreover, the most simply implemented by hardware. Hamming solves both of the problems mentioned: first, all the elements of the gamma are different for real encrypted arrays and, therefore, the result of encryption even two identical blocks in one array of data will be different. Secondly, although the elements of the gamma and are produced by the same portions of 64 bits, part of such a block with a size equal to the size of the encrypted block can be used.

We now turn directly to the description of the range of gamming. Gamma for this mode is obtained as follows: With a certain algorithmic recurrent generator of the sequence of numbers (RGPH), 64-bit data blocks are produced, which are further converted by a cycle of 32-s, that is, encryption in a simple replacement mode, the result of gamma blocks are obtained. Due to the fact that the imposition and removal of the gamma is carried out using the same operation of the beaten exclusive or, the encryption and decryption algorithms in the gamm imaging mode are identical, their general scheme is shown in Figure 4.

RGPH used to generate a gamma is a recurrent function: - elements of the recurrent sequence, f. - Conversion function. Therefore, the question of its initialization inevitably arises, that is, about the element in reality, this data element is the parameter of the algorithm for gamming modes, in the diagrams it is indicated as S.and called cryptography syncopusil , and in our guest - primary filling one of the encryber registers. For certain reasons, the GOST developers decided to use the RGPH to initialize not directly syncopower, but the result of its conversion along the cycle 32-s: . The sequence of elements produced by the RGPH is entirely dependent on its initial fill, that is, the elements of this sequence are the function of its number and the initial filling of the RGPH: where f I.(X.)=f.(f I. –1 (X.)), f. 0 (X.)=X.. Taking into account the transformation according to the simple replacement algorithm, the key dependence is added:

where G I.– i.a gamma element, K. - Key.

Thus, the sequence of gamma elements for use in gammation mode is uniquely determined by key data and syncopusca. Naturally, one and the same syncopower should be used to reversible encryption procedures in the processes and decryption. From the requirement of the uniqueness of the gamma, the non-fulfillment of which leads to a catastrophic decrease in cipher resistance, it follows that to encrypt two different data arrays in one key, it is necessary to ensure the use of various syncopyocones. This leads to the need to store or transmit syncopower through communication channels along with encrypted data, although in some special cases it can be predetermined or calculated in a special way if the encryption of two arrays is excluded on one vein.

Now consider the RGPH in detail used in Guest to generate elements of the gamma. First of all, it should be noted that it does not imply the requirements for ensuring any statistical characteristics of the sequence produced by the sequence. RGPH is designed by the GOST developers based on the need to fulfill the following conditions:

• the period of repeating the sequence of the numbers generated by the RGPH should not be strongly (in percentage terms) differ from the maximum possible value of the value of 2 64 as specified
• neighboring values \u200b\u200bproduced by RGPH should differ from each other in each pate, otherwise the criptanalytics task will be simplified;
• RGPH must simply be quite implemented both hardware and software on the most common types of processors, most of which are known to have a bit of 32 bits.

Based on the listed principles, the Creators of GOST designed a very successful RGPH, which has the following characteristics:

Where C. 0 =1010101 16 ;

Where C. 1 =1010104 16 ;

Lower index in the number of numbers means it number systemThus, the constants used at this step are recorded in a 16-riche number system.

The second expression needs comments, as in the text of the GOST, something else is given:, with the same value of the constant C. one . But further in the text of the standard is given a comment, which turns out to be under the operation of the remnant of the module 2 32 -1 there It is understood not the same as in mathematics. The difference is that according to GOST (2 32 -1) mod.(2 32 -1) \u003d (2 32 -1), and not 0. In fact, it simplifies the implementation of the formula, and a mathematically correct expression for it is given above.

• the repeat sequence period for the younger part is 2 32, for the older part 2 32 -1, for the entire sequence, the period is 2 32 (2 32 -1), the proof of this fact is quite simple, get themselves. The first formula of two is implemented for one team, the second, despite its seeming bulky, for two commands on all modern 32-bit processors - the first command is the usual addition of module 2 32 with the memorization of the transfer bit, and the second command adds the transfer bit to the resulting Value.

The scheme of the encryption algorithm in gammation mode is shown in Figure 4, below are explained to the scheme:

Figure 4. Algorithm for encryption (decryption) of data in the range of harm.

Step 0.

Defines the source data for the main step of cryptocremia:

• T. o (w) - an array of open (encrypted) arbitrary data, subjected to the encryption procedure (decryption), in the course of the procedure, the array is subjected to conversion of 64 bits in portions;
• S. – syncopyushka , 64-bit data element required to initialize the gamma generator;

Step 1

The initial transformation of syncopyers performed for its "randomization", that is, to eliminate the statistical patterns present in it, the result is used as initial filling of the RGPH;

Step 2.

One step of the work of RGPH, implementing its recurrent algorithm. During this step, the eldest ( S. 1) and the younger ( S. 0) parts of the data sequence are produced independently of each other;

Step 3.

Haming. The next 64-bit element developed by the RGPH is exposed to the encryption procedure on the cycle 32-s, the result is used as a gamma element for encryption (decryption) of the next block of open (encrypted) data of the same size.

Step 4.

The result of the operation of the algorithm is an encrypted (decrypted) data array.

The following are the features of gamming as encryption mode:

1. The same blocks in the open array of data will be given when encrypted various ciphertectic blocks, which will allow to hide the fact of their identity.
2. Since the gamma overlay is processed, the encryption of the incomplete block of the data is easy to do as encryption of the bits of this incomplete block, for which the corresponding bits of the gamma block are used. So, to encrypt an incomplete block in 1 bit according to the standard you should use the youngest bit from the gamma block.
3. Syncocrust, used when encrypted, somehow must be transmitted for use when decoding. This can be achieved in the following ways:

• store or transmit syncopyer along with an encrypted data array, which will lead to an increase in the size of the data array when encrypted on the size of the syncopioneers, that is, 8 bytes;
• use the predefined sync-drip value or to produce it synchronously with a source and receiver on a specific law, in this case there is no change in the size of the transmitted or stored data array;

Both methods complement each other, and in those rare cases where the first one is not working, the second, more exotic one can be used. The second method has much less application, since it is possible to make a syncopyonel a predetermined in the event that this set of key information is encrypted with an obviously no more than one data array, which is not so often. Generate the syncopyonel synchronously at the source and the recipient of the data array is also not always possible, since it requires hard binding to anything in the system. So, forcing at first glance, the idea is used as a sync-drip in the system of transmission of encrypted messages The number of the transmitted message is not suitable, since the message may be lost and no longer reach the addressee, in this case there will be an overlooking of the source and receiver encryption systems. Therefore, in the considered case there is no alternative to the transmission of syncropters along with an encrypted message.

On the other hand, you can also give a reverse example. Suppose data encryption is used to protect information on the disk, and it is implemented at a low level, to ensure independent access, data is encrypted by sectors. In this case, it is impossible to store the sync-powder with encrypted data, since the sector size cannot be changed, but it can be calculated as some function from the number of the disk head, the track numbers (cylinder) and sector numbers on the track. In this case, the syncopier is attached to the position of the sector on the disk, which can hardly change without reformatting the disk, that is, without destroying data on it.

Hamming mode has another interesting feature. In this mode, the data array bits are encrypted independently of each other. Thus, each bit of ciphertext depends on the corresponding bit of open text and, of course, the sequence number of the bit in the array: . This implies that changing the bit of the ciphertext to the opposite value will lead to a similar change in the open text bit to the opposite:

where denotes inverted with respect to t. Bit value ().

This property gives an attacker the opportunity to affect the bits of the ciphertext to make predictable and even targeted changes to the corresponding open text, obtained after it decryption, without having a secret key. This illustrates well-known in cryptology fact that secrecy and authenticity essence Various properties cryptographic systems . In other words, the properties of the cryptosystem provide protection against unauthorized familiarization with the contents of the message and from unauthorized amendments to the message are independent and only in some cases can intersect. This means that there are cryptographic algorithms that ensure certain secrecy of encrypted data and at the same time not protecting against changes and vice versa, providing authenticity of data and in no way limiting the possibility of familiarization with them. For this reason, the property in question, the properties of the range of gamming should not be considered as its disadvantage.

Feedback gamming.

This mode is very similar to the range of gammation and differs from it only by the method of producing gamma elements - the next element of the gamma is produced as the result of the conversion in the cycle of 32-s. Synchopian cycle. This involves the engagement of the blocks - each block of ciphertext in this mode depends on the corresponding and all previous blocks of open text. Therefore, this mode is sometimes called gamming with engagement blocks . On the cipher durability, the fact of engagement of blocks does not have any influence.

The diagram of the algorithms for and decrypting in the feedback range is shown in Figure 5 and due to its simplicity in the comments do not need.

Figure 5. Algorithm for encryption (decryption) of data in a feedback gamming mode.

Encryption in feedback gamming mode has the same features as encryption in normal range, except for the effect of ciphertext distortions to the corresponding open text. To compare, write the block decryption functions for both of the modes mentioned:

Hamming;

Feedback gamming;

If in the normal range of changes in certain bits of ciphertext affect only the corresponding bits of the open text, then in the mode of gamming with feedback, the picture is somewhat more complicated. As can be seen from the corresponding equation, when decoding the data block in feedback gamming mode, the open data unit depends on the corresponding and previous blocks of encrypted data. Therefore, if you make distortions into an encrypted block, then after decryption, two open data blocks will be distorted - the corresponding and next of it will be, and the distortion in the first case will be the same character as in the mode of gamming, and in the second case - as in the mode Simple replacement. In other words, in the corresponding open data unit, the same bits will be distorted as in the block of encrypted data, and in the next open data unit all bits independently from each other with probability 1 / 2 Change your values.

Development of imitancy to the data array.

In the previous sections, we discussed the impact of the distortion of encrypted data on the corresponding open data. We found that when decrypted in a simple replacement mode, the corresponding open data unit turns out to be distorted unpredictable manner, and when decrypting the unit in the gamming mode, changes are predictable. In the feedback gammation mode, two blocks are distorted, one predictable, and another unpredictable manner. Does this mean that from the point of view of protection against imposing false data, the range of gamming is bad, and the modes of simple replacement and gamming with feedback are good? - In no case. When analyzing this situation, it is necessary to take into account that unpredictable changes in the decoded data block can be detected only in the case of the redundancy of these very data, and the greater the degree of redundancy, the more likely the distortion detection. Very much redundancy occurs, for example, for texts on natural and artificial languages, in this case the fact of distortion is detected almost inevitably. However, in other cases, for example, when distorting compressed digitized sound images, we will simply get another image that can perceive our ear. The distortion in this case will remain unparalleled if, of course, there is no a priori information about the character of sound. The output here is this: Since the ability of some encryption modes to detect distortions made to encrypted data is significantly based on the presence and redundancy of the data encrypted, this ability is not an immanent property of the corresponding modes and cannot be considered as their advantage.

To solve the problem of detection of distortion in an encrypted data array with a given probability in GOST, an additional mode of cryptographic transformation is provided - the production of imitava. Simplening is a control combination that depends on open data and secret key information. The purpose of using imitovka is to detect all random or deliberate changes in the array of information. The problem outlined in the previous paragraph can be successfully solved by adding to encrypted imitava data. For a potential attacker, the following two tasks are practically unresolved if it does not own the key:

• calculating the imitava for a given open array of information;
• selection of open data for a given imitava;

The scheme of the algorithm for the production of imitavintage is shown in Figure 6.

Figure 6. Imitancy generation algorithm for data array.

A part of the block obtained at the output is taken as imitava, usually 32 of its younger bit. When choosing the size of the imitava, it is necessary to take into account that the probability of successful imposition of false data is equal to 2 - | I. | For one selection attempt, if an attacker has no more efficient selection method than a simple guessing. When using the imitancy of 32 bits in size, this probability is equal to

Discussion of cryptographic algorithms of GOST.

Cryptographic is the resistance of the GOST.

When choosing a cryptographic algorithm for use in a specific development, one of the defining factors is its durability, that is, resistance to opponent's attempts to disclose it. The question of the stiffeness of the cipher upon closer looks down to two interrelated issues:

• is it possible to completely reveal this cipher;
• if so, how hard it is difficult to do practically;

Ciphers that are generally impossible to reveal are called absolutely or theoretically resistant. The existence of such ciphers is proved by the Shannon Theorem, however, the price of this resistance is the need to use to encrypt each key message that is not smaller in size to the message itself. In all cases, with the exception of a number of special, this price is excessive, therefore, in practice, ciphers that do not have absolute resistance are mainly used. Thus, the most common encryption schemes can be disclosed for a finite time or, more precisely, for a finite number of steps, each of which is some operations over numbers. For them, the concept of practical resistance, expressing the practical difficulty of their disclosure, is of the most important thing. A quantitative measure of this difficulty is the number of elementary arithmetic and logic operationsthat must be performed to reveal the cipher, that is, for a given ciphertext, with a probability that is not less than the specified value, define the corresponding open text. At the same time, in addition to the decoded data array, the cryptanalytics may be located blocks of open data and the corresponding encrypted data encrypted or even the opportunity to obtain the corresponding encrypted data for any open data selected data - depending on the listed and many other unspecified conditions distinguish individual types of cryptoanalysis.

All modern cryptosystems are built on the principle of Kirchoff, that is, the secrecy of encrypted messages is determined by the key secrecy. This means that even if the encryption algorithm itself is known for cryptanalitics, one, however, is not able to decrypt the message if it does not have the appropriate key. The cipher is considered well designed if there is no method to open it in a more efficient way than full of busting throughout the key space, i.e. For all possible keys. GOST is likely to meet this principle - during the years of intensive research, no effective way of its cryptanalysis has been proposed. In terms of perseverance, he is much of the orders of magnitude exceeding the former American encryption standard, DES.

Guest uses a 256-bit key and the volume of key space is 2 256. None of the current or alleged future in the current future electronic device You can not pick up the key for the time less than many hundreds of years. This value has become the actual standard of the key size for symmetric cryptoalgorithms these days, "so, the new US encryption standard also supports it. The former American standard, DES with its real key size of 56 bits and the volume of key space is only 2 56 is no longer quite persistent in the light of the possibilities of modern computing. This was demonstrated in the late 90s by several successful attempts by hacking DES by overpowing. In addition, DES was susceptible to special ways to cryptanalysis, such as differential and linear. In this regard, DES may be represented rather a research or scientific than practical interest. In 1998, his cryptographic weakness was officially recognized, the National Institute of US Standards recommended the use of triple encryption by DES. And at the end of 2001, a new US encryption standard was officially approved, AES, built on other principles and free from the drawbacks of its predecessor.

Notes on the architecture of GOST.

It is well known that the domestic encryption standard is a representative of a whole family of ciphers built on the same principles. The most famous "relative" is the former American encryption standard, the DES algorithm. All these ciphers, like GOST, contain three level algorithms. There is always a certain "basic step", on the basis of which "basic cycles" are similar, and practical procedures for encryption and developing imitovka are built on them. Thus, the specifics of each of the ciphers of this family concluded in its main step, more precisely, even in its part. Although the architecture of classical block ciphers, to which GOST belongs, is far outside the topic of this article, still it is worth saying a few words about its occasion.

Algorithms "Basic Steps of Cryptopreforming" for ciphers like GOST, built identical manner, and this architecture is called balanced firesel network (Balanced Feistel Network) by the name of a person who first offered it. Data conversion circuit on one cycle, or, how to call it, round shown in Figure 7.

Figure 7. Content of the main cryptoprement step for block ciphers like GOST.

The input of the main step serves a block of even size, the older and younger half of which are processed separately from each other. During the conversion, the younger half of the block is placed in the place of the elder, and the eldest, combined with the operation of the broken " excluding or »With the result of calculating some function, in place younger. This feature that takes an argument is a low half of the block and key information element ( X.) is a meaningful part of the cipher and is called it encryption feature . For different reasons it turned out to be beneficial to divide the encrypted block into two characters in size: | N. 1 |=|N. 2 | - It is this fact that reflects the word "balanced" in the title of architecture. However, the encryption unbalanced networks are also used from time to time, although not as often as balanced. In addition, the consistency of the cipher consistency requires that the size of the key element is not less than half the block: in GUT, all three sizes are 32 bits .

If applied to the scheme of the main step of the GOST algorithm, it becomes obvious that blocks 1,2,3 algorithms (see Fig. 1) determine the calculation of its encryption function, and blocks 4 and 5 set the formation of the output block of the main step based on the contents of the input unit and encryption functions. In more detail about architectures of modern block ciphers with a secret key, you can read in classic work, or, in adapted form, in my work.

In the previous section, we have already compared DES and GOST by durability, now we will compare them on functional content and convenience of implementation. In the GOST encryption cycles, the main step is repeated 32 times, for DES, this value is 16. However, the GOST encryption function is significantly easier for the similar DES function, in which there are many irregular bit permutations. These operations are extremely inefficiently implemented on modern non-specialized processors. GOST does not contain such operations, so it is much more convenient for software implementation.

None of the Intel X86 projects considered by the author of the implementations for the Intel X86 platform, even half of the performance proposed to your attention in this article of the implementation of the GOST despite twice the shortest cycle. All of the above suggests that GOST developers have learned both positive and negative aspects of Desa, and the current and promising possibilities of cryptanasalysis are more realized. However, to take DES as a basis when comparing the performance of the implementations of ciphers is no longer relevant. The new European Encryption Standard is much better at the same time - with the same as the GOST size of the key in 256 bits, AES works faster by about 14% - this is to be compared by the number of "elementary operations". In addition, GOST is practically unable to parallel, and Aes has the opportunity in this regard much more. On some architectures, this advantage of AES may be less on others - more. So, on intel processor Pentium It reaches 28%. Details can be found in.

Quality requirements and key sources.

Not all keys and tables of replacements provide maximum cipher durability. For each encryption algorithm, there are evaluation criteria for key information. So, for the DES algorithm, the existence of the so-called " weak keys "When using which the connection between open and encrypted data is not masked as sufficiently, and the cipher is relatively simply open.

A comprehensive answer to the question of the criteria for the quality of the keys and the GOST substrate tables, if you can get anywhere alone, then only the developers of the algorithm. The corresponding data was not published in open print. However, according to the established procedure, key data obtained from an authorized organization should be used to encrypt information related to the marginal organization. Indirectly this may indicate the presence of key data verification techniques for "stitching". If the presence of weak keys in Guest is a discussion question, then the presence of weak replacement nodes is no doubt. Obviously, the "trivial" substitution table, according to which any value is replaced by himself, is so weak that, when using it, the cipher is wake-up elementary, whatever the key.

As already noted above, the criteria for evaluating key information are not available, but some general considerations can be expressed on their account.

Key

The key must be an array of statistically independent bits accepting equal to the probability of the value of 0 and 1. It is impossible to completely exclude that some specific key values \u200b\u200bmay be "weak", that is, the cipher may not provide a given level of resistance in case of their use. However, presumably, the proportion of such values \u200b\u200bin the total mass of all possible keys is negligible. At the very least, intensive studies of the cipher have not yet revealed a single key for any known (i.e. the proposed FAPSI) replacement tables. Therefore, the keys produced using a certain sensor of truly random numbers will be qualitative with a probability that differs from the unit to a negligible value. If the keys are generated using a pseudo-random number generator, the generator used should provide the above statistical characteristics, and, in addition, have a high cryptic resistance, not less than that of the GOST itself. In other words, the task of determining the absent member generated by the sequence generator of the elements should not be easier than the task of opening the cipher. In addition, various statistical criteria can be used to rejug keys with bad statistical characteristics. In practice, two criteria is usually enough - to check the equilibious distribution of the key bits between the values \u200b\u200b0 and 1, the Pearson criterion ("Hee square") is usually used, and to check the independence of the key bits, the series criteria. We can read about the criteria mentioned in textbooks or reference books on mathematical statistics.

The best approach to the development of keys would be the use of hardware sensors MC, but this is not always acceptable for economic considerations. When generating a small array of key information, a reasonable alternative to the use of such a sensor is and is widely used in practice the "Electronic Roulette" method, when the next generated portion of random bits depends on the time of pressing the operator's key on the computer keyboard. In this scheme, the source of random data is a computer user, more precisely - the time characteristics of its reaction. In this press, only a few bits of random data can be developed at the same time, so the total speed of key information is small - up to several bits per second. Obviously, this approach is not suitable for obtaining large massivers keys.

In the case when it is necessary to work out a large amount of key information, the use of various software sensors of pseudo-random numbers is possible and is very widely widespread. Since there are high cryptoscopy, the use of the cipher itself as it is the use of the scheme itself as it as it, it is simply "cutting" the scrambled sizes into the "pieces" of the desired size, for GOST - 32 bytes. Of course, for this approach, we will need a "master key", which we can obtain the electronic roulette method described above, and with it using the cipher in the gamma generator mode, we obtain an array of key information we need. So these two ways to develop keys, "manual" and "algorithmic", work in tandem, complementing each other. The key generation schemes in "low-budget" information cryptographic systems are almost always built on this principle.

Table replacement

The replacement table is a long-term key element, that is, acts for much more long timethan a separate key. It is assumed that it is common to all encryption sites within one cryptographic protection system. Even with a violation of the privacy of the table, the cipher durability remains extremely high and does not decrease below the permissible limit. Therefore, there is no special need to keep the table secret, and in most commercial applications of GOST it is done. On the other hand, the substitution table is a critical element to ensure the durability of the entire cipher. The choice of an improper table can lead to the fact that the cipher will be easily opened by known methods of cryptoanalysis. Criteria for the development of nodes of replacements - the mystery for seven seals and FAPSI is unlikely to share it with a public in the nearest foreseeable future. Ultimately, in order to say whether this particular table of substitutions is good or bad, it is necessary to carry out a huge amount of work - many thousands of people and car hours. Once the selected and used table is subject to replacement in that and only if the cipher with its use turned out to be vulnerable to one or another kind of cryptanalysis. therefore the best choice For an ordinary user, the cipher will take one of several tables that have become public domain. For example, from the standard for hash function, it is "Centrobankovskaya"; Information about these tables can be found in open print and even on the Internet, if you look good.

For those who are not used to go easy paths, the general scheme for obtaining high-quality tables is below:

1. Using a technique, we produce a set of eight nodes of replacements with the guaranteed characteristics of nonlinearity. There are several such techniques, one of them is the use of so-called bent functions.
2. Check the fulfillment of the simplest "quality criteria" - for example, those that are published for DES replacement nodes. Here are some more general considerations on this: each substitution node can be described by four logical functions from four logical arguments. If these functions recorded in minimum form (i.e. with the minimum possible length of expression) will be not sufficient enough, such a replacement node is rejected. In addition, individual functions within the entire substitution table should differ from each other to sufficiently. At this stage, many knowingly low-quality tables are eclipsed.
3. For cipher with your selected tables, building various round models, corresponding to different types of cryptoanalysis, and measure the corresponding "profile" characteristics. So, for linear cryptoanalysis, building a linear statistical analogue of the encryption round and calculate the "profile" characteristic - the nonlinearity indicator. If it turns out to be insufficient, the replacement table is rejected.
4. Finally, using the results of the previous paragraph, expose the cipher with the table of intensive research you chose - attempt to cryptanalya by all known methods. This stage is the most difficult and time consuming. But if it is made qualitatively, then with a high degree of probability, it can be stated that the cipher with the tables you choose will not be opened with simple mortals, and is not excluded, it will not be on the teeth of the special services.

It is possible, however, it is much easier to do. The thing is that the larger the rounds in the cipher, the less effect on the durability of the entire cipher have the characteristics of the resistance of one round. Guest AHM 32 round is more than almost all ciphers with similar architecture. Therefore, for most household and commercial applications, it is enough to obtain nodes of substitutions as independent random rearrangements of numbers from 0 to 15. This can be practically implemented, for example, by mixing a deck from sixteen cards, each of which is fixed one of the values \u200b\u200bof the specified range.

Regarding the replacement table, it is necessary to note another interesting fact. To reversible cycles of encryption "32-s" and "32-P", it is not necessary that the nodes of the replacements are permutations of numbers from 0 to 15. Everything works even if there are repeated elements in the substitution node, and replacement , irreversible, - but in this case the cipher resistance is reduced. Why this is exactly the case, is not considered in this article, but it is easy to make sure in the fact. To do this, it is enough to try first encrypt, and then decrypt the data block using such a "defective" substitution table, the nodes of which contain repeating values.

Variations on the topic of GOST

Very often, for use in the cryptographic data protection system, an algorithm is required with greater than that of the GOST performance of implementation, and this does not require such high cryptic resistance. A typical example of such tasks are various kinds of electronic stock trading systems, managing trade sessions in real time. Here from the used encryption algorithms it is required that it is impossible to decipher the operational data of the system during the session (data on the applications of the applications, about the transactions, etc.), for its expiration, these data are usually already useless for intruders. In other words, guaranteed persistence is required for only a few hours - this is the typical duration of the trading session. It is clear that the use of a full-fledged GOST in this situation would be shooting from guns on sparrows.

How to do this and similar cases to increase the speed of encryption? The answer lies on the surface - use the modification of the cipher with a smaller number of the main steps (rounds) in the basic cycles. How many times we reduce the number of rounds of encryption, speed increases at the same time. The specified change can be achieved in two ways - a decrease in the key length and a decrease in the number of "view cycles" of the key. Recall that the number of fixed steps in basic encryption cycles is equal N.=n · M.where n. - the number of 32-bit elements in the key, m. - the number of cycles using key elements in the standard n.=8, m.\u003d 4. You can reduce any of these numbers, but the simplest option is to reduce the key length, not the touch of its use.

It is clear that the payment for acceleration will be reduced cipher resistance. The main difficulty lies in the fact that it is quite difficult to more or less accurately assess the magnitude of this reduction. Obviously, the only possible way to do this is to study the cipher options with reduced cryptographic conversion cycles "on the full program". It is clear that, firstly, it requires the use of closed information, which only the developers of the GOST, and, secondly, are very laborious. Therefore, we will now try to evaluate, very and very rude, proceeding only from general patterns.

As for the stability of the cipher to the hacking "extensive" methods, that is, to the "overhead" attack, that here is more or less clear: the key of 64 bits is somewhere on the verge of accessibility this type of attack, cipher with a key 96 bits and higher ( Remember that the key must contain an integer number of 32-bit elements) is quite resistant to it. Indeed, a few years ago, the former US encryption standard, DES, was repeatedly hacked by overwhelming, - at first he hacked computing network, organized on the basis of the global Internet, and then specialized, i.e. Designed specifically for this computing machine. We will approve that the standard version of the GOST for software implementation on modern processors is running fourwise faster DES. Then the 8-round "reduced GOST" will work 16 times faster than DES. We also apply that in the past hacking DES time performance computer equipment According to the law, Moore has increased four. We obtain as a result that now checking one 64-bit key for "reduced GOST" with eight cycles is 64 times faster than in one time the test of one key DES was performed. Thus, the advantage of this option of the GOST Before DES by the complexity of the cross-stroke attack is reduced from 2 64-56 \u003d 2 8 \u003d 256 to 256 / 64 \u003d 4 times. Agree, this is a very illusory difference, almost nothing.

It is much more difficult to assess the stability of weakened state modifications to the "intense" methods of cryptanalysis. However, the overall pattern can be traced here. The fact is that the "profile" characteristics of many of the most stronger species of cryptanalysis depend exponentially from the number of rounds of encryption. So, for linear cryptoanalysis (LKA) it will be a linearity characteristic L. :

where C. and - constants, R is the number of rounds. A similar dependence exists for differential cryptanalysis. In his "physical meaning", all the characteristics of this kind - probability. Usually the amount of source data necessary for cryptanalysis and its complexity is inversely proportional to such characteristics. It follows that these labor-intensity rates are growing exponentially with an increase in the number of basic encryption steps. Therefore, with a decrease in the number of rounds, the complexity of the most well-known types of analysis will change as, - very approximately and roughly, is the root of this degree from the initial amount. This is a very large drop in resistance.

On the other hand, GOST was designed with a large margin of strength and today is resistant to all known species of cryptanalysis, including differential and linear. With regard to the LKA, this means that for its successful conduct, more pairs are required "Open block is an encrypted block" than "exists in nature", that is, more than 2,64. Taking into account the above, this means that for a successful LCA of the 16-round GOST, you will need no less blocks or 25 bytes or 32 GB of data, and for 8-round - at least blocks or 2 19 bytes or 0.5 MB.

The conclusions from all the above are given in the following table, which generalizes the characteristics of the reduced GROA options.

Roundov number	Key size, bit	Fast Action Index	Probable cipher characteristics (very rough estimate)
24	192	1,33	Sustainable to most famous types of ka, or be on the verge of stability. The practical implementation of the CA is impossible due to the high requirements for the initial data and complexity.
16	128	2	Theoretically unstable to certain types of cryptoanalysis, but their practical implementation in most cases is difficult due to high requirements for initial data and labor intensity.
12	95	2,67	Unstable to some famous types of cryptoanalysis, but it is suitable for secrecy of small amounts of data (up to ten hundreds of Krib) for a short time.
8	64	4	Unstable to some famous types of cryptoanalysis, but it is suitable for secrecy of small amounts of data (up to dozen KB) for a short time.

The last two options, with 12 and 8 rounds are capable of providing very and very limited protection in time. Their use is justified only in tasks, where only the short-term secrecy of the closed data is required, about a few hours. The possible area of \u200b\u200bapplication of these weak cipher options is the closure of UDP traffic of electronic stock trading systems. In this case, each data packet (Datagram, the average "D" from the abbreviation UDP) is encrypted on a separate 64-bit key, and the key itself is encrypted on a session key (key whose area is one communication session between two computers) and is transmitted with data.

Before completing with the reduced gost variants, I will say that all the above considerations are highly speculative. Standard provides persistence only for one, 32-round option. And no one can give you guarantees that the stability of the reduced variants of the cipher to crack will be changed above. If you still decided to use them in your developments, remember that you stepped on a very soft soil, which may come from under your feet at any time. If the encryption speed questions soon are critical for you, maybe it is worth thinking about using a faster cipher or more powerful computer? Another consideration for which it should be done is that weakened GOST variants will be as susceptible to the quality of the replacement nodes used.

The question under consideration has a reverse side. What if the encryption rate is non-critical, and the requirements for resistance is very tight? You can increase the resistance of the GOST in two ways - conventionally call them "extensive" and "intense". The first one is nothing more than a simple increase in the number of rounds of encryption. It is not entirely clear to me why it can really need it, because the domestic standard and without this provides the necessary resistance. However, if you suffer from paranoia more necessary levels (and all the "information advocates" simply obliged to suffer, this condition of professionality is, the question is only in the degree of cases of the case :), this will help you calm down somewhat. If you are not sure of this KGB-SHIFRA or the table of replacements you use, just double, set up, etc. Number of rounds - multiplicity Select based on the severity of your case. This approach allows you to really increase the cipher durability, - if earlier cryptanalysis was simply impossible, now it is impossible in the square!

More tricky and interesting is the question, and whether it is possible to increase the durability of the cipher, without changing the number and structure of the main encryption steps. No matter how surprisingly, the answer to this is positive, although we step again on the pissile soil of speculation. The fact is that in Guest, in the main step of the transformation, it is assumed to be replaced 4 by 4 bits, and in practice (this is more in front) all software implementations perform replacement toiletly, i.e. 8 to 8 bits - this is done for considerations of efficiency. If you immediately design such a replacement as an 8-bit, then we will significantly improve the characteristics of one round. First, the "diffusion" characteristic or indicator of "avalanche" will increase - one bit of the source data and / or the key will affect the larger number of the result bits. Secondly, for large substitution nodes, you can get lower differential and linear characteristics, thereby reducing exposure to the cipher of the same name of cryptanalysis. Especially relevant for the reduced GOST cycles, and for 8 and 12 round options, such a step is simply necessary. This somewhat compensates for the loss of perseverance in them from reducing the number of rounds. What makes it difficult to use this reception - this is what designing such "enlarged" replacement nodes will have to be independently. And also the fact that larger nodes are generally designed noticeably more difficult than smaller in size.

Non-standard use of the standard.

Of course, the main purpose of cryptoalgorithm GOST is encryption and imitivorous data. However, they can also find other applications related, naturally, with information protection. Briefly tell about them:

1. For encryption in gammation mode, GOST provides for the development of a cryptographic gamma - a sequence of bits with good statistical characteristics with high cryptic resistance. Further, this gamma is used to modify open data, resulting in data encrypted data. However, this is not the only possible application of the cryptographic range. The fact is that the algorithm of its production is a sequence generator of pseudo-random numbers (GPPSH) with excellent characteristics. Of course, it is not necessary to use such a GPPSh where only the statistical characteristics of the sequence produced are required, and the cryptoscope is not needed, not very reasonable - there are much more efficient generators for these cases. But for different applications related to the protection of information, such a source will be quite by the way:

• As noted above, the gamma can be used as "raw materials" to generate keys. For this you only need to get a segment of the gamma of the desired length - 32 bytes. In this way, the keys can be made as needed and they will not need to be stored - if such a key is needed, it will be enough to work out enough. It will only be necessary to remember how the key it was developed initially, which used the sync-drumper and from which byte of the produced gamma the key began. All information, except for the key, is unnecessary. This approach will allow you to easily control a rather complicated and branched key system using only one "master key".
• Similar to the previous, the gamut can be used as source "raw materials" to generate passwords. There may be a question, why do you need to generate them, it is not easier as you need to just invent them. The failure of such an approach was clearly demonstrated by a series of incidents in computer networks, the largest of which was the daily Internet palsy in November 1988, caused by the "worm of Morris". One way to penetrate the malicious program to the computer was the selection of passwords: the program tried to enter the system, consistently dealt with passwords from its internal list of several hundred, and in a significant proportion she managed to do it. The fantasy of a person to invent passwords was very poor. That is why in those organizations where security is paid due attention, passwords generate and distributes the system administrator to users. The development of passwords is slightly complicated than the development of keys, since the "raw" binary gamut must be converted to a symbol form, and not just "cut" into pieces. In addition, individual values \u200b\u200bmay have to be discarded to ensure equal probability of the appearance of all alphabet characters in the password.
• Another way to use cryptographic gamut is guaranteed to strengthen the data on magnetic media. The fact is that even when rewriting information on magnetic carrier Traces of previous data remain, which can restore the relevant examination. To destroy these traces, this overwriting must be performed repeatedly. It turned out that it would be necessary to overwrite information on the carrier fewer times if with such a procedure to use random or pseudo-random data, which will remain unknown experts trying to restore the heated information. Gamma cipher here will be as impossible.

2. Not only cryptographic gamma, but also the cryptographic transformation itself, can be used for the needs that are not directly related to encryption:

• We know that one of these options for using the GOST is the development of imitavas for data arrays. However, on the basis of any block cipher, and the GOST Including, it is fairly easy to build a scheme for calculating a one-way hash function, also called MDC in the literature, which in different sources is deciphered as detection code of changes / manipulations (M.oDIFICATION / M.anipulation D.eTECTION. C.oDE) or digest message (M.essage. D.igest. C.oDE). The first decoding appeared in the literature much earlier, the second, shorter, I think, came up with those who were unable to remember the first :) - it was a joke. MDC can be directly used in imitigator systems as an analogue of imitavintage, no, however, from the secret key. In addition, MDC is widely used in electron-digital signature schemes (EDS), because most of these schemes are designed in such a way that to sign a convenient fixed size data block. As is well known, the standard of the Russian Federation for calculating the one-sided Hash function GOST P34.11-94 is built on the basis of the GOST 28147-89 standard.
• It is less known that on the basis of any block cipher, and the GOST including, a completely functional EDS scheme can be built, with a secret key signature and an open-inspection combination. For a number of reasons, this scheme has not received widespread practical distribution, but in some cases it is still considered as a very attractive alternative to the dominant "mathematical" schemes of EDS.

Literature

Information processing systems. Cryptographic protection. Algorithm for cryptographic transformation GOST 28147-89. State Com. USSR according to standards, M., 1989. FTP://FTP.wtc-aral.ru/pub/en.crypt/GOST-28147
Shannon Claude. Mathematical theory of secret systems. In the collection of "Work on the theory of information and cybernetics", M., Il, 1963, p. 333-369. http://www.enlight.ru/crypto/articles/shannon/shann__i.htm.
Announcing Approval of Federal Information Processing Standard (FIPS) 197, Advanced Encryption Standard (AES), Federal Register Vol. 66, No. 235 / Thursday, December 6, 2001 / Notices, PP 63369-63371. http://csrc.nist.gov/encryption/aes/
Fayastel Horst. Cryptography and computer security. Translation of A. Rinokuburov by HORST FEISTEL. Cryptography and Computer Privacy, Scientific American, May 1973, Vol. 228, No. 5, pp. 15-23. http://www.enlight.ru/crypto/articles/feistel/feist_i.htm.
Schnayer Bruce. Applied cryptography. 2nd ed. Protocols, algorithms and source texts in C language., M., "Triumph", 2002 http://www.ssl.stu.neva.ru/psw/crypto/appl_rus/appl_cryp.htm
Menezes Alfred, Van Oorschot Paul, Vanstone Scott. Handbook of Applied Cryptography. TTP: //www.cacr.math.uwaterloo.ca/hac/
Vinokurov Andrey. How is the block cipher? Manuscript. http://www.enlight.ru/crypto/articles/vinokurov/blcyph_i.htm.
Vinokurov Andrey. Cryptography issues for Infused Bytes Online Email. http://www.enlight.ru/crypto/articles/ib/ib.htm.
Andrey Vinokurov, Eduard apply. Text of the report "On Software Implementation of the Standards of Encryption of the Russian Federation and the United States", conference on informatization, Moscow, MEPhI, January 28-29, 2001. Published in conference materials.
Information technology. Cryptographic information protection. Hatch function GOST R34.11-94, GOSSTANDART RF, M., 1994.

). At the same time, the number of notes about this algorithm in the Russian media and blogs of Russian users are growing: both the results of attacks on the Russian standard and containing opinions on its operational characteristics. The authors (A, consequently, readers) these notes often make up the impression that the domestic encryption algorithm is morally obsolete, slow and possessing vulnerabilities that make it exposed to attacks to substantially more than foreign encryption algorithms with a similar key length. We would like this series of notes in an affordable form to tell about the present state of affairs with the Russian standard. In the first part, all the well-known international cryptographic public attacks will be covered in GOST 28147-89, current estimates of its resistance. In future publications, we will also consider the properties of the standard in terms of constructing effective implementations.

Nicolas Courtois - "Great and Horrible"

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

In October 2010, the process of considering the inclusion of the GOST 28147-89 algorithm to the international standard ISO / IEC 18033-3 was launched. Already in May 2011, an article of a well-known cryptograph of Nicolas Courtois, noted by a very ambiguous attitude towards him of the global cryptographic community appeared on the EPRINT electronic archive. Curo publications are a sad example of manipulating with concepts that does not open any new properties of the object under consideration, but with a claim for sensation provokes the dissemination in the incompetent environment of erroneous opinions about his valid properties.

Algebraic method

Curvo's reasoning is built around two classes of cryptanalysis methods: algebraic methods and differential. Consider the first class of methods.

Simplified method of algebraic cryptoanalysis can be described as drawing up and solving a large system of equations, each of the solutions of which corresponds to the goal of cryptanalitics (for example, if the system is compiled on one pair of open and encrypted texts, all solutions of this system correspond to the keys in which this open text is converted to This encrypted). That is, in the case of the problem of cryptanalysis of block cipher, the essence of the algebraic method of cryptoanalysis is that the key is due to the solution of the system of polynomial equations. The main difficulty is that, taking into account the characteristics of a particular cipher, you can make as much as possible simple systemSo that its decision makes it as little time as possible. Here, the key role is played by the peculiarities of each specific cipher analyzed.

Algebraic method, operated by the round, can briefly describe this. At the first stage, these properties of GOST 28147-89 are used as the existence of a fixed point for a part of the encryption conversion, as well as the so-called reflection point (Reflection Point). Thanks to these properties from a sufficiently large number of open-encrypted text pairs, several pairs are selected, which allow us to consider the transforms not by 32, but only on 8 rounds. The second stage is that according to the results of the 8th round transformations obtained at the first stage, the system of nonlinear equations is built, which are unknown in which are key bits. Further, this system is solved (it sounds simply, but in reality is the most time-consuming part of the method, because the system consists of nonlinear equations).

As noted above, there is no detailed description and analyzing the complexity of the second and main stage of key definition. It is the complexity of the second stage that determines the complexity of the entire method as a whole. Instead, the author leads the notorious "facts", on the basis of which makes the consideration estimates. It is argued that these "facts" are based on the results of experiments. Analysis of "facts" from the work of the cloos in general is given in the work of domestic authors. The authors of this work noted that many of the "facts" presented without any evidence were false with experimental checks. The authors of the article went on and for the cloos conducted an analysis of the complexity of the second stage with the help of well-founded algorithms and evaluations. The labor consumption resulting as a result of the assessment shows the complete inapplicability of the attack represented. In addition to domestic authors, large problems that arise from the round with estimates and the rationale for their own methods, also noted, for example, in work.

Differential method

Consider the second method of the round, which is based on differential cryptanalysis.

The general method of differential cryptanalysis is based on the operation of the properties used in the cryptographic primitives of nonlinear mappings associated with the effect of the key value on the relationship between the differences of pairs of input and steam output values \u200b\u200bof these mappings. We describe the basic idea of \u200b\u200bthe differential method of cryptographic analysis of block cipher. Typically, block ciphers convert the input data in stages with a certain number of so-called round transformations, and each round transformation does not use the entire key, but only some part of it. Consider a little "truncated" cipher, which is different from the initial fact that it does not have the last round. Suppose that it was possible to establish that as a result of the encryption using such a "truncated" cipher of two open texts, differing in some fixed positions, with a high probability of ciphertext, which also differ in some fixed positions. This property shows that the "truncated" cipher is greater likely to leave the relationship between some open texts and the results of their encryption. To use this explicit drawback to restore part of the key, you must have the ability to encrypt pre-selected open texts on the key that we want to restore (the so-called "attack with the selected open text"). At the beginning of the "opening of the key" procedure, a certain number of open text pairs are randomly generated in the most fixed positions. All texts are encrypted with "full" cipher. The received ciparttext pairs are used to restore those key bits that are used in the last round conversion as follows. Using some selected rapid value, the value of the desired bits of the key to all ciphertexts is used to convert, reverse the last round conversion. In fact, if we guessed the desired value of the key bits, we get the result of the work of the "truncated" cipher, and if we did not guess - we actually "encrypt the data even more", which will only reduce the dependence of the blocks between blocks (difference in some fixed positions). In other words, if there were quite a few pairs of ciphertext among the results of such "finishing", differing in our fixed positions known to us, this means that we guessed the desired key bits. Otherwise, such pairs are significantly less. Since each round is used only part of the key, bits (i.e., the bits of the key used in the last round) are not as much as the bits in full key and they can simply go through, repeating the above steps. In this case, we will definitely observe the correct value.

From the above description, it follows that the most important in the differential analysis method is the numbers of those most positions in open texts and ciphertects, the differences in which they play a key role in restoring the key bits. The fundamental presence of these positions, as well as the set of their numbers, directly depends on the properties of those nonlinear transformations that are used in any block cipher (usually the entire "nonlinearity" is concentrated in the so-called S-blocks or replacement nodes).

Courtois uses a multiple modified differential method. Immediately, we note that the cloi analysis is conducted for S-blocks other than those operating and offered in ISO. The paper presents differential characteristics (the very numbers in which blocks should differ) for a small number of rounds. The rationale for the extension of the characteristics to a larger number of rounds, as usual, is based on "facts". Courtois expresses, again, nothing but its authority, not reinforced the assumption that the change in the S-blocks will not affect the resistance of GOST 28147-89 against its attack (at the same time, the S-blocks from the 1st working draft addition to the standard ISO / IEC 18033-3 were not considered). Analysis conducted by the authors of the article shows that even if we take the unreasonable "facts" of the Courtois, and conduct an analysis of GOST 28147-89 with other S-blocks, then the attack again is not better than full extinguishing.

A detailed analysis of the work of Courtoisie with a detailed substantiation of the groundwife of all statements to reduce the resistance of the Russian standard was carried out in [,].

At the same time, the absolute lack of accuracy of the calculation recognizes even the root itself! The next slide is taken from the bookcuts presentation on the short ads of FSE 2012.

It should be noted that the work of the clocus was repeatedly criticized by foreign researchers. For example, its work on the construction of attacks on the AES block encryption algorithm with the help of the XSL method contained the same fundamental flaws as the work on the analysis of the Russian standard: most of the labor-intensity estimates appear in the text completely unfounded and smoke - detailed criticism can be found, for example, in work. In addition, the Courtois itself recognizes widespread refuses to publish his work on large cryptographic conferences and in recognized peer-reviewed magazines, who often left him only the opportunity to perform on the short ads section. This, for example, can be read in section 3 of work. Here are some quotes given by the Courtois itself and related to its work:

• "I THINK THAT THE AUDIENCES OF ASIACRYPT WILL NOT FEEL IT IS INTERESTING." ASIACRYPT 2011 reviewer.
• "... There Is a Big, Big, Big Problem: This attack, Which Is The Main Contribution of The Paper Has Already Been Published at Fse'11 (IT Was Even The Best Paper), ...". Reviewer Crypto 2011.

Thus, the professional part of the international cryptographic public belongs to the quality of the work of Curo with no less doubt than, let's say, to not confirmed by any consistent calculations of the statements of some Russian specialists about their ability to crack AES for 2 100 or another "evidence" for two pages of hypothesis About the inequality of complex classes P and NP.

Attack Isoba and Dinura-Dankelman-Shamir

The overall idea of \u200b\u200bIsoba () and Dinura-Dankelman-Shamir (hereinafter: attack DDSH) () is to build for a certain (key-dependent) a narrow set of open texts equivalent on this set of transformation, which has more simple than the encryption conversion itself, structure . In the case of the Isob method, it is a set of such 64-bit X blocks that F 8 -1 (swap (F 8 (z))) \u003d z, where Z \u003d F 16 (x), via F 8 (x) and F 16 ( x) The first 8 and the first 16 encryption rounds of GOST 28147-89 are indicated, respectively, through SWAP - the exchange of seats of 64-byte words. When open text gets into this, this set of the total 32-round transformation of GOST 28147-89 coincides with the result of a 16-round, which is operated by the author of the attack. In the case of the DDS method, this is a set of such x that F 8 (x) \u003d x (fixed conversion point F 8). For all open text, the GOST 28147-89 transformation works exactly the same as its last 8 rounds, which simplifies the analysis.

The complexity of the Atobe attack is 2,224 encryption operations, DDSh attacks - 2 192. However, all questions about whether the ISOBE and DSH attacks make new restrictions on the conditions for the use of our algorithm, removes the assessment of the material requirements required for each of the attacks: for the method of Isob, 2 32 pairs of open and encrypted texts are required, and For the DDSh method - 2 64. Processing of such volumes of material without changing the key is a priori unacceptable for any block cipher with a block length 64: on the material of 2 32, taking into account the object of birth tasks (see, for example), close to 1/2 probability of repetitive blocks, which will provide The impairment is the ability to do on encrypted texts some of the conclusions about open texts without key definition. The presence of 2,64 pairs of open and encrypted texts obtained on one vein, actually allows the enemy to carry out operations of encryption and decryption at all without knowing this key. This is due to a purely combinatorial property: an opponent in this case has the entire encryption conversion table. Such a situation is absolutely invalid under any reasonable operational requirements. For example, in CSP cryptopro, there is a technical restriction on the volume of cipher (without key transform) of a 4 MB material (see). Thus, a strict ban on the use of the key on the material of this volume is inherent in any block cipher with a block length 64 of the bit, and consequently, the source attacks and DDS are in no way narrow the use of the GOST 28147-89 algorithm while maintaining the maximum possible durability 2 256.

Of course, it should not be noted that researchers (Isoba and Dinur-Dankelman-Shamir) showed that some properties of the GOST 28147-89 algorithm allow us to find ways of analysis not taken into account by the creators of the algorithm. A simple view of a key schedule that significantly simplifies the task of building effective implementations, also allows for some rare cases of keys and open texts to build more simple descriptions transformations produced by the algorithm.

The paper demonstrates that this negative property of the algorithm can be easily eliminated with the complete preservation of performance characteristics, but it, unfortunately, is an integral part of the algorithm in an universally used its form.

Note that certain negligence in the estimates of the average labor intensity are also present in the work of Dinur, Dankelman and Shamir. So, when building an attack does not pay due attention to the next moment: For a significant share of the keys, many open texts X, such that F 8 (x) \u003d x, is empty: still points in 8 rounds conversion may simply be. The existence of fixed points also depends on the selection of replacement nodes. Thus, the attack is applicable only with certain replacement nodes and keys.

It is also worth mentioning another work with the attack on GOST 28147-89. In February 2012, an updated version of the article (from November 2011) appeared on the EPRINT electronic archive of the International Cryptographic Association, which contained a new attack on GOST 28147-89. The characteristics of the presented attack are as follows: the volume of material is 2 32 (as in Isob), and the complexity - 2 192 (like DDSH). Thus, this attack has improved a record-in-time DSH attack in terms of material from 2 64 to 2 32. Note separately that the authors honestly led all the calculations with the rationale for the complexity and volume of material. After 9 months, a fundamental error was found in the above calculations, and since November 2012, the updated version of the article in the electronic archive no longer contains any results regarding the domestic algorithm.

Attacks suggest that the violator knows "something" about the keys

We will notice again that there are also some work in the literature (see, for example, and) on attacks at GOST 28147-89 in the so-called model with connected keys. This model is based on the assumption of the possibility of a violator to access the analysis not just to pairs open and encrypted using the desired key text, but also to pairs of open and encrypted texts obtained using (also unknown) keys different from the desired known regular manifold (for example, in fixed bit positions). This model really manage to get interesting results about GOST 28147-89, however, in this model, no less strong results can be received about, for example, the most widespread use of the AES standard in modern networks (see, for example). Note that the conditions for conducting such attacks occur when using cipher in some protocol. It should be noted that the results of this kind, albeit undoubted academic interest in terms of studying the properties of cryptographic transformations, but do not actually relate to practice. For example, all Certified FSB of Russia Cryptographic Information Protection Means perform strictest requirements for encryption key generation schemes (see, for example). As indicated in the results of the analysis carried out in the presence of 18 related keys and 2 10 pairs of open and encrypted text blocks, the labor intensity of the complete opening of the closed key, with the probability of success 1-10 -4, is indeed 2 26. However, subject to the above-mentioned requirements for the development of key material, the likelihood of detecting such keys is 2 -4352, that is, 2,4096 times less than if you just try to guess the secret key from the first attempt.

The work related to the model with connected keys also includes the work that, in 2010, a lot of noise in Russian electronic editions, who do not suffer from habit, carefully check the material during the race for sensations. The results presented in it were not supported by any kind of strict justification, but contained loud statements about the possibility of hacking the state standard of the Russian Federation on a weak laptop in seconds - in general, the article was written in the best traditions of Nicolas Courtois. But, despite the completely obvious little, a familiar with the basic principles of the scope of publications to the reader, the bottomless of the article, it was for the reassuring of the Russian public after the work of Rudsky was written a detailed and thorough text containing a comprehensive analysis of this flaws. In the article with the speaker name "On the zero practical significance of the work" Key Recovery Attack on Full Gost Block Cipher With Zero Time and Memory ", it is based that the average complexity of the method given in a method is no less than the complexity of full extinguishing.

Dry residue: What is the persistence in practice?

In conclusion, we give a table containing data about all the results of the well-known international cryptographic community, the results of strictly described and reasonable attacks on GOST 28147-89. It should be noted that the complexity is given in the operations of encryption of the algorithm GOST 28147-89, and the memory and material are indicated in the blocks of the algorithm (64 bits \u003d 8 bytes).

Attack	Labor intensity	Memory	Required material
Isoba	2 224	2 64	2 32
Dinur-Dankelman-Shamir, FP, 2DMITM	2 192	2 36	2 64
Dinur-Dankelman-Shamir, FP, Low-Memory	2 204	2 19	2 64
	2 224	2 36	2 32
Dinur-Dankelman-Shamir, Reflection, 2DMITM	2 236	2 19	2 32
Full bust	2 256	1	4
Number of nanoseconds with the emergence of the Universe	2 89

Despite a fairly large cycle of research in the resistance of the algorithm GOST 28147-89, at the moment, not a single attack, the conditions for the implementation of which would be achievable with the associated length of the block in 64 bits of operational requirements. Celling from the cipher parameters (Bit length of the key, bit length) limitations on the volume of material, which can be processed on one key, is essentially strictly stricter than the minimum volume, which is necessary for any of the attacks currently known at the moment. Consequently, when performing existing operational requirements, none of the GOST 28147-89 cryptanasalia proposed to date does not allow the key to determine the complexity of less complete brute force.

"While you are alive, do not die, look at this world.
Many here have a dead shower - they are dead inside.
But go and laugh, not knowing that they are not,
Not tormenting your mortal hour, "she told me.

Aria, "there is high"

1. Introduction

1. Preliminary information about block ciphers

2.1 Firesel network.
2.2 Block cipher GOST 28147-89

1. Theoretical minimum

3.1 Key information
3.2 The main step of cryptocremia

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

1. Practice

4.1 Implementation of the main step of cryptoprera formation
4.2 Increase the speed of the algorithm
5.
6. List of used literature
7. Gratitude.

Introduction

This document is my attempt to describe the method of simple replacement of the GOST 28147-89 encryption algorithm is the easiest, but, however, the technically-competent language. How much did it work out, the reader will tell his opinion after reading the first six points.

In order for my work to give more benefits, we recommend arming the works of the authors specified in the list of literature used. Calculator is also recommended to ensure that the operation is Xor.because Reading the article suggests that the reading has been removed to explore this encryption algorithm. Although, as a reference manual, she will also suit, but I wrote this article exactly as a training.

Preliminary information about block ciphers.

Before we begin to consider the algorithm, we need to familiarize yourself with the history of creating such ciphers. The algorithm refers to the discharge of block ciphers, in the architecture of which information is divided into a final number of blocks, the ultimate naturally may not be complete. The encryption process occurs precisely above the full blocks, which form a cipherogram. The final block, if it is incompletely complemented by anything (about the nuances for his addition, I will say below) and encrypts as well as full blocks. Under the cipherogram, I understand - the result of the action of the encryption function over a certain amount of data that the user filed for encryption. In other words, the cipherogram is the end result of encryption.

The history of the development of block ciphers is associated with the beginning of the 70s, when IBM has aware of the need to protect information when transferring data on EU communications channels, has begun to fulfill its own scientific research program on the protection of information in electronic networks, including cryptographics.

A group of researchers - developers of the company IBM, which has begun to study the encryption systems with a symmetric key use scheme, headed the doctor Horst Faystel.

2.1 Firelyl networks

The architecture of the new encryption method in the classic literature proposed by the Faysiel team, but at the moment a more established term is used in Russian and foreign literature - "Firestel" or Feistel`s Network. Subsequently, this architecture was built by the Lucifer cipher - which later was published and caused a new wave of interest in cryptography as a whole.

The idea of \u200b\u200bthe file of the "Firelyl network" is as follows: the input flow of information is divided into blocks in size in n bits, where n is an even number. Each block is divided into two parts - L and R, then these parts are fed to an iterative block cipher, in which the result of the J Stage is determined by the result of the previous stage J-1! This can be illustrated by the example:

Fig. one

Where, the function A is the main action of block cipher. It may be a simple action, such as an XOR operation, and may have a more complex view of being a sequence of a number of simple actions - addition by module, shift to the left, replacement of elements, etc., in the aggregate of these simple actions form the so-called the main step of cryptocremia.

It should be noted that the key elements of the function of the function is to feed the elements of the keys and the XOR operation and from how well the work of these operations is thought out, indicates the cryptopicness of the cipher as a whole.

In order for the idea of \u200b\u200bfirewall networks is final, consider the simplest case depicted on fig. onewhere in the function A - the "MOD 2" operation will perform ("XOR"), but this simpledthe case, in a more serious situation, for example, concealing information of state importance, the function A may be more complicated (how much I have seen a function, but really happens very difficult):

Initial data:

L \u003d 1110B, R \u003d 0101, K \u003d 1111B

Get a cipherogram

1. (R + K) MOD 2 4 \u003d SMOD, Smod \u003d 0100b
2. (Smod + L) MOD 2 \u003d SXOR, SXOR \u003d 1010B
3. L \u003d R, R \u003d SXOR

L \u003d 0101B, R \u003d 1010B

Let us explain our actions:

1. This operation is addition according to MOD 2 4. In practice, such an operation is reduced to simple addition, where we must fold two numbers and ignore the transfer to the 5th category. Since, if you put the numbers of the binary representation of the binary representation of the number, the fifth discharge will be four times on the fifth discharge, take a look at the figure below, where our operations are depicted:

Fig. 2.

Here I put the arrow to the degreewise indicators, as seen, the result was to get 10100, but since the MOD 2 operation operation is ignored, we get 0100.

1. This operation in the literature is called MOD 2, in the assembler language is implemented by a team Xor.. But its more correct name MOD 2 1. Without this unique operation, it is hardly possible to build a quick, easily implemented encryption algorithm, and at the same time it is still quite cryptorant. The uniqueness of this operation is that she herself is reverse! For example, if the number and the estimate with the number B, as a result we obtain, in the future, it is enough to rexore the number b and in each other to get the same value A!

In this operation, we received 1010 having numbers 1110 and 0100 to get it back 1110, it is enough to rexor the number 0100 and 1010 among themselves! You can read more about this operation in the article that is invested on the site. www.wasm.ru., « Elementary guide toCRC_Algorithms for error detection»The author, which ROSS N. Williams. In this work there is an item - " 5. Binary arithmetic without carrying gear" That's it in this article and the operation describes xor! I exclaim because in this article this operation is so painted that the reader does not just understand how this operation works, he even starts it see, hear and feel!

1. This action is necessary that when deciphereding from the cipherogram, it was possible to obtain source values.

2.2 Block cipher GOST 28147-89

The Encryption Algorithm GOST 28147 - 89 refers to the category of block ciphers working on the architecture of balanced firewall networks, where the two parts of the selected information block have an equal size. The algorithm was developed in the depths of the eighth department of the KGB transformed into the FAPSI and was enshrined as the standard of encryption of the Russian Federation back in 1989 at the USSR.

For work this method The algorithm must be divided into 64 bits in size blocks. Generate or enter into the encryption system, the following key information: key and replacement table. The selection of key and table of change during encryption should be taken very seriously, because This is the foundation for the security of your information. What requirements are imposed on the key, and the table of replacements see the "Clear Information Requirements" item.

When considering the method, we will not sharpen on this attention, because This article, as I said above, is written in order to teach the reading, encrypt the data on the simple replacement method of this encryption algorithm, but we will definitely touch this issue at the end of the article.

Theoretical minimum.

3.1 Key Information

As I said above, an active part in the data encryption:

3.1.1. The key is a sequence of eight elements of 32 bits each. Next, we denote the symbol to, and the elements of which it consists - K1, K2, K3, K4, K5, K6, K7, K8.

3.1.2 Table of replacement - matrix of eight rows and sixteen columns, in the future - Hij. Each element at the intersection of string I and the J column takes 4 bits.

The main action in the encryption process is the main step of cryptocremia. This is nothing more than an action on encrypted data on a specific algorithm, only the name developers have entered the cumbersome :).

Before you begin to encrypt, the block is broken into two parts L and R, each 32 bits each. Choose the key element and only then these two parts of the block are fed, the key element is a substitution table to 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 actions:

1. Addition The part of the block R is summed up with the K key element by MOD 2 32. I described about such an operation above, here the most indicator is also not "4", and "32" - the result of this operation will continue to denote SMOD.
2. The resulting SMOD result was divided by four bit elements S7, S6, S5, S4, S3, S2, S5, S4, S3, S2, S1, S0 and fed to the replacement function. The replacement occurs as follows: the element Smod - S i is selected, start from the beginning from the younger element, and replacing the value from the replacement table by the i - the row and the column that the value of the element s i indicates. Go to S i +1 item and we do in the same way and continue, so that I will not replace the value of the last element of the SMOD - the result of this operation will be denoted as, SSIMPLE.
3. In this operation, the value of Ssimple shift cyclically to the left of 11 bits and get srol.
4. Select the second part of the L block and fold according to mod 2 with Srol, we eventually have SXOR.
5. At this stage, part of the block L becomes equal to the value of part R, and part of R in turn is initialized by the result of SXOR and on this function of the main step is completed!

3.3 Basic cycles: "32-s", "32-p".

In order to encrypt information, you need to split it on blocks in size in 64 bits, naturally the last block can be less than 64 bits. This fact is the Achilles fifth of this method "Simple Replacement". Since its addition to 64 bits is a very important task to increase the cryptost resistance of the cipherogram and to this sensitive place, if it is present in the array of information, and it may not be (for example, a file of 512 bytes in size!), You should consider the big Liability!

After you broke information on blocks, you should smash the key to the items:

K \u003d k1, k2, k3, k4, k5, k6, k7, k8

Encryption itself is the use of the so-called basic cycles. Which in turn includes N - the number of the main steps of cryptocremia.

Basic cycles have, how to say, labeling: N - m. Where n is the number of basic steps of cryptocreforming in the base cycle, and M is the "type" of the basic cycle, i.e. about what this is speech, O "s" ashipathion or "p" of data ashiflucing.

The basic cycle of encryption 32-s consists of 32 main steps of cryptocremia. The function implementing the steps is supplied to the unit N and the key element to the one, the first step occurs with K1, the second above the resulting result with the K2 element, 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 32-P occurs in a similar way, but the key elements are fed 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 met the theory on how to encrypt information to see how encryption in practice occurs.

Initial data:

Take the information block N \u003d 0102030405060708H, here the parts L and R are equal:

L \u003d 01020304H, R \u003d 05060708H, Take the key:

K \u003d ' aS28.zW37. q839.7342uI23.8E2T. wQM2.eWP1 '(This is ASCII - codes, in order to watch a hexadecimal view, you can open this file to view mode in Total Commander by pressing the "key" F3."And then the key" 3 "). In this key, the values \u200b\u200bof the elements will be:

k1 \u003d 'as28', k2 \u003d 'zw37', k3 \u003d 'q839', k4 \u003d '7342'

k5 \u003d 'ui23', k6 \u003d '8e2t', k7 \u003d 'wqm2', k8 \u003d 'ewp1'

Also take the following substitution table:

Fig. 3.

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

A warning:All information, including the key to the replacement table, is taken as an example to consider the algorithm!

Using the "source data", it is necessary to obtain the result of the action of the main step of cryptocremia.

1. We choose the part r \u003d 05060708h and the key element K1 \u003d 'AS28', in hexadecimal the key item will look like this: 61733238h. Now we make a summation operation by MOD 2 32:

Fig. four

As can be seen in the figure, we did not have a transfer of 33 bits marked in red and with an indicator " 32 " And if we had other values \u200b\u200bof R and the key element, it could well occur, and then we would ignored it, and later used only bits marked with yellow.

I perform such an operation by the assembler command add.:

; EAX \u003d R, EBX \u003d 'AS28'

The result of this operation is smod \u003d 66793940h

1. Now the most slanting operation, but if you look at carefully, it is no longer so terrible, as it seems at first. Imagine the SMOD in the following form:

Drawing is not saved

Fig. five

I tried to clearly present the elements of the SMOD in the picture, but I still explain:

s0 \u003d 0, S1 \u003d 4, S2 \u003d 9, etc.

Now starting with the younger element S0, we produce a replacement. Remembering 3.2 Main Step Cryptopreforming»I - string, S i - column, we are looking for a value in the zero line and a zero column.

Fig.6.

Thus, the current value of SMOD, not 6679394 0 h, and 6679394 5 h.

We proceed to replace S1, i.e. four. Using the first string and fourth column (S1 \u003d 4!). We look at the picture:

Fig. 7.

Now the Smod is the value, not 667939 4 5h, 667939. 2 5h. I assume that now the replacement algorithm is understandable to the reader, and I can say that after the end result, SSimple will have the following value - 11E10325H.

I will tell you later in the form of an assembler commands, I will tell you later in the following paragraph after I tell about the extended table.

1. The obtained SSIMPLE value should be shifted by 11 bits left.

Fig. eight

As you can see this action is pretty simple, and implemented by one assembler language command - rOL. And the result of this SROL operation is 0819288fh.

1. Now it remains part of the L of our block information block with the Srol value. I take a calculator from W2K SP4 and get SXOR \u003d 091B2B8BH.
2. This action is the final and we simply assign, clean the value of part L, and part L initialize the SXOR value.

Final result:

L \u003d 091B2B8BH, R \u003d 01020304H

4.2 Increases the speed of the algorithm

Now let's talk about optimizing the speed algorithm. In the process of implementing, any project, it is necessary to take into account that a program that works with registers more often than with memory works faster and here this judgment is also very important, because Over one block of information of the whole 32 Actions of the chiffrase!

When I implemented encryption algorithm in my program, I entered as follows:

1. Selected part of the L block into the EAX register, and R in EDX.
2. The ESI register initialized the address of the extended key, about it below.
3. The EBX register assigned the value of the addresses of the extended substitution table, about this below
4. Transmitted information from paragraphs 1.2, 3 to the function of the base cycle 32 - З or 32 - p, depending on the situation.

If you look at the key of the key of the key elements in paragraph " Basic cycles: "32-s", "32-p""Our key for the base cycle 32 - z can be represented as follows:

To 32-s \u003d

'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 go K1, K2, K3, K4, K5, K6, K7, K8 - ‘ aS28 ','zW37 ','q839 ',' 7342 ','uI23 ',' 8e2.t ','wqm2 ','eWP1 Three times this sequence is repeated. 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 placed in advance in the array elements in the order as they should be supplied at 32 - s. Thereby, I increased the memory required by turnkey, but delivered myself from some processes of thinking that I was not needed, and increased the speed of the algorithm, for An account to reduce the time of referring to memory! Here I only described the key for 32 - s, for a cycle 32 - P I entered the same way, but using another diagram of feeding the elements that I also described in paragraph " Basic cycles: "32-s", "32-p».

It is time to describe the implementation of the work function, as I promised above. I could not describe before, because This requires the input of a new concept - an extended substitution table. I can not explain to you what it is. Instead, I will show you it, and you will define for yourself, what is it - an extended replacement table?

So, in order to figure out that such an extended replacement table, we will need a replacement table, for example, we will take the one that is depicted in Fig. 3.

For example, we needed to replace, the number 66793940h. I will present it in the following form:

Drawing is not saved

Fig. nine

Now if you take the elements S1, S0, i.e. Junior byte, the result of the replacement function will be equal to 25h! Having read the article by Andrei Vinokurova, which I led in point " List of literature used"You really find that if you take two lines to get an array that allows you to quickly find the replacement elements using the assembler command xLAT.It is also said to be another way faster, but Andrei Vinokurov spent on a study of quick algorithms for the sale of a GOST for about four years! I think you should not invent a bike when he is already there.

So, about the array:

Take the two first strings zero and first, create an array by 256 bytes. Now we observe one feature that if you need to convert 00h, the result will be 75h (rely on Fig. 3) - put this value into an array to the offset 00h. Take the value of 01H, the result of the replacement function 79h, put it into an array to the offset 01 and so on to 0ffh, which we will give 0FCH, which we put in an array of 0ffh. So we got an extended substitution table for the first group of rows: the first and zero. But there are three groups: the second p. 2, p.3, the third, page 4, p. 5, fourth p. 6, p.7. With this three groups enter the same way as with the first. The result is an extended substitution table!

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

lEA EBX, EXTENED_TABLE_SIMPLE

mOV EAX, [Put the number to be replaced]

add EBX, 100H; go to two next nodes

sub EBX, 300H; So that in the future EBX shown on the table

Now another feature, by previous actions, we not only replaced, but also shifted a number of 8 bits left! We can only shift the number for another 3 bits left:

and we get the result of ROL EAX, 11!

I can not add anything to optimization anything else, the only thing I can emphasize what I said above is to use registers more often than memory appeal. I think these words only for newcomers, experienced and without my words understand it perfectly :).

Key Information Requirements.

As stated in the article Andrei Vinokurova, the key is chosen in two criteria:

- Criterion of equilibly distribution of bits between values \u200b\u200b1 and 0. Usually, as the criterion of the equilibious distribution of bits, the Pearson criterion ("chi-square") appears.

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

Please note that the key of eight elements, each 32 bits, thus just in the key 32 * 8 \u003d 256 bits and the number of possible keys 2 256! Does it not amaze it? 🙂

- Criteria series.

If we look at our key that I led in point " 4.1 Implementation of the main step of cryptoprera formation"You will notice that the next entry is true:

Fig. 10

One phrase value K 1 should not be repeated not in K 2, not in any other key element.

That is, the key that we chose as the consideration of the encryption algorithm, it fully corresponds to the two criteria above.

Now about the choice of the replacement table:

Now let's talk about how to choose the right table of replacements. The basic requirement for the choice of replacement tables is the phenomenon of "non-repeatability" of elements, each of which is 4 bits in size. As you have already seen above, each line of the substitution table consists of values \u200b\u200bof 0H, 1H, 2H, 3H, ..., 0fh. So the main requirement says that in each line there are values \u200b\u200bof 0h, 1h, 2h, ..., 0fh and each such value in one instance. For example, sequence:

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

It fully meets this requirement, but still! This sequence is not recommended as a string. Since if you feed the value to the input of the function that relies on this line, then at the output you will get the same value! Do not believe? Then take the number 332DA43FH and eight such lines as a substitution table. Spend the replacement operation, and I assure you, at the output you will receive the number 332DA43FH! That is, the same thing you filed an operation! And this is not a sign of good tone in encryption, and was it? 🙂

It was one requirement, the following criterion suggests that - each bit of the output block must be statistically independent of each bits of the inlet block!

How does it look easier? But how, for example, we chose the element S0 \u003d 0FH, 01111B from the above number above. The likelihood that we will now replace the first bit unit or zero equal to 0.5! The probability of replacing the second, third and fourth bit, each bit is considered separately, units or zeros are also 0, 5. When selecting S1 \u003d 0EH, the likelihood that we are zero bit, and this is "0", zero or unit too Equal - 0.5! Thus, according to this criterion between the replacement of zero bits of elements S0, S1 there is no regularity! Yes, you could replace units, but you could also put and zeros. 🙂

To estimate the table on this criterion, you can construct a table of correlation coefficients calculated by the formula:

- if p \u003d 1, then the value of the bit J at the output is equal to the value of the bit i at the input with any combinations of the bit input;

- if p \u003d -1, then the value of the bit J at the output is always inverting the input bit I;

- If p \u003d 0, then the output bit J with equal probability takes values \u200b\u200b0 and 1 with any fixed value of the input bit i.

Take an example of one line:

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

Spread on the "components":

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

- We take the 0th bit of the 0th number (0) at the inlet and 0th bit of the 0th number at the outlet (1) we carry out the operation 0 xor 1 \u003d 1.

- We take the 0th bit of the 1st number (1) at the inlet and 0th bit of the 1st number at the outlet (1) carry out the operation 1 xor 1 \u003d 0.

- We take the 0th bit of the 2nd number (0) at the inlet and the 0th bit of the 2nd number at the outlet (0) we carry out an operation 0 xor 0 \u003d 0.

- We take the 0th bit of 3rd numbers (1) at the inlet and 0th bit of the 3rd number at the outlet (1) carry out the operation 1 xor 1 \u003d 0.

After conducting a consistent operation of XOR in such a sequence, we count the number of all non-zero values, we obtain the value of 6. Hence the p 00 \u003d 1- (6/2 4-1) \u003d 0.25. So, it turned out that the value of the bit 0 at the outlet is equal to the value of the bit 0 at the input in 4 cases out of 16;

The final table of coefficients:

The coefficient table will be the following (who does not lazy can 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 groups remain unchanged! Cryptoanalitics There are, where to turn around, taking into account all these requirements by simple prosperity ("In the forehead"), the rearrangement tables corresponding to these theory were found (today - 1276 combinations) 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 07 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 02D-05 0E 01 08-0C 07 0A 03

List of used literature.

1. Article Andrei Vinokurova:

Algorithm of Encryption GOST 28147-89, its use and implementation

for computers platform Intel X86.

(You can find at: http://www.enlight.ru/crypto/frame.htm).

Immediately the source codes, to implement the encryption algorithm.

1. Article Horst Fayastel:

Cryptography and computer security.

(You can find the same address as the previous article)

1. ROSS N. Williams:

Elementary Manual for CRC Error Detection Algorithms

Lined on the site www.wasm.ru.

Gratitude.

I would like to make gratitude to all visitors of the forum www.wasm.ru. But it would be particularly like to thank the CHS, which in currently Known like Steelrat, he helped me understand such things that I would probably have never understood, as well as help when writing the item: " Key Information Requirements"The main part of this item was written to them. Also deeply grateful to the employee of KSTU. A.N. Tupoleva Anikina Igor Vyacheslavovich and sin would not be noted Chris Kaspersky, for the fact that he is and Volodya / Wasm.ru for his instruction. Oh, and gets me from him :). I also want to celebrate Sega-Zero / Callipso but that there are some mathematical debris to my mind.

This is perhaps everything I would like to tell you.

I will be appreciated for criticism or questions related to this article or just tips. My contact details: [Email Protected], ICQ - 337310594.

Sincerely, Evil`s Interrupt.

P.S.: This article I did not try to promote someone. It was written with intent, facilitate the study of the GOST and if you had difficulty, it does not mean that I am sure about it. Be reasonable, and take patience, all the best to you!

DES Domestic encryption standard is more convenient for software implementation.

Unlike the American DES in the domestic standard, a longer key is applied - 256 bits. In addition, the Russian standard proposes to use 32 round of encryption, while DES is only 16.

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

The algorithm is a classic chain network. The encrypted data block is divided into two identical parts, right R and left L. The right-hand side is folded with the connection of the round and through a certain algorithm encrypts the left part. Before the next round, the left and right parts are changed in places. Such a structure allows the use of the same algorithm for both encryption and to decrypt the block.

The following operations are used in the encryption algorithm:

• adjusting words by module 2 32;
• the cyclic shift of the word to the left to the specified number of bits;
• bitwise addition by module 2;
• replacement on the table.

At various steps of the GOST algorithms, the data they operate are interpreted and are used in different ways. In some cases, data elements are processed as arrays of independent bits, in other cases - as an integer without a sign, in third, as having a structure complex element consisting of several simpler elements.

Round structure GOST 28147-89

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

The encrypted data block is divided into two parts, which are then processed as separate 32-bit integers without a sign. First, the right half of the block and the location of the round is folded by module 2 32. Then the block substitution is made. The 32-bit value obtained in the previous step (denote it s) is interpreted as an array of eight 4-bit code blocks: S \u003d (S 0, S 1, S 2, S 3, S 4, S 5, S 6, S 7). Next, the value of each of the eight blocks is replaced with a new one, which is selected by the table of substitutions as follows: The value of the block S i is replaced by I-th, in order the element (numbering from zero) of the i-th node of the replacement (i.e. i-th lines Replacement tables, numbering also from scratch). In other words, it is selected as a replacement for the block value of the block number with a number number equal to the number of the block being replaced, and the column number equal to the value of the block being replaced as a 4-bit integer non-negative number. In each row of the replacement table, the number is recorded from 0 to 15 in any order without repetitions. The values \u200b\u200bof the substitution table elements are taken from 0 to 15, as in four bits that are subjected to substitution, an integer can be recorded without a sign in the range from 0 to 15. For example, the first string of the S-block may contain such values: 5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11 . In this case, the value of the block S 0 (four younger bit 32-bit numbers S) will be replaced by a number that stands in position, the number of which is equal to the value of the replaceable block. If s 0 \u003d 0, then it will be replaced by 5, if S 0 \u003d 1, then it will be replaced by 8, etc.

Fig. 5.1.

After fixing the substitution, all 4-bit blocks are again combined into a single 32-bit word, which is then cyclically shifted by 11 bits to the left. Finally, using a broken operation "The sum of module 2" The result is combined with the left half, as a result of which the new right half of R i is obtained. The new left part L I is taken equal to the youngest part of the converted unit: L i \u003d R i-1.

The obtained value of the transformed block is considered as the result of the execution of one round of the encryption algorithm.

Encryption and decryption procedures

GOST 28147-89 is a block cipher, so data conversion carried out by blocks in the so-called basic cycles. Basic cycles are repeatedly executed for the data block of the main round, discussed by us earlier, using different key items and differ from each other by the order of using key elements. Each round is used one of the eight possible 32-bit connections.

Consider the process of creating a plug round. In GOST, this procedure is very simple, especially compared to DES. The 256-bit key K is divided into eight 32-bit connections, denoted by k 0, k 1, k 2, k 3, k 4, k 5, k 6, k 7. The algorithm includes 32 rounds, so each encryption plug is used in four rounds in the sequence presented on Table 5.1.

Table 5.1. Connection sequence with encryption

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

The decryption process is made on the same algorithm as encryption. The only difference is to use the connection K i. When decoding the plug must be used in the reverse order, namely, as indicated on

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

General scheme of the algorithm. The algorithm described by GOST 28147-89 "Information processing system. Cryptographic protection. The cryptographic transformation algorithm "is a domestic standard of symmetric encryption (before January 1, 2016) and is required to implement in certified tools for cryptographic protection of information used in state information systems and, in some cases, in commercial systems. Certification of cryptographic information protection information is required to protect information that make up the state secret of the Russian Federation, and the information confidentiality of which is required to be provided in accordance with applicable law. Also in the Russian Federation, the use of the GOST 28147-89 algorithm is recommended to protect bank information systems.

The algorithm GOST 28147-89 (Fig. 2.21) is based on the Faistel circuit and encrypts information by blocks of 64 bits, which are divided into two sub-blocks of 32 bits (I, and, and R). Block R, It is processed by the function of the round conversion, after which its value is folded with the value of the sub-block LJ, then the sublocks are changed in places. The algorithm has 16 or 32 rounds depending on the encryption mode (Imit the ImageTP Calculation or other encryption modes).

Fig. 2.21.

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

1. Wheel overlay. Contents sub-block R I. folded modulo 2 32 with round key K. KJ. - This is a 32-bit part of the source key used as a round. The GOST 28147-89 ns algorithm uses the key expansion procedure, the source 256-bit encryption key is represented as a concatenation (clutch) of eight 32-bit connections (Fig. 2.22): K 0, K (, K T K, K A, K 5, to 6, to 7.

In the encryption process, one of these plugs is used. TO

From the 1st to the 24th round - in direct sequence:

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

Fig. 2.22. Building key encryption algorithm GOST 28147-89

2. Tabs replacement. After overlaying the padlock key R I. It is divided into eight parts but 4 bits, the value of each of which is separately replaced in accordance with its replacement table (S-block). A total of eight S-blocks 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 \u200b\u200bof the S-block are 4-bit numbers, i.e. integers from 0 to 15.

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

Example 2.6.

Let there be a s-block of the following form:

Suppose to the input of this s block, the value of 0100 2 \u003d 4. The 4th element of the substitution table will be filled with the s-block output, i.e. 15 \u003d 1111 2 (the numbering of elements begins with zero).

replacement faces are not defined by the standard, as is done, for example, in the SIFRE DES. Replaceable values \u200b\u200bof the substitution tables make it difficult to cryptoanalysis algorithm. At the same time, the resistance of the algorithm significantly depends on their correct choice.

Unfortunately, the GOST 28147-89 algorithm has "weak" substitutions, when using which the algorithm can be quite easily uncovered with cryptanalytic methods. The "weak" refers, for example, a trivial substitution table, in which the input is equal to the output (Table 2.16).

Table 2.16

Example of a weak S-block

It is believed that the specific values \u200b\u200bof the replacement tables should be stored secretly and are a long-term key element, i.e. Act for a much longer period than separate keys. However, the secret values \u200b\u200bof the replacement tables are not part of the key and cannot increase its effective length.

Indeed, secret replacement tables can be calculated using the following attack that is practiced in practice:

• Installed zero key and search for "zero vector", i.e. Values z. = F (0) where F - Round conversion function algorithm. This requires about 2 32 test encryption operations;
• Using a zero vector, the values \u200b\u200bof the replacement tables are calculated, which takes no more than 2 11 operations.

However, even if the confidentiality of the replacement tables are violated, the cipher remains extremely high and does not become lower than the permissible limit.

It is also assumed that the substitution tables are common to all encryption sites within one cryptographic protection system.

Improving the structure of S-blocks is one of the most intensively studied problems in the field of symmetric block ciphers. In essence, it is required that any changes in the inputs of the S-blocks are poured into random on the type of change of output. On the one hand, the greater the S-blocks, the more stable algorithm to the methods of linear and differential cryptanalysis. On the other hand, a large substrate table is more complicated to design.

In modern algorithms, S-blocks are usually a vector (one-dimensional array) containing 2 "T-bit elements. The block input determines the number of the item whose value is the output of the S-block.

To design S-blocks was nominated whole line criteria. The replacement table must satisfy:

• strict avalanche criterion;
• The criterion of independence of bits;
• The requirement of nonlinearity from the input values.

To fulfill the last requirement it was proposed to set a linear combination i. bits ( i \u003d. 1, ..., t) Values \u200b\u200bof the replacement table bentfunctions (eng, bent - Dejection, in this case, from linear functions). Bent functions form a special class of boolean functions characterized by the highest class of nonlinearity and the correspondence of a strict avalanche criterion.

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

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

• random selection (for S-blocks of a small size can lead to the creation of weak substitutions);
• random selection with a subsequent test for compliance with various criteria and rejection of weak S-blocks;
• manual selection (for S-blocks of large sizes is too time consuming);
• A mathematical approach, such as generation using bent functions (this approach is applied in the CAST algorithm).

You can propose the following procedure for designing individual S-blocks of the GOST 28147-89 algorithm:

• Each S-block can be described by four logical functions, each of the functions must have four logical arguments;
• It is necessary that these functions are quite complicated. This requirement of difficulty cannot be expressed formally, however, it can be required as the necessary condition that the corresponding logical functions recorded in the minimum form (i.e. with the minimum possible length of expression) using basic logical operations were not shorter than some required value;
• Separate functions, even used in different replacement tables, should be among themselves sufficiently.

In 2011, a new attack "Reflective Meeting in the middle" was proposed, slightly reduced persistence of GOST 28147-89 (from 2256 to 2225). The best results of the cryptanalysis of the algorithm as of 2012 reduces its resistance to 2 192, requiring a relatively large size of the ciphertext and the amount of pre-formed data. Despite the proposed attacks, at the present level of development of computing equipment, GOST 28147-89 retains practical resistance.

Cipher "Magma" (GOST R 34.12-2015).The standard GOST 28147-89 acted in Russia for more than 25 years. During this time, he showed sufficient resistance and good efficacy of software and hardware implementations, including on low-pass devices. Although cryptanalytic attacks were proposed, which reduce its durability estimates (the best - up to 2 192), they are far from the possibility of practical implementation. Therefore, it was decided to include the algorithm GOST 28147-89 into a newly developed symmetric encryption standard.

In the shop 2015, 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. Modes of operation of block ciphers ", which come into effect on January 1, 2016

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

Below are the replacement blocks enshrined in the standard:

The S-blocks contained in the standard provides best characteristicsdetermining the persistence of a cryptoalgorithm to differential and linear cryptanalysis.

According to the Technical Committee on the Standardization of Cryptographic Protection of Information (TC 26), the fixation of the blocks of the nonlinear substitution will make the algorithm GOST 28147-89 more unified and will help to exclude the use of "weak" blocks of nonlinear substitution. In addition, fixation in the standard of all long-term parameters of the cipher is responding accepted international Practice. The new standard GOST R 34.12-2015 is terminologically and conceptually associated with international standards ISO / IEC 10116 "Information technologies. Security methods. Modes of operation for "-bit block ciphers" (ISO / IEC 10116: 2006 Information Technology - Security Techniques - Modes of Operation for An N-Bit Block Cipher) and ISO / IEC 18033 series "Information technologies. Methods and security tools. 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 - Encryption Algorithms - Part 3: Block Ciphers)).

The standard of GOST P 34.12-2015 also includes a new block cipher ("Grasshopper") with a block size of 128 bits. It is expected that this cipher will be resistant to all the attacks to today's attacks on block ciphers.

Modes of operation of block ciphers (simple replacement, gamming, feedback gaming, feedback, siprotext feedback gamming, simply replacing with the engagement and production of imitavage) are removed in a separate standard GOST R 34.13-2015, which corresponds to the internationally adopted international practice. These modes are applicable both to the cipher "Magma" and to the new cipher "grasshopper".

• A bitwise cyclic shift to the left of 11 bits is carried out. The decryption is carried out in the same scheme, but with another schedule use of the keys: from the 1st to the 8th round of the decryption - in line: from the 9th to the 32nd round of the decryption - in the reverse order: compared to the Sipher DES at GOST 28147-89 There are the following advantages: a significantly longer key (256 bits versus 56 in the SIFRA DES), the attack on which by the complete integrity of the key set per dim amomant is impossible; A simple key usage schedule, which simplifies the implementation of the algorithm and increases the calculation speed. Design S-blocks GOST 28147-89. Obviously, the scheme of the GOST 28147-89 algorithm is quite simple. This means that the greatest encryption load falls on the replacement table. Tab values
• Panasepko S. P. Encryption algorithms: Special Directory. SPb.: BHV-Peter-Burg, 2009.
• Kara O. Reflection Attacks on Product Ciphers. URL: http://eprint.iacr.org/2007/043.pdf.
• Russian Encryption Standard: Resistance 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.
• Achekseyev E. K., Schdslyaev S. V. GOST 28147-89: "Do not hurry to bury him."