Re: [Cfrg] Elliptic Curves - poll on security levels (ends on February 17th)

[Mike Hamburg <[e-mail]>]

On 02/10/2015 10:05 AM, Phillip Hallam-Baker wrote:
>
>
> On Tue, Feb 10, 2015 at 12:39 PM, Stephen Farrell 
> <[e-mail] <mailto:[e-mail]>> wrote:
>
>
>
>     On 10/02/15 10:52, Alexey Melnikov wrote:
>     > CFRG chairs are starting a poll, containing 2 initial questions:
>     >
>     > Q1: Should CFRG recommend a curve at the 192-bit security level?
>
>     Not interesting.
>
>     >
>     > Q2: Should CFRG recommend a curve at the 256-bit security level?
>
>     Yes, approximately.
>
>     I would also be fine if there were compelling performance reasons
>     for one strength that is in between, e.g. 2^414-17 or similar, but
>     I would like only one strength level in addition to ~128-bit.
>
>     I'm not that convinced that anything more than the 128-bit level
>     is needed, but I believe it will be demanded regardless so having
>     just one such specified is better than a zoo of higher strength
>     curves.
>
>
> One of the reasons I really want a curve above 128 bit / Curve 25519 
> is precisely to clean up the zoo. And for that to happen there has to 
> be a clear advantage of the new curve over ECC384 which is what we 
>  (and I suspect most other CAs who do ECC) support today.
>
> And by clear advantage I mean, can be explained over the phone in as 
> short as time as possible. This has to be a complete no-brainer upgrade.
For the upgrade to be a no-brainer, the performance will need to be good.
> It isn't just a matter of not being interested in the 192 bit curve, I 
> want to phase out that strength.
>
> It is important that we have a back up algorithm that can be more or 
> less relied on to provide a ten year cushion in the case that Curve 
> 25519 is broken. But we don't need that cushion to be particularly 
> efficient.
Ah, good point!  And at the standard rate of 25 bits/year, 384 bits 
would only provide a 5-year cushion.
> On Tue, Feb 10, 2015 at 12:46 PM, Daniel Kahn Gillmor 
> <[e-mail] <mailto:[e-mail]>> wrote:
>
>     On Tue 2015-02-10 09:20:59 -0500, Stanislav V. Smyshlyaev wrote:
>     > Q1: No.
>     > Q2: Yes.
>     >
>     > For Q2: for Russia it is of primary importance that the curve is
>     strictly
>     > 512-bit, not 521-bit.
>
>     Can you elaborate on why this is of primary importance?  If a 521-bit
>     curve is as performant, what would cause you to reject it?
>
>
>
> The performance advantages only exist for a 64 bit machine.
So far as I know, nobody's done a high-speed implementation on 32-bit 
for proposed primes other than 2^255-19, 2^414-17, and 2^448-2^224-1; 
and I'm not aware of FPGA benchmarks for any pair of the proposed primes 
which can be compared.  But I don't see why 2^521-1 wouldn't perform 
well on many other bit sizes.  It doesn't stop being a Mersenne prime 
when you change bit sizes.
> Anyone building a dedicated crypto processor would probably choose 
> either 256 bits or 512 bits for the internal bus size.
It depends on the crypto processor.  The ones I've seen have either an 
N-long register for some arbitrary N (and a zwei-drei-N serial 
multiplier), or a 32- or 64-bit internal bus because they accelerate 
NIST curves with 32-bit-aligned coefficients.

Also, 256 bits is a monstrous fat bus.  It's absolutely enormous for a 
crypto bignum processor, since ECC is ALU-bound and not memory-bound.  
Maybe you're thinking of an accumulator register?
> The successor to DDR4 will almost certainly be a 512 bit I/O bus width.
Cache.  Nobody's going to hit DRAM in their ECC inner loop.
> If you are working at the silicon level then 521 bits is a lot harder 
> to manage than 512. Those extra 9 bits really do make a huge difference.
This is the exact opposite of the truth.  Hardware has the flexibility 
to use 34-bit multipliers, 88-bit internal buses and 119-bit registers 
if it wants.

Maybe in GPUs or in AVX512F vector registers you'd have a point, but 
you'll need to reduce the radix in both of those cases.  And if that 8x 
52-bit multiplier ever makes it into Intel hardware, the performance 
tier will be near 400 bits instead of 512.
> Going from 256 bits to 255 is not a big deal. But going above 512 
> makes things really painful.
[citation needed].  I know that the Germans have smart cards with 
1024-bit registers and this messes up their blinding, but otherwise I 
don't know of any platform where 521 bits has a performance disadvantage 
vs 512.  If you do, please provide a citation with actual performance 
numbers, rather than BS about a "512-bit bus".

-- Mike