Why do DES's S-boxes look arbitrary, and what is differential cryptanalysis?

The S-boxes were deliberately chosen to resist differential cryptanalysis — an attack the designers already knew about roughly 15 years before it was publicly rediscovered, so the "random-looking" tables are actually carefully tuned.

Differential cryptanalysis is a chosen-plaintext attack: the analyst feeds in many pairs of plaintexts with a fixed difference and watches how that difference propagates to the ciphertext. If some input difference produces a particular output difference far more often than pure chance would allow, those statistics leak information about the key. Linear cryptanalysis is its cousin — it hunts for linear relations among plaintext, ciphertext, and key bits that hold slightly more often than 50% of the time. Both need huge numbers of pairs, which is exactly what strong confusion and the avalanche effect are meant to defeat.

Why this matters for DES:

• DES's eight S-boxes look like arbitrary lookup tables, which fuelled decades of suspicion that a backdoor was hidden inside them.
• When Biham and Shamir publicly described differential cryptanalysis around 1990, it emerged that DES's S-boxes were almost optimally chosen to resist it — IBM (with NSA input) had known the technique back in the 1970s and tuned the boxes against it.
• Generalised DES variants that swap in "nicer", more regular-looking S-boxes turn out to be markedly easier to break.

Lesson: in cipher design, "looks more complicated or more random" does not mean "more secure." Each S-box value was picked for a precise mathematical reason, not aesthetics.

Tip: Differential = chase plaintext differences; linear = chase linear bit-relations. A cipher resists both by making every output bit depend complexly on many input and key bits.

Go deeper:

• Differential cryptanalysis (Wikipedia) — the attack DES's S-boxes were secretly tuned to resist.