W2-NS
akhilesh7593
CH02NetSec6e_accessiblePPT.pptxNetwork 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.
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.
24
Figure 2-4: A E S Encryption and Decryption
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Four different stages are used, one of permutation and three of substitution
(Figure 2.4):
• Substitute bytes: Uses a table, referred to as an S-box, to perform a byte-by-
byte substitution of the block.
• Shift rows: A simple permutation that is performed row by row.
• Mix columns: A substitution that alters each byte in a column as a function
of all of the bytes in the column.
• Add round key: A simple bitwise XOR of the current block with a portion
of the expanded key.
25
Figure 2-5: A E S Encryption Round
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Figure 2.5
depicts the structure of a full encryption round.
26
Random and Pseudorandom Numbers (1 of 2)
A number of network security algorithms based on cryptography make use of random numbers
Examples:
Generation of keys for the R S A public-key encryption algorithm and other public-key algorithms
Generation of a symmetric key for use as a temporary session key; used in a number of networking applications such as Transport Layer Security, Wi-Fi, e-mail security, and I P security
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Random numbers play an important role in the use of encryption for various
network security applications. We provide an overview in this section. The topic is
examined in more detail in Appendix E.
A number of network security algorithms based on cryptography make use of
random numbers. For example,
• Generation of keys for the RSA public-key encryption algorithm (described
in Chapter 3) and other public-key algorithms.
• Generation of a stream key for symmetric stream cipher (discussed in the
following section).
• Generation of a symmetric key for use as a temporary session key. This function
is used in a number of networking applications, such as Transport Layer
Security (Chapter 5), Wi-Fi (Chapter 6), e-mail security (Chapter 7), and IP
security (Chapter 8).
• In a number of key distribution scenarios, such as Kerberos (Chapter 4),
random numbers are used for handshaking to prevent replay attacks.
These applications give rise to two distinct and not necessarily compatible
requirements for a sequence of random numbers: randomness and
unpredictability.
27
Random and Pseudorandom Numbers (2 of 2)
In a number of key distribution scenarios, such as Kerberos, random numbers are used for handshaking to prevent replay attacks
Two distinct and not necessarily compatible requirements for a sequence of random numbers are:
Randomness
Unpredictability
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Random numbers play an important role in the use of encryption for various
network security applications. We provide an overview in this section. The topic is
examined in more detail in Appendix E.
A number of network security algorithms based on cryptography make use of
random numbers. For example,
• Generation of keys for the RSA public-key encryption algorithm (described
in Chapter 3) and other public-key algorithms.
• Generation of a stream key for symmetric stream cipher (discussed in the
following section).
• Generation of a symmetric key for use as a temporary session key. This function
is used in a number of networking applications, such as Transport Layer
Security (Chapter 5), Wi-Fi (Chapter 6), e-mail security (Chapter 7), and IP
security (Chapter 8).
• In a number of key distribution scenarios, such as Kerberos (Chapter 4),
random numbers are used for handshaking to prevent replay attacks.
These applications give rise to two distinct and not necessarily compatible
requirements for a sequence of random numbers: randomness and
unpredictability.
28
Randomness (1 of 2)
The following criteria are used to validate that a sequence of numbers is random:
Uniform distribution
The distribution of bits in the sequence should be uniform
Frequency of occurrence of ones and zeros should be approximately the same
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Traditionally, the concern in the generation of a sequence of allegedly
random numbers has been that the sequence of numbers be random in some well defined
statistical sense. The following criteria are used to validate that a sequence
of numbers is random.
• Uniform distribution: The distribution of bits in the sequence should be
uniform; that is, the frequency of occurrence of ones and zeros should
be approximately the same.
• Independence: No one subsequence in the sequence can be inferred from the
others.
Although there are well-defined tests for determining that a sequence of numbers
matches a particular distribution, such as the uniform distribution, there is no
such test to “prove” independence. Rather, a number of tests can be applied to
demonstrate if a sequence does not exhibit independence. The general strategy is
to apply a number of such tests until the confidence that independence exists is sufficiently
strong.
29
Randomness (2 of 2)
Independence
No one subsequence in the sequence can be inferred from the others
There is no test to “prove” independence
The general strategy is to apply a number of tests until the confidence that independence exists is sufficiently strong
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Traditionally, the concern in the generation of a sequence of allegedly
random numbers has been that the sequence of numbers be random in some well defined
statistical sense. The following criteria are used to validate that a sequence
of numbers is random.
• Uniform distribution: The distribution of bits in the sequence should be
uniform; that is, the frequency of occurrence of ones and zeros should
be approximately the same.
• Independence: No one subsequence in the sequence can be inferred from the
others.
Although there are well-defined tests for determining that a sequence of numbers
matches a particular distribution, such as the uniform distribution, there is no
such test to “prove” independence. Rather, a number of tests can be applied to
demonstrate if a sequence does not exhibit independence. The general strategy is
to apply a number of such tests until the confidence that independence exists is sufficiently
strong.
30
Unpredictability
In applications such as reciprocal authentication and session key generation, the requirement is not so much that the sequence of numbers be statistically random but that the successive members of the sequence are unpredictable
With “true” random sequences, each number is statistically independent of other numbers in the sequence and therefore unpredictable
Care must be taken that an opponent not be able to predict future elements of the sequence on the basis of earlier elements
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
In applications such as reciprocal authentication and session key
generation, the requirement is not so much that the sequence of numbers be statistically
random but that the successive members of the sequence are unpredictable.
With “true” random sequences, each number is statistically independent of other
numbers in the sequence and therefore unpredictable. However, as is discussed
shortly, true random numbers are not always used; rather, sequences of numbers
that appear to be random are generated by some algorithm. In this latter case, care
must be taken that an opponent not be able to predict future elements of the sequence
on the basis of earlier elements.
31
Figure 2-6: Random and Pseudorandom Number Generators
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Cryptographic applications typically make use of algorithmic techniques for random
number generation. These algorithms are deterministic and therefore produce
sequences of numbers that are not statistically random. However, if the algorithm is
good, the resulting sequences will pass many reasonable tests of randomness. Such
numbers are referred to as pseudorandom numbers .
You may be somewhat uneasy about the concept of using numbers generated
by a deterministic algorithm as if they were random numbers. Despite what might be
called philosophical objections to such a practice, it generally works. That is, under
most circumstances, pseudorandom numbers will perform as well as if they were random
for a given use. The phrase “as well as” is unfortunately subjective, but the use
of pseudorandom numbers is widely accepted. The same principle applies in statistical
application, in which a statistician takes a sample of a population and assumes that
the results will be approximately the same as if the whole population were measured.
Figure 2.6 contrasts a true random number generator (TRNG) with two
forms of pseudorandom number generators. A TRNG takes as input a source
that is effectively random; the source is often referred to as an entropy source . In
essence, the entropy source is drawn from the physical environment of the computer
and could include things such as keystroke timing patterns, disk electrical
activity, mouse movements, and instantaneous values of the system clock. The
source, or combination of sources, serves as input to an algorithm that produces
random binary output. The TRNG may simply involve conversion of an analog
source to a binary output. The TRNG may involve additional processing to overcome
any bias in the source.
In contrast, a PRNG takes as input a fixed value, called the seed , and produces
a sequence of output bits using a deterministic algorithm. Typically, as shown in
Figure 2.6, there is some feedback path by which some of the results of the algorithm
are fed back as input as additional output bits are produced. The important
thing to note is that the output bit stream is determined solely by the input value or
values, so that an adversary who knows the algorithm and the seed can reproduce
the entire bit stream.
Figure 2.6 shows two different forms of PRNGs, based on application.
• Pseudorandom number generator: An algorithm that is used to produce an
open-ended sequence of bits is referred to as a PRNG. A common application
for an open-ended sequence of bits is as input to a symmetric stream cipher, as
discussed in the following section.
• Pseudorandom function (PRF): A PRF is used to produce a pseudorandom
string of bits of some fixed length. Examples are symmetric encryption
keys and nonces. Typically, the PRF takes as input a seed plus some context
specific values, such as a user ID or an application ID. A number of examples
of PRFs will be seen throughout this book.
Other than the number of bits produced, there is no difference between a
PRNG and a PRF. The same algorithms can be used in both applications. Both
require a seed and both must exhibit randomness and unpredictability. Furthermore,
a PRNG application may also employ context-specific input.
32
Algorithm Design (1 of 2)
Purpose-built algorithms
Designed specifically and solely for the purpose of generating pseudorandom bit streams
Algorithms based on existing cryptographic algorithms
Cryptographic algorithms have the effect of randomizing input
Can serve as the core of P R N G s
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Cryptographic PRNGs have been the subject of much research over the years,
and a wide variety of algorithms have been developed. These fall roughly into two
categories:
• Purpose-built algorithms: These are algorithms designed specifically and
solely for the purpose of generating pseudorandom bit streams. Some of these
algorithms are used for a variety of PRNG applications; several of these are
described in the next section. Others are designed specifically for use in a
stream cipher. The most important example of the latter is RC4, described in
the next section.
• Algorithms based on existing cryptographic algorithms: Cryptographic algorithms
have the effect of randomizing input. Indeed, this is a requirement of
such algorithms. For example, if a symmetric block cipher produced ciphertext
that had certain regular patterns in it, it would aid in the process of cryptanalysis.
Thus, cryptographic algorithms can serve as the core of PRNGs.
Three broad categories of cryptographic algorithms are commonly used to
create PRNGs:
—Symmetric block ciphers
—Asymmetric ciphers
—Hash functions and message authentication codes
Any of these approaches can yield a cryptographically strong PRNG. A
purpose-built algorithm may be provided by an operating system for general use.
For applications that already use certain cryptographic algorithms for encryption or
authentication, it makes sense to re-use the same code for the PRNG. Thus, all of
these approaches are in common use.
33
Algorithm Design (2 of 2)
Three broad categories of cryptographic algorithms are commonly used to create P R N G s:
Symmetric block ciphers
Asymmetric ciphers
Hash functions and message authentication codes
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Cryptographic PRNGs have been the subject of much research over the years,
and a wide variety of algorithms have been developed. These fall roughly into two
categories:
• Purpose-built algorithms: These are algorithms designed specifically and
solely for the purpose of generating pseudorandom bit streams. Some of these
algorithms are used for a variety of PRNG applications; several of these are
described in the next section. Others are designed specifically for use in a
stream cipher. The most important example of the latter is RC4, described in
the next section.
• Algorithms based on existing cryptographic algorithms: Cryptographic algorithms
have the effect of randomizing input. Indeed, this is a requirement of
such algorithms. For example, if a symmetric block cipher produced ciphertext
that had certain regular patterns in it, it would aid in the process of cryptanalysis.
Thus, cryptographic algorithms can serve as the core of PRNGs.
Three broad categories of cryptographic algorithms are commonly used to
create PRNGs:
—Symmetric block ciphers
—Asymmetric ciphers
—Hash functions and message authentication codes
Any of these approaches can yield a cryptographically strong PRNG. A
purpose-built algorithm may be provided by an operating system for general use.
For applications that already use certain cryptographic algorithms for encryption or
authentication, it makes sense to re-use the same code for the PRNG. Thus, all of
these approaches are in common use.
34
Figure 2-7: Stream Cipher Diagram
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
A typical stream cipher encrypts plaintext one byte at a time, although a stream
cipher may be designed to operate on one bit at a time or on units larger than a
byte at a time. Figure 2.7 is a representative diagram of stream cipher structure.
In this structure, a key is input to a pseudorandom bit generator that produces a
stream of 8-bit numbers that are apparently random. The pseudorandom stream is
unpredictable without knowledge of the input key and has an apparently random
character. The output of the generator, called a keystream , is combined one byte at
a time with the plaintext stream using the bitwise exclusive-OR (XOR) operation.
35
Stream Cipher Design Considerations (1 of 2)
The encryption sequence should have a large period
The longer the period of repeat, the more difficult it will be to do cryptanalysis
The keystream should approximate the properties of a true random number stream as close as possible
The more random-appearing the keystream is, the more randomized the ciphertext is, making cryptanalysis more difficult
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
[KUMA97] lists the following important design considerations for a stream
cipher.
1. The encryption sequence should have a large period. A pseudorandom number
generator uses a function that produces a deterministic stream of bits that
eventually repeats. The longer the period of repeat, the more difficult it will
be to do cryptanalysis.
2. The keystream should approximate the properties of a true random number
stream as close as possible. For example, there should be an approximately
equal number of 1s and 0s. If the keystream is treated as a stream of bytes,
then all of the 256 possible byte values should appear approximately equally
often. The more random-appearing the keystream is, the more randomized the
ciphertext is, making cryptanalysis more difficult.
3. Note from Figure 2.7 that the output of the pseudorandom number generator
is conditioned on the value of the input key. To guard against brute-force
attacks, the key needs to be sufficiently long. The same considerations as apply
for block ciphers are valid here. Thus, with current technology, a key length of
at least 128 bits is desirable.
With a properly designed pseudorandom number generator, a stream cipher
can be as secure as block cipher of comparable key length. A potential advantage
of a stream cipher is that stream ciphers that do not use block ciphers as a building
block are typically faster and use far less code than do block ciphers. The example
in this chapter, RC4, can be implemented in just a few lines of code. In recent years,
this advantage has diminished with the introduction of AES, which is quite efficient
in software. Furthermore, hardware acceleration techniques are now available for
AES. For example, the Intel AES Instruction Set has machine instructions for one
round of encryption and decryption and key generation. Using the hardware instructions
results in speedups of about an order of magnitude compared to pure
software implementations [XU10].
One advantage of a block cipher is that you can reuse keys. In contrast, if two
plaintexts are encrypted with the same key using a stream cipher, then cryptanalysis
is often quite simple [DAWS96]. If the two ciphertext streams are XORed together,
the result is the XOR of the original plaintexts. If the plaintexts are text strings,
credit card numbers, or other byte streams with known properties, then cryptanalysis
may be successful.
For applications that require encryption/decryption of a stream of data (such
as over a data-communications channel or a browser/Web link), a stream cipher
might be the better alternative. For applications that deal with blocks of data (such
as file transfer, e-mail, and database), block ciphers may be more appropriate.
However, either type of cipher can be used in virtually any application.
36
Stream Cipher Design Considerations (2 of 2)
The pseudorandom number generator is conditioned on the value of the input key
To guard against brute-force attacks, the key needs to be sufficiently long
With current technology, a key length of at least 128 bits is desirable
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
[KUMA97] lists the following important design considerations for a stream
cipher.
1. The encryption sequence should have a large period. A pseudorandom number
generator uses a function that produces a deterministic stream of bits that
eventually repeats. The longer the period of repeat, the more difficult it will
be to do cryptanalysis.
2. The keystream should approximate the properties of a true random number
stream as close as possible. For example, there should be an approximately
equal number of 1s and 0s. If the keystream is treated as a stream of bytes,
then all of the 256 possible byte values should appear approximately equally
often. The more random-appearing the keystream is, the more randomized the
ciphertext is, making cryptanalysis more difficult.
3. Note from Figure 2.7 that the output of the pseudorandom number generator
is conditioned on the value of the input key. To guard against brute-force
attacks, the key needs to be sufficiently long. The same considerations as apply
for block ciphers are valid here. Thus, with current technology, a key length of
at least 128 bits is desirable.
With a properly designed pseudorandom number generator, a stream cipher
can be as secure as block cipher of comparable key length. A potential advantage
of a stream cipher is that stream ciphers that do not use block ciphers as a building
block are typically faster and use far less code than do block ciphers. The example
in this chapter, RC4, can be implemented in just a few lines of code. In recent years,
this advantage has diminished with the introduction of AES, which is quite efficient
in software. Furthermore, hardware acceleration techniques are now available for
AES. For example, the Intel AES Instruction Set has machine instructions for one
round of encryption and decryption and key generation. Using the hardware instructions
results in speedups of about an order of magnitude compared to pure
software implementations [XU10].
One advantage of a block cipher is that you can reuse keys. In contrast, if two
plaintexts are encrypted with the same key using a stream cipher, then cryptanalysis
is often quite simple [DAWS96]. If the two ciphertext streams are XORed together,
the result is the XOR of the original plaintexts. If the plaintexts are text strings,
credit card numbers, or other byte streams with known properties, then cryptanalysis
may be successful.
For applications that require encryption/decryption of a stream of data (such
as over a data-communications channel or a browser/Web link), a stream cipher
might be the better alternative. For applications that deal with blocks of data (such
as file transfer, e-mail, and database), block ciphers may be more appropriate.
However, either type of cipher can be used in virtually any application.
37
R C 4 Algorithm
A stream cipher designed in 1987 by Ron Rivest for R S A Security
It is a variable key-size stream cipher with byte-oriented operations
The algorithm is based on the use of a random permutation
Is used in the Secure Sockets Layer/Transport Layer Security (S S L/T L S) standards that have been defined for communication between Web browsers and servers
Also used in the Wired Equivalent Privacy (W E P) protocol and the newer WiFi Protected Access (W P A) protocol that are part of the I E E E 802.11 wireless L A N standard
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
RC4 is a stream cipher designed in 1987 by Ron Rivest for RSA Security. It is
a variable key-size stream cipher with byte-oriented operations. The algorithm
is based on the use of a random permutation. Analysis shows that the period of
the cipher is overwhelmingly likely to be greater than 10100 [ROBS95a]. Eight
to sixteen machine operations are required per output byte, and the cipher can
be expected to run very quickly in software. RC4 is used in the Secure Sockets
Layer/Transport Layer Security (SSL/TLS) standards that have been defined
for communication between Web browsers and servers. It is also used in the
Wired Equivalent Privacy (WEP) protocol and the newer WiFi Protected Access
(WPA) protocol that are part of the IEEE 802.11 wireless LAN standard. RC4
was kept as a trade secret by RSA Security. In September 1994, the RC4 algorithm
was anonymously posted on the Internet on the Cypherpunks anonymous
remailers list.
The RC4 algorithm is remarkably simple and quite easy to explain. A
variable-length key of from 1 to 256 bytes (8 to 2048 bits) is used to initialize a
256-byte state vector S, with elements S[0], S[1], . . . , S[255]. At all times, S contains
a permutation of all 8-bit numbers from 0 through 255. For encryption and decryption,
a byte k (see Figure 2.7) is generated from S by selecting one of the 255 entries
in a systematic fashion. As each value of k is generated, the entries in S are once
again permuted.
A number of papers have been published analyzing methods
of attacking RC4 (e.g., [KNUD98], [FLUH00], [MANT01]). None of these
approaches is practical against RC4 with a reasonable key length, such as 128 bits.
A more serious problem is reported in [FLUH01]. The authors demonstrate that
the WEP protocol, intended to provide confidentiality on 802.11 wireless LAN
networks, is vulnerable to a particular attack approach. In essence, the problem is
not with RC4 itself but the way in which keys are generated for use as input to RC4.
This particular problem does not appear to be relevant to other applications using
RC4 and can be remedied in WEP by changing the way in which keys are generated.
This problem points out the difficulty in designing a secure system that involves
both cryptographic functions and protocols that make use of them.
38
Figure 2-8: R C 4
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Figure 2.8 illustrates the RC4 logic.
39
Cipher Block Modes of Operation (1 of 2)
A symmetric block cipher processes one block of data at a time
In the case of D E S and 3 D E S, the block length is b=64 bits
For A E S, the block length is b=128
For longer amounts of plaintext, it is necessary to break the plaintext into b-bit blocks, padding the last block if necessary
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
A symmetric block cipher processes one block of data at a time. In the case of
DES and 3DES, the block length is b = 64 bits; for AES, the block length is
b = 128 bits. For longer amounts of plaintext, it is necessary to break the plaintext
into b -bit blocks (padding the last block if necessary). To apply a block cipher in a
variety of applications, five modes of operation have been defined by NIST
(Special Publication 800-38A). The five modes are intended to cover virtually all
of the possible applications of encryption for which a block cipher could be used.
These modes are intended for use with any symmetric block cipher, including triple
DES and AES. The most important modes are described briefly in the remainder
of this section.
40
Cipher Block Modes of Operation (2 of 2)
Five modes of operation have been defined by N I S T
Intended to cover virtually all of the possible applications of encryption for which a block cipher could be used
Intended for use with any symmetric block cipher, including triple D E S and A E S
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
A symmetric block cipher processes one block of data at a time. In the case of
DES and 3DES, the block length is b = 64 bits; for AES, the block length is
b = 128 bits. For longer amounts of plaintext, it is necessary to break the plaintext
into b -bit blocks (padding the last block if necessary). To apply a block cipher in a
variety of applications, five modes of operation have been defined by NIST
(Special Publication 800-38A). The five modes are intended to cover virtually all
of the possible applications of encryption for which a block cipher could be used.
These modes are intended for use with any symmetric block cipher, including triple
DES and AES. The most important modes are described briefly in the remainder
of this section.
41
Electronic Codebook Mode (E C B) (1 of 2)
Plaintext is handled b bits at a time and each block of plaintext is encrypted using the same key
The term “codebook” is used because, for a given key, there is a unique ciphertext for every b-bit block of plaintext
One can imagine a gigantic codebook in which there is an entry for every possible b-bit plaintext pattern showing its corresponding ciphertext
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
The simplest way to proceed is using what is known as electronic codebook (ECB)
mode , in which plaintext is handled b bits at a time and each block of plaintext is
encrypted using the same key. The term codebook is used because, for a given key,
there is a unique ciphertext for every b -bit block of plaintext. Therefore, one can
imagine a gigantic codebook in which there is an entry for every possible b -bit plaintext
pattern showing its corresponding ciphertext.
With ECB, if the same b -bit block of plaintext appears more than once in
the message, it always produces the same ciphertext. Because of this, for lengthy
messages, the ECB mode may not be secure. If the message is highly structured,
it may be possible for a cryptanalyst to exploit these regularities. For example,
if it is known that the message always starts out with certain predefined fields,
then the cryptanalyst may have a number of known plaintext–ciphertext pairs to
work with. If the message has repetitive elements with a period of repetition a
multiple of b bits, then these elements can be identified by the analyst. This may
help in the analysis or may provide an opportunity for substituting or rearranging
blocks.
To overcome the security deficiencies of ECB, we would like a technique in
which the same plaintext block, if repeated, produces different ciphertext blocks.
42
Electronic Codebook Mode (E C B) (2 of 2)
With E C B, if the same b-bit block of plaintext appears more than once in the message, it always produces the same ciphertext
Because of this, for lengthy messages, the E C B mode may not be secure
If the message is highly structured, it may be possible for a cryptanalyst to exploit these regularities
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
The simplest way to proceed is using what is known as electronic codebook (ECB)
mode , in which plaintext is handled b bits at a time and each block of plaintext is
encrypted using the same key. The term codebook is used because, for a given key,
there is a unique ciphertext for every b -bit block of plaintext. Therefore, one can
imagine a gigantic codebook in which there is an entry for every possible b -bit plaintext
pattern showing its corresponding ciphertext.
With ECB, if the same b -bit block of plaintext appears more than once in
the message, it always produces the same ciphertext. Because of this, for lengthy
messages, the ECB mode may not be secure. If the message is highly structured,
it may be possible for a cryptanalyst to exploit these regularities. For example,
if it is known that the message always starts out with certain predefined fields,
then the cryptanalyst may have a number of known plaintext–ciphertext pairs to
work with. If the message has repetitive elements with a period of repetition a
multiple of b bits, then these elements can be identified by the analyst. This may
help in the analysis or may provide an opportunity for substituting or rearranging
blocks.
To overcome the security deficiencies of ECB, we would like a technique in
which the same plaintext block, if repeated, produces different ciphertext blocks.
43
Figure 2-9: Cipher Block Chaining (C B C) Mode
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
In the cipher block chaining (CBC) mode (Figure 2.9), the input to the encryption
algorithm is the XOR of the current plaintext block and the preceding ciphertext
block; the same key is used for each block. In effect, we have chained together the
processing of the sequence of plaintext blocks. The input to the encryption function
for each plaintext block bears no fixed relationship to the plaintext block. Therefore,
repeating patterns of b bits are not exposed.
For decryption, each cipher block is passed through the decryption algorithm.
The result is XORed with the preceding ciphertext block to produce the plaintext
block.
To produce the first block of ciphertext, an initialization vector (IV) is XORed
with the first block of plaintext. On decryption, the IV is XORed with the output of
the decryption algorithm to recover the first block of plaintext.
The IV must be known to both the sender and receiver. For maximum security,
the IV should be protected as well as the key. This could be done by sending
the IV using ECB encryption. One reason for protecting the IV is as follows: If an
opponent is able to fool the receiver into using a different value for IV, then the
opponent is able to invert selected bits in the first block of plaintext.
44
Figure 2-10: S-Bit Cipher Feedback (C F B) Mode
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
It is possible to convert any block cipher into a stream cipher by using the cipher
feedback (CFB) mode . A stream cipher eliminates the need to pad a message to
be an integral number of blocks. It also can operate in real time. Thus, if a character
stream is being transmitted, each character can be encrypted and transmitted
immediately using a character-oriented stream cipher.
One desirable property of a stream cipher is that the ciphertext be of the same
length as the plaintext. Thus, if 8-bit characters are being transmitted, each character
should be encrypted using 8 bits. If more than 8 bits are used, transmission
capacity is wasted.
Figure 2.10 depicts the CFB scheme. In the figure, it is assumed that the unit
of transmission is s bits; a common value is s = 8. As with CBC, the units of plaintext
are chained together, so that the ciphertext of any plaintext unit is a function of
all the preceding plaintext.
45
Figure 2-11: Counter (C T R) Mode
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Although interest in the counter mode (CTR) has increased recently, with applications
to ATM (asynchronous transfer mode) network security and IPSec (IP security),
this mode was proposed early on (e.g., [DIFF79]).
Figure 2.11 depicts the CTR mode. A counter equal to the plaintext block
size is used. The only requirement stated in SP 800-38A is that the counter value
must be different for each plaintext block that is encrypted. Typically, the counter
is initialized to some value and then incremented by 1 for each subsequent block
(modulo 2b , where b is the block size). For encryption, the counter is encrypted and
then XORed with the plaintext block to produce the ciphertext block; there is no
chaining. For decryption, the same sequence of counter values is used, with each
encrypted counter XORed with a ciphertext block to recover the corresponding
plaintext block.
46
Advantages of C T R Mode (1 of 3)
Hardware efficiency
Encryption/decryption can be done in parallel on multiple blocks of plaintext or ciphertext
Throughput is only limited by the amount of parallelism that is achieved
Software efficiency
Because of the opportunities for parallel execution, processors that support parallel features can be effectively utilized
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
[LIPM00] lists the following advantages of CTR mode.
• Hardware efficiency: Unlike the chaining modes, encryption (or decryption)
in CTR mode can be done in parallel on multiple blocks of plaintext or
ciphertext. For the chaining modes, the algorithm must complete the computation
on one block before beginning on the next block. This limits the maximum
throughput of the algorithm to the reciprocal of the time for one execution of
block encryption or decryption. In CTR mode, the throughput is only limited
by the amount of parallelism that is achieved.
• Software efficiency: Similarly, because of the opportunities for parallel execution
in CTR mode, processors that support parallel features (such as aggressive
pipelining, multiple instruction dispatch per clock cycle, a large number of
registers, and SIMD instructions) can be effectively utilized.
• Preprocessing: The execution of the underlying encryption algorithm does not
depend on input of the plaintext or ciphertext. Therefore, if sufficient memory
is available and security is maintained, preprocessing can be used to prepare the
output of the encryption boxes that feed into the XOR functions in Figure 2.11.
When the plaintext or ciphertext input is presented, then the only computation
is a series of XORs. Such a strategy greatly enhances throughput.
• Random access: The ith block of plaintext or ciphertext can be processed in
random-access fashion. With the chaining modes, block Ci cannot be computed
until the i- 1 prior block are computed. There may be applications in
which a ciphertext is stored, and it is desired to decrypt just one block; for such
applications, the random access feature is attractive.
• Provable security: It can be shown that CTR is at least as secure as the other
modes discussed in this section.
• Simplicity: Unlike ECB and CBC modes, CTR mode requires only the
implementation of the encryption algorithm and not the decryption algorithm.
This matters most when the decryption algorithm differs substantially
from the encryption algorithm, as it does for AES. In addition, the decryption
key scheduling need not be implemented.
47
Advantages of C T R Mode (2 of 3)
Preprocessing
The execution of the underlying encryption algorithm does not depend on input of the plaintext or ciphertext --- when the plaintext or ciphertext input is presented, the only computation is a series of X O R s, greatly enhancing throughput
Random access
The ith block of plaintext or ciphertext can be processed in random-access fashion
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
[LIPM00] lists the following advantages of CTR mode.
• Hardware efficiency: Unlike the chaining modes, encryption (or decryption)
in CTR mode can be done in parallel on multiple blocks of plaintext or
ciphertext. For the chaining modes, the algorithm must complete the computation
on one block before beginning on the next block. This limits the maximum
throughput of the algorithm to the reciprocal of the time for one execution of
block encryption or decryption. In CTR mode, the throughput is only limited
by the amount of parallelism that is achieved.
• Software efficiency: Similarly, because of the opportunities for parallel execution
in CTR mode, processors that support parallel features (such as aggressive
pipelining, multiple instruction dispatch per clock cycle, a large number of
registers, and SIMD instructions) can be effectively utilized.
• Preprocessing: The execution of the underlying encryption algorithm does not
depend on input of the plaintext or ciphertext. Therefore, if sufficient memory
is available and security is maintained, preprocessing can be used to prepare the
output of the encryption boxes that feed into the XOR functions in Figure 2.11.
When the plaintext or ciphertext input is presented, then the only computation
is a series of XORs. Such a strategy greatly enhances throughput.
• Random access: The ith block of plaintext or ciphertext can be processed in
random-access fashion. With the chaining modes, block Ci cannot be computed
until the i- 1 prior block are computed. There may be applications in
which a ciphertext is stored, and it is desired to decrypt just one block; for such
applications, the random access feature is attractive.
• Provable security: It can be shown that CTR is at least as secure as the other
modes discussed in this section.
• Simplicity: Unlike ECB and CBC modes, CTR mode requires only the
implementation of the encryption algorithm and not the decryption algorithm.
This matters most when the decryption algorithm differs substantially
from the encryption algorithm, as it does for AES. In addition, the decryption
key scheduling need not be implemented.
48
Advantages of C T R Mode (3 of 3)
Provable security
It can be shown that C T R is at least as secure as the other modes discussed in this section
Simplicity
Requires only the implementation of the encryption algorithm and not the decryption algorithm
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
[LIPM00] lists the following advantages of CTR mode.
• Hardware efficiency: Unlike the chaining modes, encryption (or decryption)
in CTR mode can be done in parallel on multiple blocks of plaintext or
ciphertext. For the chaining modes, the algorithm must complete the computation
on one block before beginning on the next block. This limits the maximum
throughput of the algorithm to the reciprocal of the time for one execution of
block encryption or decryption. In CTR mode, the throughput is only limited
by the amount of parallelism that is achieved.
• Software efficiency: Similarly, because of the opportunities for parallel execution
in CTR mode, processors that support parallel features (such as aggressive
pipelining, multiple instruction dispatch per clock cycle, a large number of
registers, and SIMD instructions) can be effectively utilized.
• Preprocessing: The execution of the underlying encryption algorithm does not
depend on input of the plaintext or ciphertext. Therefore, if sufficient memory
is available and security is maintained, preprocessing can be used to prepare the
output of the encryption boxes that feed into the XOR functions in Figure 2.11.
When the plaintext or ciphertext input is presented, then the only computation
is a series of XORs. Such a strategy greatly enhances throughput.
• Random access: The ith block of plaintext or ciphertext can be processed in
random-access fashion. With the chaining modes, block Ci cannot be computed
until the i- 1 prior block are computed. There may be applications in
which a ciphertext is stored, and it is desired to decrypt just one block; for such
applications, the random access feature is attractive.
• Provable security: It can be shown that CTR is at least as secure as the other
modes discussed in this section.
• Simplicity: Unlike ECB and CBC modes, CTR mode requires only the
implementation of the encryption algorithm and not the decryption algorithm.
This matters most when the decryption algorithm differs substantially
from the encryption algorithm, as it does for AES. In addition, the decryption
key scheduling need not be implemented.
49
Summary (1 of 3)
Symmetric encryption principles
Cryptography
Cryptanalysis
Feistel cipher structure
Symmetric block encryption algorithms
Data encryption standard
Triple D E S
Advanced encryption standard
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Chapter 2 summary.
50
Summary (2 of 3)
Random and pseudorandom numbers
The use of random numbers
T R N G s, P R N G s, P R F s
Algorithm design
Stream ciphers and R C 4
Stream cipher structure
R C 4 algorithm
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Chapter 2 summary.
51
Summary (3 of 3)
Cipher block modes of operation
E C B
C B C
C F B
C T R
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Chapter 2 summary.
52
Copyright
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
53
N e
tw o
rk S
e c u rity
E s s e
n tia
ls Applications and Standards
S ixth
E d
itio n
S T A
L L IN
G S
9
10
years
29
10
8
.
5
´
57
192
10
3
.
6
2
´
»
years
10
9.8
ns
2
40
191
´
=
years
36
10
8
.
9
´
77
256
10
2
.
1
2
´
»
years
10
1.8
ns
2
60
255
´
=
years
56
10
8
.
1
´
13
10
16
56
10
2
.
7
2
´
»
years
1.125
ns
2
55
=
38
128
10
4
.
3
2
´
»
years
10
5.3
ns
2
21
127
´
=
years
17
10
3
.
5
´
50
168
10
7
.
3
2
´
»
years
10
5.8
ns
2
33
167
´
=
