Why does Double-DES (2DES) provide almost no additional security over single DES, despite having a 112-bit key?
The meet-in-the-middle attack breaks 2DES with roughly $2^{57}$ operations and $2^{56}$ storage — barely more than breaking single DES ($2^{56}$). Double encryption only adds about 1 bit of security!
* Meet-in-the-middle: encrypt forward from M, decrypt back from C, and match in the middle — ≈2⁵⁷ work, not 2¹¹². *
How 2DES works:
- Encrypt: $C = E_{K_2}(E_{K_1}(M))$ — encrypt twice with two different 56-bit DES keys
- Key space: $K_1 \| K_2$ = 112 bits → brute force should need $2^{112} \approx 5 \times 10^{33}$ operations
The meet-in-the-middle attack:
- From the left: Encrypt the known plaintext $M$ with all $2^{56}$ possible keys $K_1$ → store all intermediate values
- From the right: Decrypt the known ciphertext $C$ with all $2^{56}$ possible keys $K_2$
- When an intermediate value from step 1 matches one from step 2 → you found $(K_1, K_2)$
Total cost: $2 \times 2^{56} = 2^{57}$ encryptions + $2^{56}$ stored entries
The devastating conclusion: 2DES with a 112-bit key is only marginally harder to break than single DES with a 56-bit key. Double encryption does not double the security — it barely increases it at all.
Go deeper:
Meet-in-the-middle attack (Wikipedia) — the attack that sinks double encryption.- Data Encryption Standard (Wikipedia) — DES, its 56-bit key, and why doubling it disappointed.