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.

Step 1: encrypt plaintext P with all possible K1 → table T[DES_{K1}(P)] = K1. Step 2: for each K2, decrypt ciphertext C: v = DES^{-1}_{K2}(C). Check if v ∈ T. If T[v] = K1 exists, verify (K1, K2) on a second plaintext-ciphertext pair. Expected 1-2 false matches; discard them.

Triple-DES (3DES) uses three keys K1,K2,K3: C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P))). MITM still applies but more weakly: two-key 3DES (K3=K1) reduces to 2^{112} work. Three-key 3DES: 2^{112} MITM attack exists, explaining why 3DES provides only ~112 bits of effective security despite 168-bit key.

Hellman (1980): precompute a table of (start_point, end_point) chains to speed up offline key search. Given a target hash/ciphertext, search the Hellman table for a chain containing it. Trade-off: P = N (time × memory = space constant). The basis for rainbow tables.

Rainbow tables (Oechslin, 2003) improve Hellman tables by using different reduction functions at each chain position, eliminating false alarms (merged chains). Efficient for cracking unsalted password hashes. A lookup takes O(table_size/chain_length) time.

A salt is a random value prepended to the password before hashing: H(salt||password). Different salts produce different hashes for the same password — a rainbow table for "password" is useless if a different salt was used. Salts must be stored alongside the hash.

MITM attacks on AES-128 (10 rounds): known attacks split at round 5 — encrypt forward 5 rounds, decrypt backward 5 rounds, meet in the middle. Best known: biclique attack reduces 2^{128} to 2^{126.1} — not practical, but shows AES has no security margin against MITM-style approaches.

For Merkle-Damgard hashes, MITM can find preimages faster than brute force on some constructions. Attack: build table from message blocks starting from IV; search backward from target hash. Against SHA-256 with full rounds: still ~2^{255} — no improvement over brute force.

Dissection attack generalizes MITM to r-way splits. For a 3-way split of a cipher: encrypt forward 1/3 of rounds, meet in the middle of the chain, then decrypt backward 1/3. Requires O(2^{n*2/3}) time and O(2^{n/3}) memory — more balanced trade-off.

In protocols, MITM attacks can be prevented by: using long KDF-derived keys from high-entropy passwords (reduces key space that can be enumerated), using hardware tokens (FIDO2) where the key never leaves the device, or using public-key authentication (no shared secret to enumerate).

What is the effective security of Double-DES (2x DES, 112-bit combined key) against a MITM attack?

MITM attacks split ciphers into halves, reducing time from 2^{2n} to 2^n with 2^n memory. Breaks Double-DES; 3DES mitigated but has 112-bit effective security. Rainbow tables use MITM logic for password cracking — defeated by salting. Next: timing attacks and side-channel attacks.