NSA's (and GCHQ) Decryption Capabilities: Truth and Lies
Edward Snowden has revealed new information concerning the cryptographic capabilities of the NSA and GCHQ (TheGuardian, ProRepublica, leaking documents...). The CryptoGirl was bound to look into that topic ;) Let's go straight to the point and answer simple questions.
Is cryptography unsecure?
No, I don't think so. Basically, cryptography is maths (prime numbers, finite fields, polynomials...), and maths are solid science with proofs and demonstrations. Cryptographic algorithms are only seldom broken (e.g MD5). What's quite often "broken" are implementations, because implementations are imperfect representation of maths. Vulnerabilities range from implementations bugs (buffer overflows etc) to side channel attacks (i.e attacks based on the physical properties of the implementation such as differential power analysis, timing attacks...). Don't believe me? This opinion of mine is backed by Bruce Schneier, who had access to NSA's documents: "They're doing it primarily by cheating, not by mathematics.".
Yes, but they seem to be able to defeat SSL!
Yes. Note that SSL is a security protocol, not a cryptographic algorithm.
The documents released by Snowden confirms our fears regarding SSL. As we said in our previous blog, we believe they do it by getting private keys of given domains or performing man-in-the-middle attacks. They could also be using attacks such as BEAST, CRIME or BREACH.
SSL is so widely deployed that there is much peer review of the protocol (good), but also new vulnerabilities are exposed each year at security conferences. It seems quite likely that the NSA is aware of those vulnerabilities, perhaps even with a few 0-days. _
Image courtesy of LaMenta3 via Flickr.
_ Matthew Green says Microsoft CryptoAPI and OpenSSL are probably among the SSL libraries the NSA is the most likely to break into, and I agree with him. In particular, a few years ago I remember that OpenSSL checked certificate chains only up to 9 levels. Certificates for a given entity are issued by a higher authority, and the higher authority's certificate is issued by an even higher authority. That's the chain of trust. So, if you have 10 certificates in your chain, OpenSSL was unable to check the chain and you might claim to be God and would be trusted :) This was a documented issue, I haven't checked if it has been fixed since.
By the way, Bruce Schneier recommends usage of TLS (for those who don't know, TLS is like "SSL 3.1", it's a newer version of SSL). It's certainly better than SSL in terms of security, but I wouldn't bet on it as there are (nearly) as many vulnerabilities.
The NSA has supercomputers and excellent cryptographers. They can break the RSA algorithm
I agree with the first sentence and disagree with the second ;) Sure, they have powerful computers and cryptographers, but that's not enough to break the RSA algorithm with 2048-bit keys (for instance, this is used in GPG). You need huge computational power to brute force RSA 2048. Currently, the RSA Factoring Challenge record is set to RSA 768, and that's already tremendous work.
I don't think the NSA can do much better, and I don't think they have better cryptographers than those of the entire world. People like Shamir, Rivest, Lenstra, Preneel, Coron, Boneh etc are just exceptional, and I would not think the NSA can influence such a diverse panel of scientists.
In the specific case of RSA, however, note that improper usage or implementations may be insecure. For instance, signing with RSA 1024 with PKCS#1 and a low exponent is not safe. So, if you use your crypto library (OpenSSL, BouncyCastle etc) with those settings, too bad. Note that it's not that RSA 1024 is insecure, but that particular combination. All cryptographic algorithms are designed to work in a specific well-designed context. If you use them outside that context, their security may fall apart. As developers say, RTFM ;)
The slides say they can do it!
No. The information I read in the Guardian's article in no way states the NSA has the ability to break RSA, nor AES etc. They say that "cryptanalytic capabilities are now coming on line" or that they have "groundbreaking capabilities", which is far too vague.
True, I haven't had access to the full set of slides, so I might be missing something important. However, still, I would not trust those slides fully. Why? Because they don't sound like technical slides from a cryptographer. Would a cryptographer write he has "groundbreaking capabilities"? No. That's not the way cryptographers talk. They'd rather say "Breakable in o(2^n)" or something like that ;) For me, the slides emanate from some high level manager. I guess all of us have already seen slides of products which actually do not really correspond to reality, huh?
The NSA influences standards and puts backdoors in applications
Yes, I believe this is possible. Matthew Green summarized it very well: "Cryptographers have always had complicated feelings about NIST, and that's mostly because NIST has a complicated relationship with the NSA."
My guess would be that the same applies to (some) RFCs and IEEE standards such as P1363. Elliptic curve choices are indeed somewhat obscure and could typically have been influenced by the NSA. This is also in line with Bruce Schneier's recommendation "Prefer conventional discrete-log-based systems over elliptic-curve systems; the latter have constants that the NSA influences when they can."
As for putting backdoors into programs, to some extent, I can personally guarantee this is true - and not only in the US! Some 15 years ago (waow...), I was a junior developer working on quite well-known encryption product. To comply with the French law and be able to commercialize the product, we had absolutely no other choice than to embed a backdoor for the French government. That backdoor enabled them to decrypt the session key and hence any document encrypted with the tool. I remember the product featured a label like "Approved by SCSSI" (French's former SSI entity) which, in practice, meant it held the backdoor. In France, laws around cryptography are now less restrictive, but this is just to say I would not be surprised the US asks for key escrows.
What tools can I use?
Bruce Schneier provides several recommendations. See also this document. It's also worth to have a look at Prism-break. I complement them with a table below of what I think - personal opinion - is secure or not. Unfortunately, "green" does not mean it is guaranteed to be secure. For instance, the implementation may be flawed. But it's better than orange...
-- the Crypto Girl