North American Network Operators Group

Date Prev | Date Next | Date Index | Thread Index | Author Index | Historical

Re:RE: 1024-bit RSA keys in danger of compromise (fwd)

  • From: rkuhljr
  • Date: Mon Mar 25 21:39:44 2002

Does NSA need compromising US-based CA's private keys ? Probably not, because they either

(a) already have the private keys, obtained thru a combination of political, financial and intelligence resources.


(b) already have proceedings with the CA's in order to issue valid look-a-like certificates for any domain they want.  

If you look from the NSA's point of view, the investment might still sound reasonable for cracking the private keys.

Rubens Kuhl Jr.
>Since you are mentioning Verisign here, and CA authorities in general, has
>anyone considered that factoring the CA authority's key is far simpler than
>breaking the underlying key [no matter how large?]. Based on the
>implementation, the CA's key cannot be changed often or easily. Key
>revocations are not automatic or even respected, and the CA's key, once
>compromised, can sign any other key you'd like for a beautiful
>man-in-the-middle attack.
>The man-in-the-middle is the only attack these keys are designed to thwart,
>because if you can't access the physical bits, you don't have anything to
>decipher anyway. The beautiful thing about compromising the CA's key is that
>its not easily traceable.
>Deepak Jain
>-----Original Message-----
>From: [email protected] [mailto:[email protected]]On Behalf Of
>Len Sassaman
>Sent: Monday, March 25, 2002 6:32 PM
>To: [email protected]
>Subject: Re: 1024-bit RSA keys in danger of compromise (fwd)
>I discussed this in detail with Lucky before he posted it. I'll give a
>summary of how this affects the readers of NANOG here -- feel free to
>forward if you like.
>Prior to Bernstein's discovery the row-reduction step in factorization
>could be made massively parallelizable, we believed that 1024 bit keys
>would remain unfactorable essentially forever. Now, 1024 bit RSA keys look
>to be factorable either presently, or in the very near future once Moore's
>law is taken into account. However, at a price tag of $2 billion for a
>specialized machine, we have a few years before anyone outside of the
>intelligence community attempts this.
>What is most concerning to me is a few discoveries that were made while
>looking into the problem of widespread use of 1024 bit keys:
>First: Verisign appears to have no minimum requirements for the key sizes
>it will sign. I have discussed at length Verisign's active contributions
>to the hindrance of security on the Internet in the past (see the
>archives of my presentation at DEFCON 9), but I somehow missed this gem. A
>few months ago, in fact, Verisign issued a 384 bit certificate. (You could
>factor this on your desk top machine in days.) 512 bit keys are also
>fairly commonly signed by Verisign. (Ugh.)
>Question for people who know: Does Verisign allow you to submit CSRs for
>2048 to 4096 bit certificates?
>Second: As far as I can tell, OpenSSH (and I assume the commercial
>versions of SSH as well) offer no mechanism for enforcing the size of
>users' keys when public key authentication is turned on. This means that
>users could be placing (factorable) 512 bit keys in their
>~/.ssh/authorized_keys files, which is in effect worse than using weak
>passwords (as an attacker would leave no false login attempts for you to
>detect in your logs).
>I've mailed Theo de Raadt asking if OpenSSH has an undocumented mechanism
>for specifying minimum permitted key size that I don't know about. If
>there is one, I'll certainly post a follow-up.
>Lucky also mentions S/MIME, which has so many flaws I'm not going to
>address it; PGP, which places the risks squarely on the key-holder and
>doesn't prevent the use of 2048 bit keys (which should be safe even taking
>Bernstein's findings into account), so I'm not to concerned with that; and
>IPsec, which sadly isn't in widespread use.
>So, my main concerns are TLS, (which is damaged due to poor engineering on
>the part of Netscape and Microsoft, and uncouth policy issues on the part
>of Versign) and SSH, which may suffer from an easily correctable
>engineering flaw. Note that the biggest concerns don't have to do
>specifically with 1024 bit keys, but rather, small key sizes in general.
>On Mon, 25 Mar 2002, Todd Suiter wrote:
>> (forwarded w/o permissions, though this hit bugtraq earlier...t)
>> ---------- Forwarded message ----------
>> Date: Sat, 23 Mar 2002 17:38:02 -0800
>> From: Lucky Green <[email protected]>
>> To: [email protected]
>> Subject: 1024-bit RSA keys in danger of compromise
>> As those of you who have discussed RSA keys size requirements with me
>> over the years will attest to, I always held that 1024-bit RSA keys
>> could not be factored by anyone, including the NSA, unless the opponent
>> had devised novel improvements to the theory of factoring large
>> composites unknown in the open literature. I considered this to be
>> possible, but highly unlikely. In short, I believed that users' desires
>> for keys larger than 1024-bits were mostly driven by a vague feeling
>> that "larger must be better" in some cases, and by downright paranoia in
>> other cases. I was mistaken.
>> Based upon requests voiced by a number of attendees to this year's
>> Financial Cryptography conference <http:/>, I assembled and
>> moderated a panel titled "RSA Factoring: Do We Need Larger Keys?". The
>> panel explored the implications of Bernstein's widely discussed
>> "Circuits for Integer Factorization: a Proposal".
>> Although the full implications of the proposal were not necessarily
>> immediately apparent in the first few days following Bernstein's
>> publication, the incremental improvements to parts of NFS outlined in
>> the proposal turn out to carry significant practical security
>> implications impacting the overwhelming majority of deployed systems
>> utilizing RSA or DH as the public key algorithms.
>> Coincidentally, the day before the panel, Nicko van Someren announced at
>> the FC02 rump session that his team had built software which can factor
>> 512-bit RSA keys in 6 weeks using only hardware they already had in the
>> office.
>> A very interesting result, indeed. (While 512-bit keys had been broken
>> before, the feasibility of factoring 512-bit keys on just the computers
>> sitting around an office was news at least to me).
>> 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. Costs may well drop lower if one has the use of a
>> chip fab. It is a matter of public record that the NSA as well as the
>> Chinese, Russian, French, and many other intelligence agencies all
>> operate their own fabs.
>> Some may consider a price tag potentially reaching $1B prohibitive. One
>> should keep in mind that the NRO regularly launches SIGINT satellites
>> costing close to $2B each. Would the NSA have built a device at less
>> than half the cost of one of their satellites to be able to decipher the
>> interception data obtained via many such satellites? The NSA would have
>> to be derelict of duty to not have done so.
>> Bernstein's machine, once built, will have power requirements in the MW
>> to operate, but in return will be able to break a 1024-bit RSA or DH key
>> in seconds to minutes. Even under the most optimistic estimates for
>> present-day PKI adoption, the inescapable conclusion is that the NSA,
>> its major foreign intelligence counterparts, and any foreign commercial
>> competitors provided with commercial intelligence by their national
>> intelligence services have the ability to break on demand any and all
>> 1024-bit public keys.
>> The security implications of a practical breakability of 1024-bit RSA
>> and DH keys are staggering, since of the following systems as currently
>> deployed tend to utilize keys larger than 1024-bits:
>> - HTTPS
>> - SSH
>> - IPSec
>> - S/MIME
>> - PGP
>> An opponent capable of breaking all of the above will have access to
>> virtually any corporate or private communications and services that are
>> connected to the Internet.
>> The most sensible recommendation in response to these findings at this
>> time is to upgraded your security infrastructure to utilize 2048-bit
>> user keys at the next convenient opportunity. Certificate Authorities
>> may wish to investigate larger keys as appropriate. Some CA's, such as
>> those used to protect digital satellite content in Europe, have already
>> moved to 4096-bit root keys.
>> Undoubtedly, many vendors and their captive security consultants will
>> rush to publish countless "reasons" why nobody is able to build such a
>> device, would ever want to build such a device, could never obtain a
>> sufficient number of chips for such a device, or simply should use that
>> vendor's "unbreakable virtual onetime pad" technology instead.
>> While the latter doesn't warrant comment, one question to ask
>> spokespersons pitching the former is "what key size is the majority of
>> your customers using with your security product"? Having worked in this
>> industry for over a decade, I can state without qualification that
>> anybody other than perhaps some of the HSM vendors would be misinformed
>> if they claimed that the majority - or even a sizable minority - of
>> their customers have deployed key sizes larger than 1024-bits through
>> their organization. Which is not surprising, since many vendor offerings
>> fail to support larger keys.
>> In light of the above, I reluctantly revoked all my personal 1024-bit
>> PGP keys and the large web-of-trust that these keys have acquired over
>> time. The keys should be considered compromised. The revoked keys and my
>> new keys are attached below.
>> --Lucky Green