A tutorial on linear and differential cryptanalysis

Cryptologia, Jul 2002 by Heys, Howard M

ABSTRACT: In this paper, we present a detailed tutorial on linear cryptanalysis and differential cryptanalysis, the two most significant attacks applicable to symmetric-key block ciphers. The intent of the paper is to present a lucid explanation of the attacks, detailing the practical application of the attacks to a cipher in a simple, conceptually revealing manner for the novice cryptanalyst. The tutorial is based on the analysis of a simple, yet realistically structured, basic Substitution-Permutation Network cipher. Understanding the attacks as they apply to this structure is useful, as the Rijndael cipher, recently selected for the Advanced Encryption Standard (AES), has been derived from the basic SPN architecture. As well, experimental data from the attacks is presented as confirmation of the applicability of the concepts as outlined.

KEYWORDS: Symmetric-key cryptography, block ciphers, substitution-permutation networks, linear cryptanalysis, differential cryptanalysis.

1 INTRODUCTION

In this paper, we present a tutorial on two powerful cryptanalysis techniques applied to symmetric-key block ciphers: linear cryptanalysis [16] and differential cryptanalysis [1]. Linear cryptanalysis was introduced by Matsui at EUROCRYPT '93 as a theoretical attack on the Data Encryption Standard (DES) [19] and later successfully used in the practical cryptanalysis of DES [17]; differential cryptanalysis was first presented by Biham and Shamir at CRYPTO '90 to attack DES and eventually the details of the attack were packaged as a book [2]. Although the early target of both attacks was DES, the wide applicability of both attacks to numerous other block ciphers has solidified the preeminence of both cryptanalysis techniques in the consideration of the security of all block ciphers. For example, many of the candidates submitted for the recent Advanced Encryption Standard process undertaken by the National Institute of Standards and Technology [20] were designed using techniques specifically targeted at thwarting linear and differential cryptanalysis. This is evident, for example, in the Rijndael cipher [6], the encryption algorithm selected to be the new standard. The concepts discussed in this paper could be used to form an initial understanding required to comprehend the design principles and security analysis of the Rijndael cipher, as well as many other ciphers proposed in recent years.

The paper is structured as a tutorial and, as such, is intended to not be rigorously mathematical. It introduces the basic concepts of linear and differential cryptanalysis but is by no means a definitive source for understanding all the many refinements and improvements of the attacks over the years. The basic purpose of the paper is to use a simple (yet somewhat realistic) cipher structure to study the most basic concepts of the two attacks. Other more formal discussions exist on the topic. For example, overviews of the attacks as applied to Substitution-Permutation Networks (the cipher structure to be considered in this paper) are presented in [10, 11]. For a general introduction to block ciphers and their analysis, see [14].

The need for a tutorial on the attacks arises from the very difficult nature of both attacks and the lack of simplified, yet detailed, reference material describing the attacks. Most published material detailing the attacks has a research focus and gives little intuition and explanation for the non-expert. When the basic concepts of the attack are described in the literature (as in Matsui's and Biham and Shamir's original papers), they are typically presented in reference to DES which is, in nature, somewhat convoluted in a manner which interferes with the understanding of the cryptanalytic concepts.

2 A BASIC SUSTITUTION-PERMUTATION NETWORK CIPHER

The cipher that we shall use to present the concepts is a basic Substitution-- Permutation Network (SPN). We will focus our discussion on a cipher, illustrated in Figure 1, that takes a 16-bit input block and processes the block by repeating the basic operations of a round four times. Each round consists of (1) substitution, (2) transposition of the bits (i.e., permutation of the bit positions), and (3) key mixing. This basic structure was presented by Feistel back in 1973 [8] and these basic operations are similar to what is found in DES and many other modern ciphers, including Rijndael. So, although we are considering a somewhat simplified structure, an analysis of the attack of such a cipher presents valuable insight into the security of larger, more practical constructions.

2.1 Substitution

In our cipher, we break the 16-bit data block into four 4-bit sub-blocks. Each sub-block forms an input to a 4x4 S-box (a substitution with 4 input and 4 output bits), which can be easily implemented with a table lookup of sixteen 4-bit values, indexed by the integer represented by the 4 input bits. The most fundamental property of an S-box is that it is a nonlinear mapping, i.e., the output bits cannot be represented as a linear operation on the input bits.