DSA key sizes

[Schlacta, Christ]

I'm going to go out on a limb and suggest that gpg should support
government sponsored cryptographic standards whenever possible, but should
consider the highest government sponsored requirement as a minimum
requirement to actually implement. DSA 4096, 5120, and 8192 should be
available when governments advocate 3072. Governments are notorious for
understating cryptography requirements. I also find the rainbow table
fairly probable. Someone on this list should start a project to compute one
on Amazon s3 and see how long it would take and how much it would cost.
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.
On Nov 10, 2014 9:39 AM, "Nan" <nan at goodcrypto.com> wrote:

> Nicholas,
>
> DSA was certainly compromised in the past. Some people think it isn't
> anymore.
>
> It doesn't matter much whether NIST knew or was conned. NIST didn't change
> their Elliptic Curve spec until Snowden published proof of a backdoor. Then
> they adjusted the spec as little as possible. NIST's DSA standard has
> shifted similarly.
>
> In our view it's generally better to avoid state sponsored standards.
>
> >From https://goodcrypto.com/qna/technical/dsa-flaws/:
>
> DSA (U.S. Digital Signature Algorithm) keys haven't made the news, but
> they should. Here's a sentence from the ssh-keygen man page:
>
>     DSA keys must be exactly 1024 bits as specified by FIPS 186-2.
>
> First, why should the whole world be restricted by a U.S. FIPS (Federal
> Information Processing Standard)? In this case it's obvious. NSA very
> likely has rainbow tables for DSA 1024 bit keys. The standard was
> compromised right in the open by not allowing longer keys.
>
> But it's worse than it appears. The SSH spec says "exactly 1024 bits", not
> "1024 bits or less". Why? Because NSA wanted the key length to sound as
> safe as possible, but still make everyone vulnerable to their attacks.
>
> Rainbow tables take a lot of resources to generate. The spec says
> "exactly" because that rainbow table is half of the size of a rainbow table
> for "1024 bits or less". NSA specified "exactly" 1024 bits to cut their
> work in half.
>
> The standard has been updated, but ssh-keygen shows their past behavior.
> We see no reason to believe it has changed.
>
> More detail: X is the size of the table at exactly 1024 bits. The table
> size for 1023 is 1/2 X, for 1022 it's 1/4 X, etc. Then (X + 1/2 X + 1/4 X +
> ...) is 2X.
>
> Nan
>
> GoodCrypto warning: Anyone could have read this message. Use encryption,
> it works.
>
> _______________________________________________
> Gnupg-users mailing list
> Gnupg-users at gnupg.org
> http://lists.gnupg.org/mailman/listinfo/gnupg-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/attachments/20141110/1b44543a/attachment.html>