Subject: [Cfrg] Rerun: Elliptic Curves - preferred curves around 256bit work factor (ends on March 3rd)

From: Alexey Melnikov <[email-masked]>
Date: Wed, 25 Feb 2015 14:27:58 +0000

CFRG chairs are starting another poll:

Q3: This is a Quaker poll (please answer one of "preferred", 
"acceptable" or "no") for each curve specified below:

1) 448 (Goldilocks)
2) 480
3) 521
4) other curve (please name another curve that you "prefer" or "accept", 
or state "no")

If you stated your curve preferences in the poll that ended on February 
23rd (see the attachment), you don't need to reply to this poll, your 
opinion is already recorded. But please double check what chairs 
recorded (see the attachment).

If you changed your mind or only answered the question about performance 
versa memory usage for curves 512 and 521, feel free to reply.

Once this issues is settled, we will be discussing (in no particular 
order. Chairs reserve the right to add additional questions) 
implementation specifics and coordinate systems for Diffie-Hellman. We 
will then make decisions on signature schemes. Please don't discuss any 
of these future topics at this time.

---

From: "Blumenthal, Uri - 0558 - MITLL" <[email-masked]>
Date: Wed, 25 Feb 2015 15:20:12 +0000

Prefer: 521
Accept (in order of preference): 512 (NUMS), 480, 448

--
Regards,
Uri Blumenthal                            Voice: (781) 981-1638
Cyber Systems and Technology   Fax:   (781) 981-0186
MIT Lincoln Laboratory                Cell:  (339) 223-5363
244 Wood Street, Lexington, MA 02420-9185       

Web:  http://www.ll.mit.edu/CST/
MIT LL Root CA:  <https://www.ll.mit.edu/labcertificateauthority.html>

----- Original Message -----
From: Alexey Melnikov [mailto:[email-masked]]
Sent: Wednesday, February 25, 2015 09:27 AM
To: [email-masked] <[email-masked]>
Subject: [Cfrg] Rerun: Elliptic Curves - preferred curves around 256bit work factor (ends on March 3rd)

1) 448 (Goldilocks)
2) 480
3) 521

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 25 Feb 2015 10:28:50 -0500

On Wed, Feb 25, 2015 at 9:27 AM, Alexey Melnikov <[email-masked]>
wrote:

> Q3: This is a Quaker poll (please answer one of "preferred", "acceptable"
> or "no") for each curve specified below:
>
> 1) 448 (Goldilocks)
> 2) 480
> 3) 521
> opinion is already recorded. But please double check what chairs recorded
> (see the attachment).
>

521 Preferred
480 OK-ish
448 Not acceptable

My problem with 521 versus 512 is the oddness factor. What I want to be
able to do is to be able to carry the argument that the IETF has specified
the best performance curve and the best security curve.

I don't want to have 20+2 curves as a result of this process, I want 2
curves and use them for absolutely everything without exception. One of the
reasons RSA is so dominant is that as far as developers are concerned, RSA
is RSA. You don't need to have an expert to pick between two dozen
different flavors.

One piece of data I had not been aware of is that NIST actually proposed
some 521 curves back in the day though not in suite B.. While not endorsing
their specific curves, it does provide a data point and an argument against
'oddness'.

Let us imagine that you are deciding between the IETF curve and the NIST
521 curve

If the IETF curve is 521, then we win against the NIST curve on performance.

If the IETF curve is 512. The NIST curve has 16 times the work factor so it
is a little stronger. So we would be arguing higher performance against
their random prime curve. It is a colorable argument but more folk know who
NIST are than IETF. We can only really win the argument if NIST agrees to
let us. And that would take them a year or more.

If the IETF curve is 480 then we are much less secure. We are giving up
2^30 worth of work factor, a billion times. Now even though we are talking
a billion, billion, billion, billion, billion, billion, billion, billion,
versus a billion, billion, billion, billion, billion, billion, billion,
billion, billion, we are still talking about a factor of a billion.

If the IETF curve is 448 then we are giving up a billion billion times the
work factor.

My desired outcomes here are

1) NIST recommends our new curves
2) NIST recommends our new curves as preferred

If we go for 512 then we might get 2 but it is a somewhat harder sell. I
can't see us winning that argument for Riding Hood (480) or Goldilocks (448)

---

From: Watson Ladd <[email-masked]>
Date: Wed, 25 Feb 2015 07:44:43 -0800

On Wed, Feb 25, 2015 at 6:27 AM, Alexey Melnikov
<[email-masked]> wrote:
> Q3: This is a Quaker poll (please answer one of "preferred", "acceptable" or
> "no") for each curve specified below:
>
> 1) 448 (Goldilocks)
> 2) 480
> 3) 521
> 4) other curve (please name another curve that you "prefer" or "accept", or
> state "no")

448 Prefered
480 Acceptable
521 Acceptable

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

---

From: Stephen Farrell <[email-masked]>
Date: Wed, 25 Feb 2015 15:46:47 +0000

> "acceptable" or "no") for each curve specified below:

all are acceptable for me, as are any other choices that
are claiming to be >200 bit work factor

I do "prefer" that CFRG document only one of those as being
the usual non-NIST choice for >128 bit work factor. I
do not care which one is annointed by CFRG, not about the
language used to separate that one from the crowd so long
as it's clear to IETF folks one way or another.

My rationale is that I don't think we have real technical
grounds for wanting >128 bit work factor today but it's going
to be inevitable that a bunch of folks insist on that so
better if we pick just one and that the work factor margin
be around or better than 80 additional bits

S.

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

---

From: Yoav Nir <[email-masked]>
Date: Wed, 25 Feb 2015 18:07:28 +0200

> On Feb 25, 2015, at 5:44 PM, Watson Ladd <[email-masked]> wrote:
> 

+1

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 25 Feb 2015 11:22:16 -0500

Do we have figures for performance of these versus RSA2048?

Yes, we get a reversal of the public/private speed advantage on signature.
And that in itself is a huge win on the server side

RSA signature verification takes 0.16 ms on a reasonably current machine
(signature is 6ms)

http://www.cryptopp.com/benchmarks.html

How much faster/slower one curve is over another matters much less to me
than whether the curve is faster or slower than what I am already using. I
am not going to be using P521 or P448 curves on a constrained device, I
will go for P255.

If we had figures comparing the curve candidates to RSA it would probably
be illuminating.

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 25 Feb 2015 08:25:14 -0800

> 521 Acceptable

+1, and +1 to Stephen's logic.

--Paul Hoffman

---

From: Adam Langley <[email-masked]>
Date: Wed, 25 Feb 2015 08:43:05 -0800

> 4) other curve (please name another curve that you "prefer" or "accept", or

448: Preferred
480: acceptable
521: acceptable

Cheers

AGL

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

---

From: Paul Lambert <[email-masked]>
Date: Wed, 25 Feb 2015 08:46:43 -0800

+1

---

From: Simon Josefsson <[email-masked]>
Date: Wed, 25 Feb 2015 17:50:47 +0100

I believe the focus on "around 256bit work factor" is distracting and
could better be phrased "alternative to Curve25519 with higher security
margin".  Given that the work factor on the mentioned curves vary quite
significantly away from 256-bit, I'm reading the poll that way.

> "acceptable" or "no") for each curve specified below:

Preferred.

Acceptable.

Acceptable.

> 4) other curve (please name another curve that you "prefer" or
> "accept", or state "no")

Curve25519       Preferred
E-382            Acceptable
M-383            Acceptable
Curve383187      Acceptable
brainpoolP384t1  No
NIST P-384       No
Curve41417       Acceptable
Ed448-Goldilocks Preferred
M-511            Acceptable
E-521            Acceptable

Generally, any curve that has high performance, reasonable security
(more than ~100 bits of work factor) and doesn't have design warts
(SafeCurves) is acceptable to me.  To become preferred, I select the
curves out of the acceptable curves that is seeing the highest adoption
rate in the implementers community and getting the most reviews in the
cryptographic community.  The former (acceptable) is a simple process,
the latter (preferred) is subjective.

/Simon

---

From: Watson Ladd <[email-masked]>
Date: Wed, 25 Feb 2015 08:53:04 -0800

> http://www.cryptopp.com/benchmarks.html

That benchmark is one measurement, on one processor, with no
indication that it was done properly.
> am not going to be using P521 or P448 curves on a constrained device, I will
> go for P255.

What if that constrained device needs to interoperate with the web
PKI, and they decide because of how important they are they must use
P521?

>
> If we had figures comparing the curve candidates to RSA it would probably be
> illuminating.

http://bench.cr.yp.to/results-encrypt.html
and http://bench.cr.yp.to/results-dh.html

>From these on Titian0, we see that ronald1024 encryption takes 41188
cycles, and Curve25519 shared secret agreement 161708 cycles, nearly 4
times as much. But ronald1024 decryption consumes seven times as many
cycles as Curve25519 shared secret agreement.

This pattern holds across processors.  Of course, ronald1024 is a
wrapper around OpenSSL: it's very possible that extensive optimization
could improve those numbers somewhat.

But I was comparing 1024 bit RSA. To properly ensure adequate security
3072 bits is closer to the mark, and here the encryption time exceeds
that of Curve25519.

A simple google search would have found SUPERCOP, where I got these
numbers from.

Sincerely,
Watson Ladd

---

From: Derek Atkins <[email-masked]>
Date: Wed, 25 Feb 2015 11:53:42 -0500

> Do we have figures for performance of these versus RSA2048?

Why are you looking at RSA 2048?  That's only a 2^112 work factor
(C.f. Section 1 of RFC4492).  If you want a 2^256 work factor you need
to go up to RSA 15360.  If you only want to get to 2^128 then you need
to look at RSA 3072.  Let's at least compare apples to apples.

> Yes, we get a reversal of the public/private speed advantage on signature. And
> that in itself is a huge win on the server side 
>
> How much faster/slower one curve is over another matters much less to me than
> whether the curve is faster or slower than what I am already using. I am not
> going to be using P521 or P448 curves on a constrained device, I will go for
> P255.
>

For the record, I have no opinion on which curves to look at; I would
want to find the best "bang-for-the-buck" curve in terms of performance
and security.  And if 521 is better than 512 in terms of performance I
don't see the extra 9 bits of data as being a deployment issue.

-derek

-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: Damien Miller <[email-masked]>
Date: Thu, 26 Feb 2015 04:45:20 +1100 (AEDT)

> 4) other curve (please name another curve that you "prefer" or "accept", or

448 preferred
480 acceptable
521 acceptable
other no

---

From: Paul Hoffman <[email-masked]>
Date: Wed, 25 Feb 2015 10:05:47 -0800

On Feb 25, 2015, at 7:46 AM, Stephen Farrell <[email-masked]> wrote:
> the usual non-NIST choice for >128 bit work factor.

The term "non-NIST" is predictive, and the crypto community kinda sucks at predictions. We have no idea what NIST will do in the future if a bunch of IETF WGs adopt specific elliptic curves that are not P256/P384. Unfortunately, I suspect current NIST folks also have no idea what NIST will do in that case either. In the past, NIST has sometimes (but not always) responded to pressure from the real world about crypto algorithms and modes; let's hope for the best here.

--Paul Hoffman

---

From: [email-masked]
Date: Wed, 25 Feb 2015 18:38:11 +0000

> The term "non-NIST" is predictive, and the crypto community kinda sucks at predictions. We have no idea what NIST will do in the future if a bunch of IETF WGs adopt specific elliptic curves that ar…

Sure, I agree it'd be good if NIST also annoint the output from this cfrg process. But right now non-NIST is the correct distinguishing term for what I meant. I see no reason that term will be needed in an RFC though if that helps assuage some sensitivity somewhere in the universe :-)

S.

> --Paul Hoffma

---

From: Paul Lambert <[email-masked]>
Date: Wed, 25 Feb 2015 11:31:52 -0800

On 2/25/15, 10:38 AM, "[email-masked]"
<[email-masked]> wrote:

>> The term "non-NIST" is predictive, and the crypto community kinda sucks
>>at predictions. We have no idea what NIST will do in the future if a
>>bunch of IETF WGs adopt specific elliptic curves that are not P256/P384.
>>Unfortunately, I suspect current NIST folks also have no idea what NIST
>>will do in that case either. In the past, NIST has sometimes (but not
>>always) responded to pressure from the real world about crypto
>>algorithms and modes; let's hope for the best here.
>
>Sure, I agree it'd be good if NIST also annoint the output from this cfrg
>process. But right now non-NIST is the correct distinguishing term for
>what I meant. I see no reason that term will be needed in an RFC though
>if that helps assuage some sensitivity somewhere in the universe :-)

Branding is very important Š  "non-NIST" is adversarial and will
discourage adoption.  NIST is also not the only Government agency
recommending specific curve parameters.

The NIST and other recommended Small Weierstrass curves are all based on
the late 90¹s technology and requirements.

The CFRG recommendations for Œnew curves¹ represent significant
improvements based on more contemporary mathematical techniques and
industry requirements. The well identified benefits and more modern
aspects of the recommendations should be emphasized.

Paul

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Wed, 25 Feb 2015 14:36:02 -0500

> aspects of the recommendations should be emphasized.
Further, NIST is holding a workshop on ECC curves specifically asking what
it can do to encourage deployment. So we are pushing against an open door
here.

---

From: Alyssa Rowan <[email-masked]>
Date: Wed, 25 Feb 2015 20:05:43 +0000

On 25/02/2015 14:27, Alexey Melnikov wrote:

> [AM] If you stated your curve preferences in the poll that ended
> on February 23rd (see the attachment), you don't need to reply to 
> this poll, your opinion is already recorded. But please double 
> check what chairs recorded (see the attachment).

Thank you. What the chairs have recorded is accurate for me.

+1 to Stephen's point also.

- -- 
/akr

---

From: Stephen Farrell <[email-masked]>
Date: Wed, 25 Feb 2015 21:49:31 +0000

On 25/02/15 19:31, Paul Lambert wrote:
> Branding is very important Š  "non-NIST" is adversarial

Branding may be important but considering this adversarial
is silly and over stated.

S.

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 25 Feb 2015 15:05:47 -0800

On Wed, Feb 25, 2015 at 10:38 AM, <[email-masked]> wrote:

> process. But right now non-NIST is the correct distinguishing term for what
> I meant. I see no reason that term will be needed in an RFC though if that
> helps assuage some sensitivity somewhere in the universe :-)

I gotta agree with Stephen here. I realize NIST is a hot-button issue, but
if we're going to get politically correct about "non-NIST", I really feel
there could've been a better representative issue here.

In the meantime, the elliptic curves people are actually using today
in-the-field are defined by NIST and I don't think this usage was uncouth.

-- 
Tony Arcieri

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 25 Feb 2015 15:06:43 -0800

Also I strongly hope NIST will adopt the curves the CFRG decides upon,
provided they're good! ;)

-- 
Tony Arcieri

---

From: Damien Miller <[email-masked]>
Date: Thu, 26 Feb 2015 10:52:20 +1100 (AEDT)

> provided they're good! ;)

What are the NIST-sneakily-trojaned-our-curves paranoiacs going to do then?

-d

---

From: Dan Brown <[email-masked]>
Date: Thu, 26 Feb 2015 17:21:41 +0000

My votes in this poll:

521: preferred
512: acceptable
480: acceptable
448: acceptable

Earlier, I voted NO on pursuing 192-bit and 256-bit security in the
short term.  Perhaps that disqualifies me to vote on this poll about
the short term choice for higher security curves, but I still have
some preferences on the outcome of the short term recommendation, so
I'll submit my vote in the current poll.  Feel free to ignore for the
short-term activity, especially if it helps to achieve CFRG to
consensus, thereby progressing with a recommendation.

Long-term, I strongly support higher-level security, including what
might be labelled as 192-bit security, and perhaps even other
intermediate values.

Though I voted above on 448 and 480 as acceptable, just to be clear,
we should not label them as providing "256-bit security" and not use
them with AES-256, until we solidify accounting arguments such
compatibility, such as:

- the for the EC operations per bit size being slower than say AES
operations per bit size,

- the stronger per-user security of ECC compared to AES,

- the more secure quadratic trade-off of success rate for time in ECC
compared to linear trade-off for AES.

These arguments are subtle, but perhaps within reach.

Alternatively, I wouldn't mind recommending the 448 and 480 field
sizes, and then using symmetric key sizes that are appropriate for the
field sizes. In other words, with public-key taking a more leading
role in security decisions, with symmetric-key just following suit.

An additional reservation I have with 480 and 448 is that they arise
from more recent, and lower profile proposals, compared to NIST P521.
Generally, I have a strong belief in the security in the security of
ECC, including the hardness of the ECDLP and other things needed for
security of ECC.  But for making recommendations of higher security,
I'd want something stronger than mere belief.

For low-characteristic fields, Menezes, Diem and others have published
attacks on weak fields, in the strongest sense of having an easier
ECDLP.  Also, some have argued here that in some prime-field are more
vulnerable to side channels than others [ref?].  Based on these two
existing threats, we might reasonably speculate that there remains a
remote risk of new weaknesses in ECC that depend on the field choice.
If we want to rationally reduce that remote risk, then we can use the
evidence of the 521-bit field size has remained unbroken since 1999.
This is a reason to deem 521 as less risky the newer 448 and 480.

Finally, others have commented that 128-bit security is so strong that
anything beyond that is pointless.  Well, I disagree, for several
reasons, albeit perhaps theoretical reasons.  For example, many
security proofs [*], especially for signature schemes, have loose
reductions, which suggest larger key sizes are needed for the provable
security results to be concretely applicable.  Of course, real-world
security can be better than what the proofs suggests, but occasionally
the bounds in the proof turn out to be right after all.  Luckily, for
many signature applications, perhaps even those of CAs and signed
ECDH, that looseness is irrelevant, either because the number of
signatures is low, or the signing oracle is more limited than the
threat model of the security proofs.  For another example, consider
known reductions between ECDHP and ECDLP, whose tightness depend on
not just on the field size, but also the group size.

[*] I'm using the conventional terms "security proof", though a more
modest label like "reductionist security argument", or "conditional
security analysis" might be better.

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Alexey Melnikov
> Sent: Wednesday, February 25, 2015 9:28 AM
> To: [email-masked]
> If you stated your curve preferences in the poll that ended on February 23rd
> (see the attachment), you don't need to reply to this poll, your opinion is
> already recorded. But please double check what chairs recorded (see the
> attachment).
> 
> Once this issues is settled, we will be discussing (in no particular order. Chairs
> reserve the right to add additional questions) implementation specifics and
> coordinate systems for Diffie-Hellman. We will then make decisions on
> signature schemes. Please don't discuss any of these future topics at this time.

---

From: "Dan Harkins" <[email-masked]>
Date: Thu, 26 Feb 2015 09:30:48 -0800 (PST)

> 4) other curve (please name another curve that you "prefer" or "accept",

1) no
2) no
3) preferred
4) no

  Dan.

---

From: _MiW <[email-masked]>
Date: Sat, 28 Feb 2015 20:26:58 +1030

1) acceptable
2) acceptable
3) /E-521/ preferred
4) /numsp512t1 acceptable, M-511 acceptable/

---

From: Rene Struik <[email-masked]>
Date: Sat, 28 Feb 2015 12:01:38 -0500

Hi Alexey:

Order of preference:
a) curve with 64-byte underlying prime field
b) curve with 521-bit underlying prime field (due to P-521 precedent 
with Mersenne primes)

Notes:
1) This curve is supposed to serve as a really conservative pick, so I 
think curves below the 500-bit demarcation line curves, no matter their 
charm, should be out.
2) Picking a curve with prime order subgroup of 508-512 bit would 
satisfy Russian parameter requirements, so if we could accommodate this 
and show inclusiveness, so much the better (this would be sign of 
strength for this group).
-- Examples: Microsoft's 512-bit nums curve, M-511 (IACR ePrint 
2013-647) {not clear (to me) what design criteria were to include field 
bit-sizes in the poll below, since neither 511/512 mentioned.}
3) Slight performance differentials (say, less than factor 2x) around 
the same design crypto bit strength should not be that important, at 
least not with this really conservative pick (I do expect 128-bit design 
strength curves to be used with, e.g., signing DH exponents, where there 
may be some roots that use the conservative pick).

Best regards, Rene

On 2/25/2015 9:27 AM, Alexey Melnikov wrote:
> If you stated your curve preferences in the poll that ended on 
> February 23rd (see the attachment), you don't need to reply to this 
> poll, your opinion is already recorded. But please double check what 
> chairs recorded (see the attachment).
>
> If you changed your mind or only answered the question about 
> performance versa memory usage for curves 512 and 521, feel free to 
> reply.
>
> will then make decisions on signature schemes. Please don't discuss 
> any of these future topics at this time.
>
>

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363