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?

migrated from security.stackexchange.comFeb 26 '18 at 12:40

This question came from our site for information security professionals.

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, C) with distinct M chosen at random gives 24 bits of ciphertext. Two pairs give 2⋅24 = 48 bits, 56-48 = 8 bits are missing, and about 28 = 256 keys would match. Three pairs give 3⋅24 = 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 < 1/50000 ). 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, C) pair, because it is the actual K used to build the pairs (M, C).

It is feasible to intentionally exhibit three pairs (M, 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<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<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}$).

• I have a slightly different calculation. If the output of a particular permutation is pseudo random, then the probability of a collision is (1-2^-72), for 2^56 possible keys thus is (1-2^-72)^(2^56). I.e. I believe we need 4 to 5 M/C pairs. Could you show some maths? – Columbo Feb 27 '18 at 13:03
• Are you using "probability of a collision" for the probability $(1-2^{-72})$ that a tested key is not eliminated after testing 3 pairs? That's not a usual meaning of collision. Yes, $(1-2^{-72})^{(2^{56})}$ is relevant, and is about the probability that 3 pairs are enough to single out the true key. That probability is very close to one, thus 3 keys are most likely enough. – fgrieu Feb 27 '18 at 16:05
• Oh, somehow I must have typed in nonsense into my calculator before. :-) I meant the probability that a particular key agrees with K on all three inputs. – Columbo Feb 27 '18 at 16:07
• @Columbo: most calculators behave as if $(1-2^{-72})=1$ due to rounding error, and are thus unable to directly evaluate powers of $(1-2^{-72})$. An ounce of math is needed! – fgrieu Feb 27 '18 at 16:10
• I used Wolfram Alpha. It now produces the correct result; I meant I must have made a typo. – Columbo Feb 27 '18 at 16:11