Re: Suggested changes for DSA2

[David Shaw <[e-mail]>]

On Fri, Mar 24, 2006 at 12:21:42PM -0800, "Hal Finney" wrote:

> First, I think this needs to be moved out of 5.2.2 since it is not
> specific to V3 signatures; either that, or it needs to be replicated
> in 5.2.3 on V4 sigs.  Actually there is a lot of stuff in 5.2.2 about
> signatures that does not belong there, a bunch of rules for RSA, OIDs
> and such.
> 
> Perhaps this should all go into 5.2.4, Computing Signatures; or into a
> new section, 5.2.5.  Unfortunately for the readability of the document,
> 5.2.3 is extremely long as it discusses each subpacket, so many people
> don't necessarily notice 5.2.4 and realize how crucially important it is.
> I wonder if it would make sense to move the subpackets out of 5.2.3 and
> into a new 5.2.6 section, so that 5.2.4 and the new 5.2.5 would be right
> up front with the other data.

I agree with all this.

> Aside from this I think David's wording is a little unclear about "the
> appropriate number" of leftmost bits.  Maybe we could say:
> 
>     DSA signatures MUST use hashes that are equal to or larger than the
>     size of q, the group generated by the DSA key's generator value.
>     If the chosen hash is larger than the size of q, the hash result
>     is truncated to fit by taking a number of leftmost bits equal to
>     the number of bits in q.  This (possibly truncated) hash function
>     result is treated as a number and used directly in the DSA signature
>     algorithm.
>
> Note that this truncation (or non-truncation) could still leave the
> hash as bigger than q, but that is OK as the signature and validation
> algorithms will either explicitly or implicitly take it mod q as it
> is used.  So I don't think we have to tell them to take it mod q.

I agree with your suggested change, but I'm not sure I follow this
comment.  How could the hash still be bigger than q if we're
explicitly truncating it to be the same size as q?

> That's a good question.  I am uncomfortable permitting larger DSA
> keys of sizes different than the DSS ones.  The balancing of the q and
> p sizes is something of an art and people tend to disagree somewhat.
> What size should q be for a 1568 bit modulus?  Or a 1024+64=1090 bit one?
> It's very questionable.
> 
> I would feel more comfortable restricting to the DSS key sizes even
> for OpenPGP keys.  Is there really much benefit to intermediate sizes?
> The size of the signature is dependent only on the size of q, and I
> don't know how we could legitimately scale up from 160 to 224 or 256
> as we increase p from 1024 to 2048 bits.  Yes, we could come up with
> some formula, but there would not be much consensus.  The FIPS guys
> undoubtedly faced the same problem and decided to finalize on just these
> two new sizes, and I am inclined to do the same.

I wasn't so much thinking about which q to use for intermediate p
sizes, but rather thinking more from the verification end: namely, we
can't stop people from generating whatever key they like, sensible or
not.  So rather than defining the set of valid p/q pairs, and
presumably rejecting any p or q outside the defined set, I was
thinking of just stepping back and saying, in effect, that this isn't
our problem to solve.  Give SHOULD guidance on what to generate
(i.e. the FIPS list), but don't make it a MUST to lock things down to
that list.  Otherwise, a few years from now, FIPS-186-4 will come out
and define a p/q pair not on the FIPS-186-3 list and break all of our
implementations.

The FIPS draft refers such questions to NIST publication SP800-57,
which actually does mention two larger p/q pairs: p=7680 q=384 and
p=15360 q=512 (see page 63).  Not that I think that a 15360-bit DSA
key is useful in practice in 2006, but clearly there is already
consideration of other key sizes.

> > Hal has expressed concern with the "weak hash can leak the secret key"
> > warning in the past, so perhaps he'll comment here.
> 
> Right, I don't believe it is true that a weak hash can leak the secret
> key.  Rather, a weak random choice of the "k" value in the signature
> can leak the secret key, but that is a completely different issue.
> 
> As far as this wording, it is OK but it needs to be emphasized for the
> verifier as much as or more than for the signer.  One problem with the
> new DSS is that it does not specify a unique hash algorithm, hence if
> any of them break then an attacker could take an existing signature,
> modify the hash algorithm ID, and perhaps create a fake message that
> works with that signature and the broken hash.  There is nothing the
> signer can do to prevent this.  Even if he uses a strong hash, if there
> is a broken hash around someone can change the signature to use that hash.
> So the point is that the verifier more than the signer must make sure that
> a DSA signature is signed by an acceptably strong hash.  If SHA-256 breaks
> but SHA-512 is still OK it needs to warn on signatures using SHA-256.
> 
> So I would suggest something like this:
> 
>      * The DSA algorithm will work with any hash, but it is
>        sensitive to the quality of the hash algorithm.  An implementation
>        should take care which hash algorithms are used with DSA.
>        Verifiers should be aware that even if the signer used a strong
>        hash, an attacker could have modified a signature to use a
>        weak one.  Only signatures issued using acceptably strong hash
>        algorithms should be accepted as valid.

Agreed.

David