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

[Eric Rescorla <ekr@xxxxxxxx>]

Eric Norman <ejnorman@xxxxxxxxxxxxx> writes:
> 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.

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