W3C home > Mailing lists > Public > w3c-ietf-xmldsig@w3.org > October to December 1999

Re: Parameters and Algorithms.

From: Eric Rescorla <ekr@rtfm.com>
Date: Thu, 14 Oct 1999 13:57:22 -0700
Message-Id: <199910142057.NAA52077@romeo.rtfm.com>
To: "Jim Schaad (Exchange)" <jimsch@EXCHANGE.MICROSOFT.com>
cc: "W3c-Ietf-Xmldsig (E-mail)" <w3c-ietf-xmldsig@w3.org>
> 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 16:57:32 GMT

This archive was generated by hypermail 2.2.0 + w3c-0.29 : Thursday, 13 January 2005 12:10:08 GMT