[cryptography] GOST attack

Marsh Ray marsh at extendedsubset.com
Tue Jun 14 22:15:50 EDT 2011

On 06/14/2011 05:32 PM, Danilo Gligoroski wrote:
> 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.

Hmmm...there's more than proportional exponents going on here.

> 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.

For an ideal block cipher of N bit block size and some given key bits, 
we can think of it as a bijective function mapping values between the 
set of 2^N plaintexts and the 2^N set of ciphertexts, more or less a 
permutation. So we can think of the cipher as defining a mapping from 
the set of possible K-bit keys to the set of all such permutations. What 
can we say about this mapping based only on the cardinalities involved?

The key space contains 2^K elements, K = 256 in our examples, while the 
set of possible permutations is (2^N)! .

In the case of N = 4, there are 16! or about 2^44 possible ways to map 
plaintexts to ciphertexts. This number is much much smaller than 2^256, 
so if we are given the pairs defining the mapping explicitly, we are 
left with a large set of keys which map to this permutation. Assuming we 
have no further information to consider we cannot know which of these 
equally-valid keys was actually used. But note that this by itself does 
not rule out the possibility of us being able to enumerate these valid 
keys efficiently.

In the case of N = 64, there are (2^64)! possible permutations. I don't 
really know how to describe this number except to say that it's quite 
large and if we start expanding the factorial a bit
   2^64 * (2^64 - 1) * (2^64 - 2) * (2^64 - 3) * (2^64 - 4) * ... * 1
it's clearly much larger than 2^256.

Thus, assuming GOST is anything close to ideal in this respect, it only 
takes 5 plaintext-ciphertext pairs to uniquely identify a specific key 
with high probability.

But that's the limit of my math, actually finding such an inverse 
mapping is left as an exercise for the reader. If you can do it in less 
than 2^228 work, I hope you'll publish us a paper.

- Marsh

More information about the cryptography mailing list