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. or (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.

Regards,

Deepak Jain AiNET

-----Original Message----- From: owner-nanog@merit.edu [mailto:owner-nanog@merit.edu]On Behalf Of Len Sassaman Sent: Monday, March 25, 2002 6:32 PM To: nanog@merit.edu 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.

--Len.

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 <shamrock@cypherpunks.to> To: cypherpunks@lne.com 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:/www.fc02.ai>, 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". http://cr.yp.to/papers.html#nfscircuit

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