DSA key sizes

[Nan]

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.