DQ
avidu
Chapter4PPT.pptxCryptography and Network Security: Principles and Practice
Eighth Edition
Chapter 4
Block Ciphers and the Data Encryption Standard
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Lecture slides prepared for “Cryptography and Network Security”, 8/e, by William Stallings, Chapter 4 – “Block Ciphers and the Data Encryption Standard”.
The objective of this chapter is to illustrate the principles of modern symmetric
ciphers. For this purpose, we focus on the most widely used symmetric cipher: the Data
Encryption Standard (DES). Although numerous symmetric ciphers have been developed
since the introduction of DES, and although it is destined to be replaced by the
Advanced Encryption Standard (AES), DES remains the most important such algorithm.
Furthermore, a detailed study of DES provides an understanding of the principles
used in other symmetric ciphers.
This chapter begins with a discussion of the general principles of symmetric block
ciphers, which are the principal type of symmetric ciphers studied in this book. The
other form of symmetric ciphers, stream ciphers, are discussed in Chapter 8. Next, we
cover full DES. Following this look at a specific algorithm, we return to a more general
discussion of block cipher design.
Several important symmetric block encryption algorithms in current use are based
on a structure referred to as a Feistel block cipher [FEIS73]. For that reason, it is
important to examine the design principles of the Feistel cipher. We begin with a
comparison of stream ciphers and block ciphers. Then we discuss the motivation for
the Feistel block cipher structure. Finally, we discuss some of its implications.
1
Learning Objectives
Understand the distinction between stream ciphers and block ciphers.
Present an overview of the Feistel cipher and explain how decryption is the inverse of encryption.
Present an overview of Data Encryption Standard (DES).
Explain the concept of the avalanche effect.
Discuss the cryptographic strength of DES.
Summarize the principal block cipher design principles.
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Stream Cipher (1 of 2)
Encrypts a digital data stream one bit or one byte at a time
Examples:
Autokeyed Vigenère cipher
Vernam cipher
In the ideal case, a one-time pad version of the Vernam cipher would be used, in which the keystream is as long as the plaintext bit stream
If the cryptographic keystream is random, then this cipher is unbreakable by any means other than acquiring the keystream
Keystream must be provided to both users in advance via some independent and secure channel
This introduces insurmountable logistical problems if the intended data traffic is very large
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
A stream cipher is one that encrypts a digital data stream one bit or one byte at
a time. Examples of classical stream ciphers are the autokeyed Vigenère cipher
and the Vernam cipher. In the ideal case, a one-time pad version of the Vernam
cipher would be used (Figure 3.7), in which the keystream (ki ) is as long as the
plaintext bit stream (pi ). If the cryptographic keystream is random, then this cipher
is unbreakable by any means other than acquiring the keystream. However, the
keystream must be provided to both users in advance via some independent and
secure channel. This introduces insurmountable logistical problems if the intended
data traffic is very large.
Accordingly, for practical reasons, the bit-stream generator must be
implemented as an algorithmic procedure, so that the cryptographic bit stream
can be produced by both users. In this approach (Figure 4.1a), the bit-stream
generator is a key-controlled algorithm and must produce a bit stream that is
cryptographically strong. That is, it must be computationally impractical to
predict future portions of the bit stream based on previous portions of the bit
stream. The two users need only share the generating key, and each can produce
the keystream.
3
Stream Cipher (2 of 2)
For practical reasons the bit-stream generator must be implemented as an algorithmic procedure so that the cryptographic bit stream can be produced by both users
It must be computationally impractical to predict future portions of the bit stream based on previous portions of the bit stream
The two users need only share the generating key and each can produce the keystream
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
A stream cipher is one that encrypts a digital data stream one bit or one byte at
a time. Examples of classical stream ciphers are the autokeyed Vigenère cipher
and the Vernam cipher. In the ideal case, a one-time pad version of the Vernam
cipher would be used (Figure 3.7), in which the keystream (ki ) is as long as the
plaintext bit stream (pi ). If the cryptographic keystream is random, then this cipher
is unbreakable by any means other than acquiring the keystream. However, the
keystream must be provided to both users in advance via some independent and
secure channel. This introduces insurmountable logistical problems if the intended
data traffic is very large.
Accordingly, for practical reasons, the bit-stream generator must be
implemented as an algorithmic procedure, so that the cryptographic bit stream
can be produced by both users. In this approach (Figure 4.1a), the bit-stream
generator is a key-controlled algorithm and must produce a bit stream that is
cryptographically strong. That is, it must be computationally impractical to
predict future portions of the bit stream based on previous portions of the bit
stream. The two users need only share the generating key, and each can produce
the keystream.
4
Block Cipher
A block of plaintext is treated as a whole and used to produce a ciphertext block of equal length
Typically a block size of 64 or 128 bits is used
As with a stream cipher, the two users share a symmetric encryption key
The majority of network-based symmetric cryptographic applications make use of block ciphers
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
A block cipher is one in which a block of plaintext is treated as a whole
and used to produce a ciphertext block of equal length. Typically, a block size of
64 or 128 bits is used. As with a stream cipher, the two users share a symmetric
encryption key (Figure 4.1b). Using some of the modes of operation explained
in Chapter 7, a block cipher can be used to achieve the same effect as a stream
cipher.
Far more effort has gone into analyzing block ciphers. In general, they seem
applicable to a broader range of applications than stream ciphers. The vast majority
of network-based symmetric cryptographic applications make use of block
ciphers. Accordingly, the concern in this chapter, and in our discussions throughout
the book of symmetric encryption, will primarily focus on block ciphers.
5
Figure 4.1 Stream Cipher and Block Cipher
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Examples of stream and block ciphers.
6
Figure 4.2 General n-bit-n-bit Block Substitution (shown with n = 4)
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
A block cipher operates on a plaintext block of n bits to produce a ciphertext
block of n bits. There are 2n possible different plaintext blocks and, for the
encryption to be reversible (i.e., for decryption to be possible), each must produce
a unique ciphertext block. Such a transformation is called reversible, or nonsingular.
Figure 4.2 illustrates the logic of a general substitution cipher for n = 4.
A 4-bit input produces one of 16 possible input states, which is mapped by the substitution
cipher into a unique one of 16 possible output states, each of which is represented
by 4 ciphertext bits.
7
Table 4.1 Encryption and Decryption Tables for Substitution Cipher of Figure 4.2
| Plaintext | Ciphertext |
| 0000 | 1110 |
| 0001 | 0100 |
| 0010 | 1101 |
| 0011 | 0001 |
| 0100 | 0010 |
| 0101 | 1111 |
| 0110 | 1011 |
| 0111 | 1000 |
| 1000 | 0011 |
| 1001 | 1010 |
| 1010 | 0110 |
| 1011 | 1100 |
| 1100 | 0101 |
| 1101 | 1001 |
| 1110 | 0000 |
| 1111 | 0111 |
| Ciphertext | Plaintext |
| 0000 | 1110 |
| 0001 | 0011 |
| 0010 | 0100 |
| 0011 | 1000 |
| 0100 | 0001 |
| 0101 | 1100 |
| 0110 | 1010 |
| 0111 | 1111 |
| 1000 | 0111 |
| 1001 | 1101 |
| 1010 | 1001 |
| 1011 | 0110 |
| 1100 | 1011 |
| 1101 | 0010 |
| 1110 | 0000 |
| 1111 | 0101 |
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
The encryption and decryption mappings can be defined
by a tabulation, as shown in Table 4.1. This is the most general form of block cipher
and can be used to define any reversible mapping between plaintext and ciphertext.
Feistel refers to this as the ideal block cipher, because it allows for the maximum
number of possible encryption mappings from the plaintext block [FEIS75].
8
Feistel Cipher
Feistel proposed the use of a cipher that alternates substitutions and permutations
Substitutions
Each plaintext element or group of elements is uniquely replaced by a corresponding ciphertext element or group of elements
Permutation
No elements are added or deleted or replaced in the sequence, rather the order in which the elements appear in the sequence is changed
Is a practical application of a proposal by Claude Shannon to develop a product cipher that alternates confusion and diffusion functions
Is the structure used by many significant symmetric block ciphers currently in use
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Feistel proposed [FEIS73] that we can approximate the ideal block cipher by utilizing
the concept of a product cipher, which is the execution of two or more simple ciphers
in sequence in such a way that the final result or product is cryptographically stronger
than any of the component ciphers. The essence of the approach is to develop a block
cipher with a key length of k bits and a block length of n bits, allowing a total of 2k
possible transformations, rather than the 2n ! transformations available with the ideal
block cipher.
In particular, Feistel proposed the use of a cipher that alternates substitutions
and permutations, where these terms are defined as follows:
• Substitution: Each plaintext element or group of elements is uniquely replaced
by a corresponding ciphertext element or group of elements.
• Permutation: A sequence of plaintext elements is replaced by a permutation
of that sequence. That is, no elements are added or deleted or replaced in the
sequence, rather the order in which the elements appear in the sequence is
changed.
In fact, Feistel’s is a practical application of a proposal by Claude Shannon
to develop a product cipher that alternates confusion and diffusion functions
[SHAN49]. We look next at these concepts of diffusion and confusion and then
present the Feistel cipher. But first, it is worth commenting on this remarkable fact:
The Feistel cipher structure, which dates back over a quarter century and which, in
turn, is based on Shannon’s proposal of 1945, is the structure used by many significant
symmetric block ciphers currently in use.
In particular, the Feistel structure
is used for Triple Data Encryption Algorithm (TDEA), which is one of the two
encryption algorithms (along with AES), approved for general use by the National
Institute of Standards and Technology (NIST). The Feistel structure is also used for
several schemes for format-preserving encryption, which have recently come into
prominence. In addition, the Camellia block cipher is a Feistel structure; it is one
of the possible symmetric ciphers in TLS and a number of other Internet security
protocols. Both TDEA and format-preserving encryption are covered in Chapter 7.
9
Diffusion and Confusion
Terms introduced by Claude Shannon to capture the two basic building blocks for any cryptographic system
Shannon’s concern was to thwart cryptanalysis based on statistical analysis
Diffusion
The statistical structure of the plaintext is dissipated into long-range statistics of the ciphertext
This is achieved by having each plaintext digit affect the value of many ciphertext digits
Confusion
Seeks to make the relationship between the statistics of the ciphertext and the value of the encryption key as complex as possible
Even if the attacker can get some handle on the statistics of the ciphertext, the way in which the key was used to produce that ciphertext is so complex as to make it difficult to deduce the key
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
The terms diffusion and confusion were introduced by
Claude Shannon to capture the two basic building blocks for any cryptographic
system [SHAN49]. Shannon’s concern was to thwart cryptanalysis based on statistical
analysis. The reasoning is as follows. Assume the attacker has some knowledge
of the statistical characteristics of the plaintext. For example, in a human-readable
message in some language, the frequency distribution of the various letters may be
known. Or there may be words or phrases likely to appear in the message (probable
words). If these statistics are in any way reflected in the ciphertext, the cryptanalyst
may be able to deduce the encryption key, part of the key, or at least a set of keys
likely to contain the exact key. In what Shannon refers to as a strongly ideal cipher,
all statistics of the ciphertext are independent of the particular key used. The arbitrary
substitution cipher that we discussed previously (Figure 4.2) is such a cipher,
but as we have seen, it is impractical.
Other than recourse to ideal systems, Shannon suggests two methods for
frustrating statistical cryptanalysis: diffusion and confusion. In diffusion, the
statistical structure of the plaintext is dissipated into long-range statistics of the
ciphertext. This is achieved by having each plaintext digit affect the value of many
ciphertext digits; generally, this is equivalent to having each ciphertext digit be
affected by many plaintext digits.
Every block cipher involves a transformation of a block of plaintext into a
block of ciphertext, where the transformation depends on the key. The mechanism
of diffusion seeks to make the statistical relationship between the plaintext and
ciphertext as complex as possible in order to thwart attempts to deduce the key. On
the other hand, confusion seeks to make the relationship between the statistics of
the ciphertext and the value of the encryption key as complex as possible, again to
thwart attempts to discover the key. Thus, even if the attacker can get some handle
on the statistics of the ciphertext, the way in which the key was used to produce that
ciphertext is so complex as to make it difficult to deduce the key. This is achieved by
the use of a complex substitution algorithm. In contrast, a simple linear substitution
function would add little confusion.
As [ROBS95b] points out, so successful are diffusion and confusion in capturing
the essence of the desired attributes of a block cipher that they have become the
cornerstone of modern block cipher design.
10
Figure 4.3 Feistel Encryption and Decryption (16 rounds)
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
The left-hand side of Figure 4.3 depicts the structure
proposed by Feistel. The inputs to the encryption algorithm are a plaintext block of
length 2w bits and a key K . The plaintext block is divided into two halves, LE0 and RE0 .
The two halves of the data pass through n rounds of processing and then combine to
produce the ciphertext block. Each round i has as inputs LEi-1 and REi-1 derived from
the previous round, as well as a subkey Ki derived from the overall K . In general,
the subkeys Ki are different from K and from each other. In Figure 4.3, 16 rounds
are used, although any number of rounds could be implemented.
All rounds have the same structure. A substitution is performed on the left half
of the data. This is done by applying a round function F to the right half of the data
and then taking the exclusive-OR of the output of that function and the left half of the
data. The round function has the same general structure for each round but is parameterized
by the round subkey Ki . Another way to express this is to say that F is a function
of right-half block of w bits and a subkey of y bits, which produces an output value
of length w bits: F (REi , Ki+1 ). Following this substitution, a permutation is performed
that consists of the interchange of the two halves of the data. This structure is a particular
form of the substitution-permutation network (SPN) proposed by Shannon.
11
Feistel Cipher Design Features (1 of 2)
Block size
Larger block sizes mean greater security but reduced encryption/decryption speed for a given algorithm
Key size
Larger key size means greater security but may decrease encryption/decryption speeds
Number of rounds
The essence of the Feistel cipher is that a single round offers inadequate security but that multiple rounds offer increasing security
Subkey generation algorithm
Greater complexity in this algorithm should lead to greater difficulty of cryptanalysis
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
The exact realization of a Feistel network depends on the choice of the following
parameters and design features:
• Block size: Larger block sizes mean greater security (all other things being
equal) but reduced encryption/decryption speed for a given algorithm. The
greater security is achieved by greater diffusion. Traditionally, a block size of
64 bits has been considered a reasonable tradeoff and was nearly universal in
block cipher design. However, the new AES uses a 128-bit block size.
• Key size: Larger key size means greater security but may decrease encryption/
decryption speed. The greater security is achieved by greater resistance to
brute-force attacks and greater confusion. Key sizes of 64 bits or less are now
widely considered to be inadequate, and 128 bits has become a common size.
• Number of rounds: The essence of the Feistel cipher is that a single round
offers inadequate security but that multiple rounds offer increasing security.
A typical size is 16 rounds.
• Subkey generation algorithm: Greater complexity in this algorithm should
lead to greater difficulty of cryptanalysis.
• Round function F: Again, greater complexity generally means greater resistance
to cryptanalysis.
There are two other considerations in the design of a Feistel cipher:
• Fast software encryption/decryption: In many cases, encryption is embedded in
applications or utility functions in such a way as to preclude a hardware implementation.
Accordingly, the speed of execution of the algorithm becomes a
concern.
• Ease of analysis: Although we would like to make our algorithm as difficult as
possible to cryptanalyze, there is great benefit in making the algorithm easy to
analyze. That is, if the algorithm can be concisely and clearly explained, it is
easier to analyze that algorithm for cryptanalytic vulnerabilities and therefore
develop a higher level of assurance as to its strength. DES, for example, does
not have an easily analyzed functionality.
12
Feistel Cipher Design Features (2 of 2)
Round function F
Greater complexity generally means greater resistance to cryptanalysis
Fast software encryption/decryption
In many cases, encrypting is embedded in applications or utility functions in such a way as to preclude a hardware implementation; accordingly, the speed of execution of the algorithm becomes a concern
Ease of analysis
If the algorithm can be concisely and clearly explained, it is easier to analyze that algorithm for cryptanalytic vulnerabilities and therefore develop a higher level of assurance as to its strength
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
The exact realization of a Feistel network depends on the choice of the following
parameters and design features:
• Block size: Larger block sizes mean greater security (all other things being
equal) but reduced encryption/decryption speed for a given algorithm. The
greater security is achieved by greater diffusion. Traditionally, a block size of
64 bits has been considered a reasonable tradeoff and was nearly universal in
block cipher design. However, the new AES uses a 128-bit block size.
• Key size: Larger key size means greater security but may decrease encryption/
decryption speed. The greater security is achieved by greater resistance to
brute-force attacks and greater confusion. Key sizes of 64 bits or less are now
widely considered to be inadequate, and 128 bits has become a common size.
• Number of rounds: The essence of the Feistel cipher is that a single round
offers inadequate security but that multiple rounds offer increasing security.
A typical size is 16 rounds.
• Subkey generation algorithm: Greater complexity in this algorithm should
lead to greater difficulty of cryptanalysis.
• Round function F: Again, greater complexity generally means greater resistance
to cryptanalysis.
There are two other considerations in the design of a Feistel cipher:
• Fast software encryption/decryption: In many cases, encryption is embedded in
applications or utility functions in such a way as to preclude a hardware implementation.
Accordingly, the speed of execution of the algorithm becomes a
concern.
• Ease of analysis: Although we would like to make our algorithm as difficult as
possible to cryptanalyze, there is great benefit in making the algorithm easy to
analyze. That is, if the algorithm can be concisely and clearly explained, it is
easier to analyze that algorithm for cryptanalytic vulnerabilities and therefore
develop a higher level of assurance as to its strength. DES, for example, does
not have an easily analyzed functionality.
13
Feistel Example
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
The process of decryption with a Feistel cipher
is essentially the same as the encryption process. The rule is as follows: Use the
ciphertext as input to the algorithm, but use the subkeys Ki in reverse order. That
is, use Kn in the first round, Kn-1 in the second round, and so on, until K1 is used in
the last round. This is a nice feature, because it means we need not implement two
different algorithms; one for encryption and one for decryption.
14
Data Encryption Standard (DES)
Issued in 1977 by the National Bureau of Standards (now NIST) as Federal Information Processing Standard 46
Was the most widely used encryption scheme until the introduction of the Advanced Encryption Standard (AES) in 2001
Algorithm itself is referred to as the Data Encryption Algorithm (DEA)
Data are encrypted in 64-bit blocks using a 56-bit key
The algorithm transforms 64-bit input in a series of steps into a 64-bit output
The same steps, with the same key, are used to reverse the encryption
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Until the introduction of the Advanced Encryption Standard (AES) in 2001, the
Data Encryption Standard (DES) was the most widely used encryption scheme.
DES was issued in 1977 by the National Bureau of Standards, now the National
Institute of Standards and Technology (NIST), as Federal Information Processing
Standard 46 (FIPS PUB 46). The algorithm itself is referred to as the Data
Encryption Algorithm (DEA). For DEA, data are encrypted in 64-bit blocks using
a 56-bit key. The algorithm transforms 64-bit input in a series of steps into a 64-bit
output. The same steps, with the same key, are used to reverse the encryption.
Over the years, DES became the dominant symmetric encryption algorithm,
especially in financial applications. In 1994, NIST reaffirmed DES for federal use
for another five years; NIST recommended the use of DES for applications other
than the protection of classified information. In 1999, NIST issued a new version
of its standard (FIPS PUB 46-3) that indicated that DES should be used only for
legacy systems and that triple DES (which in essence involves repeating the DES
algorithm three times on the plaintext using two or three different keys to produce
the ciphertext) be used. We study triple DES in Chapter 7. Because the underlying
encryption and decryption algorithms are the same for DES and triple DES, it
remains important to understand the DES cipher. This section provides an overview.
For the interested reader, Appendix C provides further detail.
15
Figure 4.5 General Depiction of DES Encryption Algorithm
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
The overall scheme for DES encryption is illustrated in Figure 4.5. As with any encryption
scheme, there are two inputs to the encryption function: the plaintext to be
encrypted and the key. In this case, the plaintext must be 64 bits in length and the
key is 56 bits in length.
Looking at the left-hand side of the figure, we can see that the processing
of the plaintext proceeds in three phases. First, the 64-bit plaintext passes through
an initial permutation (IP) that rearranges the bits to produce the permuted input .
This is followed by a phase consisting of sixteen rounds of the same function, which
involves both permutation and substitution functions. The output of the last (sixteenth)
round consists of 64 bits that are a function of the input plaintext and the
key. The left and right halves of the output are swapped to produce the preoutput .
Finally, the preoutput is passed through a permutation [IP -1 ] that is the inverse of
the initial permutation function, to produce the 64-bit ciphertext. With the exception
of the initial and final permutations, DES has the exact structure of a Feistel
cipher, as shown in Figure 4.3.
The right-hand portion of Figure 4.5 shows the way in which the 56-bit key is
used. Initially, the key is passed through a permutation function. Then, for each of
the sixteen rounds, a subkey (Ki ) is produced by the combination of a left circular
shift and a permutation. The permutation function is the same for each round, but a
different subkey is produced because of the repeated shifts of the key bits.
As with any Feistel cipher, decryption uses the same algorithm as encryption,
except that the application of the subkeys is reversed. Additionally, the initial and
final permutations are reversed.
16
Table 4.2 DES Example
Note: DES subkeys are shown as eight 6-bit values in hex format
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
We now work through an example and consider some of its implications. Although
you are not expected to duplicate the example by hand, you will find it informative
to study the hex patterns that occur from one step to the next.
For this example, the plaintext is a hexadecimal palindrome. The plaintext,
key, and resulting ciphertext are as follows:
Plaintext: 02468aceeca86420
Key: 0f1571c947d9e859
Ciphertext: da02ce3a89ecac3b
Table 4.2 shows the progression of the algorithm. The first row shows the 32-bit
values of the left and right halves of data after the initial permutation. The next 16
rows show the results after each round. Also shown is the value of the 48-bit subkey
generated for each round. Note that Li = Ri-1 . The final row shows the left- and
right-hand values after the inverse initial permutation. These two values combined
form the ciphertext.
17
Table 4.3 Avalanche Effect in DES: Change in Plaintext
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
A desirable property of any encryption algorithm is that a small change in either
the plaintext or the key should produce a significant change in the ciphertext. In
particular, a change in one bit of the plaintext or one bit of the key should produce
a change in many bits of the ciphertext. This is referred to as the avalanche effect. If
the change were small, this might provide a way to reduce the size of the plaintext
or key space to be searched.
Using the example from Table 4.2, Table 4.3 shows the result when the fourth
bit of the plaintext is changed, so that the plaintext is 12468aceeca86420. The
second column of the table shows the intermediate 64-bit values at the end of each
round for the two plaintexts. The third column shows the number of bits that differ
between the two intermediate values. The table shows that, after just three rounds,
18 bits differ between the two blocks. On completion, the two ciphertexts differ in
32 bit positions.
18
Table 4.4 Avalanche Effect in DES: Change in Key
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Table 4.4 shows a similar test using the original plaintext of with two keys that
differ in only the fourth bit position: the original key, 0f1571c947d9e859, and
the altered key, 1f1571c947d9e859. Again, the results show that about half of
the bits in the ciphertext differ and that the avalanche effect is pronounced after just
a few rounds.
19
Table 4.5 Average Time Required for Exhaustive Key Search
| Key Size (bits) | Cipher | Number of Alternative Keys | Time Required at 109 Decryptions/s | Time Required at 1013 Decryptions/s |
| 56 | DES | 256 ≈ 7.2 × 1016 | 255 ns = 1.125 years | 1 hour |
| 128 | AES | 2128 ≈ 3.4 × 1038 | 2127 ns = 5.3 × 1021 years | 5.3 × 1017 years |
| 168 | Triple DES | 2168 ≈ 3.7 × 1050 | 2167 ns = 5.8 × 1033 years | 5.8 × 1029 years |
| 192 | AES | 2192 ≈ 6.3 × 1057 | 2191 ns = 9.8 × 1040 years | 9.8 × 1036 years |
| 256 | AES | 2256 ≈ 1.2 × 1077 | 2255 ns = 1.8 × 1060 years | 1.8 × 1056 years |
| 26 characters (permutation) | Monoalphabetic | 2! = 4 × 1026 | 2 × 1026 ns = 6.3 × 109 years | 6.3 × 106 years |
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Since its adoption as a federal standard, there have been lingering concerns about
the level of security provided by DES. These concerns, by and large, fall into two
areas: key size and the nature of the algorithm.
With a key length of 56 bits, there are 256 possible keys, which is approximately
7.2 * 1016 keys. Thus, on the face of it, a brute-force attack appears impractical.
Assuming that, on average, half the key space has to be searched, a single machine
performing one DES encryption per microsecond would take more than a thousand
years to break the cipher.
However, the assumption of one encryption per microsecond is overly conservative.
As far back as 1977, Diffie and Hellman postulated that the technology
existed to build a parallel machine with 1 million encryption devices, each of which
could perform one encryption per microsecond [DIFF77]. This would bring the
average search time down to about 10 hours. The authors estimated that the cost
would be about $20 million in 1977 dollars.
With current technology, it is not even necessary to use special, purpose-built
hardware. Rather, the speed of commercial, off-the-shelf processors threaten the
security of DES. A recent paper from Seagate Technology [SEAG08] suggests that
a rate of 1 billion (109 ) key combinations per second is reasonable for today’s multicore
computers. Recent offerings confirm this. Both Intel and AMD now offer
hardware-based instructions to accelerate the use of AES. Tests run on a contemporary
multicore Intel machine resulted in an encryption rate of about half a billion
encryptions per second [BASU12]. Another recent analysis suggests that with
contemporary supercomputer technology, a rate of 1013 encryptions per second is
reasonable [AROR12].
With these results in mind, Table 4.5 shows how much time is required for
a brute-force attack for various key sizes. As can be seen, a single PC can break
DES in about a year; if multiple PCs work in parallel, the time is drastically shortened.
And today’s supercomputers should be able to find a key in about an hour.
Key sizes of 128 bits or greater are effectively unbreakable using simply a brute-force
approach. Even if we managed to speed up the attacking system by a factor
of 1 trillion (1012 ), it would still take over 100,000 years to break a code using a
128-bit key.
Fortunately, there are a number of alternatives to DES, the most important of
which are AES and triple DES, discussed in Chapters 6 and 7, respectively.
20
Strength of DES
Timing attacks
One in which information about the key or the plaintext is obtained by observing how long it takes a given implementation to perform decryptions on various ciphertexts
Exploits the fact that an encryption or decryption algorithm often takes slightly different amounts of time on different inputs
So far it appears unlikely that this technique will ever be successful against DES or more powerful symmetric ciphers such as triple DES and AES
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
We discuss timing attacks in more detail in Part Three, as they relate to public-key
algorithms. However, the issue may also be relevant for symmetric ciphers. In essence,
a timing attack is one in which information about the key or the plaintext is obtained
by observing how long it takes a given implementation to perform decryptions on
various ciphertexts. A timing attack exploits the fact that an encryption or decryption
algorithm often takes slightly different amounts of time on different inputs. [HEVI99]
reports on an approach that yields the Hamming weight (number of bits equal to one)
of the secret key. This is a long way from knowing the actual key, but it is an intriguing
first step. The authors conclude that DES appears to be fairly resistant to a successful
timing attack but suggest some avenues to explore. Although this is an interesting line
of attack, it so far appears unlikely that this technique will ever be successful against
DES or more powerful symmetric ciphers such as triple DES and AES.
21
Block Cipher Design Principles: Number of Rounds
The greater the number of rounds, the more difficult it is to perform cryptanalysis
In general, the criterion should be that the number of rounds is chosen so that known cryptanalytic efforts require greater effort than a simple brute-force key search attack
If DES had 15 or fewer rounds, differential cryptanalysis would require less effort than a brute-force key search
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
The cryptographic strength of a Feistel cipher derives from three aspects of the
design: the number of rounds, the function F, and the key schedule algorithm. Let
us look first at the choice of the number of rounds.
The greater the number of rounds, the more difficult it is to perform cryptanalysis,
even for a relatively weak F. In general, the criterion should be that the
number of rounds is chosen so that known cryptanalytic efforts require greater
effort than a simple brute-force key search attack. This criterion was certainly used
in the design of DES. Schneier [SCHN96] observes that for 16-round DES, a differential
cryptanalysis attack is slightly less efficient than brute force: The differential
cryptanalysis attack requires 255.1 operations, whereas brute force requires 255 . If
DES had 15 or fewer rounds, differential cryptanalysis would require less effort
than a brute-force key search.
This criterion is attractive, because it makes it easy to judge the strength of
an algorithm and to compare different algorithms. In the absence of a cryptanalytic
breakthrough, the strength of any algorithm that satisfies the criterion can be
judged solely on key length.
22
Block Cipher Design Principles: Design of Function F
The heart of a Feistel block cipher is the function F
The more nonlinear F, the more difficult any type of cryptanalysis will be
The SAC and BIC criteria appear to strengthen the effectiveness of the confusion function
The algorithm should have good avalanche properties
Strict avalanche criterion (SAC)
States that any output bit j of an S-box should change with probability 1/2 when any single input bit i is inverted for all i , j
Bit independence criterion (BIC)
States that output bits j and k should change independently when any single input bit i is inverted for all i , j , and k
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
The heart of a Feistel block cipher is the function F, which provides the element
of confusion in a Feistel cipher. Thus, it must be difficult to “unscramble” the
substitution performed by F. One obvious criterion is that F be nonlinear, as we
discussed previously. The more nonlinear F, the more difficult any type of cryptanalysis
will be. There are several measures of nonlinearity, which are beyond
the scope of this book. In rough terms, the more difficult it is to approximate F
by a set of linear equations, the more nonlinear F is.
Several other criteria should be considered in designing F. We would like the
algorithm to have good avalanche properties. Recall that, in general, this means that
a change in one bit of the input should produce a change in many bits of the output.
A more stringent version of this is the strict avalanche criterion (SAC) [WEBS86],
which states that any output bit j of an S-box (see Appendix C for a discussion of
S-boxes) should change with probability 1/2 when any single input bit i is inverted
for all i , j . Although SAC is expressed in terms of S-boxes, a similar criterion could
be applied to F as a whole. This is important when considering designs that do not
include S-boxes.
Another criterion proposed in [WEBS86] is the bit independence criterion
(BIC), which states that output bits j and k should change independently when any
single input bit i is inverted for all i , j , and k . The SAC and BIC criteria appear to
strengthen the effectiveness of the confusion function.
23
Block Cipher Design Principles: Key Schedule Algorithm
With any Feistel block cipher, the key is used to generate one subkey for each round
In general, we would like to select subkeys to maximize the difficulty of deducing individual subkeys and the difficulty of working back to the main key
It is suggested that, at a minimum, the key schedule should guarantee key/ciphertext Strict Avalanche Criterion and Bit Independence Criterion
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
With any Feistel block cipher, the key is used to generate one subkey for each
round. In general, we would like to select subkeys to maximize the difficulty of
deducing individual subkeys and the difficulty of working back to the main key. No
general principles for this have yet been promulgated.
Adams suggests [ADAM94] that, at minimum, the key schedule should
guarantee key/ciphertext Strict Avalanche Criterion and Bit Independence
Criterion.
24
Summary
Explain the concept of the avalanche effect
Discuss the cryptographic strength of DES
Summarize the principal block cipher design principles
Understand the distinction between stream ciphers and block ciphers
Present an overview of the Feistel cipher and explain how decryption is the inverse of encryption
Present an overview of Data Encryption Standard (DES)
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
Chapter 4 summary.
25
Copyright
This work is protected by United States copyright laws and is provided solely for the use of instructors in teaching their courses and assessing student learning. Dissemination or sale of any part of this work (including on the World Wide Web) will destroy the integrity of the work and is not permitted. The work and materials from it should never be made available to students except by instructors using the accompanying text in their classes. All recipients of this work are expected to abide by these restrictions and to honor the intended pedagogical purposes and the needs of other instructors who rely on these materials.
Copyright © 2020 Pearson Education, Inc. All Rights Reserved.
26
.MsftOfcThm_Text1_Fill { fill:#000000; } .MsftOfcThm_MainDark1_Stroke { stroke:#000000; }
