Network Working Group Markus Friedl INTERNET-DRAFT Niels Provos Expires in six months William A. Simpson January 2001 Diffie-Hellman Group Exchange for the SSH Transport Layer Protocol draft-ietf-secsh-dh-group-exchange-00.txt 1. Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other docu- ments at any time. It is inappropriate to use Internet- Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. 2. Copyright Notice Copyright (C) 2000 by Markus Friedl, Niels Provos and William A. Simpson. 3. Abstract This memo describes a new key exchange method for the SSH protocol. It allows the SSH server to propose to the client new groups on which to perform the Diffie-Hellman key exchange. The proposed groups need not be fixed and can change with time. 4. Overview and Rational SSH [4,5,6,7] is a a very common protocol for secure remote login on the Internet. Currently, SSH performs the initial key exchange Friedl/Provos/Simpson expires in six months [Page 1]
INTERNET DRAFT January 2001 using the "diffie-hellman-group1-sha1" method. This method pre- scribes a fixed group on which all operations are performed. The Diffie-Hellman key exchange provides a shared secret that can not be determined by either party alone. In SSH, the key exchange is signed with the host key to provide host authentication. The security of the Diffie-Hellman key exchange is based on the difficulty of solving the Discrete Logarithm Problem (DLP). Since we expect that the SSH protocol will be in use for many years in the future, we fear that extensive precomputation and more effi- cient algorithms to compute the discrete logarithm over a fixed group might pose a security threat to the SSH protocol. The ability to propose new groups will reduce the incentive to use precomputation for more efficient calculation of the discrete loga- rithm. The server can constantly compute new groups in the back- ground. 5. Diffie-Hellman Group and Key Exchange The server keeps a list of safe primes and corresponding generators that it can select from. A prime p is safe, if p = 2q + 1, and q is prime. New primes can be generated in the background. The generator g should be chosen such that the order of the gener- ated subgroup does not factor into small primes, i.e., with p = 2q + 1, the order has to be either q or p - 1. If the order is p - 1, then the exponents generate all possible public-values, evenly dis- tributed throughout the range of the modulus p, without cycling through a smaller subset. Such a generator is called a "primitive root" (which is trivial to find when p is "safe"). Implementation Notes: One useful technique is to select the generator, and then limit the modulus selection sieve to primes with that genera- tor: 2 when p (mod 24) = 11. 5 when p (mod 10) = 3 or 7. It is recommended to use 2 as generator, because it improves efficiency in multiplication performance. It is usable even when it is not a primitive root, as it still covers half of the space of possible residues. Friedl/Provos/Simpson expires in six months [Page 2]
INTERNET DRAFT January 2001 Servers and clients SHOULD support groups with a modulus length of k bits, where 1024 <= k <= 8192. The client requests a minimum modulus size from the server. In the following description (C is the client, S is the server; n is the minimal number of bits in the subgroup; p is a large safe prime and g is a generator for a subgroup of GF(p); V_S is S's version string; V_C is C's version string; K_S is S's public host key; I_C is C's KEXINIT message and I_S S's KEXINIT message which have been exchanged before this part begins): 1. C sends "n", the minimal number of bits in the subgroup that the server should reply with. 2. S finds a group that best matches the client's request, and sends "p || g" to C. 3. C generates a random number x (1 < x < (p-1)/2). It computes e = g^x mod p, and sends "e" to S. 4. S generates a random number y (0 < y < (p-1)/2) and computes f = g^y mod p. S receives "e". It computes K = e^y mod p, H = hash(V_C || V_S || I_C || I_S || K_S || n || p || g || e || f || K) (these elements are encoded according to their types; see below), and signature s on H with its private host key. S sends "K_S || f || s" to C. The signing operation may involve a second hashing operation. 5. C verifies that K_S really is the host key for S (e.g. using certificates or a local database). C is also allowed to accept the key without verification; however, doing so will render the protocol insecure against active attacks (but may be desirable for practical reasons in the short term in many environments). C then computes K = f^x mod p, H = hash(V_C || V_S || I_C || I_S || K_S || n || p || g || e || f || K), and verifies the signature s on H. Either side MUST NOT send or accept e or f values that are not in the range [1, p-1]. If this condition is violated, the key exchange fails. To prevent confinement attacks, they MUST accept the shared secret K only , if 1 < K < p - 1. The server should return the smallest group it knows about that is larger than the size the client requested. If the server does not know a group that is larger than the client request, then it has to return the largest group it knows. In all cases, the size of the returned group SHOULD be at least 1024 bits. Friedl/Provos/Simpson expires in six months [Page 3]
INTERNET DRAFT January 2001 This is implemented with the following messages. The hash algo- rithm for computing the exchange hash is defined by the method name, and is called HASH. The public key algorithm for signing is negotiated with the KEXINIT messages. First, the client sends: byte SSH_MSG_KEY_DH_GEX_REQUEST uint32 n, number of bits the subgroup should have at least The server responds with byte SSH_MSG_KEX_DH_GEX_GROUP mpint p, safe prime mpint g, generator for subgroup in GF(p) The client responds with: byte SSH_MSG_KEX_DH_GEX_INIT mpint e The server responds with: byte SSH_MSG_KEX_DH_GEX_REPLY string server public host key and certificates (K_S) mpint f string signature of H The hash H is computed as the HASH hash of the concatenation of the following: string V_C, the client's version string (CR and NL excluded) string V_S, the server's version string (CR and NL excluded) string I_C, the payload of the client's SSH_MSG_KEXINIT string I_S, the payload of the server's SSH_MSG_KEXINIT string K_S, the host key uint32 n, number of bits the client requested mpint p, safe prime mpint g, generator for subgroup mpint e, exchange value sent by the client mpint f, exchange value sent by the server mpint K, the shared secret This value is called the exchange hash, and it is used to authenti- cate the key exchange. 6. diffie-hellman-group-exchange-sha1 The "diffie-hellman-group-exchange-sha1" method specifies Diffie- Hellman Group and Key Exchange with SHA-1 as HASH. Friedl/Provos/Simpson expires in six months [Page 4]
INTERNET DRAFT January 2001 7. Summary of Message numbers The following message numbers have been defined in this document. #define SSH_MSG_KEX_DH_GEX_REQUEST 30 #define SSH_MSG_KEX_DH_GEX_GROUP 31 #define SSH_MSG_KEX_DH_GEX_INIT 32 #define SSH_MSG_KEX_DH_GEX_REPLY 33 The numbers 30-49 are key exchange specific and may be redefined by other kex methods. 8. Security Considerations This protocol aims to be simple and uses only well understood prim- itives. This encourages acceptance by the community and allows for ease of implementation, which hopefully leads to a more secure sys- tem. The use of multiple moduli inhibits a determined attacker from pre- calculating moduli exchange values, and discourages dedication of resources for analysis of any particular modulus. It is important to only employ safe primes as moduli. Oorshot and Wiener note that using short private exponents with a random prime modulus p makes the computation of the discrete logarithm easy [1]. However, they also state that this problem does not apply to safe primes. The least significant bit of the private exponent can be recovered, when the modulus is a safe prime [2]. However, this is not a prob- lem, if the size of the private exponent is big enough. Related to this, Waldvogel and Massey note: When private exponents are chosen independently and uniformly at random from {0,...,p-2}, the key entropy is less than 2 bits away from the maximum, lg(p-1) [3]. 9. Acknowledgments The document is derived in part from "SSH Transport Layer Protocol" by T. Ylonen, T. Kivinen, M. Saarinen, T. Rinne and S. Lehtinen. Markku-Juhani Saarinen pointed out that the least significant bit of the private exponent can be recovered efficiently when using safe primes and a subgroup with an order divisible by two. Bodo Moeller suggested that the server send only one group, reduc- ing the complexity of the implementation and the amount of data that needs to be exchanged between client and server. Friedl/Provos/Simpson expires in six months [Page 5]
INTERNET DRAFT January 2001 10. Bibliography [1] P. C. van Oorschot and M. J. Wiener, On Diffie-Hellman key agreement with short exponents, In Advances in Cryptology - EUROCRYPT'96, LNCS 1070, Springer-Verlag, 1996, pp.332-343. [2] Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Van- stone. Handbook of Applied Cryptography. CRC Press, 1996. [3] C. P. Waldvogel and J. L. Massey, The probability distribution of the Diffie-Hellman key, in Proceedings of AUSCRYPT 92, LNCS 718, Springer- Verlag, 1993, pp. 492-504. [4] Ylonen, T., et al: "SSH Protocol Architecture", Internet- Draft, draft-secsh-architecture-07.txt [5] Ylonen, T., et al: "SSH Transport Layer Protocol", Internet- Draft, draft-ietf-secsh-transport-09.txt [6] Ylonen, T., et al: "SSH Authentication Protocol", Internet- Draft, draft-ietf-secsh-userauth-09.txt [7] Ylonen, T., et al: "SSH Connection Protocol", Internet-Draft, draft-ietf-secsh-connect-09.txt 11. Appendix A: Generation of safe primes The Handbook of Applied Cryptography [2] lists the following algo- rithm to generate a k-bit safe prime p. It has been modified so that 2 is a generator for the multiplicative group mod p. 1. Do the following: 1.1 Select a random (k-1)-bit prime q, so that q mod 12 = 5. 1.2 Compute p := 2q + 1, and test whether p is prime, (using, e.g. trial division and the Rabin-Miller test.) Repeat until p is prime. If an implementation uses the OpenSSL libraries, a group consisting of a 1024-bit safe prime and 2 as generator can be created as fol- lows: DH *d = NULL; d = DH_generate_parameters(1024, DH_GENERATOR_2, NULL, NULL); BN_print_fp(stdout, d->p); Friedl/Provos/Simpson expires in six months [Page 6]
INTERNET DRAFT January 2001 The order of the subgroup generated by 2 is q = p - 1. Friedl/Provos/Simpson expires in six months [Page 7]
INTERNET DRAFT January 2001 12. Author's Address Markus Friedl Ganghoferstr. 7 80339 Munich Germany Email: markus@openbsd.org Niels Provos Center for Information Technology Integration 519 W. William Street Ann Arbor, MI, 48103 Phone: (734) 764-5207 Email: provos@citi.umich.edu William Allen Simpson DayDreamer Computer Systems Consulting Services 1384 Fontaine Madion Heights, Michigan 48071 Email: wsimpson@umich.edu wsimpson@greendragon.com Friedl/Provos/Simpson expires in six months [Page 8]