DSA key sizes
Robert J. Hansen
rjh at sixdemonbag.org
Mon Nov 10 19:31:04 CET 2014
> DSA was certainly compromised in the past. Some people think it isn't
This is news to the cryptographic community. Cite, please? I want to
know who these "some people" are, and a list of their major academic
If Dan Boneh says DSA is compromised, I'll have a coronary and I'll rush
to read the paper proving it. If Joe Bob's Web Page Of Crypto says DSA
is compromised, I'm going to yawn and click "Back".
> 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
NIST's DSA standard has never been compromised, nor did Snowden release
any proof of a backdoor in a NIST DSA standard. (I know, I know, Nan is
just saying "elliptic curve spec". Given the sentence is embedded in
some talk about DSA, I think it's reasonable to think Nan's talking
What Nan means to be talking about is the Dual Elliptical Curve
Deterministic Random Bit Generator (Dual_EC_DRBG) specification -- a way
of generating random numbers, but *not* a signature algorithm. It was
released in 2004 to a great yawn: it was inefficient, slow, and the
parameters gave some people the heebie-jeebies. In 2007, Shumow and
Ferguson presented at CRYPTO some results that made this design look
like it might be backdoored.
An algorithm that nobody used in the first place ... remained an
algorithm that nobody used in the first place.
Six years later the _New York Times_, reporting on alleged internal NSA
memos provided by _l'affaire Snowden_, accused the NSA of inserting a
back door into the Dual_EC_DRBG standard. But _l'affaire Snowden_ did
not reveal the problems in Dual_EC_DRBG. They were already quite well
known about in the crypto community.
> Then they adjusted the spec as little as possible.
This is a flat lie. NIST's official statement can be found at:
"NIST strongly recommends that, pending the resolution of the security
concerns and the re-issuance of SP 800-90A, the Dual_EC_DRBG, as
specified in the January 2012 version of SP 800-90A, no longer be used.
Effective immediately, NIST Special Publication 800-90A is being
re-issued as a draft for public comment for a period ending November 6,
2013. Any concerns or recommendations for improvement regarding the
Recommendation for Random Number Generation Using Deterministic Random
Bit Generators are solicited."
Then, on April 21, 2014, they announced their final decision with
respect to Dual_EC_DRBG:
"Following a public comment period and review, the National Institute of
Standards and Technology (NIST) has removed a cryptographic algorithm
from its draft guidance on random number generators."
Dual_EC_DRBG wasn't "adjusted as little as possible". It was outright
*removed*. And given how easy this is to find -- seriously, NIST *wants
people to know this* -- I find this error of fact pretty much inexcusable.
> In our view it's generally better to avoid state sponsored
Who is the "us" that you're referring to?
>> From https://goodcrypto.com/qna/technical/dsa-flaws/:
From that webpage:
"DSA has been compromised." No, it hasn't. So far no one has shown any
ability to break even DSA-1024. I'm not optimistic about the long-term
health of DSA-1024 (see the archives), but it's flat *wrong* to say that
we know DSA-1024 to be compromised.
"The SSH spec says 'exactly 1024 bits', not '1024 bits or less.' Why?"
Because FIPS 186-2, which OpenSSH wants to track, requires 1024-bit
DSA. FIPS 186-3 and 186-4, successors, permit up to 3072-bit DSA.
Why isn't OpenSSH tracking FIPS 186-3 and -4? Good question. Probably
because the handwriting is on the wall and ECDSA is the future, and
limited manpower can be better devoted to getting ECDSA working
correctly rather than continuing to track obsolescent DSA standards.
> First, why should the whole world be restricted by a U.S. FIPS
> (Federal Information Processing Standard)?
It's not. However, there are a *lot* of businesses that do trade with
the United States government, and these businesses are required to
comply with federal information processing standards. If your software
doesn't conform to the appropriate FIPS, you won't get the government's
It's like objecting to the Russian cipher GOST. GOST is a Russian
governmental standard. If you want to do business with the Russian
government, you need to support GOST. That doesn't mean you're
"restricted" to supporting GOST; that means supporting GOST is a good
idea for anyone who wants to do business with the Kremlin.
> 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.
This is factually incoherent. Rainbow tables attack hash functions:
they don't attack signature algorithms. If someone was interested in
using rainbow tables against a signature algorithm they'd make sure to
carefully specify what hash algorithm was used, because rainbow tables
have to be made specifically for a hash algorithm. But we don't see
that in the DSA spec, so the conclusion I draw is that what you're
saying here is flat wrong.
More information about the Gnupg-users