Re: [Cfrg] Actual security levels for IETF crypto

[Phillip Hallam-Baker <[e-mail]>]

On Tue, Oct 28, 2014 at 1:18 PM, Mike Hamburg <[e-mail]> wrote:

>
>  Is it really modest?  P-256 is 4 times as fast as P-521. We don’t have
>> numbers for a 512-bit curve, but Goldilocks is just over 3 times slower
>> than Curve25519, whereas P-521 is 23 times slower.
>>
>> So is there an argument to use #2 that is strong enough to overcome the
>> performance penalty argument?
>>
>> Yoav
>>
>>  Actually, we do have numbers.  They aren't quite apples-to-apples
> because of point formats, point compression, hashing and different
> benchmarking suites, but they're close.  And of course, keep in mind that
> these aren't benchmarks of curves, but of implementations.
>
> Curve25519 takes 194kcy for an ECDH on Sandy Bridge (SUPERCOP).  I'm using
> Sandy Bridge and ECDH because we have the most benchmarks on that
> combination.  Point compression built-in.
>
> Microsoft's ed-256-mers takes 234kcy (Bos et al, published).
>
> P256 takes 374kcy for an ECDH on Sandy Bridge (Gueron and Krasnov,
> published).
>
> ed-384-mers takes 617kcy (Bos et al, published).
>
> Ed448-Goldilocks takes 667kcy (SUPERCOP), just under 3.5x Curve25519.
> Point compression built-in.
>
> ed-512-mers takes 1293kcy (Bos et al, published).
>
> Granger and Scott posted an E-521 implementation and claimed much better
> performance than this, but their implementation is not constant-time and
> their numbers didn't account for TurboBoost. Samuel Neves measured it with
> TurboBoost disabled and got 1030kcy on Sandy Bridge.
>
> I wrote an experimental constant-time implementation of E-521 using
> Goldilocks as a framework, and measured it at 803kcy on Haswell. This would
> probably be in the same neighborhood as that 1030kcy on Sandy Bridge (~15%
> IPC difference and no AVX2).  Point compression built-in.
>
> Trevor Perrin clocked OpenSSL 1.0.2's NIST P-521 at 1714kcy on Haswell,
> which would probably be just under 2MCy on Sandy Bridge.
>
> OpenSSL's NIST-P-384 implementation isn't optimized yet, so it's even
> slower than P-521 at 2.2M Haswell cycles (Trevor again).
>


For the sake of comparison, where do RSA1024 and RSA2048 fit in?

[Accepting that the public/private key advantage flips]

And lets not forget that the performance issues are different for client
and server.


First, lets take the constrained devices off the table. Anything that is
struggling with X25519 is not going to look at anything stronger. So that
leaves non constrained clients and high volume servers.

As far as the client goes, the baseline is the RSA2048 public key
operation. Anything that takes that number of cycles or less is going to be
OK. Its moot anyway as the client does not make the choice.

On the server side things are a little more complex. But either it is
crypto limited or limited by something else. All the curves are going to be
faster than RSA2048 because we get the asymmetric advantage for private key
operations but in the sort term at least, we might lose the crypto
accelerator board advantage.


So I can see a strong argument for ~256 on the server and something much
higher (i.e. ~512). I don't see a case for something that is neither one
nor the other.