Cracking truncated DES Let's say we have a scheme in which 40 bits M are padded with 24 zeroes, encrypted using a secret DES key K, and the result truncated to the first 24 bits, C. If I wanted to determine a key that behaved identically to K, i.e. for each (or at least the majority of) M produced the same C, how many pairs of M/C would I require to find such a key with reasonable chance?
In symmetric cryptography, for fully known ciphertext, one is expected to need slightly more known plaintext bits than usefull key bits in order to reliably recover the key by pure brute force. That rule also works if we reverse plaintext and ciphertext, and that's what we want here.

The key is 56 bits. Each pair (M,&thinsp;C) with distinct M chosen at random gives 24 bits of ciphertext. Two pairs give 2⋅24&thinsp;=&thinsp;48 bits, 56-48&thinsp;=&thinsp;8 bits are missing, and about 28&thinsp;=&thinsp;256 keys would match. Three pairs give 3⋅24&thinsp;=&thinsp;72 bits and that is enough for brute force key search to pinpoint a single key with excellent probability (in the order of 256-72&thinsp;&lt;&thinsp;1/50000&thinsp;). Most likely the first key found (after an expected 255 keys have been tested, and marginally more trial encryptions) will "behave like K" for any other (M,&thinsp;C) pair, because it is the actual K used to build the pairs (M,&thinsp;C).

It is feasible to intentionally exhibit three pairs (M,&thinsp;C) (perhaps more) with distinct M such that at least two keys are possible; but again this is unlikely to happen by chance.



It is asked the math. Let $(M_i,C_i)$ be the given plaintext/ciphertext pairs (40+24 bits each), with distinct $M_i$, corresponding to an unknown actual key $K_A$. Let $C_{(K,i)}$ be the result of expanding $M_i$, enciphering under key $K$, and truncating to 24-bit. By that definition, $C_{(K_A,i)}=C_i$.

Because the $2^{56}$ DES keys only cover a small fraction of the $2^{64}!$ permutations of the DES block, and in that application at least one bit in the input is fixed (thus making irrelevant the DES complementation property that $E(\overline K,\overline P)=\overline{E(K,P)}$ ), and we'll have few plaintexts (or/and can observe only a small fraction of the bits of an output block), we can model the $C_{(K,i)}$ for each $(K,i)$ as uniformly random and independent 24-bit bitstrings. That's true including for $K=K_A$, under the assumption that the $M_i$ have been chosen independently of $K_A$.

Under that model, a key $K\ne K_A$ is such that $C_{(K,i)}=C_i$ for $n$ plaintext/ciphertext pairs with probability $2^{-24n}$ (that probability is halved for each ciphertext bit). It follows that with $n$ pairs, each $K$ can be eliminated with probability $1-2^{-24n}$. After testing all $2^{56}$ keys, $K_A$ remains the only possible key with probability $p_n=(1-2^{-24n})^{(2^{56}-1)}$ and there remains more than one possible key with probability $\overline{p_n}=1-(1-2^{-24n})^{(2^{56}-1)}$.

For $n\ge3$, we use that $1&lt;c\ll1/|\epsilon|\implies1-(1-\epsilon)^c\approx\epsilon\cdot c$ to get $\overline{p_n}\approx2^{56-24\cdot n}$. Thus $\overline{p_3}\approx2^{-16}$, which is very small (meaning 3 pairs will do with excellent odds).

For $n\le2$, we use that $\log p_n=(2^{56}-1)\log(1-2^{-24n})$, and $|\epsilon|\ll1\implies\log(1+\epsilon)\approx\epsilon$ to get that $p_n\approx e^{(-2^{56-24n})}=2^{-(56-24n)/\log2}$. Thus $p_2&lt;2^{-369}$ which is ludicrously small (meaning 2 pairs won't do). The most probable is that many keys will remain possible (in the order of $2^{56-24n}$).