Re: Suggested changes for DSA2

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

David's suggestions are a good starting point but I have a few
comments:

> ==================================
>
> Section 5.2.2 (Version 3 Signature Packet Format) says:
>
>     DSA signatures MUST use hashes with a size of 160 bits, to match q,
>     the size of the group generated by the DSA key's generator value.
>     The hash function result is treated as a 160 bit number and used
>     directly in the DSA signature algorithm.
>
> change to:
>
>     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 the appropriate number of
>     leftmost bits.  This (possibly truncated) hash function result is
>     treated as a number and used directly in the DSA signature
>     algorithm.

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.

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.

> ==================================
>
> Section 12.5. (DSA) says:
>
>     An implementation SHOULD NOT implement DSA keys of size less than
>     1024 bits. Note that present DSA is limited to a maximum of 1024 bit
>     keys, which are recommended for long-term use. Also, DSA keys MUST
>     be an even multiple of 64 bits long.
>
> change to:
>
>     An implementation SHOULD NOT implement DSA keys of size less than
>     1024 bits.  DSA keys MUST be an even multiple of 64 bits long.
>     The Digital Signature Standard (DSS) specifies that DSA be used
>     in one of the following ways:
>
>     * 1024-bit key, 160-bit q, SHA-1 hash
>     * 2048-bit key, 224-bit q, SHA-224, SHA-256, SHA-384 or SHA-512 hash
>     * 2048-bit key, 256-bit q, SHA-256, SHA-384 or SHA-512 hash
>     * 3072-bit key, 256-bit q, SHA-256, SHA-384 or SHA-512 hash
>
>     Other key size and hash combinations are usable in OpenPGP, but
>     would not be compliant to DSS.
>
>     Note that earlier versions of this standard only supported a
>     160-bit q, so earlier implementations may not be able to
>     handle a signature with a different q size.
>
> DSA keys are a multiple of 64 bits.  Are there similar requirements
> with regards to the size of q that are worth mentioning here?  I don't
> mean the NIST DSS requirements, but rather inherent requirements of
> the algorithm.

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.


> ==================================
>
> Section 13. (Security Considerations) says:
>
>      * The DSA algorithm will work with any 160-bit hash, but it is
>        sensitive to the quality of the hash algorithm, if the hash
>        algorithm is broken, it can leak the secret key. The Digital
>        Signature Standard (DSS) specifies that DSA be used with SHA-1.
>        RIPEMD-160 is considered by many cryptographers to be as strong.
>        An implementation should take care which hash algorithms are
>        used with DSA, as a weak hash can not only allow a signature to
>        be forged, but could leak the secret key.
>
> change to:
>
>      * 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, as a weak hash can not only allow a signature to
>        be forged, but could leak the secret key.
>
> 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.


Hal Finney