Re: [TLS] Next protocol negotiation

[Adam Langley <[e-mail]>]

On Thu, Jan 21, 2010 at 1:51 PM, Dean Anderson <[e-mail]> wrote:
> I don't think so. As CPU's speed up improving encryption/decryption
> times, so does cracking improve, resulting in deployment of more
> difficult ciphers, leaving time to encrypt roughly unchanged.  So I
> don't think encryption gets "easier" or less time-consuming in the
> future. Again, an impression, but consider that the RSA-768 key was just
> cracked, and so we recommend getting rid of 1024 bit keys.

Clients get the easy side of the RSA operations of course. If we take
four different hosts from the ECRYPT benchmarks[1] we can get the
number of cycles required to perform an RSA encryption of a given bit
size:

1024    203820  171138  79404   302432
1536    317448  260392  117587  519928
2048    470556  386199  157766  779696
3072    866280  704583  271095  1604108
4096    1396896 1067935 387822  2423856

(CPUs are, in order, Atom (molecule), Core2 (nmui0247), A64 X2 (mace),
Power5 (nmi0154))

Normalising each of these so that the time taken for 1024 is 1:

1024    1       1       1       1
1536    1.557   1.522   1.481   1.719
2048    2.309   2.257   1.987   2.578
3072    4.250   4.117   3.414   5.304
4096    6.854   6.240   4.884   8.015

However, from the 768-bit factoring paper[2] they suggest that a
1024-bit key is 5x harder to factor than a 768-bit key, for only a
1.3x increase in the number of bits. So it appears the that defender
has the advantage as processor speeds increase (modulo quantum
factoring, should it ever be tractable).

[1] http://bench.cr.yp.to/results-encrypt.html
[2] http://eprint.iacr.org/2010/006.pdf

> And e.g some
> interesting results were published for AES-256, suggesting it will be
> easier to crack than originally anticipated, meaning it will be obsolete
> sooner.

You can repeat the procedure above for stream ciphers too. Again, the
defenders appear to have the advantage over time.


AGL