Meet-in-the-Middle & Time-Memory Trade-offs

MITM attacks split a cipher into two halves and attack them independently. The attacker builds a table from one end, then searches from the other end for a match. Reduces the attack complexity from O(2^{2n}) to O(2^n) at the cost of O(2^n) memory.

Double-DES applies DES twice: C = DES_{K2}(DES_{K1}(P)). Key space: 2^{112}. MITM attack: for all 2^{56} K1 values, compute DES_{K1}(P) and store. For all 2^{56} K2 values, compute DES_{K2}^{-1}(C) and look up in table. Match → (K1, K2) candidate. Only 2^{57} work total.