Lucky's 1024-bit post [was: RE: objectivity and factoring analysis

Anonymous nobody at remailer.privacy.at
Thu Apr 25 14:47:06 EDT 2002


Lucky Green writes:
> Given how panels are assembled and the role they fulfill, I thought it
> would be understood that when one writes that certain results came out
> of a panel that this does not imply that each panelist performed the
> same calculations. But rather that that the information gained from a
> panel (Ian: math appears to be correct, Nicko: if the math is correct,
> these are the engineering implications of the math) are based on the
> combined input from the panelists. My apologies if this process of a
> panel was not understood by all readers and some readers therefore
> interpreted my post to indicate that both Ian and Nicko performed
> parallel engineering estimates.

What he wrote originally was:

: The panel, consisting of Ian Goldberg and Nicko van Someren, put forth
: the following rough first estimates:
:
: While the interconnections required by Bernstein's proposed architecture
: add a non-trivial level of complexity, as Bruce Schneier correctly
: pointed out in his latest CRYPTOGRAM newsletter, a 1024-bit RSA
: factoring device can likely be built using only commercially available
: technology for a price range of several hundred million dollars to about
: 1 billion dollars....
: Bernstein's machine, once built, ... will be able to break a 1024-bit
: RSA or DH key in seconds to minutes.

It's not a matter of assuming parallel engineering estimates, but rather
the implication here is that Ian endorsed the results.  In saying that
the panel put forth a result, and the panel is composed of named people,
it implies that the named people put forth the result.  The mere fact
that Ian found it necessary to immediately post a disclaimer makes it
clear how misleading this phrasing was.

Another problem with Lucky's comment is that somewhere between Nicko's
thinking and Lucky's posting, the fact was dropped that only the matrix
solver was being considered.  This is only 1/2 the machine; in fact in
most factoring efforts today it is the smaller part of the whole job.
Neither Nicko nor Ian nor anyone else passed judgement on the equally
crucial question of whether the other part of the machine was buildable.

> It was not until at least a week after FC that I contacted Nicko
> inquiring if he still believed that his initial estimates were correct,
> now that that he had some time to think about it. He told me that the
> estimates had not changed.

It is obvious that in fact Nicko had not spent much time going over
his figures, else he would have immediately spotted the factor of 10
million error in his run time estimate.  Saying that his estimates had
not changed is meaningless if he has not reviewed them.

Lucky failed to make clear the cursory nature of these estimates, that the
machine build cost was based on a hurried hour's work before the panel,
and that the run time was based on about 5 seconds calculation during
the panel itself.  It's not relevant whether this was in part Nicko's
fault for perhaps not making clear to Lucky that the estimate stood in
the same shape a week later.  But it was Lucky who went public with the
claim, so he must take the blame for the inaccuracy.

In fact, if Lucky had passed his incendiary commentary to Nicko and
Ian for review before publishing it, it is clear that they would have
asked for corrections.  Ian would have wanted to remove his name from
the implied endorsement of the numeric results, and Nicko would have
undoubtedly wanted to see more caveats placed on figures which were
going to be attached to his name all over the net, as well as making
clear that he was just talking about the matrix solution.  Of course
this would have removed much of the drama from Lucky's story.

The moral is if you're going to quote people, you're obligated to check
the accuracy of the quotes.  Lucky is not a journalist but in this
instance he is playing one on the net, and he deserves to be criticized
for committing such an elementary blunder, just as he would deserve
credit for bringing a genuine breakthrough to wide attention.

> For example, Bruce has been quoted in a widely-cited eWeek article that
> "I don't assume that someone with a massive budget has already built
> this machine, because I don't believe that the machine can be built".
>
> Bruce shortly thereafter stated in his Cryptogram newsletter that "I
> have long believed that a 1024-bit key could fall to a machine costing
> $1 billion."
>
> Since these quotes describe mutually exclusive view points, we have an
> example of what can happen when a debate spills over into the popular
> media.
> ...
> http://www.eweek.com/article/0,3658,s=712&a=24663,00.asp

They are not mutually exclusive, and the difference is clear.  In the
first paragraph, Bruce is saying that Bernstein's design is not practical.
To get his asymptotic results of 3x key length, Bernstein must forego the
use of sieving and replace it with a parallel ECM factoring algorithm
to determine smoothness.  Asymptotically, this is a much lower cost
approach for finding relations, and this asymptotic improvement plays
a major part in Bernstein's dramatic result.

However, this specific improvement is almost certainly impractical for key
sizes in current use.  There is no way that sieving is going to be slower
than taking each value and doing a brute force ECM factoring effort on it!
We came up with estimates on this list a few weeks ago suggesting that
even with unreasonably extreme parallelism and clock rates, that this
approach would take 100 million years to factor.  (These estimates were
posted 3 weeks before Lucky's alarmist pronouncement.)

What Bruce is also saying, though, is that with sufficient money and
effort using conventional technology for the sieving, it might indeed be
possible to build a machine that could factor 1024 bit keys.  This would
not use Bernstein's sieving improvements and hence would not be a matter
of using his machine.  It has been known for years that factoring 1024
bit keys should be about 10^7 times more expensive than factoring 512.
And 2048 bit keys are another 10^9 times harder.  Obviously every key
can be factored with sufficient resources.

The bottom line is that Lucky made a mistake.  He went public with a
dramatic announcement that turns out to be based on inaccurate and off the
cuff estimates which have since been disclaimed by the relevant parties.
He should have waited a few weeks for Nicko to post his estimates and for
others to respond before sounding the alarm.  It was wrong to broadcast
an urgent warning based on the limited and crude figures available at
the time, which now appear to greatly underestimate the true costs.

Fine, people make mistakes, but they should take responsibility
afterwards.  It would be nice to see Lucky post a message to Bugtraq and
wherever else his first one appeared saying that things don't look quite
so dire as they appeared a few weeks ago, that at this point we have to
adopt a wait and see stance.  But it's probably not going to happen.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com



More information about the cryptography mailing list