idnits 2.17.1 draft-ietf-secsh-dh-group-exchange-00.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 is 1 instance of too long lines in the document, the longest one being 2 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 95: '...vers and clients SHOULD support groups...' RFC 2119 keyword, line 132: '... Either side MUST NOT send or acce...' RFC 2119 keyword, line 134: '...prevent confinement attacks, they MUST...' RFC 2119 keyword, line 141: '... returned group SHOULD be at least 10...' Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 163 has weird spacing: '... string ser...' == Line 165 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 (January 2001) is 8496 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 251 looks like a reference -- Missing reference section? '5' on line 254 looks like a reference -- Missing reference section? '6' on line 257 looks like a reference -- Missing reference section? '7' on line 260 looks like a reference -- Missing reference section? '1' on line 240 looks like a reference -- Missing reference section? '2' on line 265 looks like a reference -- Missing reference section? '3' on line 247 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 January 2001 7 Diffie-Hellman Group Exchange for the SSH Transport Layer Protocol 8 draft-ietf-secsh-dh-group-exchange-00.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 Servers and clients SHOULD support groups with a modulus length of 96 k bits, where 1024 <= k <= 8192. 98 The client requests a minimum modulus size from the server. In the 99 following description (C is the client, S is the server; n is the 100 minimal number of bits in the subgroup; p is a large safe prime and 101 g is a generator for a subgroup of GF(p); V_S is S's version 102 string; V_C is C's version string; K_S is S's public host key; I_C 103 is C's KEXINIT message and I_S S's KEXINIT message which have been 104 exchanged before this part begins): 106 1. C sends "n", the minimal number of bits in the subgroup that 107 the server should reply with. 109 2. S finds a group that best matches the client's request, and 110 sends "p || g" to C. 112 3. C generates a random number x (1 < x < (p-1)/2). It computes e 113 = g^x mod p, and sends "e" to S. 115 4. S generates a random number y (0 < y < (p-1)/2) and computes f 116 = g^y mod p. S receives "e". It computes K = e^y mod p, H = 117 hash(V_C || V_S || I_C || I_S || K_S || n || p || g || e || f 118 || K) (these elements are encoded according to their types; 119 see below), and signature s on H with its private host key. S 120 sends "K_S || f || s" to C. The signing operation may involve 121 a second hashing operation. 123 5. C verifies that K_S really is the host key for S (e.g. using 124 certificates or a local database). C is also allowed to 125 accept the key without verification; however, doing so will 126 render the protocol insecure against active attacks (but may 127 be desirable for practical reasons in the short term in many 128 environments). C then computes K = f^x mod p, H = hash(V_C || 129 V_S || I_C || I_S || K_S || n || p || g || e || f || K), and 130 verifies the signature s on H. 132 Either side MUST NOT send or accept e or f values that are not 133 in the range [1, p-1]. If this condition is violated, the key 134 exchange fails. To prevent confinement attacks, they MUST 135 accept the shared secret K only , if 1 < K < p - 1. 137 The server should return the smallest group it knows about that is 138 larger than the size the client requested. If the server does not 139 know a group that is larger than the client request, then it has to 140 return the largest group it knows. In all cases, the size of the 141 returned group SHOULD be at least 1024 bits. 143 This is implemented with the following messages. The hash algo- 144 rithm for computing the exchange hash is defined by the method 145 name, and is called HASH. The public key algorithm for signing is 146 negotiated with the KEXINIT messages. 148 First, the client sends: 149 byte SSH_MSG_KEY_DH_GEX_REQUEST 150 uint32 n, number of bits the subgroup should have at least 152 The server responds with 153 byte SSH_MSG_KEX_DH_GEX_GROUP 154 mpint p, safe prime 155 mpint g, generator for subgroup in GF(p) 157 The client responds with: 158 byte SSH_MSG_KEX_DH_GEX_INIT 159 mpint e 161 The server responds with: 162 byte SSH_MSG_KEX_DH_GEX_REPLY 163 string server public host key and certificates (K_S) 164 mpint f 165 string signature of H 167 The hash H is computed as the HASH hash of the concatenation of the 168 following: 169 string V_C, the client's version string (CR and NL excluded) 170 string V_S, the server's version string (CR and NL excluded) 171 string I_C, the payload of the client's SSH_MSG_KEXINIT 172 string I_S, the payload of the server's SSH_MSG_KEXINIT 173 string K_S, the host key 174 uint32 n, number of bits the client requested 175 mpint p, safe prime 176 mpint g, generator for subgroup 177 mpint e, exchange value sent by the client 178 mpint f, exchange value sent by the server 179 mpint K, the shared secret 181 This value is called the exchange hash, and it is used to authenti- 182 cate the key exchange. 184 6. diffie-hellman-group-exchange-sha1 186 The "diffie-hellman-group-exchange-sha1" method specifies Diffie- 187 Hellman Group and Key Exchange with SHA-1 as HASH. 189 7. Summary of Message numbers 191 The following message numbers have been defined in this document. 193 #define SSH_MSG_KEX_DH_GEX_REQUEST 30 194 #define SSH_MSG_KEX_DH_GEX_GROUP 31 195 #define SSH_MSG_KEX_DH_GEX_INIT 32 196 #define SSH_MSG_KEX_DH_GEX_REPLY 33 198 The numbers 30-49 are key exchange specific and may be redefined by 199 other kex methods. 201 8. Security Considerations 203 This protocol aims to be simple and uses only well understood prim- 204 itives. This encourages acceptance by the community and allows for 205 ease of implementation, which hopefully leads to a more secure sys- 206 tem. 208 The use of multiple moduli inhibits a determined attacker from pre- 209 calculating moduli exchange values, and discourages dedication of 210 resources for analysis of any particular modulus. 212 It is important to only employ safe primes as moduli. Oorshot and 213 Wiener note that using short private exponents with a random prime 214 modulus p makes the computation of the discrete logarithm easy [1]. 215 However, they also state that this problem does not apply to safe 216 primes. 218 The least significant bit of the private exponent can be recovered, 219 when the modulus is a safe prime [2]. However, this is not a prob- 220 lem, if the size of the private exponent is big enough. Related to 221 this, Waldvogel and Massey note: When private exponents are chosen 222 independently and uniformly at random from {0,...,p-2}, the key 223 entropy is less than 2 bits away from the maximum, lg(p-1) [3]. 225 9. Acknowledgments 227 The document is derived in part from "SSH Transport Layer Protocol" 228 by T. Ylonen, T. Kivinen, M. Saarinen, T. Rinne and S. Lehtinen. 230 Markku-Juhani Saarinen pointed out that the least significant bit 231 of the private exponent can be recovered efficiently when using 232 safe primes and a subgroup with an order divisible by two. 234 Bodo Moeller suggested that the server send only one group, reduc- 235 ing the complexity of the implementation and the amount of data 236 that needs to be exchanged between client and server. 238 10. Bibliography 240 [1] P. C. van Oorschot and M. J. Wiener, On Diffie-Hellman key 241 agreement with short exponents, In Advances in Cryptology - 242 EUROCRYPT'96, LNCS 1070, Springer-Verlag, 1996, pp.332-343. 244 [2] Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Van- 245 stone. Handbook of Applied Cryptography. CRC Press, 1996. 247 [3] C. P. Waldvogel and J. L. Massey, The probability distribution 248 of the Diffie-Hellman key, in Proceedings of AUSCRYPT 92, LNCS 249 718, Springer- Verlag, 1993, pp. 492-504. 251 [4] Ylonen, T., et al: "SSH Protocol Architecture", Internet- 252 Draft, draft-secsh-architecture-07.txt 254 [5] Ylonen, T., et al: "SSH Transport Layer Protocol", Internet- 255 Draft, draft-ietf-secsh-transport-09.txt 257 [6] Ylonen, T., et al: "SSH Authentication Protocol", Internet- 258 Draft, draft-ietf-secsh-userauth-09.txt 260 [7] Ylonen, T., et al: "SSH Connection Protocol", Internet-Draft, 261 draft-ietf-secsh-connect-09.txt 263 11. Appendix A: Generation of safe primes 265 The Handbook of Applied Cryptography [2] lists the following algo- 266 rithm to generate a k-bit safe prime p. It has been modified so 267 that 2 is a generator for the multiplicative group mod p. 269 1. Do the following: 270 1.1 Select a random (k-1)-bit prime q, so that q mod 12 = 5. 271 1.2 Compute p := 2q + 1, and test whether p is prime, (using, e.g. 272 trial division and the Rabin-Miller test.) 273 Repeat until p is prime. 275 If an implementation uses the OpenSSL libraries, a group consisting 276 of a 1024-bit safe prime and 2 as generator can be created as fol- 277 lows: 279 DH *d = NULL; 280 d = DH_generate_parameters(1024, DH_GENERATOR_2, NULL, NULL); 281 BN_print_fp(stdout, d->p); 282 The order of the subgroup generated by 2 is q = p - 1. 284 12. Author's Address 286 Markus Friedl 287 Ganghoferstr. 7 288 80339 Munich 289 Germany 291 Email: markus@openbsd.org 293 Niels Provos 294 Center for Information Technology Integration 295 519 W. William Street 296 Ann Arbor, MI, 48103 298 Phone: (734) 764-5207 299 Email: provos@citi.umich.edu 301 William Allen Simpson 302 DayDreamer 303 Computer Systems Consulting Services 304 1384 Fontaine 305 Madion Heights, Michigan 48071 307 Email: wsimpson@umich.edu 308 wsimpson@greendragon.com