A Tutorial on
Linear and Differential Cryptanalysis
by
Howard M. Heys
Electrical and Computer Engineering
Faculty of Engineering and Applied Science
Memorial University of Newfoundland
St. John’s, NF, Canada A1B 3X5
email: howard@engr.mun.ca
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.
2
1. Introduction
In this paper, we present a tutorial on two powerful cryptanalysis techniques applied to
symmetric-key block ciphers: linear cryptanalysis [1] and differential cryptanalysis [2].
Linear cryptanalysis was introduced by Matsui at EUROCRYPT ’93 as a theoretical
attack on the Data Encryption Standard (DES) [3] and later successfully used in the
practical cryptanalysis of DES [4]; 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 [5]. Although the early target of both attacks was DES, the wide
applicability of both attacks to numerous other block ciphers has solidified the pre-
eminence 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 [6] were designed using techniques specifically targeted at thwarting linear
and differential cryptanalysis. This is evident, for example, in the Rijndael cipher [7], 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 structured to be
considered in this paper) are presented in [8] and [9]. For a general introduction to block
ciphers and their analysis, see [10].
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.
Conventional cryptographic references and texts [11][12][13][14] generally present
material on block ciphers in a very descriptive manner, with little detail illustrating the
concepts of the attacks. Consequently, 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 the
cryptanalytic concepts.
3
2. A Basic Substitution-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) a 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 [15] 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 4×4 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.
For our cipher, we shall use the same nonlinear mapping for all S-boxes. (In DES all the
S-boxes in a round are different, while all rounds use the same set of S-boxes.) The
attacks of linear and differential cryptanalysis apply equally to whether there is one
mapping or all S-boxes are different mappings. The mapping chosen for our cipher, given
in Table 1, is chosen from the S-boxes of DES. (It is the first row of the first S-box.) In
the table, the most significant bit of the hexadecimal notation represents the leftmost bit
of the S-box in Figure 1.
input 0 1 2 3 4 5 6 7 8 9 A B C D E F
output
E 4 D 1 2 F B 8 3 A 6 C 5 9 0 7
Table 1. S-box Representation (in hexadecimal)
2.2 Permutation
The permutation portion of a round is simply the tranposition of the bits or the
permutation of the bit positions. The permutation of Figure 1 is given in Table 2 (where
the numbers represent bit positions in the block, with 1 being the leftmost bit and 16
being the rightmost bit) and can be simply described as: the output i of S-box j is
connected to input j of S-box i. Note that there would be no purpose for a permutation in
the last round and, hence, our cipher does not have one.
input 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
output
1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16
Table 2. Permutation
4
subkey K
4
mixing
subkey K
3
mixing
subkey K
1
mixing
subkey K
2
mixing
subkey K
5
mixing
plaintext
. . . C
16
. . . P
16
P
1
. . .
S
21
S
24
S
22
S
23
S
1
1
S
14
S
12
S
13
S
31
S
34
S
32
S
33
S
41
S
44
S
42
S
43
round 1
round 2
round 3
round 4
Figure 1. Basic Substitution-Permutation Network (SPN) Cipher
C
1
. . . ciphertext
5
2.3 Key Mixing
To achieve the key mixing, we use a simple bit-wise exclusive-OR between the key bits
associated with a round (referred to as a subkey) and the data block input to a round. As
well, a subkey is applied following the last round, ensuring that the last layer of
substitution cannot be easily ignored by a cryptanalyst that simply works backward
through the last round’s substitution. Normally, in a cipher, the subkey for a round is
derived from the cipher’s master key through a process known as the key schedule. In our
cipher, we shall assume that all bits of the subkeys are independently generated and
unrelated.
2.4 Decryption
In order to decrypt, data is essentially passed backwards through the network. Hence,
decryption is also of the form of an SPN as illustrated in Figure 1. However, the
mappings used in the S-boxes of the decryption network are the inverse of the mappings
in the encryption network (i.e., input becomes output, output becomes input). This
implies that in order for an SPN to allow for decryption, all S-boxes must be bijective,
that is, a one-to-one mapping with the same number input and output bits. As well, in
order for the network to properly decrypt, the subkeys are applied in reverse order and the
bits of the subkeys must be moved around according to the permutation, if the SPN is to
look similar to Figure 1. Note also that the lack of the permutation after the last round
ensures that the decryption network can be the same structure as the encryption network.
(If there was a permutation after the last substitution layer in the encryption, the
decryption would require a permutation before the first layer of substitution.)
评论2
最新资源