DES Bruteforce attack and false positive keys

Question

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.

Answer 1

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.

Answer 2

There is more going on here than the block length vs keylength issue of DES.

A block cipher under a given key is a pseudorandom permutation of the form $$E_k:\{0,1\}^n \rightarrow \{0,1\}^n$$ where $n$ is the block length.

Consider two distinct keys, and assume the permutations $E_{k_i}$ they determine are random permutations. Then the permutation $$E_{k_2}^{-1}(E_{k_1}(\cdot))$$ is also random.

If the plaintext $x$ is mapped to the same ciphertext under these two keys then $$E_{k_1}(x)=E_{k_2}(x)$$ or $$E_{k_2}^{-1}(E_{k_1}(x))=x.$$ Therefore set of plaintext blocks fixed by this composite permutation is the set of blocks that are mapped to the same ciphertext block by the two original permutations and hence the two keys won't be distinguished by an attack that happens to use any of those blocks. How many such $x$ are there?

By the derangement problem of combinatorics, a random permutation has roughly a fraction $1/e$ of input points that it fixes. So this happens more often that you might expect.

PS: I am assuming this is not a question about false positives in, say, linear cryptanalysis which arise due to linear relations being used to search for the subkeys holding with a certain probability less than one.

Answer 3

The answer is hidden in the internal structure of DES. the Heart of DES is S-box. All internal DES operations are one-to-one mapping, except S-box which in turn, do many-to-one mapping from input to output, because it has 6-bits input and 4-bits output. that means different inputs will lead to the same output. this way some of the sub keys will generate same output for the same data (of course, I am talking for one internal Round). The average number of these subkeys is (2^48 / 2^32 = 2^16 subkeys. calculated from the input/output size of the S-BOXs). But, I still haven't a clear estimation for the number of false positive Main keys. Any ideas?