idnits 2.17.1 draft-ietf-secsh-dh-group-exchange-05.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** It looks like you're using RFC 3978 boilerplate. You should update this to the boilerplate described in the IETF Trust License Policy document (see https://trustee.ietf.org/license-info), which is required now. -- Found old boilerplate from RFC 3978, Section 5.1 on line 15. -- Found old boilerplate from RFC 3978, Section 5.5 on line 412. -- Found old boilerplate from RFC 3979, Section 5, paragraph 1 on line 389. -- Found old boilerplate from RFC 3979, Section 5, paragraph 2 on line 396. -- Found old boilerplate from RFC 3979, Section 5, paragraph 3 on line 402. ** This document has an original RFC 3978 Section 5.4 Copyright Line, instead of the newer IETF Trust Copyright according to RFC 4748. ** This document has an original RFC 3978 Section 5.5 Disclaimer, instead of the newer disclaimer which includes the IETF Trust according to RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 155 has weird spacing: '... mpint p, s...' == Line 156 has weird spacing: '... mpint g, g...' == Line 161 has weird spacing: '... mpint e...' == Line 166 has weird spacing: '... string serve...' == Line 167 has weird spacing: '... mpint f...' == (5 more instances...) -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (July 2005) is 6859 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Unused Reference: 'RFC3174' is defined on line 343, but no explicit reference was found in the text == Unused Reference: 'RFC3766' is defined on line 351, but no explicit reference was found in the text -- Possible downref: Non-RFC (?) normative reference: ref. 'FIPS-180-2' ** Downref: Normative reference to an Informational RFC: RFC 3174 Summary: 5 errors (**), 0 flaws (~~), 10 warnings (==), 9 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group M. Friedl 3 Internet-Draft N. Provos 4 Expires: January 2, 2006 W. Simpson 5 July 2005 7 Diffie-Hellman Group Exchange for the SSH Transport Layer Protocol 8 draft-ietf-secsh-dh-group-exchange-05.txt 10 Status of this Memo 12 By submitting this Internet-Draft, each author represents that any 13 applicable patent or other IPR claims of which he or she is aware 14 have been or will be disclosed, and any of which he or she becomes 15 aware will be disclosed, in accordance with Section 6 of BCP 79. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note that 19 other groups may also distribute working documents as Internet- 20 Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at any 24 time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt. 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 This Internet-Draft will expire on January 2, 2006. 35 Copyright Notice 37 Copyright (C) The Internet Society (2005). 39 Abstract 41 This memo describes a new key exchange method for the SSH protocol. 42 It allows the SSH server to propose to the client new groups on which 43 to perform the Diffie-Hellman key exchange. The proposed groups need 44 not be fixed and can change with time. 46 1. Requirements notation 48 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 49 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 50 document are to be interpreted as described in [RFC2119]. 52 2. Overview and Rationale 54 SSH [I-D.ietf-secsh-architecture] is a a very common protocol for 55 secure remote login on the Internet. Currently, SSH performs the 56 initial key exchange using the "diffie-hellman-group1-sha1" method 57 [I-D.ietf-secsh-transport]. This method prescribes a fixed group on 58 which all operations are performed. 60 The Diffie-Hellman key exchange provides a shared secret that can not 61 be determined by either party alone. Furthermore, the shared secret 62 is known only to the participant parties. In SSH, the key exchange 63 is signed with the host key to provide host authentication. 65 The security of the Diffie-Hellman key exchange is based on the 66 difficulty of solving the Discrete Logarithm Problem (DLP). Since we 67 expect that the SSH protocol will be in use for many years in the 68 future, we fear that extensive precomputation and more efficient 69 algorithms to compute the discrete logarithm over a fixed group might 70 pose a security threat to the SSH protocol. 72 The ability to propose new groups will reduce the incentive to use 73 precomputation for more efficient calculation of the discrete 74 logarithm. The server can constantly compute new groups in the 75 background. 77 3. Diffie-Hellman Group and Key Exchange 79 The server keeps a list of safe primes and corresponding generators 80 that it can select from. A prime p is safe, if p = 2q + 1, and q is 81 prime. New primes can be generated in the background. 83 The generator g should be chosen such that the order of the generated 84 subgroup does not factor into small primes, i.e., with p = 2q + 1, 85 the order has to be either q or p - 1. If the order is p - 1, then 86 the exponents generate all possible public values, evenly distributed 87 throughout the range of the modulus p, without cycling through a 88 smaller subset. Such a generator is called a "primitive root" (which 89 is trivial to find when p is "safe"). 91 The client requests a modulus from the server indicating the 92 preferred size. In the following description (C is the client, S is 93 the server; the modulus p is a large safe prime and g is a generator 94 for a subgroup of GF(p); min is the minimal size of p in bits that is 95 acceptable to the client; n is the size of the modulus p in bits that 96 the client would like to receive from the server; max is the maximal 97 size of p in bits that the client can accept; V_S is S's version 98 string; V_C is C's version string; K_S is S's public host key; I_C is 99 C's KEXINIT message and I_S S's KEXINIT message which have been 100 exchanged before this part begins): 102 1. C sends "min || n || max" to S, indicating the minimal acceptable 103 group size, the preferred size of the group and the maximal group 104 size in bits the client will accept. 105 2. S finds a group that best matches the client's request, and sends 106 "p || g" to C. 107 3. C generates a random number x, where 1 < x < (p-1)/2. It 108 computes e = g^x mod p, and sends "e" to S. 109 4. S generates a random number y, where 0 < y < (p-1)/2, and 110 computes f = g^y mod p. S receives "e". It computes K = e^y mod 111 p, H = hash(V_C || V_S || I_C || I_S || K_S || min || n || max || 112 p || g || e || f || K) (these elements are encoded according to 113 their types; see below), and signature s on H with its private 114 host key. S sends "K_S || f || s" to C. The signing operation 115 may involve a second hashing operation. 116 5. C verifies that K_S really is the host key for S (e.g. using 117 certificates or a local database to obtain the public key). C is 118 also allowed to accept the key without verification; however, 119 doing so will render the protocol insecure against active attacks 120 (but may be desirable for practical reasons in the short term in 121 many environments). C then computes K = f^x mod p, H = hash(V_C 122 || V_S || I_C || I_S || K_S || min || n || max || p || g || e || 123 f || K), and verifies the signature s on H. 125 Servers and clients SHOULD support groups with a modulus length of k 126 bits, where 1024 <= k <= 8192. The recommended values for min and 127 max are 1024 and 8192 respectively. 129 Either side MUST NOT send or accept e or f values that are not in the 130 range [1, p-1]. If this condition is violated, the key exchange 131 fails. To prevent confinement attacks, they MUST accept the shared 132 secret K only if 1 < K < p - 1. 134 The server should return the smallest group it knows that is larger 135 than the size the client requested. If the server does not know a 136 group that is larger than the client request, then it SHOULD return 137 the largest group it knows. In all cases, the size of the returned 138 group SHOULD be at least 1024 bits. 140 This is implemented with the following messages. The hash algorithm 141 for computing the exchange hash is defined by the method name, and is 142 called HASH. The public key algorithm for signing is negotiated with 143 the KEXINIT messages. 145 First, the client sends: 147 byte SSH_MSG_KEY_DH_GEX_REQUEST 148 uint32 min, minimal size in bits of an acceptable group 149 uint32 n, preferred size in bits of the group the server will send 150 uint32 max, maximal size in bits of an acceptable group 152 The server responds with 154 byte SSH_MSG_KEX_DH_GEX_GROUP 155 mpint p, safe prime 156 mpint g, generator for subgroup in GF(p) 158 The client responds with: 160 byte SSH_MSG_KEX_DH_GEX_INIT 161 mpint e 163 The server responds with: 165 byte SSH_MSG_KEX_DH_GEX_REPLY 166 string server public host key and certificates (K_S) 167 mpint f 168 string signature of H 170 The hash H is computed as the HASH hash of the concatenation of the 171 following: 173 string V_C, the client's version string (CR and NL excluded) 174 string V_S, the server's version string (CR and NL excluded) 175 string I_C, the payload of the client's SSH_MSG_KEXINIT 176 string I_S, the payload of the server's SSH_MSG_KEXINIT 177 string K_S, the host key 178 uint32 min, minimal size in bits of an acceptable group 179 uint32 n, preferred size in bits of the group the server will send 180 uint32 max, maximal size in bits of an acceptable group 181 mpint p, safe prime 182 mpint g, generator for subgroup 183 mpint e, exchange value sent by the client 184 mpint f, exchange value sent by the server 185 mpint K, the shared secret 187 This value is called the exchange hash, and it is used to 188 authenticate the key exchange as per [I-D.ietf-secsh-transport]. 190 4. Key exchange methods 192 This document defines two new key exchange methods: "diffie-hellman- 193 group-exchange-sha1" and "diffie-hellman-group-exchange-sha256" 195 4.1 diffie-hellman-group-exchange-sha1 197 The "diffie-hellman-group-exchange-sha1" method specifies Diffie- 198 Hellman Group and Key Exchange with SHA-1 [FIPS-180-2] as HASH. 200 4.2 diffie-hellman-group-exchange-sha256 202 The "diffie-hellman-group-exchange-sha256" method specifies Diffie- 203 Hellman Group and Key Exchange with SHA-256 [FIPS-180-2] as HASH. 205 Note that the hash used in key exchange (in this case SHA-256) must 206 also be used in the key derivation PRF, as per the requirement in the 207 "Output from Key Exchange" section in [I-D.ietf-secsh-transport]. 209 5. Summary of message numbers 211 The following message numbers have been defined in this document. 212 They are in a name space private to this document and not assigned by 213 IANA. 215 #define SSH_MSG_KEX_DH_GEX_REQUEST_OLD 30 216 #define SSH_MSG_KEX_DH_GEX_REQUEST 34 217 #define SSH_MSG_KEX_DH_GEX_GROUP 31 218 #define SSH_MSG_KEX_DH_GEX_INIT 32 219 #define SSH_MSG_KEX_DH_GEX_REPLY 33 221 SSH_MSG_KEX_DH_GEX_REQUEST_OLD is used for backwards compatibility. 222 Instead of sending "min || n || max", the client only sends "n". 223 Additionally, the hash is calculated using only "n" instead of "min 224 || n || max". 226 The numbers 30-49 are key exchange specific and may be redefined by 227 other kex methods. 229 6. Implementation Notes 231 6.1 Choice of generator 233 One useful technique is to select the generator, and then limit the 234 modulus selection sieve to primes with that generator: 236 2 when p (mod 24) = 11. 237 5 when p (mod 10) = 3 or 7. 239 It is recommended to use 2 as generator, because it improves 240 efficiency in multiplication performance. It is usable even when it 241 is not a primitive root, as it still covers half of the space of 242 possible residues. 244 6.2 Private exponents 246 To increase the speed of the key exchange, both client and server may 247 reduce the size of their private exponents. It should be at least 248 twice as long as the key material that is generated from the shared 249 secret. For more details see the paper by van Oorschot and Wiener 250 [VAN OORSCHOT]. 252 7. Security Considerations 254 This protocol aims to be simple and uses only well understood 255 primitives. This encourages acceptance by the community and allows 256 for ease of implementation, which hopefully leads to a more secure 257 system. 259 The use of multiple moduli inhibits a determined attacker from 260 precalculating moduli exchange values, and discourages dedication of 261 resources for analysis of any particular modulus. 263 It is important to employ only safe primes as moduli as they allow us 264 to find a generator g so that the order of the generated subgroup 265 does not factor into small primes, i.e., with p = 2q + 1, the order 266 has to be either q or p - 1. If the order is p - 1, then the 267 exponents generate all possible public-values, evenly distributed 268 throughout the range of the modulus p, without cycling through a 269 smaller subset. Van Oorshot and Wiener note that using short private 270 exponents with a random prime modulus p makes the computation of the 271 discrete logarithm easy [VAN OORSCHOT]. However, they also state 272 that this problem does not apply to safe primes. 274 The least significant bit of the private exponent can be recovered, 275 when the modulus is a safe prime [MENEZES]. However, this is not a 276 problem, if the size of the private exponent is big enough. Related 277 to this, Waldvogel and Massey note: When private exponents are chosen 278 independently and uniformly at random from {0,...,p-2}, the key 279 entropy is less than 2 bits away from the maximum, lg(p-1) 280 [WALDVOGEL]. 282 The security considerations in [I-D.ietf-secsh-architecture] also 283 apply to this key exchange method. 285 8. Acknowledgements 287 The document is derived in part from "SSH Transport Layer Protocol" 288 [I-D.ietf-secsh-transport] by T. Ylonen, T. Kivinen, M. Saarinen, T. 290 Rinne and S. Lehtinen. 292 Markku-Juhani Saarinen pointed out that the least significant bit of 293 the private exponent can be recovered efficiently when using safe 294 primes and a subgroup with an order divisible by two. 296 Bodo Moeller suggested that the server send only one group, reducing 297 the complexity of the implementation and the amount of data that 298 needs to be exchanged between client and server. 300 9. Appendix A: Generation of safe primes 302 The Handbook of Applied Cryptography [MENEZES] lists the following 303 algorithm to generate a k-bit safe prime p. It has been modified so 304 that 2 is a generator for the multiplicative group mod p. 306 1. Do the following: 307 1. Select a random (k-1)-bit prime q, so that q mod 12 = 5. 308 2. Compute p := 2q + 1, and test whether p is prime, (using, 309 e.g. trial division and the Rabin-Miller test.) 310 2. Repeat until p is prime. 312 If an implementation uses the OpenSSL libraries, a group consisting 313 of a 1024-bit safe prime and 2 as generator can be created as 314 follows: 316 DH *d = NULL; 317 d = DH_generate_parameters(1024, DH_GENERATOR_2, NULL, NULL); 318 BN_print_fp(stdout, d->p); 320 The order of the subgroup generated by 2 is q = p - 1. 322 10. References 324 10.1 Normative References 326 [FIPS-180-2] 327 National Institute of Standards and Technology (NIST), 328 "Secure Hash Standard (SHS)", FIPS PUB 180-2, August 2002. 330 [I-D.ietf-secsh-architecture] 331 Ylonen, T. and C. Lonvick, "SSH Protocol Architecture", 332 draft-ietf-secsh-architecture-22 (work in progress), 333 March 2005. 335 [I-D.ietf-secsh-transport] 336 Lonvick, C., "SSH Transport Layer Protocol", 337 draft-ietf-secsh-transport-24 (work in progress), 338 March 2005. 340 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 341 Requirement Levels", BCP 14, RFC 2119, March 1997. 343 [RFC3174] Eastlake, D. and P. Jones, "US Secure Hash Algorithm 1 344 (SHA1)", RFC 3174, September 2001. 346 10.2 Informative References 348 [MENEZES] Menezes, A., van Oorschot, P., and S. Vanstone, "Handbook 349 of Applied Cryptography", CRC Press, p. 537, 1996. 351 [RFC3766] Orman, H. and P. Hoffman, "Determining Strengths For 352 Public Keys Used For Exchanging Symmetric Keys", BCP 86, 353 RFC 3766, April 2004. 355 [VAN OORSCHOT] 356 van Oorschot, P. and M. Wiener, "On Diffie-Hellman key 357 agreement with short exponents", Advances in Cryptology - 358 EUROCRYPT'96, LNCS 1070, Springer-Verlag, pp. 332-343, 359 1996. 361 [WALDVOGEL] 362 Waldvogel, C. and J. Massey, "The probability distribution 363 of the Diffie-Hellman key", Proceedings of AUSCRYPT 92, 364 LNCS 718, Springer-Verlag, pp. 492-504, 1993. 366 Authors' Addresses 368 Markus Friedl 370 Email: markus@openbsd.org 372 Niels Provos 374 Email: provos@citi.umich.edu 376 William A. Simpson 378 Email: wsimpson@greendragon.com 380 Intellectual Property Statement 382 The IETF takes no position regarding the validity or scope of any 383 Intellectual Property Rights or other rights that might be claimed to 384 pertain to the implementation or use of the technology described in 385 this document or the extent to which any license under such rights 386 might or might not be available; nor does it represent that it has 387 made any independent effort to identify any such rights. Information 388 on the procedures with respect to rights in RFC documents can be 389 found in BCP 78 and BCP 79. 391 Copies of IPR disclosures made to the IETF Secretariat and any 392 assurances of licenses to be made available, or the result of an 393 attempt made to obtain a general license or permission for the use of 394 such proprietary rights by implementers or users of this 395 specification can be obtained from the IETF on-line IPR repository at 396 http://www.ietf.org/ipr. 398 The IETF invites any interested party to bring to its attention any 399 copyrights, patents or patent applications, or other proprietary 400 rights that may cover technology that may be required to implement 401 this standard. Please address the information to the IETF at 402 ietf-ipr@ietf.org. 404 Disclaimer of Validity 406 This document and the information contained herein are provided on an 407 "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS 408 OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET 409 ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, 410 INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE 411 INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED 412 WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 414 Copyright Statement 416 Copyright (C) The Internet Society (2005). This document is subject 417 to the rights, licenses and restrictions contained in BCP 78, and 418 except as set forth therein, the authors retain all their rights. 420 Acknowledgment 422 Funding for the RFC Editor function is currently provided by the 423 Internet Society.