Subject: Protect Algorithm identifiers?

From: "Jim Schaad" <[email-masked]>
Date: Mon, 17 Apr 2006 20:38:19 -0700

In the process of reviewing documents dealing with multiple signature
processing, I suddenly realized that we currently do not have any attribute
which lets us verify that the correct digest and signature algorithms have
been used in verifying a SignerInfo.  The question is do we need to do this?

More details on what I mean:

When you create a signer info you:

1.  Hash the body of the message, place the digest value as a signed
attribute and the digest algorithm into the SignerInfo structure in an
unprotected location.

2.  Create the sequence of signed attributes, hash the value, create a
signature value using your private key and place the signature algorithm and
the signature in unprotected locations.

The signature does not need any additional protection, however one could
change the digest algorithms being used in both the signature and body
digest locations without a verifier being able to know that it has happened.

The attack I envision would be to find a body that has a digest of the same
length, but uses a different algorithm and update the SignerInfo structure
with the new digest algorithm data and the body with the updated body.  This
would currently be undetectable by a verifier.

Jim

---

From: "Nick Pope" <[email-masked]>
Date: Tue, 18 Apr 2006 10:48:53 +0100

Jim,

If the verifier is prepared to accept a weak hash algorithm whereby a new
body value can be created with the same hash value, how can the algorithm
identifier be protected ?

Nick Pope

> -----Original Message-----
> From: [email-masked]
> [mailto:[email-masked]]On Behalf Of Jim Schaad
> Sent: 18 April 2006 04:38
> To: [email-masked]
> Subject: Protect Algorithm identifiers?
>
>
>

---

From: Alfonso De Gregorio <[email-masked]>
Date: Tue, 18 Apr 2006 17:42:12 +0200

Jim,

Let H be the set of message digest algorithms supported by the standard
(e.g., SHA-1 and MD5).

If I understand correctly your point, an adversary would be able to mount
the attack whenever _any_ hash function in H is found to be not resistant
against preimage attacks.

Preimage attacks against currently standardized message digest
algorithms would represent a significant cryptanalytic advance.

However, giving the adversaries the freedom to tamper with algorithm
identifiers means increasing their chance of succeeding in attacks
intended to compromise the integrity of the data.

Preimage resistance of all the functions in H at any given moment in
time, is a stronger requirement than preimage resistance for a given
hash function.

In fact, the adversary here is challenged to find any preimage x' such
that h2(x') = y when given any y = h1(x) (h1 in H) and any h2 in H with
h2 != h1.

Hence, I think we should counter this attack by adding integrity to the
selected digest suite. We should look at CMS envelopes as datagrams of
a store-and-forward protocol.

Phasing out weak algorithms may not always be a satisfactory approach,
since legacy systems can be slow to modify.

Workaround:
More resiliency to advances in cryptanalysis of hash functions can be
provided also using different message digest algorithms to compute
multiple digest values of data and requiring the verifier to check
the integrity of the data according to each specified digest algorithm
- while requiring the use of at least two different algorithms.

Alfonso

---

From: "Jim Schaad" <[email-masked]>
Date: Tue, 18 Apr 2006 08:43:48 -0700

Nick,

The case that worries me to some extent is the upcomming algorithms with
parameters.  It might be that creating collisions is simplier when you can
play with the parameters than with the body.  This depends in part on how
the keying of the hash function is done.

Jim

> [mailto:[email-masked]] On Behalf Of Nick Pope
> Sent: Tuesday, April 18, 2006 2:49 AM
> To: [email-masked]; [email-masked]
> Subject: RE: Protect Algorithm identifiers?
> 
> 
> Jim,
> 
> If the verifier is prepared to accept a weak hash algorithm 
> whereby a new body value can be created with the same hash 
> value, how can the algorithm identifier be protected ?
> 
> Nick Pope
> 
> > processing, I suddenly realized that we currently do not have any 
> > attribute which lets us verify that the correct digest and 
> signature 
> > algorithms have been used in verifying a SignerInfo.  The 
> question is 
> > do we need to do this?
> >
> > signature value using your private key and place the signature 
> > algorithm and the signature in unprotected locations.
> >
> > The signature does not need any additional protection, however one 
> > could change the digest algorithms being used in both the signature 
> > and body digest locations without a verifier being able to 
> know that 
> > it has happened.
> >
> >
> > The attack I envision would be to find a body that has a 
> digest of the 
> > same length, but uses a different algorithm and update the 
> SignerInfo 
> > structure with the new digest algorithm data and the body with the 
> > updated body.  This would currently be undetectable by a verifier.
> >
> > Jim
> >
> >
> >
> 
> 
> 
> 
>