Jon Callas <jon@pgp.com> wrote:
Imagine a computer that is the size of a grain of sand that can test keys against some encrypted data. Also imagine that it can test a key in the amount of time it takes light to cross it. Then consider a cluster of these computers, so many that if you covered the earth with them, they would cover the whole planet to the height of 1 meter. The cluster of computers would crack a 128-bit key on average in 1,000 years.
The error in this argument is the assumption that the computers aren't all partially replicating each others computations.
If you want to brute-force a key, it literally takes a planet-ful of computers. And of course, there are always 256-bit keys, if you worry about the possibility that government has a spare planet that they want to devote to key-cracking.
Suppose I give you one NAND gate, and ask you to build an encryption function that inputs 64 bits of data and 256 bits of key, and outputs 64 bits of data. Couldn't build a very complicated one, could you? Wouldn't take a very big computer to sweep the entire 256 bit key space, as long as you did no redundant computation. Now suppose I give you ten NAND gates. Now you can build a more complicated encryption function. Nonetheless, it is still greatly limited with regard to what it does with each of the the 2^256 keys being different from what it does with the others. Sweeping the key space is still practically instantaneous, as long as you don't do redundant computation. Now suppose I give you 100,000 NAND gates. Now you can build a really complicated encryption function, that passes all the tests of whether encryption functions are good. But the number of ways you can hook even 100,000 gates together is a small drop in the bucket compared to the confusion and diffusion necessary to make all 2^256 permutations on 2^64 integers truly statistically independent of one another. How fast can I sweep the key space now, modding out redundant computation? An interesting question you would do well to ponder. Many things that take a long time in the domain of data, happen quite speedily if you do them by transformations in the domain of the function representation.
Now of course, there are other ways to break the system.
They could know something we don't.
You think?
They could know some fundamental truth about mathematics (like how to factor really fast), some effective form of symmetric cryptanalysis, or something else. They could know about quantum computers, DNA computers, systems based upon non-Einsteinian physics, and so on. Yes, it's possible. But this quickly gets into true paranoid thought. There isn't a lot of difference between the *presumption* that they have such things and the presumption that they have aliens in a vault in Nevada. It isn't falsifiable. It gets irrational quickly. The evidence that we have about this suggests quite the opposite, but more on that later.
There are an unlimited number of surprising algorithms whose direct derivation lies just beyond the range of human ingenuity. This is why we have Experimental Mathematics and other techniques for grepping the fabric of reality for things we could never figure out on our own through a random walk of the solution space.
The last bit of evidence we have that suggests that they can't break the crypto is that they are apparently devoting a lot of effort to traffic analysis.
I'd bet money the NSA has been able to crack RSA since 1996. -- Eric Michael Cordian 0+ O:.T:.O:. Mathematical Munitions Division "Do What Thou Wilt Shall Be The Whole Of The Law"