Ebook: Advanced Linear Cryptanalysis of Block and Stream Ciphers

Linear cryptanalysis, whose original ideas can be traced back to the seminal works of Anne Tardy-Corfdir and Henri Gilbert, A Known Plaintext Attack of FEAL-4 and FEAL-6, presented at Crypto'91, as well as the now classical paper of Eurocrypt'93 by Mitsuru Matsui, Linear Cryptanalyis of DES Cipher, has quickly demonstrated to be one of the most efficient ways to break symmetrical cryptographic primitives.

Since its invention in the early 90s, several theoretical and practical aspects of this technique have been well studied, understood and generalized, resulting on the one hand in much more elaborated attacks against certain ciphers and on the other hand, in some negative results regarding the potential of various attempts of generalization.

We believe that the field is now sufficiently mature to take a snapshot of its current state and look at future potential developments. This volume aims at giving a recent state-of-the-art in the discipline, and to expose its latest developments. It consists of five parts:

- The first part, written by Baudoin Collard and François-Xavier Standaert, provides a thorough treatement and an experimental survey of the basic assumptions in linear cryptanalysis and their consequences for the design of modern block ciphers.

- The second part, written by Miia Hermelin and Kaisa Nyberg, is exposing a theory of multidimensional linear attacks on block ciphers.

- The third part, written by Martin Hell and Thomas Johansson, is a survey of how linear attacks can be applied on stream ciphers that gives an overview of the development of linear attacks as well as a theoretical explanation on how a linear attack on a stream cipher is typically launched today.

- The fourth part, written by Benoît Gérard and Jean-Pierre Tillich, details several interesting and useful links between linear cryptanalysis and coding theory.

- Finally, the fifth part, written by Joan Daemen and Vincent Rijmen, discusses how correlation analysis can be conducted at the level of elements of GF(2ⁿ) without having to deal with field representation issues.

We hope that the contents of this book will be useful and appreciated by anybody willing to dive into this fascinating, yet complex part of symmetrical cryptanalysis.

Finally, we would like to warmly thank many people: the authors of the five parts, for their high-quality contributions; Raphael C.-W. Phan, a coordinating editor of the Information for Cryptology and Information Security Series published by IOS Press, for having proposed us to edit a volume related to linear cryptanalysis; and Maarten Fröhlich, Carry Koolbergen and Maureen Twaig, from IOS Press, for their patience with respect to the numerous missed deadlines and the smooth publishing process.

Anne Canteaut (INRIA) and Pascal Junod (HEIG-VD), August 2011

Linear cryptanalysis is one of the most investigated attack against modern block ciphers. It has significantly influenced the design of symmetric encryption algorithms. However, because of the large cardinality of the problems they raise, security evaluations against these attacks frequently rely on a number of simplifying assumptions. In this chapter, we provide an experimental review of the basic hypotheses used in linear cryptanalysis, and take advantage of our experiments to discuss the practical and provable security approaches for designing secure ciphers.

In this article, the theory of multidimensional linear attacks on block ciphers is developed and the basic attack algorithms and their complexity estimates are presented. As an application, Cho's multidimensional linear distinguisher for the block cipher PRESENT is discussed in detail.

This paper is a survey of how linear attacks can be applied on stream ciphers. It gives an overview of the development of linear attacks and a short theoretical explanation on how a linear attack on a stream cipher is typically launched today. The main part of the paper is then a more detailed description of the application of linear attacks on three stream cipher designs, namely Grain, Pomaranch, and SNOW.

The main topics where coding theory can be useful for linear cryptanalysis are finding linear approximations of a cipher [6,7], recovering efficiently key bits from statistical data [1,9] and estimating the data complexity of a linear cryptanalysis [9]. We give an overview of such results here.

In this paper we provide a description of Rijndael using only algebraic operations in GF(2⁸). How the elements of GF(2⁸) are represented in bytes can be seen as a detail of the specification. In classical correlation analysis such as linear cryptanalysis, however, one works at the bit level and must assume a specific representation to study the propagation properties. We demonstrate how to conduct correlation analysis at the level of elements of GF(2ⁿ), without having to deal with representation issues. While this approach does not result in better bounds or stronger attacks, it allows to analytically address the resistance against linear cryptanalysis similar to what has been done for differential cryptanalysis in [3]. Further we show how linear functions over GF(2)ⁿ map one-to-one to linear functions over GF(2ⁿ) by the choice of a basis, and make the link with their mask propagation properties.