Re: Suggested changes for DSA2 ("Hal Finney") Tue, 28 March 2006 21:25 UTC

Received: from [] ( by with esmtp (Exim 4.43) id 1FOLh2-0005Kr-Tu for; Tue, 28 Mar 2006 16:25:36 -0500
Received: from ([]) by with esmtp (Exim 4.43) id 1FOLh1-0008ET-HC for; Tue, 28 Mar 2006 16:25:36 -0500
Received: from (localhost []) by (8.13.5/8.13.5) with ESMTP id k2SL5pNw092238; Tue, 28 Mar 2006 14:05:51 -0700 (MST) (envelope-from
Received: (from majordom@localhost) by (8.13.5/8.13.5/Submit) id k2SL5pG6092237; Tue, 28 Mar 2006 14:05:51 -0700 (MST) (envelope-from
X-Authentication-Warning: majordom set sender to using -f
Received: from ( []) by (8.13.5/8.13.5) with ESMTP id k2SL5oZP092231 for <>; Tue, 28 Mar 2006 14:05:50 -0700 (MST) (envelope-from
Received: by (Postfix, from userid 500) id 631EA57FAE; Tue, 28 Mar 2006 13:04:12 -0800 (PST)
Subject: Re: Suggested changes for DSA2
Message-Id: <>
Date: Tue, 28 Mar 2006 13:04:12 -0800
Precedence: bulk
List-Archive: <>
List-Unsubscribe: <>
List-ID: <>
X-Spam-Score: 0.1 (/)
X-Scan-Signature: 25620135586de10c627e3628c432b04a

David writes:
> Forgetting DSA2 for a moment, this isn't a new problem.  We have this
> same key size / hash size mismatch possibility today with DSA1 (since
> DSA in 2440 could be 768-1024 bits), and again with RSA (which can use
> any hash, regardless of the key size).  Fixing the q sizes for DSA2
> doesn't really solve this.

The problem is not so bad with DSA1 because at worst the hash and
subgroup would have been stronger than the key size, so by reporting
the modulus we are giving an accurate lower bound on the strength.

But you're right that we have had the problem all along with RSA.
In fact in the old days I don't doubt that we had many users with 8K
bit RSA keys using 128 bit MD5 for signatures.

Daniel is right too that there is not complete agreement about the
proper balance between subgroup/hash size and modulus size, and that
future cryptographic developments may change this balance.

Although we have not discussed it, the same problem arises for encryption,
balancing the symmetric algorithm key size with the public key size.
I've heard complaints that letting people use AES-256 with a 1024 or
2048 bit RSA key gives them a false sense of security.

Clearly this complexity is a challenge to deal with.  However we have
made attempts in the past to provide minimal security guidelines.
In our section 12 Notes on Algorithms we have sections 12.4, 12.5 and
12.6 giving minimum key sizes for RSA, DSA and DH as SHOULDs.

I support David's suggestion to include a SHOULD relating hash size to key
size.  But it makes sense to me to extend our current key size SHOULD
recommendations to include advice regarding subgroup size, hash size,
and symmetric cipher key size.  This would correspond to Table 2 on page
63 of NIST's SP800-57:

The sizes from that table are:

 1024 /  160 /  80
 2048 /  224 / 112
 3072 /  512 / 256
 7680 /  768 / 384
15360 / 1024 / 512

where the 1st column is the RSA, DSA or DH modulus size, the second
column is the hash/subgroup size, and the 3rd column is the symmetric
cipher key size (which is also the strength in bits).

We could do as David suggests and say that implementors SHOULD follow
SP800-57 or whatever updates it.  However this will require implementors
to acquire and read through this 220 page document in order to find
these five lines of information.  It seems to me that it is worthwhile to
include these lines, and also to refer to SP800-57 and advise implementors
to check for updates.  Proposed language:

   In order to provide consistent levels of security for end users,
   implementors SHOULD balance public key modulus size, subgroup size,
   hash size, and symmetric algorithm key size.  While consensus about
   appropriate choices of these parameters may change with time, NIST
   Special Publication 800-57 recommends the following parameter size

   [Some version of NIST's Table 2 here]

   Implementors SHOULD use and require public key and other parameters
   consistent with values in this table, or updated information based
   on evolving consensus in the field.

We could use this to replace the current language about key sizes in
section 12, since the 1024 bit minimum is implicit in the table.