• Home

Week 8 Discussion Post

Cryptography and Network Security:

Principles and Practice
Eighth Edition

Chapter 9

Public Key Cryptography and R S A

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 9.1 Terminology Related to Asymmetric

Encryption

Asymmetric Keys

Two related keys, a public key and a private key, that are used to perform

complementary operations, such as encryption and decryption or signature generation

and signature verification.

Public Key Certificate

A digital document issued and digitally signed by the private key of a Certification

Authority that binds the name of a subscriber to a public key. The certificate indicates

that the subscriber identified in the certificate has sole control and access to the

corresponding private key.

Public Key (Asymmetric) Cryptographic Algorithm

A cryptographic algorithm that uses two related keys, a public key and a private key.

The two keys have the property that deriving the private key from the public key is

computationally infeasible.

Public Key Infrastructure (PKI)

A set of policies, processes, server platforms, software and workstations used for the

purpose of administering certificates and public-private key pairs, including the ability to

issue, maintain, and revoke public key certificates.

Source: Glossary of Key Information Security Terms, NISTIR 7298.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Misconceptions Concerning Public-

Key Encryption

• Public-key encryption is more secure from cryptanalysis

than symmetric encryption

• Public-key encryption is a general-purpose technique that

has made symmetric encryption obsolete

• There is a feeling that key distribution is trivial when using

public-key encryption, compared to the cumbersome

handshaking involved with key distribution centers for

symmetric encryption

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Principles of Public-Key Cryptosystems

• The concept of public-key cryptography evolved from an attempt

to attack two of the most difficult problems associated with

symmetric encryption:

• Key distribution

– How to have secure communications in general without

having to trust a K D C with your key

• Digital signatures

– How to verify that a message comes intact from the claimed

sender

• W hitfield Diffie and Martin Hellman from Stanford University

achieved a breakthrough in 1976 by coming up with a method

that addressed both problems and was radically different from

all previous approaches to cryptography

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Public-Key Cryptosystems

• A public-key encryption scheme has six ingredients:

• Plaintext

– The readable message or data that is fed into the algorithm as
input

• Encryption algorithm

– Performs various transforma-tions on the plaintext

• Public key

– Used for encryption or decryption

• Private key

– Used for encryption or decryption

• Ciphertext

– The scrambled message produced as output

• Decryption algorithm

– Accepts the ciphertext and the matching key and produces
the original plaintext

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 9.1 Public-Key Cryptography
(1 of 2)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 9.1 Public-Key Cryptography (2 of 2)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 9.2 Conventional and Public-

key Encryption

Conventional Encryption Public-Key Encryption

Needed to Work:

1. The same algorithm with the same key is
used for encryption and decryption.

2. The sender and receiver must share the

algorithm and the key.

Needed to Work:

1. One algorithm is used for encryption and a
related algorithm for decryption with a pair of
keys, one for encryption and one for

decryption.
2. The sender and receiver must each have one

of the matched pair of keys (not the same
one).

Needed for Security:

1. The key must be kept secret.
2. It must be impossible or at least impractical

to decipher a message if the key is kept

secret.
3. Knowledge of the algorithm plus samples of

ciphertext must be insufficient to determine
the key.

Needed for Security:

1. One of the two keys must be kept secret.
2. It must be impossible or at least impractical

to decipher a message if one of the keys is

kept secret.
3. Knowledge of the algorithm plus one of the

keys plus samples of ciphertext must be
insufficient to determine the other key.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Public-Key Cryptosystem: Confidentiality

Figure 9.2 Public-Key Cryptosystem: Confidentiality

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Public-Key Cryptosystem: Authentication

Figure 9.3 Public-Key Cryptosystem: Authentication

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Public-Key Cryptosystem:

Authentication and Secrecy

Figure 9.4 Public-Key Cryptosystem: Authentication and

Secrecy

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Applications for Public-Key

Cryptosystems

• Public-key cryptosystems can be classified 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

• Key exchange

– Two sides cooperate to exchange a session key

• Some algorithms are suitable for all three applications, whereas

others can be used only for one or two

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 9.3 Applications for Public-Key

Cryptosystems

Algorithm Encryption/Decryption Digital

Signature

Key Exchange

RSA Yes Yes Yes

Elliptic Curve Yes Yes Yes

Diffie–Hellman No No Yes

DSS No Yes No

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Public-Key Requirements (1 of 2)

• Conditions that these algorithms must fulfill:

– It is computationally easy for a party B to generate a pair

(public-key P Ub, private key P Rb)

– It is computationally easy for a sender A, knowing the public

key and the message to be encrypted, to generate the

corresponding ciphertext

– It is computationally easy for the receiver B to decrypt the

resulting ciphertext using the private key to recover the

original message

– It is computationally infeasible for an adversary, knowing the

public key, to determine the private key

– It is computationally infeasible for an adversary, knowing the

public key and a ciphertext, to recover the original message

– The two keys can be applied in either order

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Public-Key Requirements (2 of 2)

• Need a trap-door one-way function

– A one-way function is one that maps a domain into a range such

that every function value has a unique inverse, with the condition

that the calculation of the function is easy, whereas the calculation

of the inverse is infeasible

▪ Y = f(X) easy

▪ X = f–1(Y) infeasible

• A trap-door one-way function is a family of invertible functions fk, such

that

– Y = fk(X) easy, if k and X are known

– X = fk
–1(Y) easy, if k and Y are known

– X = fk
–1(Y) infeasible, if Y known but k not known

• A practical public-key scheme depends on a suitable trap-door one-

way function

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Public-Key Cryptanalysis

• A public-key encryption scheme is vulnerable to a brute-force attack

– Countermeasure: use large keys

– Key size must be small enough for practical encryption and
decryption

– Key sizes that have been proposed result in encryption/decryption
speeds that are too slow for general-purpose use

– Public-key encryption is currently confined to key management
and signature applications

• Another form of attack is to find some way to compute the private key
given the public key

– To date it has not been mathematically proven that this form of
attack is infeasible for a particular public-key algorithm

• Finally, there is a probable-message attack

– This attack can be thwarted by appending some random bits to
simple messages

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Rivest-Shamir-Adleman (R S A)

Algorithm

• Developed in 1977 at M I T by Ron Rivest, Adi Shamir &

Len Adleman

• Most widely used general-purpose approach to public-key

encryption

• Is a cipher in which the plaintext and ciphertext are

integers between 0 and n – 1 for some n

– A typical size for n is 1024 bits, or 309 decimal digits

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

R S A Algorithm

• RSA makes use of an expression with exponentials

• Plaintext is encrypted in blocks with each block having a binary

value less than some number n

• Encryption and decryption are of the following form, for some

plaintext block M and ciphertext block C

C = Me mod n

M = Cd mod n = (Me)d mod n = Med mod n

• Both sender and receiver must know the value of n

• The sender knows the value of e, and only the receiver knows

the value of d

• This is a public-key encryption algorithm with a public key of

PU={e,n} and a private key of PR={d,n}

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Algorithm Requirements

• For this algorithm to be satisfactory for public-key

encryption, the following requirements must be met:

1. It is possible to find values of e, d, n such that Med mod

n = M for all M < n

2. It is relatively easy to calculate Me mod n and Cd mod n

for all values of M < n

3. It is infeasible to determine d given e and n

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 9.5 The R S A Algorithm

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Example of R S A Algorithm

Figure 9.6 Example of R S A Algorithm

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 9.7 R S A Processing of

Multiple Blocks (1 of 2)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 9.7 R S A Processing of

Multiple Blocks (2 of 2)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Exponentiation in Modular Arithmetic

• Both encryption and decryption in RSA involve raising an

integer to an integer power, mod n

• Can make use of a property of modular arithmetic:

[(a mod n) x (b mod n)] mod n =(a x b) mod n

• With RSA you are dealing with potentially large exponents

so efficiency of exponentiation is a consideration

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 9.8 Algorithm for Computing

ab mod n

Note: The integer b is expressed as a binary number bkbk − 1…b0

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 9.4 Result of the Fast Modular

Exponentiation Algorithm for ab mod n, where a

= 7, b = 560 = 1000110000, and n = 561

I 9 8 7 6 5 4 3 2 1 0

Bi 1 0 0 0 1 1 0 0 0 0

C 1 2 4 8 17 35 70 140 280 560

F 7 49 157 526 160 241 298 166 67 1

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Efficient Operation Using the Public

Key

• To speed up the operation of the R S A algorithm using the

public key, a specific choice of e is usually made

• The most common choice is 65537 (216 + 1)

– Two other popular choices are e=3 and e=17

– Each of these choices has only two 1 bits, so the

number of multiplications required to perform

exponentiation is minimized

– With a very small public key, such as e = 3, R S A

becomes vulnerable to a simple attack

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Efficient Operation Using the Private

Key

• Decryption uses exponentiation to power d

– A small value of d is vulnerable to a brute-force attack

and to other forms of cryptanalysis

• Can use the Chinese Remainder Theorem (C R T) to speed

up computation

– The quantities d mod (p – 1) and d mod (q – 1) can be

precalculated

– End result is that the calculation is approximately four

times as fast as evaluating M = Cd mod n directly

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Key Generation

• Before the application of the public-key cryptosystem each

participant must generate a pair of keys:

– Determine two prime numbers p and q

– Select either e or d and calculate the other

• Because the value of n = pq will be known to any potential

adversary, primes must be chosen from a sufficiently large

set

– The method used for finding large primes must be

reasonably efficient

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Procedure for Picking a Prime

Number

• Pick an odd integer n at random

• Pick an integer a < n at random

• Perform the probabilistic primality test with a as a

parameter. If n fails the test, reject the value n and go to

step 1

• If n has passed a sufficient number of tests, accept n;

otherwise, go to step 2

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

The Security of R S A

• Five possible approaches to attacking RSA are:

– Brute force

▪ Involves trying all possible private keys

– Mathematical attacks

▪ There are several approaches, all equivalent in effort to
factoring the product of two primes

– Timing attacks

▪ These depend on the running time of the decryption
algorithm

– Hardware fault-based attack

▪ This involves inducing hardware faults in the processor
that is generating digital signatures

– Chosen ciphertext attacks

▪ This type of attack exploits properties of the RSA
algorithm

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Factoring Problem

• We can identify three approaches to attacking RSA

mathematically:

– Factor n into its two prime factors. This enables

calculation of ø(n) = (p – 1) x (q – 1), which in turn

enables determination of d = e-1 (mod ø(n))

– Determine ø(n) directly without first determining p and

q. Again this enables determination of d = e-1 (mod

ø(n))

– Determine d directly without first determining ø(n)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Timing Attacks

• Paul Kocher, a cryptographic consultant, demonstrated

that a snooper can determine a private key by keeping

track of how long a computer takes to decipher messages

• Are applicable not just to RSA but to other public-key

cryptography systems

• Are alarming for two reasons:

– It comes from a completely unexpected direction

– It is a ciphertext-only attack

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Countermeasures

• Constant exponentiation time

– Ensure that all exponentiations take the same amount
of time before returning a result; this is a simple fix but
does degrade performance

• Random delay

– Better performance could be achieved by adding a
random delay to the exponentiation algorithm to
confuse the timing attack

• Blinding

– Multiply the ciphertext by a random number before
performing exponentiation; this process prevents the
attacker from knowing what ciphertext bits are being
processed inside the computer and therefore prevents
the bit-by-bit analysis essential to the timing attack

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Fault-Based Attack

• An attack on a processor that is generating R S A digital

signatures

– Induces faults in the signature computation by reducing the

power to the processor

– The faults cause the software to produce invalid signatures

which can then be analyzed by the attacker to recover the

private key

• The attack algorithm involves inducing single-bit errors and

observing the results

• W hile worthy of consideration, this attack does not appear to be

a serious threat to R S A

– It requires that the attacker have physical access to the

target machine and is able to directly control the input power

to the processor

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Chosen Ciphertext Attack (C CA)

• The adversary chooses a number of ciphertexts and is

then given the corresponding plaintexts, decrypted with the

target’s private key

– Thus the adversary could select a plaintext, encrypt it

with the target’s public key, and then be able to get the

plaintext back by having it decrypted with the private

key

– The adversary exploits properties of R S A and selects

blocks of data that, when processed using the target’s

private key, yield information needed for cryptanalysis

• To counter such attacks, R S A Security Inc. recommends

modifying the plaintext using a procedure known as

optimal asymmetric encryption padding (O A E P)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 9.9 Encryption Using Optimal

Asymmetric Encryption Padding

(O A E P)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Summary

• Present an overview of the basic principles of public-key

cryptosystems

• Explain the two distinct uses of public-key cryptosystems

• List and explain the requirements for a public-key cryptosystem

• Present an overview of the R S A algorithm

• Understand the timing attack

• Summarize the relevant issues related to the complexity of

algorithms

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright

This work is protected by United States copyright laws and is

provided solely for the use of instructors in teaching their

courses and assessing student learning. Dissemination or sale of

any part of this work (including on the World Wide Web) will

destroy the integrity of the work and is not permitted. The work

and materials from it should never be made available to students

except by instructors using the accompanying text in their

classes. All recipients of this work are expected to abide by these

restrictions and to honor the intended pedagogical purposes and

the needs of other instructors who rely on these materials.

Week 8 Discussion Post

Cryptography and Network Security:

Principles and Practice
Eighth Edition

Chapter 10

Other Public-Key Cryptosystems

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Diffie-Hellman Key Exchange

• First published public-key algorithm

• A number of commercial products employ this key

exchange technique

• Purpose is to enable two users to securely exchange a key

that can then be used for subsequent symmetric

encryption of messages

• The algorithm itself is limited to the exchange of secret

values

• Its effectiveness depends on the difficulty of computing

discrete logarithms

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 10.1 The Diffie–Hellman Key

Exchange

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 10.2 Man-in-the-Middle Attack

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

ElGamal Cryptography

• Announced in 1984 by T. Elgamal

• Public-key scheme based on discrete logarithms closely

related to the Diffie-Hellman technique

• Used in the digital signature standard (DSS) and the

S/MIME e-mail standard

• Global elements are a prime number q and a which is a

primitive root of q

• Security is based on the difficulty of computing discrete

logarithms

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 10.3 The ElGamal

Cryptosystem

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Elliptic Curve Arithmetic

• Most of the products and standards that use public-key

cryptography for encryption and digital signatures use RSA

– The key length for secure RSA use has increased over

recent years and this has put a heavier processing load

on applications using RSA

• Elliptic curve cryptography (ECC) is showing up in

standardization efforts including the IEEE P1363 Standard

for Public-Key Cryptography

• Principal attraction of ECC is that it appears to offer equal

security for a far smaller key size

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Abelian Group

• A set of elements with a binary operation, denoted by •,

that associates to each ordered pair (a, b) of elements in G

an element (a • b) in G, such that the following axioms are

obeyed:

(A1) Closure: If a and b belong to G, then a • b is

also in G

(A2) Associative: a • (b • c) = (a • b) • c for all a, b, c

in G

(A3) Identity element: There is an element e in G such

that a • e = e • a = a for all a in G

(A4) Inverse element: For each a in G there is an element

a′ in G such that a • a′ = a′ • a = e

(A5) Commutative: a • b = b • a for all a, b in G

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 10.4 Example of Elliptic

Curves

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Elliptic Curves Over Zp

• Elliptic curve cryptography uses curves whose variables and

coefficients are finite

• Two families of elliptic curves are used in cryptographic

applications:

• Prime curves over Zp

– Use a cubic equation in which the variables and coefficients

all take on values in the set of integers from 0 through p-1

and in which calculations are performed modulo p

– Best for software applications

• Binary curves over GF(2m)

– Variables and coefficients all take on values in GF(2m) and

in calculations are performed over GF(2m)

– Best for hardware applications

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 10.1 Points (other than O) on the

Elliptic Curve E23(1, 1)

(0, 1) (6, 4) (12, 19)

(0, 22) (6, 19) (13, 7)

(1, 7) (7, 11) (13, 16)

(1, 16) (7, 12) (17, 3)

(3, 10) (9, 7) (17, 20)

(3, 13) (9, 16) (18, 3)

(4, 0) (11, 3) (18, 20)

(5, 4) (11, 20) (19, 5)

(5, 19) (12, 4) (19, 18)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 10.5 The Elliptic Curve

E23(1, 1)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Elliptic Curves Over GF(2m)

• Use a cubic equation in which the variables and

coefficients all take on values in GF(2m) for some number

m

• Calculations are performed using the rules of arithmetic in

GF(2m)

• The form of cubic equation appropriate for cryptographic

applications for elliptic curves is somewhat different for

GF(2m) than for Zp

– It is understood that the variables x and y and the

coefficients a and b are elements of GF(2m) and that

calculations are performed in GF(2m)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 10.2 Points (other than O) on

the Elliptic Curve E2
4(g4, 1)

(0, 1) (g5, g3) (g9, g13)

(1, g6) (g5, g11) (g10, g)

(1, g13) (g6, g8) (g10, g8)

(g3, g8) (g6, g14) (g12, 0)

(g3, g13) (g9, g10) (g12, g12)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 10.6 The Elliptic Curve

E2
4(g4, 1)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Elliptic Curve Cryptography (ECC)

• Addition operation in ECC is the counterpart of modular

multiplication in RSA

• Multiple addition is the counterpart of modular

exponentiation

• To form a cryptographic system using elliptic curves, we

need to find a “hard problem” corresponding to factoring

the product of two primes or taking the discrete logarithm

– Q=kP, where Q, P belong to a prime curve

– Is “easy” to compute Q given k and P

– But “hard” to find k given Q, and P

– Known as the elliptic curve logarithm problem

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 10.7 ECC Diffie–Hellman Key

Exchange

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Security of Elliptic Curve

Cryptography

• Depends on the difficulty of the elliptic curve logarithm

problem

• Fastest known technique is “Pollard rho method”

• Compared to factoring, can use much smaller key sizes

than with RSA

• For equivalent key lengths computations are roughly

equivalent

• Hence, for similar security ECC offers significant

computational advantages

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 10.3 Comparable Key Sizes in

Terms of Computational Effort for

Cryptanalysis (NIST SP-800-57)

Symmetric Key

Algorithms

Diffie–Hellman, Digital

Signature Algorithm

RSA

(size of n in bits)

ECC (modulus size

in bits)

80 L = 1024

N = 160
1024 160–223

112 L = 2048

N = 224
2048 224–255

128 L = 3072

N = 256
3072 256–383

192 L = 7680

N = 384
7680 384–511

256 L = 15,360

N = 512
15,360 512 +

Note: L = size of public key, N = size of private key.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Summary

• Define Diffie-Hellman Key Exchange

• Understand the Man-in-the-middle attack

• Present an overview of the Elgamal cryptographic system

• Understand Elliptic curve arithmetic

• Present an overview of elliptic curve cryptography

• Present two techniques for generating pseudorandom
numbers using an asymmetric cipher

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright

This work is protected by United States copyright laws and is

provided solely for the use of instructors in teaching their

courses and assessing student learning. Dissemination or sale of

any part of this work (including on the World Wide Web) will

destroy the integrity of the work and is not permitted. The work

and materials from it should never be made available to students

except by instructors using the accompanying text in their

classes. All recipients of this work are expected to abide by these

restrictions and to honor the intended pedagogical purposes and

the needs of other instructors who rely on these materials.

Week 8 Discussion Post

Cryptography and Network Security:

Principles and Practice
Eighth Edition

Chapter 13

Digital Signatures

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 13.1 Simplified Depiction of

Essential Elements of Digital

Signature Process

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Digital Signature Properties

• It must verify the author and the date and time of the

signature

• It must authenticate the contents at the time of the

signature

• It must be verifiable by third parties to resolve disputes

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Attacks

• Key-only attack

– C only knows A’s public key

• Known message attack

– C is given access to a set of messages and their signatures

• Generic chosen message attack

– C chooses a list of messages before attempting to break A’s
signature scheme, independent of A’s public key; C then obtains
from A valid signatures for the chosen messages

• Directed chosen message attack

– Similar to the generic attack, except that the list of messages to be
signed is chosen after C knows A’s public key but before any
signatures are seen

• Adaptive chosen message attack

– C may request from A signatures of messages that depend on
previously obtained message-signature pairs

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Forgeries

• Total break

– C determines A’s private key

• Universal forgery

– C finds an efficient signing algorithm that provides an

equivalent way of constructing signatures on arbitrary

messages

• Selective forgery

– C forges a signature for a particular message chosen

by C

• Existential forgery

– C forges a signature for at least one message; C has

no control over the message

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Digital Signature Requirements

• The signature must be a bit pattern that depends on the

message being signed

• The signature must use some information unique to the sender

to prevent both forgery and denial

• It must be relatively easy to produce the digital signature

• It must be relatively easy to recognize and verify the digital

signature

• It must be computationally infeasible to forge a digital signature,

either by constructing a new message for an existing digital

signature or by constructing a fraudulent digital signature for a

given message

• It must be practical to retain a copy of the digital signature in

storage

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Direct Digital Signature

• Refers to a digital signature scheme that involves only the communicating

parties

– It is assumed that the destination knows the public key of the source

• Confidentiality can be provided by encrypting the entire message plus

signature with a shared secret key

– It is important to perform the signature function first and then an outer

confidentiality function

– In case of dispute some third party must view the message and its

signature

• The validity of the scheme depends on the security of the sender’s private key

– If a sender later wishes to deny sending a particular message, the sender

can claim that the private key was lost or stolen and that someone else

forged his or her signature

– One way to thwart or at least weaken this ploy is to require every signed

message to include a timestamp and to require prompt reporting of

compromised keys to a central authority

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

ElGamal Digital Signature

• Scheme involves the use of the private key for encryption

and the public key for decryption

• Global elements are a prime number q and a, which is a

primitive root of q

• Use private key for encryption (signing)

• Uses public key for decryption (verification)

• Each user generates their key

– Chooses a secret key (number): 1 < xA < q-1

– Compute their public key: yA = a
xA mod q

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Schnorr Digital Signature

• Scheme is based on discrete logarithms

• Minimizes the message-dependent amount of computation

required to generate a signature

– Multiplying a 2n-bit integer with an n-bit integer

• Main work can be done during the idle time of the

processor

• Based on using a prime modulus p, with p – 1 having a

prime factor q of appropriate size

– Typically p is a 1024-bit number, and q is a 160-bit

number

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

N I S T Digital Signature Algorithm

• Published by N I S T as Federal Information Processing

Standard F I P S 186

• Makes use of the Secure Hash Algorithm (S H A)

• The latest version, F I P S 186-3, also incorporates digital

signature algorithms based on R S A and on elliptic curve

cryptography

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 13.2 Two Approaches to

Digital Signatures

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 13.3 The Digital Signature

Algorithm (D S A)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 13.4 D S A Signing and Verifying

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Elliptic Curve Digital Signature

Algorithm (E C D S A)

• Four elements are involved:

– All those participating in the digital signature scheme use

the same global domain parameters, which define an elliptic

curve and a point of origin on the curve

– A signer must first generate a public, private key pair

– A hash value is generated for the message to be signed;

using the private key, the domain parameters, and the hash

value, a signature is generated

– To verify the signature, the verifier uses as input the signer’s

public key, the domain parameters, and the integer s; the

output is a value v that is compared to r ; the signature is

verified if the v = r

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 13.5 E C D S A Signing and

Verifying

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

R S A-P S S

• R S A Probabilistic Signature Scheme

• Included in the 2009 version of F I P S 186

• Latest of the R S A schemes and the one that R S A Laboratories

recommends as the most secure of the R S A schemes

• For all schemes developed prior to P S S it has not been possible

to develop a mathematical proof that the signature scheme is as

secure as the underlying R S A encryption/decryption primitive

• The PSS approach was first proposed by Bellare and Rogaway

• This approach, unlike the other R S A-based schemes,

introduces a randomization process that enables the security of

the method to be shown to be closely related to the security of

the R S A algorithm itself

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Mask Generation Function (M G F)

• Typically based on a secure cryptographic hash function

such as S H A-1

– Is intended to be a cryptographically secure way of

generating a message digest, or hash, of variable

length based on an underlying cryptographic hash

function that produces a fixed-length output

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 13.6 R S A-P S S Encoding

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 13.7 R S A-P S S E M Verification

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Summary

• Present an overview of the digital signature process

• Understand the ElGamal digital signature scheme

• Understand the Schnorr digital signature scheme

• Understand the N I S T digital signature scheme

• Compare and contrast the N I S T digital signature scheme

with the ElGamal and Schnorr digital signature schemes

• Understand the elliptic curve digital signature scheme

• Understand the R S A-P S S digital signature scheme

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright

This work is protected by United States copyright laws and is

provided solely for the use of instructors in teaching their

courses and assessing student learning. Dissemination or sale of

any part of this work (including on the World Wide Web) will

destroy the integrity of the work and is not permitted. The work

and materials from it should never be made available to students

except by instructors using the accompanying text in their

classes. All recipients of this work are expected to abide by these

restrictions and to honor the intended pedagogical purposes and

the needs of other instructors who rely on these materials.

Week 8 Discussion Post

Cryptography and Network Security:

Principles and Practice
Eighth Edition

Chapter 19

Electronic Mail Security

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 19.1 Function Modules and Standardized

Protocols Used between them in the Internet Mail

Architecture

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Email Protocols

• Two types of protocols are used for transferring email:

– Used to move messages through the Internet from

source to destination

▪ Simple Mail Transfer Protocol (SMTP)

– Used to transfer messages between mail servers

▪ IMAP and POP are the most commonly used

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

SMTP

• Simple Mail Transfer Protocol

• Is a text-based client-server protocol

• Encapsulates an email message in an envelope and is

used to relay the encapsulated messages from source to

destination through multiple MTAs

• Was originally specified in 1982 as RFC 821

• The term Extended SMTP (ESMTP) is often used to refer

to later versions of SMTP

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Mail Access Protocols

POP3

• Post Office Protocol

• Allows an email client to

download an email from

an email server (MTA)

• POP3 user agents

connect via TCP to the

server

• After authorization, the UA

can issue POP3

commands to retrieve and

delete mail

IMAP

Internet Mail Access

Protocol

Enables an email client to

access mail on an email

server

Also uses TCP, with server

TCP port 143

Is more complex than POP3

Provides stronger

authentication and provides

other functions not

supported by POP3

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

RFC 5322

• Defines a format for text messages that are sent using

electronic mail

• Messages are viewed as having an envelope and contents

– The envelope contains whatever information is needed

to accomplish transmission and delivery

– The contents compose the object to be delivered to the

recipient

– RFC 5322 standard applies only to the contents

• The content standard includes a set of header fields that

may be used by the mail system to create the envelope

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Example Message

Date: October 8, 2009 2:15:49 PM EDT

From: “William Stallings” <ws@shore.net>

Subject: The Syntax in RFC 5322

To: Smith@Other-host.com

Cc: Jones@Yet-Another-Host.com

Hello. This section begins the actual

message body, which is delimited from the

message heading by a blank line.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Multipurpose Internet Mail

Extensions (MIME)
• An extension to the RFC 5322 framework that is intended to address some of

the problems and limitations of the use of Simple Mail Transfer Protocol

(SMTP)

– Is intended to resolve these problems in a manner that is compatible with

existing RFC 5322 implementations

– The specification is provided in RFCs 2045 through 2049

• MIME specification includes the following elements:

– Five new message header fields are defined, which may be included in an

RFC 5322 header; these fields provide information about the body of the

message

– A number of content formats are defined, thus standardizing
representations that support multimedia electronic mail

– Transfer encodings are defined that enable the conversion of any content

format into a form that is protected from alteration by the mail system

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Limitations of the SMTP/5322 Scheme

• SMTP cannot transmit executable files or other binary objects

• SMTP cannot transmit text data that includes national language

characters

• SMTP servers may reject mail message over a certain size

• SMTP gateways that translate between ASCII and the character

code EBCDIC do not use a consistent set of mappings,

resulting in translation problems

• SMTP gateways to X.400 electronic mail networks cannot

handle nontextual data included in X.400 messages

• Some SMTP implementations do not adhere completely to the

SMTP standards defined in RFC 821

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

MIME Specifications

• The MIME specification includes the following elements:

– Five new message header fields are defined, which

may be included in an RFC 5322 header

– A number of content formats are defined, thus

standardizing representations that support multimedia

electronic mail

– Transfer encodings are defined that enable the

conversion of any content format into a form that is

protected from alteration by the mail system

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

The Five Header Fields Defined in

MIME (1 of 2)
• MIME-Version

– Must have the parameter value 1.0

– This field indicates that the message conforms to

RFCs 2045 and 2046

• Content-Type

– Describes the data contained in the body with sufficient

detail that the receiving user agent can pick an

appropriate agent or mechanism to represent the data

to the user or otherwise deal with the data in an

appropriate manner

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

The Five Header Fields Defined in

MIME (2 of 2)
• Content-Transfer-Encoding

– Indicates the type of transformation that has been used

to represent the body of the message in a way that is

acceptable for mail transport

• Content-ID

– Used to identify MIME entities uniquely in multiple

contexts

• Content-Description

– A text description of the object with the body; this is

useful when the object is not readable

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 19.1 MIME Content Types (1 of 2)

Type Subtype Description

Text Plain Unformatted text; may be ASCII or ISO 8859.

Enriched Provides greater format flexibility.

Multipart Mixed The different parts are independent but are to be

transmitted

together. They should be presented to the receiver in

the order that they appear in the mail message.

Parallel Differs from Mixed only in that no order is defined for

delivering

the parts to the receiver.

Alternative The different parts are alternative versions of the same

information. They are ordered in increasing faithfulness

to the original, and the recipient’s mail system should

display the “best” version to the user.

Digest Similar to Mixed, but the default type/subtype of each

part is message/ rfc822.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 19.1 MIME Content Types (2 of 2)

Type Subtype Description

Message rfc822 The body is itself an encapsulated message that

conforms to RFC 822.

Partial Used to allow fragmentation of large mail items, in a

way that is transparent to the recipient.

External-

body

Contains a pointer to an object that exists elsewhere.

Image jpeg The image is in JPEG format, JFIF encoding.

gif The image is in GIF format.

Video mpeg MPEG format.

Audio Basic Single-channel 8-bit ISDN μ -law encoding at a sample

rate of 8 kHz.

Application PostScript Adobe Postscript format.

octet-

stream

General binary data consisting of 8-bit bytes.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 19.2 MIME Transfer Encodings

7 bit The data are all represented by short lines of ASCII characters.

8 bit The lines are short, but there may be non-ASCII characters (octets

with the high-order bit set).

binary Not only may non-ASCII characters be present but the lines are not

necessarily short enough for SMTP transport.

quoted-

printable

Encodes the data in such a way that if the data being encoded are

mostly ASCII text, the encoded form of the data remains largely

recognizable by humans..

base64 Encodes data by mapping 6-bit blocks of input to 8-bit blocks of

output, all of which are printable ASCII characters.

x-token A named nonstandard encoding.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Formats

Native Form

• The body to be transmitted is created

in the system’s native format

• The native character set is used and,

where appropriate, local end-of-line

conventions are used as well

• The body may be any format that

corresponds to the local model for

the representation of some form of

information

• Examples include a UNIX-style text
file, or a Sun raster image, or a VMS

indexed file, and audio data in a

system-dependent format stored only

in memory

Canonical Form

• The entire body, including out-of-

band information such as record

lengths and possibly file attribute

information, is converted to a

universal canonical form

• The specific media type of the

body as well as its associated

attributes dictates the nature of the

canonical form that is used

• Conversion to the proper canonical
form may involve character set

conversion, transformation of

audio data, compression, or

various other operations specific to

the various media types

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Email Security Threats

• Authenticity-related threats

– Could result in unauthorized access to an enterprise’s

email system

• Integrity-related threats

– Could result in unauthorized modification of email

content

• Confidentiality-related threats

– Could result in unauthorized disclosure of sensitive

information

• Availability-related threats

– Could prevent end users from being able to send or

receive mail

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 19.3 Email Threats and Mitigations (1 of 2)

Threat Impact on Purported

Sender

Impact on Receiver Mitigation

Email sent by

unauthorized MTA
in enterprise (e.g.,
malware botnet)

Loss of reputation, valid

email from enterprise
may be blocked as
possible spam/phishing

attack.

UBE and/or email

containing malicious
links may be
delivered into

user inboxes.

Deployment of

domainbased
authentication
techniques. Use of

digital signatures over
email.

Email message

sent using spoofed
or unregistered
sending domain

Loss of reputation, valid

email from enterprise
may be blocked as
possible spam/phishing

attack.

UBE and/or email

containing malicious
links may be
delivered into

user inboxes.

Deployment of

domainbased
authentication
techniques. Use of

digital signatures over
email.

Email message

sent using forged
sending address or
email address (i.e.,

phishing, spear
phishing)

Loss of reputation, valid

email from enterprise
may be blocked as
possible spam/phishing

attack.

UBE and/or email

containing malicious
links may be
delivered. Users may

inadvertently divulge
sensitive information

or PII.

Deployment of

domainbased
authentication
techniques. Use of

digital signatures over
email.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 19.3 Email Threats and Mitigations (2 of 2)

Threat Impact on Purported

Sender

Impact on Receiver Mitigation

Email modified in

transit

Leak of sensitive

information or PII.

Leak of sensitive

information, altered
message may
contain malicious

information.

Use of TLS to encrypt

email transfer between
servers. Use of end to
end email encryption.

Disclosure of

sensitive
information (e.g.,
PII) via monitoring

and capturing
of email traffic

Leak of sensitive

information or PII.

Leak of sensitive

information, altered
message may
contain malicious

information.

Use of TLS to encrypt

email transfer between
servers. Use of end t
end email encryption.

Unsolicited Bulk

Email (UBE) (i.e.,
spam)

None, unless purported

sender is spoofed.

UBE and/or email

containing malicious
links may be
delivered into user

inboxes.

Techniques to address

UBE.

DoS/DDoS attack

against an
enterprises’ email
servers

Inability to send email. Inability to receive

email.

Multiple mail servers,

use of cloud-based
email providers.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Counter Threat Protocols (1 of 2)

• SP800-177 recommends use of a variety of standardized

protocols as a means for countering threats:

– STARTTLS

▪ An SMPT security extension that provides

authentication, integrity, non-repudiation and

confidentiality for the entire SMTP message by

running SMTP over TLS

– S/MIME

▪ Provides authentication, integrity, non-repudiation

and confidentiality of the message body carried in

SMTP messages

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Counter Threat Protocols (2 of 2)

• DNS Security Extensions (DNSSEC)

– Provides authentication and integrity protection of DNS

data, and is an underlying tool used by various email

security protocols

• DNS-based Authentication of Named Entities (DANE)

– Is designed to overcome problems in the certificate

authority (CA) system by providing an alternative

channel for authenticating public keys based on

DNSSEC, with the result that the same trust

relationships used to certify IP addresses are used to

certify servers operating on those addresses

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 19.2 The Interrelationship of DNSSEC, SPF, DKIM,

DMARC, DANE, and S/MIME for Assuring Message

Authenticity and Integrity

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Secure/Multipurpose Internet Mail

Extension (S/MIME)
• A security enhancement to the MIME Internet e-mail format standard based on

technology from RSA Data Security

• The most important documents relevant to S/MIME include:

– RFC 5750, S/MIME Version 3.2 Certificate Handling

– RFC 5751, S/MIME Version 3.2 Message Specification

– RFC 4134, Examples of S/MIME Messages

– RFC 2634, Enhanced Security Services for S/MIME

– RFC 5652, Cryptographic Message Syntax (CMS)

– RFC 3370, CMS Algorithms

– RFC 5752, Multiple Signatures in CMS

– RFC 1847, Security Multiparts for MIME –

Multipart/Signed and Multipart/Encrypted

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 19.4 Summary of S/MIME Services

Function Typical Algorithm Typical Action

Digital signature RSA/SHA-256 A hash code of a message is created using

SHA-256. This message digest is encrypted

using SHA-256 with the sender’s private key

and included with the message.

Message

encryption

AES-128 with CBC A message is encrypted using AES-128 with

CBC with a one-time session key generated

by the sender. The session key is encrypted

using RSA with the recipient’s public key and

included with the message.

Compression unspecified A message may be compressed for storage

or transmission.

Email

compatibility

Radix-64

conversion

To provide transparency for email

applications, an encrypted message may be

converted to an ASCII string using radix-64

conversion.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Authentication (1 of 2)

• Provided by means of a digital signature

– The sender creates a message

– SHA-256 is used to generate a 256-bit message digest of the

message

– The message digest is encrypted with RSA using the sender’s

private key, and the result is appended to the message. Also

appended is identifying information for the signer, which will

enable the receiver to retrieve the signer’s public key

– The receiver uses RSA with the sender’s public key to decrypt and

recover the message digest

– The receiver generates a new message digest for the message

and compares it with the decrypted hash code. If the two match,

the message is accepted as authentic

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Authentication (1 of 2)

• Detached signatures are supported

– A detached signature may be stored and transmitted

separately from the message it signs

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Confidentiality (1 of 2)

• S/MIME provides confidentiality by encrypting messages

– Most commonly AES with a 128-bit key is used, with

the cipher block chaining (CBC) mode

• The key itself is also encrypted, typically with RSA

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Confidentiality (2 of 2)

• Each symmetric key, referred to as a content-encryption key, is

used only once

– A new key is generated as a random number for each

message

– Because it is to be used only once, the content-encryption

key is bound to the message and transmitted with it

– To protect the key, it is encrypted with the receiver’s public

key

– To reduce encryption time, the combination of symmetric

and public-key encryption is used

– Only the recipient is able to recover the session key that is

bound to the message

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 19.3 Simplified S/MIME

Functional Flow

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

E-mail Compatibility

• Many electronic mail systems only permit the use of blocks consisting

of ASCII text

– To accommodate this restriction, S/MIME provides the service of

converting the raw 8-bit binary stream to a stream of printable

ASCII characters

– The scheme used for this purpose is Base-64 conversion

▪ Each group of three octets of binary data is mapped into four

ASCII characters

▪ The Base64 algorithm blindly converts the input stream to

Base64 format regardless of content, even if the input happens

to be ASCII text

• RFC 5751 recommends that even if outer 7-bit encoding is not used,

the original MIME content should be 7-bit encoded

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Compression

• S/MIME offers the ability to compress a message

• This has the benefit of saving space both for email transmission and for file

storage

• Compression can be applied in any order with respect to the signing and

message encryption operations

• RFC 5751 provides these guidelines:

– Compression of binary encoded encrypted data is discouraged, since it

will not yield significant compression; Base64 encrypted data could very

well benefit, however

– If a lossy compression algorithm is used with signing, you will need to
compress first, then sign

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

S/MIME Message Content Types (1 of 2)

• Defined in RFC 5652, Cryptographic Message Syntax

– Data

▪ Refers to the inner MIME-encoded message content, which may then

be encapsulated in a SignedData, EnvelopedData, or

CompressedData content type

– SignedData

▪ Used to apply a digital signature to a message

– EnvelopedData

▪ This consists of encrypted content of any type and encrypted content

encryption keys for one or more recipients

– CompressedData

▪ Used to apply data compression to a message

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

S/MIME Message Content Types (2 of 2)

• Clear signing

– A digital signature is calculated for a MIME-encoded

message and the two parts, the message and

signature, form a multipart MIME message

– Can be read and their signatures verified by email

entities that do not implement S/MIME

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Securing a MIME Entity

• S/MIME secures a MIME entity with a signature,

encryption, or both

• The MIME entity is prepared according to the normal rules

for MIME message preparation

– The MIME entity plus some security-related data, such

as algorithm identifiers and certificates, are processed

by S/MIME to produce what is known as a PKCS

object

– A PKCS object is then treated as message content and

wrapped in MIME

• In all cases the message to be sent is converted to

canonical form

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

EnvelopedData

• The steps for preparing an envelopedData MIME are:

– Generate a pseudorandom session key for a particular

symmetric encryption algorithm

– For each recipient, encrypt the session key with the

recipient’s public RSA key

– For each recipient, prepare a block known as

RecipientInfo that contains an identifier of the

recipient’s public-key certificate, an identifier of the

algorithm used to encrypt the session key, and the

encrypted session key

– Encrypt the message content with the session key

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

SignedData

• The steps for preparing an signedData MIME are:

– Select a message digest algorithm (SHA or MD5)

– Compute the message digest (hash function) of the

content to be signed

– Encrypt the message digest with the signer’s private

key

– Prepare a block known as SignerInfo that contains the

signer’s public-key certificate, an identifier of the

message digest algorithm, an identifier of the algorithm

used to encrypt the message digest, and the encrypted

message digest

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Clear Signing

• Achieved using the multipart content type with a signed

subtype

• This signing process does not involve transforming the

message to be signed

• Recipients with MIME capability but not S/MIME capability

are able to read the incoming message

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

S/MIME Certificate Processing

• S/MIME uses public-key certificates that conform to

version 3 of X.509

• S/MIME managers and/or users must configure each client

with a list of trusted keys and with certificate revocation

lists

– The responsibility is local for maintaining the

certificates needed to verify incoming signatures and to

encrypt outgoing messages

• The certificates are signed by certification authorities

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

User Agent Role (1 of 2)

• An S/MIME user has several key-management functions to

perform:

• Key generation

– The user of some related administrative utility must be

capable of generating separate Diffie-Hellman and

DSS key pairs and should be capable of generating

RSA key pairs

– A user agent should generate RSA key pairs with a

length in the range of 768 to 1024 bits and must not

generate a length of less than 512 bits

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

User Agent Role (2 of 2)

• Registration

– A user’s public key must be registered with a

certification authority in order to receive an X.509

public-key certificate

• Certificate storage and retrieval

– A user requires access to a local list of certificates in

order to verify incoming signatures and to encrypt

outgoing messages

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Enhanced Security Services (1 of 2)

• RFC 2634 defines four enhanced security services for

S/MIME:

• Signed receipt

– Returning a signed receipt provides proof of delivery to

the originator of a message and allows the originator to

demonstrate to a third party that the recipient received

the message

• Security labels

– A set of security information regarding the sensitivity of

the content that is protected by S/MIME encapsulation

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Enhanced Security Services (2 of 2)

• Secure mailing lists

– An S/MIME Mail List Agent (MLA) can take a single

incoming message, perform the recipient-specific

encryption for each recipient, and forward the message

• Signing certificates

– This service is used to securely bind a sender’s

certificate to their signature through a signing certificate

attribute

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Domain Name System (DNS)

• A directory lookup service that provides a mapping between the

name of a host on the Internet and its numeric IP address

• Is essential to the functioning of the Internet

• Is used by MUAs and MTAs to find the address of the next hop

server for mail delivery

– Is comprised of four elements:

– Domain name space

– DNS database

– Name servers

– Resolvers

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

DNS Database

• DNS is based on a hierarchical database containing resource

records (RRs) that include the name, IP address, and other

information about hosts

• The key features of the database are:

– Variable-depth hierarchy for names

– Distributed database

– Distribution controlled by the database

– Using this database, DNS servers provide a name-to-

address directory service for network applications that need

to locate specific servers

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 19.5 Resource Record Types

Type Description

A A host address. This RR type maps the name of a system to its IPv4 address. Some systems

(e.g., routers) have multiple addresses, and there is a separate RR for each.

AAAA Similar to A type, but for IPv6 addresses.

CNAME Canonical name. Specifies an alias name for a host and maps this to the canonical (true)

name.

HINFO Host information. Designates the processor and operating system used by the host.

MINFO Mailbox or mail list information. Maps a mailbox or mail list name to a host name.

MX Mail exchange. Identifies the system(s) via which mail to the queried domain name should be

relayed.

NS Authoritative name server for this domain.

PTR Domain name pointer. Points to another part of the domain name space.

SOA Start of a zone of authority (which part of naming hierarchy is implemented). Includes

parameters related to this zone.

SRV For a given service provides name of server or servers in domain that provide that service.

TXT Arbitrary text. Provides a way to add text comments to the database.

WKS Well-known services. May list the application services available at this host.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 19.4 DNS Name Resolution

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

DNSSEC

• DNS Security Extensions

• Provides end-to-end protection through the use of digital signatures that are

created by responding zone administrators and verified by a recipient’s

resolver software

• Avoids the need to trust intermediate name servers and resolvers that cache
or route the DNS records originating from the responding zone administrator

before they reach the source of the query

• Consists of a set of new resource record types and modifications to the

existing DNS protocol

• Defined in these documents:

– RFC 4033, DNS Security Introduction and Requirements

– RFC 4034, Resource Records for the DNS Security Extensions

– RFC 4035, Protocol Modifications for the DNS Security Extensions

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

DNSSEC Operation

• In essence, DNSSEC is designed to protect DNS clients from

accepting forged or altered DNS resource records

• It does this by usi

Week 8 Discussion Post

Cryptography and Network Security:

Principles and Practice
Eighth Edition

Chapter 20

IP Security

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

IP Security Overview

• RFC 1636

– “Security in the Internet Architecture”

– Issued in 1994 by the Internet Architecture Board (I A B)

– Identifies key areas for security mechanisms

▪ Need to secure the network infrastructure from

unauthorized monitoring and control of network traffic

▪ Need to secure end-user-to-end-user traffic using

authentication and encryption mechanisms

– I A B included authentication and encryption as necessary

security features in the next generation I P (I P v 6)

▪ The IPsec specification now exists as a set of Internet

standards

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

IPsec Documents (1 of 2)

• IPsec Documents

– Architecture

▪ Covers the general concepts, security requirements,

definitions, and mechanisms defining IPsec technology

▪ The current specification is RFC4301, Security Architecture for

the Internet Protocol

– Authentication Header (AH)

▪ An extension header to provide message authentication

▪ The current specification is RFC 4302, IP Authentication

Header

– Encapsulating Security Payload (ESP)

▪ Consists of an encapsulating header and trailer used to

provide encryption or combined encryption/authentication

▪ The current specification is RFC 4303, IP Encapsulating

Security Payload (ESP)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

IPsec Documents (2 of 2)

– Internet Key Exchange (IKE)

▪ A collection of documents describing the key management

schemes for use with IPsec

▪ The main specification is RFC 7296, Internet Key Exchange

(IKEv2) Protocol, but there are a number of related RFCs

– Cryptographic algorithms

▪ This category encompasses a large set of documents that

define and describe cryptographic algorithms for encryption,

message authentication, pseudorandom functions (PRFs), and

cryptographic key exchange

– Other

▪ There are a variety of other IPsec-related RFCs, including

those dealing with security policy and management information

base (MIB) content

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Applications of IPsec

• IPsec provides the capability to secure communications across

a L A N, private and public W A N s, and the Internet

• Examples include:

– Secure branch office connectivity over the Internet

– Secure remote access over the Internet

– Establishing extranet and intranet connectivity with partners

– Enhancing electronic commerce security

• Principal feature of I Psec is that it can encrypt and/or

authenticate all traffic at the I P level

– Thus all distributed applications (remote logon, client/server,

e-mail, file transfer, Web access) can be secured

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

I Psec Services

• IPsec provides security services at the IP layer by enabling a system to:

– Select required security protocols

– Determine the algorithm(s) to use for the service(s)

– Put in place any cryptographic keys required to provide the requested

services

• RFC 4301 lists the following services:

– Access control

– Connectionless integrity

– Data origin authentication

– Rejection of replayed packets (a form of partial sequence integrity)

– Confidentiality (encryption)

– Limited traffic flow confidentiality

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 20.1 IPsec Architecture

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Security Association (S A)

• A one-way logical connection between a sender and a receiver that affords
security services to the traffic carried on it

• In any I P packet, the S A is uniquely identified by the Destination Address in the
I P v 4 or I P v 6 header and the S P I in the enclosed extension header (A H or E S
P)

Uniquely identified by three parameters:

• Security Parameters Index (SPI)

– A 32-bit unsigned integer assigned to this SA and having local

significance only

• IP Destination Address

– Address of the destination endpoint of the SA, which may be an end-user
system or a network system such as a firewall or router

• Security protocol identifier

– Indicates whether the association is an AH or ESP security association

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Security Association Database (S A D)
• Defines the parameters associated with each S A

• Normally defined by the following parameters in a S A D entry:

– Security parameter index

– Sequence number counter

– Sequence counter overflow

– Anti-replay window

– A H information

– E S P information

– Lifetime of this security association

– I Psec protocol mode

– Path M T U

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Security Policy Database (S P D)

• The means by which I P traffic is related to specific S A s

– Contains entries, each of which defines a subset of I P

traffic and points to an S A for that traffic

• In more complex environments, there may be multiple

entries that potentially relate to a single S A or multiple SAs

associated with a single S P D entry

– Each S P D entry is defined by a set of I P and upper-

layer protocol field values called selectors

– These are used to filter outgoing traffic in order to map

it into a particular S A

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

SPD Entries (1 of 2)

• The following selectors determine an SPD entry:

• Remote IP address

– This may be a single IP address, an enumerated list or

range of addresses, or a wildcard (mask) address

– The latter two are required to support more than one

destination system sharing the same SA

• Local IP address

– This may be a single IP address, an enumerated list or

range of addresses, or a wildcard (mask) address

– The latter two are required to support more than one

source system sharing the same SA

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

SPD Entries (2 of 2)

• Next layer protocol

– The IP protocol header includes a field that designates

the protocol operating over IP

• Name

– A user identifier from the operating system

– Not a field in the IP or upper-layer headers but is

available if IPsec is running on the same operating

system as the user

• Local and remote ports

– These may be individual TCP or UDP port values, an

enumerated list of ports, or a wildcard port

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 20.1 Host S P D Example

Protocol Local IP Port Remote IP Port Action Comment

UDP 1.2.3.101 500 * 500 BYPASS IKE

ICMP 1.2.3.101 * * * BYPASS Error

messages

* 1.2.3.101 * 1.2.3.0/24 * PROTECT: ESP

intransport-mode

Encrypt

intranet

traffic

TCP 1.2.3.101 * 1.2.4.10 80 PROTECT: ESP

intransport-mode

Encrypt to

server

TCP 1.2.3.101 * 1.2.4.10 443 BYPASS TLS: avoid

double

encryption

* 1.2.3.101 * 1.2.4.0/24 * DISCARD Others in

DMZ

* 1.2.3.101 * * * BYPASS Internet

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 20.2 Processing Model for

Outbound Packets

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 20.3 Processing Model for

Inbound Packets

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 20.4 E S P Packet Format

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Encapsulating Security Payload (E S P) (1 of 2)

• Used to encrypt the Payload Data, Padding, Pad Length, and

Next Header fields

– If the algorithm requires cryptographic synchronization data

then these data may be carried explicitly at the beginning of

the Payload Data field

• An optional I C V field is present only if the integrity service is

selected and is provided by either a separate integrity algorithm

or a combined mode algorithm that uses an I C V

– I C V is computed after the encryption is performed

– This order of processing facilitates reducing the impact of

DoS attacks

– Because the I C V is not protected by encryption, a keyed

integrity algorithm must be employed to compute the I C V

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Encapsulating Security Payload (E S P) (2 of 2)

• The Padding field serves several purposes:

– If an encryption algorithm requires the plaintext to be a

multiple of some number of bytes, the Padding field is

used to expand the plaintext to the required length

– Used to assure alignment of Pad Length and Next

Header fields

– Additional padding may be added to provide partial

traffic-flow confidentiality by concealing the actual

length of the payload

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 20.5 Anti-replay Mechanism

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 20.6 Scope of ESP Encryption

and Authentication

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 20.7 End-to-end IPsec

Transport-Mode Encryption

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Transport Mode (1 of 2)

• Transport mode operation may be summarized as follows:

– At the source, the block of data consisting of the E S P trailer
plus the entire transport-layer segment is encrypted and the
plaintext of this block is replaced with its ciphertext to form
the I P packet for transmission. Authentication is added if this
option is selected

– The packet is then routed to the destination. Each
intermediate router needs to examine and process the I P
header plus any plaintext I P extension headers but does not
need to examine the ciphertext

– The destination node examines and processes the I P
header plus any plaintext I P extension headers. Then, on
the basis of the S P I in the E S P header, the destination node
decrypts the remainder of the packet to recover the plaintext
transport-layer segment

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Transport Mode (2 of 2)

• Transport mode operation provides confidentiality for any

application that uses it, thus avoiding the need to

implement confidentiality in every individual application

• One drawback to this mode is that it is possible to do traffic

analysis on the transmitted packets

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Tunnel Mode (1 of 3)

• Tunnel mode provides protection to the I P packet

– To achieve this, after the A H or E S P fields are added

to the I P packet, the entire packet plus security fields is

treated as the payload of new outer I P packet with a

new outer I P header

– The entire original, inner, packet travels through a

tunnel from one point of an I P network to another; no

routers along the way are able to examine the inner I P

header

– Because the original packet is encapsulated, the new,

larger packet may have totally different source and

destination addresses, adding to the security

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Tunnel Mode (2 of 3)

– Tunnel mode is used when one or both ends of a

security association (S A) are a security gateway, such

as a firewall or router that implements I Psec

– With tunnel mode, a number of hosts on networks

behind firewalls may engage in secure communications

without implementing IPsec

– The unprotected packets generated by such hosts are

tunneled through external networks by tunnel mode S

As set up by the IPsec software in the firewall or

secure router at the boundary of the local network

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Tunnel Mode (3 of 3)

• Tunnel mode is useful in a configuration that includes a

firewall or other sort of security gateway that protects a

trusted network from external networks

• Encryption occurs only between an external host and the

security gateway or between two security gateways

– This relieves hosts on the internal network of the
processing burden of encryption and simplifies the key
distribution task by reducing the number of needed
keys

– It thwarts traffic analysis based on ultimate destination

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

V P N

• Tunnel mode can be used to implement a secure virtual private

network

– A virtual private network (V P N) is a private network that is

configured within a public network in order to take advantage of

the economies of scale and management facilities of large

networks

▪ V P N s are widely used by enterprises to create wide area

networks that span large geographic areas, to provide site-to-

site connections to branch offices, and to allow mobile users to

dial up their company L A N s

▪ The pubic network facility is shared by many customers, with

the traffic of each customer segregated from other traffic

▪ Traffic designated as V P N traffic can only go from a V P N

source to a destination in the same V P N

▪ It is often the case that encryption and authentication facilities

are provided for the V P N

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 20.8 Example of Virtual Private

Network Implemented with IPsec

Tunnel Mode

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 20.2 Tunnel Mode and

Transport Mode Functionality

Blank Transport Mode S A Tunnel Mode S A

A H Authenticates I P payload

and selected portions of I P

header and IPv6 extension

headers.

Authenticates entire inner I P

packet (inner header plus I P

payload) plus selected

portions of outer I P header

and outer I P v 6 extension
headers.

E S P Encrypts I P payload and any

IPv6 extension headers

following the ESP header.

Encrypts entire inner I P

packet.

E S P with

Authentication

Encrypts I P payload and any

IPv6 extension headers

following the E S P header.

Authenticates I P payload but

not I P header.

Encrypts entire inner I P

packet. Authenticates inner I P

packet.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 20.9 Protocol Operation for E S P

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Combining Security Associations
• An individual SA can implement either the AH or ESP protocol but not both

• Security association bundle

– Refers to a sequence of SAs through which traffic must be processed to

provide a desired set of IPsec services

– The SAs in a bundle may terminate at different endpoints or at the same
endpoint

• May be combined into bundles in two ways:

• Transport adjacency

– Refers to applying more than one security protocol to the same IP packet

without invoking tunneling

– This approach allows for only one level of combination

• Iterated tunneling

– Refers to the application of multiple layers of security protocols effected

through IP tunneling

– This approach allows for multiple levels of nesting

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

E S P with Authentication Option

• In this approach, the first user applies E S P to the data to be

protected and then appends the authentication data field

• Transport mode E S P

– Authentication and encryption apply to the I P payload

delivered to the host, but the I P header is not protected

• Tunnel mode E S P

– Authentication applies to the entire I P packet delivered to

the outer I P destination address and authentication is

performed at that destination

– The entire inner I P packet is protected by the privacy

mechanism for delivery to the inner I P destination

• For both cases authentication applies to the ciphertext rather

than the plaintext

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Transport Adjacency

• Another way to apply authentication after encryption is to use

two bundled transport S A s, with the inner being an E S P S A and

the outer being an A H S A

– In this case E S P is used without its authentication option

– Encryption is applied to the I P payload

– A H is then applied in transport mode

– Advantage of this approach is that the authentication covers

more fields

– Disadvantage is the overhead of two S A s versus one S A

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Transport-Tunnel Bundle

• The use of authentication prior to encryption might be preferable

for several reasons:

– It is impossible for anyone to intercept the message and

alter the authentication data without detection

– It may be desirable to store the authentication information

with the message at the destination for later reference

• One approach is to use a bundle consisting of an inner A H

transport S A and an outer E S P tunnel S A

– Authentication is applied to the I P payload plus the I P

header

– The resulting I P packet is then processed in tunnel mode by

E S P

▪ The result is that the entire authenticated inner packet is

encrypted and a new outer I P header is added

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 20.10 Basic Combinations of

Security Associations

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Internet Key Exchange

• The key management portion of I Psec involves the determination and
distribution of secret keys

– A typical requirement is four keys for communication between two
applications

▪ Transmit and receive pairs for both integrity and confidentiality

• The I Psec Architecture document mandates support for two types of
key management:

• Manual

– A system administrator manually configures each system with its
own keys and with the keys of other communicating systems

– This is practical for small, relatively static environments

• Automated

– Enables the on-demand creation of keys for S A s and facilitates the
use of keys in a large distributed system with an evolving
configuration

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

I S A K M P/Oakley

• The default automated key management protocol of IPsec

• Consists of:

– Oakley Key Determination Protocol

▪ A key exchange protocol based on the Diffie-Hellman

algorithm but providing added security

▪ Generic in that it does not dictate specific formats

– Internet Security Association and Key Management Protocol

(I S A K M P)

▪ Provides a framework for Internet key management and

provides the specific protocol support, including formats,

for negotiation of security attributes

▪ Consists of a set of message types that enable the use

of a variety of key exchange algorithms

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Features of I K E Key Determination

• Algorithm is characterized by five important features:

1.

– It employs a mechanism known as cookies to thwart clogging

attacks

2.

– It enables the two parties to negotiate a group; this, in essence,

specifies the global parameters of the Diffie-Hellman key

exchange

3.

– It uses nonces to ensure against replay attacks

4.

– It enables the exchange of Diffie-Hellman public key values

5.

– It authenticates the Diffie-Hellman exchange to thwart man-in-the-

middle-attacks

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 20.11 IKEv2 Exchanges

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 20.12 I K E Formats

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 20.3 IKE Payload Types
Type Parameters

Security Association Proposals

Key Exchange DH Group #, Key Exchange Data

Identification ID Type, ID Data

Certificate Cert Encoding, Certificate Data

Certificate Request Cert Encoding, Certification Authority

Authentication Auth Method, Authentication Data

Nonce Nonce Data

Notify Protocol-ID, SPI Size, Notify Message Type, SPI, Notification Data

Delete Protocol-ID, SPI Size, # of SPIs, SPI (one or more)

Vendor ID Vendor ID

Traffic Selector Number of TSs, Traffic Selectors

Encrypted IV, Encrypted IKE payloads, Padding, Pad Length, ICV

Configuration CFG Type, Configuration Attributes

Extensible Authentication

Protocol

EAP Message

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Summary

• Present an overview of I P security (I Psec)

• Explain the difference between transport mode and tunnel mode

• Understand the concept of security association

• Explain the difference between the security association database and

the security policy database

• Present an overview of Encapsulating Security Payload

• Summarize the traffic processing functions performed by I Psec for out-

bound packets and for inbound packets

• Discuss the alternatives for combining security associations

• Present an overview of Internet Key Exchange

• Summarize the alternative cryptographic suites approved for use with

IPsec

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright

This work is protected by United States copyright laws and is

provided solely for the use of instructors in teaching their

courses and assessing student learning. Dissemination or sale of

any part of this work (including on the World Wide Web) will

destroy the integrity of the work and is not permitted. The work

and materials from it should never be made available to students

except by instructors using the accompanying text in their

classes. All recipients of this work are expected to abide by these

restrictions and to honor the intended pedagogical purposes and

the needs of other instructors who rely on these materials.

Week 8 Discussion Post

Cryptography and Network Security:

Principles and Practice
Eighth Edition

Chapter 3

Classical Encryption Techniques

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Definitions (1 of 2)

• Plaintext

– An original message

• Ciphertext

– The coded message

• Enciphering/encryption

– The process of converting from plaintext to ciphertext

• Deciphering/decryption

– Restoring the plaintext from the ciphertext

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Definitions (2 of 2)

• Cryptography

– The area of study of the many schemes used for

encryption

• Cryptographic system/cipher

– A scheme

• Cryptanalysis

– Techniques used for deciphering a message without

any knowledge of the enciphering details

• Cryptology

– The areas of cryptography and cryptanalysis

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 3.1 Simplified Model of

Symmetric Encryption

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Symmetric Cipher Model

• There are two requirements for secure use of conventional

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

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 3.2 Model of Symmetric

Cryptosystem

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Cryptographic Systems

• Characterized along three independent dimensions:

• The type of operations used for transforming plaintext to

ciphertext

– Substitution

– Transposition

• The number of keys used

– Symmetric, single-key, secret-key, conventional

encryption

– Asymmetric, two-key, or public-key encryption

• The way in which the plaintext is processed

– Block cipher

– Stream cipher

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Cryptanalysis and Brute-Force Attack

• Cryptanalysis

– Attack relies on the nature of the algorithm plus some

knowledge of the general characteristics of the

plaintext

– Attack exploits the characteristics of the algorithm to

attempt to deduce a specific plaintext or to deduce the

key being used

• Brute-force attack

– Attacker tries every possible key on a piece of

ciphertext until an intelligible translation into plaintext is

obtained

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

achieve success

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 3.1 Types of Attacks on

Encrypted Messages

Type of Attack Known to Cryptanalyst

Ciphertext Only • Encryption algorithm

• Ciphertext

Known Plaintext • Encryption algorithm

• Ciphertext

• One or more plaintext–ciphertext pairs formed with the secret key

Chosen Plaintext • Encryption algorithm

• Ciphertext

• Plaintext message chosen by cryptanalyst, together with its corresponding

ciphertext generated with the secret key

Chosen Ciphertext • Encryption algorithm

• Ciphertext

• Ciphertext chosen by cryptanalyst, together with its corresponding decrypted

plaintext generated with the secret key

Chosen Text • Encryption algorithm

• Ciphertext

• Plaintext message chosen by cryptanalyst, together with its corresponding

ciphertext generated with the secret key

• Ciphertext chosen by cryptanalyst, together with its corresponding decrypted

plaintext generated with the secret key

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Encryption Scheme Security

• Unconditionally secure

– No matter how much time an opponent has, it is

impossible for him or her to decrypt the ciphertext

simply because the required information is not there

• Computationally secure

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

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

• 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

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Strong Encryption

• The term strong encryption refers to encryption schemes

that make it impractically difficult for unauthorized persons

or systems to gain access to plaintext that has been

encrypted

• Properties that make an encryption algorithm strong are:

– Appropriate choice of cryptographic algorithm

– Use of sufficiently long key lengths

– Appropriate choice of protocols

– A well-engineered implementation

– Absence of deliberately introduced hidden flaws

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Substitution Technique

• Is one in which the letters of plaintext are replaced by other

letters or by numbers or symbols

• If the plaintext is viewed as a sequence of bits, then

substitution involves replacing plaintext bit patterns with

ciphertext bit patterns

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Caesar Cipher

• Simplest and earliest known use of a substitution cipher

• Used by Julius Caesar

• Involves replacing each letter of the alphabet with the

letter standing three places further down the alphabet

• Alphabet is wrapped around so that the letter following Z

is A

plain: meet me after the toga party

cipher: PHHW PH DIWHU WKH WRJD SDUWB

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Caesar Cipher Algorithm

• Can define transformation as:

a b c d e f g h i j k l m n o p q r s t u v w x y z

D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

• Mathematically give each letter a number

a b c d e f g h i j k l m n o p q r s t u v w x y z

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

• Algorithm can be expressed as:

c = E(3, p) = (p + 3) mod (26)

• A shift may be of any amount, so that the general Caesar algorithm is:

C = E(k , p ) = (p + k ) mod 26

• Where k takes on a value in the range 1 to 25; the decryption algorithm is

simply:

p = D(k , C ) = (C − k ) mod 26

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 3.3 Brute-Force Cryptanalysis

of Caesar Cipher

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Sample of Compressed Text

Figure 3.4 Sample of Compressed Text

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Monoalphabetic Cipher

• Permutation

– Of a finite set of elements S is an ordered sequence of

all the elements of S , with each element appearing

exactly once

• If the “cipher” line can be any permutation of the 26

alphabetic characters, then there are 26! or greater than

4 x 1026 possible keys

– This is 10 orders of magnitude greater than the key

space for DES

– Approach is referred to as a monoalphabetic

substitution cipher because a single cipher alphabet is

used per message

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 3.5 Relative Frequency of

Letters in English Text

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Monoalphabetic Ciphers

• Easy to break because they

reflect the frequency data of the

original alphabet

• Countermeasure is to provide

multiple substitutes

(homophones) for a single letter

• Digram

– Two-letter combination

– Most common is th

• Trigram

– Three-letter combination

– Most frequent is the

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Playfair Cipher

• Best-known multiple-letter encryption cipher

• Treats digrams in the plaintext as single units and

translates these units into ciphertext digrams

• Based on the use of a 5 × 5 matrix of letters constructed

using a keyword

• Invented by British scientist Sir Charles Wheatstone in

1854

• Used as the standard field system by the British Army in

World War I and the U.S. Army and other Allied forces

during World War II

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Playfair Key Matrix

• Fill in letters of keyword (minus duplicates) from left to right

and from top to bottom, then fill in the remainder of the

matrix with the remaining letters in alphabetic order

• Using the keyword MONARCHY:

M O N A R

C H Y B D

E F G I/J K

L P Q S T

U V W X Z

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 3.6 Relative Frequency of

Occurrence of Letters

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Hill Cipher

• Developed by the mathematician Lester Hill in 1929

• Strength is that it completely hides single-letter frequencies

– The use of a larger matrix hides more frequency

information

– A 3 x 3 Hill cipher hides not only single-letter but also

two-letter frequency information

• Strong against a ciphertext-only attack but easily broken

with a known plaintext attack

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Polyalphabetic Ciphers

• Polyalphabetic substitution cipher

– Improves on the simple monoalphabetic technique by

using different monoalphabetic substitutions as one

proceeds through the plaintext message

• All these techniques have the following features in

common:

– A set of related monoalphabetic substitution rules is

used

– A key determines which particular rule is chosen for a

given transformation

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Vigenère Cipher

• Best known and one of the simplest polyalphabetic

substitution ciphers

• In this scheme the set of related monoalphabetic

substitution rules consists of the 26 Caesar ciphers with

shifts of 0 through 25

• Each cipher is denoted by a key letter which is the

ciphertext letter that substitutes for the plaintext letter a

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Example of Vigenère Cipher

• To encrypt a message, a key is needed that is as long as

the message

• Usually, the key is a repeating keyword

• For example, if the keyword is deceptive, the message “we

are discovered save yourself” is encrypted as:

key: deceptivedeceptivedeceptive

plaintext: wearediscoveredsaveyourself

ciphertext: ZICVTWQNGRZGVTWAVZHCQYGLMGJ

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Vigenère Autokey System

• A keyword is concatenated with the plaintext itself to

provide a running key

• Example:

key: deceptivewearediscoveredsav

plaintext: wearediscoveredsaveyourself

ciphertext: ZICVTWQNGKZEIIGASXSTSLVVWLA

• Even this scheme is vulnerable to cryptanalysis

– Because the key and the plaintext share the same

frequency distribution of letters, a statistical technique

can be applied

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Vernam Cipher

Figure 3.7 Vernam Cipher

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

One-Time Pad

• Improvement to Vernam cipher

proposed by an Army Signal

Corp officer, Joseph

Mauborgne

• Use a random key that is as

long as the message so that

the key need not be repeated

• Key is used to encrypt and

decrypt a single message and

then is discarded

• Each new message requires a

new key of the same length as

the new message

• Scheme is unbreakable

– Produces random output

that bears no statistical

relationship to the

plaintext

– Because the ciphertext

contains no information

whatsoever about the

plaintext, there is simply

no way to break the code

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Difficulties

• The one-time pad offers complete security but, in practice, has two

fundamental difficulties:

– There is the practical problem of making large quantities of

random keys

▪ Any heavily used system might require millions of random

characters on a regular basis

– Mammoth key distribution problem

▪ For every message to be sent, a key of equal length is needed

by both sender and receiver

• Because of these difficulties, the one-time pad is of limited utility

– Useful primarily for low-bandwidth channels requiring very high

security

• The one-time pad is the only cryptosystem that exhibits perfect

secrecy (see Appendix F)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Rail Fence Cipher

• Simplest transposition cipher

• Plaintext is written down as a sequence of diagonals and

then read off as a sequence of rows

• To encipher the message “meet me after the toga party”

with a rail fence of depth 2, we would write:

m e m a t r h t g p r y

e t e f e t e o a a t

Encrypted message is:

MEMATRHTGPRYETEFETEOAAT

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Row Transposition Cipher

• Is a more complex transposition

• Write the message in a rectangle, row by row, and read the

message off, column by column, but permute the order of

the columns

– The order of the columns then becomes the key to the

algorithm

Key: 4 3 1 2 5 6 7

Plaintext: a t t a c k p

o s t p o n e

d u n t i l t

w o a mx y z

Ciphertext: TTNAAPTMTSUOAODWCOIXKNLYPETZ

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Summary

• Present an overview of the main concepts of symmetric

cryptography

• Explain the difference between cryptanalysis and brute-

force attack

• Understand the operation of a monoalphabetic substitution

cipher

• Understand the operation of a polyalphabetic cipher

• Present an overview of the Hill cipher

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright

This work is protected by United States copyright laws and is

provided solely for the use of instructors in teaching their

courses and assessing student learning. Dissemination or sale of

any part of this work (including on the World Wide Web) will

destroy the integrity of the work and is not permitted. The work

and materials from it should never be made available to students

except by instructors using the accompanying text in their

classes. All recipients of this work are expected to abide by these

restrictions and to honor the intended pedagogical purposes and

the needs of other instructors who rely on these materials.

Week 8 Discussion Post

Cryptography and Network Security:

Principles and Practice
Eighth Edition

Chapter 4

Block Ciphers and the Data

Encryption Standard

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Stream Cipher (1 of 2)

• Encrypts a digital data stream one bit or one byte at a time

– Examples:

▪ Autokeyed Vigenère cipher

▪ Vernam cipher

• In the ideal case, a one-time pad version of the Vernam cipher

would be used, in which the keystream is as long as the

plaintext bit stream

– If the cryptographic keystream is random, then this cipher is

unbreakable by any means other than acquiring the

keystream

▪ Keystream must be provided to both users in advance

via some independent and secure channel

▪ This introduces insurmountable logistical problems if the

intended data traffic is very large

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Stream Cipher (2 of 2)

• For practical reasons the bit-stream generator must be

implemented as an algorithmic procedure so that the

cryptographic bit stream can be produced by both users

– It must be computationally impractical to predict future

portions of the bit stream based on previous portions of

the bit stream

– The two users need only share the generating key and

each can produce the keystream

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Block Cipher

• A block of plaintext is treated as a whole and used to

produce a ciphertext block of equal length

• Typically a block size of 64 or 128 bits is used

• As with a stream cipher, the two users share a symmetric

encryption key

• The majority of network-based symmetric cryptographic

applications make use of block ciphers

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 4.1 Stream Cipher and Block Cipher

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 4.2 General n-bit-n-bit Block

Substitution (shown with n = 4)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 4.1 Encryption and Decryption Tables for

Substitution Cipher of Figure 4.2

Plaintext Ciphertext

0000 1110

0001 0100

0010 1101

0011 0001

0100 0010

0101 1111

0110 1011

0111 1000

1000 0011

1001 1010

1010 0110

1011 1100

1100 0101

1101 1001

1110 0000

1111 0111

Ciphertext Plaintext

0000 1110

0001 0011

0010 0100

0011 1000

0100 0001

0101 1100

0110 1010

0111 1111

1000 0111

1001 1101

1010 1001

1011 0110

1100 1011

1101 0010

1110 0000

1111 0101

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Feistel Cipher

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

permutations

• Substitutions

– Each plaintext element or group of elements is uniquely replaced

by a corresponding ciphertext element or group of elements

• Permutation

– No elements are added or deleted or replaced in the sequence,

rather the order in which the elements appear in the sequence is

changed

• Is a practical application of a proposal by Claude Shannon to develop

a product cipher that alternates confusion and diffusion functions

• Is the structure used by many significant symmetric block ciphers

currently in use

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Diffusion and Confusion
• Terms introduced by Claude Shannon to capture the two basic building blocks

for any cryptographic system

– Shannon’s concern was to thwart cryptanalysis based on statistical

analysis

• Diffusion

– The statistical structure of the plaintext is dissipated into long-range

statistics of the ciphertext

– This is achieved by having each plaintext digit affect the value of many

ciphertext digits

• Confusion

– Seeks to make the relationship between the statistics of the ciphertext

and the value of the encryption key as complex as possible

– Even if the attacker can get some handle on the statistics of the

ciphertext, the way in which the key was used to produce that ciphertext
is so complex as to make it difficult to deduce the key

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 4.3 Feistel Encryption and

Decryption (16 rounds)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Feistel Cipher Design Features (1 of 2)

• Block size

– Larger block sizes mean greater security but reduced

encryption/decryption speed for a given algorithm

• Key size

– Larger key size means greater security but may

decrease encryption/decryption speeds

• Number of rounds

– The essence of the Feistel cipher is that a single round

offers inadequate security but that multiple rounds offer

increasing security

• Subkey generation algorithm

– Greater complexity in this algorithm should lead to

greater difficulty of cryptanalysis

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Feistel Cipher Design Features (2 of 2)

• Round function F

– Greater complexity generally means greater resistance

to cryptanalysis

• Fast software encryption/decryption

– In many cases, encrypting is embedded in applications

or utility functions in such a way as to preclude a

hardware implementation; accordingly, the speed of

execution of the algorithm becomes a concern

• Ease of analysis

– If the algorithm can be concisely and clearly explained,

it is easier to analyze that algorithm for cryptanalytic

vulnerabilities and therefore develop a higher level of

assurance as to its strength

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Feistel Example

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Data Encryption Standard (DES)

• Issued in 1977 by the National Bureau of Standards (now

NIST) as Federal Information Processing Standard 46

• Was the most widely used encryption scheme until the

introduction of the Advanced Encryption Standard (AES) in

2001

• Algorithm itself is referred to as the Data Encryption

Algorithm (DEA)

– Data are encrypted in 64-bit blocks using a 56-bit key

– The algorithm transforms 64-bit input in a series of

steps into a 64-bit output

– The same steps, with the same key, are used to

reverse the encryption

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 4.5 General Depiction of DES

Encryption Algorithm

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 4.2 DES Example

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

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 4.3 Avalanche Effect in DES: Change in Plaintext

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 4.4 Avalanche Effect in DES: Change in Key

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 4.5 Average Time Required for Exhaustive

Key Search

Key Size

(bits) Cipher

Number of

Alternative Keys

Time Required at 109

Decryptions/s

Time Required

at 1013

Decryptions/s

56 DES 256 ≈ 7.2 × 1016 255 ns = 1.125 years 1 hour

128 AES 2128 ≈ 3.4 × 1038 2127 ns = 5.3 × 1021 years 5.3 × 1017 years

168 Triple DES 2168 ≈ 3.7 × 1050 2167 ns = 5.8 × 1033 years 5.8 × 1029 years

192 AES 2192 ≈ 6.3 × 1057 2191 ns = 9.8 × 1040 years 9.8 × 1036 years

256 AES 2256 ≈ 1.2 × 1077 2255 ns = 1.8 × 1060 years 1.8 × 1056 years

26 characters

(permutation)

Monoalphabetic 2! = 4 × 1026 2 × 1026 ns = 6.3 × 109

years

6.3 × 106 years

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Strength of DES

• Timing attacks

– One in which information about the key or the plaintext is

obtained by observing how long it takes a given

implementation to perform decryptions on various

ciphertexts

– Exploits the fact that an encryption or decryption algorithm

often takes slightly different amounts of time on different

inputs

– So far it appears unlikely that this technique will ever be

successful against DES or more powerful symmetric ciphers

such as triple DES and AES

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Block Cipher Design Principles:

Number of Rounds
• The greater the number of rounds, the more difficult it is to

perform cryptanalysis

• In general, the criterion should be that the number of

rounds is chosen so that known cryptanalytic efforts

require greater effort than a simple brute-force key search

attack

• If DES had 15 or fewer rounds, differential cryptanalysis

would require less effort than a brute-force key search

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Block Cipher Design Principles:

Design of Function F
• The heart of a Feistel block cipher is the function F

• The more nonlinear F, the more difficult any type of cryptanalysis will be

• The SAC and BIC criteria appear to strengthen the effectiveness of the

confusion function

The algorithm should have good avalanche properties

• Strict avalanche criterion (SAC)

– States that any output bit j of an S-box should change with probability 1/2

when any single input bit i is inverted for all i , j

• Bit independence criterion (BIC)

– States that output bits j and k should change independently when any
single input bit i is inverted for all i , j , and k

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Block Cipher Design Principles: Key

Schedule Algorithm

• W ith any Feistel block cipher, the key is used to generate one

subkey for each round

• In general, we would like to select subkeys to maximize the

difficulty of deducing individual subkeys and the difficulty of

working back to the main key

• It is suggested that, at a minimum, the key schedule should

guarantee key/ciphertext Strict Avalanche Criterion and Bit
Independence Criterion

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Summary

• Explain the concept of the avalanche effect

• Discuss the cryptographic strength of DES

• Summarize the principal block cipher design principles

• Understand the distinction between stream ciphers and block ciphers

• Present an overview of the Feistel cipher and explain how decryption

is the inverse of encryption

• Present an overview of Data Encryption Standard (DES)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright

This work is protected by United States copyright laws and is

provided solely for the use of instructors in teaching their

courses and assessing student learning. Dissemination or sale of

any part of this work (including on the World Wide Web) will

destroy the integrity of the work and is not permitted. The work

and materials from it should never be made available to students

except by instructors using the accompanying text in their

classes. All recipients of this work are expected to abide by these

restrictions and to honor the intended pedagogical purposes and

the needs of other instructors who rely on these materials.

Week 8 Discussion Post

Cryptography and Network Security:

Principles and Practice
Eighth Edition

Chapter 7

Block Cipher Operation

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.1 Multiple Encryption (1 of 2)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Meet-in-the-Middle Attack

• The use of double D E S results in a mapping that is not

equivalent to a single D E S encryption

• The meet-in-the-middle attack algorithm will attack this

scheme and does not depend on any particular property of

D E S but will work against any block encryption cipher

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.1 Multiple Encryption (2 of 2)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.2 Known-Plaintext Attack on

Triple D E S

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Triple D E S with Three Keys

• Many researchers now feel that three-key 3D E S is the preferred

alternative

• Three-key 3D E S has an effective key length of 168 bits and is

defined as:

– C = E( K3, D( K2, E( K1, P)))

• Backward compatibility with DES is provided by putting:

– K3 = K2 or K1 = K2

• A number of Internet-based applications have adopted three-key

3D E S including P G P and S/M I M E

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Modes of Operation

• A technique for enhancing the effect of a cryptographic

algorithm or adapting the algorithm for an application

• To apply a block cipher in a variety of applications, five modes of

operation have been defined by N I S T

– The five modes are intended to cover a wide variety of

applications of encryption for which a block cipher could be

used

– These modes are intended for use with any symmetric block

cipher, including triple D E S and A E S

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 7.1 Block Cipher Modes of Operation

Mode Description Typical Application

Electronic

Codebook (E C B)

Each block of plaintext bits is encoded

independently using the same key.

• Secure transmission of single

values (e.g., an encryption
key)

Cipher Block

Chaining (C B C)

The input to the encryption algorithm is the

X O R of the next block of plaintext and the
preceding block of ciphertext.

• General-purpose block-

oriented transmission
• Authentication

Cipher Feedback

(C F B)

Input is processed s bits at a time.

Preceding ciphertext is used as input to the
encryption algorithm to produce
pseudorandom output, which is X O Red

with plaintext to produce next unit of
ciphertext.

• General-purpose stream-

oriented transmission
• Authentication

Output Feedback

(O F B)

Similar to C F B, except that the input to the

encryption algorithm is the preceding
encryption output, and full blocks are used.

• Stream-oriented transmission

over noisy channel (e.g.,
satellite communication)

Counter (C T R) Each block of plaintext is X ORed with an

encrypted counter. The counter is
incremented for each subsequent block.

• General-purpose block-

oriented transmission
• Useful for high-speed

requirements

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.3 Electronic Codebook

(E C B) Mode

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Criteria and properties for evaluating

and constructing block cipher modes

of operation that are superior to ECB:

• Overhead

• Error recovery

• Error propagation

• Diffusion

• Security

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.4 Cipher Block Chaining

(C B C) Mode

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Cipher Feedback Mode

• For A E S, D E S, or any

block cipher, encryption is

performed on a block of b

bits

– In the case of D E S b =

64

– In the case of A E S b =

128

• There are three modes

that make it possible to

convert a block cipher

into a stream cipher:

– Cipher feedback (CFB)

mode

– Output feedback (OFB)

mode

– Counter (CTR) mode

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.5 s-bit Cipher Feedback

(C F B) Mode (1 of 2)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.5 s-bit Cipher Feedback

(C F B) Mode (2 of 2)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.6 Output Feedback (O F B)

Mode (1 of 2)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.6 Output Feedback (O F B)

Mode (2 of 2)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.7 Counter (C T R) Mode (1 of 2)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.7 Counter (C T R) Mode (2 of 2)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Advantages of C T R

• Hardware efficiency

• Software efficiency

• Preprocessing

• Random access

• Provable security

• Simplicity

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.8 Feedback Characteristic of

Modes of Operation (1 of 4)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.8 Feedback Characteristic of

Modes of Operation (2 of 4)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.8 Feedback Characteristic of

Modes of Operation (3 of 4)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.8 Feedback Characteristic of

Modes of Operation (4 of 4)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

X T S-A E S Mode for Block-Oriented

Storage Devices
• Approved as an additional block cipher mode of operation

by N I S T in 2010

• Mode is also an I E EE Standard, I E EE Std 1619-2007

– Standard describes a method of encryption for data

stored in sector-based devices where the threat model

includes possible access to stored data by the

adversary

– Has received widespread industry support

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Tweakable Block Ciphers

• X T S-A E S mode is based on the concept of a tweakable

block cipher

• General structure:

– Has three inputs:

▪ A plaintext P

▪ A symmetric key K

▪ A tweak T

• Produces a ciphertext output C

• Tweak need not be kept secret

– Purpose is to provide variability

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.9 Tweakable Block Cipher

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Storage Encryption Requirements

• The requirements for encrypting stored data, also referred to as “data at rest”,

differ somewhat from those for transmitted data

• The P1619 standard was designed to have the following characteristics:

– The ciphertext is freely available for an attacker

– The data layout is not changed on the storage medium and in transit

– Data are accessed in fixed sized blocks, independently from each other

– Encryption is performed in 16-byte blocks, independently from each other

– There are no other metadata used, except the location of the data blocks

within the whole data set

– The same plaintext is encrypted to different ciphertexts at different
locations, but always to the same ciphertext when written to the same

location again

– A standard conformant device can be constructed for decryption of data

encrypted by another standard conformant device

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

X T S-A E S Operation on Single Block

Figure 7.10 X T S-A E S Operation on Single Block

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

X T S-A E S Operation on Single Block

Figure 7.10 X T S-A E S Operation on Single Block

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.11 X T S-A E S Mode

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Format-Preserving Encryption (F P E)

• Refers to any encryption technique that takes a plaintext in

a given format and produces a ciphertext in the same

format

– For example: credit cards consist of 16 decimal digits.

An F P E that can accept this type of input would

produce a ciphertext output of 16 decimal digits. (Note

that the ciphertext need not be, and in fact in unlikely to

be, a valid credit card number.) But it will have the

same format and can be stored in the same way as

credit card number plaintext.

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 7.2 Comparison of Format-

Preserving Encryption and A E S

Blank Credit Card Tax I D Bank Account Number

Plaintext 8123 4512 3456 6780 219-09-9999 800N2982K-22

FPE 8123 4521 7292 6780 078-05-1120 709G9242H-35

AES (hex) af411326466add24

c86abd8aa525db7a

7b9af4f3f218ab25

07c7376869313afa

9720ec7f793096ff

d37141242e1c51bd

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Motivation (1 of 2)

• F P E facilitates the retrofitting of encryption technology to

legacy applications, where a conventional encryption mode

might not be feasible because it would disrupt data

fields/pathways

• F P E has emerged as a useful cryptographic tool, whose

applications include financial-information security, data

sanitization, and transparent encryption of fields in legacy

databases

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Motivation (2 of 2)

• The principal benefit of F P E is that it enables protection of

particular data elements, while still enabling workflows that were

in place before F P E was in use

– No database schema changes and minimal application

changes are required

– Only applications that need to see the plaintext of a data

element need to be modified and generally these

modifications will be minimal

• Some examples of legacy applications where F P E is desirable

are:

– C O B O L data-processing applications

– Database applications

– F P E-encrypted characters can be significantly compressed

for efficient transmission

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Difficulties in Designing an F P E

• A general-purpose standardized F P E should meet a

number of requirements:

– The ciphertext is of the same length and format as the

plaintext

– It should be adaptable to work with a variety of

character and number types

– It should work with variable plaintext length

– Security strength should be comparable to that

achieved with A E S

– Security should be strong even for very small plaintext

lengths

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.12 Feistel Structure for

Format-Preserving Encryption

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Character Strings

• The N I S T, and the other F P E algorithms that have been

proposed, are used with plaintext consisting of a string of

elements, called characters

• A finite set of two or more symbols is called an alphabet

• The elements of an alphabet are called characters

• A character string is a finite sequence of characters from

an alphabet

• Individual characters may repeat in the string

• The number of different characters in an alphabet is called

the base (also referred to as the radix) of the alphabet

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 7.3 Notation and Parameters Used in F P E

Algorithms. (a) Notation

[x]s Converts an integer into a byte string; it is the string of s bytes that encodes the

number x, with 0 ≤ x < 28s. The equivalent notation is

LEN(X) Length of the character string X.

NUMradix(X) Converts strings to numbers. The number that the numeral string X represents in

base radix, with the most significant character first. In other words, it is the
nonnegative integer less than radixLEN(X) whose most-significant-character-first
representation in base radix is X.

PRFK(X) A pseudorandom function that produces a 128-bit output with X as the input, using

encryption key K.

Given a nonnegative integer x less than radixm, this function produces a

representation of x as a string of m characters in base radix, with the most significant
character first.

[i .. j] The set of integers between two integers i and j, including i and j.

X[i .. j] The substring of characters of a string X from X[i] to X[j], including X[i] and X[j].

REV(X) Given a bit string, X, the string that consists of the bits of X in reverse order.

8

2
)STR ( .

s
x

STR ( )
m

radix
x

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 7.3 Notation and Parameters Used in F P E

Algorithms. (b) Parameters

radix The base, or number of characters, in a given plaintext

alphabet.

tweak Input parameter to the encryption and decryption functions

whose confidentiality is not protected by the mode.

tweakradix The base for tweak strings

minlen Minimum message length, in characters.

maxlen Maximum message length, in characters.

maxTlen Maximum tweak length

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.13 Algorithm P R F(X)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.14 Algorithm FF1

(F FX[Radix])

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.15 Algorithm FF2 (V A E S3)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 7.16 Algorithm FF3 (B P S-B C)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Summary

• Analyze the security of multiple encryption schemes

• Explain the meet-in-the-middle attack

• Compare and contrast E C B, C B C, C F B, O F B, and counter

modes of operation

• Present an overview of the X T S-A E S mode of operation

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright

This work is protected by United States copyright laws and is

provided solely for the use of instructors in teaching their

courses and assessing student learning. Dissemination or sale of

any part of this work (including on the World Wide Web) will

destroy the integrity of the work and is not permitted. The work

and materials from it should never be made available to students

except by instructors using the accompanying text in their

classes. All recipients of this work are expected to abide by these

restrictions and to honor the intended pedagogical purposes and

the needs of other instructors who rely on these materials.

Week 8 Discussion Post

Cryptography and Network Security:

Principles and Practice
Eighth Edition

Chapter 8

Random Bit Generation and Stream

Ciphers

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Slide in this Presentation Contain Hyperlinks.

JAWS users should be able to get a list of links

by using INSERT+F7

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Random Numbers

• A number of network security algorithms and protocols

based on cryptography make use of random binary

numbers:

– Key distribution and reciprocal authentication schemes

– Session key generation

– Generation of keys for the R S A public-key encryption

algorithm

– Generation of a bit stream for symmetric stream

encryption

• There are two distinct requirements for a sequence of

random numbers:

– Randomness

– Unpredictability

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Randomness

• The generation of a sequence of allegedly random

numbers being random in some well-defined statistical

sense has been a concern

• Two criteria are used to validate that a sequence of

numbers is random:

– Uniform distribution

▪ The frequency of occurrence of ones and zeros

should be approximately equal

– Independence

▪ No one subsequence in the sequence can be

inferred from the others

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Unpredictability

• The requirement is not just 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

– True random numbers have their limitations, such as

inefficiency, so it is more common to implement

algorithms that generate sequences of numbers that

appear to be random

– Care must be taken that an opponent not be able to

predict future elements of the sequence on the basis of

earlier elements

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Pseudorandom Numbers

• 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

• If the algorithm is good, the resulting sequences will pass

many tests of randomness and are referred to as

pseudorandom numbers

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 8.1 Random and

Pseudorandom Number Generators

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

True Random Number Generator

(T R N G)

• Takes as input a source that is effectively random

• The source is referred to as an entropy source and is

drawn from the physical environment of the computer

– Includes things such as keystroke timing patterns, disk

electrical activity, mouse movements, and

instantaneous values of the system clock

– The source, or combination of sources, serve as input

to an algorithm that produces random binary output

• The T R N G may simply involve conversion of an analog

source to a binary output

• The T R N G may involve additional processing to overcome

any bias in the source

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Pseudorandom Number Generator

(P R N G) (1 of 2)

• Takes as input a fixed value, called the seed, and

produces a sequence of output bits using a deterministic

algorithm

– Quite often the seed is generated by a T R N G

• The output bit stream is determined solely by the input

value or values, so an adversary who knows the algorithm

and the seed can reproduce the entire bit stream

• Other than the number of bits produced there is no

difference between a P R N G and a P R F

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Pseudorandom Number Generator

(P R N G) (2 of 2)

• Pseudorandom number generator

– An algorithm that is used to produce an open-ended

sequence of bits

– Input to a symmetric stream cipher is a common

application for an open-ended sequence of bits

• Pseudorandom function (P R F)

– Used to produce a pseudorandom string of bits of

some fixed length

– Examples are symmetric encryption keys and nonces

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

P R N G Requirements

• The basic requirement when a P R N G or P R F is used for a

cryptographic application is that an adversary who does not know the

seed is unable to determine the pseudorandom string

• The requirement for secrecy of the output of a P R N G or P R F leads to

specific requirements in the areas of:

– Randomness

– Unpredictability

– Characteristics of the seed

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Randomness

• The generated bit stream needs to appear random even though it is

deterministic

• There is no single test that can determine if a P R N G generates numbers that

have the characteristic of randomness

– If the P R N G exhibits randomness on the basis of multiple tests, then it
can be assumed to satisfy the randomness requirement

• N I S T S P 800-22 specifies that the tests should seek to establish three

characteristics:

– Uniformity

– Scalability

– Consistency

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Randomness Tests (1 of 2)

• S P 800-22 lists 15 separate tests of randomness

• Three tests

– Frequency test

▪ The most basic test and must be included in any

test suite

▪ Purpose is to determine whether the number of

ones and zeros in a sequence is approximately the

same as would be expected for a truly random

sequence

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Randomness Tests (2 of 2)

– Runs test

▪ Focus of this test is the total number of runs in the

sequence, where a run is an uninterrupted sequence of

identical bits bounded before and after with a bit of the

opposite value

▪ Purpose is to determine whether the number of runs of

ones and zeros of various lengths is as expected for a

random sequence

– Maurer’s universal statistical test

▪ Focus is the number of bits between matching patterns

▪ Purpose is to detect whether or not the sequence can be

significantly compressed without loss of information. A

significantly compressible sequence is considered to be

non-random

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Unpredictability

• A stream of pseudorandom numbers should exhibit two forms of

unpredictability:

– Forward unpredictability

▪ If the seed is unknown, the next output bit in the sequence should be

unpredictable in spite of any knowledge of previous bits in the
sequence

– Backward unpredictability

▪ It should not be feasible to determine the seed from knowledge of any

generated values

▪ No correlation between a seed and any value generated from that
seed should be evident

▪ Each element of the sequence should appear to be the outcome of an

independent random event whose probability is 1/2

• The same set of tests for randomness also provides a test of unpredictability

– A random sequence will have no correlation with a fixed value (the seed)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Seed Requirements

• The seed that serves as input to the P R N G must be

secure and unpredictable

• The seed itself must be a random or pseudorandom

number

• Typically the seed is generated by T R N G

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 8.2 Generation of Seed Input

to P R N G

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Algorithm Design

• Algorithms fall into two categories:

– Purpose-built algorithms

▪ Algorithms designed specifically and solely for the

purpose of generating pseudorandom bit streams

– Algorithms based on existing cryptographic algorithms

▪ Have the effect of randomizing input data

• Three broad categories of cryptographic algorithms are

commonly used to create P R N Gs:

– Symmetric block ciphers

– Asymmetric ciphers

– Hash functions and message authentication codes

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Linear Congruential Generator

• An algorithm first proposed by Lehmer that is parameterized with four

numbers:

m the modulus m > 0

a the multiplier 0 < a< m

c the increment 0≤ c < m

X0 the starting value, or seed 0 ≤ X0 < m

• The sequence of random numbers {Xn} is obtained via the following

iterative equation:

Xn+1 = (aXn + c) mod m

• If m , a , c , and X0 are integers, then this technique will produce a

sequence of integers with each integer in the range 0 ≤ Xn < m

• The selection of values for a , c , and m is critical in developing a good

random number generator

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Blum Blum Shub (B BS) Generator

• Has perhaps the strongest public proof of its cryptographic

strength of any purpose-built algorithm

• Referred to as a cryptographically secure pseudorandom

bit generator (C S P R B G)

– A C S P R B G is defined as one that passes the next-bit-

test if there is not a polynomial-time algorithm that, on

input of the first k bits of an output sequence, can

predict the (k + 1)st bit with probability significantly

greater than 1/2

• The security of B BS is based on the difficulty of factoring n

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 8.3 Blum Blum Shub Block

Diagram

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 8.1 Example Operation of B BS

Generator

i Xi Bi

0 20749 Blank

1 143135 1

2 177671 1

3 97048 0

4 89992 0

5 174051 1

6 80649 1

7 45663 1

8 69442 0

9 186894 0

10 177046 0

i Xi Bi

11 137922 0

12 123175 1

13 8630 0

14 114386 0

15 14863 1

16 133015 1

17 106065 1

18 45870 0

19 137171 1

20 48060 0

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

P R N G Using Block Cipher Modes of

Operation

• Two approaches that use a block cipher to build a P N R G

have gained widespread acceptance:

– C T R mode

▪ Recommended in N I S T S P 800-90, A N S I standard

X.82, and R F C 4086

– O F B mode

▪ Recommended in X9.82 and R F C 4086

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 8.4 P R N G Mechanisms Based

on Block Ciphers

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 8.2 Example Results for P R N G

Using O F B

Output Block

Fraction of One

Bits

Fraction of Bits that

Match with

Preceding Block

1786f4c7ff6e291dbdfdd90ec3453176 0.57 —

5e17b22b14677a4d66890f87565eae64 0.51 0.52

fd18284ac82251dfb3aa62c326cd46cc 0.47 0.54

c8e545198a758ef5dd86b41946389bd5 0.50 0.44

fe7bae0e23019542962e2c52d215a2e3 0.47 0.48

14fdf5ec99469598ae0379472803accd 0.49 0.52

6aeca972e5a3ef17bd1a1b775fc8b929 0.57 0.48

f7e97badf359d128f00d9b4ae323db64 0.55 0.45

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 8.3 Example Results for P R N G

Using C T R

Output Block

Fraction of One

Bits

Fraction of Bits that

Match with

Preceding Block

1786f4c7ff6e291dbdfdd90ec3453176 0.57 —

60809669a3e092a01b463472fdcae420 0.41 0.41

d4e6e170b46b0573eedf88ee39bff33d 0.59 0.45

5f8fcfc5deca18ea246785d7fadc76f8 0.59 0.52

90e63ed27bb07868c753545bdd57ee28 0.53 0.52

0125856fdf4a17f747c7833695c52235 0.50 0.47

f4be2d179b0f2548fd748c8fc7c81990 0.51 0.48

1151fc48f90eebac658a3911515c3c66 0.47 0.45

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 8.4 C T R_D R B G Parameters

Blank 3DES AES-128 AES-192 AES-256

outlen 64 128 128 128

keylen 168 128 192 256

seedlen 232 256 320 384

reseed_interval ≤232 ≤248 ≤248 ≤248

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 8.5 C T R_D R B G Functions

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 8.6 Generic Structure of a

Typical Stream Cipher

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Stream Cipher Design Considerations
(1 of 2)

• 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

• The keystream should approximate the properties of a

true random number stream as close as possible

– 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

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Stream Cipher Design Considerations
(2 of 2)

• A key length of at least 128 bits is desirable

– The output of the pseudorandom number generator is

conditioned on the value of the input key

– The same considerations that apply to block ciphers

are valid

• With a properly designed pseudorandom number

generator a stream cipher can be as secure as a block

cipher of comparable key length

– A potential advantage is that stream ciphers that do not

use block ciphers as a building block are typically

faster and use far less code than block ciphers

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

R C4

• Designed in 1987 by Ron Rivest for R S A Security

• Variable key size stream cipher with byte-oriented operations

• Based on the use of a random permutation

• Eight to sixteen machine operations are required per output byte

and the cipher can be expected to run very quickly in software

• R C4 is used in the W iFi Protected Access (W P A) protocol that

are part of the I E E E 802.11 wireless L A N standard

• It is optional for use in Secure Shell (S S H) and Kerberos

• R C4 was kept as a trade secret by R S A Security until

September 1994 when the R C4 algorithm was anonymously

posted on the Internet on the Cypherpunks anonymous

remailers list

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 8.7 R C4

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Strength of R C4

• A fundamental vulnerability was revealed in the R C4 key

scheduling algorithm that reduces the amount of effort to

discover the key

• Recent cryptanalysis results exploit biases in the R C4
keystream to recover repeatedly encrypted plaintexts

• As a result of the discovered weaknesses the I E T F issued

R F C 7465 prohibiting the use of R C4 in T L S

• In its latest T L S guidelines, N I S T also prohibited the use of

R C4 for government use

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Stream Ciphers Using Feedback Shift

Registers (1 of 2)
• With the increasing use of highly constrained devices there

has been increasing interest in developing new stream

ciphers that take up minimal memory, are highly efficient,

and have minimal power consumption requirements

• Most of the recently developed stream ciphers are based

on the use of feedback shift registers (F S R s)

– F S R s exhibit the desired performance behavior, are

well-suited to compact hardware implementation, and

there are well-developed theoretical results on the

statistical properties of the bit sequences they produce

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Stream Ciphers Using Feedback Shift

Registers (2 of 2)
▪ An F S R consists of a sequence of 1-bit memory

cells

▪ Each cell has an output line, which indicates the

value currently stored, and an input line

▪ At discrete time instants, known as clock times, the

value in each storage device is replaced by the

value indicated by its input line

▪ The effect is as follows: The rightmost (least

significant) bit is shifted out as the output bit for this

clock cycle; the other bits are shifted one bit position

to the right; the new leftmost (most significant) bit is

calculated as a function of the other bits in the F S R

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 8.8 Binary Linear Feedback

Shift Register Sequence Generator

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 8.9 4-Bit Linear Feedback Shift

Register

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 8.10 1/(1 + X + X3)

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 8.11 A Nonlinear Feedback

Shift Register

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Grain-128a (1 of 2)

• Grain is a family of hardware-efficient stream ciphers

• Grain was accepted as part of the eSTREAM effort to

approve a number of new stream ciphers

• The eSTREAM specification, called Grain v1, defines two

stream ciphers, one with an 80-bit key and a 64-bit

initialization vector (I V), and one with a 128-bit key and 80-

bit I V

• Grain has since been revised and expanded to include

authentication, referred to as Grain-128a

• The eSTREAM final report states that Grain has pushed

the state of the art in terms of compact implementation

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Grain-128a (2 of 2)

• Grain-128a consists of two shift registers, one with linear

feedback and the second with nonlinear feedback, and a

filter function

• The registers are couple by very lightweight, but

judiciously chosen Boolean functions

• The L F S R guarantees a minimum period for the

keystream, and it also provides balancedness in the

output.

• The N F S R, together with a nonlinear filter, introduces

nonlinearity to the cipher

• The input to the N F S R is masked with the output of the

L F S R so that the state of the N F S R is balanced

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 8.12 Grain-128a Stream Cipher

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Entropy Sources

• A true random number generator (T R N G) uses a

nondeterministic source to produce randomness

• Most operate by measuring unpredictable natural processes

such as pulse detectors of ionizing radiation events, gas

discharge tubes, and leaky capacitors

• Intel has developed a commercially available chip that samples

thermal noise by amplifying the voltage measured across

undriven resistors

• LavaRnd is an open source project for creating truly random

numbers using inexpensive cameras, open source code, and

inexpensive hardware

– The system uses a saturated C C D in a light-tight can as a

chaotic source to produce the seed; software processes the

result into truly random numbers in a variety of formats

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Possible Sources of Randomness

R F C 4086 lists the following possible sources of randomness that can be

used on a computer to generate true random sequences:

• Sound/video input

– The input from a sound digitizer with no source plugged in or from

a camera with the lens cap on is essentially thermal noise

– If the system has enough gain to detect anything, such input can

provide reasonable high quality random bits

• Disk drives

– Have small random fluctuations in their rotational speed due to

chaotic air turbulence

– The addition of low-level disk seek-time instrumentation produces

a series of measurements that contain this randomness

There is also an online service (random.org) which can deliver random

sequences securely over the Internet

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Table 8.5 Comparison of P R N Gs and

T R N Gs

Blank Pseudorandom

Number Generators

True Random Number

Generators

Efficiency Very efficient Generally inefficient

Determinism Deterministic Nondeterministic

Periodicity Periodic Aperiodic

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Conditioning
• A T R N G may produce an output that is biased in some way (such as having

more ones than zeros or vice versa)

• Biased

– N I S T S P 800-90B defines a random process as biased with respect to an

assumed discrete set of potential outcomes if some of those outcomes

have a greater probability of occurring than do others

• Entropy rate

– N I S T 800-90B defines entropy rate as the rate at which a digitized noise
source provides entropy

– Is a measure of the randomness or unpredictability of a bit string

– Will be a value between 0 (no entropy) and 1 (full entropy)

• Conditioning algorithms/deskewing algorithms

– Methods of modifying a bit stream to further randomize the bits

• Typically conditioning is done by using a cryptographic algorithm to scramble

the random bits so as to eliminate bias and increase entropy

– The two most common approaches are the use of a hash function or a

symmetric block cipher

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Hash Function

• A hash function produces an n-bit output from an input of

arbitrary length

• A simple way to use a hash function for conditioning is as

follows:

– Blocks of m input bits, with m ≥ n, are passed through

the hash function and the n output bits are used as

random bits

– To generate a stream of random bits, successive input

blocks pass through the hash function to produce

successive hashed output blocks

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 8.13 N R B G Model

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Health Tests on the Noise Source (1 of 4)

• The nature of the health testing of the noise source

depends strongly on the technology used to produce noise

• In general, the assumption can be made that the digitized

output of the noise source will exhibit some bias

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Health Tests on the Noise Source (2 of 4)

– Thus, traditional statistical tests are not useful for

monitoring the noise source, because the noise source

is likely to always fail

– The tests on the noise source need to be tailored to the

expected statistical behavior of the correctly operating

noise source

– The goal is not to determine if the source is unbiased,

but if it is operating as expected

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Health Tests on the Noise Source (3 of 4)

• S P 800-90B specifies that continuous tests be done on

digitized samples obtained from the noise source

– The purpose is to test for variability and to determine if

the noise source is producing at the expected entropy

rate

• S P 800-90B mandates the use of two tests

– Repetition Count Test

▪ Designed to quickly detect a catastrophic failure that

causes the noise source to become “stuck” on a

single output value for a long time

▪ Involves looking for consecutive identical samples

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Health Tests on the Noise Source (4 of 4)

– Adaptive Proportion Test

▪ Designed to detect a large loss of entropy, such as

might occur as a result of some physical failure or

environmental change affecting the noise source

▪ The test continuously measures the local frequency

of occurrence of some sample value in a sequence

of noise source samples to determine if the sample

occurs too frequently

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Health Tests on the Conditioning

Function

• S P 800-90B specifies that health tests should also be

applied to the output of the conditioning component, but

does not indicate which tests to use

• The purpose of the health tests on the conditioning

component is to assure that the output behaves as a true

random bit stream

• It is reasonable to use the tests for randomness defined in

S P 800-22

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Intel Digital Random Number

Generator

• T R N Gs have traditionally been used only for key

generation and other applications where only a small

number of random bits were required

– This is because T R N Gs have generally been inefficient

with a low bit rate of random bit production

• The first commercially available T R N G that achieves bit

production rates comparable with that of P R N Gs is the

Intel digital random number generator offered on new

multicore chips since May 2012

– It is implemented entirely in hardware

– The entire D R N G is on the same multicore chip as the

processors

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 8.14 Intel Processor Chip with

Random Number Generator

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Figure 8.15 Intel D R N G Logical Structure

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Summary

• Explain the concepts of randomness and unpredictability with respect

to random numbers

• Present an overview of requirements for pseudorandom number

generators

• Explain the significance of skew

• Present an overview of stream ciphers and R C4

• Understand the differences among true random number generators,

pseudorandom number generators, and pseudorandom functions

• Explain how a block cipher can be used to construct a pseudorandom

number generator

Copyright © 2020 Pearson Education, Inc. All Rights Reserved.

Copyright

This work is protected by United States copyright laws and is

provided solely for the use of instructors in teaching their

courses and assessing student learning. Dissemination or sale of

any part of this work (including on the World Wide Web) will

destroy the integrity of the work and is not permitted. The work

and materials from it should never be made available to students

except by instructors using the accompanying text in their

classes. All recipients of this work are expected to abide by these

restrictions and to honor the intended pedagogical purposes and

the needs of other instructors who rely on these materials.

Week 8 Discussion Post

 In the final discussion posting please describe what components of cryptography impacted you the most. 

PFA few Cryptography course pdf chapters. 

500 words. APA forma