An $n$-bit block cipher is a keyed function $f_k:\{0,1\}^n\rightarrow\{0,1\}^n$. There are $2^n!$ such functions. Most block ciphers seem to have only $2^n$ keys, although there is an AES mode that has a 256 bits key for a 128 bit block. This doesn't cover all of the key space though: a 128-bit key is roughly enough to fully cover a 34-bit block cipher.

For key lengths longer than block lengths, there exist a plaintext $x$ and two keys $k_0,k_1$ such that $f_{k_0}(x)=f_{k_1}(x)$. This can be seen by applying the pidgeon hole principle. This is suggested to be dangerous, but I fail to see why.


I do not think that collisions are dangeous. If they would, most real world ciphers would not be secure. Here is the argument:

Even if the block size is 2 times the key size, you will get lots of collisions due to the birthday paradox.
A good cipher behaves for each fixed message like a random mapping on the key space.
Let's assume |key space|= $2^{64}$ and |message space| = $2^{128}$.
For each message $x_0$, the birthday paradox says that for $\sqrt {2^{128}} = 2^{64}$ randomly chosen values you get a collision probability above 0.5. This means that on average at least half of the messages lead to a collision. As you have $2^{128}$ different $x_0$, at least (on average) $2^{127}$ messages will give you such a collision.

  • $\begingroup$ Yes, there are "collisions" for certain messages, just like I say in my question. My question is why is this bad? $\endgroup$ Mar 21 '18 at 19:34
  • $\begingroup$ I have shown that any real world cipher has lots of collisions. Therefore the statement that this is bad is not true. $\endgroup$
    – user27950
    Mar 21 '18 at 19:36
  • $\begingroup$ Would you mind adding that to your answer? Because I couldn't make up whether collisions are bad or not from what you wrote. $\endgroup$ Mar 22 '18 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.