DSA and SHA-1 (was RE: Parameters and Algorithms. )

FYI...

For our definition of DSA, we are currently referencing FIPS 186-1 (see
http://csrc.nist.gov/fips/fips1861.pdf).  In section 5, titled "DSA
SIGNATURE GENERATION" it defines a DSA signature thus:

    r = (g^k mod p) mod q
    s = (k^-1(SHA-1(M) + xr)) mod q

In other words, DSA is defined to use SHA-1.  Perhaps the same algorithm
could be used with other message digests (I do not know whether it is
cryptographically safe to do so), but technically speaking it would not be
DSA.  Since we're writing a standard we need to speak precisely.

-Mark Bartel
JetForm

-----Original Message-----
From: Eric Rescorla
To: Jim Schaad (Exchange)
Cc: W3c-Ietf-Xmldsig (E-mail)
Sent: 10/14/99 4:57 PM
Subject: Re: Parameters and Algorithms. 

> OK -- let me see if I have this straight.
> 
> Taking the second point first:
> 
> 1.  CMS says that you only use sha1 with DSA.  However there is
absolutely
> nothing in CMS which states that I could not write a new RFC that uses
> dsa-with-CRC and start having people use this -- correct?  
I disagree. I read the statement of "DSA is always used with SHA"
as prohibiting this. Perhaps we could get Russ to weigh in on what
he intended.

> 2.  Saying that DSA only works with 160-bit hashes is not even a
completely
> correct statement. I could easily write an RFC for dsa-with-MD5 and
have it
> work.  The first step in DSA is to compute the value of the hash mod
Q, this
> means that for dsa-with-sha1, there is a range of hash values that are
> re-mapped onto the low end (i.e. M mod Q = M' for M >= Q).  Note that
the
> MD5 variant does not have this problem and could in one sense said to
be
> stronger.
I think this issue is orthogonal to the main point of my argument.
I'm not prepared to express an opinion on the cryptographic merits
of using other digests with DSA -- in the absence of the substitution
attack.

> 3.  It is true to some extent that you can find some message that
satifies
> these needs for formatting constaints, but that is true for any
> Hash/Signature algorithm pair. 
That's correct. However, as I've been saying, with RSA this does
not permit you to forge signatures for signers who never have
used the compromised algorithm.

> You are now making a statement that
> basically states ECDSA and DSA are bad generic algorithms (as defined
in
> IEEE P1363) since the hash function is not strictly defined.  You are
also
> saying that DSA cannot be reasonably used when an AES hash algorithm
> appears.  It is always going to be a bad signature algorithm as long
as
> there is any possiblity that it may have more than one hash algorithm.
If
> this is true then we might as well go home today and quit.
I am saying precisely that ECDSA and DSA are not generic algorithms.

In any given protocol environment, it must be determined by
standardization which digest is to be used with DSA. That is to say,
that it would probably be fine to say that in (say) XML-DSIG, DSA must
always be used with RIPEMD-160. What is not acceptable is to ever
have any ambiguity about which digest is used.

I don't agree that this is catastrophic however. I don't consider
digest algorithm substitutability that important a property.

> 4.  Putting spacing and other such items is not always going to be as
> effective as what you are making out.  Atleast no in the space we are
> working in.  You also need to take into acount the cannonicalization
that is
> going to occur prior to hashing the text as well.  This means that I
can do
> just about anything I darn well please in one sense, and in another
sense it
> means that I can work againist the type of attack you are suggesting
(i.e.
> remove all extranious white-space, sort order of some items, etc.)
No, this doesn't help. The attacker is in complete control of the
message.
Remember, he's not using the original signer's message at all. He's
only using the original signer's _signature_.

All he has to have is some piece of mutable content in the message
that he wants the victim (the verifier) to accept. Whitespace was
an obvious example. Another obvious example is that many messages
contain arbitrary message-id strings. Since these are opaque,
it's trivial to use them to produce message variations. It should
be obvious that no canonicalization algorithm can eliminate all
such opportunities without also destroying data, except in very
limited problem domains. 

Jim, I'm having trouble understanding what point you're trying to
make. My reasoning is as follows:

1. DSA is vulnerable to the substitution attack I described.
2. RSA is not, at least as long as you use PKCS-1 padding.
3. (1) is a problem.
4. In order to fix (1), DSA must be mandated to work with
SHA-1 and RSA must be used with PKCS-1.

Which, if any of these statements do you disagree with?
Let's try to focus on them.

-Ekr

Received on Thursday, 14 October 1999 18:09:13 UTC