Subject: DSA hash algorithms

From: [email-masked] ("Hal Finney")
Date: Fri, 25 Feb 2005 11:22:21 -0800 (PST)

Jon and I (who both work for PGP Corp.) were looking at the situation with
DSA hash algorithms.  The recent attack on SHA-1, reducing its strength
from 2^80 down to 2^69, is motivating a move towards the SHA-2 family.
PGP is migrating towards SHA-2 as the default hash algorithm for use
with RSA signatures.

We discussed the pros and cons of allowing SHA-2 with DSA signatures.
It's a complicated issue, cryptographically and technologically, which
I could write more about.  But in the process we reviewed the language
in the RFC draft about the issue.

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.

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.

     * There is a somewhat-related potential security problem in
       signatures. If an attacker can find a message that hashes to the
       same hash with a different algorithm, a bogus signature
       structure can be constructed that evaluates correctly.

       For example, suppose Alice DSA signs message M using hash
       algorithm H. Suppose that Mallet finds a message M' that has the
       same hash value as M with H'. Mallet can then construct a
       signature block that verifies as Alice's signature of M' with
       H'. However, this would also constitute a weakness in either H
       or H' or both. Should this ever occur, a revision will have to
       be made to this document to revise the allowed hash algorithms.

Presently, then, we allow DSA signatures to use other hashes than SHA-1,
but they have to be exactly 160 bits.  The only other 160 bit hash we
support is RIPEMD-160.  The language allows this hash, but technically
disallows any of the SHA-2 family hashes from being used with our DSA
signatures.

This is unfortunate, because it makes us vulnerable to hash rollback
attacks, as described in the last paragraph above, but does not let us
move to what are thought to be the strongest hashes in the standard,
SHA-256 and SHA-512.  So in a way we have the worst of both worlds: hash
rollbacks because we don't fix on SHA-1 as the DSS does; but inability
to respond flexibly to attacks on the current hashes.

(Although RIPEMD-160 has not been attacked, the earlier RIPEMD hash was
broken last year, and it seems plausible that the new attacks could work
against RIPEMD-160 as well.)

I suggest that we do one of two things.  We could change the spec to
require SHA-1 with DSA keys, and then when NIST comes out with DSA-2
which uses SHA-2 (which they have been promising for years now), we will
then support the larger hashes.  Or we could change the spec to allow
any hash >= 160 bits to be used with DSA keys.  We could follow the NIST
recommendation in http://csrc.nist.gov/publications/fips/fips180-2/fips180-2withchangenotice.pdf
and use just the left 160 bits of the larger hash.

I lean towards the first solution, even though hash rollback attacks
require the ability to completely reverse hashes and not just find
collisions, so we really do seem safe from them.  I feel uncomfortable
going out with a spec that intentionally opens itself up to a preventable
attack.  But it's frustrating that NIST has dragged its feet and not
come up with a DSA standard that allows other hashes.  It is tempting
to allow SHA-2 with DSA as an interim measure.

BTW, I'm not sure about the comment above about weak hashes exposing
secret keys with DSA.  I can't bring such an attack to mind.  Does anyone
have a reference to that?

Hal Finney

---

From: Ian G <[email-masked]>
Date: Fri, 25 Feb 2005 20:23:25 +0000

>to allow SHA-2 with DSA as an interim measure.

I also lean to the first solution.  I do not
judge the size of the market in digital
signatures to be anywhere significant
enough to worry about, and the attacks
so far mooted are all in the theoretical,
unvalidated domain.

Secondly, if someone wants something
stronger than DSA, they can use RSA.

It's good to review the possibilities though.

(I'm sure NIST have also received their
wake up call by now ;-)

iang

-- 
News and views on what matters in finance+crypto:
        http://financialcryptography.com/

---

From: Lutz Donnerhacke <[email-masked]>
Date: Fri, 25 Feb 2005 20:07:08 +0000 (UTC)

> against RIPEMD-160 as well.)

IBTD. By the same argument applies to the SHA-2 family. It is senseless.

> and use just the left 160 bits of the larger hash.

Because every hash of 160bit will do, I'd propose to be as flexible as
possible. We can provide a general statement about hashes in all contexts:
 "If the digest is larger than expected, only the leftmost bits count."

I do not know if those truncated hashes provide the same level of security ...

---

From: Werner Koch <[email-masked]>
Date: Fri, 25 Feb 2005 23:00:57 +0100

> I also lean to the first solution.  I do not

Same here. 

  Werner