Subject: [TLS] ECC cipher suites with explicit characteristic 2 curve

From: Juho Vähä-Herttua <[email-masked]>
Date: Fri, 02 Jul 2010 14:21:15 +0300

Hi,

I've been reading through the http://www.rfc-editor.org/rfc/rfc4492.txt 
specification about using ECC cipher suites. The specification supports 
three types of curves: explicit_prime, explicit_char2 and named_curve. 
 From what I've seen it's quite common for implementations to only 
support some of the named curves. Firefox seems to only offer three 
prime based curves secp256r1, secp384r1 and secp521r1, which are 
apparently the same three curves that are supported by the Microsoft CNG 
cryptography API.

That makes my question seem pretty theoretical, but in RFC 4492 the 
ECParameters structure included in ServerKeyExchange is defined as:

enum { ec_basis_trinomial, ec_basis_pentanomial } ECBasisType;

struct {
     ECCurveType    curve_type;
     select (curve_type) {
         case explicit_prime:
             opaque      prime_p<1..2^8-1>;
             ECCurve     curve;
             ECPoint     base;
             opaque      order<1..2^8-1>;
             opaque      cofactor<1..2^8-1>;
         case explicit_char2:
             uint16      m;
             ECBasisType basis;
             select (basis) {
                 case ec_trinomial:
                     opaque  k<1..2^8-1>;
                 case ec_pentanomial:
                     opaque  k1<1..2^8-1>;
                     opaque  k2<1..2^8-1>;
                     opaque  k3<1..2^8-1>;
             };
             ECCurve     curve;
             ECPoint     base;
             opaque      order<1..2^8-1>;
             opaque      cofactor<1..2^8-1>;
         case named_curve:
             NamedCurve namedcurve;
     };
} ECParameters;

I'm putting emphasis on the ECBasisType, because it is included in the 
ECParameters struct but the values for ec_basis_trinomial and 
ec_basis_pentanomial are not defined at all. I don't see how explicit 
characteristic 2 curves can be transferred correctly without knowing the 
values for ECBasisType. Am I missing something, or is this again one 
specification detail that no one has bothered to even try to implement?

Juho

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 02 Jul 2010 23:49:03 +1200

=?ISO-8859-1?Q?Juho_V=E4h=E4-Herttua?= <[email-masked]> writes:

>Am I missing something, or is this again one specification detail that no one
>has bothered to even try to implement?

I've never found a server that doesn't do the NIST curves, and the various
toothpicks-and-rubber-bands options in RFC 4492 are such a pain to implement
that it's easiest not to (it goes beyond just the TLS side, if you're using
nonstandard curves then you also need to implement a huge amount of ECC
parameter-generation and checking code as per X9.62, and then explain why
you're using your own homebrew parameters rather than the standards-body
blessed ones, and hope that you didn't make a mistake anywhere in your code,
and ...).  I haven't looked at every possible implementation out there, but
I'd guess your comment above isn't too far off the mark.

Maybe future versions of the spec could contain some hints to implementers, 
MUST <NIST named curves>, MAY <other named curves>, PROBABLY REALLY SHOULDN'T 
<anything else>.

Peter.

---

From: Juho Vähä-Herttua <[email-masked]>
Date: Fri, 02 Jul 2010 15:22:50 +0300

> I'd guess your comment above isn't too far off the mark.

Exactly, that's why I wouldn't want to support the explicit curves at 
all, and I don't see why they were added to the specification in the 
first place... My goal is to implement as much of the TLS functionality 
as possible, to find possible flaws in the spec and to work as something 
to test other implementations against.

> MUST<NIST named curves>, MAY<other named curves>, PROBABLY REALLY SHOULDN'T
> <anything else>.
>    

I wouldn't go that far, since I understand NIST recommends curves for 
192, 224, 256, 384 and 521 bits. However, as mentioned earlier, only the 
latter three are widely supported by existing implementations. Adding 
NIST named curves as MUST would mean supporting the 192 and 224 bit 
versions as well, which might become a problem if existing cryptography 
implementations are used. Based on my knowledge I think having the other 
three as a MUST would not be a bad idea at all.

But nevertheless, the ECBasisType issue should really be fixed. It is 
basically something as simple as:

- enum { ec_basis_trinomial, ec_basis_pentanomial } ECBasisType;
+ enum { ec_basis_trinomial(1), ec_basis_pentanomial(2), (255) } ECBasisType;

Adding the explicit curves as SHOULDN'T would just be a nice plus. Right 
now the RFC lists named_curve as the last curve option, when in fact 
that is the recommended and the most common option. That is very 
confusing for someone who's not familiar with ECC and commonly supported 
curves in general.

Juho

---

From: Adam Langley <[email-masked]>
Date: Fri, 2 Jul 2010 09:40:02 -0400

On Fri, Jul 2, 2010 at 8:22 AM, Juho Vähä-Herttua <[email-masked]> wrote:
> I wouldn't go that far, since I understand NIST recommends curves for 192,
> 224, 256, 384 and 521 bits. However, as mentioned earlier, only the latter
> three are widely supported by existing implementations. Adding NIST named
> curves as MUST would mean supporting the 192 and 224 bit versions as well,
> which might become a problem if existing cryptography implementations are
> used. Based on my knowledge I think having the other three as a MUST would
> not be a bad idea at all.

NIST defines 10 curves I believe: the five you mentioned and five more
binary field curves.

I'm a little surprised that you found that Firefox didn't offer the
192 and 224 bit prime curves. Last time I checked, the code was in
NSS. But maybe they're disabling it for some reason.

However, a significant reason not to use random curves is that custom
code for a given curve is often 3-4x faster than the generic code.
Each curve is really a totally different algorithm from the
implementation point of view (if you want it to be fast) and,
therefore, proliferation of curves is to be avoided.

AGL

-- 
Adam Langley [email-masked] http://www.imperialviolet.org

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 03 Jul 2010 02:29:14 +1200

=?ISO-8859-1?Q?Juho_V=E4h=E4-Herttua?= <[email-masked]> writes:

>I wouldn't want to support the explicit curves at all, and I don't see why
>they were added to the specification in the first place...

I'm gonna guess that some standards group somewhere will want to define their
own curves that are more cromulent than everyone else's, and so the spec had
to accomodate them (it's already happened, look at the SECG curves, the
Brainpool curves, the ... ).

>used. 

Oh, I've just realised my text was a bit vague, I meant only 192, 256, and
521, which nicely align with SHA-1, SHA2-256 and SHA2-512 and which seem to be
the three that everything supports already.  From the very minimal discussions
I've had with other implemeters over this, I understand there's a reluctance
to do 224 and 384 because it means you'd also have to implement the oddball
SHA2-224 and SHA2-384, making an already somewhat painful-to-test set of
algorithm combinations even bigger.

>However, as mentioned earlier, only the latter three are widely supported by
>existing implementations.

Is 384 widely supported?  I thought it was 192 (I'll have to go back and dig
through my notes, I think I ended up using 256 as the universal standard, I
found some sites that didn't do 192 and some that didn't do 384, but that was
just random interop servers configured for who-knows-what sort of testing).

Peter.

---

From: Juho Vähä-Herttua <[email-masked]>
Date: Fri, 2 Jul 2010 17:44:33 +0300

> Brainpool curves, the ... ).

Well, even in that case they could be defined as named curves if the properties are good, but I can see the point.

> just random interop servers configured for who-knows-what sort of testing).

I didn't really investigate it that much, only in the applications that I happen to use myself. My Firefox sent the extension as:

"00 0a 00 08 00 06 00 17 00 18 00 19"

The hex codes 0x17, 0x18 and 0x19 map to 256, 384 and 521 bits respectively. Another example I mentioned was the Microsoft CNG API that does not relate to TLS in any way, but I happened to be familiar with it. The documentation in http://msdn.microsoft.com/en-us/library/bb338248.aspx says:

"Valid key sizes are 256, 384, and 521 bits."

It's not a large sample and should probably be researched more before making any decisions. Just having even one of them as a MUST would be better than nothing though.

Juho

---

From: Peter Gutmann <[email-masked]>
Date: Sat, 03 Jul 2010 02:49:10 +1200

=?UTF-8?B?SnVobyBWw6Row6QtSGVydHR1YQ==?= <[email-masked]> writes:

>However, a significant reason not to use random curves is that custom code
>for a given curve is often 3-4x faster than the generic code.

Actually that'd be one argument for using your own curves, you can generate
ones that are open to far more efficient implementation than the NIST ones, or
even more so, the Brainpool ones (see this:
http://groups.google.com/group/sci.crypt/browse_thread/thread/b71abce5eb4a89c0/b92f8a11069fe6f5#b92f8a11069fe6f5
thread for more discussion of the problem).  On the whole though, I think DIY
parameters is something you definitely want to stay away from unless you have
a customer who insists on having their own personal curves created for them as
a fashion statement.

Peter.

---

From: Wan-Teh Chang <[email-masked]>
Date: Fri, 2 Jul 2010 09:21:33 -0700

> just random interop servers configured for who-knows-what sort of testing).

Yes, P-384 is widely supported for the following reasons.

NSA Suite B specifies SHA-256 and SHA-384 for hashing and the
NIST P-256 and P-384 curves for ECC:
http://www.nsa.gov/ia/programs/suiteb_cryptography/

Certicom's IETF Contribution Letter lists the NIST P-256, P-384,
and P-521 curves:
http://www.certicom.com/index.php/licensing/ip-contributions

Wan-Teh Chang