How likely/possible is it that the NSA have broken common encryption techniques such as SSL/TLS?

Question

Jumping on the NSA/Prism questions bandwagon - There's been a lot more attention drawn to facilities such as Room 641A which indicate that the NSA has been, amongst other things, applying mass intercepts to communications through large US ISPs.

One thing that strikes me as odd in these techniques is that although they could collect a large amount of unencrypted data, large sites such as Google, Facebook, Twitter and many others typically redirect to HTTPS sites by default. This begs the question - how useful can the unencrypted data be, and do intelligence agencies have a way to decrypt the rest of it?

I know as little about this program as the next guy, but a lot of the descriptions of this program indicate that various intelligence agencies use demands such as National Security Letters to request information, or make demands such as that on Verizon to have metadata sent back on a recurring basis. If that's the case, what purpose could monitoring/recording internet traffic serve?

It's my understanding that, without having broken SSL/TLS the only way to decrypt encrypted traffic would be through having access to either a root certificate, forging a certificate for the domain you want to monitor and running a MITM attack, or through having access to the private key of the domain you want to monitor.

On the other hand, the NSA are much further ahead in crypto research than any public body, so there could be a possibility they've found a weakness? (Or simply have the compute power to break it through brute force)

Edit 2013-09-06: The Guardian has today published a story that something alarmingly similar to my question is taking place. Article here

Answer 1

There isn't really a reliable way to know for sure. What we do know from public knowledge is that algorithms exist that allow for fairly efficient breaking of relative prime based algorithms. We also know that there are now functioning quantum computers though none with sufficient quality or processing power to run the algorithms.

What we can't know is if more powerful quantum computers exist that could crack them. Either way, even if such computers do exist, it would be expensive and they would only be able to crack a limited number of cases, so your chances of having your information picked up if protected are most likely minor.

It's also worth noting this is only applicable if you are using your own keys. If you are talking with a US based company, they could simply go to that company to get the information, no cracking of the encryption keys would be necessary.

If you are using your own key and not doing anything nefarious, it is most likely that the NSA wouldn't use the resources necessary to crack your encryption due to its expense. This of course rules out any very well hidden back doors that "might" exist, but seeing as no cryptographers have publicized such a problem, it is unlikely (though I suppose not impossible) that such a hole exists.

Update: While links are generally discouraged, since someone asked for them specifically. The DWave Two is a commercially available (though unable to run Shor's algorithm and may not be truly quantum), functioning quantum computer, though not at sufficient qbits or noise levels to be an issue yet. (But who knows what might be not publicly available based on the state of the art.) Shor's Algorithm is a well known quantum algorithm for factoring large primes. This greatly decreases the effectiveness of any relative prime derived asymmetric cryptography algorithm (which most common ones are based on.) Also Grover's Algorithm should greatly reduce the complexity of cracking symmetric cryptographic algorithms, though a simple increase in bit length will compensate.

Answer 2

If it is true that the government has access to the servers that are the target of the communication (e.g. Google/Facebook) there is no need to tamper with SSL/TLS because at the servers the traffic is unencrypted.

Answer 3

I think this paper is related with the subject and it is an interesting paper :) ...

N.J. AlFardan and K.G. Paterson, Plaintext-Recovery Attacks Against Datagram TLS. In Network and Distributed System Security Symposium (NDSS 2012). Distinguished Paper Award.

http://www.isg.rhul.ac.uk/~kp/dtls.pdf

Answer 4

One technique that has always been suspected is to deliberately weaken otherwise strong encryption by various means. No smoking guns have been disclosed as far as I know, but conspiracy theorists can always speculate that any flaw, once discovered, was put there deliberately.

The famous example was that the NSA influenced IBM to alter the S-Boxes for DES. It was suspected that this was for their own, not our, benefit. I think this has been completely debunked now - that the change was actually to make the code stronger; but the elephant in the room is that DES used only 56 bit keys.

Another, recent example, was that a survey discovered that an alarmingly small number of secret primes were actually in use RSA public keys. Apparently the means of selecting random primes in several popular RSA implementations wasn't random enough.

Answer 5

Apparently, the NSA have invested a large amount of resources into brute-forcing the primes. This would be thankless work were it not for the particular (lazy) implementation of Diffie-Hellman, which regurgitates from a small selection of 1024-bit primes.

Spending a few 100m, an adversary can make a machine that cracks 1 such prime a year. So what's the payoff? Breaking a single, common 1024-bit prime would allow NSA to passively decrypt connections to two-thirds of VPNs and a quarter of all SSH servers globally. Breaking a second 1024-bit prime would allow passive eavesdropping on connections to nearly 20% of the top million HTTPS websites. In other words, a one-time investment in massive computation would make it possible to eavesdrop on trillions of encrypted connections.

(Why the weak implementation? Finding a large strong prime, of the right sort is difficult. it's not hard to find suitable candidates (there are plenty of algorithms to do that on your laptop) but another thing to check they're prime. Secondly, sender & receiver need to agree. ) https://freedom-to-tinker.com/2015/10/14/how-is-nsa-breaking-so-much-crypto/