[dave at farber.net: [IP] on crypto systems from CTO PGP]

[Eric Cordian]

Jon Callas <jon at 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"