[cryptography] GOST attack

Danilo Gligoroski danilo.gligoroski at gmail.com
Tue Jun 14 18:32:02 EDT 2011

To extract the essence of both Klimov's and Aumasson's posts about this 
attack from the codebook point of view (where I completely agree):

Alexander Klimov <alserkli at inbox.ru> wrote:
> Since GOST has a 64-bit block size, it means that the attacker starts
> with the full map of (plaintext, ciphertext) pairs. In a sane system
> the key is either random or a result of KDF -- what can be the point
> of such an attack?

Jean-Philippe Aumasson wrote:
> AFAIU this attack indeed needs store all 2^64 plaintext/ciphertext
> pairs, and needs 2^228 computations. This makes it less interesting
> than a generic codebook attack, which only needs the former 2^64
> storage.

To illustrate the futility of this attack here is an extreme example 
with a baby-block, giant-key block cipher:

Let we have a 4-bit block cipher with 256-bit keys. 
Give to the attacker all 2^4=16 pairs of (Plaintext, Ciphertext) 
i.e. give him the secret permutation of 16 elements that is our 
4-bit block cipher with 256-bit key.
Although mathematically is not equivalent as knowing the secret key, 
(in this case many different key values will give the same block cipher),
for all cryptographic purposes (encryption, decryption, any mode of
producing MACs, ...) his knowledge of the full codebook will reproduce 
the same results as knowing one secret key.

Now, 64-bit blocks are much bigger than 4-bit blocks, (and the secret key 
is still 256 bits i.e. much larger than the block size), but the principles 
of the codebook attack are the same.

Thus the task of reproducing the secret key by knowing the full codebook 
of 2^64 pairs of (Plaintext, Ciphertext) after 2^228 computations is futile.


More information about the cryptography mailing list