Network Working Group Markus Friedl
INTERNET-DRAFT Niels Provos
Expires in six months William A. Simpson
December 2002
Diffie-Hellman Group Exchange for the SSH Transport Layer Protocol
draft-ietf-secsh-dh-group-exchange-03.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-2002 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 December 2002
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 December 2002
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 December 2002
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 December 2002
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 December 2002
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
[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
Friedl/Provos/Simpson expires in six months [Page 6]
INTERNET DRAFT December 2002
[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 December 2002
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]
------- End of Forwarded Message
