DSA key sizes

[Robert J. Hansen]

> DSA was certainly compromised in the past. Some people think it isn't
> anymore.

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 
publications.

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
> backdoor.

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 
about ECDSA.)

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:

http://csrc.nist.gov/publications/nistbul/itlbul2013_09_supplemental.pdf

"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:

http://www.nist.gov/itl/csd/sp800-90-042114.cfm

"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
> standards.

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 
business.

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.