Sage Tool

Ch04Crypto7e.pptx

Home >Computer Science homework help >Sage Tool

Cryptography and Network Security

Seventh Edition

by William Stallings

Lecture slides prepared for “Cryptography and Network Security”, 7/e, by William Stallings, Chapter 4 – “Block Ciphers and the Data Encryption Standard”.

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.

Compared to public-key ciphers, such as RSA, the structure of DES and most

symmetric ciphers is very complex and cannot be explained as easily as RSA and similar

algorithms. Accordingly, the reader may wish to begin with a simplified version of

DES, which is described in Appendix G. This version allows the reader to perform

encryption and decryption by hand and gain a good understanding of the working of

the algorithm details. Classroom experience indicates that a study of this simplified

version enhances understanding of DES.

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.

Stream Cipher

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.

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

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

Block Cipher

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.

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

Examples of stream and block ciphers.

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.

Table 4.1 Encryption and Decryption Tables for Substitution Cipher of Figure 4.2

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].

Feistel Cipher

Feistel proposed the use of a cipher that alternates substitutions and permutations

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

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.

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

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

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.

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

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.

Feistel Cipher Design Features

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

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

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.

Feistel Example

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.

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

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 S provides further detail.

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.

Table 4.2 DES Example

Note: DES subkeys are shown as eight 6-bit values in hex format

(Table can be found on page 114 in textbook)

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.

Table 4.3 Avalanche Effect in DES: Change in Plaintext

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.

Table 4.4 Avalanche Effect in DES: Change in Key

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.

Table 4.5 Average Time Required for Exhaustive Key Search

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.

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

We discuss timing attacks in more detail in Part Two, 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.

Block Cipher Design Principles: Number of Rounds

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.

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

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

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 S 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.

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

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

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.

Summary

Traditional Block Cipher Structure

Stream ciphers

Block ciphers

Motivation for the Feistel cipher structure

Feistel cipher

The Data Encryption Standard (DES)

Encryption

Decryption

Avalanche effect

The strength of DES

Use of 56-bit keys

Nature of the DES algorithm

Timing attacks

Block cipher design principles

Number of rounds

Design of function F

Key schedule algorithm

Chapter 4 summary.

Bit stream

generation

algorithm

ENCRYPTION

(a) Stream Cipher Using Algorithmic Bit Stream Generator

(b) Block Cipher

Figure 4.1 Stream Cipher and Block Cipher

Key

( K )

Encryption

algorithm

Plaintext

b bits

Key

( K )

Plaintext

(pi) Plaintext

(pi)

Bit stream

generation

algorithm

DECRYPTION

Key

( K )

Ciphertext

(ci)

Ciphertext

Decryption

algorithm

Ciphertext

b bits

Key

( K )

Plaintext

4-Bit Input

4 to 16 Decoder

16 to 4 Encoder

4-Bit Output

Figure 4.2 General n-bit-n-bit Block Substitution (shown with n = 4)

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Plaintext Ciphertext Ciphertext Plaintext 0000 1110 0000 1110 0001 0100 0001 0011 0010 1101 0010 0100 0011 0001 0011 1000 0100 0010 0100 0001 0101 1111 0101 1100 0110 1011 0110 1010 0111 1000 0111 1111 1000 0011 1000 0111 1001 1010 1001 1101 1010 0110 1010 1001 1011 1100 1011 0110 1100 0101 1100 1011 1101 1001 1101 0010 1110 0000 1110 0000 1111 0111 1111 0101

Output (ciphertext)

LD0 = RE16 RD0 = LE16

LD2 = RE14 RD2 = LE14

LD14 = RE2 RD14 = LE2

LD16 = RE0

LD17 = RE0

RD16 = LE0

RD17 = LE0

RD1 = LE15LD1 = RE15

RD15 = LE1LD15 = RE1

Input (ciphertext)

Output (plaintext)

R o u

n d

Figure 4.3 Feistel Encryption and Decryption (16 rounds)

K15

K16

K15

K16

LE0 RE0

Input (plaintext)

LE1 RE1

LE2 RE2

LE14 RE14

LE15 RE15

LE16 RE16

LE17 RE17

R o u

n d

2 R

o u

n d

1 5

R o u

n d

1 6

R o u

n d

1 6

R o u

n d

1 5

R o u

n d

2 R

o u

n d

Figure 4.4 Feistel Example

12DE52

DE7F 03A6

Encryption round Decryption round

03A6

03A6 03A6F(03A6, 12DE52) DE7F F(03A6, 12DE52) DE7F

F(03A6, 12DE52) [F(03A6, 12DE52) DE7F]

= DE7F

FR ou

nd 1

R ou

nd 2

Initial Permutation

Permuted Choice 2Round 1

32-bit Swap

Inverse Initial Permutation

Permuted Choice 1

Round 2

Round 16

• • • • • • • • •

64-bit plaintext

• • • • • • • • •

64-bit key

K16

• • • • • • • • •

64-bit ciphertext

Figure 4.5 General Depiction of DES Encryption Algorithm

Left circular shift

Permuted Choice 2 Left circular shift

64 56

56 64

64 bits

Round Ki Li Ri IP 5a005a00 3cf03c0f

1 1e030f03080d2930 3cf03c0f bad22845 2 0a31293432242318 bad22845 99e9b723 3 23072318201d0c1d 99e9b723 0bae3b9e

4 05261d3824311a20 0bae3b9e 42415649 5 3325340136002c25 42415649 18b3fa41 6 123a2d0d04262a1c 18b3fa41 9616fe23

7 021f120b1c130611 9616fe23 67117cf2 8 1c10372a2832002b 67117cf2 c11bfc09 9 04292a380c341f03 c11bfc09 887fbc6c

10 2703212607280403 887fbc6c 600f7e8b 11 2826390c31261504 600f7e8b f596506e

12 12071c241a0a0f08 f596506e 738538b8 13 300935393c0d100b 738538b8 c6a62c4e 14 311e09231321182a c6a62c4e 56b0bd75

15 283d3e0227072528 56b0bd75 75e8fd8f 16 2921080b13143025 75e8fd8f 25896490

IP–1 da02ce3a 89ecac3b

Round δ Round δ

02468aceeca86420 12468aceeca86420

1 9 c11bfc09887fbc6c 99f911532eed7d94

1 3cf03c0fbad22845 3cf03c0fbad32845

1 10 887fbc6c600f7e8b 2eed7d94d0f23094

2 bad2284599e9b723 bad3284539a9b7a3

5 11 600f7e8bf596506e d0f23094455da9c4

3 99e9b7230bae3b9e 39a9b7a3171cb8b3

18 12 f596506e738538b8 455da9c47f6e3cf3

4 0bae3b9e42415649 171cb8b3ccaca55e

34 13 738538b8c6a62c4e 7f6e3cf34bc1a8d9

5 4241564918b3fa41 ccaca55ed16c3653

37 14 c6a62c4e56b0bd75 4bc1a8d91e07d409

6 18b3fa419616fe23 d16c3653cf402c68

33 15 56b0bd7575e8fd8f 1e07d4091ce2e6dc

7 9616fe2367117cf2 cf402c682b2cefbc

32 16 75e8fd8f25896490 1ce2e6dc365e5f59

8 67117cf2c11bfc09 2b2cefbc99f91153

33 IP–1 da02ce3a89ecac3b 057cde97d7683f2a

Round δ Round δ

02468aceeca86420 02468aceeca86420

0 9 c11bfc09887fbc6c 548f1de471f64dfd

1 3cf03c0fbad22845 3cf03c0f9ad628c5

3 10 887fbc6c600f7e8b 71f64dfd4279876c

2 bad2284599e9b723 9ad628c59939136b

11 11 600f7e8bf596506e 4279876c399fdc0d

3 99e9b7230bae3b9e 9939136b768067b7

25 12 f596506e738538b8 399fdc0d6d208dbb

4 0bae3b9e42415649 768067b75a8807c5

29 13 738538b8c6a62c4e 6d208dbbb9bdeeaa

5 4241564918b3fa41 5a8807c5488dbe94

26 14 c6a62c4e56b0bd75 b9bdeeaad2c3a56f

6 18b3fa419616fe23 488dbe94aba7fe53

26 15 56b0bd7575e8fd8f d2c3a56f2765c1fb

7 9616fe2367117cf2 aba7fe53177d21e4

27 16 75e8fd8f25896490 2765c1fb01263dc4

8 67117cf2c11bfc09 177d21e4548f1de4

32 IP–1 da02ce3a89ecac3b ee92b50606b62b0b

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 26! = 4 × 1026 2 × 1026 ns = 6.3 × 109 years

6.3 × 106 years