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

secret sharing is secure key management, about which we will learn more as this

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

contradict Lagrangeā™s Theorem C.40.

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

she received from Trent.

ā’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).

Password-based protocols are subject to password sniļ¬ng, which is an attack

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

instead of relying on shared secrets, or password/password equivalents stored on

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:

http://www-cs-students.stanford.edu/Ėtjw/srp/download.html.

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

driverā™s license.

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

method for key generation. See also [1] and [172].

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