GOST (block cipher)

GOST has a 64-bit block size and a key length of 256 bits. Its S-boxes can be secret, and they contain about 354 (log2(16!8)) bits of secret information, so the effective key size can be increased to 610 bits; however, a chosen-key attack can recover the contents of the S-boxes in approximately 232 encryptions. GOST is a Feistel network of 32 rounds. Its round function is very simple: add a 32-bit subkey modulo 232, 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 adjacent diagram, 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 first 24 rounds use the key words in order, and the last 8 rounds use them in reverse order. 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, thus parties that want to secure their communications 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. For example, the Central Bank of Russian Federation used the following S-boxes: However, the most recent revision of the standard, GOST R 34.12-2015, adds the missing S-box specification and defines it as follows. ==Cryptanalysis of GOST==

The latest cryptanalysis of GOST shows that it is secure in a theoretical sense. In practice, the data and memory complexity of the best published attacks has reached the level of practical, while the time complexity of even the best attack is still 2192 when 264 data is available. Since 2007, several attacks have been developed against reduced-round GOST implementations and/or weak keys. In 2011 several authors discovered more significant flaws in GOST, being able to attack the full 32-round GOST with arbitrary keys for the first time. It has even been called "a deeply flawed cipher" by Nicolas Courtois. and soon they were improved up to 2178 time complexity (at the cost of 270 memory and 264 data). In December 2012, Courtois, Gawinecki, and Song improved attacks on GOST by computing only 2101 GOST rounds. Isobe had already published a single key attack on the full GOST cipher, which Dinur, Dunkelman, and Shamir improved upon, reaching 2224 time complexity for 232 data and 236 memory, and 2192 time complexity for 264 data. Since the attacks reduce the expected strength from 2256 (key length) to around 2178, the cipher can be considered broken. However, this attack is not feasible in practice, as the number of tests to be performed 2178 is out of reach. Note that for any block cipher with block size of n bits, the maximum amount of plaintext that can be encrypted before rekeying must take place is 2n/2 blocks, due to the birthday paradox, and none of the aforementioned attacks require less than 232 data. ==GOST 2-128==

GOST 2-128 was released in 2016. It has exactly the same design but has twice as many S-tables and uses 64-bit integers instead of 32-bit integers. It no longer works on 64-bit blocks but on 128-bit blocks like AES. The two S-tables are those of the Central Bank of Russian Federation and that of the GOST R 34.12-2015 standard. GOST had 256-bit keys that were reused as subkeys. In GOST 2-128, subkeys are generated by a one-way hash function, representing 4096 bits. Thus, no weak keys exist and attacks against GOST do not work in GOST 2-128. ==See also==