3
$\begingroup$

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?
$\endgroup$
4
$\begingroup$

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}$$

$\endgroup$
  • $\begingroup$ @IImari Karonen could u please explain on the first part of your answer on how do you find a match, as I see it we will need to find a match between two sets of $2^{28}$ sizes, maybe to have a sorted structure but in that case the time complexity $n2^n$ $\endgroup$ – Mike.R Dec 12 '18 at 20:31
  • 1
    $\begingroup$ @Mike.R: A hash table would be the usual solution, offering (amortized) constant time insertion and lookup operations at the cost of a modest amount of memory overhead. For a more compact (but asymptotically slower) solution, you could simply collect all the "half-encrypted" blocks and their corresponding key halves in an array, sort the array (by the blocks, ignoring the key halves) and then use a binary search to try to look up each "half-decrypted" block in the sorted array. $\endgroup$ – Ilmari Karonen Dec 12 '18 at 20:43
  • $\begingroup$ Either way, $2^{28}$ insertions and lookups should be quite doable on any modern computer. $\endgroup$ – Ilmari Karonen Dec 12 '18 at 20:44
  • $\begingroup$ Thank a lot, @IImar Karonen u said in the third paragraph right halves has a $2^{28}/2^{64} = 1/2^{36}$ chance I can't understand what this chance stand for can u elaborate on it? $\endgroup$ – Mike.R Dec 12 '18 at 21:36
  • $\begingroup$ Take the ciphertext block and decrypt it with a random right half-key. The result will effectively be a random 64-bit block. There are $2^{64}$ possible values this block can have. We have a list of $N \approx 2^{28}$ blocks produced by encrypting the plaintext block with the $2^{28}$ left half-keys. Thus, the probability that the (essentially random) half-decrypted 64-bit block is on the list is $N$ out of $2^{64}$, or approximately $2^{28}/2^{64} = 1/2^{36}$ (where the "approximately" is due to the fact that $N$ might be slightly less than $2^{28}$ due to collisions). $\endgroup$ – Ilmari Karonen Dec 12 '18 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.