Fermi estimates

[Robert J. Hansen]

A while ago Hauke asked if the statement in the FAQ about a brute-forcer
leaving the Earth uninhabitable was correct.  I said it was, but I
didn't break out the math.  Now that I have a few minutes to breathe,
here's the full answer.  It's a Fermi estimate, which means it's not
going to be perfectly accurate.  It's going to be in the ballpark, but
more than that isn't guaranteed.

The Landauer bound: you can't flip a bit using less than 10**-29 joules
of energy.

The Margolus-Levitin theorem: at 10**-29 joules of energy, you can't
make it flip faster than 10**-5 seconds.

Let's estimate the bitflips needed to check a key at a cool one million.
 That covers loading the new key, populating key schedules, doing a
trial decryption, the whole nine yards.  10**6 operations per key.

Let's also say your computer can flip 100 bits at a time (10**2).

10**6 bits per key, processed 10**2 at a time, means a total elapsed
time of (10**6 / 10 **2 = 10**4 bitflips per thread, multiplied by
10**-5 seconds per bitflip, equals 10**-1 seconds) a tenth of a second
per key.  Now, before you say "but my computer's much faster than
that!", your computer also isn't running on less power than you generate
by scuffing your feet on the carpet.  We'll be exploring faster
computers in a bit.

Breaking a 128-bit cipher by brute force requires about 10**38 key
attempts.  10**38 attempts times 10**-1 seconds per attempt equals ...
uh ... a lot of seconds.  10**37.  A year is more or less 10**7 seconds,
so 10**30 years.  The universe is about 10 billion years old, or 10**13
years, so ... our brute-force key cracker takes 10**17 times longer than
the age of the universe in order to brute-force a 128-bit key.

Clearly, we need to speed things up a bit.  We need to upgrade from a
carpet-scuffing system to two hamsters running on a treadmill.
Unfortunately, that's only a few thousandfold power improvement, so
we're going to have to give the hamsters amphetamines to get them the
rest of the way.  Now, with 10**30 times the power input (these are some
*good* amphetamines), our brute-forcer will be finished in a single year.

10**38 attempts at 10**6 bitflips per attempt equals 10**44 bitflips
total.  At carpet-scuffing power, that's about 10**15 joules of energy,
or about a single one-megaton nuclear bomb.  Admittedly, that energy
gets released over 10**13 times the age of the universe, so that's not a
big problem.  But to make our brute-forcer 10**30 times faster (so it
can run in one year), our brute-forcer also has to release 10**30 times
as much heat.

I'm not an astrophysicist, but that's the kind of energy levels one
normally associates with phrases like "perturb the false vacuum" and
"unmake the universe at the speed of light."  Look at the time, I must
be going.

Also: I'm hiring for a minion.  (Lackey, lickspittle, graduate student.
 Call it what you like.)  The pay is almost nothing, but somebody's got
to clean the hamster cage while I'm gone.  I'm moving to the nearest
convenient parallel dimension.  It's getting weird and dangerous around
here...





-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3744 bytes
Desc: S/MIME Cryptographic Signature
URL: </pipermail/attachments/20141113/e84a2725/attachment-0001.bin>