Subject: Re: Suggested changes for DSA2

From: [email-masked] ("Hal Finney")
Date: Tue, 28 Mar 2006 13:04:12 -0800 (PST)

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:
http://csrc.nist.gov/publications/nistpubs/800-57/SP800-57-Part1.pdf

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

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

Hal

---

From: David Shaw <[email-masked]>
Date: Tue, 28 Mar 2006 18:22:49 -0500

> The sizes from that table are:

Are you sure that table is correct?  I thought it was:

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

> Proposed language:

I'm not sure this is the right way to go about it.  Is balance
actually what we want, or would it be better to just remind people
that the weakest parameter constrains the level of security?  There is
nothing invalid about a 8192-bit RSA key making SHA-1 signatures.  It
just means that the signature has at most 80 bits of strength.  The
signer could have used a 1024-bit RSA key and gotten the same 80 bits
of strength, but that doesn't make the 8192-bit signature wrong (just
large).  My suggested wording was more to encourage implementors to
indicate the actual strength, rather than to force balance.

How about this (presumably for the Security Considerations section):

   As OpenPGP combines many different asymmetric, symmetric, and hash
   algorithms, each with different measures of strength, care should
   be taken that the weakest element of an OpenPGP message is still
   sufficiently strong for the purpose at hand.  Implementations
   receiving messages SHOULD indicate to the user the actual strength
   of the messages.  While consensus about the the strength of a given
   algorithm may evolve, at publication time, NIST Special Publication
   800-57 [SP800-57] recommended the following list of equivalent
   strengths:

       [ put table here ]

I'm still in favor of making the NIST list a SHOULD for generating
DSA2 keys, of course.

David