Network Working Group M. Friedl
Request for Comments: 4419 N. Provos
Category: Standards Track W. Simpson
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 (C) The Internet Society (2006).
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
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]