From: Tom Weinstein <tomw@netscape.com>
Date: Fri, 5 Jan 1996 03:11:24 +0800
To: cypherpunks@toad.com
Subject: Re: 2047 bit keys in PGP
In-Reply-To: <v02130503ad119cbfdece@[205.231.67.43]>
Message-ID: <30EC164A.2781@netscape.com>
MIME-Version: 1.0
Content-Type: text/plain


Ian Goldberg wrote:
> 
> Order of magnitude check:
> 
> There is a very well-defined limit to the size of key that can be
> broken by brute force, independent of your "wildest dreams" as to the
> growth of technology.  It's the Laws of Thermodynamics.
> 
> For a symmetric algorithm for which any value of the appropriate
> length n is a possibly valid (and equally likely) key, there are 2^n
> keys to try in a brute-force search.  From Applied Crypto, 2nd ed,
> pp157-158, setting or clearing one bit takes at _least_ 4.4*10^-16 erg
> of energy.  For symmetric keys of size 256, then, you would need more
> than 10^61 erg (that's 10^45 GJ) of energy just to _enumerate_ the
> states.  For comparison, this about 10 billion times larger than the
> output of a typical supernova.
> (Ibid.)

Although your point is quite valid, there is always the possibility of
some technological advance that invalidates these calculations.  It is
possible that quantum crypto will some day make brute forcing 256 bit
keys practical.  (Of course, my knowledge about quantum crypto couldn't
fill a thimble, so maybe I'm wrong.)

These results also apply only to symmetric key ciphers and have no
relation to the difficulty of breaking RSA.  The techniques for
factoring large numbers have come a long way in the recent past and it
would not be much of a surprise for them to take another large leap.

All that being said, I believe that 128 bits is sufficient for a
symmetric key and 2048 for a public key.  Our paranoia would be far
better directed at as yet unknown attacks on the algoritms involved
or the specific implementations of cryptographic systems.  Paul Kocher's
recent timing attack is a perfect example of what we should be afraid
of.

-- 
Sure we spend a lot of money, but that doesn't mean | Tom Weinstein
we *do* anything.  --  Washington DC motto          | tomw@netscape.com