Also known as: differential cryptanalysis

Differential cryptanalysis examines how a fixed difference between two plaintexts propagates through a cipher to a difference between their ciphertexts.¹ Because the absolute values cancel, the propagation isolates the cipher’s nonlinear behavior; non-uniform (“biased”) propagation leaks structure and, ultimately, key bits. It was introduced publicly by Eli Biham and Adi Shamir around 1990.

Holding everything fixed but one difference makes the output difference depend only on how the cipher treats that change.

How it works

The analyst collects pairs that differ in exactly one position — adjacent lengths, a single changed character, or a one-bit flip — and tabulates the resulting output differences. If a particular input difference maps to a particular output difference far more often than chance, that “differential characteristic” constrains the internal transform and can be propagated to recover round keys or table entries. The core object is the S-box’s difference distribution table: for each input difference it counts how the output differences spread, and any entry much larger than the average is a foothold. It is most powerful in the chosen-plaintext setting, where the analyst can manufacture the exact pairs needed, but useful minimal pairs sometimes occur in a passive known-plaintext corpus.

Variants

The closely related linear cryptanalysis (Matsui, 1993) works with linear approximations — probabilistic XOR relations among plaintext, ciphertext, and key bits — rather than differences, and the two are the classic pair of statistical attacks on block ciphers.² Later generalisations include truncated differentials (tracking only part of the difference), higher-order differentials (differences of differences), and impossible differentials (exploiting a difference that can never occur to rule out keys). All share the same premise: a well-designed cipher should make every output difference equally likely, so any measurable bias is a defect.

In practice

Differential cryptanalysis reshaped cipher design. It later emerged that IBM and the NSA had tuned the DES S-boxes in the 1970s specifically to resist it — years before Biham and Shamir published the technique openly — which is why DES held up far better against it than a random S-box choice would have. Modern designs now quote their maximum differential probability as an explicit security margin, and choosing S-boxes with a flat difference distribution table is a standard part of the design process. A cipher that skips this analysis, or hides its S-boxes rather than publishing them, may carry an exploitable differential that review would have caught.

Relevance to SDR

Naturally occurring minimal pairs help reverse-engineer an obfuscation. In GopherTrunk’s clean-room analysis of the Motorola P25 talker-alias scheme (issue #773), same-length aliases that shared a prefix but differed later showed that one character change perturbs all downstream ciphertext — direct evidence the encoder carries feedback state — and the same alias seen under two radio IDs, differing only in a trailing CRC, exposed the framing.

Sources

1. Differential cryptanalysis — Wikipedia, for input/output differences and the Biham–Shamir origin. ↩

2. Linear cryptanalysis — Wikipedia, for the complementary statistical attack using linear approximations. ↩

See also

• Chosen-plaintext attack
• Known-plaintext attack
• Algebraic attack
• Brute-force attack (exhaustive key search)
• TETRA TEA ciphers