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