idnits 2.17.1 draft-ietf-secsh-dh-group-exchange-01.txt: ** The Abstract section seems to be numbered Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. ** The document seems to lack a 1id_guidelines paragraph about 6 months document validity -- however, there's a paragraph with a matching beginning. Boilerplate error? == 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 Introduction section. ** 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.) ** There are 3 instances of too long lines in the document, the longest one being 6 characters in excess of 72. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 142: '...vers and clients SHOULD support groups...' RFC 2119 keyword, line 146: '... Either side MUST NOT send or acce...' RFC 2119 keyword, line 148: '...prevent confinement attacks, they MUST...' RFC 2119 keyword, line 153: '... client request, then it SHOULD return...' RFC 2119 keyword, line 155: '... group SHOULD be at least 1024 bit...' Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 179 has weird spacing: '... string ser...' == Line 181 has weird spacing: '... string sig...' -- 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 (April 2001) is 8410 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) -- Missing reference section? '4' on line 275 looks like a reference -- Missing reference section? '5' on line 278 looks like a reference -- Missing reference section? '6' on line 281 looks like a reference -- Missing reference section? '7' on line 284 looks like a reference -- Missing reference section? '1' on line 264 looks like a reference -- Missing reference section? '2' on line 289 looks like a reference -- Missing reference section? '3' on line 271 looks like a reference Summary: 8 errors (**), 0 flaws (~~), 3 warnings (==), 10 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group Markus Friedl 3 INTERNET-DRAFT Niels Provos 4 Expires in six months William A. Simpson 5 April 2001 7 Diffie-Hellman Group Exchange for the SSH Transport Layer Protocol 8 draft-ietf-secsh-dh-group-exchange-01.txt 10 1. Status of this Memo 12 This document is an Internet-Draft and is in full conformance with 13 all provisions of Section 10 of RFC2026. 15 Internet-Drafts are working documents of the Internet Engineering 16 Task Force (IETF), its areas, and its working groups. Note that 17 other groups may also distribute working documents as Internet- 18 Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six 21 months and may be updated, replaced, or obsoleted by other docu- 22 ments at any time. It is inappropriate to use Internet- Drafts as 23 reference material or to cite them other than as "work in 24 progress." 26 The list of current Internet-Drafts can be accessed at 27 http://www.ietf.org/ietf/1id-abstracts.txt 29 The list of Internet-Draft Shadow Directories can be accessed at 30 http://www.ietf.org/shadow.html. 32 2. Copyright Notice 34 Copyright (C) 2000 by Markus Friedl, Niels Provos and William A. 35 Simpson. 37 3. Abstract 39 This memo describes a new key exchange method for the SSH protocol. 40 It allows the SSH server to propose to the client new groups on 41 which to perform the Diffie-Hellman key exchange. The proposed 42 groups need not be fixed and can change with time. 44 4. Overview and Rational 46 SSH [4,5,6,7] is a a very common protocol for secure remote login 47 on the Internet. Currently, SSH performs the initial key exchange 48 using the "diffie-hellman-group1-sha1" method. This method pre- 49 scribes a fixed group on which all operations are performed. 51 The Diffie-Hellman key exchange provides a shared secret that can 52 not be determined by either party alone. In SSH, the key exchange 53 is signed with the host key to provide host authentication. 55 The security of the Diffie-Hellman key exchange is based on the 56 difficulty of solving the Discrete Logarithm Problem (DLP). Since 57 we expect that the SSH protocol will be in use for many years in 58 the future, we fear that extensive precomputation and more effi- 59 cient algorithms to compute the discrete logarithm over a fixed 60 group might pose a security threat to the SSH protocol. 62 The ability to propose new groups will reduce the incentive to use 63 precomputation for more efficient calculation of the discrete loga- 64 rithm. The server can constantly compute new groups in the back- 65 ground. 67 5. Diffie-Hellman Group and Key Exchange 69 The server keeps a list of safe primes and corresponding generators 70 that it can select from. A prime p is safe, if p = 2q + 1, and q 71 is prime. New primes can be generated in the background. 73 The generator g should be chosen such that the order of the gener- 74 ated subgroup does not factor into small primes, i.e., with p = 2q 75 + 1, the order has to be either q or p - 1. If the order is p - 1, 76 then the exponents generate all possible public-values, evenly dis- 77 tributed throughout the range of the modulus p, without cycling 78 through a smaller subset. Such a generator is called a "primitive 79 root" (which is trivial to find when p is "safe"). 81 Implementation Notes: 83 One useful technique is to select the generator, and then 84 limit the modulus selection sieve to primes with that genera- 85 tor: 87 2 when p (mod 24) = 11. 88 5 when p (mod 10) = 3 or 7. 90 It is recommended to use 2 as generator, because it improves 91 efficiency in multiplication performance. It is usable even 92 when it is not a primitive root, as it still covers half of 93 the space of possible residues. 95 The client requests a modulus from the server indicating the pre- 96 ferred size. In the following description (C is the client, S is 97 the server; the modulus p is a large safe prime and g is a genera- 98 tor for a subgroup of GF(p); min is the minimal size of p in bits 99 that is acceptable to the client; n is the size of the modulus p in 100 bits that the client would like to receive from the server; max is 101 the maximal size of p in bits that the client can accept; V_S is 102 S's version string; V_C is C's version string; K_S is S's public 103 host key; I_C is C's KEXINIT message and I_S S's KEXINIT message 104 which have been exchanged before this part begins): 106 1. C sends "min || n || max" to S, indicating the minimal accept- 107 able group size, the preferred size of the group and the maxi- 108 mal group size in bits the client will accept. 110 2. S finds a group that best matches the client's request, and 111 sends "p || g" to C. 113 3. C generates a random number x (1 < x < (p-1)/2). It computes e 114 = g^x mod p, and sends "e" to S. 116 4. S generates a random number y (0 < y < (p-1)/2) and computes f 117 = g^y mod p. S receives "e". It computes K = e^y mod p, H = 118 hash(V_C || V_S || I_C || I_S || K_S || min || n || max || p 119 || g || e || f || K) (these elements are encoded according to 120 their types; see below), and signature s on H with its private 121 host key. S sends "K_S || f || s" to C. The signing opera- 122 tion may involve a second hashing operation. 124 Implementation Notes: 126 To increase the speed of the key exchange, both client 127 and server may reduce the size of their private expo- 128 nents. It should be at least twice as long as the key 129 material that is generated from the shared secret. For 130 more details see the paper by van Oorschot and Wiener 131 [1]. 133 5. C verifies that K_S really is the host key for S (e.g. using 134 certificates or a local database). C is also allowed to 135 accept the key without verification; however, doing so will 136 render the protocol insecure against active attacks (but may 137 be desirable for practical reasons in the short term in many 138 environments). C then computes K = f^x mod p, H = hash(V_C || 139 V_S || I_C || I_S || K_S || min || n || max || p || g || e || 140 f || K), and verifies the signature s on H. 142 Servers and clients SHOULD support groups with a modulus 143 length of k bits, where 1024 <= k <= 8192. The recommended 144 values for min and max are 1024 and 8192 respectively. 146 Either side MUST NOT send or accept e or f values that are not 147 in the range [1, p-1]. If this condition is violated, the key 148 exchange fails. To prevent confinement attacks, they MUST 149 accept the shared secret K only if 1 < K < p - 1. 151 The server should return the smallest group it knows that is larger 152 than the size the client requested. If the server does not know a 153 group that is larger than the client request, then it SHOULD return 154 the largest group it knows. In all cases, the size of the returned 155 group SHOULD be at least 1024 bits. 157 This is implemented with the following messages. The hash algo- 158 rithm for computing the exchange hash is defined by the method 159 name, and is called HASH. The public key algorithm for signing is 160 negotiated with the KEXINIT messages. 162 First, the client sends: 163 byte SSH_MSG_KEY_DH_GEX_REQUEST 164 uint32 min, minimal size in bits of an acceptable group 165 uint32 n, preferred size in bits of the group the server should send 166 uint32 max, maximal size in bits of an acceptable group 168 The server responds with 169 byte SSH_MSG_KEX_DH_GEX_GROUP 170 mpint p, safe prime 171 mpint g, generator for subgroup in GF(p) 173 The client responds with: 174 byte SSH_MSG_KEX_DH_GEX_INIT 175 mpint e 177 The server responds with: 178 byte SSH_MSG_KEX_DH_GEX_REPLY 179 string server public host key and certificates (K_S) 180 mpint f 181 string signature of H 183 The hash H is computed as the HASH hash of the concatenation of the 184 following: 185 string V_C, the client's version string (CR and NL excluded) 186 string V_S, the server's version string (CR and NL excluded) 187 string I_C, the payload of the client's SSH_MSG_KEXINIT 188 string I_S, the payload of the server's SSH_MSG_KEXINIT 189 string K_S, the host key 190 uint32 min, minimal size in bits of an acceptable group 191 uint32 n, preferred size in bits of the group the server should send 192 uint32 max, maximal size in bits of an acceptable group 193 mpint p, safe prime 194 mpint g, generator for subgroup 195 mpint e, exchange value sent by the client 196 mpint f, exchange value sent by the server 197 mpint K, the shared secret 199 This value is called the exchange hash, and it is used to authenti- 200 cate the key exchange. 202 6. diffie-hellman-group-exchange-sha1 204 The "diffie-hellman-group-exchange-sha1" method specifies Diffie- 205 Hellman Group and Key Exchange with SHA-1 as HASH. 207 7. Summary of Message numbers 209 The following message numbers have been defined in this document. 211 #define SSH_MSG_KEX_DH_GEX_REQUEST_OLD 30 212 #define SSH_MSG_KEX_DH_GEX_REQUEST 34 213 #define SSH_MSG_KEX_DH_GEX_GROUP 31 214 #define SSH_MSG_KEX_DH_GEX_INIT 32 215 #define SSH_MSG_KEX_DH_GEX_REPLY 33 217 SSH_MSG_KEX_DH_GEX_REQUEST_OLD is used for backwards compatibility. 218 Instead of sending "min || n || max", the client only sends "n". 219 Additionally, the hash is calculated using only "n" instead of "min 220 || n || max". 222 The numbers 30-49 are key exchange specific and may be redefined by 223 other kex methods. 225 8. Security Considerations 227 This protocol aims to be simple and uses only well understood prim- 228 itives. This encourages acceptance by the community and allows for 229 ease of implementation, which hopefully leads to a more secure sys- 230 tem. 232 The use of multiple moduli inhibits a determined attacker from pre- 233 calculating moduli exchange values, and discourages dedication of 234 resources for analysis of any particular modulus. 236 It is important to employ only safe primes as moduli. Van Oorshot 237 and Wiener note that using short private exponents with a random 238 prime modulus p makes the computation of the discrete logarithm 239 easy [1]. However, they also state that this problem does not 240 apply to safe primes. 242 The least significant bit of the private exponent can be recovered, 243 when the modulus is a safe prime [2]. However, this is not a prob- 244 lem, if the size of the private exponent is big enough. Related to 245 this, Waldvogel and Massey note: When private exponents are chosen 246 independently and uniformly at random from {0,...,p-2}, the key 247 entropy is less than 2 bits away from the maximum, lg(p-1) [3]. 249 9. Acknowledgments 251 The document is derived in part from "SSH Transport Layer Protocol" 252 by T. Ylonen, T. Kivinen, M. Saarinen, T. Rinne and S. Lehtinen. 254 Markku-Juhani Saarinen pointed out that the least significant bit 255 of the private exponent can be recovered efficiently when using 256 safe primes and a subgroup with an order divisible by two. 258 Bodo Moeller suggested that the server send only one group, reduc- 259 ing the complexity of the implementation and the amount of data 260 that needs to be exchanged between client and server. 262 10. Bibliography 264 [1] P. C. van Oorschot and M. J. Wiener, On Diffie-Hellman key 265 agreement with short exponents, In Advances in Cryptology - 266 EUROCRYPT'96, LNCS 1070, Springer-Verlag, 1996, pp.332-343. 268 [2] Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Van- 269 stone. Handbook of Applied Cryptography. CRC Press, 1996. 271 [3] C. P. Waldvogel and J. L. Massey, The probability distribution 272 of the Diffie-Hellman key, in Proceedings of AUSCRYPT 92, LNCS 273 718, Springer- Verlag, 1993, pp. 492-504. 275 [4] Ylonen, T., et al: "SSH Protocol Architecture", Internet- 276 Draft, draft-secsh-architecture-07.txt 278 [5] Ylonen, T., et al: "SSH Transport Layer Protocol", Internet- 279 Draft, draft-ietf-secsh-transport-09.txt 281 [6] Ylonen, T., et al: "SSH Authentication Protocol", Internet- 282 Draft, draft-ietf-secsh-userauth-09.txt 284 [7] Ylonen, T., et al: "SSH Connection Protocol", Internet-Draft, 285 draft-ietf-secsh-connect-09.txt 287 11. Appendix A: Generation of safe primes 289 The Handbook of Applied Cryptography [2] lists the following algo- 290 rithm to generate a k-bit safe prime p. It has been modified so 291 that 2 is a generator for the multiplicative group mod p. 293 1. Do the following: 294 1.1 Select a random (k-1)-bit prime q, so that q mod 12 = 5. 295 1.2 Compute p := 2q + 1, and test whether p is prime, (using, e.g. 296 trial division and the Rabin-Miller test.) 297 Repeat until p is prime. 299 If an implementation uses the OpenSSL libraries, a group consisting 300 of a 1024-bit safe prime and 2 as generator can be created as fol- 301 lows: 303 DH *d = NULL; 304 d = DH_generate_parameters(1024, DH_GENERATOR_2, NULL, NULL); 305 BN_print_fp(stdout, d->p); 307 The order of the subgroup generated by 2 is q = p - 1. 309 12. Author's Address 311 Markus Friedl 312 Ganghoferstr. 7 313 80339 Munich 314 Germany 316 Email: markus@openbsd.org 318 Niels Provos 319 Center for Information Technology Integration 320 535 W. William Street 321 Ann Arbor, MI, 48103 323 Phone: (734) 764-5207 324 Email: provos@citi.umich.edu 326 William Allen Simpson 327 DayDreamer 328 Computer Systems Consulting Services 329 1384 Fontaine 330 Madion Heights, Michigan 48071 332 Email: wsimpson@umich.edu 333 wsimpson@greendragon.com