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

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.