7 Network Working Group E. Rescorla
8 Request for Comments: 2631 RTFM Inc.
9 Category: Standards Track June 1999
12 Diffie-Hellman Key Agreement Method
16 This document specifies an Internet standards track protocol for the
17 Internet community, and requests discussion and suggestions for
18 improvements. Please refer to the current edition of the "Internet
19 Official Protocol Standards" (STD 1) for the standardization state
20 and status of this protocol. Distribution of this memo is unlimited.
24 Copyright (C) The Internet Society (1999). All Rights Reserved.
28 This document standardizes one particular Diffie-Hellman variant,
29 based on the ANSI X9.42 draft, developed by the ANSI X9F1 working
30 group. Diffie-Hellman is a key agreement algorithm used by two
31 parties to agree on a shared secret. An algorithm for converting the
32 shared secret into an arbitrary amount of keying material is
33 provided. The resulting keying material is used as a symmetric
34 encryption key. The Diffie-Hellman variant described requires the
35 recipient to have a certificate, but the originator may have a static
36 key pair (with the public key placed in a certificate) or an
41 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . 2
42 1.1. Requirements Terminology . . . . . . . . . . . . . . . . 2
43 2. Overview Of Method . . . . . . . . . . . . . . . . . . . . 2
44 2.1. Key Agreement . . . . . . . . . . . . . . . . . . . . . . 2
45 2.1.1. Generation of ZZ . . . . . . . . . . . . . . . . . . . 3
46 2.1.2. Generation of Keying Material . . . . . . . . . . . . . 3
47 2.1.3. KEK Computation . . . . . . . . . . . . . . . . . . . . 4
48 2.1.4. Keylengths for common algorithms . . . . . . . . . . . 5
49 2.1.5. Public Key Validation . . . . . . . . . . . . . . . . . 5
50 2.1.6. Example 1 . . . . . . . . . . . . . . . . . . . . . . . 5
51 2.1.7. Example 2 . . . . . . . . . . . . . . . . . . . . . . . 6
52 2.2. Key and Parameter Requirements . . . . . . . . . . . . . 7
53 2.2.1. Group Parameter Generation . . . . . . . . . . . . . . 7
54 2.2.1.1. Generation of p, q . . . . . . . . . . . . . . . . . 8
58 Rescorla Standards Track [Page 1]
60 RFC 2631 Diffie-Hellman Key Agreement Method June 1999
63 2.2.1.2. Generation of g . . . . . . . . . . . . . . . . . . . 9
64 2.2.2. Group Parameter Validation . . . . . . . . . . . . . . 9
65 2.3. Ephemeral-Static Mode . . . . . . . . . . . . . . . . . . 10
66 2.4. Static-Static Mode . . . . . . . . . . . . . . . . . . . 10
67 2.4. Acknowledgements . . . . . . . . . . . . . . . . . . . . 10
68 2.4. References . . . . . . . . . . . . . . . . . . . . . . . 11
69 Security Considerations . . . . . . . . . . . . . . . . . . . 12
70 Author's Address . . . . . . . . . . . . . . . . . . . . . . . 12
71 Full Copyright Statement . . . . . . . . . . . . . . . . . . . 13
75 In [DH76] Diffie and Hellman describe a means for two parties to
76 agree upon a shared secret in such a way that the secret will be
77 unavailable to eavesdroppers. This secret may then be converted into
78 cryptographic keying material for other (symmetric) algorithms. A
79 large number of minor variants of this process exist. This document
80 describes one such variant, based on the ANSI X9.42 specification.
82 1.1. Requirements Terminology
84 Keywords "MUST", "MUST NOT", "REQUIRED", "SHOULD", "SHOULD NOT" and
85 "MAY" that appear in this document are to be interpreted as described
90 Diffie-Hellman key agreement requires that both the sender and
91 recipient of a message have key pairs. By combining one's private key
92 and the other party's public key, both parties can compute the same
93 shared secret number. This number can then be converted into
94 cryptographic keying material. That keying material is typically
95 used as a key-encryption key (KEK) to encrypt (wrap) a content-
96 encryption key (CEK) which is in turn used to encrypt the message
101 The first stage of the key agreement process is to compute a shared
102 secret number, called ZZ. When the same originator and recipient
103 public/private key pairs are used, the same ZZ value will result.
104 The ZZ value is then converted into a shared symmetric cryptographic
105 key. When the originator employs a static private/public key pair,
106 the introduction of a public random value ensures that the resulting
107 symmetric key will be different for each key agreement.
114 Rescorla Standards Track [Page 2]
116 RFC 2631 Diffie-Hellman Key Agreement Method June 1999
119 2.1.1. Generation of ZZ
121 X9.42 defines that the shared secret ZZ is generated as follows:
123 ZZ = g ^ (xb * xa) mod p
125 Note that the individual parties actually perform the computations:
127 ZZ = (yb ^ xa) mod p = (ya ^ xb) mod p
129 where ^ denotes exponentiation
131 ya is party a's public key; ya = g ^ xa mod p
132 yb is party b's public key; yb = g ^ xb mod p
133 xa is party a's private key
134 xb is party b's private key
137 g = h^{(p-1)/q} mod p, where
138 h is any integer with 1 < h < p-1 such that h{(p-1)/q} mod p > 1
139 (g has order q mod p; i.e. g^q mod p = 1 if g!=1)
140 j a large integer such that p=qj + 1
141 (See Section 2.2 for criteria for keys and parameters)
143 In [CMS], the recipient's key is identified by the CMS
144 RecipientIdentifier, which points to the recipient's certificate.
145 The sender's public key is identified using the
146 OriginatorIdentifierOrKey field, either by reference to the sender's
147 certificate or by inline inclusion of a public key.
149 2.1.2. Generation of Keying Material
151 X9.42 provides an algorithm for generating an essentially arbitrary
152 amount of keying material from ZZ. Our algorithm is derived from that
153 algorithm by mandating some optional fields and omitting others.
155 KM = H ( ZZ || OtherInfo)
157 H is the message digest function SHA-1 [FIPS-180] ZZ is the shared
158 secret value computed in Section 2.1.1. Leading zeros MUST be
159 preserved, so that ZZ occupies as many octets as p. For instance, if
160 p is 1024 bits, ZZ should be 128 bytes long. OtherInfo is the DER
161 encoding of the following structure:
163 OtherInfo ::= SEQUENCE {
164 keyInfo KeySpecificInfo,
165 partyAInfo [0] OCTET STRING OPTIONAL,
166 suppPubInfo [2] OCTET STRING
170 Rescorla Standards Track [Page 3]
172 RFC 2631 Diffie-Hellman Key Agreement Method June 1999
177 KeySpecificInfo ::= SEQUENCE {
178 algorithm OBJECT IDENTIFIER,
179 counter OCTET STRING SIZE (4..4) }
181 Note that these ASN.1 definitions use EXPLICIT tagging. (In ASN.1,
182 EXPLICIT tagging is implicit unless IMPLICIT is explicitly
185 algorithm is the ASN.1 algorithm OID of the CEK wrapping algorithm
186 with which this KEK will be used. Note that this is NOT an
187 AlgorithmIdentifier, but simply the OBJECT IDENTIFIER. No
190 counter is a 32 bit number, represented in network byte order. Its
191 initial value is 1 for any ZZ, i.e. the byte sequence 00 00 00 01
192 (hex), and it is incremented by one every time the above key
193 generation function is run for a given KEK.
195 partyAInfo is a random string provided by the sender. In CMS, it is
196 provided as a parameter in the UserKeyingMaterial field (encoded as
197 an OCTET STRING). If provided, partyAInfo MUST contain 512 bits.
199 suppPubInfo is the length of the generated KEK, in bits, represented
200 as a 32 bit number in network byte order. E.g. for 3DES it would be
201 the byte sequence 00 00 00 C0.
203 To generate a KEK, one generates one or more KM blocks (incrementing
204 counter appropriately) until enough material has been generated. The
205 KM blocks are concatenated left to right I.e. KM(counter=1) ||
208 Note that the only source of secret entropy in this computation is
209 ZZ. Even if a string longer than ZZ is generated, the effective key
210 space of the KEK is limited by the size of ZZ, in addition to any
211 security level considerations imposed by the parameters p and q.
212 However, if partyAInfo is different for each message, a different KEK
213 will be generated for each message. Note that partyAInfo MUST be used
214 in Static-Static mode, but MAY appear in Ephemeral-Static mode.
216 2.1.3. KEK Computation
218 Each key encryption algorithm requires a specific size key (n). The
219 KEK is generated by mapping the left n-most bytes of KM onto the key.
220 For 3DES, which requires 192 bits of keying material, the algorithm
221 must be run twice, once with a counter value of 1 (to generate K1',
222 K2', and the first 32 bits of K3') and once with a counter value of 2
226 Rescorla Standards Track [Page 4]
228 RFC 2631 Diffie-Hellman Key Agreement Method June 1999
231 (to generate the last 32 bits of K3). K1',K2' and K3' are then parity
232 adjusted to generate the 3 DES keys K1,K2 and K3. For RC2-128, which
233 requires 128 bits of keying material, the algorithm is run once, with
234 a counter value of 1, and the left-most 128 bits are directly
235 converted to an RC2 key. Similarly, for RC2-40, which requires 40
236 bits of keying material, the algorithm is run once, with a counter
237 value of 1, and the leftmost 40 bits are used as the key.
239 2.1.4. Keylengths for common algorithms
241 Some common key encryption algorithms have KEKs of the following
248 RC2 effective key lengths are equal to RC2 real key lengths.
250 2.1.5. Public Key Validation
252 The following algorithm MAY be used to validate a received public key
255 1. Verify that y lies within the interval [2,p-1]. If it does not,
257 2. Compute y^q mod p. If the result == 1, the key is valid.
258 Otherwise the key is invalid.
260 The primary purpose of public key validation is to prevent a small
261 subgroup attack [LAW98] on the sender's key pair. If Ephemeral-Static
262 mode is used, this check may not be necessary. See also [P1363] for
263 more information on Public Key validation.
265 Note that this procedure may be subject to pending patents.
269 ZZ is the 20 bytes 00 01 02 03 04 05 06 07 08 09
270 0a 0b 0c 0d 0e 0f 10 11 12 13
272 The key wrap algorithm is 3DES-EDE wrap.
274 No partyAInfo is used.
276 Consequently, the input to the first invocation of SHA-1 is:
278 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 ; ZZ
282 Rescorla Standards Track [Page 5]
284 RFC 2631 Diffie-Hellman Key Agreement Method June 1999
289 06 0b 2a 86 48 86 f7 0d 01 09 10 03 06 ; 3DES wrap OID
291 00 00 00 01 ; Counter
294 00 00 00 c0 ; key length
296 And the output is the 20 bytes:
298 a0 96 61 39 23 76 f7 04 4d 90 52 a3 97 88 32 46 b6 7f 5f 1e
300 The input to the second invocation of SHA-1 is:
302 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 ; ZZ
305 06 0b 2a 86 48 86 f7 0d 01 09 10 03 06 ; 3DES wrap OID
307 00 00 00 02 ; Counter
310 00 00 00 c0 ; key length
312 And the output is the 20 bytes:
314 f6 3e b5 fb 5f 56 d9 b6 a8 34 03 91 c2 d3 45 34 93 2e 11 30
317 K1'=a0 96 61 39 23 76 f7 04
318 K2'=4d 90 52 a3 97 88 32 46
319 K3'=b6 7f 5f 1e f6 3e b5 fb
321 Note: These keys are not parity adjusted
325 ZZ is the 20 bytes 00 01 02 03 04 05 06 07 08 09
326 0a 0b 0c 0d 0e 0f 10 11 12 13
328 The key wrap algorithm is RC2-128 key wrap, so we need 128 bits (16
329 bytes) of keying material.
331 The partyAInfo used is the 64 bytes
333 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01
334 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01
338 Rescorla Standards Track [Page 6]
340 RFC 2631 Diffie-Hellman Key Agreement Method June 1999
343 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01
344 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01
346 Consequently, the input to SHA-1 is:
348 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 11 12 13 ; ZZ
351 06 0b 2a 86 48 86 f7 0d 01 09 10 03 07 ; RC2 wrap OID
353 00 00 00 01 ; Counter
356 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01 ; partyAInfo
357 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01
358 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01
359 01 23 45 67 89 ab cd ef fe dc ba 98 76 54 32 01
362 00 00 00 80 ; key length
364 And the output is the 20 bytes:
366 48 95 0c 46 e0 53 00 75 40 3c ce 72 88 96 04 e0 3e 7b 5d e9
369 K=48 95 0c 46 e0 53 00 75 40 3c ce 72 88 96 04 e0
371 2.2. Key and Parameter Requirements
373 X9.42 requires that the group parameters be of the form p=jq + 1
374 where q is a large prime of length m and j>=2. An algorithm for
375 generating primes of this form (derived from the algorithms in FIPS
376 PUB 186-1[FIPS-186] and [X942]can be found in appendix A.
378 X9.42 requires that the private key x be in the interval [2, (q -
379 2)]. x should be randomly generated in this interval. y is then
380 computed by calculating g^x mod p. To comply with this memo, m MUST
381 be >=160 bits in length, (consequently, q MUST be at least 160 bits
382 long). When symmetric ciphers stronger than DES are to be used, a
383 larger m may be advisable. p must be a minimum of 512 bits long.
385 2.2.1. Group Parameter Generation
387 Agents SHOULD generate domain parameters (g,p,q) using the following
388 algorithm, derived from [FIPS-186] and [X942]. When this algorithm is
389 used, the correctness of the generation procedure can be verified by
390 a third party by the algorithm of 2.2.2.
394 Rescorla Standards Track [Page 7]
396 RFC 2631 Diffie-Hellman Key Agreement Method June 1999
399 2.2.1.1. Generation of p, q
401 This algorithm generates a p, q pair where q is of length m and p is
404 1. Set m' = m/160 where / represents integer division with rounding
405 upwards. I.e. 200/160 = 2.
411 4. Select an arbitrary bit string SEED such that the length of SEED
416 6. For i = 0 to m' - 1
418 U = U + (SHA1[SEED + i] XOR SHA1[(SEED + m' + i)) * 2^(160 * i)
420 Note that for m=160, this reduces to the algorithm of [FIPS-186]
422 U = SHA1[SEED] XOR SHA1[(SEED+1) mod 2^160 ].
424 5. Form q from U by computing U mod (2^m) and setting the most
425 significant bit (the 2^(m-1) bit) and the least significant bit to
426 1. In terms of boolean operations, q = U OR 2^(m-1) OR 1. Note
427 that 2^(m-1) < q < 2^m
429 6. Use a robust primality algorithm to test whether q is prime.
431 7. If q is not prime then go to 4.
435 9. Set R = seed + 2*m' + (L' * counter)
439 12. For i = 0 to L'-1 do
441 V = V + SHA1(R + i) * 2^(160 * i)
443 13. Set W = V mod 2^L
445 14. Set X = W OR 2^(L-1)
450 Rescorla Standards Track [Page 8]
452 RFC 2631 Diffie-Hellman Key Agreement Method June 1999
455 Note that 0 <= W < 2^(L-1) and hence X >= 2^(L-1)
457 15. Set p = X - (X mod (2*q)) + 1
459 6. If p > 2^(L-1) use a robust primality test to test whether p is
460 prime. Else go to 18.
462 17. If p is prime output p, q, seed, counter and stop.
464 18. Set counter = counter + 1
466 19. If counter < (4096 * N) then go to 8.
470 Note: A robust primality test is one where the probability of a non-
471 prime number passing the test is at most 2^-80. [FIPS-186] provides a
472 suitable algorithm, as does [X942].
474 2.2.1.2. Generation of g
476 This section gives an algorithm (derived from [FIPS-186]) for
479 1. Let j = (p - 1)/q.
481 2. Set h = any integer, where 1 < h < p - 1 and h differs
482 from any value previously tried.
486 4. If g = 1 go to step 2
488 2.2.2. Group Parameter Validation
490 The ASN.1 for DH keys in [PKIX] includes elements j and validation-
491 Parms which MAY be used by recipients of a key to verify that the
492 group parameters were correctly generated. Two checks are possible:
494 1. Verify that p=qj + 1. This demonstrates that the parameters meet
495 the X9.42 parameter criteria.
496 2. Verify that when the p,q generation procedure of [FIPS-186]
497 Appendix 2 is followed with seed 'seed', that p is found when
498 'counter' = pgenCounter.
500 This demonstrates that the parameters were randomly chosen and
501 do not have a special form.
506 Rescorla Standards Track [Page 9]
508 RFC 2631 Diffie-Hellman Key Agreement Method June 1999
511 Whether agents provide validation information in their certificates
512 is a local matter between the agents and their CA.
514 2.3. Ephemeral-Static Mode
516 In Ephemeral-Static mode, the recipient has a static (and certified)
517 key pair, but the sender generates a new key pair for each message
518 and sends it using the originatorKey production. If the sender's key
519 is freshly generated for each message, the shared secret ZZ will be
520 similarly different for each message and partyAInfo MAY be omitted,
521 since it serves merely to decouple multiple KEKs generated by the
522 same set of pairwise keys. If, however, the same ephemeral sender key
523 is used for multiple messages (e.g. it is cached as a performance
524 optimization) then a separate partyAInfo MUST be used for each
525 message. All implementations of this standard MUST implement
526 Ephemeral-Static mode.
528 In order to resist small subgroup attacks, the recipient SHOULD
529 perform the check described in 2.1.5. If an opponent cannot determine
530 success or failure of a decryption operation by the recipient, the
531 recipient MAY choose to omit this check. See also [LL97] for a method
532 of generating keys which are not subject to small subgroup attack.
534 2.4. Static-Static Mode
536 In Static-Static mode, both the sender and the recipient have a
537 static (and certified) key pair. Since the sender's and recipient's
538 keys are therefore the same for each message, ZZ will be the same for
539 each message. Thus, partyAInfo MUST be used (and different for each
540 message) in order to ensure that different messages use different
541 KEKs. Implementations MAY implement Static-Static mode.
543 In order to prevent small subgroup attacks, both originator and
544 recipient SHOULD either perform the validation step described in
545 Section 2.1.5 or verify that the CA has properly verified the
546 validity of the key. See also [LL97] for a method of generating keys
547 which are not subject to small subgroup attack.
551 The Key Agreement method described in this document is based on work
552 done by the ANSI X9F1 working group. The author wishes to extend his
553 thanks for their assistance.
555 The author also wishes to thank Stephen Henson, Paul Hoffman, Russ
556 Housley, Burt Kaliski, Brian Korver, John Linn, Jim Schaad, Mark
557 Schertler, Peter Yee, and Robert Zuccherato for their expert advice
562 Rescorla Standards Track [Page 10]
564 RFC 2631 Diffie-Hellman Key Agreement Method June 1999
569 [CMS] Housley, R., "Cryptographic Message Syntax", RFC 2630,
572 [FIPS-46-1] Federal Information Processing Standards Publication
573 (FIPS PUB) 46-1, Data Encryption Standard, Reaffirmed
574 1988 January 22 (supersedes FIPS PUB 46, 1977 January
577 [FIPS-81] Federal Information Processing Standards Publication
578 (FIPS PUB) 81, DES Modes of Operation, 1980 December 2.
580 [FIPS-180] Federal Information Processing Standards Publication
581 (FIPS PUB) 180-1, "Secure Hash Standard", 1995 April 17.
583 [FIPS-186] Federal Information Processing Standards Publication
584 (FIPS PUB) 186, "Digital Signature Standard", 1994 May
587 [P1363] "Standard Specifications for Public Key Cryptography",
588 IEEE P1363 working group draft, 1998, Annex D.
590 [PKIX] Housley, R., Ford, W., Polk, W. and D. Solo, "Internet
591 X.509 Public Key Infrastructure Certificate and CRL
592 Profile", RFC 2459, January 1999.
594 [LAW98] L. Law, A. Menezes, M. Qu, J. Solinas and S. Vanstone,
595 "An efficient protocol for authenticated key agreement",
596 Technical report CORR 98-05, University of Waterloo,
599 [LL97] C.H. Lim and P.J. Lee, "A key recovery attack on discrete
600 log-based schemes using a prime order subgroup", B.S.
601 Kaliski, Jr., editor, Advances in Cryptology - Crypto
602 '97, Lecture Notes in Computer Science, vol. 1295, 1997,
603 Springer-Verlag, pp. 249-263.
605 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
606 Requirement Levels", BCP 14, RFC 2119, March 1997.
608 [X942] "Agreement Of Symmetric Keys Using Diffie-Hellman and MQV
609 Algorithms", ANSI draft, 1998.
618 Rescorla Standards Track [Page 11]
620 RFC 2631 Diffie-Hellman Key Agreement Method June 1999
623 Security Considerations
625 All the security in this system is provided by the secrecy of the
626 private keying material. If either sender or recipient private keys
627 are disclosed, all messages sent or received using that key are
628 compromised. Similarly, loss of the private key results in an
629 inability to read messages sent using that key.
631 Static Diffie-Hellman keys are vulnerable to a small subgroup attack
632 [LAW98]. In practice, this issue arises for both sides in Static-
633 Static mode and for the receiver during Ephemeral-Static mode.
634 Sections 2.3 and 2.4 describe appropriate practices to protect
635 against this attack. Alternatively, it is possible to generate keys
636 in such a fashion that they are resistant to this attack. See [LL97]
638 The security level provided by these methods depends on several
639 factors. It depends on the length of the symmetric key (typically, a
640 2^l security level if the length is l bits); the size of the prime q
641 (a 2^{m/2} security level); and the size of the prime p (where the
642 security level grows as a subexponential function of the size in
643 bits). A good design principle is to have a balanced system, where
644 all three security levels are approximately the same. If many keys
645 are derived from a given pair of primes p and q, it may be prudent to
646 have higher levels for the primes. In any case, the overall security
647 is limited by the lowest of the three levels.
654 East Palo Alto, CA 94303
674 Rescorla Standards Track [Page 12]
676 RFC 2631 Diffie-Hellman Key Agreement Method June 1999
679 Full Copyright Statement
681 Copyright (C) The Internet Society (1999). All Rights Reserved.
683 This document and translations of it may be copied and furnished to
684 others, and derivative works that comment on or otherwise explain it
685 or assist in its implementation may be prepared, copied, published
686 and distributed, in whole or in part, without restriction of any
687 kind, provided that the above copyright notice and this paragraph are
688 included on all such copies and derivative works. However, this
689 document itself may not be modified in any way, such as by removing
690 the copyright notice or references to the Internet Society or other
691 Internet organizations, except as needed for the purpose of
692 developing Internet standards in which case the procedures for
693 copyrights defined in the Internet Standards process must be
694 followed, or as required to translate it into languages other than
697 The limited permissions granted above are perpetual and will not be
698 revoked by the Internet Society or its successors or assigns.
700 This document and the information contained herein is provided on an
701 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
702 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
703 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
704 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
705 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
710 Funding for the RFC Editor function is currently provided by the
730 Rescorla Standards Track [Page 13]