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)
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: [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. > > >--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 <[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:/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 > > >
|