GOST
In cryptography, GOST (Gosudarstvennyi Standard Soyuza SSR, Russian for "Government Standard of the Union of Soviet Socialist Republics") is a symmetric key block cipher published in 1990 as the Soviet standard (GOST 28147-89). It is the Soviet equivalent of the United States standard algorithm, DES, and is similar in structure.
Table of contents |
2 Cryptanalysis of GOST 3 References 4 External links |
The algorithm
GOST has a 64-bit block size and a key length of 256 bits. Its S-boxes can be secret, and they contain about 512 bits of secret information, so the effective key size can be increased to 768 bits.
GOST is a Feistel network of 32 rounds. Its round function is very simple: add a 32-bit subkey modulo 2^{32}, put the result through a layer of S-boxes, and rotate that result left by 11 bits. The result of that is the output of the round function. In the diagram to the left, one line represents 32 bits.
The subkeys are chosen in a pre-specified order. The key schedule is very simple: break the 256-bit key into eight 32-bit subkeys, and each subkey is used four times in the algorithm.
The S-boxes accept a four-bit input and produce a four-bit output. The S-box substitution in the round function consists of eight 4 × 4 S-boxes. The S-boxes are implementation-dependent - parties that want to secure their communicatons using GOST must be using the same S-boxes. For extra security, the S-boxes can be kept secret. In the original standard where GOST was specified, no S-boxes were given, but they were to be supplied somehow. This led to speculation that organizations the government wished to spy on were given weak S-boxes. One GOST chip manufacturer reported that he generated S-boxes himself using a pseudorandom number generator (Schneier, 1996).
Cryptanalysis of GOST
Compared to DES, GOST has a very simple round function. However, the designers of GOST attempted to offset the simplicity of the round function by specifying the algorithm with 32 rounds and secret S-boxes.Another concern is that the avalanche effect is slower to occur in GOST than in DES. This is because of GOST's lack of an expansion permutation in the round function, as well as its use of a rotation instead of a permutation. Again, this is offset by GOST's increased number of rounds.
There is not much published cryptanalysis of GOST, but a cursory glance says that it seems secure. The large number of rounds and secret S-boxes makes both linear and differential cryptanalysis difficult. Its avalanche effect may be slower to occur, but it can propagate over 32 rounds very effectively.
References
- Schneier, Bruce. Applied Cryptography, 2nd edition, 1996. ISBN 0471117099.
External links
Block ciphers |
Algorithms: 3-Way | AES | Blowfish | Camellia | CAST-128 | CAST-256 | CMEA | DEAL | DES | DES-X | FEAL | G-DES | GOST | IDEA | Iraqi | KASUMI | KHAZAD | Khufu and Khafre; | LOKI89/91 | LOKI97 | Lucifer | MacGuffin | Madryga | MAGENTA | MARS | MISTY1 | MMB | NewDES | RC2 | RC5 | RC6 | Red Pike; | S-1 | SAFER | Serpent | SHARK | Skipjack | Square | TEA | Triple DES; | Twofish | XTEA |
Design: Feistel network; | Key schedule; | Product cipher; | S-box | SPN Attacks: Brute force; | Linear / Differential cryptanalysis | Mod n; | XSL Standardisation: AES process; | CRYPTREC | NESSIE Misc: Avalanche effect | Block size; | IV | Key size; | Modes of operation; | Piling-up lemma; | Weak key; |