# How can we reason about the cryptographic capabilities of code-breaking agencies like the NSA or GCHQ?

I have read in Applied Cryptography that the NSA is the largest hardware buyer and the largest mathematician employer in the world.

• How can we reason about the symmetric ciphers cryptanalysis capabilities of code-breaking agencies like the NSA or GCHQ given that they have performed first class unpublished cryptographic research for the last ~40 years?

• What sort of computational lower bounds can we establish on an attack against these ciphers given that these agencies may have unpublished and unknown cryptanalysis techniques of equivalent utility as differential cryptanalysis (we only know about differential cryptanalysis because someone outside the NSA/IBM rediscovered it)?

For example, could we have developed a good lower bound on the ease of finding collisions in md5 without knowledge of differential cryptanalysis?

This question is restricted to symmetric ciphers.

-
I think it's an interesting question and one that every user of cryptography outside of the US Government itself must be asking. While it's true that an organization such as the NSA gives up very little information about its capabilities (and the question could be more general and apply to all such organizations) the amount of information is non-zero. Even in the absence of information, the question degenerates to another interesting and important question: why should we have confidence that algorithm X is secure in principle? –  Marsh Ray Sep 1 '11 at 18:35
Applied Crypto is getting pretty long in the tooth. I'd be interested in seeing the community's consensus on the current strength of the NSA in this area. It's not objective, but community consensus is valuable in itself; perception is reality and all. :-) –  Steve Dispensa Sep 1 '11 at 19:03
Yes, this is a good question. Everyone should have this question. The fact that nobody has a good answer is an important fact and it is good to publish the question on this site. A lot of the most important questions around don't really have solid answers. Uncertainty and ignorance are what we have to face up to and decide how to manage. –  Zooko Sep 1 '11 at 19:56
@gokoon - are my edits in line with what you wished to ask with this question? –  Ethan Heilman Sep 1 '11 at 20:11
Don't focus too much on specific organizations, such as the American National Security Agency (NSA). Maybe you think NSA are The Good Guys and will not do anything bad (even if they have such an ability) or you at least think they are on your side and will not do anything bad to you. But do we have any reason to believe that the Chinese or Russian classified cryptography research are less advanced than the American or British? Also some users (e.g. Europeans) may not feel okay about the possibility of NSA having such power over their communications. –  Zooko Sep 6 '11 at 15:42

Applied Cryptography is book which is becoming, say, not-so-recent. NSA has quite a lot of budget, but not an infinite amount, and there are other organization, in particular big private corporation, which also have impressive means. Google or Apple, for instance, are companies with R&D activity in the area of cryptography, and who are able to potentially throw a billion dollars at a given problem (and they could probably do so with more administrative ease and flexibility than a federal agency).

Also, there has been quite some change in the area of public research on cryptography. In the early 1980s, there was a couple of conferences dedicated to cryptography; in 2011, there are more than one hundred ! The field has simply expanded, inflated, so much that no single organization, even the NSA or Microsoft or Apple, can claim employing a non-negligible proportion of the available brain resources. It is a recent change: from my own personal experience, inflation really began in earnest around 1995.

That's one thing that can be said about NSA abilities. They do not tell who they employ and what they work on; but we can estimate the probabilities of NSA having discovered advanced cryptanalytic techniques which have evaded the grasp of public academics. As Leibniz put it, discoveries are a product of ideas which are "floating around", and who will actually make the discovery is a random choice. In other words, if NSA employs 1% of the top cryptographers, then they will get 1% of the advances. Even if there is such as a thing as scientific capital (scientists work much more efficiently when they are in labs with many other scientists and a strong local tradition of working on the same subjects), it is still quite improbable that NSA is far ahead of everybody else.

Another point is about incentives. NSA is a budget sink-hole, but it has goals: namely, to protect the USA against their enemies (the rest of the World). When the NSA says that an algorithm is good (say, the AES), other US organization (both public and private) begin to use it. It is sure that NSA would like to be able to break encryption systems which are in widespread use; but, and (in my view) this is for them a much more important goal for NSA, they want the encryption that US organizations use to be unbreakable by their enemies. As such, it would make sense for NSA to promote an algorithm that they can break only if they have good reason to believe that only them can break it. NSA, like all secret services, knows what secret is: they keep their secrets, but they also assume that they do not know all about the secrets of their competitors. Correspondingly, there again, I find it implausible that NSA would know how to break AES, since they keep on brandishing it as "the solution" and there is not the slightest hint of a plan to define another symmetric encryption standard, if only as a backup.

So this is how I reason about the unknown capacities of secretive organization: I look at their resources, and I match their observable actions against their goals. Which leads to the following conclusion: if NSA can break AES, then either they have access to some non-Earth-based technology and science (a popular theme in movies, e.g. Men In Black), or they are not really trying to protect the organizations they are supposed to protect. Or both.

On the purely scientific plane, we have no proof that symmetric primitives really exist (in particular hash functions; but we do not know either if it is possible, in a Turing-said-it way, to have a symmetric cipher with an in-memory representation shorter than $\log n!$ bits: the amount of bits needed to represent a randomly selected permutation over $n$ bits). Right now we have candidates: defined block ciphers which we do not know how to break. And not block ciphers which we know cannot be broken. Therefore, there are no real "lower bounds" which would work against unknown cryptanalytic advances.

-
Your comment seems to ignore ECHELON, where the US co-operated with UK, Australia, New Zealand, and Canada, to monitor telephone (and other) communications. ECHELON was implicated in a number of government level industrial espionage events. The US happily joined ECHELON, despite the risk to their own country's industrial privacy. –  DanBeale Sep 2 '11 at 18:57
Strong encryption is in everyone's interest, including the NSA. Strong encryption == secure commerce. If the government needs access to something, it has many vectors to get the key, including jailing your for not turning over the key. –  duffbeer703 Sep 5 '11 at 20:00
They can always resort to the "Jack Bauer Side-Channel Attack", which involves them drilling holes in your kneecaps until you reveal the key. Billion dollar supercomputer or one agent with a $50 hammer drill... hey, I guess you can put a price on human rights! – Polynomial Nov 23 '11 at 14:12 There's also the possibility the attack is very difficult , to such an extent it is only available to nation states, and nation states won't usually "show their cards" to do stuff like industrial espionage. – hulkingtickets Jul 10 '13 at 19:27 Most vulnerabilities in block ciphers are related to key security. Successful attacks have not been practical against anything except smaller keysizes than 256 bits or fewer rounds of encryption. Since there are no variables to be selected for AES except the S-box and the P-box, the Holy Grail is key management. Lateral attacks against AES rely on bad management or mistakes in implementation (weak PRNGS, timing attacks, bit injection, selective plaintexts, etc.). Given this, one would assume an attacker would not spend resources on breaking the harder problem (AES), but rather attacking the easier problem (lateral attacks). Reading the slides for PRISM the cost of the program is way too low to include any sort of computationally intensive pursuits. It's not a far leap to infer PRISM being a key sharing effort. Several accounts seem to indicate the NSA are actively subverting security on the standards level or in collusion with software developers. If either proposition is true, any serious cryptographer needs to use systems where every component is known and excludes closed source operating systems and software black boxes. These are all concerns that would weight more heavily on my mind than the feasibility of the NSA having anything less than a brute-force vector against AES. Luminaries of the field concur, even in light of the Snowden expositions. Bruce Schneier has access to the Snowden documents and says that the math is sound but the software is buggy and that is how the NSA decrypts the forked datastreams. - There's your 10 rep – rath Jul 7 '13 at 16:19 Subverting security on the standards level implies that using open known protocols and components may be insecure – Richie Frame Sep 7 '13 at 9:40 What sort of computational lower bounds can we establish on an attack against these ciphers [...] At the moment we cannot prove such a result, theoretically proving strong lowerbounds on the amount of resources required to break candidate cryptographic primitives would imply separating$\mathsf{P}$from$\mathsf{NP}\$ (a million dollar problem), and it is consistent with what we know today that these two are equal, and we maybe living in what is one of the worlds called Algorithmica, Heuristica, or Pessiland (among Impagliazzo's five worlds).

For more on Impagliazzo's worlds, see his paper or check this workshop at CCI.

-

This week's revelations put this question (and its answers) into an entirely new light.

This Schneier editorial is pretty good:

http://www.theguardian.com/world/2013/sep/05/nsa-how-to-remain-secure-surveillance

The NYT has a graphic summarizing the revealed NSA capabilities thus far:

http://www.nytimes.com/interactive/2013/09/05/us/unlocking-private-communications.html?ref=us&_r=0

VPNs, SSH, SSL, "Encrypted Chat" (read the description; sounds like OTR)... Quite a grab bag. Protocol flaws? Implementation flaws? Cryptographic breaks? All of the these? Who knows.

My pet speculation, which actually covers the entire graphic, is that they know something interesting about discrete log over elliptic curves. Or at least the curves that NIST has convinced everybody to use.

I would go with Schneier's advice: Stick to traditional Diffie-Hellman and avoid elliptic curves, on the assumption they have found some structure ("smoothness"?) that is not generally known, at least for some specific curve parameters.

On the symmetric side, I would assume they can break most block ciphers, but especially AES, with fewer plaintext/ciphertext pairs than is generally known. (This is even more speculative, I admit.) So I would stop sending IVs in the clear. I would negotiate two keys for each session: One to protect the IVs and another to protect the data stream.

But I would worry about the key exchange first, since the leaks so far sound like that is the weak point.

-
People who are concerned about NIST curves should use Shamus Standard Curves instead, or generate their own. If there is an IV concern, negotiating 2 keys is not the answer, rather use a different mode of operation or encrypt the IV with the primary key using a random prepad. –  Richie Frame Sep 7 '13 at 9:48
Given that NSA enumerates the different systems, VPN, SSH m.m. one could speculate that what they have found is particular to those systems. After all, if they had broken e.g. RSA, the insecurity of systems based on this would follow. Also, many of these systems can use different underlying ciphers, so it wouldn't make sense to just write "VPN", you would have to write "VPN with RSA" if RSA was what you had broken. –  Morty Sep 7 '13 at 10:30
In CBC mode (which is still quite common), the IV only "protects" your first plaintext block. Transmitting it encrypted doesn't help much. –  Paŭlo Ebermann Sep 7 '13 at 15:35
@PaŭloEbermann: Obviously, "avoid CBC mode" is implied by my assumption. I am talking about CTR, GCM, OCB, etc. –  Nemo Sep 7 '13 at 16:39
@Morty: That graphic is the NYT's, not the NSA's. The actual documents released so far, though redacted, strongly suggest a practical cryptanalytic attack against TLS if nothing else. That means one or more of: the protocol, RC4, 3DES, AES, RSA, DH, or ECDH. I would put my money on ECDH (with NIST curves). Integers and finite fields have been exhaustively and publicly studied for centuries; elliptic curves merely for decades, with most of the attention from cryptographers. Plus NSA has been pushing ECC pretty hard. –  Nemo Sep 7 '13 at 16:52

Proving lower-bounds on attacks on ciphers (be it symmetric or asymmetric) is extremely difficult. As is well known, and as others mentioned, the question is entangled with the question of P != NP. But it is in fact even more difficult than that! Because what the P != NP question talks about is the worst-case complexity, and that's not what you're really interested in. So even if you managed to show a given system was NP-hard to break (this is not known to be the case for e.g. RSA, ECC, etc. and indeed not thought to be the case by most), and that P != NP, you would only know that it would take exponential time to break it in the worst case (i.e. for some keys), but it could be that almost all cases can be broken fast! So you need a stronger result, for instance one about average complexity, but even that may not be strong enough to ensure the system is reasonably secure. What you ideally want is of course a lower-bound on best-case complexity, but that's very difficult to formalize and reason about, since for any crypto system there will always be "easy" cases for "some" algorithms. For instance, you could imagine an algorithm has a built-in lookup table of 10000 hardcoded keys it would try first, so it could quickly crack those, so those would be the best case for that algorithm. And since a lower-bound result must apply to all algorithms, it follows that the only best-case lower-bound that can be proven of any crypto system is O(1) (or O(n) allowing for the program to actually write down the key)!

The difficulty in formalizing complexity is also seen in symmetric ciphers. Here the key size is usually fixed, which means that the usual frameworks to reason about complexity do not apply, since in those you are looking at how the complexity grows as the problem size goes to infinity. If there's only a finite amount of instances (which is the case for a fixed key size symmetric system), then for any given 'cracking' algorithm theres a fixed value M which is the max number of operations this algorithm requires, even for the worst case. Hence, the time complexity of this algorithm becomes O(1) (with something on the order of M as the constant factor).

Maybe in the future some other more suitable complexity frameworks will come about that can somehow eliminate the algorithms that don't really solve the problem but cheat using i.e. lookup tables, maybe by including program size in the analysis and allowing a small number of cases to be 'easy' for an algorithm, in proportion to the size of the algorithm etc. But it seems to be much more difficult and very different from the way it is done now.

-
Your answer is a nice elaboration about the applicability of complexity theory to cryptography, but it doesn't really answer the question. –  Paŭlo Ebermann Sep 7 '13 at 15:12