Subject: [Cfrg] Goldilocks (was Re: EC - next steps to get draft-irtf-cfrg-curves done)

From: Watson Ladd <[email-masked]>
Date: Tue, 10 Feb 2015 18:04:48 -0800

On Feb 10, 2015 1:23 PM, "Paterson, Kenny" <[email-masked]> wrote:
>
> Hi,
>
> On 10/02/2015 18:33, "Watson Ladd" <[email-masked]> wrote:
>
> >
> >On Feb 10, 2015 9:42 AM, "Stephen Farrell" <[email-masked]>
> >wrote:
> >>
> >>
> >> Thanks to the chairs for trying this approach. I've answered
> >> your first poll, but I'd also like to say that I'm entirely
> >> fine if the chairs use their judgement to evaluate poll responses
> >> and I hope you do not limit yourselves to purely mechanical
> >> evaluations. That's because it's inevitable that people will
> >> question the questions, as has happened already;-) And we
> >> don't want to have to re-do a bunch of polls I hope.
> >I'm surprised that you consider implicitly rejecting 2^448-2^224-1 for
> >unstated arguments a good idea, given your openness to supporting it.
>
> Thanks for making explicit what was implicit.
>
> Yes, we are ruling out 2^448-2^224-1 and focussing on primes yielding
> curves at or near the 192 and 256 bit security levels. There was a long
> discussion on this on the list a while back, no clear consensus emerged on
> whether we should "stick" to the 192-bit and/or 256-bit security levels or
> go for "intermediate" values, and the chairs are now making a decision on
> this.

This strikes me as extremely premature. We do not yet have hard
performance data on 32 bit machines for 2^389-21. In fact, the best
fractional radix I could come up with used exactly the same number of
limbs as the Karatsuba revisited paper uses for 2^414-17, and exactly
the same number of limbs as Goldilocks does: until we actually measure
on actual silicon highly optimized assembly optimizations (something I
can't write: I should learn someday) we don't know which prime is
better.

Of course, if you don't actually care about smartphone performance,
but only the latest and greatest Intel chips, then Goldilocks incurs a
7-8% performance penalty compared to 2^389-21. And if you don't care
about performance, but want the most secure curve possible. Goldilocks
is much smaller than 521. But each of these rationales also excludes
one of the options in the consensus poll!

Far more likely is that people who care about performance agree to eat
a 7% performance hit, and people who want maximum security absorb a
factor of 2^64 in group size, so we have stronger support for
Goldilocks than either of the two extremes. But that's not currently
an option on the poll, and it's not clear what the reason for
excluding it is, other than "448 isn't 384 or 512".

Sincerely,
Watson Ladd

<snip>
> Kenny
<snip>
> >Sincerely,
> >Watson Ladd

---

From: Alyssa Rowan <[email-masked]>
Date: Wed, 11 Feb 2015 06:56:28 +0000

On 11/02/2015 02:04, Watson Ladd wrote:

>> Yes, we are ruling out 2^448-2^224-1 and focussing on primes 
>> yielding curves at or near the 192 and 256 bit security levels. 
>> There was a long discussion on this on the list a while back, no
>>  clear consensus emerged on whether we should "stick" to the 
>> 192-bit and/or 256-bit security levels or go for "intermediate" 
>> values, and the chairs are now making a decision on this.

Um, what.

Chairs: No! I assumed that when you were asking these questions you were
including all of the 383<n<511 primes in the "192-bit" category, because
you _explicitly_ mentioned that choice of primes would take place
_afterwards_ - but instead, you've arbitarily eliminated most of the
leading candidates for an extra-strength curve?!

Does this also affect 41417?

Let me guess: Was your next question going to be, depending on the
choice, 2^384-317/2^389-21 and/or 2^512-569/2^521-1?

> This strikes me as extremely premature. […]

I concur. There was no consensus earlier because we didn't have the
performance data to make any decisions on technical grounds.

The performance data we have now looks pretty good for Goldilocks, as
I was tabulating…

For the chairs here to start making arbitrary choices may be
externally inappropriate and suggests the process has simply failed.
(Do we still have an NSA co-chair? ¬_¬)

This unexpected development changes my answer to a firm [No, No].

And inspires me to suggest that instead, perhaps an individual draft for
Goldilocks is the way to go here?

It's a leading candidate and an excellent compromise. It's a pretty
good choice for a high-performance, extra-strength, rigid curve
if we were going to recommend 2 curves.

Your arbitrary decision changes nothing with that. I think it may be
more likely to reach consensus than this ill-conceived guided choice
ballot.

- -- 
/akr

---

From: Damien Miller <[email-masked]>
Date: Wed, 11 Feb 2015 22:03:16 +1100 (AEDT)

On Wed, 11 Feb 2015, Alyssa Rowan wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
> 
> including all of the 383<n<511 primes in the "192-bit" category

me too (roughly - I thought the chairs would accept some "slop", e.g.
considering 2^448 being close enough to 2^512 to be considered).

> > This strikes me as extremely premature. [?]
> 

me too

> This unexpected development changes my answer to a firm [No, No].

me too

-d

---

From: "Paterson, Kenny" <[email-masked]>
Date: Wed, 11 Feb 2015 15:05:19 +0000

Hi Alyssa,

>leading candidates for an extra-strength curve?!

Sorry, no, that was not our intention.

It was not an arbitrary decision, though. We reviewed the long discussion
we had about security levels and how they are perceived externally by
non-cryptographers, and decided that it was better to stick to
easily-digested security levels. There was NOT consensus (even rough) on
that point, but the chairs believe that we need to make progress quickly
now, and this is one of the ways we are using to simplify the choices that
we need to make. Chairs have that discretion in IRTF, and we are
exercising it.

I don't believe it eliminates "most of the leading candidates for an
extra-strength curve" as you put it. There are several candidates with
good performance (albeit with the limited perf analysis we've seem on the
list) within a few bits of 384 and 512.

>choice, 2^384-317/2^389-21 and/or 2^512-569/2^521-1?

No. It was going to be a more open-ended question - what primes should be
considered at the 192-bit and/or 256-bit security levels? Presumably the
primes you mention would be then be put forward.

But the question also depends on the view of the list - maybe the
consensus will be that we shouldn't do any other security levels for now,
in which case the question would not need to be asked.

>
>> This strikes me as extremely premature. [Š]
>

We don't have a full set of performance data now either, and it seems
highly unlikely that we're going to get *all* the data that *all* list
readers might want to have within a reasonable time-frame. So we have to
move forward with the data we have seen so far, which while not complete
is certainly useful and indicative.

People who are uncomfortable about the amount of available performance
data for higher security levels should feel free to vote "no" on both
questions.

>I was tabulatingŠ

The choice was not arbitrary. See above.

We are trying to prevent a larger-scale process failure by steadily
narrowing the scope of our choices, based on reviewing what we've seen on
the list, our best judgement, and any consensus where we see it.

>This unexpected development changes my answer to a firm [No, No].

Noted.

>Goldilocks is the way to go here?

Please produce one if you feel strongly about it. We can even consider
adopting it as a RG draft, after we're done with the current work of
making recommendations to the TLS WG.

>Your arbitrary decision changes nothing with that.

The choice was not arbitrary. See above.

>I think it may be

Based on what I have seen on the list over the last 9 months, I tend to
disagree. There has been little consensus on pretty much anything
curve-related at any point. We very much need to start making decisions -
consensus-based where possible, and not if necessary.

Cheers

Kenny

>
>- -- 
>/akr
>-----BEGIN PGP SIGNATURE-----
>
>iQIcBAEBCgAGBQJU2v0cAAoJEOyEjtkWi2t6A9IP/jca62wUoaGl2Y447MTRv8xl
>1qg5XRQ6L1ysBMZz3LVaNKcTmqZl6L4881X2f3BB6Og/YCB2iwFRRUugmiTKBhxa
>RM3sdmyYHE7d2EDAvjChltUMorOWC+FocDX4GsMOc5wn3z+rnN5cvM0YOYKxa/sp
>A7GXL6efpQnIi+uee12V+D1Qw/IpbxOLQUQIQRMONhsMggfydLyRvm0Kuc490KBD
>iWHCqPrSawAiXUaWfwXQi2yOkUPKlYgfwkEYzf/fd5wO4koi+q0/8Eqkz6xbR36S
>KpqHHQMymf7HVLyTOMj8KXRozc3RFvMateAUAD2v9ODCJtGvcK4lyUiYJLM5/RFY
>7LjbQ0X/9iDQz9bxh2yAT5RorzcMAFIOMF4VSNXn9xg6dHFLhlOxURFO4ibN1E9a
>0Jrz5in1DwiZh3bWUeXgkVELVXMmtXoM6squSSvmwX86hWa/GH323R9XPwkOrBeV
>ej7qJQHUSdwOnih595hZk7tcUVel4L9JqHoFXL8YdyrxYazzuxun0vzGTkPpZMf7
>XZ2pgV4mgHC+nt609Iy3GVP4Yw1blkCCLH0+KGaH+PqXFM52hk/vxHw3Xnu1iSTd
>EkcnuObp5nGqW/NDB8J0Z/4kKBbaNh+iN/bP7Afx0G6iiHUt4GgMawsjxMYQ9+p9
>U5qccirwc3XQ3jC3Wqqy
>=1Nsn
>-----END PGP SIGNATURE-----
>
>_______________________________________________
>Cfrg mailing list
>[email-masked]
>http://www.irtf.org/mailman/listinfo/cfrg