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