Linear & Differential

History

Eli Biham and Adi Shamir described differential cryptanalysis in 1990, following how chosen differences between pairs of plaintexts pass through the S-boxes of DES-like ciphers. Mitsuru Matsui described linear cryptanalysis in 1993, and in 1994 recovered a full 16-round DES key from 2^43 known plaintexts. In 2001 Howard Heys of Memorial University of Newfoundland wrote a tutorial teaching both on a cipher small enough to follow by hand, a 16-bit substitution–permutation network whose S-box is the first row of DES’s first S-box; Cryptologia printed it in 2002.

How it works

Four rounds mix in a subkey, pass each four bits through the S-box and permute the sixteen bits, the last round without the permutation and a fifth subkey after it. The linear approximation table counts, for every sum of input bits and sum of output bits, how far the S-box departs from agreeing half the time. Heys chains four such approximations through three rounds; the piling-up lemma gives the chained equation a bias of −1/32. For each of the 256 guesses at eight bits of the last subkey the ciphertexts are run back through two S-boxes and the equation counted over the known plaintexts: the right guess shows the bias, the others little. The differential attack uses pairs of plaintexts differing by 0B00 and a characteristic that carries the difference through three rounds with probability 27/1024, counting for each guess the pairs that end as it predicts.

How it was checked

The linear approximation and difference distribution tables, computed from the S-box, agree with Heys’s Tables 4 and 7 in every cell, and the S-box with the first row of S1 in FIPS 46-3. His Table 6 is misprinted in four cells of one column; his errata page gives the column computed here. The trail’s −1/32 and the characteristic’s 27/1024 come out of the tables. Seeded runs are pinned in the tests: from 10,000 known plaintexts the true bits came first under 79 of 100 random keys, from 5,000 chosen pairs under all 100.

Limits

Heys publishes neither his subkeys nor his plaintexts, so his Tables 5 and 8 cannot be reproduced, only matched in kind; every run here differs with its seed. The piling-up lemma treats the four approximations as independent, which his errata note they are not quite. DES itself, with its six-bit S-boxes and sixteen rounds, is not attacked here.