# Blockcipher: key space define permutations of blocks

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.

## 1 Answer

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.

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