. 20
( 29)


(4) After receiving all five public pieces, the KDC verifies that
t = (t1 * t2 * t3 * t4 * t5) mod p

If it does, the KDC approves the public key.

At this point, the KDC knows that the trustees each have a valid piece, and that they can reconstruct
the private key if required. However, neither the KDC nor any four of the trustees working together
can reconstruct Alice™s private key.

Micali™s papers [1084,1085] also contain a procedure for making RSA fair and for combining a
threshold scheme with the fair cryptosystem, so that m out of n trustees can reconstruct the private

Failsafe Diffie-Hellman

Like the previous protocol, a group of users share a prime, p, and a generator, g. Alice™s private key is
s, and her public key is t =gs mod p.

(1) The KDC chooses a random number, B, between 0 and p - 2, and commits to B using a
bit-commitment protocol (see Section 4.9).
(2) Alice chooses a random number, A, between 0 and p - 2. She sends gA mod p to the
(3) The user “shares” A with each trustee using a verifiable secret-sharing scheme (see
Section 3.7).
(4) The KDC reveals B to Alice.
(5) Alice verifies the commitment from step (1). Then she sets her public key as
t = (gA)gB mod p

She sets her private key as

s = (A + B) mod (p - 1)

The trustees can reconstruct A. Since the KDC knows B, this is enough to reconstruct s. And Alice
cannot make use of any subliminal channels to send unauthorized information. This protocol,
discussed in [946,833] is being patented.

23.11 Zero-Knowledge Proofs of Knowledge

Zero-Knowledge Proof of a Discrete Logarithm

Peggy wants to prove to Victor that she knows an x that satisfies

G (mod p)

where p is a prime, and x is a random number relatively prime to p - 1. The numbers A, B, and p are
public, and x is secret. Here™s how Peggy can prove she knows x without revealing it (see Section 5.1)

Page 458 of 666
Applied Cryptography: Second Edition - Bruce Schneier

(1) Peggy generates t random numbers, r1 , r2 , ..., rt, where all ri are less than p - 1.1
(2) Peggy computes hi = Ari mod p, for all values of i, and sends them to Victor.
(3) Peggy and Victor engage in a coin-flipping protocol to generate t bits: b1, b2 , ..., bt.
(4) For all t bits, Peggy does one of the following:
a) If bi = 0, she sends Victor ri
b) If bi = 1, she sends Victor si = (ri - rj) mod (p - 1), where j is the lowest value for
which bj = 1
(5) For all t bits, Victor confirms one of the following:
a) If bi = 0, that Ari G i (mod p)
b) If bi = 1, that Asi G ihj-1 (mod p)
(6) Peggy sends Victor Z, where
Z = (x - rj) mod (p - 1)
(7) Victor confirms that AZ G j-1 (mod p)

Peggy™s probability of successfully cheating is 2 -t.

Zero-Knowledge Proof of the Ability to Break RSA

Alice knows Carol™s private key. Maybe she has broken RSA; maybe she has broken into Carol™s
house and stolen the key. Alice wants to convince Bob that she knows Carol™s key. However, she
doesn™t want to tell Bob the key or even decrypt one of Carol™s messages for Bob. Here™s a zero-
knowledge protocol by which Alice convinces Bob that she knows Carol™s private key [888].

Carol™s public key is e, her private key is d, and the RSA modulus is n.

(1) Alice and Bob agree on a random k and an m such that
km G (mod n)

They should choose the numbers randomly, using a coin-flip protocol to generate k and then
computing m. If both k and m are greater than 3, the protocol continues. Otherwise, they choose
(2) Alice and Bob generate a random ciphertext, C. Again, they should use a coin-flip
(3) Alice, using Carol™s private key, computes
M = Cd mod n

She then computes

X = Mk mod n

and sends X to Bob.
(4) Bob confirms that Xm mod n = C. If it does, he believes Alice.

A similar protocol can be used to demonstrate the ability to break a discrete logarithm problem [888].

Page 459 of 666
Applied Cryptography: Second Edition - Bruce Schneier

Zero-Knowledge Proof that n Is a Blum Integer

There are no known truly practical zero-knowledge proofs that n =pq, where p and q are primes
congruent to 3 modulo 4. However, if you allow n to be of the form prqs, where r and s are odd, then
the properties which make Blum integers useful in cryptography still hold. And there exists a zero-
knowledge proof that n is of that form.

Assume Alice knows the factorization of the Blum integer n, where n is of the form previously
discussed. Here™s how she can prove to Bob that n is of that form [660].

(1) Alice sends Bob a number u which has a Jacobi symbol -1 modulo n.
(2) Alice and Bob jointly agree on random bits: b1 , b2 , ..., bk.
(3) Alice and Bob jointly agree on random numbers: x1 , x2 , ..., xk.
(4) For each i = 1, 2,..., k, Alice sends Bob a square root modulo n, of one of the four
numbers: xi, -xi, uxi, -uxi. The square root must have the Jacobi symbol bi.

The odds of Alice successfully cheating are one in 2k.

23.12 Blind Signatures

The notion of blind signatures (see Section 5.3) was invented by David Chaum [317,323], who also
invented their first implementation [318]. It uses the RSA algorithm.

Bob has a public key, e, a private key, d, and a public modulus, n. Alice wants Bob to sign message m

(1) Alice chooses a random value, k, between 1 and n. Then she blinds m by computing
t = mke mod n
(2) Bob signs t
td = (mke)d mod n
(3) Alice unblinds td by computing
s = td/k mod n
(4) And the result is
s = md mod n

This can easily be shown
td G G(mke)d G dk (mod n), so td/k = mdk/k G d (mod n).
Gm Gm

Chaum invented a family of more complicated blind signature algorithms in [320,324], called blind
unanticipated signatures. These signatures are more complex in construction, but more flexible.

23.13 Oblivious Transfer

In this protocol by Michael Rabin [1286], Alice has a 50 percent chance of sending Bob two primes, p,
and q. Alice will not know whether the transfer is successful. (See Section 5.5.) (This protocol can be
used to send Bob any message with a 50 percent success rate if p and q reveal an RSA private key.)

(1) Alice sends Bob the product of the two primes: n = pq.
(2) Bob chooses a random x less than n, such that x is relatively prime to n. He sends

Page 460 of 666
Applied Cryptography: Second Edition - Bruce Schneier

a = x2 mod n
(3) Alice, knowing p and q, computes the four roots of a: x, n - x, y, and n - y. She chooses
one of these roots at random and sends it to Bob.
(4) If Bob receives y or n - y, he can compute the greatest common divisor of x + y and n,
which is either p or q. Then, of course, n/p = q.
If Bob receives x or n - x, he can™t compute anything.

This protocol may have a weakness: It might be the case that Bob can compute a number a such that
given the square root of a you can calculate a factor of n all the time.

23.14 Secure Multiparty Computation

This protocol is from [1373]. Alice knows the integer i; Bob knows the integer j. Alice and Bob
together wish to know whether i G or if i > j, but neither Alice nor Bob wish to reveal the integer
each knows. This special case of secure multiparty computation (see Section 6.2) is sometimes known
as Yao™s millionaire problem [1627].

For this example, assume that i and j range from 1 to 100. Bob has a public key and a private key.

(1) Alice chooses a large random number, x, and encrypts it in Bob™s public key.
c = EB(x)
(2) Alice computes c - i and sends the result to Bob.
(3) Bob computes the following 100 numbers:
yu = DB(c - i + u), for 1 Gu G100

DB is the decryption algorithm with Bob™s private key.
He chooses a large random prime, p. (The size of p should be somewhat smaller than x. Bob
doesn™t know x, but Alice could easily tell him the size of x.) He then computes the following 100
Gu G G100
zu = (yu mod p), for 1 G

He then verifies that, for all u
|zu - zv| G

and that for all u
0 < zu < p - 1

If this is not true, Bob chooses another prime and tries again.
(4) Bob sends Alice this sequence of numbers in this exact order:
z1 , z2 , ..., zj, zj+1 + 1, zj+2 + 1,..., z100 + 1, p
(5) Alice checks whether the ith number in the sequence is congruent to x mod p. If it is,
she concludes that i G If it is not, she concludes that i > j.
(6) Alice tells Bob the conclusion.

All the verification that Bob goes through in step (3) is to guarantee that no number appears twice in
the sequence generated in step (4). Otherwise, if za =zb, Alice knows that a j <b.

The one drawback to this protocol is that Alice learns the result of the computation before Bob does.

Page 461 of 666
Applied Cryptography: Second Edition - Bruce Schneier

Nothing stops her from completing the protocol up to step (5) and then refusing to tell Bob the results
in step (6). She could even lie to Bob in step (6).

Example of the Protocol

Assume they™re using RSA. Bob™s public key is 7 and his private key is 23; n =55. Alice™s secret value,
i, is 4; Bob™s secret value, j, is 2. (Assume that only the values 1, 2, 3, and 4 are possible for i and j.)

(1) Alice chooses x = 39, and c = EB(39) = 19.
(2) Alice computes c - i = 19 - 4 = 15. She sends 15 to Bob.
(3) Bob computes the following 4 numbers:

y1 = DB(15 + 1) = 26
y2 = DB(15 + 2) = 18
y3 = DB(15 + 3) = 2
y4 = DB(15 + 4) = 39

He chooses p =31 and calculates:

z1 = (26 mod 31) = 26
z2 = (18 mod 31) = 18
z3 = (2 mod 31) = 2
z4 = (39 mod 31) = 8

He does all the verifications and confirms that the sequence is fine.
(4) Bob sends Alice this sequence of numbers in this exact order:
26, 18, 2 + 1, 8 + 1, 31 = 26, 18, 3, 9, 31
(5) Alice checks whether the 4th number in the sequence is congruent to x mod p. Since 9
G (mod 31), then i > j.
(6) Alice tells Bob.

This protocol can be used to create far more complicated protocols. A group of people can conduct a
secret auction over a computer network. They arrange themselves in a logical circle, and through
individual pairwise comparisons, determine which is offering the highest price. In order to prevent
people from changing their bids in mid-auction, some sort of bit-commitment protocol could also be
used. If the auction is a Dutch auction, then the highest bidder gets the item for his highest price. If it
is an English auction, then he gets the item for the second-highest price. (This can be determined by a
second round of pairwise comparisons.) Similar ideas have applications in bargaining, negotiations,
and arbitration.

23.15 Probabilistic Encryption

The notion of probabilistic encryption was invented by Shafi Goldwasser and Silvio Micali [624].
Although its theory makes it the most secure cryptosystem invented, its early implementation was
impractical [625]. More recent implementations have changed that.

The point behind probabilistic encryption is to eliminate any information leaked with public-key
cryptography. Because a cryptanalyst can always encrypt random messages with a public key, he can

Page 462 of 666
Applied Cryptography: Second Edition - Bruce Schneier

get some information. Assuming he has ciphertext C =EK(M) and is trying to recover plaintext
message M, he can pick a random message M' and encrypt it: C' =EK(M'). If C'=C, then he guessed
the correct plaintext. If it™s wrong, he just guesses again.

Also, no partial information is leaked about the original message. With public-key cryptography,
sometimes a cryptanalyst can learn things about the bits: The XOR of bits 5, 17, and 39 is 1, and so
on. With probabilistic encryption, even this type of information remains hidden.

Not a whole lot of information is to be gained here, but there are potential problems with allowing a
cryptanalyst to encrypt random messages with your public key. Some information is being leaked to
the cryptanalyst every time he encrypts a message. No one really knows how much.

Probabilistic encryption tries to eliminate that leakage. The goal is that no computation on the
ciphertext, or on any other trial plaintexts, can give the cryptanalyst any information about the
corresponding plaintext.

In probabilistic encryption, the encrypting algorithm is probabilistic rather than deterministic. In
other words, a large number of ciphertexts will decrypt to a given plaintext, and the particular
ciphertext used in any given encryption is randomly chosen.

C1 = EK(M), C2 = EK(M), C3 = EK(M),..., Ci = EK(M)
M = DK(C1) = DK(C2) = DK(C3) =...= DK(Ci)

With probabilistic encryption, a cryptanalyst can no longer encrypt random plaintexts looking for the
correct ciphertext. To illustrate, assume the cryptanalyst has ciphertext Ci =EK(M). Even if he guesses
M correctly, when he encrypts EK(M), the result will be a completely different C: Cj. He cannot
compare Ci and Cj, and so cannot know that he has guessed the message correctly.

This is amazingly cool stuff. Even if a cryptanalyst has the public encryption key, the plaintext, and
the ciphertext, he cannot prove that the ciphertext is the encryption of the plaintext without the
private decryption key. Even if he tries exhaustive search, he can only prove that every conceivable
plaintext is a possible plaintext.

Under this scheme, the ciphertext will always be larger than the plaintext. You can™t get around this;
it™s a result of the fact that many ciphertexts decrypt to the same plaintexts. The first probabilistic
encryption scheme [625] resulted in a ciphertext so much larger than the plaintext that it was

However, Manual Blum and Goldwasser have an efficient implementation of probabilistic encryption
using the Blum Blum Shub (BBS) random-bit generator described in Section 17.9 [199].

The BBS generator is based on the theory of quadratic residues. In English, there are two primes, p
and q, that are congruent to 3 modulo 4. That™s the private key. Their product, pq =n, is the public
key. (Mind your ps and qs; the security of this scheme rests in the difficulty of factoring n.)

To encrypt a message, M, first choose some random x, relatively prime to n. Then compute

x0 = x2 mod n

Page 463 of 666
Applied Cryptography: Second Edition - Bruce Schneier

Use x0 as the seed of the BBS pseudo-random-bit generator and use the output of the generator as a
stream cipher. XOR M, one bit at a time, with the output of the generator. The generator spits out bits
bi (the least-significant bit of xi, where xi =xi-12 mod n), so

M = M1 , M2 , M3 , ..., Mt
C = M1 b1 , M2 b2 , M 3 b3 , ..., Mt bt
where t is the length of the plaintext

Append the last computed value, xt, to the end of the message and you™re done.

The only way to decrypt this message is to recover x0 and then set up the same BBS generator to XOR
with the ciphertext. Because the BBS generator is secure to the left, the value xt is of no use to the
cryptanalyst. Only someone who knows p and q can decrypt the message.

In C, the algorithm to recover x0 from xt is:

int x0 (int p, int q, int n, int t, int xt)
int a, b, u, v, w, z;
/* we already know that gcd(p, q) == 1 */
(void)extended_euclidian(p, q, &a, &b);
u = modexp ((p+1)/4, t, p-1);
v = modexp ((q+1)/4, t, q-1);
w = modexp (xt%p, u, p);
z = modexp (xt%q, v, q);
return (b*q*w + a*p*z) % n;

Once you have x0, decryption is easy. Just set up the BBS generator and XOR the output with the

You can make this scheme go even faster by using all the known secure bits of xi, not just the least
significant bit. With this improvement, Blum-Goldwasser probabilistic encryption is faster than RSA
while leaking no partial information about the plaintext. You can also prove that the difficulty of
breaking this scheme is the same as the difficulty of factoring n.

On the other hand, this scheme is totally insecure against a chosen-ciphertext attack. From the least
significant bits of the right quadratic residues, it is possible to calculate the square root of any
quadratic residue. If you can do this, then you can factor. For details, consult [1570,1571,35,36].

23.16 Quantum Cryptography

Quantum cryptography taps the natural uncertainty of the quantum world. With it, you can create a
communications channel where it is impossible to eavesdrop without disturbing the transmission. The
laws of physics secure this quantum channel: even if the eavesdropper can do whatever he wants,
even if the eavesdropper has unlimited computing power, even if P = NP. Charles Bennett, Gilles
Brassard, Claude Cr©peau, and others have expanded on this idea, describing quantum key
distribution, quantum coin flipping, quantum bit commitment, quantum oblivious transfer, and
quantum secure multiparty computation. Their work is described in
[128,129,123,124,125,133,126,394,134,392,396]. The best overview of quantum cryptography can be

Page 464 of 666
Applied Cryptography: Second Edition - Bruce Schneier

found in [131]; [1651] is another good nontechnical overview. A complete bibliography of quantum
cryptography is [237].

This would still be on the lunatic fringe of cryptography, but Bennett and Brassard actually went and
built a working model of the thing [127,121,122]. Now we have experimental quantum cryptography.

So sit back, get yourself something to drink, and relax. I™m going to explain what this is all about.

According to quantum mechanics, particles don™t actually exist in any single place. They exist in
several places at once, with probabilities of being in different places if someone looks. However, it
isn™t until a scientist comes along and measures the particle that it “collapses” into a single location.
But you can™t measure every aspect (for example, position and velocity) of a particle at the same time.
If you measure one of those two quantities, the very act of measuring it destroys any possibility of
measuring the other quantity. The quantum world has a fundamental uncertainty and there™s no way
to avoid it.

That uncertainty can be used to generate a secret key. As they travel, photons vibrate in some
direction; up and down, left to right, or more likely at some angle. Normal sunlight is unpolarized; the
photons vibrate every which way. When a large group of photons vibrate in the same direction they
are polarized. Polarization filters allow only photons that are polarized in a certain direction through;
the rest are blocked. For example, a horizontal polarization filter only allows horizontally polarized
photons through. Turn that filter 90 degrees, and only vertically polarized photons can come through.

Let™s say you have a pulse of horizontally polarized photons. If they try to pass through a horizontally
polarized filter, they all get through. Slowly turn that filter 90 degrees; the number of photons getting
through gets smaller and smaller, until none get through. This is counterintuitive. You™d think that
turning the filter just a little will block all the photons, since the photons are horizontally polarized.
But in quantum mechanics, each particle has a probability of suddenly switching its polarization to
match the filter. If the angle is a little bit off, it has a high probability. If the angle is 90 degrees off, it
has zero probability. And if the angle is 45 degrees off, it has a 50 percent probability of passing
through the filter.

Polarization can be measured in any basis: two directions at right angles. An example basis is
rectilinear: horizontal and vertical. Another is diagonal: left-diagonal and right-diagonal. If a photon
pulse is polarized in a given basis and you measure it in the same basis, you learn the polarization. If
you measure it in the wrong basis, you get a random result. We™re going to use this property to
generate a secret key:

(1) Alice sends Bob a string of photon pulses. Each of the pulses is randomly polarized in
one of four directions: horizontal, vertical, left-diagonal, and right-diagonal.
For example, Alice sends Bob:
(2) Bob has a polarization detector. He can set his detector to measure rectilinear
polarization or he can set his detector to measure diagonal polarization. He can™t do both;
quantum mechanics won™t let him. Measuring one destroys any possibility of measuring the
other. So, he sets his detectors at random, for example:

Now, when Bob sets his detector correctly, he will record the correct polarization. If he sets his
detector to measure rectilinear polarization and the pulse is polarized rectilinearly, he will learn
which way Alice polarized the photon. If he sets his detector to measure diagonal polarization
and the pulse is polarized rectilinearly, he will get a random measurement. He won™t know the
difference. In this example, he might get the result:

Page 465 of 666
Applied Cryptography: Second Edition - Bruce Schneier

(3) Bob tells Alice, over an insecure channel, what settings he used.
(4) Alice tells Bob which settings were correct. In our example, the detector was correctly
set for pulses 2, 6, 7, and 9.
(5) Alice and Bob keep only those polarizations that were correctly measured. In our
example, they keep:

Using a prearranged code, Alice and Bob each translate those polarization measurements into
bits. For example, horizontal and left-diagonal might equal one, and vertical and right-diagonal
might equal zero. In our example, they both have:


So, Alice and Bob have generated four bits. They can generate as many as they like using this system.
On the average, Bob will guess the correct setting 50 percent of the time, so Alice has to send 2n
photon pulses to generate n bits. They can use these bits as a secret key for a symmetric algorithm or
they can guarantee perfect secrecy and generate enough bits for a one-time pad.

The really cool thing is that Eve cannot eavesdrop. Just like Bob, she has to guess which type of
polarization to measure; and like Bob, half of her guesses will be wrong. Since wrong guesses change
the polarization of the photons, she can™t help introducing errors in the pulses as she eavesdrops. If
she does, Alice and Bob will end up with different bit strings. So,Alice and Bob finish the protocol like

(6) Alice and Bob compare a few bits in their strings. If there are discrepancies, they
know they are being bugged. If there are none, they discard the bits they used for comparison
and use the rest.

Enhancements to this protocol allow Alice and Bob to use their bits even in the presence of Eve
[133,134,192]. They could compare only the parity of subsets of the bits. Then, if no discrepancies are
found, they only have to discard one bit of the subset. This detects eavesdropping with only a 50
percent probability, but if they do this with n different subsets Eve™s probability of eavesdropping
without detection is only 1 in 2n .

There™s no such thing as passive eavesdropping in the quantum world. If Eve tries to recover all the
bits, she will necessarily disrupt the communications.

Bennett and Brassard built a working model of quantum key distribution and have exchanged secure
bits on a laser table. The latest I heard, some folks at British Telecom were sending bits over a 10-
kilometer fiber-optic link [276,1245,1533]. They figure ilometers is feasible. The mind boggles.

Part IV
The Real World
Chapter 24
Example Implementations
It™s one thing to design protocols and algorithms, but another thing to field them in operational
systems. In theory, theory and practice are the same; in practice they are different. Often ideas that

Page 466 of 666
Applied Cryptography: Second Edition - Bruce Schneier

look good on paper don™t work in real life. Maybe the bandwidth requirements are too large; maybe
the protocol is too slow. Chapter 10 discusses some of the issues related to using cryptography; this
chapter gives examples of how it has been done in practice.

24.1 IBM Secret-Key Management Protocol

In the late 1970s IBM developed a complete key management system for communications and file
security on a computer network, using only symmetric cryptography [515, 1027]. This protocol is less
important in the actual mechanisms and more in its overall philosophy: By automating the
generation, distribution, installation, storage, changing, and destruction of keys, the protocol went a
long way to ensure the security of the underlying cryptographic algorithms.

This protocol provides three things: secure communications between a server and several terminals,
secure file storage at the server, and secure communication among servers. The protocol doesn™t
really provide for direct terminal-to-terminal communication, although it can be modified to do that.

Each server on the network is attached to a cryptographic facility, which does all of the encrypting
and decrypting. Each server has a Master Key, KM0, and two variants, KM1 and KM2, both of which
are simple variants of KM0. These keys are used to encrypt other keys and to generate new keys. Each
terminal has a Master Terminal Key, KMT, which is used to exchange keys with other terminals.

The servers store KMT, encrypted with KM1. All other keys, such as those used to encrypt files of keys
(called KNF), are stored in encrypted form under KM2. The master key, KM0, is stored in some
nonvolatile security module. Today that could be either a ROM key or a magnetic card, or it could be
typed in by the user (probably as a text string and then key crunched). KM1 and KM2 are not stored
anywhere in the system, but are computed from KM0 whenever they are needed. Session keys, for
communication among servers, are generated with a pseudo-random process in the server. Keys to
encrypt files for storage (KNF) are generated in the same manner.

The heart of the protocol is a tamper-resistant module, called a cryptographic facility. At both the
server and the terminal, all encryption and decryption takes place within this facility. The most
important keys, those used to generate the actual encryption keys, are stored in this module. These
keys can never be read once they are stored. And they are tagged by use: A key dedicated for one
purpose cannot accidentally be used for another. This concept of key control vectors is probably the
most significant contribution of this system. Donald Davies and William Price discuss this key
management protocol in detail [435].

A Variation

A variation on this scheme of master and session keys can be found in [1478]. It™s built around
network nodes with key notarization facilities that serve local terminals. It is designed to:

” Secure two-way communication between any two terminal users.
” Secure communications using encrypted mail.
” Provide personal file protection.
” Provide a digital signature capability.

For communication and file transfer among users, the scheme uses keys generated in the key
notarization facility and sent to the users encrypted under a master key. The identities of the users are
incorporated with the key, to provide evidence that the session key has been used between a particular
pair of users. This key notarization feature is central to the system. Although the system does not use

Page 467 of 666
Applied Cryptography: Second Edition - Bruce Schneier

public-key cryptography, it has a digital-signature-like capability: A key could have only come from a
particular source and could only be read at a particular destination.


One of the earliest implementations of public-key cryptography was the experimental system MEMO
(MITRE Encrypted Mail Office). MITRE is a DoD contractor, a government think tank, and an all-
around bunch of smart guys. MEMO was a secure electronic mail system for users in the MITRENET
network, using public-key cryptography for key exchange and DES for file encryption.

In the MEMO system, all public keys are stored in a Public Key Distribution Center, which is a
separate node on the network. They are stored in an EPROM to prevent anyone from changing them.
Private keys are generated by users or by the system.

For a user to send secure messages, the system first establishes a secure communications path with the
Public Key Distribution Center. The user requests a file of all public keys from the Center. If the user
passes an identification test using his private key, the Center sends this list to the user™s workstation.
The list is encrypted using DES to ensure file integrity.

The implementation uses DES to encrypt messages. The system generates a random DES key for file
encryption; the user encrypts the file with the DES key and encrypts the DES key with the recipient™s
public key. Both the DES-encrypted file and the public-key-encrypted key are sent to the recipient.

MEMO makes no provision for lost keys. There is some provision for integrity checking of the
messages, using checksums. No authentication is built into the system.

The particular public-key implementation used for this system”Diffie-Hellman key exchange over
GF(2127)”was proven insecure before the system was implemented (see Section 11.6), although it is
easy to modify the system to use larger numbers. MEMO was intended mainly for experimental
purposes and was never made operational on the real MITRENET system.

24.3 ISDN

Bell-Northern Research developed a prototype secure Integrated Services Digital Network (ISDN)
telephone terminal [499, 1192, 493, 500]. As a telephone, it was never developed beyond prototype.
The resulting product was the Packet Data Security Overlay. The terminal uses Diffie-Hellman key
exchange, RSA digital signatures, and DES data encryption; it can transmit and receive voice and
data at 64 kilobits per second.


A long-term public-key/private-key key pair is embedded in the phone. The private key is stored in a
tamper-resistant area of the phone. The public key serves as the identification of the phone. These
keys are part of the phone itself and cannot be altered in any way.

Additionally, two other public keys are stored in the phone. One of these keys is the owner™s public
key. This key is used to authenticate commands from the owner and can be changed via a command
signed by the owner. In this way an owner can transfer ownership of the phone to someone else.

The public key of the network is also stored in the phone. This key is used to authenticate commands
from the network™s key management facility and to authenticate calls from other users on the

Page 468 of 666
Applied Cryptography: Second Edition - Bruce Schneier

network. This key can also be changed via a signed command from the owner. This permits the owner
to move his phone from one network to another.

These keys are considered long-term keys: rarely, if ever, changed. A short-term public-key/private-
key key pair is also stored on the phone. These are encapsulated in a certificate signed by the key
management facility. When two phones set up a call, they exchange certificates. The public key of the
network authenticates these certificates.

This exchange and verification of certificates only sets up a secure call from phone to phone. To set up
a secure call from person to person, the protocol has an additional piece. The owner™s private key is
stored on a hardware ignition key, which is inserted into the telephone by the owner. This ignition key
contains the owner™s private key, encrypted under a secret password known only by the owner (not
by the phone, not by the network™s key management facility, not by anybody). It also contains a
certificate signed by the network™s key management facility that contains the owner™s public key and
some identifying information (name, company, job title, security clearance, favorite pizza toppings,
sexual preference, or whatever). This is also encrypted. To decrypt this information and enter it into
the phone, the owner types his secret password on the phone™s keypad. After the phone uses this
information to set up calls, it is erased after the owner removes his ignition key.

The phone also stores a set of certificates from the network™s key management facility. These
certificates authorize particular users to use particular phones.


A call from Alice to Bob works as follows.

(1) Alice inserts her ignition key into the phone and enters her password.
(2) The phone interrogates the ignition key to determine Alice™s identity and gives Alice a
dial tone.
(3) The phone checks its set of certificates to ensure that Alice is authorized to use the
particular phone.
(4) Alice dials the number; the phone places the call.
(5) The two telephones use a public-key cryptography key-exchange protocol to generate
a unique and random session key. All subsequent protocol steps are encrypted using this key.
(6) Alice™s phone transmits its certificate and user authentication.
(7) Bob™s phone authenticates the signatures on both the certificate and the user
authentication using the network™s public key.
(8) Bob™s phone initiates a challenge-and-reply sequence. It demands real-time signed
responses to time-dependent challenges. (This prevents an adversary from using certificates
copied from a previous exchange.) One response must be signed by Alice™s phone™s private key;
another must be signed by Alice™s private key.
(9) Bob™s phone rings, unless he is already on the phone.
(10) If Bob is home, he inserts his ignition key into the phone. His phone interrogates the
ignition key and checks Bob™s certificate as in steps (2) and (3).
(11) Bob transmits his certificate and user authentication.
(12) Alice™s phone authenticates Bob™s signatures as in step (7), and initiates a challenge-
and-reply sequence as in step (8).
(13) Both phones display the identity of the other user and phone on their displays.
(14) The secure conversation begins.
(15) When one party hangs up, the session key is deleted, as are the certificates Bob™s
phone received from Alice™s phone and the certificates Alice™s phone received from Bob™s

Page 469 of 666
Applied Cryptography: Second Edition - Bruce Schneier

Each DES key is unique to each call. It exists only inside the two phones for the duration of the call
and is destroyed immediately afterward. If an adversary captures one or both of the phones involved
in the call, he will not be able to decrypt any previous call between the two phones.

24.4 STU-III

STU stands for “Secure Telephone Unit, ” an NSA-designed secure phone. The unit is about the size
and shape of a conventional telephone, and can be used as such. The phones are also tamper-resistant,
enough so that they are unclassified if unkeyed. They also have a data port and can be used to secure
modem traffic as well as voice [1133].

Whitfield Diffie described the STU-III in [494]:

To make a call with a STU-III, the caller first places an ordinary call to another STU-III,
then inserts a key-shaped device containing a cryptographic variable and pushes a “go
secure” button. After an approximately 15-second wait for cryptographic setup, each
phone shows information about the identity and clearance of the other party on its display
and the call can proceed.

In an unprecedented move, Walter Deeley, NSA™s deputy director for communications
security, announced the STU-III or Future Secure Voice System in an exclusive interview
given to The New York Times [282]. The objective of the new system was primarily to
provide secure voice and low-speed data communications for the U.S. Defense Department
and its contractors. The interview didn™t say much about how it was going to work, but
gradually the word began to leak out. The new system was using public key.

The new approach to key management was reported early on [68] and one article spoke of
phones being “reprogrammed once a year by secure telephone link, ” a turn of phrase
strongly suggestive of a certificate passing protocol, similar to that described [in Section
24.3], that minimizes the need for phones to talk to the key management center. Recent
reports have been more forthcoming, speaking of a key management system called
FIREFLY that [1341] “evolved from public key technology and is used to establish pair-
wise traffic encryption keys.” Both this description and testimony submitted to the U.S.
Congress by Lee Neuwirth of Cylink [1164] suggest a combination of key exchange and
certificates similar to that used in the ISDN secure phone and it is plausible that
FIREFLY too is based on exponentiation.

STU-IIIs are manufactured by AT&T and GE. Somewhere between 300, 000 and 400, 000 have been
fielded through 1994. A new version, the Secure Terminal Equipment (STE), will work on ISDN lines.

24.5 Kerberos

Kerberos is a trusted third-party authentication protocol designed for TCP/IP networks. A Kerberos
service, sitting on the network, acts as a trusted arbitrator. Kerberos provides secure network
authentication, allowing a person to access different machines on the network. Kerberos is based on
symmetric cryptography (DES as implemented, but other algorithms could be used instead). Kerberos
shares a different secret key with every entity on the network and knowledge of that secret key equals
proof of identity.

Kerberos was originally developed at MIT for Project Athena. The Kerberos model is based on
Needham-Schroeder™s trusted third-party protocol (see Section 3.3) [1159]. The original version of

Page 470 of 666
Applied Cryptography: Second Edition - Bruce Schneier

Kerberos, Version 4, is specified in [1094, 1499]. (Versions 1 through 3 were internal development
versions.) Version 5, modified from Version 4, is specified in [876, 877, 878]. The best overview of
Kerberos is [1163]. Other survey articles are [1384, 1493], and two good articles on using Kerberos in
the real world are [781, 782].

The Kerberos Model

The basic Kerberos protocol was outlined in Section 3.3. In the Kerberos model, there are entities”
clients and servers”sitting on the network. Clients can be users, but can also be independent
software programs that need to do things: download files, send messages, access databases, access
printers, obtain administrative privileges, whatever.

Kerberos keeps a database of clients and their secret keys. For a human user, the secret key is an
encrypted password. Network services requiring authentication, as well as clients who wish to use
these services, register their secret key with Kerberos.

Because Kerberos knows everyone™s secret key, it can create messages that convince one entity of
another entity™s identity. Kerberos also creates session keys which are given to a client and a server
(or to two clients) and no one else. A session key is used to encrypt messages between the two parties,
after which it is destroyed.

Kerberos uses DES for encryption. Kerberos Version 4 provided a nonstandard mode for
authentication. This mode is weak: It fails to detect certain changes to the ciphertext (see Section
9.10). Kerberos Version 5 uses CBC mode.

Figure 24.1 Kerberos authentication steps.

How Kerberos Works

This section discusses Kerberos Version 5. I will outline the differences between Version 4 and
Version 5 further on. The Kerberos protocol is straightforward (see Figure 24.1). A client requests a
ticket for a Ticket-Granting Service (TGS) from Kerberos. This ticket is sent to the client, encrypted
in the client™s secret key. To use a particular server, the client requests a ticket for that server from
the TGS. Assuming everything is in order, the TGS sends the ticket back to the client. The client then
presents this ticket to the server along with an authenticator. Again, if there™s nothing wrong with the
client™s credentials, the server lets the client have access to the service.

Table 24.1
Kerberos Table of Abbreviations
c = client
s = server
a = client™s network address
v = beginning and ending validity time for a ticket

Page 471 of 666
Applied Cryptography: Second Edition - Bruce Schneier

t = timestamp
Kx = x˜s secret key
Kx, y = session key for x and y
{m}Kx = m encrypted in x˜s secret key
Tx, y = x˜s ticket to use y
Ax, y = authenticator from x to y


Kerberos uses two types of credentials: tickets and authenticators. (The rest of this section uses the
notation used in Kerberos documents”see Table 24.1.) A ticket is used to pass securely to the server
the identity of the client for whom the ticket was issued. It also contains information that the server
can use to ensure that the client using the ticket is the same client to whom the ticket was issued. An
authenticator is an additional credential, presented with the ticket.

A Kerberos ticket takes this form:

Tc, s = s, {c, a, v, Kc, s}Ks

A ticket is good for a single server and a single client. It contains the client™s name and network
address, the server™s name, a timestamp, and a session key. This information is encrypted with the
server™s secret key. Once the client gets this ticket, she can use it multiple times to access the server”
until the ticket expires. The client cannot decrypt the ticket (she does not know the server™s secret
key), but she can present it to the server in its encrypted form. No one listening on the network can
read or modify the ticket as it passes through the network.

A Kerberos authenticator takes this form:

Ac, s = {c, t, key}Kc, s

The client generates it every time she wishes to use a service on the server. The authenticator contains
the client™s name, a timestamp, and an optional additional session key, all encrypted with the session
key shared between the client and the server. Unlike a ticket, it can only be used once. However, since
the client can generate authenticators as needed (it knows the shared secret key), this is not a problem.

The authenticator serves two purposes. First, it contains some plaintext encrypted in the session key.
This proves that it also knows the key. Just as important, the sealed plaintext includes the timestamp.
An eavesdropper who records both the ticket and the authenticator can™t replay them two days later.

Kerberos Version 5 Messages

Kerberos Version 5 has five messages (see Figure 24.1):

Page 472 of 666
Applied Cryptography: Second Edition - Bruce Schneier

1. Client to Kerberos: c, tgs
2. Kerberos to client: {Kc, tgs}Kc, {Tc, tgs}Ktgs
3. Client to TGS: {Ac, s}Kc, tgs, {Tc, tgs}Ktgs
4. TGS to client: {Kc, s}Kc, tgs, {Tc, s}Ks
5. Client to server: {Ac, s}Kc, s, {Tc, s}Ks

These will now be discussed in detail.

Getting an Initial Ticket

The client has one piece of information that proves her identity: her password. Obviously we don™t
want her to send this password over the network. The Kerberos protocol minimizes the chance that
this password will be compromised, while at the same time not allowing a user to properly
authenticate herself unless she knows the password.

The client sends a message containing her name and the name of her TGS server to the Kerberos
authentication server. (There can be many TGS servers.) In reality, the user probably just enters her
name into the system and the login program sends the request.

The Kerberos authentication server looks up the client in his database. If the client is in the database,
Kerberos generates a session key to be used between her and the TGS. This is called a Ticket
Granting Ticket (TGT). Kerberos encrypts that session key with the client™s secret key. Then it
creates a TGT for the client to authenticate herself to the TGS, and encrypts that in the TGS™s secret
key. The authentication server sends both of these encrypted messages back to the client.

The client now decrypts the first message and retrieves the session key. The secret key is a one-way
hash of her password, so a legitimate user will have no trouble doing this. If the user were an
imposter, he would not know the correct password and therefore could not decrypt the response from
the Kerberos authentication server. Access would be denied and he wouldn™t be able to get the ticket
or the session key.

The client saves the TGT and session key and erases the password and the one-way hash. This
information is erased to reduce the chance of compromise. If an adversary manages to copy the
client™s memory, he will only get the TGT and the session key. These are valuable pieces of
information, but only during the lifetime of the TGT. After the TGT expires, they will be worthless.

The client can now prove her identity to the TGS for the lifetime of the TGT.

Getting Server Tickets

A client has to obtain a separate ticket for each service she wants to use. The TGS grants tickets for
individual servers.

When a client needs a ticket that she does not already have, she sends a request to the TGS. (In
reality, the program would do this automatically, and it would be invisible to the user.)

The TGS, upon receiving the request, decrypts the TGT with his secret key. Then he uses the session
key included in the TGT to decrypt the authenticator. Finally, he compares the information in the

Page 473 of 666
Applied Cryptography: Second Edition - Bruce Schneier

authenticator with the information in the ticket, the client™s network address with the address the
request was sent from, and the timestamp with the current time. If everything matches, he allows the
request to proceed.

Checking timestamps assumes that all machines have synchronized clocks, at least to within several
minutes. If the time in the request is too far in the future or the past, the TGS treats the request as an
attempt to replay a previous request. The TGS should also keep track of all live authenticators,
because past requests can have timestamps that are still valid. Another request with the same ticket
and timestamp as one already received can be ignored.

The TGS responds to a valid request by returning a valid ticket for the client to present to the server.
The TGS also creates a new session key for the client and the server, encrypted with the session key
shared by the client and the TGS. Both of these messages are then sent back to the client. The client
decrypts the message and extracts the session key.

Requesting a Service

Now the client is ready to authenticate herself to the server. She creates a message very similar to the
one sent to the TGS (which makes sense, since the TGS is a service).

The client creates an authenticator, consisting of her name and network address, and a timestamp,
encrypted with the session key for her and the server that the TGS generated. The request consists of
the ticket received from Kerberos (already encrypted with the server™s secret key) and the encrypted

The server decrypts and checks the ticket and the authenticator, as discussed previously, and also
checks the client™s address and the timestamp. If everything checks out, the server knows that,
according to Kerberos, the client is who she says she is.

For applications that require mutual authentication, the server sends the client back a message
consisting of the timestamp, encrypted with the session key. This proves that the server knew his
secret key and could decrypt the ticket and therefore the authenticator.

The client and the server can encrypt future messages with the shared key, if desired. Since only they
share this key, they both can assume that a recent message encrypted in that key originated with the
other party.

Kerberos Version 4

The previous sections discussed Kerberos Version 5. In the messages and the construction of the
tickets and authenticators, Version 4 is slightly different.

In Kerberos Version 4, the five messages looked like:

1. Client to Kerberos: c, tgs
2. Kerberos to client: {Kc, tgs, {Tc, tgs}Ktgs}Kc
3. Client to TGS: {Ac, s}Kc, tgs, {Tc, tgs}Ktgs, s
4. TGS to client: {Kc, s, {Tc, s}Ks}Kc, tgs
5. Client to server: {Ac, s}Kc, s, {Tc, s}Ks

Page 474 of 666
Applied Cryptography: Second Edition - Bruce Schneier

Tc, s = {s, c, a, v, l, Kc, s}Ks
Ac, s = {c, a, t}Kc, s

Messages 1, 3, and 5 are identical. The double encryption of the ticket in steps 2 and 4 has been
removed in Version 5. The Version 5 ticket adds the possibility of multiple addresses, and it replaces a
“lifetime” field, l, with a beginning and ending time. The Version 5 authenticator adds the option of
including an additional key.

Security of Kerberos

Steve Bellovin and Michael Merritt discussed several potential security vulnerabilities of Kerberos
[108]. Although this paper was written about the Version 4 protocols, many of their comments also
apply to Version 5.

It may be possible to cache and replay old authenticators. Although timestamps are supposed to
prevent this, replays can be done during the lifetime of the ticket. Servers are supposed to store all
valid tickets to prevent replays, but this is not always possible. And ticket lifetimes can be long; eight
hours is typical.

Authenticators rely on the fact that all the clocks in the network are more or less synchronized. If a
host can be fooled about the correct time, then an old authenticator can be replayed without any
problem. Most network time protocols are insecure, so this can be a serious problem.

Kerberos is also vulnerable to password-guessing attacks. An intruder can collect tickets and then try
to decrypt them. Remember that the average user doesn™t usually choose good passwords. If Mallory
collects enough tickets, his chances of recovering a password are good.

Perhaps the most serious attack involves malicious software. The Kerberos protocols rely on the fact
that the Kerberos software is trustworthy. There™s nothing to stop Mallory from surreptitiously
replacing all client Kerberos software with a version that, in addition to completing the Kerberos
protocols, records passwords. This is a problem with any cryptographic software package on an
insecure computer, but the widespread use of Kerberos in these environments makes it a particularly
tempting target.

Enhancements to Kerberos are in the works, including an implementation of public-key cryptography
and a smart-card interface for key management.


Kerberos is not in the public domain, but MIT™s code is freely available. Actually implementing it into
a working UNIX environment is another story. Several companies sell versions of Kerberos, but you
can get a good version free from Cygnus Support, 814 University Ave., Palo Alto, CA, 94301; (415)
322-3811; fax: (415) 322-3270.

24.6 KryptoKnight

KryptoKnight (Kryptonite”get it?) is an authentication and key distribution system designed by
IBM. It is a secret-key protocol and uses either DES in CBC mode (see Section 9.3) or a modified
version of MD5 (see Section 18.5).

Page 475 of 666
Applied Cryptography: Second Edition - Bruce Schneier

KryptoKnight supports four security services:

” User authentication (called single sign-on)
” Two-party authentication
” Key distribution
” Authentication of data origin and content

From a user™s perspective, KryptoKnight is similar to Kerberos. Some differences are:

” KryptoKnight uses a hash function for authentication and encrypting tickets.
” KryptoKnight does not rely on synchronized clocks; it uses nonces for challenges (see
Section 3.3).
” If Alice wishes to communicate with Bob, KryptoKnight has the option of allowing
Alice to send a message to Bob and then for Bob to initiate the key exchange protocol.

KryptoKnight has tickets and authenticators, just like Kerberos. It has TGSs, but KryptoKnight calls
them authentication servers. KryptoKnight™s designers spent considerable effort minimizing the
number of messages, lengths of messages, and amount of encryption. For further information on
KryptoKnight, read [1110, 173, 174, 175].


SESAME stands for Secure European System for Applications in a Multivendor Environment. It™s a
European Community security project, 50 percent funded by RACE (see Section 25.7), whose
primary objective is producing technology for user authentication with distributed access control.
Think of it as kind of a European version of Kerberos. It™s a two-part project: Stage one is a basic
prototype of the architecture, and stage two is a set of commercial projects. The three companies with
the greatest hand in development are ICL in the United Kingdom, Siemens in Germany, and Bull in

SESAME is an authentication and key-exchange system [361, 1248, 797, 1043]. It uses the Needham-
Schroeder protocol, with public-key cryptography to communicate between different security
domains. The system is seriously flawed in several respects. Instead of using a real encryption
algorithm, they use XOR with a 64-bit key size. Even worse, they use XOR in CBC mode, which
leaves half the plaintext unencrypted. In their defense, they planned on using DES until the French
government complained; they validated the code with DES but then removed it, and expect people to
add it back. I am unimpressed nonetheless.

Authentication in SESAME is a function on the first block of a message, not on the entire message.
This has the effect of authenticating “Dear Sir” and not the body of a letter. Key generation consists
of two calls to the UNIX rand function, which isn™t very random. SESAME uses crc32 and MD5 as
one-way hash functions. And of course, SESAME is vulnerable to Kerberos-like password-guessing.

24.8 IBM Common Cryptographic Architecture

The Common Cryptographic Architecture (CCA) was designed and developed by IBM to provide
cryptographic primitives for confidentiality, integrity, key management, and personal identification
number (PIN) processing [751, 784, 1025, 1026, 940,752]. Keys are managed by control vectors (CVs)
(see Section 8.5). Every key has a CV XORed with it and is never separated from the vector unless
inside secure hardware. The CV is a data structure providing an intuitive understanding of the
privileges associated with a particular key.

Page 476 of 666
Applied Cryptography: Second Edition - Bruce Schneier

The individual bits of the CV are defined to have specific meanings for using and handling each key
managed by CCA. The CV is carried with the encrypted key in data structures called key tokens.
Internal key tokens are used locally and contain keys encrypted under the local master key (MK).
External key tokens are used to export and import encrypted keys between systems. Keys in external
key tokens are encrypted under key-encrypting keys (KEK). The KEKs are managed in internal key
tokens. Keys are separated according to their permitted uses.

Key length is also specified and enforced using bits in the CV. Single length keys are 56 bits and are
used for such functions as privacy and message authentication. Double length keys are 112 bits and
are used for key management, PIN functions, and other special uses. Keys can be required to be
DOUBLE-ONLY in which both the left and right halves of the key must be different, DOUBLE in
which the halves are permitted to be equal by chance, SINGLE-REPLICATED in which the left and
right halves are equal, or SINGLE which contains only 56 bits. The CCA functions specify hardware
enforcement of certain key types to be used for some operations.

The CV is checked in a secure hardware processor: It must conform to the permitted CCA rules for
each CCA function. If the CV successfully passes the test requirements, a variant of the KEK or MK
is obtained by the XOR of the KEK or MK with the CV, and the plaintext target key is recovered for
use internally with the CCA function. When new keys are generated, the CV specifies the uses of the
generated key. Those combinations of key types that could be used in attacking the system are not
generated or imported into a CCA-compliant system.

CCA uses a combination of public-key cryptography and secret-key cryptography for key
distribution. The KDC shares a secret master key with each user and encrypts session keys using that
master key. Master keys are distributed using public-key cryptography.

The system™s designers chose this hybrid approach for two reasons. The first is performance. Public-
key cryptography is computationally intensive; if session keys are distributed using public-key
cryptography, the system might bog down. The second is backwards compatibility; this system can be
overlaid on existing secret-key schemes with minimal disruption.

CCA systems are designed to be interoperable. For systems that are non-CCA compliant, a Control
Vector Translate (CVXLT) function permits keys to be passed between the two implementations.
Initialization of the CVXLT function requires dual control. Two individuals must set up the required
translation tables independently. Such dual control provides a high degree of assurance concerning
the integrity and pedigree of any keys introduced into the system.

A key of type DATA is provided for compatibility with other systems. A DATA key is stored with a
CV that identifies the key as a DATA key. DATA keys can have broad uses and as such must be
regarded with suspicion and used with care. DATA keys may not be used for any key management

The Commercial Data Masking Facility (CDMF) provides an exportable version of CCA. It has a
special feature that reduces DES keys to an effective 40 bits for export (see Section 15.5) [785].

24.9 ISO Authentication Framework

Public-key cryptography has been recommended for use with the ISO authentication framework, also
known as the X.509 protocols [304]. This framework provides for authentication across networks.
Although no particular algorithms are specified for either security or authentication, the specification
recommends RSA. There are provisions, however, for multiple algorithms and hash functions. X.509
was initially issued in 1988. After public review and comment, it was revised in 1993 to correct some

Page 477 of 666
Applied Cryptography: Second Edition - Bruce Schneier

security problems [1100, 750].

Figure 24.2 An X.509 certificate.


The most important part of X.509 is its structure for public-key certificates. Each user has a distinct
name. A trusted Certification Authority (CA) assigns a unique name to each user and issues a signed
certificate containing the name and the user™s public key. Figure 24.2 shows an X.509 certificate [304].

The version field identifies the certificate format. The serial number is unique within the CA. The
next field identifies the algorithm used to sign the certificate, together with any necessary parameters.
Issuer is the name of the CA. The period of validity is a pair of dates; the certificate is valid during the
time period between the two. Subject is the name of the user. The subject™s public key information
includes the algorithm name, any necessary parameters, and the public key. The last field is the CA™s

If Alice wants to communicate with Bob, she first gets his certificate from a database. Then she
verifies its authenticity. If both share the same CA, this is easy. Alice simply verifies the CA™s
signature on Bob™s certificate.

If they use different CAs, it™s more complicated. Think of a tree structure, with different CAs
certifying other CAs and users. On the top is one master CA. Each CA has a certificate signed by the
CA above it, and by the CAs below it. Alice uses these certificates to verify Bob™s certificate.

Figure 24.3 illustrates this. Alice™s certificate is certified by CAA ; Bob™s is certified by CAB. Alice
knows CAA™s public key. CAC has a certificate signed by CAA, so Alice can verify that. CAD has a
certificate signed by CAC. CAB has a certificate signed by CAD. And Bob™s certificate is signed by
CAB. By moving up the certification tree to a common point, in this case CAD, and then down to Bob,
Alice can verify Bob™s certificate.

Page 478 of 666
Applied Cryptography: Second Edition - Bruce Schneier

Figure 24.3 Sample certification hierarchy.

Certificates can be stored on databases around the network. Users can send them to each other. When
a certificate expires, it should be removed from any public directories. The issuing CA, however,
should maintain a copy of the certificate. Should a dispute arise later, it will be required.

Certificates can also be revoked, either because the user™s key has been compromised, the CA™s key
has been compromised, or because the CA no longer wants to certify the user. Each CA must
maintain a list of all revoked but not expired certificates. When Alice receives a new certificate, she
should check to see if it has been revoked. She can check a database of revoked keys on the network,
but more likely she will check a locally cached list of revoked certificates. There are certainly possible
abuses to this system; key revocation is probably its weakest part.

Authentication Protocols

Alice wants to communicate with Bob. First she goes to a database and obtains what is called a
certification path from Alice to Bob, and Bob™s public key. At this point Alice can initiate either a one-
way, two-way, or three-way authentication protocol.

The one-way protocol is a single communication from Alice to Bob. It establishes the identities of both
Alice and Bob and the integrity of any information communicated by Alice to Bob. It also prevents
any replay attacks on the communication.

The two-way protocol adds a reply from Bob. It establishes that Bob, and not an imposter, sent the
reply. It also establishes the secrecy of both communications and prevents replay attacks.

Both the one-way and two-way protocols use timestamps. A three-way protocol adds another message
from Alice to Bob and obviates the need for timestamps (and therefore authenticated time).

The one-way protocol is:

(1) Alice generates a random number, RA.
(2) Alice constructs a message, M = (TA, RA, IB, d), where TA is Alice™s timestamp, IB is
Bob™s identity, and d is an arbitrary piece of data. The data may be encrypted with Bob™s public
key, EB, for security.
(3) Alice sends (CA, DA (M)) to Bob. (CA is Alice™s certificate; DA is Alice™s private key.)
(4) Bob verifies CA and obtains EA. He makes sure these keys have not expired. (EA is
Alice™s public key.)
(5) Bob uses EA to decrypt DA(M). This verifies both Alice™s signature and the integrity of

Page 479 of 666
Applied Cryptography: Second Edition - Bruce Schneier

the signed information.
(6) Bob checks the IB in M for accuracy.
(7) Bob checks the TA in M and confirms that the message is current.
(8) As an option, Bob can check RA in M against a database of old random numbers to
ensure the message is not an old one being replayed.

The two-way protocol consists of the one-way protocol and then a similar one-way protocol from Bob
to Alice. After executing steps (1) through (8) of the one-way protocol, the two-way protocol continues

(9) Bob generates another random number, RB.
(10) Bob constructs a message M™ = (TB, RB, IA, RA, d), where TB is Bob™s timestamp, IA is
the identity of Alice and d is arbitrary data. The data may be encrypted with Alice™s public key,
EA, for security. RA is the random number Alice generated in step (1).
(11) Bob sends DB(M™) to Alice.
(12) Alice uses EB to decrypt DB(M™). This verifies both Bob™s signature and the integrity
of the signed information.
(13) Alice checks the IA in M™ for accuracy.
(14) Alice checks the TB in M™ and confirms that the message is current.
(15) As an option, Alice can check the RB in M™ to ensure the message is not an old one
being replayed.

The three-way protocol accomplishes the same thing as the two-way protocol, but without timestamps.
Steps (1) through (15) are identical to the two-way protocol, with TA = TB = 0.

(16) Alice checks the received version of RA against the RA she sent to Bob in step (3).
(17) Alice sends DA(RB) to Bob.
(18) Bob uses EA to decrypt DA(RB). This verifies both Alice™s signature and the integrity
of the signed information.
(19) Bob checks the received version of RB against the RB he sent to Alice in step (10).

24.10 Privacy-Enhanced Mail (PEM)

PEM is the Internet Privacy-Enhanced Mail standard, adopted by the Internet Architecture Board
(IAB) to provide secure electronic mail over the Internet. It was initially designed by the Internet
Research Task Force (IRTF) Privacy and Security Research Group (PSRG), and then handed over to
the Internet Engineering Task Force (IETF) PEM Working Group. The PEM protocols provide for
encryption, authentication, message integrity, and key management.

The complete PEM protocols were initially detailed in a series of RFCs (Requests for Comment) in
[977] and then revised in [978]. The third iteration of the protocols [979, 827, 980] is summarized in
[177, 178]. The protocols were modified and improved, and the final protocols are detailed in another
series of RFCs [981, 825, 76, 802]. Another paper by Matthew Bishop [179] details the changes.
Reports of attempts to implement PEM include [602, 1505, 1522, 74, 351, 1366, 1367]. See also [1394].

PEM is an inclusive standard. The PEM procedures and protocols are intended to be compatible with
a wide range of key-management approaches, including both symmetric and public-key schemes to
encrypt data-encrypting keys. Symmetric cryptography is used for message-text encryption.

Page 480 of 666
Applied Cryptography: Second Edition - Bruce Schneier

Cryptographic hash algorithms are used for message integrity. Other documents support key-
management mechanisms using public-key certificates; algorithms, modes, and associated identifiers;
and paper and electronic format details and procedures for the key-management infrastructure to
support these services.

PEM supports only certain algorithms, but allows for different suites of algorithms to be specified
later. Messages are encrypted with DES in CBC mode. Authentication, provided by something called
a Message Integrity Check (MIC), uses either MD2 or MD5. Symmetric key management can use
either DES in ECB mode or triple-DES using two keys (called EDE mode). PEM also supports public-
key certificates for key management, using the RSA algorithm (key length up to 1024 bits) and the
X.509 standard for certificate structure.

PEM provides three privacy-enhancement services: confidentiality, authentication, and message
integrity. No special processing requirements are imposed on the electronic mail system. PEM can be
incorporated selectively, by site or by user, without affecting the rest of the network.

PEM Documents

The specifications for PEM come from four documents:

” RFC 1421: Part I, Message Encryption and Authentication Procedures. This document
defines message encryption and authentication procedures in order to provide privacy-
enhanced mail services for electronic mail transfer on the Internet.
” RFC 1422: Part II, Certificate-Based Key Management. This document defines a
supporting key management architecture and infrastructure, based on public-key certificate
techniques to provide keying information to message originators and recipients.
” RFC 1423: Part III, Algorithms, Modes, and Identifiers. This document provides
definitions, formats, references, and citations for cryptographic algorithms, usage modes, and
associated identifiers and parameters.
” RFC 1424: Part IV, Key Certification and Related Services. This document describes
three types of service in support of PEM: key certification, certificate revocation list (CRL)
storage, and CRL retrieval.


PEM is compatible with the authentication framework described in [304]; see also [826]. PEM is a
superset of X.509; it establishes procedures and conventions for a key-management infrastructure for
use with PEM and with other protocols (from both the TCP/IP and OSI suites) in the future.

The key-management infrastructure establishes a single root for all Internet certification. The
Internet Policy Registration Authority (IPRA) establishes global policies that apply to all certification
under this hierarchy. Beneath the IPRA root are Policy Certification Authorities (PCAs), each of
which establishes and publishes its policies for registering users or organizations. Each PCA is
certified by the IPRA. Below PCAs, CAs certify users and subordinate organizational entities (such as
departments, offices, subsidiaries). Initially, the majority of users are expected to be registered with
some organization.

Some PCAs are expected to provide certification for users who wish to register independent of any
organization. For users who wish anonymity while taking advantage of PEM privacy facilities, one or
more PCAs are expected to be established with policies that allow for registration of users who do not
wish to disclose their identities.

Page 481 of 666
Applied Cryptography: Second Edition - Bruce Schneier

PEM Messages

PEM™s heart is its message format. Figure 24.4 shows an encrypted message using symmetric key
management, Figure 24.5 shows an authenticated and encrypted message using public-key key
management, and Figure 24.6 shows an authenticated (but unencrypted) message using public-key
key management.


. 20
( 29)