Subject: Re: [saag] Another bad day at the hash function factory

From: Eric Norman <[email-masked]>
Date: Wed, 02 Mar 2005 19:49:03 -0600

Here's my take.

Santosh seems to have asked the key question, "what is the threat?"
I think Jean-Marc has come close to answering it.

First of all, it doesn't have anything to do with serial numbers or 
anything else
in certificates other than public keys.  The threat is against the 
non-repudiation
support of PKI.  Here's how I would describe a possible attack.

I generate two different bit strings that will cause an MD5 collision.

I set my computers to work for a few hours to turn those bit strings 
into public
keys that will also collide, and I know the associated private keys.  
Call these
keypair A and keypair B.  This is what's detailed in the paper.

I send public key A off to a certification authority, provide proof of 
possession
(private key A), whatever identity information is appropriate, and 
receive a
certificate from the CA.

I replace the public key of that certificate with public key B to get 
certificate B.
Everything in certificate B is identical to what's in certificate A 
except for the
public key part.  And the signature by the CA in certificate B still 
verifies!

I now sign something using private key B and send along certificate B 
for
purposes of verification.

The relying party uses public key B to verify my signature, the relying 
party
relies on that and does whatever.  The relying party can even record the
entire certificate (certificate B) as evidence to be used in case of 
repudiation.

I come along later and claim that I didn't sign that and therefore I 
don't owe
the relying party anything, or whatever.

What evidence does the relying party have?  He has a recording of a 
public
key (B), mathematical evidence that someone knows the associated private
key (B), and a claim that I control private key B.  But he doesn't have 
proof of
that binding between claim of identity and keypair; he has to get such 
evidence
from the CA that signed the certificate.  So he asks the CA to testify.

What evidence does the CA have?  The CA has evidence that keypair A
belongs to me, but the CA has never seen public key B and has no 
evidence
about it whatsoever.

The only place evidence about keypair B exists is on my equipment and 
since
I'm a very thorough miscreant, I have destroyed it just in case someone 
comes
along with a search warrant.

Eric Norman
University of WIsconsin -- DoIT

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 03 Mar 2005 06:23:53 -0800

Eric Norman <[email-masked]> writes:
> The relying party uses public key B to verify my signature, the
> relying party
> key (B), and a claim that I control private key B.  But he doesn't
> have proof of
> I'm a very thorough miscreant, I have destroyed it just in case
> someone comes

First, let me say that I'm extremely skeptical of this entire
line of argument and doubt that it would convince a judge. 

That said, even if I thought you could make a convincing argument
against non-repudiation based on hash collisions I don't think this
example shows what you think it shows:

We have available:

* A certificate containing key A (retained by the CA)
* A certificate containing key B (retained by the relying party)

The CA can demonstrate (to the extent that they can demonstrate
this at all) that the attesting party obtained certificate A.

It's also easy to verify that certificates A and B have the
same interior message digest value, so it's clear that something
is fishy. 

However, it's easy to demonstrate that the cert holder is the one who
is cheating, because they are the only one who could have generated
the A,B pair. By assumption, collision attacks are possible but 2nd
preimages are not, and its undisputed that the cert holder generated
key A, therefore he must ALSO have generated key B.

It's worth mentioning that in current practice, facsimile copies of
holographic signatures are considered legally binding even though they
have essentially no binding to the underlying document and are trivial
to forge using photoshop. It's the intention that counts, not proof
that the signature occurred. Note also that when you sign a paper
document, nothing stops you from making some signature mark that
doesn't look at all like your real signature. I assure you that this
doesn't mean that you're not bound to the contract.
 
-Ekr

---

From: Eric Norman <[email-masked]>
Date: Thu, 03 Mar 2005 14:21:09 -0600

> line of argument and doubt that it would convince a judge.

I am also skeptical, now.

> same interior message digest value, so it's clear that something

I didn't think of that.  That is indeed pretty substantial evidence, 
isn't it?
In this example, there's even more evidence of fishyness in the public
keys themselves.  Save for a few bits here and there, they are virtually
identical.

Nevertheless, one of the points to remember is that all this 
non-repudiation
stuff is eventually going to come down to what it will take to convince 
a
judge.  What that means to me is that it's important to think about what
evidence will be available when that time comes, how the parties should
preserve and protect that evidence, and so forth.

Now, wouldn't it be neat to turn on our TV sets some day in the future 
and
hear Judge Judy say, "judgment for the plaintiff; the Hamming distance 
is
too small"?

Eric Norman
University of Wisconsin -- DoIT

---

From: Dr Stephen Henson <[email-masked]>
Date: Thu, 03 Mar 2005 21:22:57 +0000

> key A, therefore he must ALSO have generated key B.

I also notice that the examples don't include the subject public key ID 
extension. If the CA used an appropriate recommended algorithm to 
generate SKID then it could demonstrate that the certificate containing 
A contained a consistent SKID whereas the one containing B did not.

Steve.
-- 
Dr Stephen N. Henson.
Core developer of the   OpenSSL project: http://www.openssl.org/
Freelance consultant see: http://www.drh-consultancy.co.uk/
Email: [email-masked], PGP key: via homepage.

---

From: Jean-Marc Desperrier <[email-masked]>
Date: Fri, 04 Mar 2005 08:51:46 +0100

>> * A certificate containing key B (retained by the relying party)
As I said initially I think it may happen, thought not very likely, that 
the relying party think it's safe enough to keep only the identification 
of the certificat for key B, and not the whole certificate.

In that case, it would very sensible to the attack.

> I also notice that the examples don't include the subject public key 
> ID extension. If the CA used an appropriate recommended algorithm to 
> generate SKID then it could demonstrate that the certificate 
> containing A contained a consistent SKID whereas the one containing B 
> did not.

At the time being, it's more strongly recommended to use the SKI 
extension for CA certificates than it is for end entity certificate.

---

From: Eric Rescorla <[email-masked]>
Date: Fri, 04 Mar 2005 06:57:39 -0800

Jean-Marc Desperrier <[email-masked]> writes:

> As I said initially I think it may happen, thought not very likely,
> that the relying party think it's safe enough to keep only the
> identification of the certificat for key B, and not the whole
> certificate.
>

Well, we know now that people ought not to do that.

-Ekr