The greatest brute-force attack successes that we know of are generally reversing password hashes, because the input spaces and/or effective input spaces under some model of a password's structure are so small. People have achieved very effective results with that, often using special hardware.
The most common attack model for this is "get ahold of a hashed password list, try to reverse as many as possible, then try to see if any has re-used those passwords on other systems". Spy agencies might be doing that too. By contrast, as Bunnie says, modern algorithms have a very large safety margin so brute-force against a random key is very implausible without some significant new algorithmic insight.
So one question is, are there significant security-sensitive deployments that are still out there of obsolete stuff with too short a keylength? 1024-bit RSA, 1024-bit DH, DES, export ciphers?
If, on the other hand, it's really mostly about password hashes, where brute force has been known to be so effective, are there any other attack contexts where the ability to reverse a password hash would be useful?
This is off the top of my head and I'd welcome correction:
Large scale password cracking has a much clearer payoff than attacks on 1024 bit DH, which have to be targeted to individual (probably TLS) connections. The RSA that most of the Internet depends on is brokered by CAs --- so, problem 1, the USG already owns CAs and doesn't need supercomputers to get valid certificates, problem 2, the most valuable "authentic" CA signatures are 2048 bit and far outside the capabilities of an IBM supercomputer, and problem 3, even after breaking that certificate you still have to target individual TLS connections to use it.
On the other hand, you don't need the world's most powerful supercomputer to effectively crack passwords.
It's not unlikely that the simplest explanation here is just "the NSA will do whatever thing secures it the largest budget". That doesn't mean they won't use those budget-enhancing projects in ways that will shock our conscience!
A friend pointed out privately that a more realistic target for this kind of firepower is IPSEC VPNs, which overwhelmingly use finite field Diffie Hellman. So there's that.
I suppose I'm also wondering if there's an authentication protocol where the challenger actually tells the prover what hash it has to match. Does a challenger ever effectively say "Please tell me the secret whose SHA256 is equal to fcdf324499312efa027b5033513b0c0968f74ae7ba81a271ae62b3dda2cd4143 in order to proceed"?
Maybe protocols where the attacker has access to a signature over some data, but doesn't get access to the signed data in plaintext? Then the attacker could try to brute-force values of the signed data using the hash that forms the basis of the signature?
I think you're describing most KDF attacks, of which password hashes are particular (and easy) example. I can't think of an instance of this attack that isn't password hashes that is so widely deployed that it would be economical to invest in 9-figure supercomputers to attack it, but that obviously doesn't mean one doesn't exist.
Think about any software updates you do (Windows Update, apt, yum, etc). All these systems rely on distributing a cryptographic ally signed manifest of what each files hash should be.
If you can forge the hash of a file, or the signature on that manifest, there are hundreds of different ways you can easily replace one file for another in transit over the internet.
We're also not a supercomputer advance away from breaking SHA2. There are hash-designing cryptographers who believe we may never break SHA2 with conventional computers.
That's a very different attack than I was looking for; you've described a second preimage attack, which would be considered a fundamental weakness of the hash. I was looking for a protocol where a comparatively small amount of signed data (let's say less than 90 bits) is kept secret, but can potentially be brute-forced on an appropriate supercomputer.
I'd guess something like Quantum Insert + targeting unprotected connections. Which I'd imagine there are still a lot of out there (circa pre-2000).
I'd be curious if there's any older network gear that provides a hash-based rather than connection-based security model. It seems like the thing that might have seemed like a good idea to a military 40 years ago.
> so, problem 1, the USG already owns CAs and doesn't need supercomputers to get valid certificates
I'm sure it's gotten a lot tougher out there for this kind of thing since the Comodo and DigiNotar attacks. Looking forward to more mandatory CT mechanisms!
Widespread modern encryption methods like RSA, named for the initials of the cryptographers who developed it, rely on the use of hugely complex numbers derived from prime numbers. Speaking very roughly, so long as those original prime numbers remain secret, the integrity of the encoded data will remain safe. But were someone able to factor the hugely complex number — a process identical to the sort of math exercise children are taught to do on a chalkboard, but on a massive scale — they would be able to decode the data on their own. Luckily for those using encryption, the numbers in question are so long that they can only be factored down to their prime numbers with an extremely large amount of computing power. Unluckily for those using encryption, government agencies in the U.S., Norway, and around the globe are keenly interested in computers designed to excel at exactly this purpose.
The point of modern RSA is that we use a modulus that can't be factored by any conceivable computer, with limits derived from the physics of computation and projected far out into the future. We aren't a supercomputer advance away from factoring 2048 bit moduli. The government's "keen interest" in that problem is irrelevant.
We've known for coming up on 2 decades, at least (from Eran Tromer in 2001-2003) that 1024 bit moduli aren't safe. There's been speculation for years that the NSA is standing up giant compute clusters in Utah to target 1024 bit discrete logs (it's speculation because it's hard to see how those attacks make economic sense, even with advances in batch attacks). If we want to suppose that IBM and NSA are mounting a supercomputing attack on weak crypto, fine. The presumption that these attacks will get more viable is why, for instance, the WebPKI is urgently scrubbing itself of 1024 bit keys and has been for years.
But that's not what this article says. Instead, it puts forward a narrative that the USG is collaborating with IBM to build supercomputers that would break all of RSA. Not only is that not what's happening, but if it was, IBM and the USG would be doing us a great service, because we can't rely on cryptography that is a supercomputing advance away from being broken.
Needless to say, they're not really doing us a service, and they're not really about to break RSA, and breaking RSA isn't a really big IBM purchase order away from happening.
Sorry to see you conclude the piece, or that portion, is malpractice :-\
The paragraph you quote was intended to give an overview of one type of work a machine like WindsorGreen might do, in broad terms. While it's true we mention RSA as a very basic example of the sort of thing a government would be /interested/ in breaking, we also specifically quote a security researcher saying WindsorGreen “might also have applications for things like … breaking older/weaker (1024 bit) RSA keys” and then quote another (bunnie) saying "“Even if [WindsorGreen] gave a 100x advantage in cracking strength, it’s a pittance compared to the additional strength conferred by going from say, 1024-bit RSA to 4096-bit RSA or going from SHA-1 to SHA-256.”
It's really not clear to me how the piece "puts forward a narrative that the USG is collaborating with IBM to build supercomputers that would break all of RSA" -- indeed, it specifically says this would be of use primarily against 1024-bit RSA.
That said, I'm definitely curious how you think the piece could have framed this more obviously for the lay reader.
I'm guessing Thomas thinks that only problems that supercomputers can, in fact, usefully attack should be mentioned as the likely targets of this computer. :-)
Although the experts quoted only mention 1024-bit keys as targets of attack, the particular paragraph that Thomas mentioned really seems to suggest that RSA in general may be within reach. The worst problem is the last two sentences:
> Luckily for those using encryption, the numbers in question are so long that they can only be factored down to their prime numbers with an extremely large amount of computing power. Unluckily for those using encryption, government agencies in the U.S., Norway, and around the globe are keenly interested in computers designed to excel at exactly this purpose.
This doesn't mention anything about key lengths, but in a sense key lengths are nearly the whole story with regard to the feasibility of brute-force attacks against RSA. Particularly, both sentences refer to "those using encryption" as an undifferentiated class put at risk by this sort of project, and that's one thing that particularly suggests that all of RSA is at risk.
I appreciate the explanation from schoen, I can grasp the argument more clearly.
I do believe that is an aggressive reading of the paragraph, out of its context, and that "malpractice" is unfair.
The paragraph you quoted is followed, after just a single intervening paragraph, by this, which I would argue speaks explicitly and accurately to your point:
---
A very important question remains: What exactly could WindsorBlue, and then WindsorGreen, crack? Are modern privacy mainstays like PGP, used to encrypt email, or the ciphers behind encrypted chat apps like Signal under threat? The experts who spoke to The Intercept don’t think there’s any reason to assume the worst.
“As long as you use long keys and recent-generation hashes, you should be OK,” said Huang. “Even if [WindsorGreen] gave a 100x advantage in cracking strength, it’s a pittance compared to the additional strength conferred by going from say, 1024-bit RSA to 4096-bit RSA or going from SHA-1 to SHA-256.”
Translation: Older encryption methods based on shorter strings of numbers, which are easier to factor, would be more vulnerable, but anyone using the strongest contemporary encryption software (which uses much longer numbers) should still be safe and confident in their privacy.
---
If someone read a sentence saying encryption users are unlucky that the U.S. government is buying supercomputers to crack encryption, which used RSA as an example of something the government wanted to crack, and concluded that this means RSA is broken, they would be cleared of this misreading within a few paragraphs, no?
We are diligent in our reporting, research, editing, and fact checking; this piece involved no small number of staffers doing all of those things and more. A term like "malpractice" we take seriously, but seems to have been tossed off a bit casually here.
"Don't think there's any reason to assume the worst"? We know there's no reason to assume the worst, or really even suspect it. RSA-4096? The 2048-bit moduli which are the industry standard today are hopelessly out of reach of conventional computers; your story implicitly makes a case that people might be at risk for using them. The difference between 2048 and 4096 is a lot of computing power for defenders.
There are other quotes in the article that are also presented without enough context to avoid misleading. For instance, you can see speculation in this thread about the utility of this system for breaking "signatures" on updates --- but again, that's only possible if the systems in question are already using weak cryptography.
I stand by my criticism of the article. The paragraph I quoted was poorly constructed, and I think the narrative subtext of the whole piece is "worry that the USG is going to subvert all mainstream cryptography". That narrative is extraordinarily harmful. As someone who has done some recent pro-bono training for at-risk people, it's hard enough to get people to adopt best practices without having to beat back concerns that all the effort is for naught.
I further agree with everyone else here who have pointed out that without the documents, or at least far more of them, or far more comments from experts than are present in the article, this story isn't providing much value. It's not exactly a secret that the USG IC invests heavily in compute for these purposes. What have we really learned here?
Again, the article states very clearly and explicitly that WindsorGreen should not impact people using strong crypto.
You criticize a reference to RSA-4096 as implying RSA-2048 is weak. That reference was made in a quote by bunnie huang, a security researcher, who, like us, was using it to illustrate a broader point, with no insinuation that 2048 is weak. The quote was surrounded by higher level paragraphs from us saying, again, that contemporary crypto should be safe from WindsorGreen.
If we were advancing that narrative — that crypto is useless or will soon be rendered useless — I can see why you'd be concerned. But you have to blow past explicit, lengthy blocks of text saying the opposite of that, and ignore them, to come to that conclusion.
(I'm also not sure why we'd promote that narrative when we ourselves put a lot of effort into crypto education, here's just from Micah Lee and the video team that works with him, only a portion of what I'm talking about: https://theintercept.com/staff/micah-lee/ )
I like Bunnie Huang as much as anyone here. Your publication chose to quote him in a manner suggesting that people should be adopting RSA-4096 because of NSA supercomputers. I think it's fair to criticize you for doing that.
I'm not sure why I'm meant to care about the work you've done to educate people about cryptography, or how that's germane to the discussion. I assume The Intercept is broadly supportive of cryptography. That doesn't mean you can't write a bad story about it, or even that your incentives will tend to keep you from doing that --- those incentives, after all, are mostly about growing a readership, just like any other publication.
It's eerie to read this thread - I know little about crypto, after reading the article, I thought the NSA was clearly planning to break all HTTPS traffic. Its unimpressive to watch whoever you are (author? Publisher? Someone who repeatedly implies they have a connection to The Intercept but doesn't explicate it?) to be argumentative with, frankly, poor excuses whenever someone points out its possible for someone to misread the article exactly the way I misread it.
"supercomputers" are archaic in a day when one can rent a 40,000 core GPU system with 732GB of RAM for $14/hour, on demand, via Amazon Web Services. Available whether you need one or a hundred (4 million cores crunching on a problem with 20Gb/second throughput is still only $1400 per hour).
edit: more thorough response.
> breaking RSA isn't a really big IBM purchase order away from happening
You seem to also be completely discounting the possibility of implementation flaws or unpublished advancements against RSA that simply require a ton of hardware to pull off.
What if we don't know that a major RSA implementation is leaking enough key material that it brings the attack down from physically impossible to really really hard?
I'm not discounting it; it's simply orthogonal to the story. We already know NSA spends huge on compute. None of us are surprised that they have a custom supercomputer contracted from IBM. So we can't derive from that revelation that they've got a viable attack on RSA-2048 --- which, by the way, if they did, would be some of the most closely held information in the world, as there is nothing on the horizon (short of QC) suggesting RSA-2048 will ever fall.
If they had a break on RSA, that would be the story!
> The point of modern RSA is that we use a modulus that can't be factored by any conceivable computer, with limits derived from the physics of computation and projected far out into the future.
I'm sure you know about quantum computers. So what am I missing here? Surely they are a conceivable computer with a practical realization some decades away.
Sorry, I meant "conceivable conventional computer" but forgot the extra word (I'd used it elsewhere on the thread).
If this was some crazy undocumented advance in quantum computing, I'd have written a different comment. But it's not: it's high end conventional computing, which absent some fundamental break in the integer factorization problem (in which case that break would be the story, not the supercomputer) isn't going to make a dent in RSA.
Well said, but note that this assumes partial solutions aren't possible, that brute force is the only way in. For example, it assumes that you can't guess a single prime and then successfully test for more uniformity in the resulting (failed) test decryption. Maybe that's a great and true assumption. Maybe it ain't.
The security impact of the relationship between RSA primes is well studied. Also: if you know q and n (which is p * q, and also public)...
It's always possible that NSA has new science unknown to the rest of the world. But they've also always been huge consumers of compute hardware, so an attempt to read tea leaves here is pretty much conspiracy-theoretic. If you believe this, there's no reason to believe any (practical, non-information-theoretically-secure) crypto is safe.
Proving a negative is awfully hard - well studied doesn't quite cut it. RSA and NSA have a history that precedes the apparent invention, so it's interesting that the tech was allowed to proceed (patents can be seized and kept secret.) I've pointed to an assumption, you've assumed a belief on my part - that's something of a conspiracy theory on your part, it's nothing I've said. The history of cryptography is replete with examples of assumptions of safety that were spectacularly overturned, and that's all I'm pointing to.
The title was likely shortened by the submitter due to the 80-char length limit on HN. If you believe the submitted title is inappropriate for HN, please contact the mods via the Contact link in the footer.
The Intercept uses uppercase for all titles. This isn't emphasis, it's style. No need to carry that forward here.
Many people comment here without reading the article, based solely on the title, so discussing the fact that it's inaccurate seems to be pretty pertinent.
> The Intercept uses uppercase for all titles. This isn't emphasis, it's style. No need to carry that forward here.
I didn't say it should be. I was explaining why the text I had posted was in all caps.
> Many people comment here without reading the article, based solely on the title, so discussing the fact that it's inaccurate seems to be pretty pertinent.
Indeed. Go a step further: don't just discuss it; get it fixed. The mods are very responsive in my experience. Help make HN better. Each of us plays a role in curating HN.
This is interesting and remarkably incoherent at the same time. The article seems to conflate the existence of a dedicated ASIC based cracking machine with another more general purpose one (apparently a BlueGene relative).
Is this really about a "code-breaking computer", or just some big data collection and analysis cluster? A code-breaking machine would look like a Bitcoin mining farm - all ASICs, very little storage, not much I/O, no disks. An collection and analysis machine looks like an ordinary data center.
Is this maybe the Cyrogenic Computer Complexity Program? [1] That's an attempt to build a 10GHz machine running in liquid helium.
The very fact that the government invests substantially in brute-forcing encryption means that there are enough weak implementations to make it worthwhile.
Nothing in this article remotely qualifies as news. IBM builds computers, fast ones, to crack passwords for the US DOD. They engage with academia to apply research in building and programming them. Is that surprising? Even if it were, there's not even a source document in the article. Snoozefest.
Andrew "Bunnie" Huang: "My guess is this thing, compared to the TOP500 supercomputers at the time (and probably even today) pretty much wipes the floor with them for anything crypto-related."
We've always guessed the NSA has some incredible resources, but to get a peek like this into what they had 3 years ago is definitely newsworthy. It makes the whole supercomputing race kind of a joke if governments have massively more powerful machines hidden from public view.
Apparently the context suggests this particular machine had not been built and delivered at the time the documents were written, so it doesn't show that NSA had this exact machine at that time (though maybe they had other computers that were this fancy or fancier).
I also guess the machine will be built in some form, just that the documents probably don't reflect three-year-old computational capabilities, but might reflect something more like present-day capabilities.
They're classified...if the guy who discovered they were publicly revealed on accident had actually provided them to the Intercept, he would certainly have lost his job, and likely ended up in prison.
The Intercept article says that they gave the documents to at least three (named) experts to review in their entirety, suggested that the Intercept does possess them but decided to publish only a small excerpt.
In terms of the prior commenters assertion about source protection, that was not a factor as the source alerted various of the original parties directly that their material was in public view (as we mention in the story).
In terms of the (admittedly) small volume of original documents we published, all I feel comfortable saying at this point is that we were interested in publishing more, but there were significant legal concerns.
It's really too bad the specifics of the machine weren't shared. I'm not speaking from a national security perspective, where it should be mentioned that other nations most likely already obtained this information, but rather from an academic perspective. It seems that there are a lot of questions regarding the machine, its purpose for instance, and such questions could best be answered by public study.
It is also slightly nauseating that a US company finds it perfectly acceptable to undermine US citizen's privacy for profit. I suppose money is attractive.
The most common attack model for this is "get ahold of a hashed password list, try to reverse as many as possible, then try to see if any has re-used those passwords on other systems". Spy agencies might be doing that too. By contrast, as Bunnie says, modern algorithms have a very large safety margin so brute-force against a random key is very implausible without some significant new algorithmic insight.
So one question is, are there significant security-sensitive deployments that are still out there of obsolete stuff with too short a keylength? 1024-bit RSA, 1024-bit DH, DES, export ciphers?
If, on the other hand, it's really mostly about password hashes, where brute force has been known to be so effective, are there any other attack contexts where the ability to reverse a password hash would be useful?