Domestic encryption standard.
Domestic encryption standard
S. Panasenko,
&nb sp; &nb sp; &nb sp; &nb sp; Source: Peace and Security, No. 5, 2003
Despite the fact that GOST 28147-89 was adopted back in 1989, nowadays it is widely used both in Russia and in the world as a whole. Firstly, this is facilitated by domestic legislation. Government organizations and a number of commercial ones are required to use only FAPSI-certified cryptographic tools to protect information, and obtaining a FAPSI certificate implies that “the specified cryptographic tools implement cryptographic algorithms declared state or industry standards of the Russian Federation.” Despite the abolition of FAPSI this year, the regulatory documents establishing these requirements are still valid. Secondly, this algorithm was developed with a huge reserve of cryptographic resistance, and with very little damage to the encryption speed.
The GOST 28147-89 algorithm is a classic symmetric encryption algorithm based on the Feistel network (see Fig. 1). This algorithm encrypts information in 64-bit blocks (such algorithms are called «block»). The idea of the Feistel network is that the block of encrypted information is divided into two or more sub-blocks, some of which are processed according to a certain law, after which the result of this processing is superimposed (by the bitwise addition operation modulo 2) on the unprocessed sub-blocks. Then the sub-blocks are swapped, after which they are processed again, etc., a certain number of times — rounds — for each algorithm.
Fig. 1. Feistel network
The main difference between symmetric encryption algorithms is precisely in the different functions for processing subblocks. This function is often called the «main cryptographic transformation» since it bears the main load when encrypting information. The main transformation of the GOST 28147-89 algorithm is quite simple, which ensures high speed of the algorithm; it performs the following operations (see Fig. 2):
Fig. 2. The main transformation of the GOST 28147-89 algorithm
1. Addition of a subblock to a certain fragment of the encryption key modulo 232. Kx is a 32-bit part («subkey») of a 256-bit encryption key, which can be represented as a concatenation of 8 subkeys: K = K0K1K2K3K4K5K6 K7. Depending on the round number and the algorithm operating mode (more on that below), one of the subkeys is selected for this operation.
2. Table substitution. To perform this, the subblock is divided into 8 4-bit fragments, each of which is run through its own substitution table. The substitution table contains values from 0 to 15 in a certain sequence (i.e. all possible values of a 4-bit data fragment); a block of data is fed to the table input, the numerical representation of which determines the number of the output value. For example, the value 5 is fed to the input of the following table: «13 0 11 74 91 10 143 5 122 15 8 6». As a result, the output value is 9 (since 0 is replaced by 13, 1 by 0, 2 by 11, etc.).
3. Bitwise cyclic shift of data within the subblock by 11 bits to the left.
The GOST 28147-89 algorithm has 4 operating modes:
- Simple replacement mode.
- Gamma mode.
- Feedback gamming mode.
- Imitation prefix generation mode.
All modes use the same basic transformation, but with a different number of rounds and in a different way.
The simple substitution mode is intended for encryption of keys (there are many schemes for applying symmetric encryption algorithms that use several keys for different purposes; in these cases, encryption of some keys with others is required). In this mode, 32 rounds of the main transformation are performed. In each of the rounds, as was said above, a certain subkey is used, which is selected as follows:
K((r — 1) % 8) — for rounds 1 through 24 (r denotes the round number, and % is the remainder operation after division), i.e. K0, K1, K2, K3, K4, K5, K6, K7, K0, K1, K2, etc.;
K ( (32 – r) % 8) — for rounds 25 through 32, i.e. in reverse order: K7, K6, K5, K4, K3, K2, K1, K0.
To decrypt information in the simple replacement mode, 32 rounds of the main transformation are also performed, but using subkeys according to a different scheme:
- in direct order in rounds 1 through 8;
- in reverse order in subsequent rounds.
For the actual encryption of information, the gamma and gamma with feedback modes are used. In these modes, information is encrypted by bitwise addition modulo 2 of each 64-bit block of encrypted information with the cipher gamma block. The cipher gamma is a pseudo-random sequence generated using the main transformation of the GOST 28147-89 algorithm as follows (see Fig. 3):
Fig. 3. Gamma mode
1. Registers N1 and N2 are written with their initial filling—a 64-bit value called a “sync packet.”
2. The contents of registers N1 and N2 (in this case, sync messages) are encrypted in simple replacement mode.
3. The contents of N1 are added modulo (232 — 1) with the constant C1 = 224 + 216 + 28 + 24, the result of the addition is written to register N1.
4. The contents of N2 are added modulo 232 with the constant C2 = 224 + 216 + 28 + 1, the result of the addition is written to register N2.
5. The contents of registers N1 and N2 are output as a 64-bit block of the cipher gamma (i.e. in this case N1 and N2 form the first block of the gamma).
6. If the next block of the gamma is needed (i.e. encryption or decryption must be continued), return to step 2.
For subsequent decryption, the cipher gamma is generated in a similar manner and added to the encrypted information. The result is the original information, since it is known that:
A ? B ? B=A
for any sequences of the same dimension A and B, where ? is the operation of bitwise addition modulo 2.
It is clear that to decrypt information, it is necessary to have the same encryption key and the same value of the sync message as during encryption. There are implementations of the GOST 28147-89 algorithm, in which the sync message is also a secret element, along with the encryption key. In fact, in this case, it can be considered that the encryption key is increased by the length of the sync message (64 bits), which increases the strength of the algorithm.
The feedback gamma mode differs from the gamma mode only in that before returning to step 2 (to generate the next gamma block), the contents of the encrypted information block, for the encryption of which the previous gamma block was used, are written to registers N1 and N2.
The checksum generation mode calculates checksums—cryptographic checksums of information calculated using a specific encryption key. Checksums are usually calculated before information is encrypted and stored or sent along with the encrypted data to be used for integrity control later. After decrypting the information, the checksum is calculated again and compared with the stored one; a mismatch indicates corruption or deliberate modification of the data during storage or transmission, or a decryption error.
The following operations are performed in the checksum generation mode:
1. The first 64-bit block of information for which the ciphertext prefix is calculated is written to registers N1 and N2 and encrypted in the reduced simple substitution mode, which performs 16 rounds of the main transformation instead of 32.
2. The resulting value is summed modulo 2 with the next plaintext block and stored in N1 and N2.
3. And so on until the last plaintext block.
The resulting contents of registers N1 and N2 or a part of it (depending on the required level of security) are used as the ciphertext prefix—the 32-bit contents of register N1 are often considered to be the ciphertext prefix.
When developing the GOST 28147-89 algorithm, cryptographers of domestic special services included excessive resistance—to this day, no more effective methods of hacking this algorithm are known than the method of a complete enumeration of possible encryption key options. And a complete enumeration of 2256 keys (not counting the secret sync message) is impossible to carry out in real time with the current development of computer technology.