Linear Cryptanalysis
Kaisa Nyberg, Antonio Flórez-Gutiérrez · 2023
Linear cryptanalysis of block ciphers has its origins in stream cipher cryptanalysis. This chapter introduces an approach to linear cryptanalysis of iterative block ciphers, including tools such as the piling-up lemma and a statistical model for estimating the data requirement of a key-recovery attack. Together with differential cryptanalysis, linear cryptanalysis is today one of the main methods to evaluate the security of a block cipher. The Walsh-Hadamard transform has numerous applications in linear cryptanalysis. In order to recover some key bits, the sample correlations are compared to the correlations obtained in the offline analysis of the cipher. There are two basic types of key recovery methods: Matsui's Algorithm 1 and Matsui's Algorithm 2. The idea of using multiple linear approximations started with using several linear approximations involving the same key bits. The chapter describes the wrong-key and right-key probability distributions for some commonly used linear cryptanalysis statistics.