idnits 2.17.1 draft-provos-secsh-dh-group-exchange-00.txt: 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 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 10 instances of too long lines in the document, the longest one being 5 characters in excess of 72. ** The abstract seems to contain references ([2], [3], [1]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. ** 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 69: '... SHOULD know at least one safe prime...' RFC 2119 keyword, line 125: '... Either side MUST NOT send or acce...' Miscellaneous warnings: ---------------------------------------------------------------------------- == Line 149 has weird spacing: '... string ser...' == Line 151 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 (May 2000) is 8740 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? '1' on line 221 looks like a reference -- Missing reference section? '2' on line 234 looks like a reference -- Missing reference section? '3' on line 228 looks like a reference Summary: 7 errors (**), 0 flaws (~~), 3 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Network Working Group Markus Friedl 2 INTERNET-DRAFT Niels Provos 3 Expires in six months William A. Simpson 4 May 2000 6 Diffie-Hellman Group Exchange for the SSH Transport Layer Protocol 7 draft-provos-secsh-dh-group-exchange-00.txt 9 Status of this Memo 11 This document is an Internet-Draft and is in full conformance with 12 all provisions of Section 10 of RFC2026, except that the right to 13 produce derivative works is not granted. 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 months 21 and may be updated, replaced, or obsoleted by other documents at any 22 time. It is inappropriate to use Internet- Drafts as reference 23 material or to cite them other than as "work in progress." 25 The list of current Internet-Drafts can be accessed at 26 http://www.ietf.org/ietf/1id-abstracts.txt 28 The list of Internet-Draft Shadow Directories can be accessed at 29 http://www.ietf.org/shadow.html. 31 Copyright Notice 33 Copyright (C) 2000 by Markus Friedl, Niels Provos and William A. 34 Simpson. All Rights Reserved. 36 Abstract 38 This memo describes a new key exchange method for the SSH protocol. 39 It allows the SSH server to propose to the client new groups on which 40 to perform the Diffie-Hellman key exchange. The proposed groups need 41 not be fixed and can change with time. 43 Overview and Rational 45 SSH is a de-facto standard for secure remote login on the Internet. 46 Currently, SSH performs the initial key exchange using the "diffie- 47 hellman-group1-sha1" method. This method prescribes a fixed group on 48 which all operations are performed. The security of the Diffie- 49 Hellman key exchange is based on the difficulty of solving the 50 Discrete Logarithm Problem (DLP). Since we expect that the SSH 51 protocol will be in use for many years in the future, we fear that 52 extensive precomputation and more efficient alogorithms to compute 53 the Discrete Logarithm might pose a security threat to the SSH 54 protocol. 56 The ability to propose new moduli will reduce the possibility to use 57 precomputation for more efficient calculation of the DL. The server 58 can constantly compute new moduli in the background. 60 Diffie-Hellman Group and Key Exchange 62 The Diffie-Hellman key exchange provides a shared secret that can not 63 be determined by either party alone. The key exchange is combined 64 with a signature with the host key to provide host authentication. 66 The server keeps a list of safe primes and corresponding generators 67 that it can select from. A prime p is safe, if p = 2q + 1, and q is 68 prime. New primes can be generated in the background. The server 69 SHOULD know at least one safe prime that has 1024 or more bits. 71 The generator g should be chosen such that the order of the generated 72 subgroup does not factor into small primes, i.e., with p = 2q + 1, 73 the order has to be either q or p - 1. If the order is p - 1, then 74 the exponents generate all possible public-values, evenly distributed 75 throughout the range of the modulus p, without cycling through a 76 smaller subset. Such a generator is called a "primitive root" (which 77 is trivial to find when p is "safe"). 79 Implementation Notes: 81 One useful technique is to select the generator, and then limit 82 the modulus selection sieve to primes with that generator: 84 2 when p (mod 24) = 11. 85 5 when p (mod 10) = 3 or 7. 87 It is recommened to to use 2 as generator, because it improves 88 efficiency in multiplication performance. It is usable even when 89 it is not a primitive root, as it still covers half of the space 90 of possible residues. 92 The client requests a minimum modulus size from the server. In the 93 following description (C is the client, S is the server; n is the 94 minimal number of bits the subgroup the server replies with should 95 have; p is a large safe prime and g is a generator for a subgroup of 96 GF(p); V_S is S's version string; V_C is C's version string; K_S is 97 S's public host key; I_C is C's KEXINIT message and I_S S's KEXINIT 98 message which have been exchanged before this part begins): 100 1. C sends n, the minimal number of bits the subgroup the server 101 replies with should have. 103 2. S finds a group that matches the clients request the closest 104 and sends p and g to C. 106 3. C generates a random number x (1 < x < (p-1)/2). It computes 107 e = g^x mod p, and sends "e" to S. 109 4. S generates a random number y (0 < y < (p-1)/2) and computes 110 f = g^y mod p. S receives "e". It computes K = e^y mod p, 111 H = hash(V_C || V_S || I_C || I_S || K_S || n || p || g || e || 112 f || K) (these elements are encoded according to their types; see 113 below), and signature s on H with its private host key. S sends 114 "K_S || f || s" to C. The signing operation may involve a second 115 hashing operation. 117 5. C verifies that K_S really is the host key for S (e.g. using 118 certificates or a local database). C is also allowed to accept the 119 key without verification; however, doing so will render the protocol 120 insecure against active attacks (but may be desirable for practical 121 reasons in the short term in many environments). C then computes K = 122 f^x mod p, H = hash(V_C || V_S || I_C || I_S || K_S || n || p || g || 123 e || f || K), and verifies the signature s on H. 125 Either side MUST NOT send or accept e or f values that are not in the 126 range [1, p-1]. If this condition is violated, the key exchange 127 fails. 129 This is implemented with the following messages. The hash algorithm 130 for computing the exchange hash is defined by the method name, and is 131 called HASH. The public key algorithm for signing is negotiated with 132 the KEXINIT messages. 134 First, the client sends: 135 byte SSH_MSG_KEY_DH_GEX_REQUEST 136 uint32 n, number of bits the subgroup should have at least 138 The server responds with 139 byte SSH_MSG_KEX_DH_GEX_GROUP 140 mpint p, safe prime 141 mpint g, generator for subgroup in GF(p) 143 The client responds with: 144 byte SSH_MSG_KEX_DH_GEX_INIT 145 mpint e 147 The server responds with: 148 byte SSH_MSG_KEX_DH_GEX_REPLY 149 string server public host key and certificates (K_S) 150 mpint f 151 string signature of H 153 The hash H is computed as the HASH hash of the concatenation of the 154 following: 155 string V_C, the client's version string (CR and NL excluded) 156 string V_S, the server's version string (CR and NL excluded) 157 string I_C, the payload of the client's SSH_MSG_KEXINIT 158 string I_S, the payload of the server's SSH_MSG_KEXINIT 159 string K_S, the host key 160 uint32 n, number of bits the client requested 161 mpint p, safe prime 162 mpint g, generator for subgroup 163 mpint e, exchange value sent by the client 164 mpint f, exchange value sent by the server 165 mpint K, the shared secret 167 This value is called the exchange hash, and it is used to 168 authenticate the key exchange. 170 diffie-hellman-group-exchange-sha1 172 The "diffie-hellman-group-exchange-sha1" method specifies Diffie- 173 Hellman Group and Key Exchange with SHA-1 as HASH. 175 Summary of Message numbers 177 The following message numbers have been defined in this document. 179 #define SSH_MSG_KEX_DH_GEX_REQUEST 30 180 #define SSH_MSG_KEX_DH_GEX_GROUP 31 181 #define SSH_MSG_KEX_DH_GEX_INIT 32 182 #define SSH_MSG_KEX_DH_GEX_REPLY 33 184 The numbers 30-49 are key exchange specific and may be redefined by 185 other kex methods. 187 Security Considerations 189 The use of multiple moduli inhibits a determined attacker from pre- 190 calculating moduli exchange values, and discourages dedication of 191 resources for analysis of any particular modulus. 193 It is important to only employ safe primes as moduli. Oorshot and 194 Wiener note that using short private exponents with a random prime 195 modulus p makes the computation of the discrete logarithm easy [1]. 196 However, they also state that this problem does not apply to safe 197 primes. 199 The least significant bit of the private exponent can be recovered, 200 when the modulus is a safe prime [2]. However, this is not a 201 problem, if the size of the private exponent is big enough. Related 202 to this, Waldvogel and Massey note: When private exponents are chosen 203 independently and uniformly at random from {0,...,p-2}, the key 204 entropy is less than 2 bits away from the maximum, lg(p-1) [3]. 206 Acknowledgments 208 The document is derived in part from "SSH Transport Layer Protocol" 209 by T. Ylonen, T. Kivinen, M. Saarinen, T. Rinne and S. Lehtinen. 211 Markku-Juhani Saarinen pointed out that the least significant bit of 212 the private exponent can be recovered efficiently when using safe 213 primes and a subgroup with an order divisible by two. 215 Bodo Moeller suggested that the server sends only one group reducing 216 the complexity of the implementation and the amount of data that 217 needs to be exchanged between client and server. 219 Bibliography 221 [1] P. C. van Oorschot and M. J. Wiener, On Diffie-Hellman key agreement 222 with short exponents, In Advances in Cryptology - EUROCRYPT'96, 223 LNCS 1070, Springer-Verlag, 1996, pp.332-343. 225 [2] Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone. 226 Handbook of Applied Cryptography. CRC Press, 1996. 228 [3] C. P. Waldvogel and J. L. Massey, The probability distribution of the 229 Diffie-Hellman key, in Proceedings of AUSCRYPT 92, LNCS 718, Springer- 230 Verlag, 1993, pp. 492-504. 232 Appendix A: Generation of safe primes 234 The Handbook of Applied Cryptography [2] lists the following 235 algorithm to generate a k-bit safe prime p. It has been modified so 236 that 2 is a generator for the multiplicative group mod p. 238 1. Do the following: 239 1.1 Select a random (k-1)-bit prime q, so that q mod 12 = 5. 240 1.2 Compute p := 2q + 1, and test whether p is prime, (using, e.g. 241 trial division and the Rabin-Miller test.) 242 Repeat until p is prime. 244 If an implementation uses the OpenSSL libraries, a group consisting 245 of a 1024-bit safe prime and 2 as generator can be created as 246 follows: 248 DH *d = NULL; 249 d = DH_generate_parameters(1024, DH_GENERATOR_2, NULL, NULL); 250 BN_print_fp(stdout, d->p); 252 The order of the subgroup generated by 2 is q = p - 1. 254 Author's Address 256 Niels Provos 257 CITI 258 519 W. William Street 259 Ann Arbor, MI, 48103 261 Phone: (734) 764-5207 263 EMail: provos@citi.umich.edu