Fwd: Ultimate limits to computation

[R.A. Hettinga]

Begin forwarded message:

> From: hal at finney.org ("Hal Finney")
> Date: August 11, 2009 2:47:27 PM GMT-04:00
> To: leichter at lrw.com
> Cc: cryptography at 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 at al-qaeda.net
> Date: Wed,  4 Aug 2004 11:04:15 -0700 (PDT)
> From: hal at 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 at metzdowd.com