lect1  Lecture 15

Modern Methods of Cryptanalysis



We have seen:

1. Matsui's algorithm for search for the best linear approximation/differential pattern.

2. Final comments on Linear cryptanalysis:
a) Only 5 one-round approximations are used (A,B,C,D,E) from these
B and E are locally best used at first or last rounds only. A is Shamir's
approximation which is the best rounds approximation for the F-function. Note that all best approximations have only one active S-box per round.
Examples: 14-round approximation  -DCA-ACD-DCA-A
16-round approximation E-DCA-ACD-DCA-AB

This shows that LC is a very fragile attack, DES can be made immune to this attack by minor changes in permutations or S-boxes.

b) LC is easily convertible to ciphertext only attacks under plaintext redundancy assumption. For example assume that ASCII encoded English is encrypted and thus in each byte two most significant bits are fixed. Find Approximation that involves only these fixed plaintext.

c) Approximations for the same subsets of Plain and Cipher but with opposite
biases can compensate each other. Thus having found a good approximation one also has to check that no other "balancing" approximation exists.

d) As in differential cryptanalysis "piling up lemma" allows to multiply the round biases if rounds are independent. This since round subkeys are not-independent any bias estimation (as well as DC) has to be checked empirically. This is especially true for the case of several  active (adjacent) S-boxes per round.

2.Davies's attack on DES (1987)
a) We have seen an interesting linear approximation which does not depend on the input bits and thus leads to a two round iterative linear approximation:
X[3,4] + F(X,K) [0,10,20,25] = K[6,7]
X[3,4] + F(X,K) [5,11,27] = K[4,5]
lead to
F(X,K)[0,5,10,11,20,25,27] = K[4,5,6,7] which holds with probability 29/64

The effect is due to approximation of two expanded bits [3,4] once in S7 and once in S8. While similar equations can be written for all pairs of S-boxes S7 and S8 give the highest bias. The total probability of 16-round approximation is 1/2-1.07x 2^{-25}. This results in a known plaintext attack which uses 1.75x2^{52} known plaintexts for high success probability.

b) In 1987 Davies discovered that distribution of pairs of adjacent S-boxes is not uniform due to two common bits. For example if one fixes the input to S_i and lets S_{i+1} accept all 16 possible inputs (varying four rightmost bits of input to S_{i+1}) the output of S_{i+1} will not be uniform. One can easily compile a 16x16 distribution table for each value of the four key-bits (denote them by k1,k2,k3,k4) xored with the expanded bits. It is clear that distributions depend only on xors k1+k3 and k2+k4. Davies has shown however that there are not four but only two different distributions that depend only on parity k1+k2+k3+k4 (this is a consequence design criteria of the S-boxes: four permutations and two outmost bits decide which permutation to use).

The attack proceeds by observing that non-uniform outputs are xored in every odd (or even) rounds and thus can be observed by xoring plaintext and ciphertext bytes corresponding to the outputs of the pair of adjacent S-boxes. One can also
show that Davies's distribution for n rounds still depends only on the parity of all the keybits that cover the expanded bits in all the odd (or even rounds).

Thus given enough data we will be able to distinguish between distributions and thus find a parity bit of the key. While finding single parity bit of the key does not sound as a tremendous gain,  similarly to LC we can cover only 14 rounds of the cipher by our predictions and guess the key bits leading to the S-box pair of interest in the last (or first) rounds. This way one finds 13+13 bit of the key
(13 for odd and 13 for even rounds). The best deviation from the uniform distribution is given by S-boxes S7 and S8 (recall paragraph (a)). For 14 rounds 2^{49.7} known plaintexts are needed in order to distinguish this distribution from random with probability 97%. The attack runs with 2^{50} texts and time.
Note slight improvement over (a) due to wider path (8 bits instead of 1 bit).

3. Slide Attacks
We have seen definition of aslide attack, slid pair and attacks on Feistel ciphers with periodic keyschedule. Attack on autokey cipher (modified Blowfish).

Reading for the lecture

1. FIPS PUB: The Data Encryption Standard.

2. Adi Shamir, On the Security of DES, LNCS, proceedings of Crypto'85, 1985.

3. Mitsuru Matsui, Linear Cryptanalysis of DES Cipher (I),  1994.
Here is the handout1 from this paper (password as for HW3).

4. Mitsuru Matsui, On Correlation between the order of S-boxes and the strength of DES, proceedings of Eurocrypt'94, LNCS, Springer-Verlag, 1994.
Here is the handout2 from this paper (password as for HW3).

5. Eli Biham, Alex Biryukov,
   An Improvement of Davies' Attack on DES (.ps),
   CS 817, May 1994
   Proceedings of Eurocrypt'94, LNCS 950
   Journal of Cryptology, Vol. 10, No. 3, pp. 195-206, 1997.

6. Alex Biryukov, David Wagner,
    Slide Attacks, Proceedings of FSE'99, 1999.