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.
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&amp;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.