Are NSA routinely cracking AES ??

[marcus_of_augustus]

I would really like to get people's opinion on this.

This passage in the much-talked about Wired article seems to be implying this but I find that a little too incredible ... or ??

"At the DOE’s unclassified center at Oak Ridge, work progressed at a furious pace, although it was a one-way street when it came to cooperation with the closemouthed people in Building 5300. Nevertheless, the unclassified team had its Cray XT4 supercomputer upgraded to a warehouse-sized XT5. Named Jaguar for its speed, it clocked in at 1.75 petaflops, officially becoming the world’s fastest computer in 2009.

Meanwhile, over in Building 5300, the NSA succeeded in building an even faster supercomputer. “They made a big breakthrough,” says another former senior intelligence official, who helped oversee the program. The NSA’s machine was likely similar to the unclassified Jaguar, but it was much faster out of the gate, modified specifically for cryptanalysis and targeted against one or more specific algorithms, like the AES. In other words, they were moving from the research and development phase to actually attacking extremely difficult encryption systems. The code-breaking effort was up and running.

The breakthrough was enormous, says the former official, and soon afterward the agency pulled the shade down tight on the project, even within the intelligence community and Congress. “Only the chairman and vice chairman and the two staff directors of each intelligence committee were told about it,” he says. The reason? “They were thinking that this computing breakthrough was going to give them the ability to crack current public encryption.”

http://www.wired.com/threatlevel/2012/03/ff_nsadatacenter/all/1

Are NSA capable of routinely (i.e hours not weeks) cracking AES ... anybody?

[bulanula]

I would really like to get people's opinion on this.

This passage in the much-talked about Wired article seems to be implying this but I find that a little too incredible ... or ??

"At the DOE’s unclassified center at Oak Ridge, work progressed at a furious pace, although it was a one-way street when it came to cooperation with the closemouthed people in Building 5300. Nevertheless, the unclassified team had its Cray XT4 supercomputer upgraded to a warehouse-sized XT5. Named Jaguar for its speed, it clocked in at 1.75 petaflops, officially becoming the world’s fastest computer in 2009.

Meanwhile, over in Building 5300, the NSA succeeded in building an even faster supercomputer. “They made a big breakthrough,” says another former senior intelligence official, who helped oversee the program. The NSA’s machine was likely similar to the unclassified Jaguar, but it was much faster out of the gate, modified specifically for cryptanalysis and targeted against one or more specific algorithms, like the AES. In other words, they were moving from the research and development phase to actually attacking extremely difficult encryption systems. The code-breaking effort was up and running.

The breakthrough was enormous, says the former official, and soon afterward the agency pulled the shade down tight on the project, even within the intelligence community and Congress. “Only the chairman and vice chairman and the two staff directors of each intelligence committee were told about it,” he says. The reason? “They were thinking that this computing breakthrough was going to give them the ability to crack current public encryption.”

http://www.wired.com/threatlevel/2012/03/ff_nsadatacenter/all/1

Are NSA capable of routinely (i.e hours not weeks) cracking AES ... anybody?

With their undisclosed budgets and figures of $2 billion I honestly would not be surprised if they could, quantum computing ( "big breakthrough" ) and all that.

[rjk]

If you’re talking about a brute-force attack on a 256-bit AES encryption algorithm then probably not but it’s possible if you have a small defined search space. The key length used determines the likelihood of a successful match. I'm sure you know with a 256 key size 2x256 permutations would yield a maximum brute-force time of 50,955,671,114,250,072,156,962,268,275,658,377,807,020,642,877,435,085 years. A specialized supercomputer that could check a billion billion (1018) AES keys per second would require about 3×1051 years to exhaust the 256-bit key space. Not likely but I suppose it's possible and luck changes the mix because you would not always need to exhaust the key space.

Farther into the article, it shows that they are targeting 128-bit and weaker versions of AES, as well as other weak algos. They are not breaking it in real time, but rather are cracking communications from 10 years or more ago, which they have collected and stored all these years until they have the tech to break in. Which it seems that they do now.

They wish to read old government communications and run analysis on them, hoping to detect patterns and such in their dealing with other nations. I have no doubt that they are targeting anyone and everyone.

[deepceleron]

"Major breakthrough" might be something significant. The NSA also has a classified budget for hiring the best mathematicians.

For example: NSA modified the DES specification to be more resistant against differential cryptanalysis (but with recommended key sizes that were possibly within their cracking abilities), two decades before these techniques were publicly known. AES is supposed to be DC resistant; however the NSA might have identified a technique that is still secret that would allow a lower barrier to analysis than full key size and current public knowledge would indicate in the rijndael AES candidate, and let it go through. There is already public cryptanalysis that cuts two bits off the brute-forcing of AES: http://research.microsoft.com/en-us/projects/cryptanalysis/aes.aspx

[The00Dustin]

I was thinking of posting about a similar article to get opinions.  The article I refer to was in Network World's Backspin column.  It is this article: http://www.networkworld.com/columnists/2012/042312-backspin.html

Here is a quote from it that made me wonder similar things:

With a $2 billion budget, 1 million square feet of data center, and a claimed storage capacity of a yottabyte, the Utah Data Center will be pushing the envelope of Big Data.

In case you're wondering what a yottabyte might be, a recent Wired article about the Utah Data Center explained, "A yottabyte is a septillion bytes — so large that no one has yet coined a term for the next higher magnitude." If a septillion doesn't help, consider that a yottabyte equals 10 followed by 24 zeros worth of bytes.

To give that figure a bit more perspective, it has been estimated by Cisco that by 2015 the Internet will generate something around 966 exabytes (something less than a zettabyte or 10 to the 21) of data annually. The Utah Data Center will be able to store 1,000 times that volume! And to analyze it and crack encrypted content they have computers that, it is claimed, are capable of exaflop (10 to the 18 floating point operations per second) performance.

He goes on to talk about mission creep and the government forcing businesses to help it spy, and while I don't consider myself a conspiracy theorist, I don't have much trouble believing that based on historical government action.  It looks like maybe he is referring to the same wired article in the OP, but I didn't drill down into it because the additional information wouldn't help me determine whether or not it would put bitcoin (or any of my encrypted data) at risk without more research than I plan to do.

[compro01]

With their undisclosed budgets and figures of $2 billion I honestly would not be surprised if they could, quantum computing ( "big breakthrough" ) and all that.

implications of a quantum computer able to run at comparable speed to modern supercomputers and run both Grover's algorithm and Shor's algorithm (lets assume they have some smart guy who figured out how to make it work in addition to the smart guys who made a real quantum computer.) :

128 bit encryption is completely broken and able to be brute forced in minutes or less.

192 bit encryption is marginally safe.  at a billion billion keys per second, it would take you about 1250 years on average.

256-bit remains impossible to break barring other flaws in the algorithm itself.  256 bit is basically as safe against a quantum attack as 128 bit is against a conventional attack.

RSA public key encryption is completely broken for all key sizes and Diffie-Hellman-Merkel key exchange is completely broken.  As a result, SSL/TLS is completely useless.

ECDSA is completely broken.

[Foxpup]

Didn't know there was an quantum attack on ECC ...
References ?

Shor's discrete logarithm quantum algorithm for elliptic curves

[arby]

Maybe they do, maybe they do not. I would not worry much about it, because the NSA, even if they crack AES256, which as I understand is easier to crack that AES128, they will not focus on the bitcoin/bitcoin and internet users just yet, they have the billion dollar fish they can catch. If you are in connection with BP, Exxon, or an oil rich country's government maybe you should worry about the NSA, if not, I would worry about FBI, or the local Police trying to 'crack' your encryption.

P.S. Usually they send an old friend or someone new to befriend you, and find out your password, rather than wasting resources cracking it.