In message <425FF239.5050509@optusnet.com.au>, Dmitri Nikulin writes:

>
>Out of curiosity, is there any severe problem with DSA keys? I have read
>that many poor implementations rely too much on quality entropy
>generation, which is (apparently) not a problem in RSA, but have also
>read conflicting documentation that says DSA is usually more 'secure'
>than RSA for authentication on the same key length. Any clarification is
>appreciated.
>
DSA requires a high-quality random number in every signature operation; 
if the attacker can figure out that number, he or she can recover the 
signing key.  If you have enough high-quality randomness lying around, 
you're fine -- and if you don't, your cryptographic keys aren't going to
be very good, either.

>>
>I'm not worried about the security aspect nearly as much as the privacy
>aspects. But if it's really impractical to brute force 256 bits worth of
>AES even /with/ some verifiable plaintext, then there's nothing to worry
>about. I'm more worried about the hassles of no easy way to force both
>Racoons to re-negotiate - I must be missing something. But it's not
>urgent because static keys are 'good enough' for the part of the network
>using IPSec.
>

It's really impractical to brute-force 128-bit keys.  Let's crunch some 
numbers.

We'll start with the successful attack against DES, with its 56-bit 
keys.  That was in 1997, and cost US$250K.  If we assuming that price/
performance has doubled each year since then (i.e., better than Moore's 
Law), the same money would buy a 64-bit key-cracker.  That's 2^64 short 
of what we need.  Maybe our attacker will spend US$250*10^12 to build 
the device.  That still leaves us about 10^10 short of what we need....

Assume there are 10 billion (10^10) people in the world.  Assume that 
each person has 10 billion brute-force cracking chips aimed at you.  
Assume that each chip can do 10 billion trials/second.  That comes to 
10^30 trials/second.  2^128 is about 10^38.5, so it would take 10^8.5
seconds to recover one key.  That's about 10 years.

10 billion people is clearly plausible.  There are AES chips that work 
at 10 Gbps, though since there are 128 bits/block we're still two 
orders of magnitude shy of what I'm postulating.  But I don't believe 
anyone is going to have 10^10 computers, not even Bill Gates, until we 
can do DNA computing.  Pick your favorite derating factor; assuming 
1000 chips/person means the cracking time is ~10^8 years.  That's not 
in my threat model.

As for 256-bit keys -- well, the mass of a proton is 1.67*10^-27 kg.  The 
mass of Jupiter is 1.9*10^27 kg; there are thus ~10^54  protons or 
neutrons in that planet.  But 2^256 is about 10^77; if we run each 
subatomic computer at 10^10 trials/sec it will take 10^13 seconds.
That's about 320,000 years.  Maybe we should use the sun instead; it's 
about 1000 times larger, so we'd only have to wait 320 years for a 
solution...

But all this is meaningless.  As I and others have said before, this 
isn't the weak point.  For far less in the way of resources, I could 
pay for burglars to plant a keystroke and screen logger, listen for 
TEMPEST emissions, bribe or coerce someone into putting a back door 
into the next version of NetBSD and/or its IPsec.  (Don't assume it 
would be found, either; the record on people finding ordinary bugs 
isn't too good, let alone ones that someone has tried to conceal.)

I believe it was John Gilmore who noted that "cryptography is a matter 
of economics".  You're trying to protect some data.  AES is far from 
the weak point.  I'm much more worried about the rate of security holes 
in pkgsrc.

		--Prof. Steven M. Bellovin, http://www.cs.columbia.edu/~smb