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

[Eric Norman <ejnorman@xxxxxxxxxxxxx>]

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