# 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 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.

-