chp 5.pdf

CHAPTER DIGITAL SIGNATURES 13.1 Digital Signatures Properties Attacks and Forgeries Digital Signature Requirements Direct Digital Signature 13.2 ElGamal Digital Signature Scheme 13.3 Schnorr Digital...

CHAPTER DIGITAL SIGNATURES 13.1 Digital Signatures Properties Attacks and Forgeries Digital Signature Requirements Direct Digital Signature 13.2 ElGamal Digital Signature Scheme 13.3 Schnorr Digital Signature Scheme 13.4 Digital Signature Standard The DSS Approach The Digital Signature Algorithm 13.5 Recommended Reading and Web Site 13.6 Key Terms, Review Questions, and Problems 395 396 CHAPTER 13 / DIGITAL SIGNATURES To guard against the baneful influence exerted by strangers is therefore an elementary dictate of savage prudence. Hence before strangers are allowed to enter a district, or at least before they are permitted to mingle freely with the inhabitants, certain ceremonies are often performed by the natives of the coun- try for the purpose of disarming the strangers of their magical powers, or of disinfecting, so to speak, the tainted atmosphere by which they are supposed to be surrounded. —The Golden Bough, Sir James George Frazer KEY POINTS ◆ A digital signature is an authentication mechanism that enables the creator of a message to attach a code that acts as a signature. Typically the signature is formed by taking the hash of the message and encrypting the message with the creator’s private key. The signature guarantees the source and integrity of the message. ◆ The digital signature standard (DSS) is an NIST standard that uses the secure hash algorithm (SHA). The most important development from the work on public-key cryptography is the digital signature. The digital signature provides a set of security capabilities that would be difficult to implement in any other way. Figure 13.1 is a generic model of the process of making and using digital signa- tures. Bob can sign a message using a digital signature generation algorithm.The inputs to the algorithm are the message and Bob’s private key. Any other user, say Alice, can verify the signature using a verification algorithm, whose inputs are the message, the signature, and Bob’s public key. In simplified terms, the essence of the digital signature mechanism is shown in Figure 13.2. This repeats the logic shown in Figure 11.3. A worked-out example, using RSA, is available at this book’s Web site. We begin this chapter with an overview of digital signatures. Then, we introduce the Digital Signature Standard (DSS). 13.1 DIGITAL SIGNATURES Properties Message authentication protects two parties who exchange messages from any third party. However, it does not protect the two parties against each other. Several forms of dispute between the two are possible.  13.1 / DIGITAL SIGNATURES 397 Bob Transmit Alice Message M Bob’s Bob’s private public key key Message M Digital Digital signature signature generation S verification algorithm algorithm S Return signature valid or not valid Bob’s signature for M Figure 13.1 Generic Model of Digital Signature Process For example, suppose that John sends an authenticated message to Mary, using one of the schemes of Figure 12.1. Consider the following disputes that could arise. 1. Mary may forge a different message and claim that it came from John. Mary would simply have to create a message and append an authentication code using the key that John and Mary share. 2. John can deny sending the message. Because it is possible for Mary to forge a message, there is no way to prove that John did in fact send the message. Both scenarios are of legitimate concern. Here is an example of the first sce- nario: An electronic funds transfer takes place, and the receiver increases the amount of funds transferred and claims that the larger amount had arrived from the sender. An example of the second scenario is that an electronic mail message contains instructions to a stockbroker for a transaction that subsequently turns out badly. The sender pretends that the message was never sent. 398 CHAPTER 13 / DIGITAL SIGNATURES Bob Alice Message M Bob’s Message M public key S Cryptographic hash Cryptographic function hash Bob’s function Decrypt private key h h h’ Encrypt Compare S Return Bob’s signature signature valid or not valid for M Figure 13.2 Simplified Depiction of Essential Elements of Digital Signature Process In situations where there is not complete trust between sender and receiver, something more than authentication is needed. The most attractive solution to this problem is the digital signature. The digital signature must have the following properties: It must verify the author and the date and time of the signature. It must authenticate the contents at the time of the signature. It must be verifiable by third parties, to resolve disputes. Thus, the digital signature function includes the authentication function. Attacks and Forgeries [GOLD88] lists the following types of attacks, in order of increasing severity. Here A denotes the user whose signature method is being attacked, and C denotes the attacker.  13.1 / DIGITAL SIGNATURES 399 Key-only attack: C only knows A’s public key. Known message attack: C is given access to a set of messages and their signatures. Generic chosen message attack: C chooses a list of messages before attempt- ing to breaks A’s signature scheme, independent of A’s public key. C then obtains from A valid signatures for the chosen messages. The attack is generic, because it does not depend on A’s public key; the same attack is used against everyone. Directed chosen message attack: Similar to the generic attack, except that the list of messages to be signed is chosen after C knows A’s public key but before any signatures are seen. Adaptive chosen message attack: C is allowed to use A as an “oracle.” This means the A may request signatures of messages that depend on previously obtained message–signature pairs. [GOLD88] then defines success at breaking a signature scheme as an outcome in which C can do any of the following with a non-negligible probability: Total break: C determines A’s private key. Universal forgery: C finds an efficient signing algorithm that provides an equivalent way of constructing signatures on arbitrary messages. Selective forgery: C forges a signature for a particular message chosen by C. Existential forgery: C forges a signature for at least one message. C has no control over the message. Consequently, this forgery may only be a minor nuisance to A. Digital Signature Requirements On the basis of the properties and attacks just discussed, we can formulate the fol- lowing requirements for a digital signature. The signature must be a bit pattern that depends on the message being signed. The signature must use some information unique to the sender to prevent both forgery and denial. It must be relatively easy to produce the digital signature. It must be relatively easy to recognize and verify the digital signature. It must be computationally infeasible to forge a digital signature, either by constructing a new message for an existing digital signature or by constructing a fraudulent digital signature for a given message. It must be practical to retain a copy of the digital signature in storage. A secure hash function, embedded in a scheme such as that of Figure 13.2, provides a basis for satisfying these requirements. However, care must be taken in the design of the details of the scheme. 400 CHAPTER 13 / DIGITAL SIGNATURES Direct Digital Signature The term direct digital signature refers to a digital signature scheme that involves only the communicating parties (source, destination). It is assumed that the destina- tion knows the public key of the source. Confidentiality can be provided by encrypting the entire message plus signa- ture with a shared secret key (symmetric encryption). Note that it is important to perform the signature function first and then an outer confidentiality function. In case of dispute, some third party must view the message and its signature. If the signature is calculated on an encrypted message, then the third party also needs access to the decryption key to read the original message. However, if the signature is the inner operation, then the recipient can store the plaintext message and its sig- nature for later use in dispute resolution. The validity of the scheme just described depends on the security of the sender’s private key. If a sender later wishes to deny sending a particular message, the sender can claim that the private key was lost or stolen and that someone else forged his or her signature. Administrative controls relating to the security of pri- vate keys can be employed to thwart or at least weaken this ploy, but the threat is still there, at least to some degree. One example is to require every signed message to include a timestamp (date and time) and to require prompt reporting of compro- mised keys to a central authority. Another threat is that some private key might actually be stolen from X at time T. The opponent can then send a message signed with X’s signature and stamped with a time before or equal to T. The universally accepted technique for dealing with these threats is the use of a digital certificate and certificate authorities. We defer a discussion of this topic until Chapter 14, and focus in this chapter on digital signature algorithms. 13.2 ELGAMAL DIGITAL SIGNATURE SCHEME Before examining the NIST Digital Signature standard, it will be helpful to under- stand the ElGamal and Schnorr signature schemes. Recall from Chapter 10, that the ElGamal encryption scheme is designed to enable encryption by a user’s public key with decryption by the user’s private key. The ElGamal signature scheme involves the use of the private key for encryption and the public key for decryption [ELGA84, ELGA85]. Before proceeding, we need a result from number theory. Recall from Chapter 8 that for a prime number q, if a is a primitive root of q, then a, a2,... , aq - 1 are distinct (mod q). It can be shown that, if a is a primitive root of q, then 1. For any integer m, am K 1 (mod q) if and only if m K 0 (mod q - 1). 2. For any integers, i, j, ai K aj (mod q) if and only if i K j (mod q - 1).  13.2 / ELGAMAL DIGITAL SIGNATURE SCHEME 401 As with ElGamal encryption, the global elements of ElGamal digital signature are a prime number q and α, which is a primitive root of q. User A generates a private/public key pair as follows. 1. Generate a random integer XA, such that 1 6 XA 6 q - 1. 2. Compute YA = aXA mod q. 3. A’s private key is XA; A’s pubic key is {q, a, YA}. To sign a message M, user A first computes the hash m = H(M), such that m is an integer in the range 0 … m … q - 1. A then forms a digital signature as follows. 1. Choose a random integer K such that 1 … K … q - 1 and gcd(K, q - 1) = 1. That is, K is relatively prime to q - 1. 2. Compute S1 = aK mod q. Note that this is the same as the computation of C1 for ElGamal encryption. 3. Compute K - 1mod (q - 1). That is, compute the inverse of K modulo q - 1. 4. Compute S2 = K - 1(m - XAS1) mod (q - 1). 5. The signature consists of the pair (S1, S2). Any user B can verify the signature as follows. 1. Compute V1 = am mod q. 2. Compute V2 = 1YA2S11S12S2 mod q. The signature is valid if V1 = V2. Let us demonstrate that this is so. Assume that the equality is true. Then we have am mod q = 1YA2S11S12S2 mod q assume V1 = V2 am mod q = aXAS1aKS2 mod q substituting for YA and S1 am - XA S1 mod q = aKS2 mod q rearranging terms m - XAS1 K KS2 mod (q - 1) property of primitive roots m - XAS1 K KK - 1 (m - XAS1) mod (q - 1) substituting for S2 For example, let us start with the prime field GF(19); that is, q = 19. It has primitive roots {2, 3, 10, 13, 14, 15}, as shown in Table 8.3. We choose a = 10. Alice generates a key pair as follows: 1. Alice chooses XA = 16. 2. Then YA = aXA mod q = a16 mod 19 = 4. 3. Alice’s private key is 16; Alice’s pubic key is {q, a, YA} = {19, 10, 4}. Suppose Alice wants to sign a message with hash value m = 14. 1. Alice chooses K = 5, which is relatively prime to q - 1 = 18. 2. S1 = aK mod q = 105 mod 19 = 3 (see Table 8.3). 402 CHAPTER 13 / DIGITAL SIGNATURES 3. K - 1 mod (q - 1) = 5 - 1 mod 18 = 11. 4. S2 = K - 1 (m - XAS1) mod (q - 1) = 11 (14 - (16)(3)) mod 18 = -374 mod 18 = 4. Bob can verify the signature as follows. 1. V1 = am mod q = 1014 mod 19 = 16. 2. V2 = (YA)S1(S1)S2 mod q = (43)(34) mod 19 = 5184 mod 19 = 16. Thus, the signature is valid. 13.3 SCHNORR DIGITAL SIGNATURE SCHEME As with the ElGamal digital signature scheme, the Schnorr signature scheme is based on discrete logarithms [SCHN89, SCHN91]. The Schnorr scheme minimizes the message-dependent amount of computation required to generate a signature. The main work for signature generation does not depend on the message and can be done during the idle time of the processor. The message-dependent part of the signature generation requires multiplying a 2n-bit integer with an n-bit integer. The scheme is based on using a prime modulus p, with p - 1 having a prime factor q of appropriate size; that is, p - 1 K (mod q). Typically, we use p L 21024 and q L 2160. Thus, p is a 1024-bit number, and q is a 160-bit number, which is also the length of the SHA-1 hash value. The first part of this scheme is the generation of a private/public key pair, which consists of the following steps. 1. Choose primes p and q, such that q is a prime factor of p - 1. 2. Choose an integer a, such that aq = 1 mod p. The values a, p, and q comprise a global public key that can be common to a group of users. 3. Choose a random integer s with 0 6 s 6 q. This is the user’s private key. 4. Calculate v = a - s mod p. This is the user’s public key. A user with private key s and public key v generates a signature as follows. 1. Choose a random integer r with 0 6 r 6 q and compute x = ar mod p. This computation is a preprocessing stage independent of the message M to be signed. 2. Concatenate the message with x and hash the result to compute the value e: e = H(M || x) 3. Compute y = (r + se) mod q. The signature consists of the pair (e, y).  13.4 / DIGITAL SIGNATURE STANDARD 403 Any other user can verify the signature as follows. 1. Compute x¿ = ayve mod p. 2. Verify that e = H(M || x¿). To see that the verification works, observe that x¿ K ayve K aya - se K ay - se K ar K x (mod p) Hence, H(M || x¿) = H(M || x). 13.4 DIGITAL SIGNATURE STANDARD The National Institute of Standards and Technology (NIST) has published Federal Information Processing Standard FIPS 186, known as the Digital Signature Standard (DSS). The DSS makes use of the Secure Hash Algorithm (SHA) described in Chapter 12 and presents a new digital signature technique, the Digital Signature Algorithm (DSA). The DSS was originally proposed in 1991 and revised in 1993 in response to public feedback concerning the security of the scheme. There was a further minor revision in 1996. In 2000, an expanded version of the standard was issued as FIPS 186-2, subsequently updated to FIPS 186-3 in 2009. This latest version also incorporates digital signature algorithms based on RSA and on elliptic curve cryptography. In this section, we discuss the original DSS algorithm. The DSS Approach The DSS uses an algorithm that is designed to provide only the digital signature function. Unlike RSA, it cannot be used for encryption or key exchange. Nevertheless, it is a public-key technique. Figure 13.3 contrasts the DSS approach for generating digital signatures to that used with RSA. In the RSA approach, the message to be signed is input to a hash function that produces a secure hash code of fixed length. This hash code is then encrypted using the sender’s private key to form the signature. Both the mes- sage and the signature are then transmitted. The recipient takes the message and produces a hash code. The recipient also decrypts the signature using the sender’s public key. If the calculated hash code matches the decrypted signature, the signa- ture is accepted as valid. Because only the sender knows the private key, only the sender could have produced a valid signature. The DSS approach also makes use of a hash function. The hash code is pro- vided as input to a signature function along with a random number k generated for this particular signature. The signature function also depends on the sender’s private key (PRa) and a set of parameters known to a group of communicating principals. We can consider this set to constitute a global public key (PUG).1 The result is a sig- nature consisting of two components, labeled s and r. 1 It is also possible to allow these additional parameters to vary with each user so that they are a part of a user’s public key. In practice, it is more likely that a global public key will be used that is separate from each user’s public key. 404 CHAPTER 13 / DIGITAL SIGNATURES H M || M PRa PUa Compare H E E(PRa, H(M)] D (a) RSA approach M || M H PUG PRa s PUG PUa r H Sig Ver Compare k (b) DSS approach Figure 13.3 Two Approaches to Digital Signatures At the receiving end, the hash code of the incoming message is generated. This plus the signature is input to a verification function. The verification function also depends on the global public key as well as the sender’s public key (PUa), which is paired with the sender’s private key. The output of the verification function is a value that is equal to the signature component r if the signature is valid. The signa- ture function is such that only the sender, with knowledge of the private key, could have produced the valid signature. We turn now to the details of the algorithm. The Digital Signature Algorithm The DSA is based on the difficulty of computing discrete logarithms (see Chapter 8) and is based on schemes originally presented by ElGamal [ELGA85] and Schnorr [SCHN91]. Figure 13.4 summarizes the algorithm.There are three parameters that are pub- lic and can be common to a group of users. A 160-bit prime number q is chosen. Next, a prime number p is selected with a length between 512 and 1024 bits such that q (p - 1)/q divides (p - 1). Finally, g is chosen to be of the form h mod p, where h is an integer between 1 and (p - 1) with the restriction that g must be greater than 1.2 Thus, the global public-key components of DSA have the same for as in the Schnorr signature scheme. With these numbers in hand, each user selects a private key and generates a public key. The private key x must be a number from 1 to (q - 1) and should be cho- sen randomly or pseudorandomly. The public key is calculated from the private key as y = gx mod p. The calculation of y given x is relatively straightforward. However, given the public key y, it is believed to be computationally infeasible to determine x, which is the discrete logarithm of y to the base g, modp (see Chapter 8). 2 In number-theoretic terms, g is of order q mod p; see Chapter 8.  13.4 / DIGITAL SIGNATURE STANDARD 405 Global Public-Key Components Signing L1 p prime number where 2 p2 L r  (g mod p) mod q k for 512  L  1024 and L a multiple of 64; i.e., bit length of between 512 and 1024 bits s  [k1 (H(M)  xr)] mod q in increments of 64 bits Signature  (r, s) q prime divisor of (p  1), where 2159  q  2160; i.e., bit length of 160 bits Verifying (p  1)/q g h mod p, w  (s ) 1 mod q where h is any integer with 1  h  (p  1) such that h(p  1)/q mod p 1 u1  [H(M )w] mod q u2  (r )w mod q User’s Private Key v  [(gu1 yu2) mod p] mod q x random or pseudorandom integer with 0  x  q TEST: v  r User’s Public Key M  message to be signed y  gx mod p H(M)  hash of M using SHA-1 M , r , s  received versions of M, r, s User's Per-Message Secret Number k  random or pseudorandom integer with 0  k  q Figure 13.4 The Digital Signature Algorithm (DSA) To create a signature, a user calculates two quantities, r and s, that are func- tions of the public key components (p, q, g), the user’s private key (x), the hash code of the message H(M), and an additional integer k that should be generated randomly or pseudorandomly and be unique for each signing. At the receiving end, verification is performed using the formulas shown in Figure 13.4.The receiver generates a quantity v that is a function of the public key com- ponents, the sender’s public key, and the hash code of the incoming message. If this quantity matches the r component of the signature, then the signature is validated. Figure 13.5 depicts the functions of signing and verifying. The structure of the algorithm, as revealed in Figure 13.5, is quite interesting. Note that the test at the end is on the value r, which does not depend on the message at all. Instead, r is a function of k and the three global public-key components. The multiplicative inverse of k (mod q) is passed to a function that also has as inputs the message hash code and the user’s private key. The structure of this function is such that the receiver can recover r using the incoming message and signature, the public key of the user, and the global public key. It is certainly not obvious from Figure 13.4 or Figure 13.5 that such a scheme would work. A proof is provided in Appendix K. Given the difficulty of taking discrete logarithms, it is infeasible for an oppo- nent to recover k from r or to recover x from s. Another point worth noting is that the only computationally demanding task in signature generation is the exponential calculation gk mod p. Because this value does not depend on the message to be signed, it can be computed ahead of time. 406 CHAPTER 13 / DIGITAL SIGNATURES p q g f2 r y q g H M x q q k s f4 v r f3 M f1 s H Compare s  f1(H(M), k, x, r, q)  (k1 (H(M)  xr)) mod q w  f3(s , q) = (s )1 mod q r  f2(k, p, q, g)  (gk mod p) mod q v  f4(y, q, g, H(M ), w, r )  ((g(H(M )w) mod q yr w mod q) mod p) mod q (a) Signing (b) Verifying Figure 13.5 DSS Signing and Verifying Indeed, a user could precalculate a number of values of r to be used to sign documents as needed. The only other somewhat demanding task is the determina- tion of a multiplicative inverse, k - 1. Again, a number of these values can be precalculated. 13.5 RECOMMENDED READING AND WEB SITE [AKL83] is the classic paper on digital signatures and is still highly relevant. A more recent, and excellent, survey is [MITC92]. AKL83 Akl, S. “Digital Signatures: A Tutorial Survey.” Computer, February 1983. MITC92 Mitchell, C.; Piper, F. ; and Wild, P. “Digital Signatures.” In [SIMM92a]. Recommended Web Site: Digital Signatures: NIST page with information on NIST-approved digital signature options.  13.6 / KEY TERM, REVIEW QUESTIONS, AND PROBLEMS 407 13.6 KEY TERM, REVIEW QUESTIONS, AND PROBLEMS Key Terms direct digital signature digital signature standard Schnorr digital signature digital signature (DSS) timestamp digital signature algorithm ElGamal digital signature (DSA) Review Questions 13.1 List two disputes that can arise in the context of message authentication. 13.2 What are the properties a digital signature should have? 13.3 What requirements should a digital signature scheme satisfy? 13.4 What is the difference between direct and arbitrated digital signature? 13.5 In what order should the signature function and the confidentiality function be applied to a message, and why? 13.6 What are some threats associated with a direct digital signature scheme? Problems 13.1 Dr. Watson patiently waited until Sherlock Holmes finished. “Some interesting prob- lem to solve, Holmes?” he asked when Holmes finally logged out. “Oh, not exactly. I merely checked my e-mail and then made a couple of net- work experiments instead of my usual chemical ones. I have only one client now and I have already solved his problem. If I remember correctly, you once mentioned cryp- tology among your other hobbies, so it may interest you.” “Well, I am only an amateur cryptologist, Holmes. But of course I am interested in the problem. What is it about?” “My client is Mr. Hosgrave, director of a small but progressive bank. The bank is fully computerized and of course uses network communications extensively. The bank already uses RSA to protect its data and to digitally sign documents that are communicated. Now the bank wants to introduce some changes in its procedures; in particular, it needs to digitally sign some documents by two signatories. 1. The first signatory prepares the document, forms its signature, and passes the doc- ument to the second signatory. 2. The second signatory as a first step must verify that the document was really signed by the first signatory. She then incorporates her signature into the docu- ment’s signature so that the recipient, as well as any member of the public, may verify that the document was indeed signed by both signatories. In addition, only the second signatory has to be able to verify the document’s signature after the first step; that is, the recipient (or any member of the public) should be able to verify only the complete document with signatures of both signatories, but not the document in its intermediate form where only one signatory has signed it. Moreover, the bank would like to make use of its existing modules that support RSA-style digital signatures.” “Hm, I understand how RSA can be used to digitally sign documents by one signa- tory, Holmes. I guess you have solved the problem of Mr. Hosgrave by appropriate generalization of RSA digital signatures.” 408 CHAPTER 13 / DIGITAL SIGNATURES “Exactly, Watson,” nodded Sherlock Holmes. “Originally, the RSA digital sig- nature was formed by encrypting the document by the signatory’s private decryption key ‘d’, and the signature could be verified by anyone through its decryption using publicly known encryption key ‘e’. One can verify that the signature S was formed by the person who knows d, which is supposed to be the only signatory. Now the problem of Mr. Hosgrave can be solved in the same way by slight generalization of the process, that is...” Finish the explanation. 13.2 DSA specifies that if the signature generation process results in a value of s = 0, a new value of k should be generated and the signature should be recalculated. Why? 13.3 What happens if a k value used in creating a DSA signature is compromised? 13.4 The DSS document includes a recommended algorithm for testing a number for primality. 1. [Choose w] Let w be a random odd integer. Then (w - 1) is even and can be expressed in the form 2am with m odd. That is, 2a is the largest power of 2 that divides (w - 1). 2. [Generate b] Let b be a random integer in the range 1 6 b 6 w. 3. [Exponentiate] Set j = 0 and z = bm mod w. 4. [Done?] If j = 0 and z = 1, or if z = w - 1, then w passes the test and may be prime; go to step 8. 5. [Terminate?] If j 7 0 and z = 1, then w is not prime; terminate algorithm for this w. 6. [Increase j] Set j = j + 1. If j 6 a, set z = z2mod w and go to step 4. 7. [Terminate] w is not prime; terminate algorithm for this w. 8. [Test again?] If enough random values of b have been tested, then accept w as prime and terminate algorithm; otherwise, go to step 2. a. Explain how the algorithm works. b. Show that it is equivalent to the Miller-Rabin test described in Chapter 8. 13.5 With DSS, because the value of k is generated for each signature, even if the same message is signed twice on different occasions, the signatures will differ. This is not true of RSA signatures. What is the practical implication of this difference? 13.6 Consider the problem of creating domain parameters for DSA. Suppose we have already found primes p and q such that q|(p - 1). Now we need to find g H Zp with g of order q mod p. Consider the following two algorithms: Algorithm 1 Algorithm 2 repeat repeat select g 僆 Zp select h 僆 Zp h ; gq mod p g ; h(p - l)/p mod p until (h = 1 and g Z 1) until (g Z 1) return g return g a. Prove that the value returned by Algorithm 1 has order q. b. Prove that the value returned by Algorithm 2 has order q. c. Suppose p = 40193 and q = 157. How many loop iterations do you expect Algorithm 1 to make before it finds a generator? d. If p is 1024 bits and q is 160 bits, would you recommend using Algorithm 1 to find g? Explain. e. Suppose p = 40193 and q = 157. What is the probability that Algorithm 2 com- putes a generator in its very first loop iteration? (If it is helpful, you may use the fact that a w1d2 = n when answering this question.) dƒn  13.6 / KEY TERM, REVIEW QUESTIONS, AND PROBLEMS 409 13.7 It is tempting to try to develop a variation on Diffie-Hellman that could be used as a digital signature. Here is one that is simpler than DSA and that does not require a secret random number in addition to the private key. Public elements: q prime number a a 6 q and a is a primitive root of q Private key: X X 6 q Public key: Y = aX mod q To sign a message M, compute h = H(M), which is the hash code of the message. We require that gcd(h, q - 1) = 1. If not, append the hash to the message and calculate a new hash. Continue this process until a hash code is produced that is relatively prime to (q - 1). Then calculate Z to satisfy Z * h K X(mod q - 1). The signature of the message is aZ. To verify the signature, a user verifies that Y = (aZ)h = aXmod q. a. Show that this scheme works. That is, show that the verification process produces an equality if the signature is valid. b. Show that the scheme is unacceptable by describing a simple technique for forg- ing a user’s signature on an arbitrary message. 13.8 An early proposal for a digital signature scheme using symmetric encryption is based on the following. To sign an n-bit message, the sender randomly generates in advance 2n 56-bit cryptographic keys: k1, K1, k2, K2,... , kn, Kn which are kept private. The sender prepares in advance two sets of corresponding non-secret 64-bit validation parameters, which are made public: u1, U1, u2, U2,... , un, Un and v1, V1, v2, V2,... , vn, Vn where vi = E(ki, ui), Vi = E(ki, Ui) The message M is signed as follows. For the ith bit of the message, either ki or Ki is attached to the message, depending on whether the message bit is 0 or 1. For example, if the first three bits of the message are 011, then the first three keys of the signature are k1, K2, K3. a. How does the receiver validate the message? b. Is the technique secure? c. How many times can the same set of secret keys be safely used for different messages? d. What, if any, practical problems does this scheme present? This page intentionally left blank PART 4: MUTUAL TRUST CHAPTER KEY MANAGEMENT AND DISTRIBUTION 14.1 Symmetric Key Distribution Using Symmetric Encryption A Key Distribution Scenario Hierarchical Key Control Session Key Lifetime A Transparent Key Control Scheme Decentralized Key Control Controlling Key Usage 14.2 Symmetric Key Distribution Using Asymmetric Encryption Simple Secret Key Distribution Secret Key Distribution with Confidentiality and Authentication A Hybrid Scheme 14.3 Distribution Of Public Keys Public Announcement of Public Keys Publicly Available Directory Public-Key Authority Public-Key Certificates 14.4 X.509 Certificates Certificates X.509 Version 3 14.5 Public-Key Infrastructure PKIX Management Functions PKIX Management Protocols 14.6 Recommended Reading and Web Sites 14.7 Key Terms, Review Questions, and Problems 411 412 CHAPTER 14 / KEY MANAGEMENT AND DISTRIBUTION No Singhalese, whether man or woman, would venture out of the house without a bunch of keys in his hand, for without such a talisman he would fear that some devil might take advantage of his weak state to slip into his body. —The Golden Bough, Sir James George Frazer John wrote the letters of the alphabet under the letters in its first lines and tried it against the message. Immediately he knew that once more he had broken the code. It was extraordinary the feeling of triumph he had. He felt on top of the world. For not only had he done it, had he broken the July code, but he now had the key to every future coded message, since instructions as to the source of the next one must of necessity appear in the current one at the end of each month. —Talking to Strange Men, Ruth Rendall KEY POINTS ◆ Key distribution is the function that delivers a key to two parties who wish to exchange secure encrypted data. Some sort of mechanism or pro- tocol is needed to provide for the secure distribution of keys. ◆ Key distribution often involves the use of master keys, which are infre- quently used and are long lasting, and session keys, which are generated and distributed for temporary use between two parties. ◆ Public-key encryption schemes are secure only if the authenticity of the public key is assured. A public-key certificate scheme provides the neces- sary security. ◆ X.509 defines the format for public-key certificates. This format is widely used in a variety of applications. ◆ A public-key infrastructure (PKI) is defined as the set of hardware, software, people, policies, and procedures needed to create, manage, store, distribute, and revoke digital certificates based on asymmetric cryptography. ◆ Typically, PKI implementations make use of X.509 certificates. The topics of cryptographic key management and cryptographic key distribution are complex, involving cryptographic, protocol, and management considerations. The pur- pose of this chapter is to give the reader a feel for the issues involved and a broad sur- vey of the various aspects of key management and distribution. For more information, the place to start is the three-volume NIST SP 800-57, followed by the recommended readings listed at the end of this chapter.  14.1 / SYMMETRIC KEY DISTRIBUTION USING SYMMETRIC ENCRYPTION 413 14.1 SYMMETRIC KEY DISTRIBUTION USING SYMMETRIC ENCRYPTION For symmetric encryption to work, the two parties to an exchange must share the same key, and that key must be protected from access by others. Furthermore, fre- quent key changes are usually desirable to limit the amount of data compromised if an attacker learns the key. Therefore, the strength of any cryptographic system rests with the key distribution technique, a term that refers to the means of deliver- ing a key to two parties who wish to exchange data without allowing others to see the key. For two parties A and B, key distribution can be achieved in a number of ways, as follows: 1. A can select a key and physically deliver it to B. 2. A third party can select the key and physically deliver it to A and B. 3. If A and B have previously and recently used a key, one party can transmit the new key to the other, encrypted using the old key. 4. If A and B each has an encrypted connection to a third party C, C can deliver a key on the encrypted links to A and B. Options 1 and 2 call for manual delivery of a key. For link encryption, this is a reasonable requirement, because each link encryption device is going to be exchang- ing data only with its partner on the other end of the link. However, for end-to-end encryption over a network, manual delivery is awkward. In a distributed system, any given host or terminal may need to engage in exchanges with many other hosts and terminals over time. Thus, each device needs a number of keys supplied dynamically. The problem is especially difficult in a wide-area distributed system. The scale of the problem depends on the number of communicating pairs that must be supported. If end-to-end encryption is done at a network or IP level, then a key is needed for each pair of hosts on the network that wish to communicate. Thus, if there are N hosts, the number of required keys is [N(N - 1)]/2. If encryption is done at the application level, then a key is needed for every pair of users or processes that require communication. Thus, a network may have hundreds of hosts but thousands of users and processes. Figure 14.1 illustrates the magnitude of the key distribution task for end-to-end encryption.1 A network using node-level encryption with 1000 nodes would conceivably need to distribute as many as half a million keys. If that same network supported 10,000 applications, then as many as 50 million keys may be required for application-level encryption. Returning to our list, option 3 is a possibility for either link encryption or end- to-end encryption, but if an attacker ever succeeds in gaining access to one key, then all subsequent keys will be revealed. Furthermore, the initial distribution of poten- tially millions of keys still must be made. 1 Note that this figure uses a log-log scale, so that a linear graph indicates exponential growth. A basic review of log scales is in the math refresher document at the Computer Science Student Resource Site at WilliamStallings.com/StudentSupport.html. 414 CHAPTER 14 / KEY MANAGEMENT AND DISTRIBUTION 109 108 Number of keys 107 106 5 6 7 8 9 2 3 4 5 6 7 8 9 2 3 4 5 6 7 8 9 103 104 105 Number of endpoints Figure 14.1 Number of Keys Required to Support Arbitrary Connections between Endpoints For end-to-end encryption, some variation on option 4 has been widely adopted. In this scheme, a key distribution center is responsible for distributing keys to pairs of users (hosts, processes, applications) as needed. Each user must share a unique key with the key distribution center for purposes of key distribution. The use of a key distribution center is based on the use of a hierarchy of keys. At a minimum, two levels of keys are used (Figure 14.2). Communication between end systems is encrypted using a temporary key, often referred to as a session key. Typically, the session key is used for the duration of a logical connection, such as a frame relay connection or transport connection, and then discarded. Each session key is obtained from the key distribution center over the same networking facilities used for end-user communication. Accordingly, session keys are transmitted in encrypted form, using a master key that is shared by the key distribution center and an end system or user. For each end system or user, there is a unique master key that it shares with the key distribution center. Of course, these master keys must be distributed in some fashion. However, the scale of the problem is vastly reduced. If there are N entities that wish to communicate in pairs, then, as was mentioned, as many as [N(N - 1)]/2 session keys are needed at any one time. However, only N master keys are required, one for each entity. Thus, master keys can be distributed in some noncryptographic way, such as physical delivery.  14.1 / SYMMETRIC KEY DISTRIBUTION USING SYMMETRIC ENCRYPTION 415 Data Cryptographic protection Session keys Cryptographic protection Master keys Non-cryptographic protection Figure 14.2 The Use of a Key Hierarchy A Key Distribution Scenario The key distribution concept can be deployed in a number of ways. A typical sce- nario is illustrated in Figure 14.3, which is based on a figure in [POPE79]. The sce- nario assumes that each user shares a unique master key with the key distribution center (KDC). Key Distribution Center (KDC) (1) IDA || IDB || N1 Key distribution (2) E(Ka, [Ks || IDA || IDB || N1]) || E(Kb, [Ks || IDA]) steps (3) E(Kb, [Ks || IDA]) Initiator Responder A B (4) E(Ks, N2) (5) E(Ks, f(N2)) Authentication steps Figure 14.3 Key Distribution Scenario 416 CHAPTER 14 / KEY MANAGEMENT AND DISTRIBUTION Let us assume that user A wishes to establish a logical connection with B and requires a one-time session key to protect the data transmitted over the connection. A has a master key, Ka, known only to itself and the KDC; similarly, B shares the master key Kb with the KDC. The following steps occur. 1. A issues a request to the KDC for a session key to protect a logical connection to B. The message includes the identity of A and B and a unique identifier, N1, for this transaction, which we refer to as a nonce. The nonce may be a time- stamp, a counter, or a random number; the minimum requirement is that it dif- fers with each request. Also, to prevent masquerade, it should be difficult for an opponent to guess the nonce. Thus, a random number is a good choice for a nonce. 2. The KDC responds with a message encrypted using Ka. Thus, A is the only one who can successfully read the message, and A knows that it originated at the KDC. The message includes two items intended for A: The one-time session key, Ks, to be used for the session The original request message, including the nonce, to enable A to match this response with the appropriate request Thus, A can verify that its original request was not altered before reception by the KDC and, because of the nonce, that this is not a replay of some previous request. In addition, the message includes two items intended for B: The one-time session key, Ks, to be used for the session An identifier of A (e.g., its network address), IDA These last two items are encrypted with Kb (the master key that the KDC shares with B).They are to be sent to B to establish the connection and prove A’s identity. 3. A stores the session key for use in the upcoming session and forwards to B the information that originated at the KDC for B, namely, E(Kb,[Ks ƒ ƒ IDA]). Because this information is encrypted with Kb, it is protected from eavesdrop- ping. B now knows the session key (Ks), knows that the other party is A (from IDA), and knows that the information originated at the KDC (because it is encrypted using Kb). At this point, a session key has been securely delivered to A and B, and they may begin their protected exchange. However, two additional steps are desirable: 4. Using the newly minted session key for encryption, B sends a nonce, N2, to A. 5. Also, using Ks, A responds with f(N2) , where f is a function that performs some transformation on N2 (e.g., adding one). These steps assure B that the original message it received (step 3) was not a replay. Note that the actual key distribution involves only steps 1 through 3, but that steps 4 and 5, as well as step 3, perform an authentication function. 14.1 / SYMMETRIC KEY DISTRIBUTION USING SYMMETRIC ENCRYPTION 417 Hierarchical Key Control It is not necessary to limit the key distribution function to a single KDC. Indeed, for very large networks, it may not be practical to do so. As an alternative, a hierarchy of KDCs can be established. For example, there can be local KDCs, each responsible for a small domain of the overall internetwork, such as a single LAN or a single building. For communication among entities within the same local domain, the local KDC is responsible for key distribution. If two entities in different domains desire a shared key, then the corresponding local KDCs can communicate through a global KDC. In this case, any one of the three KDCs involved can actually select the key. The hierarchical concept can be extended to three or even more layers, depending on the size of the user population and the geographic scope of the internetwork. A hierarchical scheme minimizes the effort involved in master key distribu- tion, because most master keys are those shared by a local KDC with its local enti- ties. Furthermore, such a scheme limits the damage of a faulty or subverted KDC to its local area only. Session Key Lifetime The more frequently session keys are exchanged, the more secure they are, because the opponent has less ciphertext to work with for any given session key. On the other hand, the distribution of session keys delays the start of any exchange and places a burden on network capacity. A security manager must try to balance these competing considerations in determining the lifetime of a particular session key. For connection-oriented protocols, one obvious choice is to use the same ses- sion key for the length of time that the connection is open, using a new session key for each new session. If a logical connection has a very long lifetime, then it would be prudent to change the session key periodically, perhaps every time the PDU (protocol data unit) sequence number cycles. For a connectionless protocol, such as a transaction-oriented protocol, there is no explicit connection initiation or termination. Thus, it is not obvious how often one needs to change the session key. The most secure approach is to use a new ses- sion key for each exchange. However, this negates one of the principal benefits of connectionless protocols, which is minimum overhead and delay for each transac- tion. A better strategy is to use a given session key for a certain fixed period only or for a certain number of transactions. A Transparent Key Control Scheme The approach suggested in Figure 14.3 has many variations, one of which is described in this subsection. The scheme (Figure 14.4) is useful for providing end-to- end encryption at a network or transport level in a way that is transparent to the end users. The approach assumes that communication makes use of a connection-ori- ented end-to-end protocol, such as TCP. The noteworthy element of this approach is a session security module (SSM), which may consist of functionality at one protocol layer, that performs end-to-end encryption and obtains session keys on behalf of its host or terminal. 418 Key distribution 1. Host sends packet requesting connection. 2. Security service buffers packet; asks center KDC for session key. 3. KDC distributes session key to both hosts. 4. Buffered packet transmitted. 3 Application Application 2 1 Security Security service service 4 HOST HOST Network Figure 14.4 Automatic Key Distribution for Connection-Oriented Protocol  14.1 / SYMMETRIC KEY DISTRIBUTION USING SYMMETRIC ENCRYPTION 419 The steps involved in establishing a connection are shown in Figure 14.4. When one host wishes to set up a connection to another host, it transmits a connec- tion-request packet (step 1). The SSM saves that packet and applies to the KDC for permission to establish the connection (step 2). The communication between the SSM and the KDC is encrypted using a master key shared only by this SSM and the KDC. If the KDC approves the connection request, it generates the session key and delivers it to the two appropriate SSMs, using a unique permanent key for each SSM (step 3). The requesting SSM can now release the connection request packet, and a connection is set up between the two end systems (step 4). All user data exchanged between the two end systems are encrypted by their respective SSMs using the one- time session key. The automated key distribution approach provides the flexibility and dynamic characteristics needed to allow a number of terminal users to access a number of hosts and for the hosts to exchange data with each other. Decentralized Key Control The use of a key distribution center imposes the requirement that the KDC be trusted and be protected from subversion. This requirement can be avoided if key distribution is fully decentralized. Although full decentralization is not practical for larger networks using symmetric encryption only, it may be useful within a local context. A decentralized approach requires that each end system be able to communi- cate in a secure manner with all potential partner end systems for purposes of ses- sion key distribution. Thus, there may need to be as many as [n(n - 1)]/2 master keys for a configuration with n end systems. A session key may be established with the following sequence of steps (Figure 14.5). 1. A issues a request to B for a session key and includes a nonce, N1. 2. B responds with a message that is encrypted using the shared master key. The response includes the session key selected by B, an identifier of B, the value f(N1) , and another nonce, N2. 3. Using the new session key, A returns f(N2) to B. (1) IDA || N1 Initiator Responder A B (2) E(Km, [Ks || IDA || IDB || f(N1) || N2 ]) (3) E(Ks, f(N2)) Figure 14.5 Decentralized Key Distribution 420 CHAPTER 14 / KEY MANAGEMENT AND DISTRIBUTION Thus, although each node must maintain at most (n - 1) master keys, as many session keys as required may be generated and used. Because the messages trans- ferred using the master key are short, cryptanalysis is difficult. As before, session keys are used for only a limited time to protect them. Controlling Key Usage The concept of a key hierarchy and the use of automated key distribution techniques greatly reduce the number of keys that must be manually managed and distributed. It also may be desirable to impose some control on the way in which automatically distributed keys are used. For example, in addition to separating mas- ter keys from session keys, we may wish to define different types of session keys on the basis of use, such as Data-encrypting key, for general communication across a network PIN-encrypting key, for personal identification numbers (PINs) used in elec- tronic funds transfer and point-of-sale applications File-encrypting key, for encrypting files stored in publicly accessible locations To illustrate the value of separating keys by type, consider the risk that a master key is imported as a data-encrypting key into a device. Normally, the mas- ter key is physically secured within the cryptographic hardware of the key distrib- ution center and of the end systems. Session keys encrypted with this master key are available to application programs, as are the data encrypted with such session keys. However, if a master key is treated as a session key, it may be possible for an unauthorized application to obtain plaintext of session keys encrypted with that master key. Thus, it may be desirable to institute controls in systems that limit the ways in which keys are used, based on characteristics associated with those keys. One simple plan is to associate a tag with each key ([JONE82]; see also [DAVI89]). The pro- posed technique is for use with DES and makes use of the extra 8 bits in each 64-bit DES key. That is, the eight non-key bits ordinarily reserved for parity checking form the key tag. The bits have the following interpretation: One bit indicates whether the key is a session key or a master key. One bit indicates whether the key can be used for encryption. One bit indicates whether the key can be used for decryption. The remaining bits are spares for future use. Because the tag is embedded in the key, it is encrypted along with the key when that key is distributed, thus providing protection. The drawbacks of this scheme are 1. The tag length is limited to 8 bits, limiting its flexibility and functionality. 2. Because the tag is not transmitted in clear form, it can be used only at the point of decryption, limiting the ways in which key use can be controlled. A more flexible scheme, referred to as the control vector, is described in [MATY91a and b]. In this scheme, each session key has an associated control vector  14.1 / SYMMETRIC KEY DISTRIBUTION USING SYMMETRIC ENCRYPTION 421 Control Master Session Control Master Encrypted vector key key vector key session key Hashing Hashing Function Function Key Plaintext Key Ciphertext input input input input Encryption Decryption Function Function Encrypted Session key session key (a) Control vector encryption (b) Control vector decryption Figure 14.6 Control Vector Encryption and Decryption consisting of a number of fields that specify the uses and restrictions for that session key. The length of the control vector may vary. The control vector is cryptographically coupled with the key at the time of key generation at the KDC. The coupling and decoupling processes are illustrated in Figure 14.6. As a first step, the control vector is passed through a hash function that produces a value whose length is equal to the encryption key length. Hash functions are discussed in detail in Chapter 11. In essence, a hash function maps values from a larger range into a smaller range with a reasonably uniform spread. Thus, for example, if numbers in the range 1 to 100 are hashed into numbers in the range 1 to 10, approximately 10% of the source values should map into each of the target values. The hash value is then XORed with the master key to produce an output that is used as the key input for encrypting the session key. Thus, Hash value = H = h(CV) Key input = Km 䊝 H Ciphertext = E([Km 䊝 H], Ks) where Km is the master key and Ks is the session key. The session key is recovered in plaintext by the reverse operation: D([Km 䊝 H], E([Km 䊝 H], Ks)) 422 CHAPTER 14 / KEY MANAGEMENT AND DISTRIBUTION When a session key is delivered to a user from the KDC, it is accompanied by the control vector in clear form. The session key can be recovered only by using both the master key that the user shares with the KDC and the control vector. Thus, the linkage between the session key and its control vector is maintained. Use of the control vector has two advantages over use of an 8-bit tag. First, there is no restriction on length of the control vector, which enables arbitrarily com- plex controls to be imposed on key use. Second, the control vector is available in clear form at all stages of operation. Thus, control of key use can be exercised in multiple locations. 14.2 SYMMETRIC KEY DISTRIBUTION USING ASYMMETRIC ENCRYPTION Because of the inefficiency of public key cryptosystems, they are almost never used for the direct encryption of sizable block of data, but are limited to relatively small blocks. One of the most important uses of a public-key cryptosystem is to encrypt secret keys for distribution. We see many specific examples of this in Part Five. Here, we discuss general principles and typical approaches. Simple Secret Key Distribution An extremely simple scheme was put forward by Merkle [MERK79], as illustrated in Figure 14.7. If A wishes to communicate with B, the following procedure is employed: 1. A generates a public/private key pair {PUa, PRa} and transmits a message to B consisting of PUa and an identifier of A, IDA. 2. B generates a secret key, Ks, and transmits it to A, which is encrypted with A’s public key. 3. A computes D(PRa, E(PUa, Ks)) to recover the secret key. Because only A can decrypt the message, only A and B will know the identity of Ks. 4. A discards PUa and PRa and B discards PUa. A and B can now securely communicate using conventional encryption and the session key Ks. At the completion of the exchange, both A and B discard Ks. (1) PUa || IDA A B (2) E(PUa, Ks) Figure 14.7 Simple Use of Public-Key Encryption to Establish a Session Key  14.2 / SYMMETRIC KEY DISTRIBUTION USING ASYMMETRIC ENCRYPTION 423 Despite its simplicity, this is an attractive protocol. No keys exist before the start of the communication and none exist after the completion of communication. Thus, the risk of compromise of the keys is minimal. At the same time, the communication is secure from eavesdropping. The protocol depicted in Figure 14.7 is insecure against an adversary who can intercept messages and then either relay the intercepted message or substitute another message (see Figure 1.3c). Such an attack is known as a man-in-the-middle attack [RIVE84]. In this case, if an adversary, E, has control of the intervening com- munication channel, then E can compromise the communication in the following fashion without being detected. 1. A generates a public/private key pair {PUa, PRa} and transmits a message intended for B consisting of PUa and an identifier of A, IDA. 2. E intercepts the message, creates its own public/private key pair {PUe, PRe} and transmits PUe ƒ ƒ IDA to B. 3. B generates a secret key, Ks, and transmits E(PUe, Ks). 4. E intercepts the message and learns Ks by computing D(PRe, E(PUe, Ks)). 5. E transmits E(PUa, Ks) to A. The result is that both A and B know Ks and are unaware that Ks has also been revealed to E. A and B can now exchange messages using Ks. E no longer actively interferes with the communications channel but simply eavesdrops. Knowing Ks, E can decrypt all messages, and both A and B are unaware of the problem. Thus, this simple protocol is only useful in an environment where the only threat is eavesdropping. Secret Key Distribution with Confidentiality and Authentication Figure 14.8, based on an approach suggested in [NEED78], provides protection against both active and passive attacks. We begin at a point when it is assumed that A and B have exchanged public keys by one of the schemes described subsequently in this chapter. Then the following steps occur. (1) E(PUb, [N1 || IDA]) (2) E(PUa, [N1 || N2]) Initiator Responder A B (3) E(PUb, N2) (4) E(PUb, E(PRa, Ks)) Figure 14.8 Public-Key Distribution of Secret Keys 424 CHAPTER 14 / KEY MANAGEMENT AND DISTRIBUTION 1. A uses B’s public key to encrypt a message to B containing an identifier of A(IDA) and a nonce (N1), which is used to identify this transaction uniquely. 2. B sends a message to A encrypted with PUa and containing A’s nonce (N1) as well as a new nonce generated by B (N2). Because only B could have decrypted message (1), the presence of N1 in message (2) assures A that the correspondent is B. 3. A returns N2, encrypted using B’s public key, to assure B that its correspondent is A. 4. A selects a secret key Ks and sends M = E(PUb, E(PRa, Ks)) to B. Encryption of this message with B’s public key ensures that only B can read it; encryption with A’s private key ensures that only A could have sent it. 5. B computes D(PUa, D(PRb, M)) to recover the secret key. The result is that this scheme ensures both confidentiality and authentication in the exchange of a secret key. A Hybrid Scheme Yet another way to use public-key encryption to distribute secret keys is a hybrid approach in use on IBM mainframes [LE93]. This scheme retains the use of a key distribution center (KDC) that shares a secret master key with each user and distributes secret session keys encrypted with the master key. A public key scheme is used to distribute the master keys. The following rationale is provided for using this three-level approach: Performance: There are many applications, especially transaction-oriented applications, in which the session keys change frequently. Distribution of ses- sion keys by public-key encryption could degrade overall system performance because of the relatively high computational load of public-key encryption and decryption. With a three-level hierarchy, public-key encryption is used only occasionally to update the master key between a user and the KDC. Backward compatibility: The hybrid scheme is easily overlaid on an existing KDC scheme with minimal disruption or software changes. The addition of a public-key layer provides a secure, efficient means of distrib- uting master keys. This is an advantage in a configuration in which a single KDC serves a widely distributed set of users. 14.3 DISTRIBUTION OF PUBLIC KEYS Several techniques have been proposed for the distribution of public keys. Virtually all these proposals can be grouped into the following general schemes: Public announcement Publicly available directory Public-key authority Public-key certificates  14.3 / DISTRIBUTION OF PUBLIC KEYS 425 PUa PUb PUa PUb A B PUa PUb PUa PUb Figure 14.9 Uncontrolled Public-Key Distribution Public Announcement of Public Keys On the face of it, the point of public-key encryption is that the public key is public. Thus, if there is some broadly accepted public-key algorithm, such as RSA, any par- ticipant can send his or her public key to any other participant or broadcast the key to the community at large (Figure 14.9). For example, because of the growing pop- ularity of PGP (pretty good privacy, discussed in Chapter 18), which makes use of RSA, many PGP users have adopted the practice of appending their public key to messages that they send to public forums, such as USENET newsgroups and Internet mailing lists. Although this approach is convenient, it has a major weakness. Anyone can forge such a public announcement. That is, some user could pretend to be user A and send a public key to another participant or broadcast such a public key. Until such time as user A discovers the forgery and alerts other participants, the forger is able to read all encrypted messages intended for A and can use the forged keys for authentication (see Figure 9.3). Publicly Available Directory A greater degree of security can be achieved by maintaining a publicly available dynamic directory of public keys. Maintenance and distribution of the public direc- tory would have to be the responsibility of some trusted entity or organization (Figure 14.10). Such a scheme would include the following elements: 1. The authority maintains a directory with a {name, public key} entry for each participant. 2. Each participant registers a public key with the directory authority. Registration would have to be in person or by some form of secure authenti- cated communication. 3. A participant may replace the existing key with a new one at any time, either because of the desire to replace a public key that has already been used for a large amount of data, or because the corresponding private key has been com- promised in some way. 426 CHAPTER 14 / KEY MANAGEMENT AND DISTRIBUTION Public-key directory PUa PUb A B Figure 14.10 Public-Key Publication 4. Participants could also access the directory electronically. For this purpose, secure, authenticated communication from the authority to the participant is mandatory. This scheme is clearly more secure than individual public announcements but still has vulnerabilities. If an adversary succeeds in obtaining or computing the private key of the directory authority, the adversary could authoritatively pass out counterfeit public keys and subsequently impersonate any participant and eaves- drop on messages sent to any participant. Another way to achieve the same end is for the adversary to tamper with the records kept by the authority. Public-Key Authority Stronger security for public-key distribution can be achieved by providing tighter control over the distribution of public keys from the directory. A typical scenario is illustrated in Figure 14.11, which is based on a figure in [POPE79]. As before, the scenario assumes that a central authority maintains a dynamic directory of public keys of all participants. In addition, each participant reliably knows a public key for the authority, with only the authority knowing the corresponding private key. The following steps (matched by number to Figure 14.11) occur. 1. A sends a timestamped message to the public-key authority containing a request for the current public key of B. 2. The authority responds with a message that is encrypted using the authority’s pri- vate key, PRauth.Thus,A is able to decrypt the message using the authority’s pub- lic key.Therefore,A is assured that the message originated with the authority.The message includes the following: B’s public key, PUb, which A can use to encrypt messages destined for B The original request used to enable A to match this response with the cor- responding earlier request and to verify that the original request was not altered before reception by the authority  14.3 / DISTRIBUTION OF PUBLIC KEYS 427 Public-Key Authority (1) Request || T1 (4) Request || T2 (2) E(PRauth, [PUb || Request || T1]) (5) E(PRauth, [PUa || Request || T2]) (3) E(PUb, [ IDA || N1]) Initiator Responder A B (6) E(PUa, [ N1 || N2]) (7) E(PUb, N2) Figure 14.11 Public-Key Distribution Scenario The original timestamp given so A can determine that this is not an old mes- sage from the authority containing a key other than B’s current public key 3. A stores B’s public key and also uses it to encrypt a message to B containing an identifier of A (IDA) and a nonce (N1), which is used to identify this transaction uniquely. 4, 5. B retrieves A’s public key from the authority in the same manner as A retrieved B’s public key. At this point, public keys have been securely delivered to A and B, and they may begin their protected exchange. However, two additional steps are desirable: 6. B sends a message to A encrypted with PUa and containing A’s nonce (N1) as well as a new nonce generated by B (N2). Because only B could have decrypted message (3), the presence of N1 in message (6) assures A that the correspondent is B. 7. A returns N2, which is encrypted using B’s public key, to assure B that its cor- respondent is A. Thus, a total of seven messages are required. However, the initial four mes- sages need be used only infrequently because both A and B can save the other’s public key for future use—a technique known as caching. Periodically, a user should request fresh copies of the public keys of its correspondents to ensure currency. Public-Key Certificates The scenario of Figure 14.11 is attractive, yet it has some drawbacks. The public-key authority could be somewhat of a bottleneck in the system, for a user must appeal to 428 CHAPTER 14 / KEY MANAGEMENT AND DISTRIBUTION the authority for a public key for every other user that it wishes to contact. As before, the directory of names and public keys maintained by the authority is vul- nerable to tampering. An alternative approach, first suggested by Kohnfelder [KOHN78], is to use certificates that can be used by participants to exchange keys without contacting a public-key authority, in a way that is as reliable as if the keys were obtained directly from a public-key authority. In essence, a certificate consists of a public key, an identifier of the key owner, and the whole block signed by a trusted third party. Typically, the third party is a certificate authority, such as a government agency or a financial institution, that is trusted by the user community. A user can present his or her public key to the authority in a secure manner and obtain a cer- tificate. The user can then publish the certificate. Anyone needing this user’s pub- lic key can obtain the certificate and verify that it is valid by way of the attached trusted signature. A participant can also convey its key information to another by transmitting its certificate. Other participants can verify that the certificate was created by the authority. We can place the following requirements on this scheme: 1. Any participant can read a certificate to determine the name and public key of the certificate’s owner. 2. Any participant can verify that the certificate originated from the certificate authority and is not counterfeit. 3. Only the certificate authority can create and update certificates. These requirements are satisfied by the original proposal in [KOHN78]. Denning [DENN83] added the following additional requirement: 4. Any participant can verify the currency of the certificate. A certificate scheme is illustrated in Figure 14.12. Each participant applies to the certificate authority, supplying a public key and requesting a certificate. Certificate Authority PUa PUb CA  E(PRauth, [T1 || IDA || PUa]) CB  E(PRauth, [T2 || IDB || PUb]) (1) CA A B (2) CB Figure 14.12 Exchange of Public-Key Certificates  14.4 / X.509 CERTIFICATES 429 Application must be in person or by some form of secure authenticated communi- cation. For participant A, the authority provides a certificate of the form CA = E(PRauth, [T ƒ ƒ IDA ƒ ƒ PUa]) where PRauth is the private key used by the authority and T is a timestamp. A may then pass this certificate on to any other participant, who reads and verifies the cer- tificate as follows: D(PUauth, CA) = D(PUauth, E(PRauth, [T ƒ ƒ IDA ƒ ƒ PUa])) = (T ƒ ƒ IDA ƒ ƒ PUa) The recipient uses the authority’s public key, PUauth, to decrypt the certifi- cate. Because the certificate is readable only using the authority’s public key, this verifies that the certificate came from the certificate authority. The elements IDA and PUa provide the recipient with the name and public key of the certificate’s holder. The timestamp T validates the currency of the certificate. The timestamp counters the following scenario. A’s private key is learned by an adversary. A gen- erates a new private/public key pair and applies to the certificate authority for a new certificate. Meanwhile, the adversary replays the old certificate to B. If B then encrypts messages using the compromised old public key, the adversary can read those messages. In this context, the compromise of a private key is comparable to the loss of a credit card. The owner cancels the credit card number but is at risk until all possible communicants are aware that the old credit card is obsolete. Thus, the timestamp serves as something like an expiration date. If a certificate is sufficiently old, it is assumed to be expired. One scheme has become universally accepted for formatting public-key cer- tificates: the X.509 standard. X.509 certificates are used in most network security applications, including IP security, transport layer security (TLS), and S/MIME, all of which are discussed in Part Five. X.509 is examined in detail in the next section. 14.4 X.509 CERTIFICATES ITU-T recommendation X.509 is part of the X.500 series of recommendations that define a directory service. The directory is, in effect, a server or distributed set of servers that maintains a database of information about users. The information includes a mapping from user name to network address, as well as other attributes and information about the users. X.509 defines a framework for the provision of authentication services by the X.500 directory to its users. The directory may serve as a repository of public-key certificates of the type discussed in Section 14.3. Each certificate contains the public key of a user and is signed with the private key of a trusted certification authority. In addition, X.509 defines alternative authentication protocols based on the use of public-key certificates. X.509 is an important standard because the certificate structure and authenti- cation protocols defined in X.509 are used in a variety of contexts. For example, the 430 CHAPTER 14 / KEY MANAGEMENT AND DISTRIBUTION X.509 certificate format is used in S/MIME (Chapter 18), IP Security (Chapter 19), and SSL/TLS (Chapter 16). X.509 was initially issued in 1988. The standard was subsequently revised to address some of the security concerns documented in [IANS90] and [MITC90]; a revised recommendation was issued in 1993. A third version was issued in 1995 and revised in 2000. X.509 is based on the use of public-key cryptography and digital signatures. The standard does not dictate the use of a specific algorithm but recommends RSA.The dig- ital signature scheme is assumed to require the use of a hash function. Again, the stan- dard does not dictate a specific hash algorithm. The 1988 recommendation included the description of a recommended hash algorithm; this algorithm has since been shown to be insecure and was dropped from the 1993 recommendation. Figure 14.13 illustrates the generation of a public-key certificate. Certificates The heart of the X.509 scheme is the public-key certificate associated with each user. These user certificates are assumed to be created by some trusted certifica- tion authority (CA) and placed in the directory by the CA or by the user. The directory server itself is not responsible for the creation of public keys or for the certification function; it merely provides an easily accessible location for users to obtain certificates. Figure 14.14a shows the general format of a certificate, which includes the fol- lowing elements. Bob's ID information Unsigned certificate: contains user ID, user's public key Bob's public key H Recipient can verify H CA signature by comparing information hash code values E D Generate hash Signed certificate code of unsigned certificate Encrypt hash code Decrypt signature with CA's private key with CA's public key to form signature to recover hash code Create signed Use certificate to digital certificate verify Bob's public key Figure 14.13 Public-Key Certificate Use  14.4 / X.509 CERTIFICATES 431 Signature Algorithm Version algorithm identifier Parameters Certificate Issuer Name serial number Signature Algorithm algorithm This update date identifier Parameters Version 1 Issuer name Next update date Version 2 Period of Not before Revoked User certificate serial # validity Not after certificate Revocation date Version 3 Subject name Subject's Algorithms public key Parameters info Key Issuer unique Revoked User certificate serial # identifier certificate Revocation date Subject unique Algorithms Signature Parameters identifier Encrypted Extensions versions (b) Certificate revocation list Algorithms Signature All Parameters Encrypted hash (a) X.509 certificate Figure 14.14 X.509 Formats Version: Differentiates among successive versions of the certificate format; the default is version 1. If the issuer unique identifier or subject unique identifier are present, the value must be version 2. If one or more extensions are present, the version must be version 3. Serial number: An integer value unique within the issuing CA that is unam- biguously associated with this certificate. Signature algorithm identifier: The algorithm used to sign the certificate together with any associated parameters. Because this information is repeated in the signature field at the end of the certificate, this field has little, if any, utility. Issuer name: X.500 is the name of the CA that created and signed this certificate. Period of validity: Consists of two dates: the first and last on which the certifi- cate is valid. Subject name: The name of the user to whom this certificate refers. That is, this certificate certifies the public key of the subject who holds the corresponding private key. Subject’s public-key information: The public key of the subject, plus an identi- fier of the algorithm for which this key is to be used, together with any associ- ated parameters. Issuer unique identifier: An optional-bit string field used to identify uniquely the issuing CA in the event the X.500 name has been reused for different entities. 432 CHAPTER 14 / KEY MANAGEMENT AND DISTRIBUTION Subject unique identifier: An optional-bit string field used to identify uniquely the subject in the event the X.500 name has been reused for different entities. Extensions: A set of one or more extension fields. Extensions were added in version 3 and are discussed later in this section. Signature: Covers all of the other fields of the certificate; it contains the hash code of the other fields encrypted with the CA’s private key. This field includes the signature algorithm identifier. The unique identifier fields were added in version 2 to handle the possible reuse of subject and/or issuer names over time. These fields are rarely used. The standard uses the following notation to define a certificate: CA V A W = CA {V, SN, AI, CA, UCA, A, UA, Ap, TA} where YV XW = the certificate of user X issued by certification authority Y Y {I} = the signing of I by Y. It consists of I with an encrypted hash code appended V = version of the certificate SN = serial number of the certificate AI = identifier of the algorithm used to sign the certificate CA = name of certificate authority UCA = optional unique identifier of the CA A = name of user A UA = optional unique identifier of the user A Ap = public key of user A TA = period of validity of the certificate The CA signs the certificate with its private key. If the corresponding public key is known to a user, then that user can verify that a certificate signed by the CA is valid. This is the typical digital signature approach illustrated in Figure 13.2. OBTAINING A USER’S CERTIFICATE User certificates generated by a CA have the following characteristics: Any user with access to the public key of the CA can verify the user public key that was certified. No party other than the certification authority can modify the certificate with- out this being detected. Because certificates are unforgeable, they can be placed in a directory without the need for the directory to make special efforts to protect them. If all users subscribe to the same CA, then there is a common trust of that CA. All user certificates can be placed in the directory for access by all users. In addition, a user can transmit his or her certificate directly to other users. In either case, once B is in possession of A’s certificate, B has confidence that messages it encrypts with A’s public key will be secure from eavesdropping and that messages signed with A’s private key are unforgeable.  14.4