[dave at farber.net: [IP] on crypto systems from CTO PGP]
Eric Cordian
emc at artifact.psychedelic.net
Mon Jul 10 13:31:44 PDT 2006
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"
More information about the Testlist
mailing list