Subject: [Cfrg] MAY use specified curves

From: Dan Brown <[email-masked]>
Date: Tue, 9 Sep 2014 17:03:10 +0000

Dear CFRG,

In addition to CFRG responding to the TLS request for recommending one or
two curves per security level, possibly as mandatory-to-implement, I think
CFRG should make a further recommendation to permit a MAY for IETF
implementations to specify elliptic curves.  

My understanding is that many IETF WGs have applied a MUST NOT to the
ANSI/SECG mechanisms of specifying an elliptic curve.  I do not know recall
the rationale for this MUST NOT, but I presume it was to improve
interoperability.   But this seems to _force_ users of the protocols to use
certain curves.  By contrast, ANSI and SECG recommended certain curves, but
they did not require them.

The main justification for allowing specified curves is that all _known_
attacks on the ECDLP and ECDHP are fairly easy to avoid, either by users
checking the parameters, or trusting them via some authentication channel,
e.g. in a certificate.  So, there's no fundamental security concerns with
specified curves.  Side channels must be listed as an important security
consideration for implementation of specified curves.

Allowing users to specify their own curves, instead of forcing particular
curves upon them, appears to have the following minor security benefits:

+1) resistance certain types of _suspected_ attacks, e.g. maliciously
generated curves, since users can select their own curves, or their friend's
curves.

+2) algorithm agility: in the unlikely event that the named curves are
discovered to be compromised (some breakthrough attack on the named curves),
then users can switch over to a specified curve quite quickly if using
implementations that support specified curves.  

+3) the effort spent to solve one ECDLP can be re-used to solve another the
ECDLP on the _same_ curve, whereas, for a different curve, almost all of any
previous effort is not useful.

Specified curves add the costs:

-1) decreased interoperability and efficiency: 

-2) complicated negotiation: extra bandwidth to convey the curves details,
and extra effort (for implementations or CAs) to verify the curve
parameters.

-3) difficulty to achieve side channel resistance, etc.

This cost appears to be the inherent price for the whatever security benefit
of specified curves.  Whether or not is an acceptable cost should perhaps be
left to the implementer, except perhaps the side channel resistance problem.

Securing the ensuing negotiation of the specified curves might be done with
the MTI curves, again expensive but not abnormal.  For example, a relying
party has to trust the CA's choice of algorithm used in the root
certificates, say ECDSA with a named curve, but then builds on this trust
(of the CA and of the named curve) to accept the algorithm indicated in the
issued certificate, say some specified curve.   I think that that this would
be an instance of the principle that authentication requires only short term
security, making the named curve adequate, while confidentiality requires
long-term security, and thus much greater caution, perhaps warranting a
specified curve.

Regarding the risk that specified curves can be misinterpreted as something
else, e.g. some weak non-EC DH or some weak RSA key, that should be
correctible by unambiguous formatting (in conjunction with secured
negotiation).

To make this proposal more specific to TLS without client authentication, if
a client specifies a curve, the server must validate the curve, which
especially includes checking that it is not vulnerable to Pohlig-Hellman, by
doing a primality check on the large subgroup order.  This could be costly
for the server.  The TLS protocol itself must ensure that such a client will
not allow client curve proposals to be substituted: but this is an issue
with the named curves, not just specified curves.  On the other hand, if the
server specifies the curve, the server's authentication can be added onto
the specified curve.  If the specified curve itself is used for the
authentication, e.g. for the server signatures, then it will be the CA's
signature from which the client derives trust of the specified curve.  In
addition, the client could validate the specified curve.

ANSI and SECG already provide mechanisms to specify curves, but perhaps
these could be updated for other types of curves.

Best regards,

Daniel Brown

Research In Motion Limited

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 09 Sep 2014 19:36:36 +0100

Dan,

On 09/09/14 18:03, Dan Brown wrote:
> ANSI/SECG mechanisms of specifying an elliptic curve.  

I'm not clear what you mean here. Can you provide citations?

I think its fair to say that people generally prefer named
curves for simplicity and interop reasons but I don't know
what "MUST NOT" statements you mean.

Thanks,
S.

---

From: Manuel Pégourié-Gonnard <[email-masked]>
Date: Tue, 09 Sep 2014 20:59:09 +0200

> I'm not clear what you mean here. Can you provide citations?
I can't say for sure what Dan was referring to, but there is a MUST NOT in PKIX,
specifically RFC 5480 section 2.1.1:

     ECParameters ::= CHOICE {
       namedCurve         OBJECT IDENTIFIER
       -- implicitCurve   NULL
       -- specifiedCurve  SpecifiedECDomain
     }
       -- implicitCurve and specifiedCurve MUST NOT be used in PKIX.
       -- Details for SpecifiedECDomain can be found in [X9.62].
       -- Any future additions to this CHOICE should be coordinated
       -- with ANSI X9.

On the other hand, TLS allows specified curves, via the special NamedCurve
values arbitrary_explicit_prime_curves and  arbitrary_explicit_char2_curves (RFC
4492 section 5.1.1). But according to wikipedia [1], none of the usual TLS
libraries implement this option.

[1]
https://en.wikipedia.org/wiki/Comparison_of_TLS_implementations#Supported_elliptic_curves

(Outside of PKIX and TLS, I have no idea.)

Manuel.

---

From: Dan Brown <[email-masked]>
Date: Tue, 9 Sep 2014 19:38:52 +0000

> -----Original Message-----
> From: Stephen Farrell [mailto:[email-masked]]
>
> I think its fair to say that people generally prefer named curves for 
> simplicity and
> interop reasons but I don't know what "MUST NOT" statements you mean.

Well, I guess I was thinking of PKIX: RFC 5480 Section 2.1.1, has  a literal 
"MUST NOT"

http://tools.ietf.org/html/rfc5480#section-2

By contrast, RFC 3279 allowed specified curves, which I had forgotten.  My 
proposal is for CFRG to recommend PKIX reverting to something more the 
previous state.

But I was exactly wrong about TLS.  Oops, terribly sorry.  Haste on my part. 
Thanks for catching my mistake.  I should be more careful.

For certificates, I thought TLS followed PKIX, but I now see that RFC 4492 
refers to RFC 3279, which still allowed specified curves.  But 3279 is updated 
by 5480, so I'm not sure what rule is in effect for 4492 certificates.

Anyway, based on this poor misunderstanding, I presumed that 4492 followed 
disallowed specified curves ECDHE. My mistake here is a much worse here, 
because there's plenty of text in 4492 about specifying curves. Specifically, 
RFC 4492, Section 5.4 allows explicit prime ECDHE parameters, though it uses a 
different format than ANSI/SECG.  (In particular, it does not allow the seed 
to be sent, but I guess that's okay, because the server is sending the curve 
parameters, and the client already has to trust the server.)  Also, 4492 does 
not allow client to specify curves ... but maybe that saves servers from 
headaches.

I vaguely recall some TLS WG list emails agreeing to move towards named DHE 
parameters, and perhaps dropping DHE parameters.  Perhaps the TLS WG plans on 
doing the same for ECDHE?  If so, then my proposal is for CFRG to ask to 
retain the option of specified curves.

Since I was so wrong about TLS, my understanding about other WGs is probably 
wrong too: they allow users to specify their own curves.

Well, now that it seems many IETF WG already allow users to specify their own 
curves, CFRG might suggest ways to specify curves (and formats) for the new 
types of curves of being proposed.  That would be a formatting issue though, 
not a curve choice issue.

---

From: Stephen Farrell <[email-masked]>
Date: Tue, 09 Sep 2014 21:08:26 +0100

Hiya,

On 09/09/14 20:38, Dan Brown wrote:
>  My 

IMO CFRG should not be in the business of making such statements.
That is not an IRTF thing, but an IETF thing as you more or less
said yourself:

> That would be a formatting issue though, not a curve choice issue.

If you think the IETF ought take that road, then the saag list is
the place to suggest that in general or if there is no current
relevant working group.

If there is a specific protocol that has an active working group,
then its list is the place to go. The PKIX WG is closed, but the
list is still open and gets traffic so you could start there I guess.

But as I said, my impression is that folks mostly prefer named
curves and similar these days so I'm not sure you'd get that much
traction, but you should take this up on an IETF list if you
think it useful.

S.

---

From: Daniel Kahn Gillmor <[email-masked]>
Date: Tue, 09 Sep 2014 17:35:40 -0400

> retain the option of specified curves.

Yes, TLS is moving toward supporting a known set of named finite-field
DHE groups (though i don't think anyone has proposed eliminating custom
DHE groups for the full handshake yet).

  https://tools.ietf.org/html/draft-ietf-tls-negotiated-ff-dhe

No TLS implementation supports custom ECC curves that i've seen.

The advantage of using named groups/curves is that the groups/curves can
be evaluated in detail (for both cryptographic strength and
implementation optimization) by the community once, and then used
everywhere without any additional per-connection cost.

Custom groups/curves are far more expensive to use in practice.

With custom groups/curves, the recipient of the group/curve has a
difficult challenge -- they need to review the group/curve offered and
determine whether it meets their intended security level.  for finite
field DHE, evaluating a group for security requires at least (a)
checking the length of the modulus p, (b) testing the p for primality,
(c) testing q=(p-1)/2 for primality (to ensure a safe prime), and (d)
verify the order of the generator g and peer's share X (for safe primes,
this is an easy check, since group sizes are either 1, 2, p-1, or q, and
we know where the generators of order 2 are).  Very few implementations
actually do all these tests, and some common implementations do not even
verify (a), which is relatively cheap.

You can point your preferred TLS client at https://demo.cmrg.net/, which
uses finite-field DHE with the 16-bit "safe" prime 0x8C7B.  OpenSSL
currently connects to this server without complaint :/ [0]  What
advantage there might be in offering custom groups seems outweighed by
the implausibility of effective endpoint verification.

I can see a private organization deciding to all use a novel curve/group
in their internal communication because they don't like the existing
named groups/curves.  One option for them that wouldn't would be to all
agree to use a specific custom group/curve and then just verify that the
offered group/curve matches that one (and reject otherwise).  But for
this use case, a declared experimental code point (or private OID,
depending on where the group/curve is in use) would be sufficient, and
cheaper in terms of bandwidth.

Consider how long it has taken this group of very clever people to
decide whether any given curve is reasonable to use.  Do we expect a TLS
implementation confronted with a novel curve or group to be able to make
any sane representation to the user of the security level represented by
the offered curve?

i'd say that custom groups or curves are at best a SHOULD NOT, unless
there are some very clear guidelines on how to evaluate them at
connection time to determine what approximate security level they provide.

	--dkg

[0] https://rt.openssl.org/Ticket/Display.html?id=3120

---

From: "David Leon Gil" <[email-masked]>
Date: Tue, 09 Sep 2014 18:07:32 -0700 (PDT)

​

​To expand on this, I think that the CFRG should provide a method for evaluating curves for safety for IETF WGs to use.​

A number of people have mentioned applications with specific criteria that may not be satisfied by curves that are good for TLS. This matter is -- unlike performance considerations, or cipher-equivalent-security-level minutiae -- very clearly in-scope for CFRG.

---

From: Watson Ladd <[email-masked]>
Date: Tue, 9 Sep 2014 18:18:04 -0700

>> connection time to determine what approximate security level they provide.

There are a number of "attacks" on ECDSA where an existing signature
can be made to verify under a newly created key by using a custom
group. While these do not violate the security assumptions in the
standard signature model, they are occasionally annoying. Insofar as
we can trust servers not to be stupid, there isn't an issue with
custom curves in TLS, but sadly that is not the case.

Furthermore, no security benefit to using custom curves exists: the
batching attacks are of no consequence as getting even one discrete
log is hard. The only claimed security benefit is adapting to changes
in ECC security.

>
> To expand on this, I think that the CFRG should provide a method for
> evaluating curves for safety for IETF WGs to use.
>
> A number of people have mentioned applications with specific criteria that
> may not be satisfied by curves that are good for TLS. This matter is --
> unlike performance considerations, or cipher-equivalent-security-level
> minutiae -- very clearly in-scope for CFRG.

Which applications with which criteria? So far the only one has been
random primes for hardware, with an eye towards TLS and PKIX. If you
really want to know, look at safecurves.cr.yp.to. I don't see why we
should have dozens of curves, one for each protocol with a WG, further
complicating the work of implementers, and harming interoperability in
situations where only a few curves can be built in.

Your argument looks to me that CFRG should not recommend new curves,
and should say all the proposals are fine, and kick them back to the
TLS WG.

Sincerely,
Watson Ladd

>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin