DES Bruteforce attack and false positive keys I have read that a bruteforce attack (regardless on which block cipher is used) can lead to a false positive if key space is greater than blocks space.
It is pretty clear to me that is due the pigeons hole principle (if I have more keys than available blocks, sooner or later I will use two different keys for the same mapping).

My question is, how can DES exhibit such behavior if the key space is about $2^{56}$ and block space is $2^{64}$.

What I am expecting from those premises is that given a plaintext and all possible keys, not all possible ciphertexts will be addressed.
My question is, how can DES exhibit such behaviour if the key space is about $2^{56}$ and block space is $2^{64}$


Let us assume that the attacker has a single plaintext/ciphertext pair, that is, two eight byte values $P, C$ with $C = \text{DES}_k(P)$, where $k$ is the correct unknown key.

Then, let us consider the values $\text{DES}_{k'}(P)$; there $k'$ ranges over the $2^{56}-1$ possible incorrect keys.  If we model DES with the incorrect key as a random permutation, then what we get is a list of $2^{56}-1$ random 8 byte values, each one of which has a $2^{-64}$ probability of just happening to be $C$.

Hence, the expected number of times the value $C$ appears on that list is $(2^{56}-1)2^{-64} \approx 2^{-8}$ (and the probability that the value $C$ appears at least once on the list is a tad smaller).

Hence, there does indeed exist a nontrivial probability that a brute force search would find two keys; the correct key $k$, and another key $k'$ that just happens to map $P$ to $C$.

Of course, in practice, we never really get only one plaintext block and one ciphertext block; we generally get additional ciphertext blocks that, at the very least, attempt to decrypt, and see if they make sense; that'll allow us to distinguish the correct key from any incorrect ones.