Subject: [Curdle] DH Group Exchange in SSH (RFC 4419) - Avoiding Backsdoors

From: "Mark D. Baushke" <[email-masked]>
Date: Thu, 29 Sep 2016 07:47:27 -0700

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
[email-masked]

---

From: Damien Miller <[email-masked]>
Date: Fri, 30 Sep 2016 03:28:54 +1000 (AEST)

> of creating a Nobody-But-Us (NOBUS) Diffie-Hellman backdoor:

NOBUS backdoors aren't the only concern; another motivation was
logjam-style precomputation attacks.

-d

---

From: "Mark D. Baushke" <[email-masked]>
Date: Thu, 29 Sep 2016 12:22:54 -0700

Hi Damien,

> logjam-style precomputation attacks.

Yes, the creation of a new set of DH parameters allows us to avoid
logjam precomputation attacks against a well known set of DH groups.

That said, with NOBUS, how is an SSH client able to identify improper
ephemeral DH parameters that have been intesionally weakened?

Had RFC4419 sent all three of p,q,g to the client, then the client would
may have been able to do more validity checks.

However, RFC 4419 does NOT send q AND the methods to select g as given
in the RFC is not always going to generate a q-orded subgroup of p. 

If g is not able to generate a proper q-ordered subgroup value, then
concerns of NOBUS arise and in turn means that an attacker may be able
to learn the parity of the secret (thus losing only) one bit of
security. However, a misconfigured g could also be an indication that
there is a NOBUS DH backdoor in the server connection.

Moving to the MODP group16 for DH key exchange reduces the ability for a
full precomputation logjam type attack.

So, I am asking if it is time to deprecate the RFC 4419 kex methods.

Failing that, what may be done to enhance a RFC4419bis to handle both
logjam and NOBUS attack vectors?

	Thanks,
	-- Mark

---

From: Damien Miller <[email-masked]>
Date: Fri, 30 Sep 2016 15:41:27 +1000 (AEST)

> ephemeral DH parameters that have been intesionally weakened?

I think there's little point - a peer that wants to leak has myraid
ways to do so. E.g. it could leak keys via nonces, random padding, DH
public values, optional packet padding, etc.

Leaking by backdooring DH groups is possibly the worst way to do it -
the only reason they can't be properly tested by a client is that its
too expensive to do so at connection time. That doesn't mean that it
couldn't be done post-hoc or even passively, since the values are sent
in the clear (at least for the inital KEX).

That's not the case with the other leak paths. E.g. leaking a PRNG
seed by encrypting it with a public key and putting it in the KEXINIT
nonce is undetectable on the wire and NOBUS as far as you trust your PK
crypto.

-d

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 30 Sep 2016 06:38:59 +0000

Mark D. Baushke <[email-masked]> writes:

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

No.

If you're worried about a malicious server then you'd really have to deprecate
RFCs 4251 to 4253, since only that will protect you from one.

Peter.