5 ms·

"According to another top official also involved with the program, the NSA made an enormous breakthrough several years ago in its ability to cryptanalyze, or br

"According to another top official also involved with the program, the NSA made an enormous breakthrough several years ago in its ability to cryptanalyze, or break, unfathomably complex encryption systems employed by not only governments around the world but also many average computer users in the US. The upshot, according to this official: “Everybody’s a target; everybody with communication is a target.” What do people think this refers to? Somebody managed to compile sslsniff, or something more significant? Have they found a key weakness in RSA or similar? Are they just bruteforcing all those crappy ssl certs that are floating around? Does it refer to realtime decoding of GSM? Don't we all believe they can do that anyway? I guess we can only speculate. Just because I'm paranoid, doesn't mean they're not out to get me...

Spearchucker 15y ago
It refers to a number of technologies including DES, SSL and GSM. I suspect also <128bit AES. The NSA stores everything anyway, because if it can't be decrypted today, it can probably be decrypted tomorrow. On the positive side, even if the NSA could break AES 256 (or even DES) it is still a relevant and useful algorithm. It's relevant because if I, say, issue an order to storm Wimbledon Common, that order is tactically valid and useful and hence secret for maybe a day or two, after which Wimbledon Common has been taken, and the order no longer has value. Assuming the symmetric keys are solid, even weaker algorithms will do. On that basis, if AES 256 is only relevant for another 10 years then that's ok to encrypt my documents with, because when something better comes along those documents are probably no longer relevant. Of course they may still be relevant as evidence if someone wants to come after you. In closing, a lot of the Wired article is drawn from the book The Shadow Factory, which ends with the start of the construction of the Utah facility. It's interesting reading that also goes into the political side of it.
jcfrei 15y ago
I doubt they have the computing power or the tools to decypher more complex algorithms, the sheer amount of encrypted data seems to big. occams razor would dictate they are just storing vast amounts of data, maybe mapping communications (eg. mails from afghanistan to the us, etc) and then bruteforcing some of the really interesting stuff. it's not like a us government agency can suddenly leapfrog decades of research in encryption.
drostie 15y ago
From the article's excitement, I would almost guess that they have a working attack against AES, but that sounds extremely unlikely with the amount of scrutiny AES has received. Still, AES is known to have some very clean algebraic properties, and people have wondered since the AES competition whether those would translate into real attacks -- perhaps the NSA has found a way. At least, the discussions about saving data to decrypt later sounds very suggestive of a break on either Triple DES or AES. But I should say that you wouldn't have to break AES to break HTTPS and read most of the encrypted conversations on the web. In late 2008 a group of academics broke HTTPS by lifting a digital signature from a legitimately-signed document which gave few HTTPS permissions, onto a document which gave them arbitrary permissions. They did this by breaking the MD5 algorithm, and it caused the community to finally excise the last of the MD5 certificates for SHA1 certificates. But the NSA could do the same with the SHA1 algorithm's known weakness, and could then listen in on any man-in-the-middle attack they wanted. How complex is this? Since 2008, we've had an attack which might work in 2^52 operations or so. For the NSA that's approximately nothing. The Cray computer (one which we know the US government has) does roughly 2 petaflops now, or 2^51 operations per second or 2^67 per day. So it's reasonable to believe that, if they move from eavesdropping to active communication, they can already break HTTPS. (There is a risk in this method, however: if someone catches you doing this "in the wild", then they might notice and raise a big stink about it.) Their exaflop goal would then be 2^85/year, which would be enough to run publicly-known attacks against Triple DES and perhaps to factor known 1024-bit RSA moduli -- for example the Equifax Root CA is 1024 bit RSA. If you could compromise one of those just once, you could issue certificates of your own -- and it would be extremely difficult if not impossible to detect the intrusion. So with exaflop computing, they could seriously just spend a couple weeks breaking an RSA-1024 modulus and launch undetectable man-in-the-middle attacks against everyone. It's also likely that they've got more efficient attacks than the public researchers have, since they have access not only to the public research but also to a set of well-paid brilliant minds who work on these problems every day, and have been for quite some time. (It would be nice to have some transparency and know just how far they have gotten, but of course they won't even tell us that. I guess that's a bit of a weird question anyway, like asking, "in the odd event that you might want to stab the Internet to death, we would like to know: how large is the largest knife you own?")
- 15y ago
harshreality 15y ago
If they had some completely unknown attack, I doubt they would leak it during an interview about their new facility... which is going to draw a lot of attention from privacy advocates and tin foil hatters. Possibilities include: 1. Disinformation. Maybe it's about hashes, either SHA-1 (unlikely since there are known, feasible, collision attacks) or an unknown vulnerability in SHA-2 variants, and the NSA is trying to make people look elsewhere by talking about how they're going to decrypt mountains of old data. 2. GSM. I don't think the entities the NSA cares about consider GSM secure, so I doubt it. 3. RSA, DSA, plain DH. It's no secret that the NSA has been strongly encouraging suite B (EC-based) variants of older ciphersuites. But why would they encourage people to be skeptical about security of existing non-EC public key crypto just a few years after they're able to start cracking it? 4. AES. Nightmare scenario (no replacement in the pipeline). Perhaps someone else has discovered whatever the vulnerability is, and they're too visible and cannot be coerced into shutting up, but were induced to shut up temporarily; in that case this could be part of a disclosure strategy by the NSA, possibly about a factoring/DLP advance enabling cracking of plain RSA and/or DH. The article doesn't say anything was cracked, and the "breakthrough" is mentioned when talking about supercomputing. It would take a mind-boggling supercomputing breakthrough to put 128 bit block ciphers at risk. Could this be Bamford trying to sell more books by creating drama?
- Estragon 15y ago
  > the NSA has been strongly encouraging suite B (EC-based) > variants of older ciphersuites. There is so much structure in the arithmetic of elliptic curves that I would expect ECC methods to be cracked before RSA/DSA. I assumed they were talking about ECC when they claimed a new attack.
  - harshreality 15y ago
    Ignoring mathematical properties, the timing wouldn't make sense. Barely anyone used ECDSA/ECDH until very recently, and still it's rare. It wouldn't make sense that the NSA has been pushing suite B for gov agencies since this "breakthrough".

Spearchucker 15y ago

It refers to a number of technologies including DES, SSL and GSM. I suspect also <128bit AES. The NSA stores everything anyway, because if it can't be decrypted today, it can probably be decrypted tomorrow. On the positive side, even if the NSA could break AES 256 (or even DES) it is still a relevant and useful algorithm. It's relevant because if I, say, issue an order to storm Wimbledon Common, that order is tactically valid and useful and hence secret for maybe a day or two, after which Wimbledon Common has been taken, and the order no longer has value. Assuming the symmetric keys are solid, even weaker algorithms will do. On that basis, if AES 256 is only relevant for another 10 years then that's ok to encrypt my documents with, because when something better comes along those documents are probably no longer relevant. Of course they may still be relevant as evidence if someone wants to come after you. In closing, a lot of the Wired article is drawn from the book The Shadow Factory, which ends with the start of the construction of the Utah facility. It's interesting reading that also goes into the political side of it.

jcfrei 15y ago

I doubt they have the computing power or the tools to decypher more complex algorithms, the sheer amount of encrypted data seems to big. occams razor would dictate they are just storing vast amounts of data, maybe mapping communications (eg. mails from afghanistan to the us, etc) and then bruteforcing some of the really interesting stuff. it's not like a us government agency can suddenly leapfrog decades of research in encryption.

drostie 15y ago

From the article's excitement, I would almost guess that they have a working attack against AES, but that sounds extremely unlikely with the amount of scrutiny AES has received. Still, AES is known to have some very clean algebraic properties, and people have wondered since the AES competition whether those would translate into real attacks -- perhaps the NSA has found a way. At least, the discussions about saving data to decrypt later sounds very suggestive of a break on either Triple DES or AES. But I should say that you wouldn't have to break AES to break HTTPS and read most of the encrypted conversations on the web. In late 2008 a group of academics broke HTTPS by lifting a digital signature from a legitimately-signed document which gave few HTTPS permissions, onto a document which gave them arbitrary permissions. They did this by breaking the MD5 algorithm, and it caused the community to finally excise the last of the MD5 certificates for SHA1 certificates. But the NSA could do the same with the SHA1 algorithm's known weakness, and could then listen in on any man-in-the-middle attack they wanted. How complex is this? Since 2008, we've had an attack which might work in 2^52 operations or so. For the NSA that's approximately nothing. The Cray computer (one which we know the US government has) does roughly 2 petaflops now, or 2^51 operations per second or 2^67 per day. So it's reasonable to believe that, if they move from eavesdropping to active communication, they can already break HTTPS. (There is a risk in this method, however: if someone catches you doing this "in the wild", then they might notice and raise a big stink about it.) Their exaflop goal would then be 2^85/year, which would be enough to run publicly-known attacks against Triple DES and perhaps to factor known 1024-bit RSA moduli -- for example the Equifax Root CA is 1024 bit RSA. If you could compromise one of those just once, you could issue certificates of your own -- and it would be extremely difficult if not impossible to detect the intrusion. So with exaflop computing, they could seriously just spend a couple weeks breaking an RSA-1024 modulus and launch undetectable man-in-the-middle attacks against everyone. It's also likely that they've got more efficient attacks than the public researchers have, since they have access not only to the public research but also to a set of well-paid brilliant minds who work on these problems every day, and have been for quite some time. (It would be nice to have some transparency and know just how far they have gotten, but of course they won't even tell us that. I guess that's a bit of a weird question anyway, like asking, "in the odd event that you might want to stab the Internet to death, we would like to know: how large is the largest knife you own?")

15y ago

harshreality 15y ago

If they had some completely unknown attack, I doubt they would leak it during an interview about their new facility... which is going to draw a lot of attention from privacy advocates and tin foil hatters. Possibilities include: 1. Disinformation. Maybe it's about hashes, either SHA-1 (unlikely since there are known, feasible, collision attacks) or an unknown vulnerability in SHA-2 variants, and the NSA is trying to make people look elsewhere by talking about how they're going to decrypt mountains of old data. 2. GSM. I don't think the entities the NSA cares about consider GSM secure, so I doubt it. 3. RSA, DSA, plain DH. It's no secret that the NSA has been strongly encouraging suite B (EC-based) variants of older ciphersuites. But why would they encourage people to be skeptical about security of existing non-EC public key crypto just a few years after they're able to start cracking it? 4. AES. Nightmare scenario (no replacement in the pipeline). Perhaps someone else has discovered whatever the vulnerability is, and they're too visible and cannot be coerced into shutting up, but were induced to shut up temporarily; in that case this could be part of a disclosure strategy by the NSA, possibly about a factoring/DLP advance enabling cracking of plain RSA and/or DH. The article doesn't say anything was cracked, and the "breakthrough" is mentioned when talking about supercomputing. It would take a mind-boggling supercomputing breakthrough to put 128 bit block ciphers at risk. Could this be Bamford trying to sell more books by creating drama?

Estragon 15y ago
> the NSA has been strongly encouraging suite B (EC-based) > variants of older ciphersuites. There is so much structure in the arithmetic of elliptic curves that I would expect ECC methods to be cracked before RSA/DSA. I assumed they were talking about ECC when they claimed a new attack.
- harshreality 15y ago
  Ignoring mathematical properties, the timing wouldn't make sense. Barely anyone used ECDSA/ECDH until very recently, and still it's rare. It wouldn't make sense that the NSA has been pushing suite B for gov agencies since this "breakthrough".