Is there any point in making block size less than key size in block cipher? For example, Russian GOST symmetric cipher uses 256-bit keys to encrypt 64-bit blocks. That means there are many keys which give the same result, so why making keys so large?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ I've answered, but I could also live with closing the question as a dupe for the AES / Rijndael specific questions. I'll leave that up to the rest of the crypto crowd. $\endgroup$– Maarten Bodewes ♦Commented Apr 9, 2016 at 20:34
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
GOST symmetric cipher uses 256-bit keys to encrypt 64-bit blocks. That means there are many keys which give the same result
This is actually incorrect. A block cipher, when given a key, maps $n$-bit plaintext blocks to $n$-bit ciphertext blocks (and vice versa for decryption). Here's a toy example for $n=2$:
$E_k(00) = 01 \\ E_k(01) = 10 \\ E_k(10) = 00 \\ E_k(11) = 11$
Although there are $2^n$ possible plaintext blocks and $2^n$ possible ciphertext blocks, there are actually $2^n!$ different possible ways to map plaintext blocks to ciphertext blocks. In this toy example, there are actually $2^2! = 4! = 1\times2\times3\times4 = 24$ different ways of mapping each two-bit input to a unique two-bit output.
Back to your question, GOST uses 256-bit keys, meaning that there are $2^{256}$ possible keys. However, with a 64-bit block size, there are $2^{64}!$ different possible permutations, and $2^{64}!$ is much larger than $2^{256}$.
answered Apr 9, 2016 at 20:33
-
$\begingroup$ Shouldn't some of those 2^64! be same?? $\endgroup$ Commented Feb 21, 2018 at 6:23
$\begingroup$
$\endgroup$
This is because the set of possible permutations of 64 bit blocks of plaintext ($2^{64}$ possibilities) to 64 blocks of ciphertext is very high. A key selections just one of these permutations. Even a 256 bit key space is smaller by far than the number of possible permutations.
Some plaintext blocks will likely map to the same ciphertext block for a few of these permutations. But the permutation itself that gets selected by the key is still very likely to be unique, and it is very improbable that you find the matching pairs in the first place.
So your statement "...that means there are many keys which give the same result" is not correct. The result of the key is a specific permutation, and there are plenty of permutations to divide over the keys.
Also see this question as well as this question which explain this for AES/Rijndael specifically.
answered Apr 9, 2016 at 20:31