GOST (block Cipher) - Cryptanalysis of GOST

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 (Schneier, 1996; Vitaly V. Shorin, Vadim V. Jelezniakov and Ernst M. Gabidulin, 2001). 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.

However, GOST is not fully defined by its standard: It does not specify the S-blocks (replacement tables). On the one hand, this can be additional secure information (in addition to key). On the other hand, the following problems arise:

• different algorithm implementations can use different replacement tables, and thus, can be incompatible to each other
• possibility of deliberate weak replacement table usage
• possibility (standard does not forbid it) to use replacement tables in which nodes are not commutation, that may lead to extreme security downfall

Despite its apparently strong construction, GOST is vulnerable to generic attacks based on its short (64-bit) block size, and should therefore never be used in contexts where more than 232 blocks could be encrypted with the same key.

Since 2007, several attacks were developed against GOST implementations with reduced number of rounds and/or keys with additional special properties.

In 2011 several authors discovered more significant flaws in GOST cipher, being able to attack full 32-round GOST with arbitrary keys for the first time. It has been even called "a deeply flawed cipher" by Nicolas Courtois. First attacks were able to reduce time complexity from to at the cost of huge memory requirements, and soon they were improved up to time complexity (at the cost of memory and data).

So far all attacks on full GOST remain strictly theoretical ("certificational weakness"), being extremely far from any practical attack. It's notable that the best known attack on GOST is far worse than best known attack (, also based on another weakness noted by Nicolas Courtois) on widely-used Advanced Encryption Standard.

GOST has been submitted to ISO standardization in 2010.