Re: [Cfrg] ECC reboot (Was: When's the decision?)

[Watson Ladd <[e-mail]>]

On Oct 17, 2014 1:22 PM, "Phillip Hallam-Baker" <[e-mail]>
wrote:
>
> On Thu, Oct 16, 2014 at 2:29 PM, Alyssa Rowan <[e-mail]> wrote:
> > -----BEGIN PGP SIGNED MESSAGE-----
> > Hash: SHA512
> >
> > On 16/10/2014 17:08, Paterson, Kenny wrote:
> >
> >> Our first task should be to finalise the requirements that we will
> >> use to guide the selection process. I think we are close, with a
> >> couple of outstanding issues:
> >
> > Alright, so let's try to get things in high gear and argue those out…?
> >
> >> 1. Amount of "wiggle room" that should be permitted.
> >
> > Broadly: I think what we're aiming for is probably one faster/strong
> > curve, and one stronger/fast curve.
> >
> > Given the strong preferences of some to minimise the number of curves,
> > it looks to me like ­≈384 is almost-definitely dropped, leaving us
> > with something near ≈256 and something near ≈512.
> >
> > We seem to be in agreement that wiggle room on ≈256 would include
> > fields of 2^255-19 as well as 2^256-189 in scope.
> >
> > For the paranoid-strong, performance-second ≈512, 2^512-569 very
> > obviously falls within scope.
>
> Agree so far.
>
>
> > I put forth that 2^521-1 also falls within scope. It's not very far
> > away, and it's a true Mersenne prime rather than a pseudo-Mersenne,
> > and they do not grow on trees - no others fall near our criteria (the
> > next lowest is 2^127-1 which is way too small, and the next biggest is
> > 2^607-1). They are very attractive - attractive enough for 4 (?)
> > independent research groups to independently arrive on E-521, and
> > SECG/NIST to have independently picked the same prime years ago for
> > secp521r1.
>
> It is a Mersenne but the performance advantage is compromised by it
> being larger than 512 bits. That means every memory operation is going
> to break stride. Which is a really bad tradeoff for the marginal
> improvement in speed.

Shouldn't this show up in benchmarks? Or is this a performance issue that
doesn't actually do anything with performance?

>
>
> > [Previous discussion countering this point: Sean Parkinson @ RSA
> > suggested stepping over a power of 2 is "only going to hurt
> > performance in the future". Phillip Hallam-Baker also thought anything
> > that is not less than a clean multiple of a power of two "may cause
> > severe performance hits on future architectures", mentioning 512-bit
> > memory buses on graphics cards?!
>
> There is a good reason for that. What we call 'graphics cards' are
> really just what we used to call a vector unit.
>
> Getting someone to build purpose built ECC accelerators is hard and
> expensive. I can buy an nvida card that with a ridiculous number of
> cores that I can pretty much program to do anything I like.
>

Actually,  there are major issues with offloading to graphics cards in
latency. My guess is that CPU performance is fast enough that graphics
cards don't win out.

>
> Its not just a question of speed, its a question of the amount of
> microcode required to implement ECC math as a native function of the
> GPU.

Right: an extra load is so hard.
>
>
> > although I'm not convinced that's
> > actually primarily relevant to an implementation of a high-strength
> > curve. We will, of course, evaluate performance of contenders in Phase
> > II, future architectures can be more-or-less anything that works well,
> > and performance implications usually aren't anything like so obvious…
> > Aren't Mersennes actually particularly _good_ performance-wise?]
>
> That depends on whether you are looking for a reason to include or
exclude.
>
> At the ~512 level, what I am looking for is a curve that absolutely
> nobody is going to be able to suggest is suspect as being bongoed.
> 2^512 is a round number that needs no explanation. 2^521 isn't.
>
> The Web PKI will almost certainly be based exclusively on the ~512
> level curve. The roots certainly will. So the performance advantage of
> issuing end entity ~256 certs would be very small.
>
> Where I think ~256 keys will be used is for ephemeral mix ins. So I
> exchange a master session key M with the ~512 bit key, use an
> ephemeral ~256 to create a second session key E and then derive my
> encryption and authentication keys using a one way function on M and
> E. That preserves the ~512 work factor for confidentiality and adds a
> ~256 work factor for forward secrecy.
>
>
> So I am willing to be more flexible on ~256 than ~512 because for my
> applications the attacker always has to break the ~512.
>
>
> > I put forth that 2^414-17 and 2^448-2^224-1 might fall outside "wiggle
> > room" there, although I do so very reluctantly as I think it's a shame
> > to exclude them on that basis if they have otherwise nice properties,
> > and they do seem to have very good performance for their strength.
>
> I agree. They are a little faster but we have to give up a lot of
> security to get that speed. Its not 64 bits, its a 2^20 reduction in
> work factor. I want them bits.
>

As Mike Hamburg points out downthread, TLS doesn't work that way.

Furthermore, P384 is in use now. I wish someone would toss it into eBATS,
but I think both Curve 41417 and Goldilocks are faster by something, can't
recall what.

>
> >> 31/10/14 (2 weeks from now): we agree on whatever benchmarking
> >> system we're going to use for performance measurements. (Right now,
> >> supercop seems like the front runner to me.)
>
> I think a significant performance difference is a tie breaker but not
> the best determinant. What I see as being convincing are:
>
> 1) Difficulty of screwing up the implementation (see Watson Ladd's post).

Which has little to nothing to do with curves. See DJB's curves coordinates
and computations email.

>
> 2) Legacy deployment.

See above.
>
>
> Given the way that I think we are likely to use ~256 and given the
> fact that DJB has established a large user base for the curve already.
> I am willing to suggest we just let him win on that one unless there
> is at least a 10%, maybe a 20% speed advantage he missed.
>
> For ~512 I want the Platinum level security, whatever it takes.
>
> _______________________________________________
> Cfrg mailing list
>[e-mail]
>http://www.irtf.org/mailman/listinfo/
<http://www.irtf.org/mailman/listinfo/cfrg>cfrg