DH Group Exchange in SSH (RFC 4419) - Avoiding Backsdoors

["Mark D. Baushke" <mdb%juniper.net@localhost>]

Hi,

Question:

Should RFC 4419 - "Diffie-Hellman Group Exchange for the Secure Shell
(SSH) Transport Layer Protocol" be deprecated?

Background:

The paper "How to Backdoor Diffie-Hellman" by David Wong
https://eprint.iacr.org/2016/644.pdf describes two ways
of creating a Nobody-But-Us (NOBUS) Diffie-Hellman backdoor:

  * a composite modulus with a hidden subgroup (CMHS) and

  * a composite modulus with a smooth order

To the best of my understanding, the only place that the SSH protocol
could be impacted by the attacks suggested in this paper today are in
the use of the RFC 4419 "diffie-hellman-group-exchange-sha1" and
"diffie-hellman-group-exchange-sha256" key exchanges.

The mitigation for this kind of attack would seem to be to use safe
primes of the form 2q + 1 with q prime and ensure that the generator g
has a q-ordered subgroup (g^q = 1 mod p) (c.f. FIPS 186-4 A.2.2
Assurance of the Validity of the Generator g). The checks for Attacks on
Prime Order Subgroups is also discussed in the "Security Issues in the
Diffie-Hellman Key Agreement Protocol" by Jean-Francois Raymond and
Anton Stiglic of Zero-Knowledge Systems Inc., IEEE Transactions on
Information Theory 22-January-2002 (google shows a few URLs for this one
including: http://instantlogic.net/publications/DiffieHellman.pdf )

However, with RFC 4419, only p,g are sent over the wire. So, any
attempts to prove that the Diffie Hellman pramaeters are non-trivial, or
make assumptions that q and p are computationally related.

Indeed, if someone is generating a Lim-Lee prime p (which is a very
efficient way to generate a composite prime), then q is unrelated to p
and would be unavailable to validate the generator g.

I am wondering if David Wong's paper is enough to recommend against
using the RFC 4419 ephemeral DH parameters entirely? Or, is there some
useful way to quickly validate that the server DH parameters are valid
from the client?

I would appreciate any feedback you may have on this matter.

-- 
Mark D. Baushke
mdb%juniper.net@localhost