DSA key sizes

[Robert J. Hansen]

> DSA 4096, 5120, and 8192 should be available when governments
> advocate 3072.

The USG does not advocate any particular key size.  They've made DSA
available in three sizes (as of FIPS 180-something) to support a variety
of different needs.

> I also find the rainbow table fairly probable.

I don't want to sound blunt, but I respectfully suggest you don't
understand how rainbow tables work.

They aren't used against signature algorithms.  They're used against
*hash algorithms*.  Huge difference.  If you have a rainbow table that
can break SHA-1 (not that I think one exists today), then it's
completely useless against RIPEMD-160 or truncated SHA-256.

If anyone wanted to use rainbow tables against DSA-1024, they would need
some way to ensure that only one particular hash algorithm could be used
with DSA-1024.  Instead, DSA-1024 just requires 160 bits of hash.
SHA-1, RIPEMD-160, Tiger-192, WHIRLPOOL, SHA-224/160, SHA-256/160,
SHA-384/160, SHA-512/160...

Or, if you already believe some shadowy and nefarious organization has
rainbow tables for SHA-1, then I guess you could just say "I believe the
shadowy and nefarious conspiracy has at least eight times the resources
it did before, and it has rainbow tables for *everything*."

But at that point you've got a problem: if you're positing that your
opponent has such unlimited computational resources that they're in
effect God, well ... you don't win against God.  You've just defined the
opposition as having such unlimited computational resources that nothing
you do will matter and nothing you do can possibly save you.

> Given the recent demonstration of an md5 break for less than a dollar
> on s3 gpu nodes, I'd not be surprised to see it in under a year.

That's MD5.  We knew all the way back in 1997 that MD5 could be broken
on a Pentium-90 (that's a 90MHz Pentium, kids: a full tenth of a
gigahertz) in under an hour.  We knew it because Hans Dobbertin *did
it*.  (The MD5 attacks have all been attacks on the MD5 compression
function, extended out to attacks on the full MD5 hash.  In 1997, Hans
Dobbertin proved the MD5 compression function was quite a lot weaker
than anyone expected and produced collisions in the compression function.)

SHA-1 has been shown to have a much weaker compression function than the
designers intended.

No one has shown any such weaknesses in RIPEMD-160, SHA-224, SHA-256,
SHA-384, SHA-512, Tiger192, or WHIRLPOOL.