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
_______________________________________________
cryptography mailing list
[email protected]
http://lists.randombit.net/mailman/listinfo/cryptography
