From 4bfd864f10b68b71482b35c818559068ef8d5797 Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Wed, 27 Nov 2024 20:54:24 +0100 Subject: doc: Add RFC documents --- doc/rfc/rfc4419.txt | 563 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 563 insertions(+) create mode 100644 doc/rfc/rfc4419.txt (limited to 'doc/rfc/rfc4419.txt') diff --git a/doc/rfc/rfc4419.txt b/doc/rfc/rfc4419.txt new file mode 100644 index 0000000..87f9af7 --- /dev/null +++ b/doc/rfc/rfc4419.txt @@ -0,0 +1,563 @@ + + + + + + +Network Working Group M. Friedl +Request for Comments: 4419 N. Provos +Category: Standards Track W. Simpson + March 2006 + + + Diffie-Hellman Group Exchange for + the Secure Shell (SSH) Transport Layer Protocol + +Status of This Memo + + This document specifies an Internet standards track protocol for the + Internet community, and requests discussion and suggestions for + improvements. Please refer to the current edition of the "Internet + Official Protocol Standards" (STD 1) for the standardization state + and status of this protocol. Distribution of this memo is unlimited. + +Copyright Notice + + Copyright (C) The Internet Society (2006). + +Abstract + + This memo describes a new key exchange method for the Secure Shell + (SSH) protocol. It allows the SSH server to propose new groups on + which to perform the Diffie-Hellman key exchange to the client. The + proposed groups need not be fixed and can change with time. + +1. Overview and Rationale + + SSH [RFC4251] is a very common protocol for secure remote login on + the Internet. Currently, SSH performs the initial key exchange using + the "diffie-hellman-group1-sha1" method [RFC4253]. This method + prescribes a fixed group on which all operations are performed. + + The Diffie-Hellman key exchange provides a shared secret that cannot + be determined by either party alone. Furthermore, the shared secret + is known only to the participant parties. 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 efficient + algorithms to compute the discrete logarithm over a fixed group might + pose a security threat to the SSH protocol. + + + + + +Friedl, et al. Standards Track [Page 1] + +RFC 4419 SSH DH Group Exchange March 2006 + + + The ability to propose new groups will reduce the incentive to use + precomputation for more efficient calculation of the discrete + logarithm. The server can constantly compute new groups in the + background. + +2. Requirements Notation + + The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", + "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this + document are to be interpreted as described in [RFC2119]. + +3. 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 generated + subgroup does not factor into small primes; that is, 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 distributed + 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"). + + The client requests a modulus from the server indicating the + preferred 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 generator + 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 is S's KEXINIT message that has been + exchanged before this part begins): + + 1. C sends "min || n || max" to S, indicating the minimal acceptable + group size, the preferred size of the group, and the maximal + 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, where 1 < x < (p-1)/2. It + computes e = g^x mod p, and sends "e" to S. + + + + + + +Friedl, et al. Standards Track [Page 2] + +RFC 4419 SSH DH Group Exchange March 2006 + + + 4. S generates a random number y, where 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 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 to obtain the public key). 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 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 algorithm + 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 will send + uint32 max, maximal size in bits of an acceptable group + + + + + + + + +Friedl, et al. Standards Track [Page 3] + +RFC 4419 SSH DH Group Exchange March 2006 + + + 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 min, minimal size in bits of an acceptable group + uint32 n, preferred size in bits of the group the server will 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 + authenticate the key exchange as per [RFC4253]. + +4. Key Exchange Methods + + This document defines two new key exchange methods: + "diffie-hellman-group-exchange-sha1" and + "diffie-hellman-group-exchange-sha256". + + + + + + + + +Friedl, et al. Standards Track [Page 4] + +RFC 4419 SSH DH Group Exchange March 2006 + + +4.1. diffie-hellman-group-exchange-sha1 + + The "diffie-hellman-group-exchange-sha1" method specifies + Diffie-Hellman Group and Key Exchange with SHA-1 [FIPS-180-2] as + HASH. + +4.2. diffie-hellman-group-exchange-sha256 + + The "diffie-hellman-group-exchange-sha256" method specifies + Diffie-Hellman Group and Key Exchange with SHA-256 [FIPS-180-2] as + HASH. + + Note that the hash used in key exchange (in this case, SHA-256) must + also be used in the key derivation pseudo-random function (PRF), as + per the requirement in the "Output from Key Exchange" section in + [RFC4253]. + +5. Summary of Message Numbers + + The following message numbers have been defined in this document. + They are in a name space private to this document and not assigned by + IANA. + + #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 backward compatibility. + Instead of sending "min || n || max", the client only sends "n". In + addition, 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. + +6. Implementation Notes + +6.1. Choice of Generator + + One useful technique is to select the generator, and then limit the + modulus selection sieve to primes with that generator: + + 2 when p (mod 24) = 11. + 5 when p (mod 10) = 3 or 7. + + + + + +Friedl, et al. Standards Track [Page 5] + +RFC 4419 SSH DH Group Exchange March 2006 + + + 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. + +6.2. Private Exponents + + To increase the speed of the key exchange, both client and server may + reduce the size of their private exponents. 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 + [VAN-OORSCHOT]. + +7. Security Considerations + + This protocol aims to be simple and uses only well-understood + primitives. This encourages acceptance by the community and allows + for ease of implementation, which hopefully leads to a more secure + system. + + The use of multiple moduli inhibits a determined attacker from + precalculating moduli exchange values, and discourages dedication of + resources for analysis of any particular modulus. + + It is important to employ only safe primes as moduli, as they allow + us to find a generator g so that the order of the generated subgroup + does not factor into small primes, that is, 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 distributed + throughout the range of the modulus p, without cycling through a + smaller subset. Van Oorshot and Wiener note that using short private + exponents with a random prime modulus p makes the computation of the + discrete logarithm easy [VAN-OORSCHOT]. 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 [MENEZES]. However, this is not a + problem 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) + [WALDVOGEL]. + + The security considerations in [RFC4251] also apply to this key + exchange method. + + + + + + +Friedl, et al. Standards Track [Page 6] + +RFC 4419 SSH DH Group Exchange March 2006 + + +8. Acknowledgements + + The document is derived in part from "SSH Transport Layer Protocol" + [RFC4253] 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, reducing + the complexity of the implementation and the amount of data that + needs to be exchanged between client and server. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Friedl, et al. Standards Track [Page 7] + +RFC 4419 SSH DH Group Exchange March 2006 + + +Appendix A: Generation of Safe Primes + + The "Handbook of Applied Cryptography" [MENEZES] lists the following + algorithm 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. Select a random (k-1)-bit prime q, so that q mod 12 = 5. + + 2. Compute p := 2q + 1, and test whether p is prime (using, + e.g., trial division and the Rabin-Miller test). + + 2. 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 + follows: + + 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. + +References + +Normative References + + [FIPS-180-2] National Institute of Standards and Technology (NIST), + "Secure Hash Standard (SHS)", FIPS PUB 180-2, + August 2002. + + [RFC4251] Ylonen, T. and C. Lonvick, "The Secure Shell (SSH) + Protocol Architecture", RFC 4251, January 2006. + + [RFC4253] Lonvick, C., "The Secure Shell (SSH) Transport Layer + Protocol", RFC 4253, January 2006. + + [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate + Requirement Levels", BCP 14, RFC 2119, March 1997. + +Informative References + + [MENEZES] Menezes, A., van Oorschot, P., and S. Vanstone, + "Handbook of Applied Cryptography", CRC Press, p. 537, + 1996. + + + + +Friedl, et al. Standards Track [Page 8] + +RFC 4419 SSH DH Group Exchange March 2006 + + + [VAN-OORSCHOT] van Oorschot, P. and M. Wiener, "On Diffie-Hellman key + agreement with short exponents", Advances in + Cryptology -EUROCRYPT'96, LNCS 1070, + Springer-Verlag, pp. 332-343, 1996. + + [WALDVOGEL] Waldvogel, C. and J. Massey, "The probability + distribution of the Diffie-Hellman key", Proceedings + of AUSCRYPT 92, LNCS 718, Springer-Verlag, pp. + 492-504, 1993. + +Authors' Addresses + + Markus Friedl + EMail: markus@openbsd.org + + + Niels Provos + EMail: provos@citi.umich.edu + + + William A. Simpson + EMail: wsimpson@greendragon.com + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Friedl, et al. Standards Track [Page 9] + +RFC 4419 SSH DH Group Exchange March 2006 + + +Full Copyright Statement + + Copyright (C) The Internet Society (2006). + + This document is subject to the rights, licenses and restrictions + contained in BCP 78, and except as set forth therein, the authors + retain all their rights. + + This document and the information contained herein are provided on an + "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS + OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET + ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, + INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE + INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED + WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. + +Intellectual Property + + The IETF takes no position regarding the validity or scope of any + Intellectual Property Rights or other rights that might be claimed to + pertain to the implementation or use of the technology described in + this document or the extent to which any license under such rights + might or might not be available; nor does it represent that it has + made any independent effort to identify any such rights. Information + on the procedures with respect to rights in RFC documents can be + found in BCP 78 and BCP 79. + + Copies of IPR disclosures made to the IETF Secretariat and any + assurances of licenses to be made available, or the result of an + attempt made to obtain a general license or permission for the use of + such proprietary rights by implementers or users of this + specification can be obtained from the IETF on-line IPR repository at + http://www.ietf.org/ipr. + + The IETF invites any interested party to bring to its attention any + copyrights, patents or patent applications, or other proprietary + rights that may cover technology that may be required to implement + this standard. Please address the information to the IETF at + ietf-ipr@ietf.org. + +Acknowledgement + + Funding for the RFC Editor function is provided by the IETF + Administrative Support Activity (IASA). + + + + + + + +Friedl, et al. Standards Track [Page 10] + -- cgit v1.2.3