Preface

Christina BOURA1 and María NAYA-PLASENCIA2

1University of Paris-Saclay, UVSQ, CNRS, Versailles, France

2Inria, Paris, France

Symmetric-key cryptology is one of the two main branches of modern cryptology. It comprises all primitives, modes and constructions used to ensure the confidentiality, authenticity and integrity of communications by means of a single key shared between the two communicating parties. Hash functions and some other keyless constructions are equally considered as symmetric constructions because of the similarity in the design and analysis with classical keyed symmetric ciphers. Symmetric algorithms are essential for establishing secure communications, as they can have very compact implementations and achieve high speed in both software and hardware. Furthermore, compared to public-key algorithms, keys used in symmetric cryptography are short, typically of 128 or 256 bits only.

The goal of this two-volume project is to provide a thorough overview of the most important design, cryptanalysis and proof techniques for symmetric designs. The first volume is dedicated to the most popular design trends for symmetric primitives, modes and constructions, and to the presentation of the most important proof techniques. On the other hand, the current volume describes and analyzes some of the most well-established and powerful cryptanalysis techniques against symmetric constructions.

Cryptanalysis is an essential process for establishing trust toward the symmetric ciphers to be used and deployed. Indeed, in symmetric cryptography, it is common to provide security proofs for the modes of operation and high-level constructions. These security proofs, analyzed in Volume 1, are fundamental for having confidence in the high-level constructions themselves, but they often rely on unrealistic assumptions, for example, by considering the internal functions to be perfect random ones. Therefore, in order to trust the primitives, cryptanalysis is a necessary process to be taken into account together with the security proofs.

The first modern symmetric cryptanalysis techniques started developing almost together with the appearance of the first symmetric designs. These first cryptanalysis techniques have not stopped evolving since. Moreover, the appearance of new designs had as a consequence the development of new analysis techniques adapted to these new schemes.

The goal of this second volume is to present the most powerful and the most promising attacks among those that have emerged since the 1980s. The book is divided into two parts. The first part contains 15 chapters and gives an overview of the most important cryptanalysis techniques. The second part is composed of four chapters and investigates some future directions for the field of symmetric cryptology.

Chapter 1 is dedicated to differential cryptanalysis, the oldest and probably the most well-studied attack against block ciphers and related primitives. First, a general background for statistical attacks is provided and the notion of distinguisher is introduced. Then, the most important notions encountered in differential cryptanalysis are given. Some possible refinements and extensions of the basic attack are provided, notably the differential effect and truncated differential characteristics. Finally, the most prominent design approaches to achieve resistance against this class of attacks are given.

Together with differential cryptanalysis, linear cryptanalysis is without doubt the second most well-known analysis technique against block ciphers. This technique is described in Chapter 2. After a brief historical note, the main notions for this attack, notably those of correlation, linear hull and multidimensional linear approximations are presented. Then, two well-known algorithms for key recovery, namely Matsui's algorithms 1 and 2, are given. The problem of finding good linear approximations for a given cipher is analyzed next and some techniques to speed up key recovery are given. Finally, two extensions of classical linear cryptanalysis are provided: the use of multiple linear approximations and the technique of multidimensional linear cryptanalysis.

Impossible differential cryptanalysis is another powerful attack against block ciphers. The idea, explained in Chapter 3, is to exploit differentials of probability zero. The distinguishing part, consisting of finding good impossible differentials, is first analyzed. Techniques for the key recovery part are given next. In this part, closed formulas for estimating the complexity of an attack are given. Some improvements to the classical version of this cryptanalysis technique are provided at the end of this chapter.

Zero-correlation attacks are an extension of linear cryptanalysis. These attacks, presented in Chapter 4, are based on linear approximations with correlation exactly zero. First, this chapter presents the central notion of correlation matrices. The notions of linear trails and hulls are defined once again and some results on computing the correlations over a permutation are provided next. Then, this chapter analyzes how linear hulls with correlation zero can be used to mount an attack and techniques for reducing the data complexity are given. Finally, some important applications for Feistel ciphers and for the advanced encryption standard (AES) are discussed.

Chapter 5 is dedicated to differential-linear attacks. This cryptanalysis technique consists of successfully combining a differential attack together with a linear one. First, the attack framework is presented and ways to estimate correlations of a differential-linear distinguisher are given next. Then, the key recovery part is discussed and the notion of differential-linear connecting table (DLCT) is presented. At the end, three techniques to improve differential-linear attacks are discussed.

Boomerang attacks are statistical attacks against block ciphers based on differential cryptanalysis. Chapter 6 introduces this type of cryptanalysis and some of its refinements, namely, the amplified boomerang and rectangle attacks. A discussion on the probability computation of boomerangs is next given, and several ways to improve or formalize this computation are discussed. Finally, a recent tool to calculate the boomerang probability for a single S-box, called Boomerang connectivity table (BCT) is presented together with its Feistel variant, FBCT.

Chapter 7 gives an overview of another famous cryptanalysis technique called meet-in-the-middle cryptanalysis. Meet-in-the-middle attacks are among the oldest symmetric cryptanalysis techniques and still continue to evolve. This chapter starts by presenting the basic meet-in-the-middle framework together with a first complexity analysis. The most important techniques used in modern meet-in-the-middle cryptanalysis are given next, such as the partial or indirect matching, the sieve-in-the-middle or the slice-and-cut technique. Finally, a method called biclique, which permits extension of the number of rounds of a meet-in-the-middle attack, is presented.

Chapter 8 presents meet-in-the-middle Demirci-Selçuk attacks, an advanced form of meet-in-the-middle cryptanalysis, particularly successful on reduced versions of the AES. The chapter starts by presenting the basic form of this attack and discusses its application to the AES. Then, several refinements and techniques are given. A discussion of how to choose the best parameters for mounting such an attack is provided, and finally a series of tools for applying a meet-in-the-middle attack in an automated way are briefly presented.

Invariant attacks are a form of structural cryptanalysis against block ciphers and cryptographic permutations that showed to be particularly efficient against some lightweight cryptographic designs. Chapter 9 presents the most important concepts and ideas behind two important invariant attacks classes, the invariant subspace attacks and the nonlinear invariant attacks. Methods to detect potential vulnerabilities in cryptographic designs that could lead to the presence of invariants are discussed. Finally, design criteria to prevent attacks based on invariants are provided, and a link between invariant attacks and linear approximations is discussed.

Chapter 10 gives an overview of higher order differential and integral attacks as well as some of their most important variants. All these attacks exploit either some algebraic or some structural property of the underlying design, or sometimes both type of properties at the same time. The chapter starts by describing the notions of integrals and higher order derivatives. The notion of algebraic degree, essential for these attacks, and its properties for iterated permutations are presented next. A powerful tool, called the division property, that can be seen as a combination of integral and higher order differential cryptanalysis is given. Finally, attacks based on integrals are discussed.

Cube attacks and cube testers are additional methods of algebraic cryptanalysis that target designs with a relatively low number of nonlinear operations. Chapter 11 is dedicated to this class of attacks and summarizes the main ideas of these techniques. The classical cube attack that aims at recovering the secret key by analyzing the algebraic form of the cipher is described first. Then, a related distinguishing technique, called cube testers, is presented. Finally, conditional differential attacks and dynamic cube attacks, key recovery techniques related to cube attacks, are briefly given.

Chapter 12 describes correlation attacks against stream ciphers, one of...