lect1  Lecture 13

Linear Cryptanalysis"



Notes after the lecture

We have finished differential cryptanalysis by showing the attack on full 16-round DES. The main idea is to use "first round trick" to gain two first rounds for free, by
using compact structures of 2^13 chosen plaintexts. Thus we can use a 12-round iterative charecteristic and a 2R attack. See Biham-Shamir's book/paper (referenced in previous lecture) for the details. The attack requres 2^47 chosen plaintexts and 2^37 steps of analysis. The key is found as soon as the first right pair is found and analyzed. The attack works even if the key is changed every
2^35 encryptions.

We started by showing Shamir's linear approximation of the S-boxes [2]. Then we proceeded to the Linear cryptanalysis [3].  We have seen maximal likelihood Algorithms I and II for finding parity bit of the key in a known plaintext attack.

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, On Matsui's Linear Cryptanalysis (.ps),
CS 813, April 1994, Proceedings of Eurocrypt'94, LNCS 950.