[Top] [All Lists]

Re: How to Calculate Signatures?

2005-04-03 12:26:03

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,
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