Chapter 8

Key Management

If the doors of perception were cleansed everything would appear to man as
it is, inļ¬nite.
William Blake (1757ā“1827) English Poet

A cryptographic scheme is only as strong as the security of its keys. This
chapter is devoted to key management ā” the secure generation, distribution,
and storage of keys. These are aspects of public key infrastructure ā” protocols,
services, and standards ā” used in concert as an ediļ¬ce to support secure public-
key cryptography, which we will discuss in Section 8.3. However, we already have
been introduced to a means of key recovery for digital cash schemes discussed
in Section 7.3. Thus, we begin with a section that looks at more general such
schemes to be used in public-key cryptosystems.

8.1 Secret Sharing
We became acquainted with a secret sharing scheme in Section 7.3, where
we discussed secret splitting between two entities on page 144. This is the
simplest form of secret sharing, and can easily be generalized to N ā N entities
by simply breaking up the message into N distinct pieces mj so that m =
m1 ā• m2 ā• Ā· Ā· Ā· ā• mN . We now look at some other secret sharing schemes.
The prime motivations for secret sharing of cryptographic keys are to ensure
schemes for key recovery (of lost keys) and to address the problem of autho-
rization of key use. Secret sharing assures that the key can be used only when
certain groups of authorized participants are present and agree. This protects
the key from misuse and allows for security of backup copies of keys.
The origins of secret sharing may be traced to the 1979 (independent) work
of Blakely [27] and Shamir [202]. We begin with a secret sharing scheme due to
Shamir.
Suppose that we have a bank vault and no single individual can be trusted
with the combination. One way is to split the combination among three entities,
any two of whom can open the vault. This notion can be formalized.

153
Ā© 2003 by CRC Press LLC
154 8. Key Management

Deļ¬nition 8.1 (Threshold Schemes)8.1
Let t, w ā N such that t ā¤ w. A (t, w)-threshold scheme is a method of
sharing a message m among a set S of w entities such that any subset of t of
them can recover m, but no smaller subset can do so. If Pj ā S knows mj , then
mj is called a share (sometimes called a shadow) for the participant Pj .

The secret splitting discussed in Section 7.3 is an example of a (2, 2) threshold
scheme. The following also goes by the name of the Lagrange Interpolation
Scheme. In fact, the reader must be familiar with the Lagrange interpolation
formula, Theorem C.40, given in Appendix C on page 222.
x Shamirā™s Threshold Scheme
Trent distributes shares of m to w ā N participants of whom any t ā¤ w of
them will be able to recover m.
Setup Stage: Trent performs the following.
(1) Choose a prime p > max(m, w), where p is public, and set m0 = m ā Z/pZ.
(2) Select t ā’ 1 random integers cj for j = 1, 2, . . . , t ā’ 1 and set
tā’1 tā’1
p(x) ā” m + cj x ā”
j
cj xj (mod p),
j=1 j=0

where c0 = m.
(3) Compute p(xk ) ā” mk (mod p) for distinct integers xk ā¤ p ā’ 1 and securely
distribute the share (xk , mk ) to participant Pk for 1 ā¤ k ā¤ w.

Pooling Shares: Without loss of generality, suppose a group of t partici-
pants Pk for 1 ā¤ k ā¤ t get together and plug their shares into the Lagrange
interpolation formula:
t t
xā’x
f (x) = mk = mk Kk (x),
xk ā’ x
k=1 k=1
1ā¤ ā¤t
=k

where
xā’x
Kk (x) = .
xk ā’ x
1ā¤ ā¤t
=k

Then by Exercise 8.1,

f (xk ) ā” mk (mod p), for 1 ā¤ k ā¤ t
can be shown that for any t ā¤ w and t > 1, there exists a (t, w)-threshold scheme (see
8.1 It

[127]).

Ā© 2003 by CRC Press LLC
8.1. Secret Sharing 155

and by Exercise 8.2,
t
p(0) ā” f (0) ā” mk Kk (0) ā” m (mod p).
k=1

Example 8.2 Let p = 3361, m = 3001, w = 5, and t = 3 in the Shamir
threshold scheme. Select

p(x) = 111x2 + 256x + 3001.

Then compute p(xi ) for x1 = 1, x2 = 2, x3 = 3, x4 = 4, x5 = 5, since we only
need ensure that the xi are distinct and less than p. We get

(x1 , m1 ) = (1, 7), (x2 , m2 ) = (2, 596), (x3 , m3 ) = (3, 1407),

(x4 , m4 ) = (4, 2440), and (5, m5 ) = (5, 334).
we select i = 1, 3, 5 for pooling among the three participants and calculate the
Lagrange interpolation formula to be,
2473 2 3873 12963
f (x) = ā’ xā’
x+ ,
8 2 8
Since
8ā’1 ā” 2941 (mod p), 2ā’1 ā” 1681 (mod p),
then
ā’2473 Ā· 2941 ā” 111 (mod p), 3873 Ā· 1681 ā” 256 (mod p),
and
ā’2941 Ā· 12963 ā” 3001 (mod p).
Thus, the participants consider f (x) ā” 111x2 + 256x + 3001 (mod p), and com-
pute f (0) ā” 3001 ā” m (mod p) to recover the message. See Exercises 8.3ā“8.7.

In Shamirā™s scheme, no fewer than t participants can recover m (a property
that makes it an example of what is sometimes called a perfect threshold scheme).
Thus, knowing only t ā’ 1 shares does not give an advantage to a participant
over an adversary who does not know any of the shares, other than the size
of m, which does not help to recover it. Furthermore, the security of Shamirā™s
scheme does not rely upon the assumed intractability of such problems as the
DLP or the IFP. Thus, the scheme is as secure as a one-time pad in the sense
that an exhaustive search of all possible shares will reveal to an adversary that
any message m could be the secret.
There are variations on Shamirā™s scheme. For instance, suppose that the
CEO of a large corporation wants to control the majority of the shares in a
scheme for secret sharing the combination to the company vault. Suppose that
t = 7 shares are required and the CEO has 5 shares while other participants have

Ā© 2003 by CRC Press LLC
156 8. Key Management

only 1 share. Therefore, the CEO gets together with two underlings to recover
the combination, but without participation by the CEO, it takes 7 participants
to recover it.
Another variation on Shamirā™s scheme is illustrated by the following scenario.
Suppose that two corporations A and B hold their securities in the same vault.
They wish to create a scheme where 2 participants from corporation A and 3
participants from corporation B hold shares. Here is how they do it. Take a
linear polynomial p1 and a quadratic polynomial p2 , and form their product.
Then give w1 ā„ 2 employees of corporation A a share p1 (xi ) for 1 ā¤ i ā¤ w1 , and
give w2 ā„ 3 employees from corporation B a share p2 (yi ) for 1 ā¤ i ā¤ w2 . Then
any two participants from corporation A can get together and recover p1 but
not p2 , and any 3 participants from corporation B can get together and recover
p2 but not p1 . Participants from both corporations A and B must act in concert
to recover the full combination determined by the product p1 p2 acting on the
individual shares.
Another secret sharing scheme [7] developed in 1983 which uses the Chinese
Remainder Theorem, is the following.
x Asmuth-Bloom Threshold Scheme
This is a (t, w)-threshold scheme for sharing a secret m.
Setup Stage: Each of the following is executed.
(1) Choose a large prime p > m, where p is public.
(2) Select pairwise relatively prime values aj ā (Z/pZ)ā— for j = 1, 2, . . . , w such
that a1 < a2 < Ā· Ā· Ā· < aw .

Share Creation and Distribution: Each of the following is executed.
t
(1) Select a random value r ā N such that m + rp < j=1 aj . (One must be
careful to select the values so that (the rare event) m + rp < aj does not
occur. Otherwise, participant j has the secret.)
(3) Securely distribute shares sj ā” m + rp (mod aj ) for j = 1, 2, . . . , w ā„ t,
together with aj and p.

Pooling Shares: Any t participants can get together to recover m using
the Chinese Remainder Theorem, but less than t cannot.

Example 8.3 Let p = 2111, t = 3, w = 4, m = 291, and select (a1 , a2 , a3 , a4 ) =
(1193, 1213, 1217, 1223). Then randomly choose r = 834264. Since

m + rp = 1761131595 < a1 Ā· a2 Ā· a3 = 1761131653,

then we compute the shares s1 ā” 1135 (mod 1193); s2 ā” 1155 (mod 1213); s3 ā”
1159 (mod 1217), and securely distribute them. The participants gather and use
the Chinese Remainder Theorem to solve the three congruences to recover m+rp,
and the secret message via, 1761131595 ā” 291 (mod 2111). See Exercises 8.8ā“
8.12

Ā© 2003 by CRC Press LLC
8.1. Secret Sharing 157

We close this section with a secret sharing scheme based upon vector spaces
and matrices (see Appendix C for a reminder of the basic notions). The following
scheme [27] was introduced in 1979. This is not a (t, w)-threshold scheme.
x Blakelyā™s Secret Sharing Vector Scheme
The secret message is m1 to be reconstructed by t > 2 participants.
Setup Stage: The following are executed.
(1) Choose a large prime p > m1 , where p is made public, and select
m2 , m3 , . . . , mt ā Fp at random. Then m = (m1 , m2 , . . . , mt ) is a point in
the t-dimensional vector space Ft . p

(j) (j)
(2) For each j = 1, 2, . . . , t, select n1 , . . . , ntā’1 ā Fp at random and set
tā’1
(j)
cj ā” mt ā’ ni mi (mod p).
i=1

(3) Each of the t participants is given the equation for a hyperplane in Fp as
follows,
tā’1
(j)
ā” cj + ni xi (mod p),
j
i=1

for j = 1, 2, . . . , t, where the intersection of the t hyperplanes must be the
point m.

Pooling Stage: The participants gather to reconstruct the secret message
as follows. They form the equations,
tā’1
(j)
ni xi ā’ ā” ā’cj (mod p),
j
i=1

for j = 1, 2, . . . , t. In matrix terminology, this translates into the following

ļ£« ļ£¶ļ£« ļ£¶ ļ£« ļ£¶
(1) (1) (1)
Ā· Ā· Ā· ntā’1 ā’1 ā’c1
n1 n2 x1
ļ£¬ ļ£·ļ£¬ ļ£·ļ£¬ ļ£·
ā’c2
(2) (2) (2)
ļ£¬ ļ£·ļ£¬
Ā· Ā· Ā· ntā’1 ā’1 x2
n1 n2 ļ£·ļ£¬ ļ£·
AX ā” ļ£¬ ļ£·ļ£¬ ļ£·ā”ļ£¬ ļ£· (mod p). (8.4)
ļ£¬ ļ£·ļ£­ . .
. . . . ļ£øļ£­ ļ£ø
. .
. . . .
ļ£­ ļ£ø . .
. . . .
ā’ct
xt
(t) (t) (t)
Ā· Ā· Ā· ntā’1 ā’1
n1 n2

It follows from Theorem C.38 on page 221 that, if det(A) = 0, then there is the
unique solution X = (m1 , . . . , mt ), so the secret m1 is recovered.

Example 8.5 Let p = 409, m1 = 96 and t = 3. If we randomly select m2 = 109
and m3 = 208, then m = (96, 109, 208). We select the following at random:
(1) (1) (2) (2) (3) (3)
n1 = 2; n2 = 51; n1 = 25; n2 = 111; n1 = 105; n2 = 308.

Ā© 2003 by CRC Press LLC
158 8. Key Management

Then the values in step (2) are:
(1) (1)
c1 ā” m3 ā’ n1 m1 ā’ n2 m2 ā” 208 ā’ 2 Ā· 96 ā’ 51 Ā· 109 ā” 183 (mod 409),
(2) (2)
c2 ā” m3 ā’ n1 m1 ā’ n2 m2 ā” 208 ā’ 25 Ā· 96 ā’ 111 Ā· 109 ā” 24 (mod 409),
(3) (3)
c3 ā” m3 ā’ n1 m1 ā’ n2 m2 ā” 208 ā’ 105 Ā· 96 ā’ 308 Ā· 109 ā” 319 (mod 409).
Thus, the hyperplanes distributed to the participants are:

ā” 183 + 2x1 + 51x2 (mod 409),
1

ā” 24 + 25x1 + 111x2 (mod 409),
2

ā” 319 + 105x1 + 308x2 (mod 409).
3

Plugging these values into (8.4),we get,

ļ£« ļ£¶ļ£« ļ£¶ļ£« ļ£¶
51 ā’1 ā’183
2 x1
AX = ļ£­ 25 111 ā’1 ļ£ø ļ£­ x2 ļ£ø = ļ£­ ā’24 ļ£ø = C.
308 ā’1 ā’319
105 x3

then solving for det(A) = 269, and using Cramerā™s rule, we get

(x1 , x2 , x3 ) = (ā’49023/269, 19505/269, 945936/269).

However, 269ā’1 ā” 260 (mod 409) and

ā’49023 Ā· 260 ā” 96; 19505 Ā· 260 ā” 109; 945936 Ā· 260 ā” 208,

all congruences modulo 409. Thus, (m1 , m2 , m3 ) = (96, 109, 208), and the secret
message m1 = 96 is retrieved. See Exercises 8.13ā“8.16.

It is not guaranteed that det(A) = 0 in (8.4), but if we choose p large
enough, then it is highly probable that A is indeed invertible. Shamirā™s method is
essentially a special case of the Blakely method since Shamirā™s method eļ¬ectively
deals with a Vandermonde matrix for A, the determinant of which is zero if
and only if some xk ā” xi (mod p), but we chose these values to be distinct in
step (3) of the algorithm, (see Exercise 8.17). This gives Shamirā™s method an
advantage over Blakelyā™s method. Moreover, Shamirā™s method clearly requires
each participant to have less information in their respective shares.
There are numerous other secret sharing schemes, and related topics not
covered herein. The interested reader may consult [17], [28], [50], [64], [108],
[129], [156], [198], [208], and [214]. The bottom line is that the motivation for
chapter unfolds.

Ā© 2003 by CRC Press LLC
8.1. Secret Sharing 159

Exercises

8.1. In Shamirā™s threshold scheme, prove: f (xk ) ā” mk (mod p) for 1 ā¤ k ā¤ t.
8.2. Prove that p(x) ā” f (x) (mod p) in the Shamir threshold scheme.
8.3. Given g(x) = 444x2 + 68x + 2856, with g(1) = 7, g(2) = 1407, and
g(3) = 334, which are the same values produced by f (x) in Example
8.2, where g(x) is taken modulo p = 3361. Explain why this does not
In Exercises 8.4ā“8.7, use the Shamir threshold scheme with (t, w) = (3, 5)
to recover the message m = p(0) with the given values of p(x) for x1 = 1,
x3 = 3, and x5 = 5 as done in Example 8.2 modulo the given prime p.
8.4. (p(x), p) = (561x2 + 273x + 111, 2707).
8.5. (p(x), p) = (225x2 + 56x + 207, 4231).
8.6. (p(x), p) = (714x2 + 541x + 147, 5417).
8.7. (p(x), p) = (69x2 + 19x + 999, 6991).
8.8. Show that in Example 8.3, if we choose r = 834265, then we cannot recover
the message with the Amuth-Bloom scheme. Why?
In Exercises 8.9ā“8.12, use the Asmuth-Bloom scheme with (t, w) = (3, 4)
to recover the message m with the given values of p, r, ai for i = 1, 2, 3.
8.9. (p, m, a1 , a2 , a3 , r) = (5039, 519, 5, 7, 7103, 10).
8.10. (p, m, a1 , a2 , a3 , r) = (6379, 679, 5, 706, 7001, 101).
8.11. (p, m, a1 , a2 , a3 , r) = (7103, 3071, 10, 11, 7001, 100).
8.12. (p, m, a1 , a2 , a3 , r) = (8179, 1703, 51, 91, 7156, 515).
In Exercises 8.13ā“8.16, use the Blakely secret sharing scheme with t = 3
with each of the given values to show how the secret message m1 can be
recovered using the same technique as in Example 8.5. In each of the
(1) (1) (2) (2) (3) (3)
following, we are given: (m1 , m2 , m3 , n1 , n2 , n1 , n2 , n1 , n2 , p).
8.13. (59, 409, 90, 15, 52, 11, 123, 308, 400, 503).
8.14. (77, 88, 99, 85, 95, 103, 204, 305, 406, 607).
8.15. (107, 1, 718, 297, 306, 419, 537, 698, 709, 719).
8.16. (333, 737, 900, 157, 206, 315, 473, 585, 696, 937).
t
8.17. Show that the modular equations mk ā” m + j=1 cj xj (mod p) in
k
Shamirā™s threshold scheme give rise to a matrix equation modulo p, where
the matrix having the values xj is the Vandermonde matrix whose deter-
k
minant is 0 modulo p exactly when some xk ā” xi (mod p) for k = i. (See
page 222.) (Hint: Use (C.37) on page 221.)

Ā© 2003 by CRC Press LLC
160 8. Key Management

8.2 Key Establishment
The management of a balance of power is a permanent undertaking, not an
exertion that has a foreseeable end.
Henry Kissinger (1923ā“) American politician

A Key establishment protocol is a protocol using cryptography to securely
establish a shared secret (symmetric) key. One would expect that public-key
cryptography would not need such a protocol since public enciphering keys are
stored in public databases. However, recall the discussion on page 75, wherein we
looked at the more practical use of a hybrid cryptosystem. The reason that they
are used in practice is that public-key methods are much slower than those using
symmetric keys. Thus, RSA, for example, could be used to transfer symmetric
keys, which could then be used for the bulk of the data communication.
Key establishment can manifest itself in two distinct ways. One is called
key distribution (also called key transfer, and key transport) where one entity
generates a symmetric key and sends it to other entities. For instance, Alice
could use Bobā™s public key to encipher the symmetric key (see page 128). The
second method for key establishment is key agreement which is a protocol where
entities act in concert by contributing to the generation of a symmetric key. For
example, the Diļ¬e-Hellman key-exchange protocol discussed on page 49 is such
a protocol. Note that the (less accurate) term key exchange is often used in the
literature since two entities perform an exchange of information, the result of
which is their agreement on a shared key. Key management here is crucial since,
in practice, adversaries will likely attack the key management scheme before
the cryptographic scheme. Thus, the ease of key management with public-
key cryptography may be seen as the primary advantage over symmetric-key
cryptography. For instance, in a network having a large number of users, such
as that described on page 73, public-key cryptography has a huge advantage in
key management.
One of the weaknesses of the aforementioned Diļ¬e-Hellman protocol is that
it is susceptible to the man-in-the-middle attack (see pages 27 and 127). One
solution to this weakness is the use of digital signatures (see Section 7.1). For
example, there is a variant of Diļ¬e-Hellman that employs entity authentication
and mutual explicit key authentication, all with entity anonymity guaranteed
against eavesdroppers. An instance of such an authenticated key agreement pro-
tocol (meaning that the key agreement protocol itself authenticates the partici-
pants identities) is given as follows as a variant of the Diļ¬e-Hellman exchange.
This is due to Diļ¬e, Van Oorschot, and Weiner [75], which evolved from earlier
work (see [73, p. 568]).
The following is considered to be a three-pass variant of the Diļ¬e-Hellman
protocol. Compare this with the discussion of Shamirā™s three-pass protocol
(embedded in steps (3)ā“(5) of the Massey-Omura cryptosystem on page 71),
which itself can be used as a key agreement scheme.

Ā© 2003 by CRC Press LLC
8.2. Key Establishment 161

x Station-to-Station Protocol (STS)8.2
Alice and Bob exchange three messages with the goal of authenticated agree-
ment on a symmetric key k.
Background Assumptions:
(a) Alice and Bob possess identiļ¬cation certiļ¬cates,

C(A) = (IA , verA , sigA (IA , verA )), C(B) = (IB , verB , sigB (IB , verB )),

respectively, where (sigA , verA ) and (sigB , verB ) are their respective sign-
ing and veriļ¬cation algorithms (see Section 7.1). Also, the signatures in
C(A) and C(B) are computed by Trent.
(b) Trent has a signature scheme including a public veriļ¬cation algorithm verT .

(c) There is a publicly known prime p and primitive root Ī± modulo p.
(d) E is a symmetric enciphering algorithm (for which a key k will be developed
below, and its use with the key denoted by Ek ).

Protocol Steps:
(1) Alice selects a random secret eA ā (Fp )ā— such that eA ā¤ pā’2 and computes
Ī±eA (mod p), which she sends to Bob.

(2) Bob chooses a random secret eB ā (Fp )ā— with eB ā¤ p ā’ 2, calculates

k ā” (Ī±eA )eB (mod p), and sB = sigB (Ī±eB , Ī±eA ),

then sends (C(B), Ī±eB (mod p), Ek (sB )) to Alice.
ā’1
(3) Alice computes k ā” (Ī±eB )eA (mod p), and uses Ek to decrypt and obtain
sB , which she veriļ¬es using verB , and she veriļ¬es C(B) using verT .

(4) Upon successful completion of step (3), Alice computes

sA = sigA (Ī±eA , Ī±eB ),

and sends (C(A), Ī±eA (mod p), Ek (sA )) to Bob.
ā’1
(5) Bob uses Ek to decipher and get sA which he veriļ¬es using verA , and uses
verT to verify C(A). (A successful completion of this step ensures Alice
and Bob have a shared key k.)

The STS protocol establishes a key k, mutually conļ¬rmed by Alice and Bob,
whose identities have been veriļ¬ed to each other, but not to Eve. Thus, we
indeed have an authenticated key agreement protocol. Now Alice and Bob can
use k to encrypt all subsequent messages between them.
8.2 Fora relatively new partial attack on STS, and means to defend against it, see:
http//:www.cacr.math.uwaterloo.ca/Ėajmeneze/publications/sts.ps

Ā© 2003 by CRC Press LLC
162 8. Key Management

Suppose that we want to dispense with the need for (explicit) certiļ¬cates,
such as C(A) and C(B). Then we need a means whereby Alice and Bob can im-
plicitly authenticate each otherā™s identity. This is accomplished in the following
scheme [97], developed by Girault in 1991, although he cites work established
by others as his motivation.
x Giraultā™s Self-Certifying Key Agreement Scheme
Alice and Bob exchange messages with a goal of implicitly certiļ¬ed agree-
ment on a public key k.
Setup Stage: Trent performs each of the following.

(1) Select primes p and q, form the RSA modulus n = pq, and choose an
element Ī± of maximum order in (Z/nZ)ā— (see Exercise 8.18). The value
of n is public, but its factorization known only to Trent. Also, the DLP
in Z/nZ must be intractable.
(2) Select an RSA public/private key pair (e, d).
(3) Create identity strings IA and IB for Alice and Bob, respectively.

Protocol Steps:
(4) Alice and Bob individually choose private exponents dA , and dB , com-
pute cA ā” Ī±dA (mod n), cB ā” Ī±dB (mod n), and send (cA , dA ), (cB , dB ),
respectively, to Trent.
(5) Trent veriļ¬es that cA ā” Ī±dA (mod n) and cB ā” Ī±dB (mod n), and if valid,
calculates

pA ā” (cA ā’ IA )d (mod n), pB ā” (cB ā’ IB )d (mod n),

sends pA to Alice, and pB to Bob.

(6) Alice randomly chooses eA ā (Z/nZ)ā— , computes sA ā” Ī±eA (mod n), and
sends (IA , pA , sA ) to Bob.

(7) Bob selects eB ā (Z/nZ)ā— at random, computes sB ā” Ī±eB (mod n), and
sends (IB , pB , sB ) to Alice.

(8) Alice computes
k ā” sdA (pe + IB )eA (mod n),
B
B

and Bob computes

k ā” sdB (pe + IA )eB (mod n).
A
A

(See Exercise 8.19.)

Ā© 2003 by CRC Press LLC
8.2. Key Establishment 163

Example 8.6 Suppose that p = 919, q = 839, so n = 771041 is the RSA modu-
lus for the Girault protocol. Trent also chooses (e, d) = (53, 420929) as the RSA
key pair, and Ī± = 77 as the element of maximum order 384642 = lcm(838, 918)
in (Z/nZ)ā— . The identiļ¬cation strings chosen by Trent are IA = 19 and IB = 39.
Alice selects dA = 5 and computes cA ā” Ī±dA ā” 430247 (mod n). Bob chooses
dB = 89 and computes cB ā” Ī±dB ā” 264373 (mod n). Then cA and cB are sent
to Trent. Trent computes both

pA ā” (cA ā’ IA )d ā” (430247 ā’ 19)420929 ā” 907 (mod n),

and
pB ā” (cB ā’ IB )d ā” (264373 ā’ 39)420929 ā” 682111 (mod n),
which are sent to Alice and Bob, respectively. Alice chooses eA = 15, computes

sA ā” Ī±eA ā” 7715 ā” 297843 (mod n),

and sends (IA , pA , sA ) = (19, 907, 297843) to Bob. Bob selects eB = 83, com-
putes
sB ā” Ī±eB ā” 7783 ā” 312102 (mod n),
and sends (IB , pB , sB ) = (39, 682111, 312102) to Alice. Alice computes,

k ā” sdA (pe + IB )eA ā” 3121025 (68211153 + 39)15 ā” 517619 (mod n),
B
B

and Bob computes,

k ā” sdB (pe + IA )eB ā” 29784389 (90753 + 19)83 ā” 517619 (mod n),
A
A

so they have agreed on k = 517619 (mod n) via implicit key authentication. (See
Exercises 8.21ā“8.24.)

In step (5) of the Girault scheme, Trentā™s calculation of pA and pB essen-
tially replaces the certiļ¬cates, since pA and pB are the self-certifying public keys,
given that, for instance, pe + IA ā” cA ā” Ī±eA (mod n), so from this information
A
anyone can verify Aliceā™s public key Ī±eA . However, since (IA , pA , sA ), for in-
stance, is not signed by Trent, then Mallory could forge this information. Yet,
if Mallory takes IA and produces a forgery sA , there is no way for him to com-
pute dA corresponding to sA , provided that the DLP is intractable in Z/nZ.
Hence, without dA , a key construction cannot be accomplished by Mallory who
is impersonating Alice. Thus, Trent cannot be duped by Mallory who must be
convinced that Alice knows dA . This is the reason that Alice must send dA to
Trent. He could quite easily compute pA from cA without knowing dA , but Alice
must convince him that she knows dA . Of course, there exist other means for
Alice to convince Trent of this knowledge without giving away dA . For instance,
see the discussion surrounding Schnorrā™s identiļ¬cation scheme at the bottom of
page 130. If Trent does not verify knowledge of dA in some fashion, however,
there can be dire consequences (see Exercise 8.20).

Ā© 2003 by CRC Press LLC
164 8. Key Management

There are numerous other key agreement protocols. The above are presented
as an introduction to the topic with illustrations suļ¬cient for us to carry on with
our investigations. The reader interested in more recent protocols may consult
[115], wherein the authors present an authenticated key agreement protocol
provably secure against the man-in-the-middle attack. Also see [208] and [234].
We now turn to another aspect of key management, namely, key distribution.
It may be argued that secure key distribution is the most diļ¬cult aspect of key
management. We have already seen a preliminary aspect of key distribution
when we discussed key predistribution on page 73. By key predistribution we will
mean a key agreement protocol where Trent acts as a key server who generates
and distributes enciphered session keys to a network of users. Here we will think
of a network as a system of computers that transfers data among the entities
called users. Thus any pair of users can decipher and use a shared key, unknown
to all other users except, of course, Trent.
If there are n users on a network using symmetric-key techniques, and there
is no key server, then there must be n(n ā’ 1)/2 centrally stored keys, or ap-
proximately n2 . This is called the n2 -key distribution problem. Of course, as n
gets very big, this becomes unacceptable. Hence, public-key techniques (or a
key server) are needed to solve the problem since, as we noted on page 73, only
n ā’ 1 keys are needed in that case.
We now discuss one of the best-known key predistribution schemes in what
follows. This was introduced in [31] as a simpliļ¬cation of Blomā™s original method
[29].
x Blomā™s (Simpliļ¬ed) Key Predistribution Scheme
The goal is for the key server to distribute a symmetric key to each user over
a secure channel.
Basic Assumptions: We suppose that there is a network of n ā N users,
and that keys are taken from Fp where p ā„ n is a public prime. Each user, such
as Alice, has a unique public key kA ā Fp .
Protocol Steps:

(1) Trent chooses three random values r1 , r2 , r3 ā Fp , not necessarily distinct,
and forms,
p(x, y) ā” r1 + r2 (x + y) + r3 xy (mod p).

(2) For each user, such as Bob, Trent computes,

fB (x) ā” r1 + r2 kB + (r2 + r3 kB )x (mod p),

which he sends to Bob over a secure channel.
(3) Now Alice and Bob may communicate over the network using the shared
symmetric key,

k ā” r1 + r2 (kA + kB ) + r3 kA kB (mod p),

Ā© 2003 by CRC Press LLC
8.2. Key Establishment 165

where Alice computes k via,

kA,B ā” fA (kB ) ā” r1 + r2 kA + (r2 + r3 kA )kB (mod p),

and Bob computes it via,

kB,A ā” fB (kA ) ā” r1 + r2 kB + (r2 + r3 kB )kA (mod p),

since k ā” kA,B ā” kB,A (mod p).

Example 8.7 Let p = 569, and n = 3, with Alice, Bob, and Cathy on the
network, where kA = 356, kB = 215, and kC = 501. Assume that Trent chooses
r1 = 5, r2 = 96, and r3 = 416, so p(x, y) ā” 5 + 96(x + y) + 416xy (mod p).
Then the individual polynomials sent to Alice, Bob, and Cathy are,

fA (x) ā” 41 + 252x; fB (x) ā” 161 + 203x; fC (x) ā” 305 + 258x.

the three session keys are,

kA,B ā” 166 (mod p); kA,C ā” 544 (mod p); kB,C ā” 13 (mod p),

for communications between Alice and Bob; Alice and Cathy, and Bob and
Cathy, respectively.

By Exercise 8.30, Blomā™s simpliļ¬ed scheme is unconditionally secure against
an attack by any individual user, but is vulnerable to a total break by more
than one user acting in concert (see Exercise 8.31). However, the scheme can
easily be made secure against any n ā N users acting in concert by altering the
choice by Trent in step (1) of the polynomial to be,
n n
p(x, y) ā” ri,j xi y j (mod p), (8.8)
i=0 j=0

for randomly chosen ri,j ā Fp with ri,j ā” rj,i (mod p) for all such i, j. The
general setup (8.8) is an aspect of the full Blom protocol.
On page 73, we made a brief reference of Kerberos, which is actually a key
predistribution/authentication scheme that we now discuss in detail.
The development of Kerberos began in 1989, and originated from a larger
endeavor at MIT, called Project Athena, the purpose of which was secure com-
munication across a public network for student access of their ļ¬les. Kerberos
is the authentication protocol aspect of Project Athena, and is based upon a
client-server-veriļ¬er model described as follows. First, a client, Carol, is a user
(which might in reality be dedicated software or a person) with some goal to
achieve, and this could be as simple as sending e-mail or as complex as installa-
tion of a system component. A server (and veriļ¬er), Victor, provides services
to clients. This might involve anything from e-commerce to allowing access to

Ā© 2003 by CRC Press LLC
166 8. Key Management

personal ļ¬les. In the Kerberos model, Trent is a trusted authority, called the
Kerberos authentication server. The property of producing a new session key
each time a pair of users wants to communicate is called key freshness.
x Kerberos Authentication/Session Key Distribution Protocol ā”
Simpliļ¬ed
Carol interacts with Trent and Victor with the goal of authenticating her
identity to Victor, and establishing a session key, k, which she can use to com-
municate with him.
Basic Assumptions: We are given a symmetric-key algorithm E (such as
AES ā” see page 22). Trent selects a random key k, a timestamp t, and a validity
period L, called a lifetime. Carol and Trent share a secret symmetric key kC,T ,
and Victor and Trent share one, kV,T . Also, IC , IV , and IT are identity strings
for Carol, Victor, and Trent, respectively.
Protocol Activities:
(1) Carol sends her request for a session key to use with Victor, together with
her identity string IC to Trent.
(2) Trent computes mC = EkC,T (k, IV , t, L) where IV is Victorā™s identity
string that he has taken from a database. He also computes mV =
EkV,T (k, IC , t, L), called a ticket for Victor, and sends both mC and mV
to Carol.
ā’1
(3) Carol uses EkC,T to retrieve k, IV , t, and L from mC . She veriļ¬es that t
and L are valid, and that IV is the identity of Victor. She then creates a
fresh timestamp tC , computes

mV = Ek (IC , tC ),

called the authenticator, which she sends to Victor along with mV that
ā’1 ā’1
(4) Victor uses EkV,T to get k from the ticket, mV . Then he uses Ek to decrypt
the authenticator mV . He checks that the two copies of IC from the
ticket and authenticator match. He checks that tC is within the expiration
window, which can be accomplished by Victor subtracting tC from the
current time which must be within some mutually accepted ļ¬xed time
interval. Then he checks that his current time is within the lifetime L
speciļ¬ed by the ticket. If these three facts hold, he declares Carol to be
authentic, and he computes mC = Ek (tC ), and sends it to her.
ā’1
(5) Carol applies Ek to mC , and checks that tC matches the value in mC
from step (3). If it does, she declares Victor to be authentic and now has
a session key k to communicate with him.

The role of the timestamp t and the lifetime L is to thwart Mallory from
storing old messages for retransmission at a later time (a replay attack ā” see

Ā© 2003 by CRC Press LLC
8.2. Key Establishment 167

page 133). If any of the checks against t in the above protocol fail, then the
protocol terminates since a stale timestamp has been discovered. Checks that
are valid are those that show the current time to be in the range t to t + L.
The lifetime L also has the advantage of allowing Carol to re-use Victorā™s ticket
without contacting Trent, so steps (1)ā“(2) can be eliminated over the lifetime
of the ticket. However, each time Carol reuses the ticket, she must create a new
authenticator with a fresh timestamp, but the same session key k.
The expiration window can be any agreed ļ¬xed amount that takes into
consideration such things as clock skew, message transit time, and processing
time. This could be measured in seconds or milliseconds, depending on the
situation. However, the clocks have to be āroughly synchronizedā for all users
in the network, and they must be secured to prevent modiļ¬cations. We say
roughly synchronized since perfect synchronization is a tremendously diļ¬cult
task. This is one of the drawbacks of Kerberos, since the current time is used
to determine the validity of the session key k. There are solutions that involve
synchronized distributed clocks using network protocols, which themselves must
be secure.
Going back in time, the basic protocol for Kerberos comes from the following
key predistribution protocol introduced in [173] where timestamps are not used.
These were later proposed by Denning and Sacco [69].
x Needham-Schroeder Key Predistribution Scheme
Alice and Bob communicate with Trent for the purpose of mutual identity
and shared key authentication.
Basic Assumptions: E is a symmetric-key algorithm and nA , nB are
nonces (see page 133) chosen by Alice and Bob, respectively. Trent selects a
session key k for Alice and Bob to share.
Setup Stage: Alice and Trent use a shared symmetric key kA,T , and Bob
and Trent use a shared symmetric key kB,T . Also, IA and IB are identity strings
for Alice and Bob, respectively.
Protocol Steps:
(1) Alice sends (IA , nA ) to Trent.

(2) Trent sends EkA,T (nA , IB , k, EkB,T (k, IA )) to Alice.
ā’1
(3) Alice uses EkA,T to decrypt k and conļ¬rms that nA is the same as in step
(1), and veriļ¬es IB . Then she sends EkB,T (k, IA ) to Bob.

(4) Bob deciphers k and sends Ek (nB ) to Alice.
ā’1
(5) Alice decrypts with Ek , generates nB ā’ 1 and sends Ek (nB ā’ 1) to Bob.
ā’1
(6) Bob deciphers with Ek and veriļ¬es nB ā’ 1.

The above protocol diļ¬ers from Kerberos in that it has no lifetime parameter
L or timestamp t, but rather uses nonces. However, step (3) is essentially the

Ā© 2003 by CRC Press LLC
168 8. Key Management

same as the ticket in the Kerberos protocol, but with Needham-Schroeder, the
ticket is double-encrypted in Step (2). Yet, Bob has no means of verifying the
freshness of k. Thus, Mallory can resend the message in step (3), which Bob
receives in step (4) and sends the message to Alice, which Mallory intercepts. If
Mallory can get access to k, he can send the message in step (5), impersonating
Alice, and Bob veriļ¬es as in step (6) that it is Alice, when in fact he is now
dealing with Mallory.
Needham and Schroeder addressed this problem in [174], which is the same
as the Otway-Rees protocol [179]. The above is presented largely for historical
reasons since it is not secure. However, they also have a public-key protocol
that results in authentication and key agreement on a distributed symmetric
key. This was also introduced in [173]. However, almost twenty years after its
publication, Lowe [144] discovered an attack that compromises authenticity of
the messages. Thus, we present the modiļ¬cation made by Lowe to address this
weakness.
x Needham-Schroeder (Modiļ¬ed) Public-Key Scheme
Alice and Bob communicate with the goal of mutual identity and key au-
thentication as well as agreement on a symmetric key.
Background Assumptions: P is a public-key encryption algorithm (such
as RSA) and PA (m1 , m2 ), for instance, will denote the use of Aliceā™s public key
to send messages m1 , m2 . Also, kA , kB are Alice and Bobā™s respective chosen
symmetric session keys. Moreover, Alice and Bob are assured of having each
otherā™s authentic public key. The strings IA and IB identify Alice and Bob.
Protocol Steps:
(1) Alice sends Bob PB (kA , IA ).
(2) Bob decrypts with his private key, and veriļ¬es Aliceā™s identity IA . If valid,
he sends PA (kA , kB , IB ) to Alice.
(3) Alice uses her private key to decipher and checks that the copy of kA agrees
with what she sent in step (1). Also, she veriļ¬es Bobā™s identity IB . If these
are valid, she sends PB (kB ) to Bob.
(4) Bob uses his private key to decrypt and veriļ¬es that the copy of kB agrees
with what he sent in step (2). If all is valid, then they can use a one-
way function f to compute f (kA , kB ), which they may use as a mutually
agreed and authenticated session key for them to communicate.

The diļ¬erence between the above (modiļ¬ed) protocol and that exhibited
by Needham and Schroeder in 1978, is that Lowe added Bobā™s identiļ¬cation
string IB in step (2). Without this, Alice could unknowingly initiate a run with
Mallory who receives PM (kA , IA ), which he decrypts using his private key. If
he sends PB (kA , IA ) to Bob, then Bob veriļ¬es Aliceā™s identity IA , not knowing
that he is communicating with Mallory. Bob then sends PA (kA , kB ) to Alice,
which Mallory allows. She has only to verify that kA is as she sent it in step

Ā© 2003 by CRC Press LLC
8.2. Key Establishment 169

(1), and it is, so she sends PM (kB ), which Mallory intercepts, and decrypts. He
then sends PB (kB ) to Bob. Bob veriļ¬es and establishes the session key. Hence,
Mallory can successfully negotiate a man-in-the-middle attack without Alice or
Bob knowing they have been duped. The addition of Bobā™s identity string in
step (2) thwarts Mallory in this attack since Bob, by sending PA (kA , kB , IB ) is
essentially issuing a challenge, namely, extract kB from the latter and return
PB (kB ) to Bob. Only Alice can meet this challenge since she has kept her
private key secure. If Bob receives PB (kB ), he knows that only Alice could have
received and transformed it. If Mallory tries his little trick above, Alice will
immediately know it since she will see that IB does not correspond to IM , and
Mallory is foiled.
The aforementioned attack on the Needham-Schroeder scheme escaped de-
tection for nearly two decades before Loweā™s ļ¬x. This demonstrates that due
diligence is necessary. Any protocol must be free from oļ¬ering unwanted open-
ings for an attacker. For instance, in the original protocol above, Alice unwit-
tingly oļ¬ers Mallory the opportunity to decipher PM (kA ) from which he can
learn kA . The Lowe ļ¬x allows Alice to check IB against IM at which point she
knows that IB did not come from Mallory and she can stop the protocol on the
spot. Also, a protocol must be provably correct in the sense that there is some
authentication test method that it must pass. Work in this direction is being
done, for instance, by J. Guttman (see [106]).
Other than the Diļ¬e-Hellman protocol, we have also seen other key agree-
ment schemes based on asymmetric techniques. For example, the ElGamal
cryptosystem discussed on page 67 contains the essence of the ElGamal key-
agreement protocol (called ElGamal Key Generation on page 67). Once Bob
has generated his public key (p, Ī±, Ī±a ), Alice may obtain a copy of it. She then
chooses a random natural number n ā¤ pā’1 and sends Ī±n (mod p) to Bob. Then
the shared key is k ā” Ī±ax (mod p), computed by Alice as k ā” (Ī±a )x (mod p),
and by Bob as k ā” (Ī±x )a (mod p). This protocol is sometimes called the one-
pass ElGamal key agreement protocol, which neither authenticates the identity
of individual entities nor guarantees key conļ¬rmation (meaning the assurance
both that the key is fresh and the entity with the public key is also in possession
of the corresponding private key). One way of ensuring this is through the use
of public-key certiļ¬cates, about which we will learn in Section 8.3.
We conclude this section with an example of a hybrid key agreement and
authentication protocol. This was introduced [22] in 1992. We will describe it
with the Diļ¬e-Hellman implementation, although RSA or ElGamal could also
be used, for instance. The Diļ¬e-Hellman implementation is one of the simplest.
x Encrypted Key Exchange (EKE) ā” Diļ¬e-Hellman Implemented
Alice and Bob share a common password k (a secret data item used to
authenticate an entity, also called passcode, and when expanded into a longer
phrase passphrase) and E, a symmetric-key algorithm. This protocol establishes
both identity authentication and a shared key.
Background Assumptions: From the Diļ¬e-Hellman protocol on page 49,
we have a ļ¬xed prime p and generator Ī± of Fā— publicly known for all users in
p

Ā© 2003 by CRC Press LLC
170 8. Key Management

the network employing this protocol. The string IA identiļ¬es Alice.
Protocol Steps:
(1) (Initialization) Alice randomly selects a number RA ā (Z/pZ)ā— , computes
Ī±RA (mod p), and sends (IA , Ī±RA (mod p)) to Bob.
(2) (Challenge) Bob chooses a random RB ā (Z/pZ)ā— and calculates

K ā” (Ī±RA )RB (mod p).

Then he generates a random string RB , computes

Ek (Ī±RB (mod p), EK (RB )),

and sends it to Alice.
(3) (Response/Challenge) Alice uses Ek to decipher Ī±RB (mod p). Then she
computes K ā” (Ī±RB )RA (mod p), and uses EK to decrypt RB . She then
generates a random string RA , computes EK (RA , RB ), and sends it to
Bob.
(4) (Veriļ¬cation/Response) Bob decrypts RA , RB using EK , and checks that
RB is the same as that sent in step (2). If so, he sends EK (RA ) to Alice.
(5) (Veriļ¬cation) Alice uses EK to decipher, and if RA is the same as the value
she sent in step (3), the protocol is complete.

The challenge-response portion of the protocol in steps (2)ā“(4) is designed to
convince Bob that Alice has knowledge of K, while the portion in steps (3)ā“(5)
are designed to convince Alice that Bob knows K. The reader may go to the
Kerberos protocol and verify that steps (2)ā“(5) of that protocol serve the same
function for Carol and Victor with the timestamp playing the role of K.
One of the strengths of EKE is against password-guessing attacks, since
knowledge of EK (RB ) does not allow for easy checking of guesses for k. Each
choice for k yields a candidate value for Ī±RB , which in turn yields a candidate
value for K. But RB was randomly chosen so there is no method for verifying
if this guess is correct. Moreover, a passive attacker such as Eve, even with
knowledge of k, will still have to solve the DHP in order to determine K. The
reason is that she will know Ī±RA (mod p) and Ek (Ī±RB (mod p), EK (RB )), so
she has Ī±, Ī±RA (mod p), and Ī±RB (mod p), but not RA or RB . Thus, this
hybrid protocol, EKE, draws on the strengths of both symmetric and public-key
cryptography by working in concert to strengthen both of them. The inventors
of EKE, Bellovin and Merritt have a patent on their protocol [23].
With all the above being said, EKE still relies on a shared secret, so if a
password is somehow captured, it can be used for impersonation. Since the
inception of EKE, authentication protocols have proliferated. In 1996, for ex-
ample, Jablon [113] developed the Simple Password Exponential Key Exchange
(SPEKETM ), (pronounced āspeakā) which is an improvement on EKE. (He did

Ā© 2003 by CRC Press LLC
8.2. Key Establishment 171

so as the founder of Integrity Sciences, now part of Phoenix Technologies, where
he is currently CTO of the Platform Security Division.) The SPEKE protocol
has two stages. It ļ¬rst uses a variant of the Diļ¬e-Hellman key exchange protocol
to establish a shared key K. The second stage is a zero-knowledge challenge-
response protocol for Alice and Bob to mutually authenticate their respective
knowledge of K. As with EKE, the end result is mutual identity authentication
and shared key agreement. Both EKE and SPEKE allow use of a small pass-
word to provide authentication and key agreement over an unsecured channel.
Moreover, it is immune to oļ¬„ine dictionary attacks (for example, such attacks
might involve an adversary using a list of probable passwords, hashing the list,
and comparing them with the list of encrypted passwords in an attempt to ļ¬nd
a match). SPEKE has a number of applications from cell phones to smart cards
(see http://www.IntegritySciences.com/uses.html).
in which an adversary listens to data traļ¬c that includes secret passwords in or-
der to capture them for use at a later time. Thus, eavesdropping on a TCP/IP8.3
network can be easily accomplished against protocols that transmit passwords
in the clear. Moreover, password protocols require the passwords to be stored on
the host, usually hashed, and if revealed would compromise security. To address
these concerns, a new protocol was developed at Stanford University in 1997,
called Secure Remote Protocol (SRP), which diļ¬ers from EKE, SPEKE in that
a server, SRP mandates that the server store a salt value and a veriļ¬er. Hence,
without password storage, SRP is more secure than password schemes, and it
performs a secure key exchange in the authentication process.
SRP solves the long-standing problem of having both ease-of-use and secu-
rity. It relies on a type of Diļ¬e-Hellman exchange. However, authentication to
a server is rarely done. Also, it has the additional advantage of forward secrecy,
which is the property that the loss of a veriļ¬cation secret does not compromise
earlier encrypted sessions. SRP is freely available to residents of North America
in the form of SRP-enabled Telnet8.4 and FTP8.5 software ā” see:
8.3 This is the acronym for the protocols packaged in a network protocol stack for Internet
protocols. By a network protocol stack we mean a software package that supports network-
ing functions for operations software. IP is the acronym for Internet protocol, which is the
protocol that transports speciļ¬c bundles between hosts ā” those individual computer systems
on a network that communicate with other such systems. The Internet itself is the globally
interconnected network using the set of Internet protocols.
8.4 This is the Internet protocol that supports remote connections between computers.
8.5 This is the acronym for of File Transfer Protocol, the protocol used on the Internet for

sending ļ¬les, which are either uploaded from an individual computer to the FTP server,
or downloaded from the FTP server to an individual computer. Thus, FTP is a two-way
protocol. This is distinct from Hyper Text Transfer Protocol, or HTTP, which is a protocol
used to transfer ļ¬les from an Internet server onto a browser in order to view a page that
is on the Internet. HTTP is a one-way system ā” the contents of a page from the server
are downloaded onto the computerā™s browser for viewing, but ļ¬les are not transferred to the
computerā™s memory.

Ā© 2003 by CRC Press LLC
172 8. Key Management

Exercises

8.18. Prove that if n = pq is an RSA modulus, then the maximum order of an
element in (Z/nZ)ā— is lcm(p ā’ 1, q ā’ 1).

8.19. Prove that the two values in step (8) of the Girault scheme are actually
congruent modulo n.
ā° 8.20. In the Girault scheme, suppose that Trent does not verify that Alice knows
dA . Show how Mallory can successfully launch a man-in-the-middle attack
that dupes Bob into thinking he is communicating with Alice when, in fact,
he is communicating with Mallory.
In Exercises 8.21ā“8.24, use the Girault scheme to ļ¬nd the shared self-
certiļ¬ed key k, where the following values correspond to the variables:
(e, d, p, q, Ī±, IA , IB , dA , dB , eA , eB ).

8.21. (5, 9701, 173, 283, 3, 21, 93, 10279, 32773, 151, 37).
8.22. (23, 39239, 317, 409, 21, 517, 944, 13, 2131, 109093, 51547).

8.23. (131, 290315, 499, 593, 7, 156, 1001, 2021, 3011, 14033, 221675).
8.24. (311, 11387, 599, 659, 7, 133, 399, 1123, 1103, 233007, 323563).
In Exercises 8.25ā“8.29, use the Blom key predistribution scheme with n =
3 to ļ¬nd the shared keys kA,B , kA,C , kB,C as in Example 8.7, given the
values for (p, kA , kB , kC , r1 , r2 , r3 ), as follows.

8.25. (601, 10, 101, 568, 11, 13, 200).
8.26. (701, 12, 113, 686, 121, 311, 203).
8.27. (809, 666, 66, 6, 5, 15, 25).
8.28. (907, 270, 307, 47, 12, 13, 800).

8.29. (1009, 12, 901, 108, 5, 808, 700).
ā° 8.30. Prove that the simpliļ¬ed Blom scheme is unconditionally secure against an
attack by a user, Mallory. In other words, show that with the knowledge
Mallory has, namely, fM (x) ā” r1 + r2 kM + (r2 + r3 kM )x (mod p) sent by
Trent, all values of k ā Fp are possible for kA,B , which he is trying to
cryptanalyze.
8.31. Show that if Mallory conspires with another user, Eve, in the simpliļ¬ed
Blom scheme, then they can determine r1 , r2 , r3 , thereby allowing them
to determine any key, resulting in a total break.

Ā© 2003 by CRC Press LLC
8.3. Public-Key Infrastructure 173

8.3 Public-Key Infrastructure (PKI)
If a man will begin with certainties, he shall end in doubts; but if he will be
content to begin with doubts, he shall end in certainties.
Francis Bacon (1561ā“1626)
English lawyer, courtier, philosopher, and essayist

A public-key infrastructure, or PKI, embodies a foundation of protocols and
standards, which support and enable the secure and transparent use of public-
key cryptography, particularly in applications requiring the use of public-key
cryptography. Since the term PKI is quite a recent phenomenon, the reader
may not ļ¬nd uniformity of deļ¬nition throughout the literature, and therefore
no āsingleā PKI (see [2] for a book dedicated to the task of explaining PKI and
its various services). The core PKI services are authentication, integrity, and
conļ¬dentiality. We have already devoted the entirety of Chapter 7 to authen-
tication, which includes some integrity establishment techniques such as digital
signatures, and the integrity of digital cash (see Section 7.3). We have also
addressed conļ¬dentiality in Sections 8.1ā“8.2. A central view of PKI is that it
provides protocols for certiļ¬cation of public keys and veriļ¬cation of certiļ¬cates.
The reason is that if the core services are to be provided, then Alice must be
assured of being able to associate a public key clearly and veriļ¬ably to Bob,
with whom she wants to communicate. This is where the role of a certiļ¬cate
comes into play, and this will be our focus. We were introduced to certiļ¬cates
(with Trent as a certiļ¬cation authority) on page 129. We now expand this dis-
cussion with a view of PKI as providing key management through the use of a
certiļ¬cation authority (CA) and a registration authority (RA).
The CA is an entity responsible for issuing public-key certiļ¬cates (PKC)
(which are tamperproof data blocks containing, at a minimum, entity identiļ¬-
cation, CA identiļ¬er, and a public key), which are used to bind the individual
name to the corresponding public key. The CA accomplishes this by aļ¬xing
its private key as a digital signature, thereby performing key registration via
the issuing of a certiļ¬cate. Think of the certiļ¬cate as being the analogue of a
The RA typically plays the role of assisting the CA by establishing and ver-
ifying the identity of entities who wish to register on a network, for instance.
These entities are typically called end-users. Other functions of the RA may
include key predistribution for later online veriļ¬cation; initiation of the certiļ¬-
cation process with the CA for end-users; and performance of certiļ¬cate man-
agement functions such as certiļ¬cate revocation (meaning the cancellation of a
previously issued certiļ¬cate). Hence, we may come to an agreement as to the
probable services of a given PKI: certiļ¬cate creation, distribution, management,
and revocation. There are also PKI-enabled services that are not part of the
PKI, but can be built upon the core PKI. These include secure communications;
secure timestamping; and non-repudiation. Note that a PKI, in itself, may not
involve any cryptographic operations with the keys that it is managing. A com-
mon feature of all PKIs is a set of certiļ¬cation and validation protocols, since

Ā© 2003 by CRC Press LLC
174 8. Key Management

the fundamental core predicate of PKI is the secure management of public keys.
At the end of Chapter 7, when we were discussing issues surrounding e-
commerce, we mentioned SET, the Secure Electronic Transaction speciļ¬cation
established by Visa and Master Card to support credit card payments over the
Internet. Basically SET has adopted the ISO/ITU-T X.509 Version 3 public-key
certiļ¬cate format.8.6 SET was created to ensure the authenticity, conļ¬dentiality,
and integrity of e-commerce transactions over the World Wide Web (WWW).8.7
The X.509 Version 3 certiļ¬cate is sophisticated enough that it can handle e-
commerce applications as an international standard.
There exist other network and security protocols that use a proļ¬le of X.509
Version 3 certiļ¬cates such as Internet Protocol Security (IPSec). There are some
that are proprietary, such as Pretty Good Privacy (PGP) introduced by Zim-
merman [247] in 1995. PGP does not have the sophistication, nor was it meant
to have, as that enjoyed by the SET certiļ¬cate. It is essentially a method for
encrypting and digitally signing e-mail messages and ļ¬les. There is an improved
version, called Open PGP, as an IETF8.8 standards-track speciļ¬cation. Version
6.5 of Open PGP actually supports X.509 certiļ¬cates, but the trust8.9 model
diļ¬erences between PGP certiļ¬cates and X.509 Version 3 PKCs are enormous,
so it is unlikely that PGP will ever be used for e-commerce.
In PKIs, the trust models are used to describe the relationships of CAs with
8.6 The International Organization for Standardization (ISO) is a global federation of na-
tional standards bodies, one from each of 140 countries. This non-governmental organization
was initiated in 1947 to promote the development of standardization and related activities.
Note that ISO is not an acronym, but rather it is taken from the Greek isos meaning equal
and this is the preļ¬x iso- such as in isometric. So equal devolved to standard, and the ISO
name was adopted. Note that it has the feature of not requiring translation in each country,
as would an acronym. ISO develops precise criteria for such applications as the formatting
of smart cards, for instance. ITU is the International Telecommunication Union, which was
established on May 17, 1865 (as the International Telegraph Union) to manage the ļ¬rst inter-
national telegraph networks. The name change came in 1906 to properly reļ¬‚ect the new scope
of the Unionā™s mandate. The ITU-T is the ITU Telecommunication Standardization Section,
one of three sections of ITU. It was established on March 1, 1993. In conjunction ISO and
ITU-T form world standards such as the X.509, which is a public-key certiļ¬cate. Version 3 (as
speciļ¬ed in [112]) was developed to correct deļ¬ciencies in earlier versions. This version has
become the accepted standard so that often the term certiļ¬cate is used to mean this version
of X.509. Version 3 contains each of the following ļ¬elds: version number, certiļ¬cate serial
number, signature algorithm identiļ¬er, issuer name, validity period, entity name, entity pub-
lic key information, issuer unique identiļ¬er, entity unique identiļ¬er, extensions, and signature.
In addition, the extensions ļ¬eld can contain numerous types such as authority key identiļ¬er,
extended key usage, and private key usage period. There are other widely known joint stan-
dards such as ISO/IEC, which are joint between ISO and the International Electrotechnical
Commission (IEC). For example, [112] is tantamount to ISO/IEC 9594-8, 1997.
8.7 This is the information network using HTTP (see Footnote 8.5) and HTML on Internet

host computers. HTML means HyperText Markup Language, which is the text format used
for World Wide Web pages.
8.8 This is the Internet Engineering Task Force, which is responsible for making recommenda-

tions concerning the progress of so-called āstandard-trackā speciļ¬cations from a status called
Proposed Standard (PS) to a stage called Draft Standard (DS) to the ļ¬nal stage called Stan-
dard (STD). The citation [10] is called a Request for Comments (RFC), which are essentially
working documents of the Internet R&D community.
8.9 We take the deļ¬nition of ātrustā to be that used in [2], which is from [112, Section 3.3.23]:

Entity A trusts entity B when A assumes that B will behave exactly as A expects.

Ā© 2003 by CRC Press LLC
8.3. Public-Key Infrastructure 175

end-users and others. We describe only two of them, the one used by PGP and
the one used by X.509 Version 3. The ļ¬rst, used by PGP is called User-Centric
Trust. In this model, each user makes the decision as to which certiļ¬cates to
accept and which to reject. In the PGP implementation, a user, such as Alice,
exchanges certiļ¬cates which are public keys of those other users with whom she
wants to communicate. She protects her certiļ¬cate from alteration by signing it
with her private key. Alice acts as a CA in the following fashion. Upon receipt
of, say, Bobā™s certiļ¬cate, she will assign it one of three levels: (1) complete trust,
meaning that she trusts Bob and anyone whose certiļ¬cate is signed with Bobā™s
key; (2) partial trust, meaning that Alice does not completely trust Bob, so
certiļ¬cates signed by Bob must also be signed by other users (whom she does
trust) before she accepts it; (3) no trust, meaning that Alice does not trust Bob
and will not trust any certiļ¬cate signed by Bob. In some implementations, there
is a fourth level of uncertain, but this essentially amounts to no trust. In this
fashion she builds a web of trust with other users. However, this user-centric
model is not acceptable for such applications as e-commerce. Nevertheless, it is
popular for sending secure e-mail, but for most people it is diļ¬cult to manage
securely. A more generally secure trust model is described in what follows.
In the PKI trust model called cross-certiļ¬cation, ļ¬rst the CAs (in their re-
spective security domains8.10 ) are required to form a trust path between them-
selves. The process called mutual cross-certiļ¬cation involves CA1 signing the
certiļ¬cate of CA2 , and CA2 signing the certiļ¬cate of CA1 (see [1]). If the do-
mains are diļ¬erent, called interdomain cross-certiļ¬cation, then relying parties
(those entities who verify the authenticity of an end-userā™s certiļ¬cate) are able
to trust end-users in the other domain. This trust model is clearly suited to
e-commerce, such as that engaged by two distinct business organizations. If the
two CAs are part of the same domain, called intradomain cross-certiļ¬cation,
then this model can be varied to accommodate a hierarchy of CAs where CA1
can sign the certiļ¬cate of CA2 who is at a lower level, without having CA2 sign
CA1 ā™s certiļ¬cate. This is called unilateral cross-certiļ¬cation. An advantage of
unilateral cross-certiļ¬cation is that it allows relying parties to trust only the
top-level root CA, but have their certiļ¬cates issued by the authority closest to
them.
Clearly, the trust model is a vital part of any PKI. We have described only
two of many such models, which is suļ¬cient for our purposes. The reader
interested in seeing more of them in greater detail may consult, for instance, [2],
[49], or [156].
We have not addressed the PKI issue of certiļ¬cate storage. After the gener-
ation of a certiļ¬cate, it must be stored for use at a later time. It is not desirable
to have the end-users store them on their individual computers, so CAs require
what is called a public certiļ¬cate directory, which is a public database or server
accessible for read-access by end-users. The CA manages the directory and sup-
plies certiļ¬cates to it. The directory is a central storage location that provides
an individual, public, central location for the administration and distribution of
8.10 A security domain is a system governed by a trusted authority.

Ā© 2003 by CRC Press LLC
176 8. Key Management

certiļ¬cates. As with PKI itself, there is no single standard. Perhaps the most
popular is the X.500 series, which is the ISO/ITU-T array of standards with
speciļ¬cations in [111], which is equivalent to ISO/IEC 9594-1 (see Footnote 8.6).
In fact, the X.500 series is the underlying structure in which X.509 was origi-
nated. Proprietary directories based on X.500 include Microsoft Exchange, for
instance. An additional beneļ¬t of X.500 is that there are standardized protocols
for obtaining the data structures, thus allowing any PKI to have access. The
reason is that X.500 has a standardization mechanism called a schema for the
storage of certiļ¬cates and certiļ¬cate revocation list (CRL)8.11 data structures in
a given entityā™s directory entry. We will now look at certiļ¬cate revocation.
Suppose that Aliceā™s private key has been compromised. Thus, the corre-
sponding public key can no longer be used for Alice. The mechanism for alerting
the rest of the network of users is certiļ¬cate revocation checking. We can now
invoke the earlier analogy in terms of a driverā™s license. A police oļ¬cer, upon
checking a driverā™s license, not only veriļ¬es the date on the license, but also calls
some central police authority to conļ¬rm that the license has not be revoked.
Certiļ¬cate revocation refers to the act of marking the certiļ¬cate as revoked by
the CA and placing it in a CRL. CAs issue periodic CRLs to ensure relying par-
ties that the most recent CRL is current, so even if there are no changes, a CRL
is issued on time according to the schedule. In addition, as we have seen, some
certiļ¬cates are cross-certiļ¬ed between the CAs themselves. To revoke these cer-
tiļ¬cates, we need a separate authority revocation list (ARL), which plays the
role of CRLs. However, revoking the PKC of a CA is rare and usually occurs
when the CAs private key is compromised.
The X.509 Version 2 standard for CRLs, as with the Version 3 certiļ¬cates,
discussed earlier, has extension ļ¬elds to make the CAā™s job of revocation easier.
They are (1) reason code, namely, a speciļ¬cation of the reason for the revoca-
tion; (2) hold instruction code, which is a mechanism to temporarily suspend a
certiļ¬cate, and contains an object identiļ¬er (OID), which stipulates the action
to be taken if this ļ¬eld is ļ¬lled; (3) certiļ¬cate issuers, which has the identity
of the certiļ¬cate issuer; (4) invalidity date, which contains the date and time of
the known or suspected compromise.
There is an alternative online mechanism for certiļ¬cate revocation, the most
popular being the Online Certiļ¬cate Status Protocol (OCSP), documented in
[170] with HTTP being the most common practical mechanism (see Footnote
8.5). This is a challenge-response protocol oļ¬ering a mechanism for online re-
vocation of data from a trusted authority, called an OCSP responder. However,
as a mere protocol, it does not have the capacity to store revocation data, so
the OCSP responder must obtain information from some other source. Thus,
latency is involved with its use. Moreover, it is limited to the supplying of in-
formation about the revocation status of a given list of certiļ¬cates, and nothing
else. Hence, there is still the need for CRLs.
The next aspect of PKI that we will discuss is the key backup and recovery
8.11 This CRL is a signed data structure embodying a timestamped inventory of revoked
certiļ¬cates.

Ā© 2003 by CRC Press LLC
8.3. Public-Key Infrastructure 177

server. This gives the CA a mechanism for backing up private keys together
with a means of recovering them later should end-users lose their private keys.
In the literature, the term ākey recoveryā is often used synonymously with ākey
escrowā. However, the latter is quite diļ¬erent from the former in that key
escrow requires that keys are released to a third-party organization, such as a
police agency, as evidence in an investigation. On the other hand, key recovery
is implemented in an individual PKI by its authorities to provide key recovery
for its end-users. The key recovery server is an automated process to relieve the
burden on PKI authorities (see [1]). To prevent an adversary from accessing an
entityā™s private key and launching an impersonation attack, a CA may support
not one, but two key pairs: one for enciphering and deciphering and the other
for signature and veriļ¬cation. For instance, in the DSA, discussed on page
139, the key pair cannot be used for encryption and decryption, whereas the
Diļ¬e-Hellman key pair, discussed on page 49, cannot be use for signing and
veriļ¬cation. The management of key pairs is paramount in any PKI, and dual
key pairs has become a central feature of any in-depth PKI.
First, keys must be generated. This can occur at the end-userā™s computer,
then conveyed securely to the CA or RA. This necessitates the user having
software to generate cryptographic keys and securely send them to a central
authority. Alternatively, a CA or RA can generate the key pair. The mechanism
for so doing may vary. For instance, the ANSI X9.17 standard delineates a
Once multiple key pairs for individual entities have been generated, there
is a need for multiple certiļ¬cates, since X.509, for example, does not support
multiple key pairs in a single certiļ¬cate. A private key used for signing and
veriļ¬cation requires secure storage throughout its lifetime. In this case, we
should not back up the key pair, since the compromise of the pair necessitates
the generation of a new key pair. Moreover, compromise of the key pair makes
veriļ¬cation of all signatures associated with that key pair impossible. Such key
pairs must always be secured, usually in one module as mandated by [6], since
knowledge of the private key needed for non-repudiation will allow the owner of
the key to claim the adversary engaged in the non-repudiable act. This defeats
the whole point of having the key pair for non-repudiation. Furthermore, once
this key pair expires, it should be destroyed within the same module in which
it was secured, again as required in [6]. On the other hand, a private key
used for decryption must be backed up to enable recovery of enciphered data.
Moreover, it should not be destroyed once expired since it may be needed for
later decryptions. It should be placed in a key archive, which is a long-term
storage of keying data including certiļ¬cates. Typically, archives are appended
with timestamp and notarization data in order to resolve any future disputes,
as well as for audit purposes.
Another aspect of PKI is the updating of keys. Key pairs must be updated at
regular intervals, if for no other reason than to thwart compromise threatened
by cryptanalytic attacks. Once the key pair expires, the CA can reissue a new
certiļ¬cate based on the new key pair, or a new certiļ¬cate for the old key pair can
be generated. This gives rise what is called a key history, consisting principally

Ā© 2003 by CRC Press LLC
178 8. Key Management

of old private keys. A key history must be maintained by the PKI for such
purposes as later decryptions of old data. Ideally, a key history is stored with a
CA who has an automated process available to retrieve the data from the key
history as it is needed. This is diļ¬erent from key archiving which meets the
need for storing public keys and certiļ¬cates for digital signature purposes.
To leave the end-user with the task of requesting updates is usually an un-
acceptable burden, so the process in any comprehensive PKI will be automatic.
This can be done by an automatic veriļ¬cation of a certiļ¬cate each time it is
used on the network. Once expiration approaches, the automated system will
request a key update from a suitable CA or more likely, an RA. Once the new
certiļ¬cate is created by a CA, it is automatically replaced and the end-user is
spared any unnecessary burden of having to interact to make it so.
If private keys are lost by end-users, and they will be, there should also be an
optimal automatic process of key recovery in the PKI (see [1]). Note that this
means the recovery of private decryption keys only, not private signature keys,
for the reasons cited above. An alternative method to the CAs storing public
keys and certiļ¬cates for digital signature purposes is the RSA digital envelope
(see page 75). Alice can use a secret symmetric session key to encipher, but
also she encrypted it, using an RSA public recovery key, when it was generated.
Thus, if Alice loses her key, the CA who owns the private RSA recovery key
can open the digital envelope and recover Aliceā™s session key. Key recovery can
also be accomplished using secret sharing schemes such as those we discussed in
Section 8.1. These key recovery threshold schemes are also very common. The
palatable aspect of using threshold schemes is the checks and balances feature.
Splitting a private key among shares thwarts attempts by any one entity from
capturing private keys in a clandestine fashion. Yet, it allows, as we have seen,
a reconstruction of the key shares without one or more of the trusted entities
being present to pool the shares.
The future of PKI is open, vigorous, and exciting. It is developing at a
fast pace and new standards are emerging. For instance, the reader may con-
sult the PKI Forum for further information at: http://www.pkiforum.org.
Recall that we have already mentioned the IETFā™s working group, see:
http://www.ietf.cnri.reston.va.us/html.charters/pkix-charter.html. Moreover,
there are standard PKIs developed by The Government of Canada:
http://www.cse-cst.gc.ca/en/services/pki/pki.html. NIST has a Federal PKI
Technical Working Group (PKI-TWG) studying PKI infrastructures for use by
government agencies: http://csrc.nist.gov/pki/twg/. The Open Group, an in-
ternational vendor and technology-neutral consortium, is developing PKI stan-
dards: http://www.opengroup.org/public/tech/security/pki/cki/, and there
are numerous others.
In the next chapter we will look at the future of PKI and several revolution-
ary applications. We have barely opened the door, but what we see is truly a
magniļ¬cent vista to bring us a better and more secure world.

Ā© 2003 by CRC Press LLC