Subject: New version: draft-green-secsh-ecc-06

From: Douglas Stebila <[email-masked]>
Date: Tue, 14 Apr 2009 11:32:47 +1000

A new version of the draft for elliptic curve cryptography in SSH has  
been posted.

http://www.ietf.org/internet-drafts/draft-green-secsh-ecc-06.txt

The main substantive revision is that ecdsa-sha2 is now using a family  
of identifiers (as ecdh-sha2-* does) to specify the curve at the  
algorithm negotiation stage.

Douglas

---

From: Damien Miller <[email-masked]>
Date: Tue, 14 Apr 2009 14:06:48 +1000 (EST)

On Tue, 14 Apr 2009, Douglas Stebila wrote:

> A new version of the draft for elliptic curve cryptography in SSH has been
> posted.
> 
> The main substantive revision is that ecdsa-sha2 is now using a family of
> identifiers (as ecdh-sha2-* does) to specify the curve at the algorithm
> negotiation stage.

I have to say that I really dislike the Base64(MD5(DER(OID))) encoding
of curve names into the kex method names. Why not just use the SEC names?
Actually, why bake the names into the kex names at all? (as opposed to
sending a curve spec as a parameter).

Do the many ECC patent apply to the methods described in this draft? It
seems to lack any section on IPR.

The "Security Considerations" section talks about the possible need to
replace SHA2 with other algorithms, but the name "sha2" is baked into
the kex method name. Should the hash algorithm be a parameter too?

-d

---

From: Douglas Stebila <[email-masked]>
Date: Tue, 14 Apr 2009 14:43:01 +1000

> of curve names into the kex method names. Why not just use the SEC  

Not all curves have SEC names.  There exist standardized curves that  
have OIDs but not SEC names.

The most relevant curves in my mind are the NIST Suite B curves, which  
are a subset of the NIST curves, which are a subset of the SEC curves,  
which are a subset of all curves with OIDs, which are a subset of all  
curves.  One could draw the line anywhere, and currently the line is  
drawn at OIDs.  I would need more feedback from implementers as to  
whether only SEC curves suffice.  I recognize that for many  
implementers the driving force right now is NSA Suite B compliance,  
which requires only secp256r1 or secp384r1.

As for the Base64(MD5(DER(OID))) encoding: I was told that not all  
OIDs are guaranteed to be sufficiently short to keep the overall  
method name down to no more than 64 characters as required by RFC 4251  
Section 6.  This mechanism guarantees sufficiently short method names  
which are extensible and (almost certainly) unique.

> sending a curve spec as a parameter).

This would require a second round of negotiation, which could fail.   
Suppose that two implementations agreed to use ecdh-sha2 and then in  
the subsequent curve negotiation discovered that they had no common  
set of curves (this may be possible as REQUIRED curves can still be  
disabled by local security policy).  I don't believe SSH has a  
mechanism for dealing with a failed kex method by moving on to the  
next method in the list of mutually supported kex methods, but I could  
be mistaken about that.

(For comparison, when ECC was added to TLS a similar problem arose and  
they used extensions in the client_hello and server_hello messages to  
transport the list of supported curves.

I don't know any way other way around this problem, but if you know of  
one I'd be happy to consider it.

> seems to lack any section on IPR.

Other IETF documents involving ECC, such as RFC 3278 (ECC in CMS) and  
RFC 4492 (ECC in TLS) do not include a discussion speculating on how  
the documents are affected by ECC patents.  I am not a lawyer and do  
not feel qualified to include any speculation of my own in the document.

> the kex method name. Should the hash algorithm be a parameter too?

That's an option, although one that I don't think is worth pursuing at  
this point.  The SHA-3 competition is a long way from being done, so  
SHA-2 is the gold standard right now.  If there's a desire to see  
SHA-3 adopted in SSH, it would not be hard to create a short RFC  
indicating that SHA-3 could be substituted fro SHA-2, and this draft,  
while not explicitly saying how to do it, is very suggestive.

Douglas

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 14 Apr 2009 17:25:36 +1200

Damien Miller <[email-masked]> writes:

>I have to say that I really dislike the Base64(MD5(DER(OID))) encoding of
>curve names into the kex method names. Why not just use the SEC names?

Oh, so it wasn't just me :-).  My reaction to seeing this was "did someone
lose a bet or something...".

>sending a curve spec as a parameter).

This is another case where SSH really needs an extension mechanism like TLS.
In TLS the curve parameters and point formats are negotiated via extensions.

Having said that, in practice everyone (well, among TLS implementors) has 
settled on a small number of popular curves and that's it (which is quite 
convenient, you don't even have to worry about extensions, just go with P256 
and everything'll support it).  I'd define a few fixed names for the 
well-known curves that everyone ends up using (the NIST ones, basically) and 
leave the strange stuff to the usual name@vendor-name mechanism, which is 
exactly what it was meant for.

Peter.

---

From: Douglas Stebila <[email-masked]>
Date: Tue, 14 Apr 2009 15:53:12 +1000

> lose a bet or something...".

As I mentioned, this was a change that my IETF document shepherd asked  
me to make in going from -02 to -03.  I agree it's ugly.

> In TLS the curve parameters and point formats are negotiated via  

I'm afraid that's outside the scope of my lowly draft.  :)

> exactly what it was meant for.

If the consensus on this mailing list is that using a few fixed names  
is fine, then I am willing to make that change.

My preference would be the following:

Method names are ecdh-sha2-[identifier] and ecdsa-sha2-[identifier],  
where [identifier] is
	nistp256 -- REQUIRED (Suite B)
	nistp384 -- REQUIRED (Suite B)
	Base64(MD5(DER(OID))) -- OPTIONAL
with the additional proviso that, if the curve in question is in fact  
nistp256 (== secp256r1) or nistp384 (== secp384r1), then  
implementations MUST use the nistp256/nistp384 naming convention and  
MUST NOT use the Base64(MD5(DER(OID))) naming convention.

The rationale for this compromise is as follows.  It seems as if we  
expect the vast majority of implementations to be aiming for Suite B  
which is nistp256 and nistp384. Those implementations need never worry  
about the ugly names.  For implementations that want to go beyond  
Suite B, they can use the ugly (but universal and extensible) names.

Points for debate:

1) Should the list of named curves be longer, for example, including  
all the NIST curves or all the SEC curves?

2) Should the named curves be named by their NIST name or their SEC  
name?  (nistp256 versus secp256r1)

3) Should we entirely remove the Base64(MD5(DER(OID))) optional  
encoding and entirely leave it to name@vendor-name?  My opinion is  
no:  Although name@vendor-name is the common mechanism for naming  
additional SSH mechanisms, elliptic curves in other standards are  
often named with OIDs which are universal.

Regards,

Douglas

---

From: Peter Gutmann <[email-masked]>
Date: Tue, 14 Apr 2009 18:28:53 +1200

Douglas Stebila <[email-masked]> writes:

>[...]

That sounds sensible.

>1) Should the list of named curves be longer, for example, including all the
>NIST curves or all the SEC curves?

This could be really hard to answer because there isn't enough operational
experience in using these.  I know from TLS that some people seem to be
implementing every curve they can think of, but also that these are a lot of
our-curves-go-to-11 implementations done more to show off the capabilities for
interop purposes rather than everyday use (whoever ships with the most curves
wins).  If you look at the more mainstream implementations they're mostly just
Suite-B and that's it, for example Vista (via MSIE/IIS/whatever) just does
P256, 384, and 521 and that's it.  This is why your suggestion to have the two
Suite-B's (and I'd add 521 to that) as the mandatory-to-support standard is a
good one, you can pretty much assume that everyone will do that anyway.

>2) Should the named curves be named by their NIST name or their SEC name?
>(nistp256 versus secp256r1)

I'd go for NIST for the Suite-B's and SECG for the rest, because they've named
a lot more than NIST has.  This also means that you could define Suite-B's as
mandatory, refer to the SECG names (via "as defined in 'SEC 2:2000' or any
later version") for the remaiming names without explicitly having to catalogue
them all, and then leave the hash as anything-that's-left.

Having said that though I'm still a bit nervous about using the OIDs, there
are all sorts of other odd things you can do with those that could cause
problems, for example there's the "use this with a hash algorithm that's the
largest possible that can be used with the curve without truncation" OID and
the "dance along the wharf slapping people with a dead fish" OID and ... .
Since you can have multiple OIDs for a curve and anything that defines an OID
will also define a curve name, it'd be much easier to just use the name
directly since you're not getting much from the OID except complexity.  If you
really want to be safe, use 'name@source', e.g. curve1@standardsgroupname,
although even then it seems that groups are being careful to choose unique
names.  For example all the SECG names being 'sec' to distinguish them from
other names.

BTW the TLS ECC RFC has a table at the end mapping X9.62 <-> NIST <-> SECG
names for people who need this.

Peter.

---

From: "Timo J. Rinne" <[email-masked]>
Date: Tue, 14 Apr 2009 09:40:02 +0300

> sending a curve spec as a parameter).

I second this opinion warmly.  Method names, whether kex, cipher, mac, 
or compression should (and in my opinion must) be not only readable but 
also human readable.

If a large number of curves is needed and OID really must be used, then 
it should be encoded to ascii in some human readable way e.g. 
"ec-1.2.3.4.5".  Still, SEC names would be much more sensible.

Anyways, if you assign an OID for each new curve, you can as well assign 
an unique symbolic name that also somewhat lists the characteristichs of 
the curve.

> the kex method name. Should the hash algorithm be a parameter too?

Maybe it should but MAC in kex has somewhat specific meaning and maybe 
it should be tied to specific kex name.  I don't have a strong opinion here.

-- 
Timo J. Rinne <[email-masked]>        Valimotie 17       +358 20 500 7000 T
Chief Technology Officer           FIN-00380 Helsinki +358 20 500 7397 F
SSH Communications Security Corp.  Finland            http://www.ssh.com

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 14 Apr 2009 11:05:24 -0400

> seems to lack any section on IPR.

It doesn't need a section on IPR; the IETF does not take a position on IPR 
claims and doesn't formalize such claims in its documents.  If the authors 
hold IPR on the ECC methods referenced in this document, they're obligated 
to disclose it through the IETF IPR disclosure process, not by mentioning 
it in a document.  I believe that one or more holders of ECC-related IPR 
have done so already, though probably not with respect to this document, 
which is relatively new.

It is appropriate for a working group to discuss IPR issues when deciding 
whether to adopt a particular approach, but this is not a working group 
document and the secsh working group no longer exists.  So, feel free to 
ask questions about the IPR issues, but the document does not need a 
section addressing them.

-- Jeff

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 14 Apr 2009 11:10:39 -0400

--On Tuesday, April 14, 2009 03:53:12 PM +1000 Douglas Stebila 
<[email-masked]> wrote:

> As I mentioned, this was a change that my IETF document shepherd asked me
> to make in going from -02 to -03.  I agree it's ugly.

That was me.  The particular encoding I suggested is the same one we used 
in gss-keyex for GSS-API mechanisms, which are also named by OID's.  I 
agree it's ugly, but I don't know of any better alternatives (ironically, 
the SASL WG is working on a better alternative for GSS-API mechanisms, too 
late for us, but it doesn't apply to OID's in general).

It would be fine to name the kex methods by names, if there are such, but 
using an OID encoded in ASCII won't work; OID's can be arbitrarily long and 
you'll quickly run out of space.

> If the consensus on this mailing list is that using a few fixed names is
> fine, then I am willing to make that change.
>
> nistp256 (== secp256r1) or nistp384 (== secp384r1), then implementations
> MUST use the nistp256/nistp384 naming convention and MUST NOT use the
> Base64(MD5(DER(OID))) naming convention.
>
> about the ugly names.  For implementations that want to go beyond Suite
> B, they can use the ugly (but universal and extensible) names.

Note that this is similar to the compromize we made for mod-p DH keyex, 
where we have fixed names for a few groups, plus a "group exchange" method 
that allows negotiation of a specific group once the method has been 
selected.  However, that does have the two-level negotiation problem.

-- Jeff

---

From: Jeffrey Hutzelman <[email-masked]>
Date: Tue, 14 Apr 2009 11:14:17 -0400

--On Tuesday, April 14, 2009 02:43:01 PM +1000 Douglas Stebila 
<[email-masked]> wrote:

> SHA-2 is the gold standard right now.  If there's a desire to see SHA-3
> adopted in SSH, it would not be hard to create a short RFC indicating
> that SHA-3 could be substituted fro SHA-2, and this draft, while not
> explicitly saying how to do it, is very suggestive.

Well, you'd have to not only substitute SHA-3 for SHA-2, but also change 
the names, since the two wouldn't interoperate.

Including the hash in the kex name is consistent with what we have done in 
other SSH kex methods, and avoids a multi-level negotiation problem.

-- Jeff

---

From: James Blaisdell <[email-masked]>
Date: Tue, 14 Apr 2009 09:36:35 -0700

I've implemented draft-06: ECDH and ECDSA.  It was very simple to refactor TLS EC code to support SSH.  The base64 encoding is ugly, but I agree it's necessary.  IMO - The @domain approach is uglier and the thought of ASCII encoding OIDs is even nastier.  Since the base64 encoded OID string is static, I don't bother to decode, I simply know this string maps to a curve.  

Earlier on this thread, it was suggest that perhaps the client and server could fall back, if the host key type did not match.  This would add many more messages to the protocol.  I recommended to Douglas to append the base64 to the base type (i.e. ecdsa-sha2-<BASE64>) to avoid this issue.  I think it's the correct approach, and most true to SSH protocol.  Adding TLS-like hello extension would be messier, and break interoperability with all preexisting implementations in the field.  

It seems the base64 oid is the only controversial item in this draft.  If so, it's a minor issue.  I would very much like to see this draft version move to RFC.  It's well written, easy to implement, matches other SSH RFCs in naming convention and feels complete imo.  

Thank you,

James

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Jeffrey Hutzelman
Sent: Tuesday, April 14, 2009 8:11 AM
To: Douglas Stebila; Peter Gutmann
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: Re: New version: draft-green-secsh-ecc-06

-- Jeff

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 16 Apr 2009 00:50:09 +1200

>you'll quickly run out of space.

They can in theory be arbitrarily long, but no-one ever uses them that way,
the longest ones that I'm aware of in crypto use are 20-25 characters, which
puts the extreme, worst-case OIDs in the same range as standard MD5-in-ASCII.

If they're OIDs encoded as ASCII then if someone sends you a new value that
you've never seen before all you need to do is cut and paste it into Google to
find the curve.  If you put the binary value through a *one-way* hash function
there's no way you can ever figure out what some string of base64 that you're
seeing actually started out as, and therefore no way to locate the curve
unless you've already got a copy to hand whose hash you can compare with (and
even then you need to do a brute-force search to figure out which value's hash
you're seeing).  Non-reversible hash functions are great for what they were
designed for, creating fingerprints of documents for signing.  They're less
useful when you need to map them back to the data they were created from.

Peter.

---

From: James Blaisdell <[email-masked]>
Date: Wed, 15 Apr 2009 06:11:40 -0700

Hello,

For my implementation, it would be trivial to have some ECDH/ECDSA methods name with ASCII OID, an English name, or a Base64 encoded OID.  I would imagine most people would use a table driven model, as we have done.  The first field is debug string name, second is the on the wire algo negotiation string, length of algo string, etc.  I simply need to change that one field, so mixing would be fine --- some could use one naming convention and others could use the base64 for future proofing.  

Here is a row from my table:

    { (sbyte *)"ecdh-sha2-secp521r1", (sbyte *)"ecdh-sha2-h/SsxnLCtRBh7I9ATyeB3A==",   34, cid_EC_P521, &ecdhMethods,      &sshHandshakeSHA512, secp521r1_OID, kTransReceiveECDH, kReduxTransReceiveECDH },

Here are the beauty contestants:
    { (sbyte *)"ecdh-sha2-secp256r1", (sbyte *)"ecdh-sha2-scep256r1",                  19, cid_EC_P256, &ecdhMethods,      &sshHandshakeSHA256, secp256r1_OID, kTransReceiveECDH, kReduxTransReceiveECDH },
    { (sbyte *)"ecdh-sha2-secp256r1", (sbyte *)"ecdh-sha2-1.2.840.10045.3.1.7",        29, cid_EC_P256, &ecdhMethods,      &sshHandshakeSHA256, secp256r1_OID, kTransReceiveECDH, kReduxTransReceiveECDH },
    { (sbyte *)"ecdh-sha2-secp256r1", (sbyte *)"ecdh-sha2-9UzNcgwTlEnSCECZa7V1mw==",   34, cid_EC_P256, &ecdhMethods,      &sshHandshakeSHA256, secp256r1_OID, kTransReceiveECDH, kReduxTransReceiveECDH },

With table driven approach, I can actually leave all three of these naming conventions in the same table.  Mixing would be fine.  This seems to be more of cosmetic question than technical issue.  Is it A, B or C?  

Thank you,

James

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of Peter Gutmann
Sent: Wednesday, April 15, 2009 5:50 AM
To: [email-masked]; [email-masked]; [email-masked]
Cc: [email-masked]; [email-masked]
Subject: Re: New version: draft-green-secsh-ecc-06

Peter.