RE: Should alg spec be included in hashed data ?

[caught in spam filter -rrs]

Message-ID: <2F3EC696EAEED311BB2D009027C3F4F408EAF5@vhqpostal.verisign.com>
From: Philip Hallam-Baker <pbaker@verisign.com>
To: "'lcs Mixmaster Remailer'" <mix@anon.lcs.mit.edu>,
        IETF/W3C XML-DSig WG
	 <w3c-ietf-xmldsig@w3.org>
Date: Mon, 15 May 2000 09:20:21 -0700


If we are talking about RSA PKCS#1 then the algorithm is already
included in the signed data.

If we are talking about DSS then the only legal hash is SHA-1

Inclusing the hash algorithm in the hash rather than the signed
data does not actually close the loophole. If junkhash is valid
and completely broken then the alg spec can be modified along with
other data.

That is why the signed data RSA component is the place to place
the alg spec.

		Phill

-----Original Message-----
From: lcs Mixmaster Remailer [mailto:mix@anon.lcs.mit.edu]
Sent: Monday, January 24, 2000 6:00 PM
To: IETF/W3C XML-DSig WG
Subject: [Moderator Action] Should alg spec be included in hashed data?


When computing a signature, does it add security to include the sig and
hash algorithm in the data which is hashed?

Some writers seem to suggest that it does.  For example, in the XML
Digital Signatures working group,
http://www.ietf.org/internet-drafts/draft-ietf-xmldsig-core-03.txt says:
   
   The SignatureMethod is the algorithm used to convert the
canonicalized
   SignedInfo into the SignatureValue. It is a combination of a digest
   algorithm and a key dependent algorithm and possibly other algorithms
   such as padding, for example RSA-SHA1 or HMAC-SHA1. The algorithm
   names are signed to resist attacks based on substituting a weaker
   algorithm.

The idea is that some data is signed, and included in the data is a
description of the signature algorithm itself (public key and hash
algorithm, for PK sigs).  This, it is said, resists attacks based on
substituting a weaker algorithms.

The alternative would be to specify the signature and hash algorithm
*outside* the signed portion.  Of course the verifier needs to know
these algorithms to verify the signature, but the question is whether
it adds security to include this information in what is hashed.

Consider attacks based on substituting weaker algortihms.  For example,
DSS always uses SHA1.  Suppose someone proposes an alternative form of
DSS that uses a different hash but still the same signing algorithm,
DSA.  Suppose further that this hash eventually is found to be weak.
Call it JUNKHASH.

Now, using DSA + JUNKHASH allows one to forge signatures, because it
is easy to create a fake message M_fake which, hashed with JUNKHASH,
creates the same hash as a legitimate message M_real hashed with SHA1.
The attacker takes an existing legitimate DSS signature on M_real,
and substitutes M_fake, saying to use hash algorithm JUNKHASH.  The DSA
signature value is left alone, and the new signature will verify
correctly
since the hash is the same.

This is the basic idea of the attack.  Now, the question is, does
including the algorithm specification (DSS vs DSA+JUNKHASH) in the
material that is hashed make the attack harder to execute?

To some limited extent, the answer is probably yes.  In order to create
M_fake the attacker is going to need some freedom of action.  He will
have
to adjust some parts of the message in order to make the hash come out
to what he wants.  Including the alg spec in the hashed data forces him
to leave that part of the message as "DSA+JUNKHASH".  He can't play with
this, he must leave it that way or else the message can't be verified.
So his freedom of action is reduced somewhat, and he can only make
alterations to other parts of the message in order to achieve his goal.

But really, this is a very minor restriction.  And in fact it could be
met equally well by putting a fixed string in the algorithm
specification
field, like "THIS SPACE INTENTIONALLY LEFT BLANK".  If the spec required
that such a field exist, the attacker's flexibility and freedom to
adjust
the message would be just as constrained as if he were forced to put
his algorithm there.

Including the algorithm spec in the hashed data really does not play
a significant role in adding security.  In particular it does not in
any way force the attacker to use the same algorithm specification, or
prevent him from changing it to the specification of the weak algorithm.
And given that the algorithm is weak, making him include the algorithm
spec in the hash is not likely to add significantly to the difficulty
of the attack.

As a general principal, it does not strengthen protocols against
algorithm
substitution attacks to include the algorithm specification as an INPUT
to the potentially weakened stage.  It must go outside that channel in
order to add security.  We see this in PKCS-1, where the hash algorithm
spec is input to the RSA signature stage.  It does not go through the
hash algorithm itself; the designers presumably recognized that that
would be weak.  It bypasses the hash stage, and feeds directly into the
signature stage.  This adds strength.  The present proposal, although
it bears some resemblance to that, fails because it sends the alg spec
through the very stage it purports to protect.

Of course, it may turn out that requiring the algorithm spec in that
place
does happen to make the attacker's job more difficult, due to the
specific
nature of the weakness he is exploiting.  But on the other hand, it
could
conceivably make his job easier, if the exploit happened to work well
with the particular encoding of the alg spec in the specified location.

Overall, it doesn't seem appropriate to conclude that requiring the
algorithm specification to be included in the hashed data will add
resistance to attacks based on substituting a weaker algorithm.  In the
interests of including only cryptographically justified security
features,
it would be more appropriate to move the algorithm specification out of
the hashed data region.