Re: [Cfrg] revised requirements for new curves

On 09/14/2014 07:22 AM, Phillip Hallam-Baker wrote:
> On Tue, Sep 9, 2014 at 4:23 PM, Adam Langley <agl@imperialviolet.org> wrote:
>
>> Although flexibility should be eliminated where possible, we believe
>> that forgoing sensible optimisations because of a fear that someone
>> might know a magic attack on a subset of curves and might be guiding
>> the selection them that would be a mistake. We are not looking for a
>> replacement for P-256 because we seriously worry that the NSA
>> backdoored it.
>
> Well maybe not. BUT one of the main advantages of moving to new curves
> is that the deployment of ECC has been gradual and incremental and has
> taken an enormous amount of time. And one of the main points to a flag
> day is not just burning the old ones, it is getting everyone to buy
> and hang the new.
>
>
>> We're looking for a replacement because we think that
>> we can get something much faster and simpler.
>
> Case in point here, can anyone who has these facts at their disposal
> tell us what sort of leverage random curves are believed to provide
> over primes close to a power of 2.
>
> The issue here is cryptographic leverage. I am prepared to do more
> work to increase the work factor for the attacker. But should I pick
> (say) a fast curve with 256 bits or a slower curve with 192 bits?
>
> If the two curves give exactly the same work factor or take exactly as
> long with different security, then the comparison is easy. But things
> rarely turn out so simple, chances are that the fast but bigger curve
> turns out to be a little bit slower and a bit more secure than the
> smaller one... oops.
>
>
> The basis for comparison is a little tricky...
>
> If I am doing RSA 2048 then I an doing four times the work of RSA 1028

As can be seen with timing of openssl speed rsa1024/rsa2048/2048, the 
factor is ~7.5 (e.g. in op.sec: 5940.2/791.2/111.8)

 > But if I am doing a symmetric cipher then 256 bits is more likely to
 > take about double 128

This is exactly 40% more work with AES in bulk encryption (10 rounds 
v.s. 14, not counting 1 XOR as a round).

>
> Oh and RSA 2048 does not give anywhere close to the square of the work
> factor of RSA1024 (i.e. double the bits). In fact that is one of the
> main reasons we have to look beyond RSA.

RSA 2048 and DH 2048 are on the margin of standard security at 110 bits, 
as considered by NIST. There is a measurable penalty for stronger 
security if one were to do the upgrade with RSA/DH/DSA.

1024 EDH in TLS is common today and still the default in OpenSSL.

>
>
> But if we plot the points on graphs of defender effort vs attacker
> work factor and look at the curves we can probably see quite easily
> what we are buying with the different approaches.
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg
>