Re: [Cfrg] Comparing ECC curves

[Michael Hamburg <[e-mail]>]

Hi Phillip,

This has also been discussed on the [e-mail] list.  Trevor Perrin and I have discussed roughly the following:

There’s nothing magical about 128, 192 or 256-bit security levels.  We are hedging against improvements in the math of attacking ECC, not against specific levels of improved compute power.  So other things being equal, a bigger group order is better, but the question is how big a group order (and thus how good a hedge) can be bought for a given performance budget.  DJB has also advanced this argument in favor of Curve41417, and I’ve advanced it in favor of Ed448-Goldilocks.

Obviously we want only a few curves of fairly different security levels, so something aimed at 2^160 work isn’t interesting.  We should pay attention to which curves are efficient, i.e. attain the best security level compared to their performance.  Ideally, it would be best to select only two new curves instead of three, i.e. a 128-ish-bit secure one and a much stronger one.

Since Karatsuba multiplication is suitable for the curves in question, we should expect EC software to take time proportional to T(group size) := log(group size) ^ (1 + log 3 / log 2) time.  So a simple benchmark would be that, other things being equal, we should look especially closely at curves where T(group size) / (time for ECDH or sign or verify) is largest.  Obviously this will vary by platform and implementation, but it seems like a reasonable benchmark between security levels.

For example, on Intel Sandy Bridge, Microsoft’s Ed-384-mers takes 617kcy to compute a shared secret (not counting decompression).  Ed448-Goldilocks takes 674kcy (counting decompression) and Ed-512-mers takes 1293kcy (not counting decompression).  So their “efficiency” scores on that platform are roughly 7.7, 10.5, and 7.7 respectively.

This is why Trevor and I (and perhaps also DJB?) believe that a fast, ordinary-security curve like Curve25519 and a high-security curve like Goldilocks or Curve41417 would be a good pair of alternatives in future deployments.

Cheers,
— Mike

On Jul 23, 2014, at 3:28 PM, Phillip Hallam-Baker <[e-mail]> wrote:

> Thanks to all the presenters, some thoughts on comparing like with like:
> 
> 1) How do we compare algorithm A taking X cycles and offering a work
> factor 2^Y with algorithm B taking 2X cycles and offering a work
> factor 2^(Y+Z)?
> 
> My answer here is that I am interested in the yield ratio i.e.
> [attacker work factor] / [defender effort]. so having the defender do
> twice as much work to get an improvement of one bit is not a win.
> 
> We can define an exclusion rule: B, is definitely not going to be
> interesting as an alternative to A if Z >= 1. Doubling the work factor
> is not a win if I have to do twice as much work.
> 
> But that still leaves open the question of how much defender effort it
> is worth to increase the difficulty by a factor of two.
> 
> 
> 2) Should the security levels be maximums or minimums?
> 
> Looking through the Microsoft presentation I see that they have chosen
> work factors of 128, 192 and 256 bits. This is reasonable of course
> but maybe not the best way to compare like with like. Because the real
> limitations here are the machine resources which nowadays come in
> units of 64 bits.
> 
> What I am really interested in is how much security you can provide
> for an n*64 bits wide datapath. I do not want to have to mess about
> with a129 bits to achieve 128 bits security. If someone can do the
> math significantly faster then I'll take 127 bits. But I certainly
> don't want to go below 120 bits unless the advantages were phenomenal.
> 
> 
> 3) Do we need to consider 2^192 work factor?
> 
> I can't see any case where I am interested in a work factor of 2^192.
> Either I am willing to make some concession to performance or I want
> it gold plated and 2^256. I would quite like to see the 2^192 work
> factor nuked.
> 
> The only reason for going above 2^128 is that I don't trust the
> algorithm. Its not about increasing the work factor by 2^64, its about
> increasing the safety margin in the case of a cryptanalytic attack. I
> have seen attacks that reduce the work factor to the root of the
> intended one (i.e. 2^n becomes 2^(n/2)). I can't think of a better one
> that has been discovered offhand (most are not that good of course).
> So 2^256 makes me feel like I am sufficiently protected against
> algorithm compromise while 2^192 is kinda marginal.
> 
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg