diff options
Diffstat (limited to 'doc/draft-ietf-secsh-dh-group-exchange-04.txt')
| -rw-r--r-- | doc/draft-ietf-secsh-dh-group-exchange-04.txt | 451 |
1 files changed, 451 insertions, 0 deletions
diff --git a/doc/draft-ietf-secsh-dh-group-exchange-04.txt b/doc/draft-ietf-secsh-dh-group-exchange-04.txt new file mode 100644 index 0000000..ee6b2fb --- /dev/null +++ b/doc/draft-ietf-secsh-dh-group-exchange-04.txt @@ -0,0 +1,451 @@ + + + + + + +Network Working Group Markus Friedl +INTERNET-DRAFT Niels Provos +Expires in six months William A. Simpson + July 2003 + + + Diffie-Hellman Group Exchange for the SSH Transport Layer Protocol + draft-ietf-secsh-dh-group-exchange-04.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-2003 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 July 2003 + + + 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 July 2003 + + + The client requests a modulus from the server indicating the pre- + ferred size. In the following description (C is the client, S is + the server; the modulus p is a large safe prime and g is a genera- + tor for a subgroup of GF(p); min is the minimal size of p in bits + that is acceptable to the client; n is the size of the modulus p in + bits that the client would like to receive from the server; max is + the maximal size of p in bits that the client can accept; 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 "min || n || max" to S, indicating the minimal accept- + able group size, the preferred size of the group and the maxi- + mal group size in bits the client will accept. + + 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 || min || n || max || 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 opera- + tion may involve a second hashing operation. + + Implementation Notes: + + To increase the speed of the key exchange, both client + and server may reduce the size of their private expo- + nents. It should be at least twice as long as the key + material that is generated from the shared secret. For + more details see the paper by van Oorschot and Wiener + [1]. + + 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 || min || n || max || p || g || e || + f || K), and verifies the signature s on H. + + Servers and clients SHOULD support groups with a modulus + + + +Friedl/Provos/Simpson expires in six months [Page 3] + +INTERNET DRAFT July 2003 + + + length of k bits, where 1024 <= k <= 8192. The recommended + values for min and max are 1024 and 8192 respectively. + + 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 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 SHOULD return + the largest group it knows. In all cases, the size of the returned + group SHOULD be at least 1024 bits. + + 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 min, minimal size in bits of an acceptable group + uint32 n, preferred size in bits of the group the server should send + uint32 max, maximal size in bits of an acceptable group + + 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 + + + +Friedl/Provos/Simpson expires in six months [Page 4] + +INTERNET DRAFT July 2003 + + + uint32 min, minimal size in bits of an acceptable group + uint32 n, preferred size in bits of the group the server should send + uint32 max, maximal size in bits of an acceptable group + 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. + +7. Summary of Message numbers + + The following message numbers have been defined in this document. + + #define SSH_MSG_KEX_DH_GEX_REQUEST_OLD 30 + #define SSH_MSG_KEX_DH_GEX_REQUEST 34 + #define SSH_MSG_KEX_DH_GEX_GROUP 31 + #define SSH_MSG_KEX_DH_GEX_INIT 32 + #define SSH_MSG_KEX_DH_GEX_REPLY 33 + + SSH_MSG_KEX_DH_GEX_REQUEST_OLD is used for backwards compatibility. + Instead of sending "min || n || max", the client only sends "n". + Additionally, the hash is calculated using only "n" instead of "min + || n || max". + + 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 employ only safe primes as moduli. Van Oorshot + + + +Friedl/Provos/Simpson expires in six months [Page 5] + +INTERNET DRAFT July 2003 + + + 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. + +10. Bibliography + + + 10.1. Informative References + + + [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. + + + + + + + + + + +Friedl/Provos/Simpson expires in six months [Page 6] + +INTERNET DRAFT July 2003 + + + 10.2. Normative References + + + [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); + + The order of the subgroup generated by 2 is q = p - 1. + + + + + + + + + + + + + +Friedl/Provos/Simpson expires in six months [Page 7] + +INTERNET DRAFT July 2003 + + +12. Author's Address + + Markus Friedl + Ganghoferstr. 7 + 80339 Munich + Germany + + Email: markus@openbsd.org + + Niels Provos + Center for Information Technology Integration + 535 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@greendragon.com + + + + + + + + + + + + + + + + + + + + + + + + + + + +Friedl/Provos/Simpson expires in six months [Page 8] + |