key bit lengths

In Applied Crypto, it talks about thermodynamic limitations of brute 
force attacks.  I did some calculations and it looks like it will take, 
given a perfectly effecient computer, the combined energy of 509,485,193 
average supernovas to brute force a 256 bit key. I was just wondering if 
there are any theoretical ways around this. I am just talking about 
plain brute force here, not attacking other weaknesses.
-- 
thecrow@iconn.net
"It can't rain all the time"

RSA ENCRYPTION IN 3 LINES OF PERL
---------------------------------------------------------
#!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj
$/=unpack('H*',$_);$_=`echo 16dio\U$k"SK$/SM$n\EsN0p[lN*1
lK[d2%Sa2/d0$^Ixp"|dc`;s/\W//g;$_=pack('H*',/((..)*)$/)

-----BEGIN PGP SIGNED MESSAGE-----

On Sun, 14 Apr 1996, Jack Mott wrote:

> In Applied Crypto, it talks about thermodynamic limitations of brute
> force attacks.  I did some calculations and it looks like it will take,
> given a perfectly effecient computer, the combined energy of 509,485,193
> average supernovas to brute force a 256 bit key. I was just wondering if
> there are any theoretical ways around this. I am just talking about
> plain brute force here, not attacking other weaknesses.

I doubt it.  This calculation is based on the minimum amount of energy
needed to invert a bit.  The amount of energy is a function of the temperature,
so a brute force attack might take much less energy several billion years
hence, since the universe will cooled off more.  There only way for there to
be any way around this, is if a way was found to lower the termperature to
near absolute zero consuming a very little amount of energy, or if some way
was found to invert a bit using less energy than is currently believed (very
doubtfull).  Of course, if P=NP, then brute-force attacks will be pointless.

- -- Mark

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
markm@voicenet.com              | finger -l for PGP key 0xf9b22ba5
http://www.voicenet.com/~markm/ | bd24d08e3cbb53472054fa56002258d5
"The concept of normalcy is just a conspiracy of the majority" -me

-----BEGIN PGP SIGNATURE-----
Version: 2.6.3
Charset: noconv

iQCVAwUBMXFCPbZc+sv5siulAQF2jAP9GgSk+YqNjcnyThzs6ow1Ecyp60iK0kiE
Y9RMqLtdwpMv2Jx10KigDsyOvQrM0+W/RJ3Q2Zka+VF4aBT82z5NcbUvzEG4Y1iT
t12PZF8rhFgxNB+jNOOCxS0BYRcFAC3epZ050+gRdtOenLLNsczyrXJN+fMyaTAf
gnCis3s1n1o=
=Rvcm
-----END PGP SIGNATURE-----

> so a brute force attack might take much less energy several billion years
> hence, since the universe will cooled off more.

Proportionally to the amount of energy available in the universe to conduct
such an attack however. You have to get it from somewhere.

-- 
"I mean, after all;  you have to consider we're only made out of dust.  That's
 admittedly not  much  to  go  on  and  we  shouldn't  forget  that.  But even
 considering, I mean it's sort of a bad beginning, we're not doing too bad. So
 I personally have faith that even in this lousy situation we're faced with we
 can make it. You get me?" - Leo Bulero/PKD
+---------------------+--------------------+----------------------------------+
|Julian Assange RSO   | PO Box 2031 BARKER | Secret Analytic Guy Union        |
|proff@suburbia.net   | VIC 3122 AUSTRALIA | finger for PGP key hash ID =     |
|proff@gnu.ai.mit.edu | FAX +61-3-98199066 | 0619737CCC143F6DEA73E27378933690 |
+---------------------+--------------------+----------------------------------+

> force attacks.  I did some calculations and it looks like it will take, 
> given a perfectly effecient computer, the combined energy of 509,485,193 
> average supernovas to brute force a 256 bit key. I was just wondering if 

I'd be interested to see those calculations. If 128 bit keys would require
sqr(509485193) supernovas, I think we probably don't need to go much
higher with the number of bits.  OTOH, if the feds can somehow figure out
how to convert all the matter in the solar system into energy, they might
be able to get enough energy... e=mc^2... But, there wouldn't be anywhere
to put the computers. :)

While we're exchanging calculations.... 

I've done some simple calculations myself (which have probably already
been done, but anyway...), regarding 128 bit keys, assuming a billion
(10**9) computers trying a billion keys per second... I heard it would
take an average of 6 billion years to crack a 128 bit key with those
resources, but my calculations (using GNU bc v1.02 under FreeBSD) figure
it at over 5 trillion years... 

echo "2^128 / 10^9 / 10^9 / (60 * 60 * 24 * 365.25)" | bc
10782897524556

With commas, that's 10,782,897,524,556 years. Cut that in half (for
average cracking time), it comes to 5,391,448,762,278 years. I don't know 
where I heard the 6 billion year figure, it might have been in the Wired 
Cypherpunks article, but I think I read it somewhere else as well... Is 
my calculation okay?

Similar calculation... Assume you have a 384 bit key that you want to
brute-force, and you have 10^73 computers trying 10^9 calculations per
second. (Last I heard, 10^73 is the number of particles in the universe). 

echo "2^384 / 10^73 / 10^9 / (60 * 60 * 24 * 365.25)" | bc
124857423240026108488221664

That's an impressive number. :)

As an aside, I've heard that "billion" and "trillion" are different in 
different parts of the world...

           Western   British
billion     10^9      10^12
trillion    10^12     10^18

A British friend mentioned to me that they are different... We checked
with American and British dictionaries to get those figures. AFAICS,
Canada seems to use the American system. Weird, eh? 

=====================================================================
| Steve Reid - SysAdmin & Pres, EDM Web (http://www.edmweb.com/)    |
| Email: steve@edmweb.com   Home Page: http://www.edmweb.com/steve/ |
| PGP Fingerprint: 11 C8 9D 1C D6 72 87 E6  8C 09 EC 52 44 3F 88 30 |
|              -- Disclaimer: JMHO, YMMV, IANAL. --                 |
===================================================================:)