Re: Bernstein factoring machine one year later

From: David Hopwood (david.hopwood_at_zetnet.co.uk)
Date: 05/08/03 

Date: Thu, 08 May 2003 04:30:25 +0000

-----BEGIN PGP SIGNED MESSAGE-----

"Larry williams
> About this time last year, everyone was panicked that 1024-bit RSA keys
> were in danger of being easily factored.
>
> Eventually, guys like Schneier downplayed the risks,

Schneier doesn't know what he is talking about on this issue. His first
article about Bernstein's paper in Cryptogram clearly indicated that he
didn't understand the cost metric it used (in particular that simple
use of parallelism would not produce any improvement in that metric), and
his conclusions were based on that misunderstanding. If any of Schneier's
conclusions were right, they were right by coincidence.

> and everyone calmed down.
>
> So, approximatly one year later...is Bernsteins paper debunked, or is his
> proposal still merit some consideration?

Bernstein's paper never claimed that "1024-bit RSA keys were in danger of
being easily factored". The asymptotic estimates of the cost of breaking RSA
in that paper are correct, and have not been disputed.

There was some dispute about what the asymptotic cost of breaking RSA was
*before* Bernstein's paper - see <http://cr.yp.to/nfscircuit/history.html>.
(This is significant only in that it affects how much of an improvement
Bernstein's algorithm can be considered to be over the previous state of the
art; it is clear that it is the best algorithm, or collection of algorithms,
now.)

Basically, it was argued by Lenstra et al in <http://www.cryptosavvy.com/mesh.pdf>
that it was correct to measure cost on the basis of number of operations, because
*for small problem sizes*, say up to 512 bits, memory was not a limiting factor.
The problem with this argument is obvious: optimising only for operation count
doesn't scale to larger problem sizes (it's unlikely that it scales even to 1024
bits), and therefore it can't be considered a true asymptotic cost measure. The
*right* way to measure asymptotic cost is the way Bernstein does it, using the AT
(area*time) metric. Lenstra et al's argument against the AT metric is entirely
bogus (and not even self-consistent, since operation count suffers from the
same limitations that their paper criticises AT for).

In terms of practical rather than asymptotic costs, there have also been
considerable improvements, in particular for the matrix step on purpose-designed
hardware for ~1024 bit keys (see the appendix of Lenstra et al's paper, which is
derived from one of Bernstein's suggestions as described at
<http://cr.yp.to/nfscircuit/historyrouting.html>). This uses a physical
hardware arrangement involving chips that overlap, which could also be
useful for non-crypto applications requiring high bandwidth between processing
elements.

Before Bernstein's paper, a lot of people were saying that the NFS matrix step
was memory-limited. Now Lenstra et al are saying that the matrix step is not
memory-limited, and that for 1024 bit moduli the "bottleneck" is the sieving step.
However, as pointed out at <http://cr.yp.to/nfscircuit/balance.html>, if either
of the sieving or matrix step is significantly more costly than the other (for
any reasonable definition of cost), that just means that the trade-off between
the two steps needs to be recalculated, since the optimal choice of NFS parameters
always makes these two costs about the same. I have not seen any paper that does
this recalculation yet, but that is what Bernstein's grant proposal was for:

<http://cr.yp.to/nfscircuit/exactcost.html>
# The National Science Foundation has funded the grant for summer 2002, summer
# 2003, and summer 2004. Results will be announced on these web pages.

Meanwhile, IMHO 2048 or 3072 bit RSA keys are not unreasonable overkill, and
performance for keys of this length is unlikely to be a problem for most
applications. In particular, it would be a good idea to increase the size of
critical keys, such as CA root keys, to at least 2048 bits now (many are
still 1024 bits).

- --
David Hopwood <david.hopwood@zetnet.co.uk>

Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip

-----BEGIN PGP SIGNATURE-----
Version: 2.6.3i
Charset: noconv

iQEVAwUBPrmJujkCAxeYt5gVAQHm3Af9EclxEPx1b+WJg6dS4A0yALCVwqcxV3FP
oU+bNjKyilE0ouXkbYk+okA8dbjczuncb5piOBTOAi1CCY279MHyTnbMbiz5ZznS
Td67quaN9SrKzYcaMuVO9gZDvZ7XZJCgKwavLWSwcjPYIw4Yb1eMcx/Z+sRnRu2n
q/kQK0Ch2AS+ppJ6CosTW34mV5iKbO3JNOSmTqc2XC2nDV60aHI9U2f+/BMLrg1F
bRnSXgd2vbbHlKplfVwnBZaUGwoxXvb1hnn1cqTgwiQAzDu2VTs9zG3VpJ3dBaRU
ecZsEZW1DGtQwmu8K8Sj8bGcOfWyAtAd+3yUQ8Gi7OAe+tukS8j7qQ==
=kAo8
-----END PGP SIGNATURE-----

Relevant Pages

  • Re: Cut Citroen Key
    ... Coded keys and transponders can be ridiculously expensive to ... > obtain from main dealers; ... > well-known ripoff merchants) told me it could cost up to a grand to ... less than the saving I made, ...
    (uk.rec.cars.maintenance)
  • Re: Cut Citroen Key
    ... >> tidy sum off as I coped the sales manager as they were closing & he wanted ... Maybe the cost of the replacement keys would completely negate the ... my local vauxhall dealers (Hartwells, ...
    (uk.rec.cars.maintenance)
  • Re: Elliptic Curve Cryptography algorithm for key exchange
    ... > Anyway, another trend, particularly in .NET documentation that should be ... > only password derived keys. ... "An iteration count has traditionally served the purpose of increasing the ... This will increase the cost of exhaustive search ...
    (microsoft.public.platformsdk.security)
  • Re: LED Keyboard by 2006
    ... > It's a look up table of images which correspond to keys. ... hooking the keyboard controller to replace images as keys are ... display electronics in the keytop at a reasonable cost. ...
    (comp.sys.cbm)
  • Fwd: IP: 1024-bit RSA keys in danger of compromise
    ... 1024-bit RSA keys in danger of compromise ... moderated a panel titled "RSA Factoring: ... The security implications of a practical breakability of 1024-bit RSA ...
    (Security-Basics)