Subject: Re: [Cfrg] Formal request from TLS WG to CFRG for new elliptic curves

From: Nigel Smart <[email-masked]>
Date: Sun, 20 Jul 2014 16:27:52 +0100

Hi

It seems there is a lot of noise about new types of curves, curvexxxyy this,
and NUMS that.

Note the request is for new ELLIPTIC CURVES not elliptic curve PROTOCOLS

Thus any curve should be IMHO usable with any STANDARD protocol, in any
STANDARD way of implementing the protocol. Without this constraint one is
bound to get implementation errors.

   - Curve25519 is a combined curve/protocol; so is out of scope IMHO. As
      someone is bound to use the underlying curve with some other protocol
      and make mistakes.

Benjamin Black is correct; having new types of this that and the other for
a marginal security gain, and/or a marginal performance gain is IMHO
inviting problems.

Thus the ONLY response in my view as responsible cryptographers is
to recommend curves which

    i) Whose data format for point transfer/curve definition is in 
Weierstrass
       form
           - I dont care if some implementation wants to use some 
super-duper
             form to do some calculation; the data transfer must enable
             interoperability.
  ii) Whose group order is prime
           - Not having prime group order is inviting problems. Thus Edwards
             curves are out as I am sure they require non-prime group order
iii) The "b" coordinate should be generated by a hash value on some
       random string.
  iv) Usual security constraints; base field has 256 and 512 bits of 
security
        to match AES 128 and AES 256; MOV criteria; SmartASS criteria;
  v) Ignore "esorteric" constrains like twist security etc.

So basically I cannot see what is wrong with the NIST curves. And if people
want something new then they should really come up with a credible
reason for wanting something new. No argument I have seen warrants
the massive change in software and infrastructure that is being proposed.
If people really are that worried about this NIST curves then
    i) They should probably stop using the internet full stop, as that means
       the NSA probably has massive more capability than even Snowden has
       revealed.
   ii) Generate curves as above; and not trust some new fingle-fangled ideas
       which are not supported by all the major cryptographers who have
       worked on ECC.

BTW I still stand by my statement that we should recommend EC-Schnorr
as an extra hash function.
   - Minor change in code needed to support it (compared to some of the 
other
     proposals)
   - Provides some "hedge" against future collisions in SHA-256 and SHA-3.
   - Has IMHO (and this is purely subjective) better provable security than
     EC-DSA
But that is not what we have been asked to comment on; as this is a new
"protocol" (i.e. signature scheme).

Yours

Nigel

---

From: "Salz, Rich" <[email-masked]>
Date: Sun, 20 Jul 2014 12:12:12 -0400

>       someone is bound to use the underlying curve with some other protocol

Strongly disagree.  Many find the performance issues compelling, and the fact that it defines everything down to the bytes on the wire highly attractive; the fact that high-quality reference implementations are available makes the "someone will get it wrong" not particularly interesting.

	/r$

--  
Principal Security Engineer
Akamai Technologies, Cambridge, MA
IM: [email-masked]; Twitter: RichSalz

---

From: Michael Hamburg <[email-masked]>
Date: Sun, 20 Jul 2014 10:25:21 -0700

You sound a little bit like you’re trolling us, Nigel.  It’s one thing to say that the marginal security and performance gains of the new curves isn’t worth the complexity of supporting them in TLS.  It’s another to say that every crypto curve should have all the properties that NIST chose for theirs (except 512 bits instead of 521), and that it shouldn’t have any other properties, even twist security.  Do you have any justification for those criteria?

— Mike

On Jul 20, 2014, at 8:27 AM, Nigel Smart <[email-masked]> wrote:

>   i) Whose data format for point transfer/curve definition is in Weierstrass
>      form
>          - I dont care if some implementation wants to use some super-duper
> iv) Usual security constraints; base field has 256 and 512 bits of security
>  - Minor change in code needed to support it (compared to some of the other
>    proposals)
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Nigel Smart <[email-masked]>
Date: Sun, 20 Jul 2014 18:57:24 +0100

Hi

Various issues here....

i) Is there any justification for new curves at this current point in time?
      - My opinion is no. There is no reasonable argument which can 
suggest that
        NIST cooked their curves. There may be better ways to generate 
the curves
        now with extra functionality (see below), but the basic security 
criteria are
         still valid.

ii) Should we add new SECURITY criteria on the CURVES?
      - My opinion is that this is marginal. I see no benefit at all in 
twist security.
        Dont get me wrong, I think twist security is a cool idea worthy 
of an academic
        paper. Its just not practically relevant here (unless we are 
changing protocols,
        which is not the request).

iii) Should we add in curves with better performance which may deviate 
from the
       NIST choices?
           - Only if they can represent points in Weierstrass form for 
transmission.
           - Only if they have prime order.
                 - Note, here I am being stronger than the ANSI/NIST 
criteria (but actually
                   NIST curves have this property in any case).
                 - I really think prime order curves are vital to avoid 
mistakes. I have
                   been recommending their use in nearly 18 years of 
advising companies
                   on ECC stuff.
           - In other words the curve addition is OK, as long as it can 
interoperate with
             existing software, and will not cause security/patent 
violation issues when
             used with all possible protocols
                  - Last point is key, as we cannot force a new curve to 
only be used
                    with protocol X, as some idiot will use it with Y. 
This is why I think
                    Curve25519 should be treated as a complete protocol, 
as opposed
                    to a curve. The naming by Danja is a unfortunate in 
this respect.

iv) Should we add in new FUNCTIONALITY criteria on the CURVES?
           - Actually yes I do think this. If we were to re-do NIST like 
curves I would also
             publish seeds for TWO base points. The reason for this is 
that many protocols
             require two base points, and not having them defined in the 
"standard" curves
             is a problem and we need the DLP to be unknown so we need 
the seeds to be
             able to guarantee this.

<humour mode>

My problem with the discussion is that it seems to be being conducted in 
exactly
the way which resulted in the mess which is the current TLS. It would 
appear that
to people (like me) who have spend years researching ECC, key agreement 
protocols,
trying to make cryptographic sense of the current TLS protocol, etc etc, 
are being
trolled by people on the list   :-)

</humour mode>

Cheers

Nigel

---

From: Watson Ladd <[email-masked]>
Date: Sun, 20 Jul 2014 11:51:05 -0700

On Sun, Jul 20, 2014 at 10:57 AM, Nigel Smart <[email-masked]> wrote:
>      - My opinion is no. There is no reasonable argument which can suggest
> that
>        NIST cooked their curves. There may be better ways to generate the
> curves

Except that we want higher performance, to enable the use of TLS with
PFS in places where
it is currently not deployed. Performance matters: if you can get a
curve of size 448 to go faster
then one of size 224, and an even faster curve of size 256, this
enables the use of forwards secrecy
in places where it didn't fit before, and with bigger keys than before.

If you want to see something like tcpcrypt be ubiquitous, than every
little percent of performance matters.
Rich Salz has sent emails saying essentially that the cost of ECDH
exchanges is making it hard for CDNs
to adopt ECDHE. What's the point of cryptography if it cannot be used?

>      - My opinion is that this is marginal. I see no benefit at all in twist
> security.
>        Dont get me wrong, I think twist security is a cool idea worthy of an
> academic
>        paper. Its just not practically relevant here (unless we are changing
> protocols,

Twist security enables use of ladders without validation: assume
checks not required for interop get screwed up.

This process began with Curve25519 for TLS. Then Microsoft showed up
with substantially similar NUMS
curves. I think it was obvious that new code was going to be written
and this was understood by the TLS
1.3 WG.

>
> iii) Should we add in curves with better performance which may deviate from
> the
>       NIST choices?
>                 - Note, here I am being stronger than the ANSI/NIST criteria
> (but actually
>                   been recommending their use in nearly 18 years of advising
> companies
>                   on ECC stuff.
>             existing software, and will not cause security/patent violation
> issues when
>                  - Last point is key, as we cannot force a new curve to only
> be used
>                    with protocol X, as some idiot will use it with Y. This
> is why I think
>                    Curve25519 should be treated as a complete protocol, as
> opposed
>                    to a curve. The naming by Danja is a unfortunate in this
> respect.

DJB, not Tanja Lange, made Curve25519: he's the author on the original
(2006) paper.
Read the SEC1 and NIST standards: they do include non-prime order
curves, and picked prime order because they could.
Yes, I can make protocols where non-prime order could be an issue, but
it's a very slight change to make them work.

There isn't going to be an interop problem: TLS includes mechanisms to
negotiate the use of curves
precisely to enable the addition of new mechanisms. The only issue is
certificates, but even there there are ways
to deal with it.

>             publish seeds for TWO base points. The reason for this is that
> many protocols
>             is a problem and we need the DLP to be unknown so we need the
> seeds to be
>             able to guarantee this.

The only protocols I've seen with that property are PAKEs, and
Pedersen commitments, neither of which has great usage
in the IETF. And it's not for lack of definition: SRP was in TLS but unused.
> the way which resulted in the mess which is the current TLS. It would appear
> that
> trying to make cryptographic sense of the current TLS protocol, etc etc, are
> being

Do you see a security issue with Curve25519, or any of the proposals?
Or is this a complaint about interoperability?
One of those you are qualified to talk about: the other one Rich Salz
and Adam Langley know far more about, because they
actually manage large deployments of TLS software.

Sincerely,
Watson Ladd

>> You sound a little bit like you’re trolling us, Nigel.  It’s one thing to
>> say that the marginal security and performance gains of the new curves isn’t
>> worth the complexity of supporting them in TLS.  It’s another to say that
>> every crypto curve should have all the properties that NIST chose for theirs
>> (except 512 bits instead of 521), and that it shouldn’t have any other
>> properties, even twist security.  Do you have any justification for those
>> criteria?
>>
>> — Mike
>>

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

---

From: Michael Hamburg <[email-masked]>
Date: Sun, 20 Jul 2014 12:51:28 -0700

On Jul 20, 2014, at 10:57 AM, Nigel Smart <[email-masked]> wrote:

>     - My opinion is no. There is no reasonable argument which can suggest that
>       NIST cooked their curves. There may be better ways to generate the curves
>       now with extra functionality (see below), but the basic security criteria are
>        still valid.

I also do not believe that the NIST curves have backdoors.  They have reasonable security criteria as well.  It’s just that the state of the art has progressed in terms of architecture, implementation, security, performance, protocols, etc.  So it makes sense to standardize new curves for future protocols.

Just because the NIST security criteria were good choices doesn’t mean that they are the best choices.  Making ‘b’ the hash of a random seed was a reasonable choice.  I do not see why it is clearly a better choice than the DJB / Microsoft NUMS approach.  Prime-order curves have good properties.  Edwards curves have different good properties.  Just because prime order is desirable doesn’t mean that it’s the only desirable thing.  We should weigh its properties against the properties of curves with cofactors.

Perhaps the new curves should not go into TLS for complexity reasons.  I defer on that question to those who manage large-scale TLS delpoyments.

>     - My opinion is that this is marginal. I see no benefit at all in twist security.
>       Dont get me wrong, I think twist security is a cool idea worthy of an academic
>       paper. Its just not practically relevant here (unless we are changing protocols,

You might well think that various new security features — twist security, strongly unified formulas, no point with x=0 for power analysis, etc — are not worth a new standard.  But you asserted explicitly, and with no justification, that the ONLY responsible course is to recommend curves which ignore these constraints.  I don’t understand why extra security constraints would be irresponsible, so long as they’re clearly not part of a "BADA55” manipulation of the parameters.

> iii) Should we add in curves with better performance which may deviate from the
>      NIST choices?
>          - Only if they can represent points in Weierstrass form for transmission.
>                - Note, here I am being stronger than the ANSI/NIST criteria (but actually
>                - I really think prime order curves are vital to avoid mistakes. I have
>                  been recommending their use in nearly 18 years of advising companies
>                  on ECC stuff.

There is a class of mistakes that people make with prime order curves, and a different class of mistakes that they make with cofactors.  You may feel that mistakes involving incomplete formulas are less serious or easier to avoid than those involving cofactors.  Go ahead and push for that.  But it’s not helpful to just assert that cofactors aren’t acceptable.

>          - In other words the curve addition is OK, as long as it can interoperate with
>            existing software, and will not cause security/patent violation issues when
>                 - Last point is key, as we cannot force a new curve to only be used
>                   with protocol X, as some idiot will use it with Y. This is why I think
>                   Curve25519 should be treated as a complete protocol, as opposed
>                   to a curve. The naming by Danja is a unfortunate in this respect.

It is safe to carry out other protocols over Curve25519, or over isomorphic Weierstrass or Edwards curves if they specify those formats.  Most EC protocols account for a cofactor, including the TLS-revelant ECDHE and ECDSA.  It is of course possible to screw up implementing such protocols.  But is Curve25519 any more dangerous for this than any other curve with a cofactor?

>          - Actually yes I do think this. If we were to re-do NIST like curves I would also
>            publish seeds for TWO base points. The reason for this is that many protocols
>            require two base points, and not having them defined in the "standard" curves
>            is a problem and we need the DLP to be unknown so we need the seeds to be
>            able to guarantee this.
> 
> <humour mode>
> 
> My problem with the discussion is that it seems to be being conducted in exactly
> the way which resulted in the mess which is the current TLS. It would appear that
> to people (like me) who have spend years researching ECC, key agreement protocols,
> trying to make cryptographic sense of the current TLS protocol, etc etc, are being

I don’t want to see a mess, and I respect your input.  It’s just that most of these criteria have been discussed for a while now.  It’s frustrating to have a discussion like this, and then you come in and say “actually, it’s obvious that the criteria should be that the curve looks like a NIST curve.  Also it’s important that the new desiderata that you all have been discussing should be ignored.”  That position requires justification.  You’ve provided justification for some of your points, which is helpful.

> Nigel

Cheers,
— Mike

---

From: Patrick Longa Pierola <[email-masked]>
Date: Sun, 20 Jul 2014 20:04:33 +0000

> Nigel Smart wrote:
> Thus any curve should be IMHO usable with any STANDARD protocol, in any STANDARD way of implementing the protocol. Without this constraint one is bound to get implementation errors.

> Benjamin Black is correct; having new types of this that and the other for a marginal security gain, and/or a marginal performance gain is IMHO inviting problems.
 
IMO these are important points made by Ben and Nigel. To the point: so far I haven't seen compelling evidence to want to "hardwire" a curve to a protocol. Many well-designed curves can be used for different protocols without restrictions, with the same (or potentially stronger) security assurances and with virtually equivalent performance. OTOH, tying curve/protocol can bring potential compatibility problems, make agility harder, increase complexity of implementations (from a narrow perspective "hardwired" curve/protocol implementations might seem to simplify things, however in actual deployments in which many other components participate this is not necessarily the case), etc.

As a rule of thumb, IMHO a solid curve selection process should focus on curves (and reference implementations) that apply to a flexible number of protocols and, in special, to ECDHE and ECDSA. 

>> Nigel Smart wrote:
> Rich Salz wrote:

Can you point me out the reference implementations that make the performance that compelling? Please, if you can, back your response with precise performance numbers for ECDHE (IMO this is the most important metric to evaluate performance in this IETF process). This is important because we wouldn't want to dismiss strong compatibility features at the expense of negligible speedups.

Best regards,

Patrick