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

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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 cryptosystem 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 cryptosystem 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 there is 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.

Answer 6

The way to reason about the cryptographic capabilities of any entity-- a national-level agency, a large corporation, other non-state actors-- is to avoid conjecture and search for evidence, of which there is much:

1. leaked documents about cryptographic primitives, methods, etc., especially information that had been closely held
2. testimony from former insiders
3. inadvertent disclosures
4. what they generally do to protect their own information from each other
5. how they use cryptography for themselves: key schedules, hashes, ciphers, salts, etc.
6. what they avoid
7. facts about subverting ciphers and pseudo-random number generators, etc.; facts about backdoors, other vulnerabilities by design, and the push for standardization involving dubious ciphers, hashes, etc.

Everything else should be bracketed out, and we must not victim to confirmation bias.

Answer 7

This question has wonderful answers, but I think I can add another perspective. In game theory, it can be said that the intelligence community (IC) strictly dominates public cryptography because they have the sum of knowledge developed in-house and public knowledge, whereas the public only has public knowledge, but that says nothing about the gap between public knowledge and the sum of public and IC-owned knowledge. From this we can conclude that the IC will always have an upper hand, but it says nothing about how much of an upper hand they have, and whether or not it is significant.

Given that cryptographic algorithms are intentionally designed such that there is a huge security margin between the theoretical and the practical, the IC would need its advantage to significantly exceed this security margin, which is highly unlikely, despite them having a greater amount of cryptographic knowledge. We would need the hidden variable (how much in-house knowledge they have) to know what kind of threat they pose to cryptography. Thomas Pornin's answer provides a solid argument focusing on the percentage of mathematical expertise the NSA can employ.