Ultimate limits to computation

Hal Finney hal at finney.org
Tue Aug 11 14:47:27 EDT 2009


[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



More information about the cryptography mailing list