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

[Lucky Green]

Anonymous wrote (quoting Adam):
> Adam Back wrote:
> > The mocking tone of recent posts about Lucky's call seems quite 
> > misplaced given the checkered bias and questionable 
> authority of the 
> > above conflicting claims we've seen quoted.
> 
> No, Lucky made a few big mistakes.  First, he invoked Ian 
> Goldberg's name as a source of the estimate, which was wrong. 
>  Second, he presented Nicko's estimate as being more 
> authoritative than it actually was, as Nicko makes clear 
> here.  And third, he fostered panic by precipitously revoking 
> his key and widely promulgating his "sky is falling" message.

Rather than continuing with guesses by those that were not present at
the time as to my motivations and objectives behind my post, allow me to
establish the facts and thought processes that lead to my original post.

Prior to the panel at FC, I held the belief that 1024-bit RSA keys could
not be factored in an operationally significant timeframe irrespective
of the budget of the attacker. I know that this belief was held by many,
if not most, of the implementers of cryptographic production systems and
believe that it was held by many, if not most, cryptographers. In some
sense, if this belief had not been held so widely, current debate would
not be as heated.

So let's look at the supposed mistakes Anonymous asserts I made:

1) As is the case with many panel discussions, and in many cases the
reason for choosing a panel format rather than an individual presenter,
the panelists, Ian Goldberg and Nicko van Someren, were selected to
represent subject matter experts in different areas of relevance to the
subject to be discussed: Ian's role was to help determine the
mathematical impact and correctness of Bernstein's proposal: are the
mathematical assumptions correct? Did the author make a mathematical
error in the paper? Ian did not identify errors in the math, though
cautioned that the interconnections required by an actual device would
represent a challenge of significant engineering impact. (Which, as
Nicko addressed in his previous posts to this list, he too considered to
be the limiting factor on performance).

Having thus established, as well as it could been established at the
time, that the paper that triggered the discussion appeared to not
contain mathematical errors, Nicko, as the subject matter expert in
building cryptographic hardware implementations, presented what the math
meant from an engineering perspective. In particular, can a device be
built based on the mathematical assumptions, how much would it cost to
build such a device, and what would the device's operating
characteristics be?

It is correct that Nicko presented estimates that literally were being
refined during the panel session. Naturally, I would not have even
considered posting such hasty generated estimates to a widely-read
mailing list. (More on that later).

Interestingly enough, the reaction to the estimates from the attendees
at the conference, which contained many well-known cryptographers, was
quite different from what I would have expected. Nobody stood up, and FC
is a conference quite amenable to open discussion, that they found the
suggestion that 1024-bit RSA could be broken by a well-resourced
attacker in operationally significant times to be unrealistic. The most
vocal comment in the ensuing discussion came from Yvo Desmedt, who
pointed out that no expert in the field should be surprised by these
results, since it was pointed out in Beth, Frisch, and Simmons
"Public-Key Cryptography: State of the Art and Future Directions, LNCS
578, published in back 1992, ten years ago, that 1024-bit keys would be
suitable for protection against a national adversary for about another
10 years: until about 2002. As it so happens, this the year 2002.

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.

2) Immediately after the panel, a reporter for the Financial Times in
attendance approached me, inquiring if these estimates had already been
published in the media. I told him that I was not aware of any such
publications and that this was the first time I had heard these
estimates. He informed me that he intended to publish this information
in a matter of days. I don't know if he wrote the article or not; I am
not a Financial Times subscriber.

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. We now, after the calculations had been made
public and because the calculations had been made public, that Nicko's
calculations contained an oversight which was not discovered until much
later. While the oversight changed the speed by which a 1024-bit RSA key
could be broken by such a device, no correction to the calculations that
I have seen so far indicated that 1024-bit keys could not be broken in
an operationally significant time frame well below the expectations of a
large percentage of users that had fielded 1024-bit systems.

In short, the information I relayed was as authorative as any
information you are likely to obtain from a panel discussion. If you
want information to be more authorative, you would have to cite a
research paper on the topic. Papers that I am sure we all hope will be
written soon. One might hold that only security-relevant information
that represents the long-term universal consensus of the academic
community should ever be distributed to the public. I respectfully
disagree with this viewpoint.

Given the above, I fail to see the foundation for the claims made by
Anonymous that I relayed the information to the community hastily or
presenting it as anything other than what it was: new (at least to me)
and interesting information with potentially significant security
implications to a potentially wide number of current users of public key
cryptography-based authentication and confidentiality systems.

3) One of the claims Anonymous makes is that I revoked my key
precipitately. I did indeed upgrade the entire security infrastructure
under my direct control to keys larger than 1024-bits following the to
me new estimates indicating the feasibility of attacking such keys. And
I didn't enjoy the process. There is an old saying, of which I heard
varying versions over the years in the cryptographic community, which is
also published in AC, though I don't know if it originated with Bruce or
predates the publication of AC. The saying is that there are two kinds
of cryptography: the kind that will keep your kid sister from reading
your writings and the kind that will keep national governments from
reading your writings. Of the two, it is the latter kind that interests
me and that presumably interests most working in the field.

Since my original post, even some of the loudest voices in support of
the position that 1024-bit keys are safe have published tables that
indicate that 1024-bit keys are expected to be breakable by a
well-resourced attacker in a few years, if they are not already. See the
RSA Labs FAQ and Bruce's recent Cryptogram for some of those estimates,
both of which are readily available on the web. I have seen similar
tables in other communications.

A key size which that is widely considered to be insufficient to offer
security against passive cryptanalytical attack by a dedicated attacker
and its customers is not a key size that I consider desirable. Nor is
this the level of security many customers of cryptographic products are
told they are afforded by 1024-bit keys.

Since Moore's Law has made it faster for me to use a 2048-bit key today
than it was for me to use a 1024-bit key back when I began using
1024-bit key on a daily basis as an alpha tester of PGP 2.0, the logical
step was to upgrade key sizes. Was my doing so precipitately? One could
argue that it was unscheduled. The sole reason why the upgrade was
unscheduled was because I previously failed to act on the results of the
various key size viability studies starting with Beth and Frisch, moving
to the NIST recommendations quoted in the RSA Lab's FAQ, to Bruce's 1995
figures republished in his latest Cryptogram in which he pointed out
that he predicted 7 years ago that 1024-bits should not be considered
sufficient against a well-resourced attacker by the year 2000. If there
is one mistake related to my action surrounding this debate that I
perhaps can reasonably be chastised for, it is that I failed to remove
1024-bit keys from my security infrastructure sooner.

As Bruce put it in his Cryptogram: "To me, the big news in Lucky Green's
announcement is not that he believes that Bernstein's research is
sufficiently worrisome as to warrant revoking his 1024-bit keys; it's
that, in 2002, he still has 1024-bit keys to revoke."

How the anonymous author of the post criticizing my action of
publicizing that I, and dozens of attendees at a cryptographic
convention, heard evidence that 1024-bit keys are in danger of
compromise hopes to gather support for his contention  from my having
failed to revoke my keys sooner is beyond my comprehension.

To just make a minor comment on Bruce's quote, Bernstein's paper simply
triggered the discussion now underway. Looking back at all the expert
predictions, from the workshop in 1992, to Bruce's estimates from 1995,
to the NIST recommendations years ago, it appears that time and Moore's
Law have simply crept up on us and nobody really noticed.

Which brings us to why the current discussion is so heated and my post
is by some considered to be so "alarmist": just about everybody with a
few notable exceptions, from the community, to the vendors, to the
public failed to act on the numerous expert predictions that all stated
the same fact for a decade: 1024-bit RSA keys are either breakable today
or will be so very shortly. To put it bluntly, a good percentage of us
have been caught with their pants down. In many cases leaving their
customers with deployed, difficult to upgrade, security infrastructures
that were either built or selected based on our recommendations.

Some of us, myself included, chose to bite the bullet, take the painful
remedial actions, and confess to it in public. Others chose to pursue a
different response, in some cases quoting predictions that state that
1024-bits are either already breakable today or will soon be breakable
while simultaneously asserting that by-and-large 1024-bit keys are good
enough. Others continue to insist that 1024-bit keys are unbreakable and
will remain so for the lifetime of a deployed system irrespective of how
well resourced the attacker. I sincerely hope they are correct, but
based on what I know now, I am no longer willing to base a security
infrastructure on that hope. Nor would I recommend doing so to others.
As always, I have faith that now that the interest has been raised and
the predictions of old have been dusted off and republished, the
scientific process will fulfill its role to determine fresher, more
accurate figures.

> We wouldn't be in this situation of duelling bias and 
> authority if people would provide some minimal facts and 
> figures rather than making unsubstantiated claims.

I fully agree that higher levels of details lead to faster, more
efficient analysis and a more efficient scientific process. What further
complicates matters is that the resolution of this question has
significant implications to many of the participants in the discussion.
And while healthy disagreement between participants helps further the
state-of-the art, some of these disagreements may lend themselves to
misinterpretation by interested, and potentially impacted, observers
outside the community.

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. The only way to avoid such confusion would be to exclude those
outside of the cryptographic community from the discussion by not
communicating with the information intermediaries that the press
represents. But given that the enterprise and the public places their
faith into the results of our work, and given the potentially large
implications if 1024-bit keys are subject to cryptanalysis, I believe
that those directly impacted by this issue have a right to know about
it. I therefore am quite unapologetic for not having limited my report
on the interesting events that took place at Financial Cryptography 2002
to a post to sci.crypt. Not that doing so would have necessarily ensured
that the debate would not spill over outside the cryptographic
community.

http://www.eweek.com/article/0,3658,s=712&a=24663,00.asp
http://www.counterpane.com/crypto-gram-0204.html#3

--Lucky


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