Subject: [Curdle] RFC 4253 possible errata

From: "Mark D. Baushke" <[email-masked]>
Date: Wed, 21 Jun 2017 11:20:05 -0700

Hi Folks,

While working with the IETF AD Eric Rescorla <[email-masked]> doing the AD
review of draft-ietf-curdle-ssh-modp-dh-sha2, the topic came up of
validation of the Diffie-Hellman public key on both client and server
(peers).

The RFC 4253 Section 8 writes:

|8.  Diffie-Hellman Key Exchange
|
|   The Diffie-Hellman (DH) key exchange provides a shared secret that
|   cannot be determined by either party alone.  The key exchange is
|   combined with a signature with the host key to provide host
|   authentication.  This key exchange method provides explicit server
|   authentication as defined in Section 7.
|
|   The following steps are used to exchange a key.  In this, C is the
|   client; S is the server; p is a large safe prime; g is a generator
|   for a subgroup of GF(p); q is the order of the subgroup; V_S is S's
|   identification string; V_C is C's identification string; K_S is S's
|   public host key; I_C is C's SSH_MSG_KEXINIT message and I_S is S's
|   SSH_MSG_KEXINIT message that have been exchanged before this part
|   begins.
|
|   1. C generates a random number x (1 < x < q) and computes
|      e = g^x mod p.  C sends e to S.
|
...elided...

|   Values of 'e' or 'f' that are not in the range [1, p-1] MUST NOT be
|   sent or accepted by either side.  If this condition is violated, the
|   key exchange fails.

...elided...

The z in range [1, p-1] notation, specifies a closed interval which
includes the end points which is equivant to 1 <= z <= p-1. The (1, p-1)
notation specifies an open interval which excludes the endpoints 1 < z <
p-2.

Eric noted that https://tools.ietf.org/rfcmarkup?rfc=7919#section-5.1
uses open endpoints.

Eric suggested that my draft should include text that is similar to the
ext in the RFC 7919 to correct this errata.

Before I make such a change, I wish understand if what folks have been
using for the test in their implementations and get a consensus on such
a change.

	Thank you,
	-- Mark

---

From: Ron Frederick <[email-masked]>
Date: Wed, 21 Jun 2017 11:41:35 -0700

Hi Mark,

> notation specifies an open interval which excludes the endpoints 1 < z <

[Ron] I don’t understand the “p-2” here. Is that a typo? Also, if you want to convert from the closed range [1, p-1], shouldn’t that to be to an open range of (0, p), which would correspond to “0 < z < p”?

> ext in the RFC 7919 to correct this errata.

[Ron] I see RFC 7919 refers to a closed range [2, p-2]. This would be a change from what is allowed by RFC 4253 today.

> using for the test in their implementations and get a consensus on such

[Ron] In asyncssh, the test I’m doing on e & f is “1 <= e < p” and “1 <= f < p", which is essentially the half-open range of [1, p) that is equivalent to the closed range [1, p-1] listed in RFC 4253.
-- 
Ron Frederick
[email-masked]

---

From: "Mark D. Baushke" <[email-masked]>
Date: Wed, 21 Jun 2017 12:32:00 -0700

Hi Ron,

Ron Frederick <[email-masked]> writes:

> [Ron] I don’t understand the “p-2” here. Is that a typo? 

Yes, I guess I should be careful when I touch-type numerals. It is
intended to be p-1 in both cases.

> Also, if you want to convert from the closed range [1, p-1], shouldn’t
> that to be to an open range of (0, p), which would correspond to “0 <
> z < p”?

Yes.

That is the error. I believe it should either have been written as [2,
p-2] or (1, p-1).

If we look at other sources such as NIST SP 800-56A revision 2, page 36
section 5.6.2.3.1 we see the verification is [2, p-2] which is also used
in RFC 7919.

> [Ron] I see RFC 7919 refers to a closed range [2, p-2]. This would be
> a change from what is allowed by RFC 4253 today.

Yes.

> [Ron] In asyncssh, the test I’m doing on e & f is “1 <= e < p” and “1
> <= f < p", which is essentially the half-open range of [1, p) that is
> equivalent to the closed range [1, p-1] listed in RFC 4253.

Okay.

This implies that there would need to be an implementation change if we
agree that RFC 4253 use of a closed range is an errata because an open
range was intended. Or, we could agree that narrowing the range is in
the best interests of the DH key exchange.

	-- Mark

---

From: Ron Frederick <[email-masked]>
Date: Wed, 21 Jun 2017 22:31:02 -0700

Hi Mark,

> section 5.6.2.3.1 we see the verification is [2, p-2] which is also used

[Ron] Interesting. I just checked the OpenSSH code, and it looks like it is already enforcing [2, p-2], so that would support considering this to be an error in the RFC, and would also suggest I should change my implementation to avoid picking a value that OpenSSH would reject if I was doing a DH exchange with it.

> the best interests of the DH key exchange.

[Ron] If there’s a mix of implementations out there, that would argue that making all of them use the narrower range would be best. In additional to bringing this in line with RFC 7919, it would help to avoid a rare but possible interoperability problem.
-- 
Ron Frederick
[email-masked]

---

From: denis bider <[email-masked]>
Date: Thu, 22 Jun 2017 02:32:06 -0600

(Removing the SSH mailing list from CC under the presumption that most of
those who are interested are already subscribed to Curdle, and don't want
duplicate messages.)

Correct me if I'm wrong, but I'm not seeing a way that a cooperating
implementation would send "e" or "f" that violates this requirement in
either way. The likelihood of accidentally generating e=1, or f=p-1, is
orders of magnitude lower than accidentally generating one of Satoshi's
Bitcoin private keys. If I got a genie lamp that lets me generate numbers
like this on accident, I'd rather generate Satoshi's private key.

So therefore, it's not meaningful to talk about compatibility here. It's
meaningful to talk about contributing behavior ("e" or "f" is random),
non-contributing behavior ("e" or "f" is fixed but valid), or sabotaging
the DH key exchange ("e" or "f" is invalid and results in an insecure key
exchange).

Which view in particular are we talking about here? Because valid
implementations (contributing or non-contributing) will not be sending f=1
or e=p-1. Ever.

denis

On Wed, Jun 21, 2017 at 12:20 PM, Mark D. Baushke <[email-masked]> wrote:

> _______________________________________________
> Curdle mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/curdle
>

---

From: "Mark D. Baushke" <[email-masked]>
Date: Thu, 22 Jun 2017 01:51:00 -0700

Hi denis,

> like this on accident, I'd rather generate Satoshi's private key.

Yes, I would NOT expect an honest and correct implementation to send the
public key of e=1 or e=p-1 (or f=1 or f=p-1). The check is there to
detect and fail interoperability from malicous peers.

> implementations (contributing or non-contributing) will not be sending f=1

I believe we are likely talking about a malicious peer or an invalid
implementation.

I am asking if it desirable that I include the following text into
draft-ietf-curdle-ssh-modp-dh-sha2-07

| 4.  Checking the Peer's DH Public Key
| 
|    As specified in [RFC4253] Section 3 contains a small errata when
|    checking e (client public key) and f (server public key) values:
| 
|       Values of 'e' or 'f' that are not in the range [1, p-1] MUST NOT
|       be sent or accepted by either side.  If this condition is
|       violated, the key exchange fails.
| 
|    The problem is that the range should have been an open bound (1, p-1)
|    which means 1 < e < p-1 and 1 < f < p-1.  This document ammends that
|    document text as follows:
| 
|       DH Public key values MUST be checked and both 1 < e < p-1 and 1 <
|       f < p-1 and values not within these bounds MUST NOT be sent or
|       accepted by either side.  If this condition is violated, the key
|       exchange fails.

Or, perhaps:

       Values of 'e' or 'f' that are not in the range [2, p-2] MUST NOT
       be sent or accepted by either side.  If this condition is
       violated, the key exchange fails.

| 
|    This simple check ensures that the remote peer is properly behaved
|    and isn't forcing the local system into the 2-element subgroup.

Or, perhaps some other set of text that basically specifies the
tightening of boundary checks.

I ask this as Eric was concerned that argument validation was not being
properly handled for Diffie-Hellman MODP groups as compared to how TLS
does the job.

	Thanks,
	-- Mark

---

From: denis bider <[email-masked]>
Date: Thu, 22 Jun 2017 02:54:47 -0600

In this case I think Eric's concern is well-founded, and the errata should
be added. It appears there is no interoperability issue, there is simply a
failure of the spec to correctly document effective defense against
malicious peers. This needs to be corrected.

---

From: "Mark D. Baushke" <[email-masked]>
Date: Thu, 22 Jun 2017 02:01:47 -0700

> malicious peers. This needs to be corrected.

Thank you. This is my belief as well.

Does anyone have a preferences between these equivalent notations?

     1 < e < p-1

     (1, p-1)

     2 <= e <= p-2

     [2, p-2]

for the Errata as a replacement for [1, p-1] currently in the RFC4253?

	-- Mark

---

From: denis bider <[email-masked]>
Date: Thu, 22 Jun 2017 03:19:02 -0600

2 <= e <= p-2 appears to be least ambiguous to me. My second choice would
be [2, p-2].

If these closed forms are misinterpreted as open forms, the ramifications
are minimal (there will be some implementation that won't accept e=2, big
deal). But if the open forms are misinterpreted as closed forms, the
ramifications are substantial (there will be implementations that will
accept e=1, which is a security risk).

---

From: "Salz, Rich" <[email-masked]>
Date: Thu, 22 Jun 2017 12:25:23 +0000

I agree, please use 2 <= e <= p-2

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 22 Jun 2017 07:49:21 -0700

FWIW, 7919 uses "1 < Y < p-1"

-Ekr

---

From: Daniel Migault <[email-masked]>
Date: Thu, 22 Jun 2017 11:05:42 -0400

(1, p-1) might be ambiguous. As far as I am concerned, I am more used to
the ]1, p-1[ notation. <= vs < notation does not seem ambiguous. I tend to
prefer < but only for aesthetic.
Yours,
Daniel