Multiple Encryption

Multiple Encryption

1. Why Encrypt Twice? (Motivation from DES's Death)

DES's 56-bit key fell to brute force ($2^{55}$ average, EFF 56 hours), but DES hardware was everywhere — replacing it overnight was impossible. Multiple encryption reuses the DES circuit 2–3 times with independent keys to stretch effective strength without new hardware. Question: does $E_{K2}(E_{K1}(P))$ double security to $2^{112}$? Answer: NO for double (meet-in-the-middle), YES-ish for triple (Topic 4).

2. Double Encryption and Meet-in-the-Middle (Worked Attack)

Attacker with one known $(P, C)$: compute $E_{K}(P)$ for all $2^{56}$ $K$ (table A), compute $D_{K}(C)$ for all $2^{56}$ $K$ (table B), match $X$ values — each match is a candidate $(K_1, K_2)$ (false positives filtered with a second pair). Cost: $2^{56} + 2^{56} = 2^{57}$ encryptions + $2^{56}$ storage — barely more than single DES's $2^{55}$! Effective strength $\approx 2^{57}$, NOT $2^{112}$.

Worked numbers: single DES brute force $2^{55}$ avg; double-DES MITM $2^{57}$ worst-case time + $2^{56}$ blocks memory ($\approx 10^{18}$ bytes — infeasible storage in 1998, feasible-ish for agencies today, but time gain nil). Lesson: naive key-length addition fails against MITM; storage–time tradeoff kills double encryption.

3. Design Rules Multiple Encryption Teaches

• Encrypt-decrypt-encrypt (EDE): $C = E_{K3}(D_{K2}(E_{K1}(P)))$ with $K_1 = K_2$ collapsing to single DES (backward compatibility with legacy single-DES boxes) — the Triple-DES trick (Topic 4).
• Independent keys required: same key twice ($K_1 = K_2$) gains nothing; related keys invite related-key attacks.
• More stages ≠ proportional gain: security grows only if the construction defeats MITM (odd stages: 3DES $\approx 2^{112}$ vs MITM $2^{112}$ with $2^{56}$ data — genuine gain).
• Modern answer: just use AES-128 ($2^{128}$, one pass) instead of stacking broken ciphers — multiple encryption was a migration bridge, not a design goal.

Exam Points

• MITM equation $D_{K2}(C) = E_{K1}(P)$ + $2^{57}$ time / $2^{56}$ memory numbers — 5-mark numerical core.
• "Double DES ≈ single DES strength" conclusion with storage-time reasoning.
• EDE backward-compatibility logic (bridge to Triple DES).
• Modern lesson: AES replaces stacking.