In the meet-in-the-middle attack, if we built the tables first and then looked for matches, we would have another high complexity problem. For each of the table 1 entries, compare with all the table 2 entries; this algorithm has complexity of O(2^2k). How the matching could be done while building the tables, resulting in the total complexity remaining at O(2k+1)?

  • 2
    $\begingroup$ Dictionary (aka hash tables) search complexity is about O(1). $\endgroup$ – kludg Sep 14 '16 at 4:40

Let $(K,K')$ be the key and let $C=E_{K'}(E_K(P))$.

Generate $$L=[(E_K(P),K):K \in \{0,1\}^k]$$ sorted in a hash table on first coordinate with time complexity $O(2^k).$ You can take a hash table of size a few times $2^k$ to avoid long chains by avoiding too many collisions in the table. Or sort the list at cost $O(k2^k)=\tilde{O}(2^k).$

Now try all $K'\in \{0,1\}^k$ and compute $D_{K'}(C)$ and lookup in the table at constant time, until you get a match. Check a few other plaintext ciphertext pairs to ensure the match is not spurious since the permutation $$u\rightarrow E_{K'}(E_K(u))$$ will typically have some fixed points, which may include $u=P.$ This gives overall time complexity $O(2^k)$ if you choose hash sorting.


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.