# Can you help me with this DES variant analysis?

I'm struggling with some DES variant that I got as an exercise (exercise taken from Katz-Lindell Ex5.14).

The variant is as follows:

The left half of the master key is used to derive all the sub-keys in rounds 1-8, while the right half of the master key is used to derive all the sub-keys in rounds 9-16.

My direction is to execute a meet-in-the-middle attack. We can observe that if we guess the 28 bit left-half of the master key we can completely compute $L_8$ and $R_8$, also, if we guess the 28 bit right-half of the master key we can completely compute $L_8$ and $R_8$ too, but now by the inverse direction. So we extensively guess all the possible keys for the right-half and for the left half which will take $O(2\cdot2^{28})$ time and space - since for each guess $L_k$ of left-half key we store $L_k:<L_8,R_8>$ computed by it and we store all those key-value pair in the set $S_L$, we do the same for the right-half guesses and store the values in set $S_R$. Of course the correct $L_k$ and $R_k$ will apply the same $<L_8,R_8>$.

My question

1. How many $L_k$ and $R_k$ would I find? How to analyse this?
2. How many plaintexts & ciphertexts pairs would I need to find the key with high probability? How to analyze this?
-

Each half of the key is 28 bits long, so there will be $2^{28}$ possible choices for each of them.

In the first part of your attack, you start with the known block of plaintext and encrypt it for the first 8 rounds using each possible left half of the key. This gives you $2^{28}$ "half-encrypted" 64-bit blocks. This is less than the birthday bound, so most likely the blocks will all be distinct, although there's a small chance (about 1 in $2^9$) of there being at least one collision. Still, for practical purposes, we can assume the number of distinct half-encrypted blocks to be close to $2^{28}$.

In the second part of your attack, you start with the known block of ciphertext, decrypt it for 8 rounds using each possible right half of the key, and look the resulting "half-decrypted" block up in the list of half-encrypted blocks compiled in the first part of the attack. Obviously, if the ciphertext is indeed the result of encrypting the corresponding plaintext with the modified DES algorithm you describe, there will be at least one match corresponding to the correct pair of half-keys.

As for the other half-keys, each of the $2^{28}$ right halves has a $2^{28}/2^{64} = 1/2^{36}$ chance of producing a half-decrypted block that, just by chance, matches one of the half-encrypted blocks computed in the first part. Since these probabilities are essentially independent, the total expected number of "false positive" matches is $2^{28} \times 1/2^{36} = 1/2^8$. By the law of rare events, the actual number of false positives is approximately Poisson-distributed, and, since the expected number is significantly less than one, the probability of there being at least one false positive is also approximately equal to the expected number.

Thus, with probability about $1 - 1/2^8$, just carrying out this meet-in-the-middle attack on one pair of known plaintext and ciphertext blocks will yield a single pair of half-keys corresponding to the correct key. If you do get unlucky and end up with multiple candidate keys, testing them on a second plaintext / ciphertext block will rule out each of the false ones with probability $1 - 1/2^{64}$.

Edit: (Copied and extended from comments below.) All of the analysis above is in the ideal cipher model, i.e. it assumes that each of the halves of your modified DES can be treated as if it were a family of random permutations (of the set of 64-bit blocks) indexed by the corresponding 28-bit half-key. Of course, neither DES nor your modified version of it are actually ideal ciphers, but, like any good block cipher, they're designed to generally look like one, so for basic statistical analysis like this, the ideal cipher approximation is usually good.

If the statistical behavior of your (half-)DES variant turned out to be significantly different from an ideal cipher when the attack was actually carried out, this would most likely imply a much more fundamental weakness in the cipher than the mere(!) vulnerability to meet-in-the-middle attacks (not that it isn't a devastating vulnerability in itself, given the already low key length). In particular, note that several of the various known deviations of DES from an ideal cipher, such as the complementation property, don't really apply here since we've fixed the input.

As for the $1/2^9$ collision rate, $2^{28}$ keys give $2^{28}(2^{28}-1)/2 \approx (2^{28})^2/2 = 2^{55}$ pairs of outputs. Each of these outputs has approximately a $1/2^{64}$ chance of colliding (assuming independence, which is of course not really true, but a reasonable approximation), giving an expected number of $2^{55}/2^{64} = 1/2^9$ collisions. Since this is much less than 1, by the law of rare events it also approximately equals the probability of there being at least one collision.

Another way of calculating the collision probability is to note that, in order to get no collisions among the $2^{28}$ half-encrypted blocks, each of them must evaluate to a distinct 64-bit value as we calculate them one by one. Thus, the exact probability of not getting a collision (under the ideal cipher assumption) is

\begin{aligned} & (1 - 0/2^{64})\cdot(1 - 1/2^{64})\cdot(1 - 2/2^{64})\dotsb(1 - (2^{28}-1)/2^{64}) \\ \approx& 1 - 0/2^{64} - 1/2^{64} - 2/2^{64} - \dots - (2^{28}-1)/2^{64} \\ =& 1 - (0 + 1 + 2 + \dots + (2^{28}-1)) / 2^{64} \\ =& 1 - (2^{28}(2^{28}-1) / 2) / 2^{64} \\ =& 1 - 1/2^9 + 1/2^{37} \\ \approx& 1 - 1/2^9 \end{aligned}

-