What are the two basic functions used in encryption algorithms

Symmetric Encryption And Message Confidentiality

1 What are the essential ingredients of a symmetric cipher?

2 What are the two basic functions used in encryption algorithms?

3 How many keys are required for two people to communicate via a symmetric cipher?

4 What is the difference between a block cipher and a stream cipher?

5 What are the two general approaches to attacking a cipher?

6 Why do some block cipher modes of operation only use encryption while others use both encryption and decryption?

7 What is triple encryption?

8 Why is the middle portion of 3DES decryption rather than encryption?

Answer the above questions using the attached reference file only.

Network Security Essentials: Applications and Standards

Sixth Edition

Chapter 2

Symmetric Encryption and

Message Confidentiality

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

If this PowerPoint presentation contains mathematical equations, you may need to check that your computer has the following installed:

1) MathType Plugin

2) Math Player (free versions available)

3) NVDA Reader (free versions available)

This chapter provides a general overview of the subject matter that structures the material in the remainder of the book. We begin with a general discussion of network security services and mechanisms and of the types of attacks they are designed for. Then we develop a general overall model within which the security services and mechanisms can be viewed.

1

Figure 2-1: Simplified Model of Symmetric Encryption

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

A symmetric encryption scheme has five ingredients (Figure 2.1):

• Plaintext: This is the original message or data that is fed into the algorithm

as input.

• Encryption algorithm: The encryption algorithm performs various substitutions

and transformations on the plaintext.

• Secret key: The secret key is also input to the algorithm. The exact substitutions

and transformations performed by the algorithm depend on the key.

• Ciphertext: This is the scrambled message produced as output. It depends on

the plaintext and the secret key. For a given message, two different keys will

produce two different ciphertexts.

• Decryption algorithm: This is essentially the encryption algorithm run in

reverse. It takes the ciphertext and the same secret key and produces the

original plaintext.

2

Requirements (1 of 2)

There are two requirements for secure use of symmetric encryption:

A strong encryption algorithm

Sender and receiver must have obtained copies of the secret key in a secure fashion and must keep the key secure

The security of symmetric encryption depends on the secrecy of the key, not the secrecy of the algorithm

This makes it feasible for widespread use

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

There are two requirements for secure use of symmetric encryption:

1. We need a strong encryption algorithm. At a minimum, we would like the

algorithm to be such that an opponent who knows the algorithm and has

access to one or more ciphertexts would be unable to decipher the ciphertext

or figure out the key. This requirement is usually stated in a stronger form:

The opponent should be unable to decrypt ciphertext or discover the key even

if he or she is in possession of a number of ciphertexts together with the plaintext

that produced each ciphertext.

2. Sender and receiver must have obtained copies of the secret key in a secure

fashion and must keep the key secure. If someone can discover the key and

knows the algorithm, all communication using this key is readable.

It is important to note that the security of symmetric encryption depends on

the secrecy of the key, not the secrecy of the algorithm. That is, it is assumed that

it is impractical to decrypt a message on the basis of the ciphertext plus knowledge

of the encryption/decryption algorithm. In other words, we do not need to keep the

algorithm secret; we need to keep only the key secret.

This feature of symmetric encryption is what makes it feasible for widespread

use. The fact that the algorithm need not be kept secret means that manufacturers

can and have developed low-cost chip implementations of data encryption

algorithms. These chips are widely available and incorporated into a number of

products. With the use of symmetric encryption, the principal security problem is

maintaining the secrecy of the key.

3

Requirements (2 of 2)

Manufacturers can and have developed low-cost chip implementations of data encryption algorithms

These chips are widely available and incorporated into a number of products

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

There are two requirements for secure use of symmetric encryption:

1. We need a strong encryption algorithm. At a minimum, we would like the

algorithm to be such that an opponent who knows the algorithm and has

access to one or more ciphertexts would be unable to decipher the ciphertext

or figure out the key. This requirement is usually stated in a stronger form:

The opponent should be unable to decrypt ciphertext or discover the key even

if he or she is in possession of a number of ciphertexts together with the plaintext

that produced each ciphertext.

2. Sender and receiver must have obtained copies of the secret key in a secure

fashion and must keep the key secure. If someone can discover the key and

knows the algorithm, all communication using this key is readable.

It is important to note that the security of symmetric encryption depends on

the secrecy of the key, not the secrecy of the algorithm. That is, it is assumed that

it is impractical to decrypt a message on the basis of the ciphertext plus knowledge

of the encryption/decryption algorithm. In other words, we do not need to keep the

algorithm secret; we need to keep only the key secret.

This feature of symmetric encryption is what makes it feasible for widespread

use. The fact that the algorithm need not be kept secret means that manufacturers

can and have developed low-cost chip implementations of data encryption

algorithms. These chips are widely available and incorporated into a number of

products. With the use of symmetric encryption, the principal security problem is

maintaining the secrecy of the key.

4

Cryptography (1 of 3)

Cryptographic systems are generically classified along three independent dimensions:

The type of operations used for transforming plaintext to ciphertext

Substitution

Each element in the plaintext is mapped into another element

Transposition

Elements in the plaintext are rearranged

Fundamental requirement is that no information be lost

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

Cryptographic systems are generically classified along three independent

dimensions:

1. The type of operations used for transforming plaintext to ciphertext. All

encryption algorithms are based on two general principles: substitution, in

which each element in the plaintext (bit, letter, group of bits or letters) is

mapped into another element, and transposition, in which elements in the

plaintext are rearranged. The fundamental requirement is that no information

be lost (i.e., that all operations be reversible). Most systems, referred to as

product systems, involve multiple stages of substitutions and transpositions.

2. The number of keys used. If both sender and receiver use the same key, the

system is referred to as symmetric, single-key, secret-key, or conventional

encryption. If the sender and receiver each use a different key, the system is

referred to as asymmetric, two-key, or public-key encryption.

3. The way in which the plaintext is processed. A block cipher processes the

input one block of elements at a time, producing an output block for each

input block. A stream cipher processes the input elements continuously, producing

output one element at a time, as it goes along.

5

Cryptography (2 of 3)

Product systems

Involve multiple stages of substitutions and transpositions

The number of keys used

Referred to as symmetric, single-key, secret-key, or conventional encryption if both sender and receiver use the same key

Referred to as asymmetric, two-key, or public-key encryption if the sender and receiver each use a different key

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

Cryptographic systems are generically classified along three independent

dimensions:

1. The type of operations used for transforming plaintext to ciphertext. All

encryption algorithms are based on two general principles: substitution, in

which each element in the plaintext (bit, letter, group of bits or letters) is

mapped into another element, and transposition, in which elements in the

plaintext are rearranged. The fundamental requirement is that no information

be lost (i.e., that all operations be reversible). Most systems, referred to as

product systems, involve multiple stages of substitutions and transpositions.

2. The number of keys used. If both sender and receiver use the same key, the

system is referred to as symmetric, single-key, secret-key, or conventional

encryption. If the sender and receiver each use a different key, the system is

referred to as asymmetric, two-key, or public-key encryption.

3. The way in which the plaintext is processed. A block cipher processes the

input one block of elements at a time, producing an output block for each

input block. A stream cipher processes the input elements continuously, producing

output one element at a time, as it goes along.

6

Cryptography (3 of 3)

The way in which the plaintext is processed

Block cipher processes the input one block of elements at a time, producing an output block for each input block

Stream cipher processes the input elements continuously, producing output one element at a time, as it goes along

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

Cryptographic systems are generically classified along three independent

dimensions:

1. The type of operations used for transforming plaintext to ciphertext. All

encryption algorithms are based on two general principles: substitution, in

which each element in the plaintext (bit, letter, group of bits or letters) is

mapped into another element, and transposition, in which elements in the

plaintext are rearranged. The fundamental requirement is that no information

be lost (i.e., that all operations be reversible). Most systems, referred to as

product systems, involve multiple stages of substitutions and transpositions.

2. The number of keys used. If both sender and receiver use the same key, the

system is referred to as symmetric, single-key, secret-key, or conventional

encryption. If the sender and receiver each use a different key, the system is

referred to as asymmetric, two-key, or public-key encryption.

3. The way in which the plaintext is processed. A block cipher processes the

input one block of elements at a time, producing an output block for each

input block. A stream cipher processes the input elements continuously, producing

output one element at a time, as it goes along.

7

Table 2-1: Types of Attacks on Encrypted Messages (1 of 2)

Type of Attack Known to Cryptanalyst
Ciphertext only •Encryption algorithm •Ciphertext to be decoded
Known plaintext •Encryption algorithm •Ciphertext to be decoded •One or more plaintext-ciphertext pairs formed with the secret key
Chosen plaintext •Encryption algorithm •Ciphertext to be decoded •Plaintext message chosen by cryptanalyst. together with its corresponding ciphertext generated with the secret key
Copyright © 2017 Pearson Education, Inc. All Rights Reserved

The process of attempting to discover the plaintext or key is known as cryptanalysis .

The strategy used by the cryptanalyst depends on the nature of the encryption scheme

and the information available to the cryptanalyst.

Table 2.1 summarizes the various types of cryptanalytic attacks based on the

amount of information known to the cryptanalyst. The most difficult problem is

presented when all that is available is the ciphertext only . In some cases, not even

the encryption algorithm is known, but in general, we can assume that the opponent

does know the algorithm used for encryption. One possible attack under these circumstances

is the brute-force approach of trying all possible keys. If the key space

is very large, this becomes impractical. Thus, the opponent must rely on an analysis

of the ciphertext itself, generally applying various statistical tests to it. To use this

approach, the opponent must have some general idea of the type of plaintext that

is concealed, such as English or French text, an EXE file, a Java source listing, an

accounting file, and so on.

The ciphertext-only attack is the easiest to defend against because the

opponent has the least amount of information to work with. In many cases, however,

the analyst has more information. The analyst may be able to capture one

or more plaintext messages as well as their encryptions. Or the analyst may know

that certain plaintext patterns will appear in a message. For example, a file that is

encoded in the Postscript format always begins with the same pattern, or there may

be a standardized header or banner to an electronic funds transfer message, and so

on. All of these are examples of known plaintext . With this knowledge, the analyst

may be able to deduce the key on the basis of the way in which the known plaintext

is transformed.

Closely related to the known-plaintext attack is what might be referred to as a

probable-word attack. If the opponent is working with the encryption of some general

prose message, he or she may have little knowledge of what is in the message.

However, if the opponent is after some very specific information, then parts of the

message may be known. For example, if an entire accounting file is being transmitted,

the opponent may know the placement of certain key words in the header of

the file. As another example, the source code for a program developed by a corporation

might include a copyright statement in some standardized position.

If the analyst is able somehow to get the source system to insert into the system

a message chosen by the analyst, then a chosen-plaintext attack is possible. In

general, if the analyst is able to choose the messages to encrypt, the analyst may

deliberately pick patterns that can be expected to reveal the structure of the key.

Table 2.1 lists two other types of attack: chosen ciphertext and chosen text.

These are less commonly employed as cryptanalytic techniques but are nevertheless

possible avenues of attack.

8

Table 2-1: Types of Attacks on Encrypted Messages (2 of 2)

Chosen ciphertext •Encryption algorithm •Ciphertext to be decoded •Purported ciphertext chosen by cryptanalyst. together with its corresponding decrypted plaintext generated with the secret key
Chosen text •Encryption algorithm •Ciphertext to be decoded •Plaintext message chosen by cryptanalyst. together with its corresponding ciphertext generated with the secret key •Purported ciphertext chosen by cryptanalyst. together with its corresponding decrypted plaintext generated with the secret key
Copyright © 2017 Pearson Education, Inc. All Rights Reserved

The process of attempting to discover the plaintext or key is known as cryptanalysis .

The strategy used by the cryptanalyst depends on the nature of the encryption scheme

and the information available to the cryptanalyst.

Table 2.1 summarizes the various types of cryptanalytic attacks based on the

amount of information known to the cryptanalyst. The most difficult problem is

presented when all that is available is the ciphertext only . In some cases, not even

the encryption algorithm is known, but in general, we can assume that the opponent

does know the algorithm used for encryption. One possible attack under these circumstances

is the brute-force approach of trying all possible keys. If the key space

is very large, this becomes impractical. Thus, the opponent must rely on an analysis

of the ciphertext itself, generally applying various statistical tests to it. To use this

approach, the opponent must have some general idea of the type of plaintext that

is concealed, such as English or French text, an EXE file, a Java source listing, an

accounting file, and so on.

The ciphertext-only attack is the easiest to defend against because the

opponent has the least amount of information to work with. In many cases, however,

the analyst has more information. The analyst may be able to capture one

or more plaintext messages as well as their encryptions. Or the analyst may know

that certain plaintext patterns will appear in a message. For example, a file that is

encoded in the Postscript format always begins with the same pattern, or there may

be a standardized header or banner to an electronic funds transfer message, and so

on. All of these are examples of known plaintext . With this knowledge, the analyst

may be able to deduce the key on the basis of the way in which the known plaintext

is transformed.

Closely related to the known-plaintext attack is what might be referred to as a

probable-word attack. If the opponent is working with the encryption of some general

prose message, he or she may have little knowledge of what is in the message.

However, if the opponent is after some very specific information, then parts of the

message may be known. For example, if an entire accounting file is being transmitted,

the opponent may know the placement of certain key words in the header of

the file. As another example, the source code for a program developed by a corporation

might include a copyright statement in some standardized position.

If the analyst is able somehow to get the source system to insert into the system

a message chosen by the analyst, then a chosen-plaintext attack is possible. In

general, if the analyst is able to choose the messages to encrypt, the analyst may

deliberately pick patterns that can be expected to reveal the structure of the key.

Table 2.1 lists two other types of attack: chosen ciphertext and chosen text.

These are less commonly employed as cryptanalytic techniques but are nevertheless

possible avenues of attack.

9

Cryptanalysis

An encryption scheme is computationally secure if the ciphertext generated by the scheme meets one or both of the following criteria:

The cost of breaking the cipher exceeds the value of the encrypted information

The time required to break the cipher exceeds the useful lifetime of the information

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

Only relatively weak algorithms fail to withstand a ciphertext-only attack.

Generally, an encryption algorithm is designed to withstand a known-plaintext

attack.

An encryption scheme is computationally secure if the ciphertext generated

by the scheme meets one or both of the following criteria:

• The cost of breaking the cipher exceeds the value of the encrypted information.

• The time required to break the cipher exceeds the useful lifetime of the

information.

10

Brute Force Attack

Involves trying every possible key until an intelligible translation of the cipher text into plaintext is obtained

On average, half of all possible keys must be tried to achieve success

Unless known plaintext is provided, the analyst must be able to recognize plaintext as plaintext

To supplement the brute-force approach

Some degree of knowledge about the expected plaintext is needed

Some means of automatically distinguishing plaintext from garble is also needed

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

Unfortunately, it is very difficult to estimate the amount of effort required

to cryptanalyze ciphertext successfully. However, assuming there are no inherent

mathematical weaknesses in the algorithm, then a brute-force approach is indicated.

A brute-force attack involves trying every possible key until an intelligible

translation of the ciphertext into plaintext is obtained. On average, half of all possible

keys must be tried to achieve success. That is, if there are x different keys, on

average an attacker would discover the actual key after x /2 tries. It is important

to note that there is more to a brute-force attack than simply running through all

possible keys. Unless known plaintext is provided, the analyst must be able to recognize

plaintext as plaintext. If the message is just plaintext in English, then the

result pops out easily, although the task of recognizing English would have to be

automated. If the text message has been compressed before encryption, then recognition

is more difficult. And if the message is some more general type of data,

such as a numerical file, and this has been compressed, the problem becomes even

more difficult to automate. Thus, to supplement the brute-force approach, some

degree of knowledge about the expected plaintext is needed, and some means of

automatically distinguishing plaintext from garble is also needed.

11

Figure 2-2: Feistel Encryption and Decryption (16 Rounds)

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

Many symmetric block encryption algorithms, including DES, have a structure first

described by Horst Feistel of IBM in 1973 [FEIS73] and shown in Figure 2.2. 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 and are generated from the key

by a subkey generation algorithm. In Figure 2.2, 16 rounds are used, although any

number of rounds could be implemented. The right-hand side of Figure 2.2 shows

the decryption process.

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 (XOR) 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. Following this substitution, a permutation

is performed that consists of the interchange of the two halves of the data.

12

Feistel Cipher Design Elements (1 of 3)

Block size

Larger block sizes mean greater security but reduced encryption/decryption speed

Key size

Larger key size means greater security but may decrease encryption/decryption speed

Number of rounds

The essence of a symmetric block cipher is that a single round offers inadequate security but that multiple rounds offer increasing security

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

The Feistel structure is a particular example of the more general structure

used by all symmetric block ciphers. In general, a symmetric block cipher consists of

a sequence of rounds, with each round performing substitutions and permutations

conditioned by a secret key value. The exact realization of a symmetric block cipher

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. A block size of 128 bits is a

reasonable trade-off and is nearly universal among recent block cipher designs.

• Key size: Larger key size means greater security but may decrease encryption/

decryption speed. The most common key length in modern algorithms is 128 bits.

• Number of rounds: The essence of a symmetric block cipher is that a single

round offers inadequate security but that multiple rounds offer increasing

security. A typical size is from 10 to 16 rounds.

• Subkey generation algorithm: Greater complexity in this algorithm should

lead to greater difficulty of cryptanalysis.

• Round function: Again, greater complexity generally means greater resistance

to cryptanalysis.

There are two other considerations in the design of a symmetric block 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 Cipher Design Elements (2 of 3)

Sub key generation algorithm

Greater complexity in this algorithm should lead to greater difficulty of cryptanalysis

Round function

Greater complexity generally means greater resistance to cryptanalysis

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

The Feistel structure is a particular example of the more general structure

used by all symmetric block ciphers. In general, a symmetric block cipher consists of

a sequence of rounds, with each round performing substitutions and permutations

conditioned by a secret key value. The exact realization of a symmetric block cipher

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. A block size of 128 bits is a

reasonable trade-off and is nearly universal among recent block cipher designs.

• Key size: Larger key size means greater security but may decrease encryption/

decryption speed. The most common key length in modern algorithms is 128 bits.

• Number of rounds: The essence of a symmetric block cipher is that a single

round offers inadequate security but that multiple rounds offer increasing

security. A typical size is from 10 to 16 rounds.

• Subkey generation algorithm: Greater complexity in this algorithm should

lead to greater difficulty of cryptanalysis.

• Round function: Again, greater complexity generally means greater resistance

to cryptanalysis.

There are two other considerations in the design of a symmetric block 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.

14

Feistel Cipher Design Elements (3 of 3)

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 seed 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 © 2017 Pearson Education, Inc. All Rights Reserved

The Feistel structure is a particular example of the more general structure

used by all symmetric block ciphers. In general, a symmetric block cipher consists of

a sequence of rounds, with each round performing substitutions and permutations

conditioned by a secret key value. The exact realization of a symmetric block cipher

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. A block size of 128 bits is a

reasonable trade-off and is nearly universal among recent block cipher designs.

• Key size: Larger key size means greater security but may decrease encryption/

decryption speed. The most common key length in modern algorithms is 128 bits.

• Number of rounds: The essence of a symmetric block cipher is that a single

round offers inadequate security but that multiple rounds offer increasing

security. A typical size is from 10 to 16 rounds.

• Subkey generation algorithm: Greater complexity in this algorithm should

lead to greater difficulty of cryptanalysis.

• Round function: Again, greater complexity generally means greater resistance

to cryptanalysis.

There are two other considerations in the design of a symmetric block 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.

15

Symmetric Block Encryption Algorithms

Block cipher

The most commonly used symmetric encryption algorithms

Processes the plaintext input in fixed-sized blocks and produces a block of ciphertext of equal size for each plaintext block

The three most important symmetric block ciphers

Data Encryption Standard (D E S)

Triple DES (3 D E S)

Advanced Encryption Standard (A E S)

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

The most commonly used symmetric encryption algorithms are block ciphers.

A block cipher processes the plaintext input in fixed-sized blocks and produces a

block of ciphertext of equal size for each plaintext block. This section focuses on

the three most important symmetric block ciphers: the Data Encryption Standard

(DES), triple DES (3DES), and the Advanced Encryption Standard (AES).

16

Data Encryption Standard (D E S)

Most widely used encryption scheme

Issued in 1977 as Federal Information Processing Standard 46 (F I P S 46) by the National Institute of Standards and Technology (N I S T)

The algorithm itself is referred to as the Data Encryption Algorithm (D E A)

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

Until the introduction of the Advanced Encryption Standard in 2001, the most

widely used encryption scheme was based on the Data Encryption Standard (DES)

issued in 1977 as Federal Information Processing Standard 46 (FIPS 46) by the

National Bureau of Standards, now known as the National Institute of Standards

and Technology (NIST). The algorithm itself is referred to as the Data Encryption

Algorithm (DEA).

17

D E S Algorithm (1 of 2)

Description of the algorithm:

Plaintext is 64 bits in length

Key is 56 bits in length

Structure is a minor variation of the Feistel network

There are 16 rounds of processing

Process of decryption is essentially the same as the encryption process

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

The plaintext is 64 bits in length and the key is

56 bits in length; longer plaintext amounts are processed in 64-bit blocks. The DES

structure is a minor variation of the Feistel network shown in Figure 2.2. There are

16 rounds of processing. From the original 56-bit key, 16 subkeys are generated, one

of which is used for each round.

The process of decryption with DES is essentially the same as the encryption

process. The rule is as follows: Use the ciphertext as input to the DES algorithm, but

use the subkeys Ki in reverse order. That is, use K16 on the first iteration, K15 on the

second iteration, and so on until K1 is used on the 16th and last iteration.

Concerns about the strength of DES fall into two categories:

concerns about the algorithm itself and concerns about the use of a 56-bit key.

The first concern refers to the possibility that cryptanalysis is possible by exploiting

the characteristics of the DES algorithm. Over the years, there have been numerous

attempts to find and exploit weaknesses in the algorithm, making DES the most studied

encryption algorithm in existence. Despite numerous approaches, no one

has so far succeeded in discovering a fatal weakness in DES.

A more serious concern is key length. 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. DES finally and definitively proved insecure in July 1998, when the

Electronic Frontier Foundation (EFF) announced that it had broken a DES encryption

using a special-purpose “DES cracker” machine that was built for less than

$250,000. The attack took less than three days. The EFF has published a detailed

description of the machine, enabling others to build their own cracker [EFF98].

And, of course, hardware prices will continue to drop as speeds increase, making

DES virtually worthless.

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 paper from Seagate Technology [SEAG08] suggests that a rate

of one 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 [BASU12].

Another recent analysis suggests that with contemporary supercomputer technology,

a rate of 1013 encryptions/s is reasonable [AROR12].

18

D E S Algorithm (2 of 2)

The strength of D E S:

Concerns fall into two categories

The algorithm itself

Refers to the possibility that cryptanalysis is possible by exploiting the characteristics of the algorithm

The use of a 56-bit key

Speed of commercial, off-the-shelf processors threatens the security

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

The plaintext is 64 bits in length and the key is

56 bits in length; longer plaintext amounts are processed in 64-bit blocks. The DES

structure is a minor variation of the Feistel network shown in Figure 2.2. There are

16 rounds of processing. From the original 56-bit key, 16 subkeys are generated, one

of which is used for each round.

The process of decryption with DES is essentially the same as the encryption

process. The rule is as follows: Use the ciphertext as input to the DES algorithm, but

use the subkeys Ki in reverse order. That is, use K16 on the first iteration, K15 on the

second iteration, and so on until K1 is used on the 16th and last iteration.

Concerns about the strength of DES fall into two categories:

concerns about the algorithm itself and concerns about the use of a 56-bit key.

The first concern refers to the possibility that cryptanalysis is possible by exploiting

the characteristics of the DES algorithm. Over the years, there have been numerous

attempts to find and exploit weaknesses in the algorithm, making DES the most studied

encryption algorithm in existence. Despite numerous approaches, no one

has so far succeeded in discovering a fatal weakness in DES.

A more serious concern is key length. 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. DES finally and definitively proved insecure in July 1998, when the

Electronic Frontier Foundation (EFF) announced that it had broken a DES encryption

using a special-purpose “DES cracker” machine that was built for less than

$250,000. The attack took less than three days. The EFF has published a detailed

description of the machine, enabling others to build their own cracker [EFF98].

And, of course, hardware prices will continue to drop as speeds increase, making

DES virtually worthless.

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 paper from Seagate Technology [SEAG08] suggests that a rate

of one 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 [BASU12].

Another recent analysis suggests that with contemporary supercomputer technology,

a rate of 1013 encryptions/s is reasonable [AROR12].

19

Table 2-2: Average Time Required for Exhaustive Key Search

Key size (bits) Cipher Number of Alternative Keys Time Required at 10 to the ninth power decryptions/s Time Required at 10 to the thirteenth power decryptions/s
56 D E S 2 to the fifty sixth power approximately equals 7.2 times 10 to the sixteenth power 2 to the fifty fifth power nanoseconds = 1.125 years. 1 hour
128 A E S 2 to the 120 eighth power approximately equals 3.4 times 10 to the thirty eighth power 2 to the 120 seventh power nanoseconds = 5.3 times 10 to the twenty first power years. 5.3 times 10 to the seventeenth power years
168 Triple D E S 2 to the 160 eighth power approximately equals 3.7 times 10 to the fiftieth power 2 to the 160 seventh power nanoseconds = 5.8 times 10 to the thirty third power years 5.8 times 10 to the twenty ninth power years
192 A E S 2 to the 190 second power approximately equals 6.3 times 10 to the fifty seventh power 2 to the 190 first power nanoseconds = 9.8 times 10 to the fortieth power years. 9.8 times 10 to the thirty sixth power years
256 A E S 2 to the 250 sixth power approximately equals 1.2 times 10 to the seventy seventh power. 2 to the 250 fifth power nanoseconds = 1.8 times 10 to the sixtieth power years. 1.8 times 10 to the fifty sixth power years.
Copyright © 2017 Pearson Education, Inc. All Rights Reserved

Considering these results, Table 2.2 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.

20

Figure 2-3: Triple D E S

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

Triple DES (3DES) was first standardized for use in financial applications in ANSI

standard X9.17 in 1985. 3DES was incorporated as part of the Data Encryption

Standard in 1999 with the publication of FIPS 46-3.

3DES uses three keys and three executions of the DES algorithm. The function

follows an encrypt-decrypt-encrypt (EDE) sequence (Figure 2.3a).

There is no cryptographic significance to the use of decryption for the second

stage of 3DES encryption. Its only advantage is that it allows users of 3DES to

decrypt data encrypted by users of the older single DES.

With three distinct keys, 3DES has an effective key length of 168 bits.

21

3 D E S Guidelines

F I P S 46-3 includes the following guidelines for 3 D E S:

3 D E S is the F I P S-approved symmetric encryption algorithm of choice

The original D E S, which uses a single 56-bit key, is permitted under the standard for legacy systems only; new procurements should support 3 D E S

Government organizations with legacy D E S systems are encouraged to transition to 3 D E S

It is anticipated that 3 D E S and the Advanced Encryption Standard (A E S) will coexist as F I P S-approved algorithms, allowing for a gradual transition to A E S

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

FIPS 46-3 includes the following guidelines for 3DES.

• 3DES is the FIPS-approved symmetric encryption algorithm of choice.

• The original DES, which uses a single 56-bit key, is permitted under the standard

for legacy systems only. New procurements should support 3DES.

• Government organizations with legacy DES systems are encouraged to transition

to 3DES.

• It is anticipated that 3DES and the Advanced Encryption Standard (AES) will

coexist as FIPS-approved algorithms, allowing for a gradual transition to AES.

It is easy to see that 3DES is a formidable algorithm. Because the underlying

cryptographic algorithm is DEA, 3DES can claim the same resistance to cryptanalysis

based on the algorithm as is claimed for DEA. Furthermore, with a 168-bit key

length, brute-force attacks are effectively impossible.

Ultimately, AES is intended to replace 3DES, but this process will take a

number of years. NIST anticipates that 3DES will remain an approved algorithm

(for U.S. government use) for the foreseeable future.

22

Advanced Encryption Standard (A E S) (1 of 2)

In 1997 N I S T issued a call for proposals for a new A E S:

Should have a security strength equal to or better than 3 D E S and significantly improved efficiency

Must be a symmetric block cipher with a block length of 128 bits and support for key lengths of 128, 192, and 256 bits

Evaluation criteria included security, computational efficiency, memory requirements, hardware and software suitability, and flexibility

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

The principal drawback of 3DES is that the algorithm is relatively sluggish

in software. The original DEA was designed for mid-1970s hardware implementation

and does not produce efficient software code. 3DES, which has three times

as many rounds as DEA, is correspondingly slower. A secondary drawback is that

both DEA and 3DES use a 64-bit block size. For reasons of both efficiency and

security, a larger block size is desirable.

Because of these drawbacks, 3DES is not a reasonable candidate for long term

use. As a replacement, NIST in 1997 issued a call for proposals for a new

Advanced Encryption Standard (AES) , which should have a security strength equal

to or better than 3DES and significantly improved efficiency. In addition to these

general requirements, NIST specified that AES must be a symmetric block cipher

with a block length of 128 bits and support for key lengths of 128, 192, and 256 bits.

Evaluation criteria included security, computational efficiency, memory requirements,

hardware and software suitability, and flexibility.

In a first round of evaluation, 15 proposed algorithms were accepted. A second

round narrowed the field to five algorithms. NIST completed its evaluation process

and published a final standard (FIPS PUB 197) in November of 2001. NIST selected

Rijndael as the proposed AES algorithm. The two researchers who developed and

submitted Rijndael for the AES are both cryptographers from Belgium: Dr. Joan

Daemen and Dr. Vincent Rijmen.

AES uses a block length of 128 bits and a key length

that can be 128, 192, or 256 bits. In the description of this section, we assume a key

length of 128 bits, which is likely to be the one most commonly implemented.

The input to the encryption and decryption algorithms is a single 128-bit

block. In FIPS PUB 197, this block is depicted as a square matrix of bytes. This

block is copied into the State array, which is modified at each stage of encryption or

decryption. After the final stage, State is copied to an output matrix. Similarly, the

128-bit key is depicted as a square matrix of bytes. This key is then expanded into an

array of key schedule words: Each word is four bytes and the total key schedule is

44 words for the 128-bit key. The ordering of bytes within a matrix is by column. So,

for example, the first four bytes of a 128-bit plaintext input to the encryption cipher

occupy the first column of the in matrix, the second four bytes occupy the second

column, and so on. Similarly, the first four bytes of the expanded key, which form a

word, occupy the first column of the w matrix.

23

Advanced Encryption Standard (A E S) (2 of 2)

N I S T selected Rijndael as the proposed A E S algorithm

F I P S P U B 197

Developers were two cryptographers from Belgium: Dr. Joan Daemen and Dr. Vincent Rijmen

Copyright © 2017 Pearson Education, Inc. All Rights Reserved

The principal drawback of 3DES is that the algorithm is relatively sluggish

in software. The original DEA was designed for mid-1970s hardware implementation

and does not produce efficient software code. 3DES, which has three times

as many rounds as DEA, is correspondingly slower. A secondary drawback is that

both DEA and 3DES use a 64-bit block size. For reasons of both efficiency and

security, a larger block size is desirable.

Because of these drawbacks, 3DES is not a reasonable candidate for long term

use. As a replacement, NIST in 1997 issued a call for proposals for a new

Advanced Encryption Standard (AES) , which should have a security strength equal

to or better than 3DES and significantly improved efficiency. In addition to these

general requirements, NIST specified that AES must be a symmetric block cipher

with a block length of 128 bits and support for key lengths of 128, 192, and 256 bits.

Evaluation criteria included security, computational efficiency, memory requirements,

hardware and software suitability, and flexibility.