Subject: Re: How to Calculate Signatures?

From: [email-masked] ("Hal Finney")
Date: Sun, 3 Apr 2005 12:39:29 -0700 (PDT)

Konrad Rosenbaum writes:
> On Sunday 03 April 2005 18:41, Ben Laurie wrote:
> > Oh, yes. This left me with an unresolved issue: how does one use
> > SHA{256,384,512} with DSA (which requires a 160 bit hash).
>
> Simple: you don't. DSA was designed to be used with SHA-1, which is 160 bit. 
> Since SHA-1 is theoretically broken (practically will probably follow in a 
> few months) one should see what the NIST makes of it. Supplanting a broken 
> hash with another hash doesn't make much sense with DSA, since it does not 
> contain the ID of the hash (as PKCS#1 does for RSA) - so any attacker could 
> find a collission with the broken hash and then simply change the hash ID 
> in the signature packet.

I have mixed feelings on this issue.  The situation is complex:

 - RFC 2440 has always allowed hashes other than SHA-1 if they matched the
   size of q.  The only one that fit was RIPEMD-160.  This already opens
   the attack Konrad describes.  If RIPEMD-160 were badly broken, you
   could substitute it into a DSA signature using SHA-1.

 - If a hash were broken, recipients can defend against this attack by
   not trusting signatures made with that hash.  That's not all that
   bad.  We are already in a similar situation with regard to other
   cryptographic components.  If a signature algorithm were broken, people
   would have to distrust signatures made with that algorithm.  Same with
   an encryption algorithm, people would have to know not to use it.
   Even with RSA, you'd have to know not to trust signatures made with a
   broken hash.  The specific risk raised by the hash substitution attack
   is that a signer can't protect his signature against substitution
   with a broken hash, he has to rely on the verifier to know that the
   hash is broken and not to trust it.

 - The current hash breaks only allow for collisions and not preimage
   attacks.  It is still not possible, even with MD5, to create a hash
   that matches a target value.  Hashes would have to be broken much
   more severely than they are now before this would become a threat.

 - NIST is dragging their feet on incorporating SHA-2 into a new DSS.
   They have been talking about this for years.  Hopefully the new results
   will motivate them to speed things up, but "fast" in a bureaucracy
   could still mean a year or more.

 - How can we update the replacement for RFC-2440 to incorporate a new
   DSS-2 or whatever it will be called?  Do we need to update the base
   document, or can we create a separate RFC that just documents the
   new format?  Will it be a new algorithm ID, or will we overload the
   DSA algorithm ID?  These issues may slow down the incorporation of
   DSS-2 into OpenPGP even once it is announced.

For all of these reasons, I am tempted to allow the SHA-2 family with
current DSA keys, as an interim measure pending the move to DSS-2.

FIPS 180, which defines the SHA family, had a change notice to add SHA-224,
a truncated form of SHA-256.  This document,
<http://csrc.nist.gov/publications/fips/fips180-2/fips180-2withchangenotice.pdf>,
describes truncation of hash algorithms on page 73:

"Some applications may require a hash function with an output size (i.e.,
message digest size) different than those provided by the hash functions
in this Standard. In such cases, a truncated hash output may be used,
whereby a hash function with a larger output size is applied to the
data to be hashed, and the resulting output (i.e., message digest) is
truncated by selecting an appropriate number of the leftmost bits. For
example, if an output of 96 bits is desired, the SHA256 hash function
could be used (e.g., because it is available to the application), and
the leftmost 96 bits of the output are selected as the message digest,
discarding the rightmost 160 bits of the SHA-256 output."

On this basis, if we did want to support the larger SHA hashes, we should
truncate them and keep the left 160 bits for use with existing DSA keys.

Hal Finney

---

From: Ben Laurie <[email-masked]>
Date: Sun, 03 Apr 2005 21:26:12 +0100

> truncate them and keep the left 160 bits for use with existing DSA keys.

Yes, please.

And "doh!" on the downgrade attack. Must think before posting.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---

From: Ian G <[email-masked]>
Date: Sun, 03 Apr 2005 22:28:19 +0100

>> truncate them and keep the left 160 bits for use with existing DSA keys.

I'm curious on this point.  Other than the fact that
"it's broken" why is it that you see it important to
repair the DSA in OpenPGP?

iang

PS: As a point of notation for the RFC, isn't it DSS?
Or are we saying that DSA is implemented because it
is not quite DSS?
-- 
News and views on what matters in finance+crypto:
         http://financialcryptography.com/

---

From: Jon Callas <[email-masked]>
Date: Mon, 4 Apr 2005 06:44:21 -0700

> discarding the rightmost 160 bits of the SHA-256 output."

This is the reason that Beta 1 of PGP 9.0 allowed SHA-256, and did  
precisely that. However, we decided that that was pushing things, and  
it's not going to be in Beta 2.

	Jon

---

From: Jon Callas <[email-masked]>
Date: Mon, 4 Apr 2005 06:40:21 -0700

> Or are we saying that DSA is implemented because it

DSA is the Digital Signature Algorithm. DSS is the Digital Signature 
Standard. DSS specifies DSA+SHA1 plus operational whatsits. If you use 
DSA with RIPE/MD-160, for example, it's not DSS. 2440 does cover all of 
this.

	Jon