Begin forwarded message:
From: hal@finney.org ("Hal Finney") Date: August 11, 2009 2:47:27 PM GMT-04:00 To: leichter@lrw.com Cc: cryptography@metzdowd.com Subject: Ultimate limits to computation
[Note subject line change] Jerry Leichter writes:
Since people do keep bringing up Moore's Law in an attempt to justify larger keys our systems "stronger than cryptography," it's worth keeping in mind that we are approaching fairly deep physical limits. I wrote about this on this list quite a while back. If current physical theories are even approximately correct, there are limits to how many "bit flips" (which would encompass all possible binary operations) can occur in a fixed volume of space-time. You can turn this into a limit based solely on time through the finite speed of light: A computation that starts at some point and runs for n years can't involve a volume of space more than n light years in radius. (This is grossly optimistic - if you want the results to come back to the point where you entered the problem, the limit is n/2 light years, which has 1/8 the spacial volume). I made a very approximate guess at how many bit-flips you could get in a time-space volume of a 100 light- year sphere; the answer came out somewhere between 2^128 and 2^256, though much closer to the former. So physical limits prevent you from doing a brute force scan - in fact, you can't even enumerate all possible keys - in 100 years for key lengths somewhere not much more than 128 bits.
Things may not be quite as favorable as this. Here is a posting I made to cypherpunks in 2004:
To: cypherpunks@al-qaeda.net Date: Wed, 4 Aug 2004 11:04:15 -0700 (PDT) From: hal@finney.org ("Hal Finney") Subject: Re: On what the NSA does with its tech
MV writes:
Yes. They can't break a 128 bit key. That's obvious. ("if all the atoms in the universe were computers..." goes the argument).
Not necessarily, if nanotechnology works. 128 bits is big but not that big.
Eric Drexler, in Nanosystems, section 12.9, predicts that a nanotech based CPU fitting in a 400 nm cube could run at 1000 MIPS and consume 60 nanowatts, performing 10^16 instructions per second per watt.
Let's design a system to break a 128 bit cipher. Let's suppose it has to do 2^10 instructions per test, so this is 2^138 instructions total, or about 10^41. Let's let it run for four months, which is 10^7 seconds, so our necessary processing rate is 10^34 instructions per second.
This means we need 10^34 IPS / 1000 MIPS or 10^25 of Drexler's gigahertz cubes, call it 10^25 cubic microns or 10^7 cubic meters, a cube about 220 meters on a side.
The system will consume 10^25 * 60 nanowatts or about 6 * 10^17 watts. Now, that's a lot. It's four times what the earth receives from the sun. So we have to build a disk four times the area (not volume) of the earth, collect that power and funnel it to our computers. Probably we would scatter the computers throughout the disk, which would be mostly composed of solar collectors. (Keeping the disk gravitationally stable is left as an exercise for the student, as is the tradeoff involved in making it smaller but moving it closer to the sun.)
Fortunately, exhaustive key search is perfectly parallelizable so there is no need for complex communications or synchronizations between the processors.
As you can see, breaking 128 bit keys is certainly not a task which is so impossible that it would fail even if every atom were a computer. If we really needed to do it, it's not outside the realm of possibility that it could be accomplished within 50 years, using nanotech and robotics to move and reassemble asteroids into the necessary disk.
Now, 256 bit keys really are impossible, unless the whole contraption above can be made to operate as an enormous, unified quantum computer, in which case it could theoretically break even 256 bit keys.
512 bit keys... now those really are impossible.
Hal Finney
--------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com