NSA, Decryption and Backdoors

Edward Snowden, a former NSA employee, copied and now is releasing confidential material from internal operations of the NSA and its partners. I don't want do judge his decision to do so, but i want to discuss the information that the NSA can decrypt most of the current internet traffic.

The question that comes up is: How is the NSA able to do this? The cryptographic protocols in question are using hard and well known cryptographic assumptions, e.g., RSA, DH, ECDH etc..., or are based on official and world-wide reviewed scramble routines, e.g., AES. Does the NSA really know much more about cryptanalysis than the rest of the world, especially than its academic counterpart? And if they have secret full blown factoring and discrete logarithm algorithms, why should they pay companies for letting them get access to the user informations? Is it 250 million dollar of distraction money?



Probably not. The NSA has around 40K employees, whereof a large chunk are mathematicians or computer scientists. A lot of these are hired only for special purposes. That is, trying to find some weaknesses in the protocol implementation of xy or trying to optimize the factoring algorithm and its implementation on a special purpose 10 million hardware. They get money for this. And even if they find only a tiny optimization point, its probably worthwhile.

The academic counterpart can not behave equally. Tiny optimization points will not get them a publishable paper, nor can they spent their academic career on just trying to find an algorithm that breaks the discrete logarithm problem. The chances are too high that they will fail and get stuck. You can only behave this way if you are paid for this kind of work and your employer does not (really) care if you are successful or not.

It is believed that the NSA is having a computing power of $\approx 2^{80}$. Hence, this should be the lower bound of any cryptographic algorithm in a security chain in order to establish a secure connection. If you use for example AES-$128$ with preplaced keys for your phone encryption, then NSA must have a technique to reduce the complexity of an attack by $48$-bit before they could successfully apply their breaking-algorithm. As i know, the best algorithm for full-round AES is the Biclique attack [1] and it reduces the complexity by around $2$ bits. So the NSA has to jump $46$-bit ahead of academic research. I don't think that this is possible.

But what strikes me most is not that they pay companies for information or that they might have improved some cryptanalysis algorithms. It is that they could have brought weaknesses into some international standards that will and are probably implemented by the rest of the world. Read for example the old story of the A5/2 GSM algorithm.

Furthermore, the NSA is also able to push a certain technique into the markets if they see some potential benefits (or hidden weaknesses). See for example the blog post of Bruce Schneier, where he states:

"Certainly the fact that the NSA is pushing elliptic-curve cryptography is some indication that it can break them more easily."

Do they know more about elliptic cryptography than we do? Could we trust the elliptic curves that are published by the NIST or are they chosen in some special way? I am very concerned about this kind of questions, since even if a company does everything right and closes all doors, they are still vulnerable since they trusted and chose the wrong standard.

See also the article from the Crypto Rump-Session [2] and the article from NIST itself, where they recommend not to use its own standard [3]. 

[1] Andrey Bogdanov, Dmitry Khovratovich, Christian Rechberger: Biclique Cryptanalysis of the Full AES. In: ASIACRYPT 2011 (Lecture Notes in Computer Science. 7073). Springer, 2011, S. 344−371