Subject: Re: deaft-gree-sedsh-ecc-08: small correction

From: Douglas Stebila <[email-masked]>
Date: Fri, 13 Aug 2010 16:02:45 +1000

Damien, I'm confused about this email I just received from you.  The draft you're referring to, draft-green-secsh-ecc-08, became RFC 5656 back in December 2009.  At this point, the only ways to make changes are either through errata or through a new document that updates/obsoletes the existing document.

To respond to your individual points:

On 2010-Aug-13, at 3:29 PM, Damien Miller wrote:

> Why not drop ECMQV from the draft entirely? AFAIK it is patented,
> which is enough to stop us (OpenSSH) from implementing it. I think
> new KEX methods need a very good justification, since they represent
> a significant part of the pre-auth attack surface.

ECMQV is an optional element of RFC 5656.  We received expressions of interest for including this from some parties, and were aware of concerns like the one you raised, and as such went for making it an optional element.  

> Also on the -08 draft, shouldn't the client and server in ECDH reject
> public keys from the peer that are points at infinity? Are there
> other degenerate values to worry about?

RFC 5656 requires that all elliptic curve public keys be validated after being received, and cites the validation algorithm from Section 3.2.2 from SEC1, which for example includes rejecting the point at infinity.

Douglas

---

From: Damien Miller <[email-masked]>
Date: Fri, 13 Aug 2010 15:29:46 +1000 (EST)

On Tue, 16 Jun 2009, Igoe, Kevin M. wrote:

> In the Introduction to draft-green-secsh-ecc-08 we find
>  
>    In the interest of adding Suite B algorithms to SSH this document
>    adds three ECC Suite B algorithms to the Secure Shell arsenal:
>    Elliptic Curve Menezes-Qu-Vanstone (ECMQV), Elliptic Curve Diffie-
>    Hellman (ECDH), and Elliptic Curve Digital Signature Algorithm
>    (ECDSA), as well as utilizing the SHA2 family of secure hash
>    algorithms.
> Slight error here: ECMQV is no longer part of Suite B.  For sake of
> correctness, I'd suggest something like the following:
>  
>    In the interest of adding Suite B algorithms to SSH this document
>    adds two ECC Suite B algorithms to the Secure Shell arsenal:
>    Elliptic Curve Diffie-Hellman (ECDH), and Elliptic Curve Digital  
>    Signature Algorithm (ECDSA), as well as utilizing the SHA2 family
>    of secure hash algorithms. Additonally, support is provided for
>       Elliptic Curve Menezes-Qu-Vanstone (ECMQV).

-d

---

From: Damien Miller <[email-masked]>
Date: Fri, 13 Aug 2010 23:38:30 +1000 (EST)

On Fri, 13 Aug 2010, Douglas Stebila wrote:

> Damien, I'm confused about this email I just received from you. The
> draft you're referring to, draft-green-secsh-ecc-08, became RFC
> 5656 back in December 2009. At this point, the only ways to make
> changes are either through errata or through a new document that
> updates/obsoletes the existing document.

sorry, I hadn't realised that the draft had matriculated.

I'm thinking of implementing the ECDH and ECDSA parts of the draft when
I return from the USA. Is anyone interested in some interop testing?

-d

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Fri, 13 Aug 2010 09:05:45 -0400

You are correct, MQV was thrown out of Suite B some time ago
and we should rephrase this statement to reflect that.  I
view leaving MQV in this draft as harmless.  Yes, currently
there are Intellectual Property issues involving MQV, but that
may well change in the future.

As to checking for the point at infinity in ECDH, I'd
rather have that issue addressed in a document that is
clearly directed at ECDH rather than having it hidden 
in a document that only peripherally touches ECDH.
I'll be putting out a "Suite B for Secure Shell" document
in the near future and plan to cover such issues in there.

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On
> Behalf Of Damien Miller
> Sent: Friday, August 13, 2010 1:30 AM
> To: Igoe, Kevin M.; Douglas Stebila
> Cc: [email-masked]
> Subject: Re: deaft-gree-sedsh-ecc-08: small correction
>

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Fri, 13 Aug 2010 10:55:13 -0400

Thanks Peter, I'm happy to find this issue has been already been
addressed.

> From: Peter Gutmann [mailto:[email-masked]]
> Sent: Friday, August 13, 2010 10:37 AM
> To: [email-masked]; [email-masked]; Igoe, Kevin M.
> Cc: [email-masked]
> Subject: RE: deaft-gree-sedsh-ecc-08: small correction
> 
> "Igoe, Kevin M." <[email-masked]> writes:
> 
> >As to checking for the point at infinity in ECDH, I'd rather have
that
> issue
> >addressed in a document that is clearly directed at ECDH rather than
> having
> >it hidden in a document that only peripherally touches ECDH. I'll be
> putting
> >out a "Suite B for Secure Shell" document in the near future and plan
> to cover
> >such issues in there.
> 
> Shouldn't this check be automatic anyway for a (correct)
> implementation?  The
> standard that defines ECC use (keygen, key checking, data formats,
> etc),
> X9.62, already mandates this check (although for some reason the RFC
> references it as informative rather than normative and gives the SECG
> doc as
> the primary reference when pretty much everything else uses X9.62, and
> AFAIK
> the SECG stuff was derived from the earlier X9.62 work), so if you
> implement
> ECC correctly than you already do this check.  In any case the text
> says:
> 
>    All elliptic curve public keys MUST be validated after they are
>    received.  An example of a validation algorithm can be found in
>    Section 3.2.2 of [SEC1].  If a key fails validation, the key
> exchange
>    MUST fail.
> 
> so it appears this is already covered.  The checks I have, from X9.62,
> are:
> 
> 	/* Verify that the public key parameter sizes are valid:
> 
> 		qx, qy >= MIN_PKCSIZE_ECC, qx, qy <= p - 1 */
> 
> 	/* Verify that Q is not the point at infinity */
> 
> 	/* Verify that qx, qy are elements in the field Fq, i.e. in the
> range
> 	   0...p - 1 */
> 
> 	/* Verify that qy^2 is congruent to qx^3 + a*qx + b (mod p) */
> 
> 	/* Verify that n * Q is the point at infinity */
> 
> If that's sufficient for checking Q then the existing doc already
> covers
> things.
> 
> Peter.

---

From: "Igoe, Kevin M." <[email-masked]>
Date: Fri, 13 Aug 2010 10:51:39 -0400

Opps, mea culpa.  I see are referring to draft-green-secsh-ecc-08, now
known as RFC 5656.  My responses were in reference to
draft-igoe-secsh-x509v3-05.

Given it has already been published as an RFC, the inclusion of MQV is
Suite B is an historical artifact that reflects the early genesis of
Suite B, and as such can stand.

The point at infinity is a worthy observation perhaps best 
addressed by an errata? I'm not terribly familiar with the IESG errata
process.

> Behalf Of Igoe, Kevin M.
> Sent: Friday, August 13, 2010 9:06 AM
> To: Damien Miller; Douglas Stebila
> Cc: [email-masked]

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 14 Aug 2010 02:37:26 +1200

"Igoe, Kevin M." <[email-masked]> writes:

>As to checking for the point at infinity in ECDH, I'd rather have that issue
>addressed in a document that is clearly directed at ECDH rather than having
>it hidden in a document that only peripherally touches ECDH. I'll be putting
>out a "Suite B for Secure Shell" document in the near future and plan to cover
>such issues in there.

Shouldn't this check be automatic anyway for a (correct) implementation?  The
standard that defines ECC use (keygen, key checking, data formats, etc),
X9.62, already mandates this check (although for some reason the RFC
references it as informative rather than normative and gives the SECG doc as
the primary reference when pretty much everything else uses X9.62, and AFAIK
the SECG stuff was derived from the earlier X9.62 work), so if you implement
ECC correctly than you already do this check.  In any case the text says:

   All elliptic curve public keys MUST be validated after they are
   received.  An example of a validation algorithm can be found in
   Section 3.2.2 of [SEC1].  If a key fails validation, the key exchange
   MUST fail.

so it appears this is already covered.  The checks I have, from X9.62, are:

	/* Verify that qx, qy are elements in the field Fq, i.e. in the range
	   0...p - 1 */

If that's sufficient for checking Q then the existing doc already covers
things.

Peter.

---

From: Damien Miller <[email-masked]>
Date: Wed, 18 Aug 2010 07:46:05 +1000 (EST)

> 		qx, qy >= MIN_PKCSIZE_ECC, qx, qy <= p - 1 */

What do you use as this minimium? AFAIK SEC1 doesn't specify this check, but
I guess it should be at least 2 and probabalistically something less than
p/4 or so (for p of a hundred bits or more)

-d

---

From: Damien Miller <[email-masked]>
Date: Wed, 18 Aug 2010 12:35:32 +1000 (EST)

> p/4 or so (for p of a hundred bits or more)

oops, I meant "a number about 1/4 the length of p"

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 18 Aug 2010 21:32:29 +1200

>oops, I meant "a number about 1/4 the length of p"

I use ( 256 - 192 ) bits, assuming that a value for which the first 64 (or
more) bits are zero is a sign of a problem rather than just a really unlikely
coincidence.  The spec doesn't require this (it could be only two bits long,
with a probability of 2^-254), but it seems like prudent engineering practice
to reject values like this.

Peter.