The weakness of double DES, E (k1, E(k2, M)) is that Meet-in-the-middle attack is possible. When performing Meet-in-the-middle attack, we first need to build the table with the first column all the possible keys and the second column all the encryption with these keys, then second step is sorting the second column, why do we need to sort the second column? What do we base on when performing the sorting?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
That's an optimization for the attack. It would work without it, but slower.
To do a Meet-in-the-middle attack, we need to encrypt a known plaintext with every possible key and save the resulting text (with the used key) in a list. Now we decrypt a known ciphertext with every possible key and look if we got the resulting text in our list.
We want to know the key for a specific ciphertext. Searching for a specific value in an unordered list is quite hard: We need to look at every single entry and see if it is what we search. That takes (on average) $\frac{n}{2}$ attempts (with $n$ = the key space of the algorithm, for DES it is $2^{56}$).
If we sort the resulting list before we do the decryption we can use the Binary Search. This reduces the search attempts to ca. $\log_2(n)$ (n = the keyspace). That's only 56 for DES, much less than with an unsorted list.
Small note: We sort the column with the key at the same time as we sort the column with the ciphertext. For example, the first key will be the key for the first ciphertext.
-
$\begingroup$ Small note: In practice, you probably wouldn't use a binary search, but rather you'd sort both sets and run a list merge on them. In any case, though, you still end up doing about $O(n \log n)$ comparisons; without sorting, that would be $O(n^2)$, which is no more efficient than brute force. $\endgroup$ Nov 16, 2014 at 20:11
-
$\begingroup$ @IlmariKaronen: Minor note: we can do rather better than $O(n \log n)$ comparisons (!); the data we're sorting on is uniformly distributed, and for data like that, approaches such as radix sorting have better asymptotic complexity. $\endgroup$– ponchoNov 16, 2014 at 20:33
-
$\begingroup$ @IlmariKaronen: I don't know how that works, so I can't insert it into my answer. Feel free to edit it, if you want. $\endgroup$– NovaNov 16, 2014 at 20:55