Colliding X.509 Certificates

[Weger, B.M.M. de]

Hi Joerg,

> My concern is not MD5, its SHA-1. I don't see that we can get rid of 
> SHA-1 in certificates in the next 5 years:
> * None of the alternatives is widely implemented today.
> * For controlled environments like in-house applications you might be 
> able to switch earlier (0-2 years).
> * In open environments like inter company S/MIME or public facing SSL 
> servers it will take years before you can assume that people 
> are able to 
> verify non SHA-1 certs.
> * For CA certificates you'll have to add more years (not to 
> speak about 
>   those CA certs with notAfter=2038).
>
>  From this perspective it makes sense to think about 
> operating a CA with 
> a broken hash function, I believe.
> * Technically SHA-1 is broken today.
> * I don't fear that anybody might attack my CA based on the 
> attack known 
> today.
> * But given the progress in the last year I personally expect the 
> attacks on SHA-1 to get more practical.

It makes sense to do a risk analysis, based on a.o.
* how critical is the particular application to the business
* what threats are there (who might try something bad)
* what's the user community (in-house or the entire world or
  something in between)
and then accept a certain residual risk of continuing the use of
'broken' hash functions for some more time. 

At the same time it is wise to start deploying better hash functions. 
I hope the Microsofts and Suns and <name your favourite software
factory> of this world are working on this right now. It's clear that 
this is going to take a long time and cost a lot of money. We're very 
lucky that the present attacks are still to a large extent theoretical 
in nature, and do not (yet) lead to realistic attack scenarios (at 
least we couldn't think of one, and we haven't seen anybody else 
coming up with one).

The main lesson to be learnt here is that we have made our systems 
too dependent on a few cryptographic primitives only; much more
flexibility is needed. One of these days some smart person may come 
up with a real attack on <name your favorite cryptographic primitive>,
then you cannot afford two years to change your systems.

So I still think that the message we should send into the world is
to phase out MD5 now, and SHA-1 a.s.a.p. (NIST says: by 2010, that 
sounds very long to me). If you cannot do that for practical reasons, 
then that's your risk. When you accept that risk, that's fine with me.
 
Apart from that I've never understood why there are CA certificates 
with such incredibly long lifetimes. That's simply asking for trouble.

> > A relying party cannot find out from the certificate alone whether
> > it has a "twin sister" or not. The fact that there is a 
> random-looking
> > serial number doesn't help you there.
> That is true, and its certainly not nice. But I think the 
> real concern 
> of the relying party is not specifically about certificates with the 
> same hash, its about
> * the correctness of the contents (name of private key holder 
> etc.) and
> * the existance of other certificates issued to same key but 
> different 
> name, which might be used to repudiate signatures, e.g.
> 
> The relying party always needs to trust the CA on those two 
> properties, 
> as the CA can easily issue certs with incorrect conents, it 
> doesn't need 
> hash collisions for that.
> 
> My question is: Can a CA prevent "twin sisters" from coming into 
> existance by using my proposed procedure?

With current knowledge the answer is: yes. Randomized serial numbers 
will be sufficient. And indeed: a CA doesn't need hash collisions
to do real damage. 

Grtz,
Benne

========================================= 
Technische Universiteit Eindhoven 
Coding & Crypto Groep 
Faculteit Wiskunde en Informatica 
Den Dolech 2 
Postbus 513 
5600 MB Eindhoven 
kamer HG 9.84 
www: http://www.win.tue.nl/~bdeweger 
========================================= 
 

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com