Linear cryptanalysis started to attract broad interest from the worldwide cryptologic community in 1994, when Mitsuru Matsui presented a method to break the data encryption standard (DES) cipher through what can be substantively defined as a known-plaintext attack [1]. Since then, the inner details of linear cryptanalysis--both their theoretical and practical aspects--have been studied and understood, thus achieving a significant degree of maturity, as documented by editors Junod and Canteaut in this new book.
The book starts with a survey of basic assumptions in linear cryptanalysis and their impact on the design of modern block ciphers. The general idea is to replace certain nonlinear parts of the cipher algorithm (for example, substitution boxes) with linear expressions of ciphertext, plaintext, and key bits. Clearly, the linear expression would not always be correct because of approximation errors, but by studying the results across many different plaintext and ciphertext pairs, the potential exists for determining the key bits involved. The discussion rests on the balance between practical and provable security, as well as on considerations regarding the performance of the cipher system. Increasing the block size and number of rounds could provide increased resilience against linear cryptanalysis attacks, at the price of increased latency and decreased efficiency.
The use of multiple linear approximations is further detailed in the second chapter, where Hermelin and Nyberg dissect a linear attack against the block cipher PRESENT, discuss multidimensional generalizations of Matsui’s algorithms, and assess their efficiency.
Regarding stream ciphers, Matsui’s work could potentially be applied to those cases in which block ciphers are used to deliver a streaming mode. There are, however, other ways of implementing stream ciphers, the main one being the simple XOR addition of two streams, where one is the plaintext and the other is the output of a keystream generator. Hell and Johansson cover linear attacks against stream ciphers in chapter 3. Whereas one important objective in the design of stream ciphers is to make them look as random as possible, one important class of attacks against stream ciphers relates to the analysis of the statistical deviation of the keystream under different values of the initialization vector (IV). Other methods include linear distinguishing attacks in which approximations are used to achieve a linear expression of the output that does not show a uniform distribution.
Chapter 4 offers a complementary point of view to the discovery of linear approximations of a cipher, which is based on the application of tools from error correction theory. The fifth and concluding chapter, by Daemen and Rijmen, presents a complete description of the Rijndael cipher (the base of the advanced encryption standard (AES)) as algebraic operations in a 256-bit finite field, aimed at the analytical quantification of its resistance against linear cryptanalysis.
In summary, this book is highly relevant to those who have an interest in looking under the hood of encryption systems. Linear cryptanalysis is not the only way in which systems can be attacked, but it is surely something worth considering when assessing the robustness of a given algorithm. Despite the complex subject matter, the book is accessible to a broad audience, from postgraduate students to researchers and practitioners, although a full understanding of the details requires a certain degree of familiarity with the underlying mathematics.
