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

  • 2
    not sure why the downvotes – timpone Jun 11 '13 at 20:39
  • It seems a bit speculative and hard to answer definitively. I didn't downvote it because I'm curious. – Matt Jun 16 '13 at 21:12

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.

  • 1
    could you please add some links/citations to "know" (quantum computers, efficient breaking, etc.) – n611x007 Jun 16 '13 at 10:21
  • @naxa - updated answer with relevant links. – AJ Henderson Jun 16 '13 at 18:56
  • 4
    The number of qubits is the smallest issue with DWave's computer. It is not able to run general purpose quantum algorithms, in particular it can't run Shor's algo. From what I heard it's not even entirely clear if it's actually a quantum computer at all. – CodesInChaos Jun 16 '13 at 19:07
  • 3
    Agree with @CodesInChaos. DWave can only do quantum annealing algorithms (not Shor or Grover) and only for one very specific type of problem (the DWave Problem) and its qubits are very noisy with a high-error rate (ok for Monte Carlo simulations). The evidence seems to be that it does have quantum effects, but there's no suggestion whatsoever that its in any faster than optimized classical annealing algorithms. Quantum computing is very interesting work (Umesh Varizani has a good MOOC at edx.org on quantum computing). – dr jimbob Jun 16 '13 at 19:18
  • 1
    thank you very much for the links! off-note (meta): afaik, links are "discouraged" only when no other information is given in an answer/quetsion, but when the information is provided on-site, as citation sources they are encouraged. or at least this is how I thought and what makes sense to me. either way, thank you very much! – n611x007 Jun 16 '13 at 19:31

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

  • 1
    That's what I thought; why bother with a massive (and expensive as hell!) wiretap when you have 95% of the info you want available under PATRIOT act/NSL style access? – jackweirdy Jun 10 '13 at 14:45

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.



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.


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 Diffe-Hellmann, 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 algorrithms to do that on your laptop) but another thing to check they're prime. Secondly, sender & reciever need to agree. ) https://freedom-to-tinker.com/2015/10/14/how-is-nsa-breaking-so-much-crypto/

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.