Re: Suggested changes for DSA2

[[e-mail] ("Hal Finney")]

David Shaw writes:
> On Fri, Mar 24, 2006 at 12:21:42PM -0800, "Hal Finney" wrote:
> > 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?

For example, we have a 1024 bit key with a 160 bit q.  We truncate a
SHA-256 hash to 160 bits.  But q < 2^160, hence the truncated hash can
still be greater than q, i.e.  q < trunc(hash) < 2^160.

I see that my proposed text still has this somewhat ambiguous reference
to "the size of q".  It also refers to the size of the chosen hash when
it should say the output size.  If I fix those two it becomes:

    DSA signatures MUST use hashes whose output size is equal to or larger
    than the number of bits of q, the group generated by the DSA key's
    generator value.  If the output size of the chosen hash is larger
    than the number of bits of q, the hash result is truncated to fit by
    taking a number of leftmost bits equal to the number of bits of q.
    This (possibly truncated) hash function result is treated as a number
    and used directly in the DSA signature algorithm.

Regarding the question of whether to allow intermediate sizes:

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

It's always a tricky question, how much we should try to enforce
security standards in a data-format document.  We do put minimum length
restrictions on the moduli to try to protect users against making one
kind of mistake, using a too-short key.  In the same way, I don't think
we should allow them to use a 160-bit q for a 3072-bit p.  This is the
spirit behind my suggestion to just allow the NIST sizes.

Allowing the bigger sizes would also be consistent with this proposal
but I don't think everyone would want to support those.

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

On re-reading this I have two improvements.  The second sentence is
redundant.  And the last sentence cautions verifiers about what hash
was used when the sig was "issued", but the verifier doesn't know this
(that is the point), it only knows what it sees:

     * The DSA algorithm will work with any hash, but it is
       sensitive to the quality of the hash algorithm.  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 using acceptably strong hash algorithms should
       be accepted as valid.

Hal Finney