W3-NS
akhilesh7593
CH03NetSec6e_accessiblePPT.pptxNetwork Security Essentials: Applications and Standards
Sixth Edition
Chapter 3
Public Key Cryptography and Message Authentication
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
Message Authentication
Encryption protects against passive attack (eavesdropping)
A different requirement is to protect against active attack (falsification of data and transactions)
Protection against such attacks is known as message authentication
Message authentication is a procedure that allows communicating parties to verify that received messages are authentic
The two important aspects are to verify that the contents of the message have not been altered and that the source is authentic
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Encryption protects against passive attack (eavesdropping). A different requirement
is to protect against active attack (falsification of data and transactions).
Protection against such attacks is known as message authentication.
A message, file, document, or other collection of data is said to be authentic
when it is genuine and comes from its alleged source. Message authentication is a
procedure that allows communicating parties to verify that received messages are
authentic. The two important aspects are to verify that the contents of the message
have not been altered and that the source is authentic. We may also wish to
verify a message’s timeliness (it has not been artificially delayed and replayed) and
sequence relative to other messages flowing between two parties. All of these concerns
come under the category of data integrity as described in Chapter 1.
2
Approaches to Message Authentication (1 of 2)
Using conventional encryption
Symmetric encryption alone is not a suitable tool for data authentication
We assume that only the sender and receiver share a key, so only the genuine sender would be able to encrypt a message successfully
The receiver assumes that no alterations have been made and that sequencing is proper if the message includes an error detection code and a sequence number
If the message includes a timestamp, the receiver assumes that the message has not been delayed beyond that normally expected for network transit
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
It would seem possible to perform authentication simply by the use of symmetric
encryption. If we assume that only the sender and receiver share a key (which
is as it should be), then only the genuine sender would be able to encrypt a message
successfully for the other participant, provided the receiver can recognize a
valid message. Furthermore, if the message includes an error-detection code and a
sequence number, the receiver is assured that no alterations have been made and
that sequencing is proper. If the message also includes a timestamp, the receiver is
assured that the message has not been delayed beyond that normally expected for
network transit.
In fact, symmetric encryption alone is not a suitable tool for data authentication.
To give one simple example, in the ECB mode of encryption, if an attacker
reorders the blocks of ciphertext, then each block will still decrypt successfully.
However, the reordering may alter the meaning of the overall data sequence.
Although sequence numbers may be used at some level (e.g., each IP packet), it is
typically not the case that a separate sequence number will be associated with each
b -bit block of plaintext. Thus, block reordering is a threat.
In this section, we examine several approaches to message authentication that do
not rely on encryption. In all of these approaches, an authentication tag is generated
and appended to each message for transmission. The message itself is not encrypted
and can be read at the destination independent of the authentication function at the
destination.
Because the approaches discussed in this section do not encrypt the message,
message confidentiality is not provided. As was mentioned, message encryption by
itself does not provide a secure form of authentication. However, it is possible to
combine authentication and confidentiality in a single algorithm by encrypting a
message plus its authentication tag. Typically, however, message authentication is
provided as a separate function from message encryption.
There is a place for both authentication and encryption in meeting security
requirements.
3
Approaches to Message Authentication (2 of 2)
Without message encryption
An authentication tag is generated and appended to each message for transmission
The message itself is not encrypted and can be read at the destination independent of the authentication function at the destination
Because the message is not encrypted, message confidentiality is not provided
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
It would seem possible to perform authentication simply by the use of symmetric
encryption. If we assume that only the sender and receiver share a key (which
is as it should be), then only the genuine sender would be able to encrypt a message
successfully for the other participant, provided the receiver can recognize a
valid message. Furthermore, if the message includes an error-detection code and a
sequence number, the receiver is assured that no alterations have been made and
that sequencing is proper. If the message also includes a timestamp, the receiver is
assured that the message has not been delayed beyond that normally expected for
network transit.
In fact, symmetric encryption alone is not a suitable tool for data authentication.
To give one simple example, in the ECB mode of encryption, if an attacker
reorders the blocks of ciphertext, then each block will still decrypt successfully.
However, the reordering may alter the meaning of the overall data sequence.
Although sequence numbers may be used at some level (e.g., each IP packet), it is
typically not the case that a separate sequence number will be associated with each
b -bit block of plaintext. Thus, block reordering is a threat.
In this section, we examine several approaches to message authentication that do
not rely on encryption. In all of these approaches, an authentication tag is generated
and appended to each message for transmission. The message itself is not encrypted
and can be read at the destination independent of the authentication function at the
destination.
Because the approaches discussed in this section do not encrypt the message,
message confidentiality is not provided. As was mentioned, message encryption by
itself does not provide a secure form of authentication. However, it is possible to
combine authentication and confidentiality in a single algorithm by encrypting a
message plus its authentication tag. Typically, however, message authentication is
provided as a separate function from message encryption.
There is a place for both authentication and encryption in meeting security
requirements.
4
Figure 3-1: Message Authentication Using a Message Authentication Code (M A C)
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
One authentication technique involves the use
of a secret key to generate a small block of data, known as a message authentication
code (MAC) , that is appended to the message.
This technique assumes that
two communicating parties, say A and B, share a common secret key KAB. When
A has a message to send to B, it calculates the message authentication code as a
function of the message and the key: MACM = F(KAB , M ). The message plus code
are transmitted to the intended recipient. The recipient performs the same calculation
on the received message, using the same secret key, to generate a new message
authentication code. The received code is compared to the calculated code
(Figure 3.1).
If we assume that only the receiver and the sender know the identity
of the secret key, and if the received code matches the calculated code, then the following
statements apply:
1. The receiver is assured that the message has not been altered. If an attacker
alters the message but does not alter the code, then the receiver’s calculation
of the code will differ from the received code. Because the attacker is assumed
not to know the secret key, the attacker cannot alter the code to correspond to
the alterations in the message.
2. The receiver is assured that the message is from the alleged sender. Because
no one else knows the secret key, no one else could prepare a message with a
proper code.
3. If the message includes a sequence number (such as is used with HDLC and
TCP), then the receiver can be assured of the proper sequence, because an
attacker cannot successfully alter the sequence number.
A number of algorithms could be used to generate the code. The NIST specification,
FIPS PUB 113, recommends the use of DES. DES is used to generate an
encrypted version of the message, and the last number of bits of ciphertext are used
as the code. A 16- or 32-bit code is typical.
The process just described is similar to encryption. One difference is that the
authentication algorithm need not be reversible, as it must for decryption. Because
of the mathematical properties of the authentication function, it is less vulnerable to
being broken than encryption.
5
One-Way Hash Functions
Accepts a variable-size message M as input and produces a fixed-size message digest
as output
Does not take a secret key as input
To authenticate a message, the message digest is sent with the message in such a way that the message digest is authentic
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
An alternative to the message authentication code is
the one-way hash function . As with the message authentication code, a hash function
accepts a variable-size message M as input and produces a fixed-size message
digest H(M ) as output. Unlike the MAC, a hash function does not take a secret key
as input. To authenticate a message, the message digest is sent with the message in
such a way that the message digest is authentic.
6
Figure 3-2: Message Authentication Using a One-Way Hash Function
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Figure 3.2 illustrates three ways in which the message can be authenticated.
The message digest can be encrypted using conventional encryption (part a); if
it is assumed that only the sender and receiver share the encryption key, then
authenticity is assured. The message digest can be encrypted using public-key
encryption (part b); this is explained in Section 3.5. The public-key approach
has two advantages: (1) It provides a digital signature as well as message
authentication. (2) It does not require the distribution of keys to communicating
parties.
These two approaches also have an advantage over approaches that encrypt
the entire message in that less computation is required. Nevertheless, there has
been interest in developing a technique that avoids encryption altogether.
Figure 3.2c shows a technique that uses a hash function but no encryption for
message authentication. Because the secret value itself is
not sent, it is not possible for an attacker to modify an intercepted message. As long
as the secret value remains secret, it is also not possible for an attacker to generate
a false message.
A variation on the third technique, called HMAC, is the one adopted for
IP security (described in Chapter 9); it also has been specified for SNMPv3
(Chapter 13).
7
Secure Hash Functions (1 of 3)
Is important not only in message authentication but in digital signatures
Purpose is to produce a “fingerprint” of a file, message, or other block of data
To be useful for message authentication, a hash function H must have the following properties:
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
The purpose of a hash function is to produce a “fingerprint” of a file, message, or
other block of data. To be useful for message authentication, a hash function H
must have the following properties:
1. H can be applied to a block of data of any size.
2. H produces a fixed-length output.
3. H(x ) is relatively easy to compute for any given x , making both hardware and
software implementations practical.
4. For any given code h , it is computationally infeasible to find x such that
H(x ) = h. A hash function with this property is referred to as one-way or
preimage resistant .
5. For any given block x, it is computationally infeasible to find y x with
H(y) = H(x). A hash function with this property is referred to as second preimage
resistant. This is sometimes referred to as weak collision resistant.
6. It is computationally infeasible to find any pair (x, y) such that H(x) = H(y).
A hash function with this property is referred to as collision resistant. This is
sometimes referred to as strong collision resistant.
A hash function that satisfies the first five properties in the preceding list is
referred to as a weak hash function. If the sixth property is also satisfied, then it is
referred to as a strong hash function. The sixth property, collision resistant, protects
against a sophisticated class of attack known as the birthday attack.
8
Secure Hash Functions (2 of 3)
H can be applied to a block of data of any size.
H produces a fixed-length output.
is relatively easy to compute for any given x, making both hardware and software implementations practical.
For any given code h, it is computationally infeasible to
find x such that
A hash function with this
property is referred to as one-way or preimage resistant.
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
The purpose of a hash function is to produce a “fingerprint” of a file, message, or
other block of data. To be useful for message authentication, a hash function H
must have the following properties:
1. H can be applied to a block of data of any size.
2. H produces a fixed-length output.
3. H(x ) is relatively easy to compute for any given x , making both hardware and
software implementations practical.
4. For any given code h , it is computationally infeasible to find x such that
H(x ) = h. A hash function with this property is referred to as one-way or
preimage resistant .
5. For any given block x, it is computationally infeasible to find y x with
H(y) = H(x). A hash function with this property is referred to as second preimage
resistant. This is sometimes referred to as weak collision resistant.
6. It is computationally infeasible to find any pair (x, y) such that H(x) = H(y).
A hash function with this property is referred to as collision resistant. This is
sometimes referred to as strong collision resistant.
A hash function that satisfies the first five properties in the preceding list is
referred to as a weak hash function. If the sixth property is also satisfied, then it is
referred to as a strong hash function. The sixth property, collision resistant, protects
against a sophisticated class of attack known as the birthday attack.
9
Secure Hash Functions (3 of 3)
For any given block x, it is computationally infeasible to
find y x with
A hash function with this
property is referred to as second preimage resistant.
This is sometimes referred to as weak collision resistant.
It is computationally infeasible to find any pair
such that
A hash function with this property
is referred to as collision resistant. This is sometimes referred to as strong collision resistant.
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
The purpose of a hash function is to produce a “fingerprint” of a file, message, or
other block of data. To be useful for message authentication, a hash function H
must have the following properties:
1. H can be applied to a block of data of any size.
2. H produces a fixed-length output.
3. H(x ) is relatively easy to compute for any given x , making both hardware and
software implementations practical.
4. For any given code h , it is computationally infeasible to find x such that
H(x ) = h. A hash function with this property is referred to as one-way or
preimage resistant .
5. For any given block x, it is computationally infeasible to find y x with
H(y) = H(x). A hash function with this property is referred to as second preimage
resistant. This is sometimes referred to as weak collision resistant.
6. It is computationally infeasible to find any pair (x, y) such that H(x) = H(y).
A hash function with this property is referred to as collision resistant. This is
sometimes referred to as strong collision resistant.
A hash function that satisfies the first five properties in the preceding list is
referred to as a weak hash function. If the sixth property is also satisfied, then it is
referred to as a strong hash function. The sixth property, collision resistant, protects
against a sophisticated class of attack known as the birthday attack.
10
Security of Hash Functions
There are two approaches to attacking a secure hash function:
Cryptanalysis
Involves exploiting logical weaknesses in the algorithm
Brute-force attack
The strength of a hash function against this attack depends solely on the length of the hash code produced by the algorithm
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
As with symmetric encryption, there are two approaches to attacking a secure hash
function: cryptanalysis and brute-force attack. As with symmetric encryption algorithms,
cryptanalysis of a hash function involves exploiting logical weaknesses in the
algorithm.
The strength of a hash function against brute-force attacks depends solely on
the length of the hash code produced by the algorithm.
If collision resistance is required (and this is desirable for a general-purpose
secure hash code), then the value 2n/2 determines the strength of the hash code
against brute-force attacks. Van Oorschot and Wiener [VANO94] presented a
design for a $10 million collision search machine for MD5, which has a 128-bit
hash length, that could find a collision in 24 days. Thus, a 128-bit code may be
viewed as inadequate. The next step up, if a hash code is treated as a sequence
of 32 bits, is a 160-bit hash length. With a hash length of 160 bits, the same
search machine would require over four thousand years to find a collision. With
today’s technology, the time would be much shorter, so that 160 bits now
appears suspect.
11
Figure 3-3: Simple Hash Function Using Bitwise XOR
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
All hash functions operate using the following general principles. The input (message,
file, etc.) is viewed as a sequence of n -bit blocks. The input is processed one
block at a time in an iterative fashion to produce an n -bit hash function.
One of the simplest hash functions is the bit-by-bit exclusive-OR (XOR) of
every block.
Figure 3.3 illustrates this operation; it produces a simple parity for each bit
position and is known as a longitudinal redundancy check.
12
The S H A Secure Hash function
S H A was developed by N I S T and published as a federal information processing standard (F I P S 180) in 1993
Was revised in 1995 as S H A-1 and published as F I P S 180-1
The actual standards document is entitled “Secure Hash Standard”
Based on the hash function M D4 and its design closely models M D4
Produces 160-bit hash values
In 2005 N I S T announced the intention to phase out approval of S H A-1 and move to a reliance on S H A-2 by 2010
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
In recent years, the most widely used hash function has been the Secure Hash
Algorithm (SHA). Indeed, because virtually every other widely used hash function
had been found to have substantial cryptanalytic weaknesses, SHA was more or
less the last remaining standardized hash algorithm by 2005. SHA was developed
by the National Institute of Standards and Technology (NIST) and published as a
federal information processing standard (FIPS 180) in 1993. When weaknesses were
discovered in SHA (now known as SHA-0), a revised version was issued as FIPS
180-1 in 1995 and is referred to as SHA-1 . The actual standards document is entitled
“Secure Hash Standard.” SHA is based on the hash function MD4, and its design
closely models MD4.
SHA-1 produces a hash value of 160 bits.
In 2005, NIST announced the intention to phase out approval of SHA-1 and
move to a reliance on SHA-2 by 2010.
13
Table 3-1: Comparison of S H A Parameters
| Blank | SHA-I | SHA-224 | SHA-256 | SHA-384 | SHA-512 |
| Message Digest Size | 160 | 224 | 256 | 384 | 512 |
| Message Size | less than 2 to the sixty fourth power | less than 2 to the sixty fourth power | less than 2 to the sixty fourth power | less than 2 to the 120 eighth power | less than 2 to the 120 eighth power |
| Block Size | 512 | 512 | 512 | 1024 | 1024 |
| Word Size | 32 | 32 | 32 | 64 | 64 |
| Number of Steps | 80 | 64 | 64 | 80 | 80 |
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
In 2002, NIST produced a revised
version of the standard, FIPS 180-2, that defined three new versions of SHA with
hash value lengths of 256, 384, and 512 bits known as SHA-256, SHA-384, and
SHA-512, respectively. Collectively, these hash algorithms are known as SHA-2 .
These new versions have the same underlying structure and use the same types of
modular arithmetic and logical binary operations as SHA-1. A revised document
was issued as FIP PUB 180-3 in 2008, which added a 224-bit version (Table 3.1).
SHA-1 and SHA-2 are also specified in RFC 6234, which essentially duplicates the
material in FIPS 180-3 but adds a C code implementation.
14
Figure 3-4: Message Digest Generation Using S H A-512
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
The algorithm takes as input a message with a maximum length of less than
2128 bits and produces as output a 512-bit message digest. The input is processed in
1024-bit blocks. Figure 3.4 depicts the overall processing of a message to produce a
digest.
15
Figure 3-5: S H A-512 Processing of a Single 1024-Bit Block
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
The heart of the algorithm
is a module that consists of 80 rounds; this module is labeled F in Figure 3.4.
The logic is illustrated in Figure 3.5.
16
S H A-3
Basic requirements that must be satisfied by any candidate for S H A-3
It must be possible to replace S H A-2 with S H A-3 in any application by a simple drop-in substitution. Therefore, S H A-3 must support hash value lengths of 224, 256, 384, and 512 bits.
S H A-3 must preserve the online nature of S H A-2. That is, the algorithm must process comparatively small blocks (512 or 1024 bits) at a time instead of requiring that the entire message be buffered in memory before processing it.
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
SHA-2, particularly the 512-bit version, would appear to provide unassailable security.
However, SHA-2 shares the same structure and mathematical operations
as its predecessors, and this is a cause for concern. Because it would take years to find a
suitable replacement for SHA-2, should it become vulnerable, NIST announced in
2007 a competition to produce the next-generation NIST hash function, which is to
be called SHA-3. Following are the basic requirements that must be satisfied by any
candidate for SHA-3:
1. It must be possible to replace SHA-2 with SHA-3 in any application by a simple
drop-in substitution. Therefore, SHA-3 must support hash value lengths of
224, 256, 384, and 512 bits.
2. SHA-3 must preserve the online nature of SHA-2. That is, the algorithm must
process comparatively small blocks (512 or 1024 bits) at a time instead of
requiring that the entire message be buffered in memory before processing it.
In 2012, NIST selected a winning submission and formally published SHA-3.
A detailed presentation of SHA-3 is provided in Chapter 15.
17
H M A C (1 of 2)
There has been an increased interest in developing a M A C derived from a cryptographic hash code, such as S H A-1
Cryptographic hash functions generally execute faster in software than conventional encryption algorithms such as D E S
Library code for cryptographic hash functions is widely available
A hash function such as S H A-1 was not designed for use as a M A C and cannot be used directly for that purpose because it does not rely on a secret key
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
In recent years, there has been increased interest in developing a MAC derived
from a cryptographic hash code, such as SHA-1. The motivations for this interest
are as follows:
• Cryptographic hash functions generally execute faster in software than conventional
encryption algorithms such as DES.
• Library code for cryptographic hash functions is widely available.
A hash function such as SHA-1 was not designed for use as a MAC and cannot
be used directly for that purpose because it does not rely on a secret key. There have
been a number of proposals for the incorporation of a secret key into an existing hash
algorithm. The approach that has received the most support is HMAC [BELL96a,
BELL96b]. HMAC has been issued as RFC 2104, has been chosen as the mandatory-to-
implement MAC for IP Security, and is used in other Internet protocols, such as
Transport Layer Security (TLS) and Secure Electronic Transaction (SET).
18
H M A C (2 of 2)
There have been a number of proposals for the incorporation of a secret key into an existing hash algorithm
The approach that has received the most support is H M A C.
Has been issued as R F C 2104
Has been chosen as the mandatory-to-implement M A C for I P Security
Is used in other Internet protocols, such as Transport Layer Security (T L S) and Secure Electronic Transaction (S E T)
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
In recent years, there has been increased interest in developing a MAC derived
from a cryptographic hash code, such as SHA-1. The motivations for this interest
are as follows:
• Cryptographic hash functions generally execute faster in software than conventional
encryption algorithms such as DES.
• Library code for cryptographic hash functions is widely available.
A hash function such as SHA-1 was not designed for use as a MAC and cannot
be used directly for that purpose because it does not rely on a secret key. There have
been a number of proposals for the incorporation of a secret key into an existing hash
algorithm. The approach that has received the most support is HMAC [BELL96a,
BELL96b]. HMAC has been issued as RFC 2104, has been chosen as the mandatory-to-
implement MAC for IP Security, and is used in other Internet protocols, such as
Transport Layer Security (TLS) and Secure Electronic Transaction (SET).
19
H M A C Design Objectives (1 of 2)
To use, without modifications, available hash functions --- in particular, hash functions that perform well in software, and for which code is freely and widely available
To allow for easy replace ability of the embedded hash function in case faster or more secure hash functions are found or required
To preserve the original performance of the hash function without incurring a significant degradation
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
RFC 2104 lists the following design objectives for
HMAC.
• To use, without modifications, available hash functions. In particular, hash
functions that perform well in software, and for which code is freely and
widely available
• To allow for easy replaceability of the embedded hash function in case faster
or more secure hash functions are found or required
• To preserve the original performance of the hash function without incurring a
significant degradation
• To use and handle keys in a simple way
• To have a well-understood cryptographic analysis of the strength of the
authentication mechanism based on reasonable assumptions on the embedded
hash function
The first two objectives are important to the acceptability of HMAC. HMAC
treats the hash function as a “black box.” This has two benefits. First, an existing
implementation of a hash function can be used as a module in implementing
HMAC. In this way, the bulk of the HMAC code is prepackaged and ready to use
without modification. Second, if it is ever desired to replace a given hash function
in an HMAC implementation, all that is required is to remove the existing hash
function module and drop in the new module. This could be done if a faster hash
function were desired. More important, if the security of the embedded hash function
were compromised, the security of HMAC could be retained simply by replacing
the embedded hash function with a more secure one
.
The last design objective in the preceding list is, in fact, the main advantage
of HMAC over other proposed hash-based schemes. HMAC can be proven secure
provided that the embedded hash function has some reasonable cryptographic
strengths. We return to this point later in this section, but first we examine the structure
of HMAC.
20
H M A C Design Objectives (2 of 2)
To use and handle keys in a simple way
To have a well understood cryptographic analysis of the strength of the authentication mechanism based on reasonable assumptions on the embedded hash function
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
RFC 2104 lists the following design objectives for
HMAC.
• To use, without modifications, available hash functions. In particular, hash
functions that perform well in software, and for which code is freely and
widely available
• To allow for easy replaceability of the embedded hash function in case faster
or more secure hash functions are found or required
• To preserve the original performance of the hash function without incurring a
significant degradation
• To use and handle keys in a simple way
• To have a well-understood cryptographic analysis of the strength of the
authentication mechanism based on reasonable assumptions on the embedded
hash function
The first two objectives are important to the acceptability of HMAC. HMAC
treats the hash function as a “black box.” This has two benefits. First, an existing
implementation of a hash function can be used as a module in implementing
HMAC. In this way, the bulk of the HMAC code is prepackaged and ready to use
without modification. Second, if it is ever desired to replace a given hash function
in an HMAC implementation, all that is required is to remove the existing hash
function module and drop in the new module. This could be done if a faster hash
function were desired. More important, if the security of the embedded hash function
were compromised, the security of HMAC could be retained simply by replacing
the embedded hash function with a more secure one
.
The last design objective in the preceding list is, in fact, the main advantage
of HMAC over other proposed hash-based schemes. HMAC can be proven secure
provided that the embedded hash function has some reasonable cryptographic
strengths. We return to this point later in this section, but first we examine the structure
of HMAC.
21
Figure 3-6: H M A C Structure
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Figure 3.6 illustrates the overall operation of HMAC.
22
Figure 3-7: Cipher-Based Message Authentication Code (C M A C)
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
The Cipher-based
Message Authentication Code mode of operation is for use with AES and triple
DES. It is specified in NIST Special Publication 800-38B.
23
Counter with Cipher Block Chaining-Message Authentication Code (C C M)
N I S T standard S P 800-38C
Referred to as an authenticated encryption mode
“Authenticated encryption” is a term used to describe encryption systems that simultaneously protect confidentiality and authenticity of communications
A single key is used for both encryption and M A C algorithms
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
The Counter with Cipher Block Chaining-Message Authentication Code (CCM)
mode of operation, defined in NIST SP 800-38C, is referred to as an authenticated
encryption mode. “Authenticated encryption” is a term used to describe encryption
systems that simultaneously protect confidentiality and authenticity (integrity) of
communications. Many applications and protocols require both forms of security,
but until recently the two services have been designed separately.
The key algorithmic ingredients of CCM are the AES encryption algorithm
(Section 2.2), the CTR mode of operation (Section 2.5), and the CMAC authentication
algorithm. A single key K is used for both encryption and MAC algorithms.
24
Figure 3-8: Counter with Cipher Block Chaining-Message Authentication Code (C C M)
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Figure 3.8 illustrates the operation of CCM. For authentication, the input
includes the nonce, the associated data, and the plaintext. This input is formatted as
a sequence of blocks B0 through Br . The first block contains the nonce plus some
formatting bits that indicate the lengths of the N , A , and P elements. This is followed
by zero or more blocks that contain A , followed by zero of more blocks that
contain P. The resulting sequence of blocks serves as input to the CMAC algorithm,
which produces a MAC value with length Tlen , which is less than or equal to the
block length (Figure 3.8a).
For encryption, a sequence of counters is generated that must be independent
of the nonce. The authentication tag is encrypted in CTR mode using the single
counter Ctr0 . The Tlen most significant bits of the output are XORed with the tag
to produce an encrypted tag. The remaining counters are used for the CTR mode
encryption of the plaintext (Figure 2.11). The encrypted plaintext is concatenated
with the encrypted tag to form the ciphertext output (Figure 3.8b).
25
Public-Key Encryption Structure (1 of 2)
First publicly proposed by Diffie and Hellman in 1976
Based on mathematical functions rather than on simple operations on bit patterns
Is asymmetric, involving the use of two separate keys
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Public-key encryption, first publicly proposed by Diffie and Hellman in 1976
[DIFF76], is the first truly revolutionary advance in encryption in literally thousands
of years. Public-key algorithms are based on mathematical functions rather
than on simple operations on bit patterns, such as are used in symmetric encryption
algorithms. More important, public-key cryptography is asymmetric, involving the
use of two separate keys—in contrast to the symmetric conventional encryption,
which uses only one key. The use of two keys has profound consequences in the
areas of confidentiality, key distribution, and authentication.
Before proceeding, we should first mention several common misconceptions
concerning public-key encryption. One is that public-key encryption is more
secure from cryptanalysis than conventional encryption. In fact, the security of any
encryption scheme depends on (1) the length of the key and (2) the computational
work involved in breaking a cipher. There is nothing in principle about either conventional
or public-key encryption that makes one superior to another from the
point of view of resisting cryptanalysis. A second misconception is that public-key
encryption is a general-purpose technique that has made conventional encryption
obsolete. On the contrary, because of the computational overhead of current public-
key encryption schemes, there seems no foreseeable likelihood that conventional
encryption will be abandoned. Finally, there is a feeling that key distribution
is trivial when using public-key encryption, compared to the rather cumbersome
handshaking involved with key distribution centers for conventional encryption.
In fact, some form of protocol is needed, often involving a central agent, and the
procedures involved are no simpler or any more efficient than those required for
conventional encryption.
26
Public-Key Encryption Structure (2 of 2)
Misconceptions:
Public-key encryption is more secure from cryptanalysis than conventional encryption
Public-key encryption is a general-purpose technique that has made conventional encryption obsolete
There is a feeling that key distribution is trivial when using public-key encryption, compared to the rather cumbersome handshaking involved with key distribution centers for conventional encryption
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Public-key encryption, first publicly proposed by Diffie and Hellman in 1976
[DIFF76], is the first truly revolutionary advance in encryption in literally thousands
of years. Public-key algorithms are based on mathematical functions rather
than on simple operations on bit patterns, such as are used in symmetric encryption
algorithms. More important, public-key cryptography is asymmetric, involving the
use of two separate keys—in contrast to the symmetric conventional encryption,
which uses only one key. The use of two keys has profound consequences in the
areas of confidentiality, key distribution, and authentication.
Before proceeding, we should first mention several common misconceptions
concerning public-key encryption. One is that public-key encryption is more
secure from cryptanalysis than conventional encryption. In fact, the security of any
encryption scheme depends on (1) the length of the key and (2) the computational
work involved in breaking a cipher. There is nothing in principle about either conventional
or public-key encryption that makes one superior to another from the
point of view of resisting cryptanalysis. A second misconception is that public-key
encryption is a general-purpose technique that has made conventional encryption
obsolete. On the contrary, because of the computational overhead of current public-
key encryption schemes, there seems no foreseeable likelihood that conventional
encryption will be abandoned. Finally, there is a feeling that key distribution
is trivial when using public-key encryption, compared to the rather cumbersome
handshaking involved with key distribution centers for conventional encryption.
In fact, some form of protocol is needed, often involving a central agent, and the
procedures involved are no simpler or any more efficient than those required for
conventional encryption.
27
Figure 3-9: Public-Key Cryptography
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
A public-key encryption scheme has six ingredients (Figure 3.9a).
• Plaintext: This is the readable message or data that is fed into the algorithm as
input.
• Encryption algorithm: The encryption algorithm performs various transformations
on the plaintext.
• Public and private key: This is a pair of keys that have been selected so that if
one is used for encryption, the other is used for decryption. The exact transformations
performed by the encryption algorithm depend on the public or
private key that is provided as input.
• Ciphertext: This is the scrambled message produced as output. It depends on
the plaintext and the key. For a given message, two different keys will produce
two different ciphertexts.
• Decryption algorithm: This algorithm accepts the ciphertext and the matching
key and produces the original plaintext.
As the names suggest, the public key of the pair is made public for others to
use, while the private key is known only to its owner. A general-purpose public-key
cryptographic algorithm relies on one key for encryption and a different but related
key for decryption.
The key used in conventional encryption is typically referred to as a secret
key . The two keys used for public-key encryption are referred to as the public key
and the private key . Invariably, the private key is kept secret, but it is referred
to as a private key rather than a secret key to avoid confusion with conventional
encryption.
28
Applications for Public-Key Cryptosystems
Public-key systems are characterized by the use of a cryptographic type of algorithm with two keys, one held private and one available publicly
Depending on the application, the sender uses either the sender’s private key, the receiver’s public key, or both to perform some type of cryptographic function
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Before proceeding, we need to clarify one aspect of public-key cryptosystems that
is otherwise likely to lead to confusion. Public-key systems are characterized by
the use of a cryptographic type of algorithm with two keys, one held private and
one available publicly. Depending on the application, the sender uses either the
sender’s private key, the receiver’s public key, or both to perform some type of
cryptographic function. In broad terms, we can classify the use of public-key cryptosystems
into three categories:
• Encryption/decryption: The sender encrypts a message with the recipient’s
public key.
• Digital signature: The sender “signs” a message with its private key. Signing
is achieved by a cryptographic algorithm applied to the message or to a small
block of data that is a function of the message.
• Key exchange: Two sides cooperate to exchange a session key. Several different
approaches are possible, involving the private key(s) of one or both
parties.
29
Table 3-2: Applications for Public-Key Cryptosystems
| Algorithm | Encryption/Decryption | Digital Signature | Key Exchange |
| RSA | Yes | Yes | Yes |
| Diffie-Hellman | No | No | Yes |
| DSS | No | Yes | No |
| Elliptic Curve | Yes | Yes | Yes |
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Some algorithms are suitable for all three applications, whereas others can be
used only for one or two of these applications. Table 3.2 indicates the applications
supported by the algorithms discussed in this chapter: RSA and Diffie–Hellman.
This table also includes the Digital Signature Standard (DSS) and elliptic-curve
cryptography, also mentioned later in this chapter.
One general observation can be made at this point. Public-key algorithms
require considerably more computation than symmetric algorithms for comparable
security and a comparable plaintext length. Accordingly, public-key algorithms
are used only for short messages or data blocks, such as to encrypt a secret key
or PIN.
30
Figure 3-10: The R S A Algorithm
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
The two most widely used public-key algorithms are RSA and Diffie–Hellman.
We look at both of these in this section and then briefly introduce two other
algorithms.
One of the first public-key schemes was developed in 1977 by Ron Rivest, Adi
Shamir, and Len Adleman at MIT and first published in 1978 [RIVE78]. The
RSA scheme has since that time reigned supreme as the most widely accepted and
implemented approach to public-key encryption. RSA is a block cipher in which the
plaintext and ciphertext are integers between 0 and n - 1 for some n.
Figure 3.10 summarizes the RSA algorithm.
31
Figure 3-11: Example of R S A Algorithm
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
An example, from [SING99], is shown in Figure 3.11.
32
Security Considerations
The security of R S A depends on it being used in such a way as to counter potential attacks
Possible attack approaches are:
Mathematical attacks
Timing attacks
Chosen cipher text attacks
To counter sophisticated chosen cipher text attacks, R S A Security Inc. recommends modifying the plaintext using a procedure known as optimal asymmetric encryption padding (O A E P)
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
The security of RSA depends on it being used in such a
way as to counter potential attacks. Four possible attack approaches are as follows:
■ Mathematical attacks: There are several approaches, all equivalent in effort to
factoring the product of two primes. The defense against mathematical attacks
is to use a large key size. Thus, the larger the number of bits in d , the better.
However, because the calculations involved, both in key generation and in encryption/
decryption, are complex, the larger the size of the key, the slower the
system will run. SP 800-131A (Transitions: Recommendation for Transitioning
the Use of Cryptographic Algorithms and Key Lengths , November 2015) recommends
the use of a 2048-bit key size. A recent report from the European
Union Agency for Network and Information Security (Algorithms, key size
and parameters report—2014 , November 2014) recommends a 3072-bit key
length. Either of these lengths should provide adequate security for a considerable
time into the future.
■ Timing attacks: These depend on the running time of the decryption algorithm.
Various approaches to mask the time required so as to thwart attempts
to deduce key size have been suggested, such as introducing a random delay.
■ Chosen ciphertext attacks: This type of attack exploits properties of the RSA
algorithm by selecting blocks of data that, when processed using the target’s
private key, yield information needed for cryptanalysis. These attacks can be
thwarted by suitable padding of the plaintext.
To counter sophisticated chosen ciphertext attacks, RSA Security Inc., a
leading RSA vendor and former holder of the RSA patent, recommends modifying
the plaintext using a procedure known as optimal asymmetric encryption padding
(OAEP). A full discussion of the threats and OAEP are beyond our scope;
see [POIN02] for an introduction and [BELL94a] for a thorough analysis. Here, we
simply summarize the OAEP procedure.
33
Figure 3-12: Encryption Using Optimal Asymmetric Encryption Padding (O A E P)
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Figure 3.12 depicts OAEP encryption.
34
Diffie-Hellman Key Exchange
First published public-key algorithm
A number of commercial products employ this key exchange technique
Purpose of the algorithm is to enable two users to exchange a secret key securely that then can be used for subsequent encryption of messages
The algorithm itself is limited to the exchange of the keys
Depends for its effectiveness on the difficulty of computing discrete logarithms
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
The first published public-key algorithm appeared in the seminal paper by Diffie
and Hellman that defined public-key cryptography [DIFF76] and is generally
referred to as the Diffie–Hellman key exchange . A number of commercial products
employ this key exchange technique.
The purpose of the algorithm is to enable two users to exchange a secret key
securely that then can be used for subsequent encryption of messages. The algorithm
itself is limited to the exchange of the keys.
The Diffie–Hellman algorithm depends for its effectiveness on the difficulty
of computing discrete logarithms.
35
Figure 3-13: Diffie-Hellman Key Exchange
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
The Diffie–Hellman key exchange is summarized in Figure 3.13.
36
Figure 3-14: Man-In-The-Middle Attack
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
The protocol depicted in Figure 3.13 is insecure
against a man-in-the-middle attack. Suppose Alice and Bob wish to exchange keys,
and Darth is the adversary. The attack proceeds as follows (Figure 3.14).
The key exchange protocol is vulnerable to such an attack because it does not
authenticate the participants. This vulnerability can be overcome with the use of
digital signatures and public-key certificates; these topics are explored later in this
chapter and in Chapter 4.
37
Digital Signature Standard (D S S)
F I P S P U B 186
Makes use of the S H A-1 and presents a new digital signature technique, the Digital Signature Algorithm (D S A)
Originally proposed in 1991 and revised in 1993 and again in 1996
Uses an algorithm that is designed to provide only the digital signature function
Unlike R S A, it cannot be used for encryption or key exchange
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
The National Institute of Standards and Technology
(NIST) has published Federal Information Processing Standard FIPS PUB 186,
known as the Digital Signature Standard (DSS) . The DSS makes use of the SHA-1
and presents a new digital signature technique, the Digital Signature Algorithm
(DSA). The DSS was originally proposed in 1991 and revised in 1993 in response to
public feedback concerning the security of the scheme. There was a further minor revision
in 1996. The DSS uses an algorithm that is designed to provide only the digital
signature function. Unlike RSA, it cannot be used for encryption or key exchange.
38
Digital Signatures (1 of 2)
N I S T F I P S P U B 186-4 (Digital Signature Standard (D S S)) defines a digital signature as: “the result of a cryptographic transformation of data that, when properly implemented, provides a mechanism for verifying origin authentication, data integrity, and signatory non-repudiation”
Thus, a digital signature is a data-dependent bit pattern, generated by an agent as a function of a file, message, or other form of data block
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
NIST FIPS PUB 186-4 [Digital Signature Standard (DSS) , July 2013] defines a digital
signature as follows: The result of a cryptographic transformation of data that,
when properly implemented, provides a mechanism for verifying origin authentication,
data integrity, and signatory non-repudiation.
Thus, a digital signature is a data-dependent bit pattern, generated by an agent
as a function of a file, message, or other form of data block. Another agent can access
the data block and its associated signature and verify that (1) the data block has
been signed by the alleged signer and that (2) the data block has not been altered
since the signing. Further, the signer cannot repudiate the signature.
FIPS 186-4 specifies the use of one of three digital signature algorithms:
■ Digital Signature Algorithm (DSA): The original NIST-approved algorithm,
which is based on the difficulty of computing discrete logarithms.
■ RSA Digital Signature Algorithm: Based on the RSA public-key algorithm.
■ Elliptic Curve Digital Signature Algorithm (ECDSA): Based on elliptic curve
cryptography.
In this section, we provide a brief overview of the digital signature process,
then describe the RSA digital signature algorithm.
39
Digital Signatures (2 of 2)
F I P S 186-4 specifies the use of one of three digital signature algorithms:
Digital signature algorithm (D S A)
R S A digital signature algorithm
Elliptic curve digital signature algorithm (E C D S A)
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
NIST FIPS PUB 186-4 [Digital Signature Standard (DSS) , July 2013] defines a digital
signature as follows: The result of a cryptographic transformation of data that,
when properly implemented, provides a mechanism for verifying origin authentication,
data integrity, and signatory non-repudiation.
Thus, a digital signature is a data-dependent bit pattern, generated by an agent
as a function of a file, message, or other form of data block. Another agent can access
the data block and its associated signature and verify that (1) the data block has
been signed by the alleged signer and that (2) the data block has not been altered
since the signing. Further, the signer cannot repudiate the signature.
FIPS 186-4 specifies the use of one of three digital signature algorithms:
■ Digital Signature Algorithm (DSA): The original NIST-approved algorithm,
which is based on the difficulty of computing discrete logarithms.
■ RSA Digital Signature Algorithm: Based on the RSA public-key algorithm.
■ Elliptic Curve Digital Signature Algorithm (ECDSA): Based on elliptic curve
cryptography.
In this section, we provide a brief overview of the digital signature process,
then describe the RSA digital signature algorithm.
40
Elliptic-Curve Cryptography (E C C)
Technique is based on the use of a mathematical construct known as the elliptic curve
Principal attraction of E C C compared to R S A is that it appears to offer equal security for a far smaller bit size, thereby reducing processing overhead
The confidence level in E C C is not yet as high as that in R S A
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
The vast majority of the products and standards
that use public-key cryptography for encryption and digital signatures use RSA.
The bit length for secure RSA use has increased over recent years, and this has
put a heavier processing load on applications using RSA. This burden has ramifications,
especially for electronic commerce sites that conduct large numbers of secure
transactions. Recently, a competing system has begun to challenge RSA: elliptic
curve cryptography (ECC) . Already, ECC is showing up in standardization efforts,
including the IEEE P1363 Standard for Public-Key Cryptography.
The principal attraction of ECC compared to RSA is that it appears to offer
equal security for a far smaller bit size, thereby reducing processing overhead. On
the other hand, although the theory of ECC has been around for some time, it is
only recently that products have begun to appear and that there has been sustained
cryptanalytic interest in probing for weaknesses. Thus, the confidence level in ECC
is not yet as high as that in RSA.
ECC is fundamentally more difficult to explain than either RSA or Diffie–
Hellman, and a full mathematical description is beyond the scope of this book.
The technique is based on the use of a mathematical construct known as the
elliptic curve.
41
Figure 3-15: Simplified Depiction of Essential Elements of Digital Signature
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Figure 3.15 is a generic model of the process of making and using digital signatures.
All of the digital signature schemes in FIPS 186-4 have this structure. Suppose that
Bob wants to send a message to Alice. Although it is not important that the message
be kept as a secret, he wants Alice to be certain that the message is indeed
from him. For this purpose, Bob uses a secure hash function, such as SHA-512, to
generate a hash value for the message. That hash value, together with Bob’s private
key, serve as input to a digital signature generation algorithm that produces a short
block that functions as a digital signature. Bob sends the message with the signature
attached. When Alice receives the message plus signature, she (1) calculates
a hash value for the message and (2) provides the hash value and Bob’s public key
as inputs to a digital signature verification algorithm. If the algorithm returns the
result that the signature is valid, Alice is assured that the message must have been
signed by Bob. No one else has Bob’s private key and therefore no one else could
have created a signature that could be verified for this message with Bob’s public
key. In addition, it is impossible to alter the message without access to Bob’s private
key, so the message is authenticated both in terms of source and in terms of
data integrity.
It is important to emphasize that the encryption process just described does
not provide confidentiality. That is, the message being sent is safe from alteration,
but not safe from eavesdropping. This is obvious in the case of a signature based
on a portion of the message, because the rest of the message is transmitted in
the clear. Even in the case of complete encryption, there is no protection of confidentiality
because any observer can decrypt the message by using the sender’s
public key.
42
Figure 13-16: R S A-P S S Encoding and Signature Generation
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
The essence of the RSA digital signature algorithm is to encrypt the hash of the
message to be signed using RSA. However, as with the use of RSA for encryption of
keys or short messages, the RSA digital signature algorithm first modifies the hash
value to enhance security. There are several approaches to this, one of which is the
RSA Probabilistic Signature Scheme (RSA-PSS). RSA-PSS is the latest of the RSA
schemes and the one that RSA Laboratories recommends as the most secure of the
RSA digital signature schemes. We provide a brief overview here; for more detail
see [STAL16].
Figure 3.16 illustrates the RSS-PSS signature generation process.
The objective with this algorithm is to make it more difficult for an adversary
to find another message that maps to the same message digest as a given message or
to find two messages that map to the same message digest. Because the salt changes
with every use, signing the same message twice using the same private key will yield
two different signatures. This is an added measure of security.
43
Summary (1 of 3)
Approaches to message authentication
Authentication using conventional encryption
Message authentication without message encryption
Secure hash functions
Hash function requirements
Security of hash functions
Simple hash functions
The S H A secure hash function
S H A-3
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Chapter 3 summary.
44
Summary (2 of 3)
Digital signatures
Digital signature generation and verification
R S A digital signature algorithm
Message authentication codes
H M A C
M A C s based on block ciphers
Public-key cryptography principles
Public-key encryption structure
Applications for public-key cryptosystems
Requirements for public-key cryptography
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Chapter 3 summary.
45
Summary (3 of 3)
Public-key cryptography algorithms
The R S A public-key encryption algorithm
Diffie-Hellman key exchange
Other public-key cryptography algorithms
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
Chapter 3 summary.
46
Copyright
Copyright © 2017 Pearson Education, Inc. All Rights Reserved
47
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
(
)
M
H
(
)
x
H
(
)
.
h
x
H
=
(
)
(
)
x
H
y
H
=
(
)
y
x
,
(
)
(
)
.
y
H
x
H
=
64
2
<
64
2
<
128
2
<
128
2
<
