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, 0 insertions, 451 deletions
diff --git a/doc/draft-ietf-secsh-dh-group-exchange-04.txt b/doc/draft-ietf-secsh-dh-group-exchange-04.txt deleted file mode 100644 index ee6b2fb..0000000 --- a/doc/draft-ietf-secsh-dh-group-exchange-04.txt +++ /dev/null @@ -1,451 +0,0 @@ - - - - - - -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] - |