Diffie-Hellman Group Exchange for the Secure Shell (SSH) Transport Layer Protocol
RFC 4419

Document Type RFC - Proposed Standard (March 2006; Errata)
Updated by RFC 8270
Authors Markus Friedl  , Niels Provos  , William Simpson 
Last updated 2018-12-08
Stream IETF
Formats plain text html pdf htmlized bibtex
Stream WG state WG Document
Document shepherd No shepherd assigned
IESG IESG state RFC 4419 (Proposed Standard)
Consensus Boilerplate Unknown
Telechat date
Responsible AD Russ Housley
Send notices to sommerfeld@east.sun.com
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).


   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",
   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
Show full document text