Strength of DES

Strength of DES

1. The Three Strength Questions

Stallings evaluates DES on: (a) key size — brute force? (b) analytical attacks — differential/linear (Topics 5–6)? (c) design choices — S-boxes, rounds, key schedule sound? Verdict: design excellent for its era; 56-bit key fatally short today; 8-round variants fall to analysis, full 16 rounds resisted both classical attacks in practice.

2. Key Size: The Fatal 56 Bits

$2^{56} \approx 7.2 \times 10^{16}$ keys; average search $2^{55}$:

Year	Machine	Time
1977 (Diffie–Hellman estimate)	$20M parallel engine (then-$)	~1 day (projected)
1998 EFF Deep Crack ($250k)	1,536 custom chips, 90B keys/s	56 hours (with distributed.net)
2006 COPACOBANA (~$10k FPGA)	reconfigurable cluster	~6 days
Today	Cloud GPUs / ASIC farms	hours or less

Worked estimate: $10^{11}$ keys/s (modern rig): $2^{55}/10^{11} \approx 3.6 \times 10^5$ s $\approx 4$ days single rig; parallelize ×100 → ~1 hour. Lesson: security margin must outlive hardware — DES's 56 bits (minus 8 parity!) lasted ~20 years; AES mandates ≥128.

3. Nature of DES Design Criticisms

• Short key: NSA allegedly cut Lucifer's 112 → 56 bits; Diffie–Hellman warned publicly in 1977.
• S-box secrecy: design criteria classified until 1990s → suspicion of backdoor; Coppersmith later revealed criteria (no output close to linear function, Avalanche) — S-boxes actually hardened against differential cryptanalysis (unknown publicly then!).
• Complement + weak keys: 4 weak + 6 semi-weak pairs of $2^{56}$ — negligible operationally (reject all-equal halves), 1-bit complement saving irrelevant vs $2^{55}$.
• 64-bit block: Sweet32 birthday collisions after $\approx 2^{32}$ blocks ($\approx 32$ GB) — kills DES/3DES in TLS (CVE-2016-2183).

4. Analytical Attacks vs Full DES (Bridge to Topics 5–6)

• Differential (Biham–Shamir): 15-round DES needs $2^{47}$ chosen plaintexts; full 16 needs $2^{47}$–$2^{55}$ — worse than brute force's $2^{55}$ time but absurd data. DES resists in practice.
• Linear (Matsui): $2^{43}$ known plaintexts for full DES — demonstrated experimentally (50 days compute, 1994) but impractical data-wise.
• Reduced-round DES (≤8 rounds) falls fast — proof that 16 rounds was the right margin; AES kept the philosophy (10–14 rounds + margin analysis).

Exam Points

• Timeline table (1977 projection → 1998 EFF 56 h → today) — 5-mark theory core.
• $2^{55}$ average + worked rig estimate — favourite numerical.
• S-box controversy's ironic twist (secretly differential-resistant) — 2-mark story.
• 16-round margin vs ≤8-round breaks; block-size Sweet32 footnote.