Creating a rogue CA certificate with MD5 hash collisions

http://www.phreedom.org/research/rogue-ca/

by brl • 18 years ago

107 55 18 years ago

phreedom.org

ambition• 18 years ago

Browser makers should ban any root CA using MD5 very, very soon.

geekamongus• 18 years ago

And root CA's should stop using MD5 even sooner.

wyday4• 18 years ago

And all the customers that bought certificates from these CA's? Let 'em hang?

Who cares that these customers business reputations depends on the SSL certificates validity.

I agree with you that certificates made with the MD5 hash should be phased out gradually by the CAs, but you can't just do a sweeping revocation without ruining businesses.

cperciva• 18 years ago

Which would you prefer to have: Customers complaining that your SSL certificate is invalid until you spend the a few minutes to get an updated certificate; or customers complaining that you're a fraud because they gave you (well, really just someone pretending to be you) money and you haven't delivered the product/service they ordered?

stcredzero• 18 years ago

The customers that bought certificates should be getting an SHA1 certificate from the CAs. Why shouldn't there be a sweeping revocation? Any web apps that are dependent on rapid response to problems like this will be able to respond quickly. If things are handled properly, we should see abandonment of MD5 certs in a matter of days. Taking more time just gives time to the exploiters.

randomwalker• 18 years ago

First of all, congrats to the people who pulled this off. A couple of the authors are friends of mine, and I heard a few weeks ago that they were going to announce something major today, but this is still bigger than I expected.

In a way, I'm very gratified to see this. Let me explain. I used to do hash function research a couple of years ago before I shifted to other things. I've also worked in a team building a security product. When I suggested that they should stop using MD5 to publish hashes of worm binaries, they weren't sure why I wanted them to do that. This was well after MD5 collisions had been widely publicized. I brought it up in a meeting, and they said that other teams also used MD5s, so it would be confusing for users to have two different formats, and so they weren't going to switch "until everyone else did." I was very surprised, but dropped it because I figured I was getting a taste of how things worked in the real world.

In my life as an academic, the one thing I've repeatedly observed is that the disconnect between people doing research and people directly applying that research is huge. Seriously, what does one have to do? It's not like we're trying to educate end-users here -- root CA's are in the business of staying on top of this stuff. Sheesh.

Edit. The talk video is available at http://tinyurl.com/a9754t but it's kinda slow right now.

tlrobinson• 18 years ago

Video available via BitTorrent as well. Much faster: http://thepiratebay.org/torrent/4611622/25c3_Tag4-Saal1-Slot...

It's quite impressive due to the timing involved. It takes approx 2 days to compute the collision. They need to pick an exact time (to the second) that they will request the cert after the collision is computed, and the exact serial number that the CA will issue. They can monitor and increment the serial number as the target time approaches by buying more certs.

cscott3• 18 years ago

If all 6 impacted CAs stop signing MD5 signed certs today and no new CAs started, is the risk reduced to the possibility of prior discovery?

brl3• 18 years ago

Yes, but prior discovery is a real problem. If Jake and Alex hadn't told us that they had successfully pulled this off we would never have otherwise known. In that case they would be in silent and permanent possession of something like the master keys to the whole SSL certificate system.

cscott3• 18 years ago

Agreed. However, wouldn't an operational review of certificate issuance activity of the impacted CAs provide another level of assurance that the researchers were the only ones who successfully exploited this vulnerability? I would imagine their activity (when inspected as a series of requests) would look rather anomalous.

timf5• 18 years ago

I wrote a program to list out relevant entries from my Firefox 3.0.4 trusted CAs, the list is here:

http://www.gridvm.org/rogue-root-cas-because-of-md5-collisio...

tptacek17• 18 years ago

Am I reading your output correctly, or are you saying that Verisign US is vulnerable? Or is this just humor?

The reality seems to be that only RapidSSL and FreeSSL are practically vulnerable; of the small subset of CAs that will sign with MD5, they're the two that will sign predictably; the others randomize the serial number field.

Moreover, this is an exceedingly hard vulnerability to exploit. Sotirov's team not only had a cluster of PS3s running custom code optimized to quickly find MD5 collisions, but were also working with a new academic result on collision-finding that has not yet been published.

timf5• 18 years ago

OK, if you're right about the serial number part that is great. All I did was export the CA certs in my Firefox install and then ran a quick program on all the files to extract the signature algorithm.

tptacek17• 18 years ago

Capsule summary:

They created an MD5 collision to get RapidSSL to sign a certificate whose signature also verifies a CA=YES certificate. In other words, they used an MD5 collision to synthesize a new CA. Your browser will trust an Amazon.com certificate signed by their rogue CA.

They were able to do this because:

(1) RapidSSL, FreeSSL, TC TrustCenter, RSA, Thawte, and Verisign Japan will sign certs with MD5.

(2) They worked with Arjen Lenstra and Marc Stevens and obtained a method to generate pairs of plaintexts with arbitrary chosen prefixes within 72 hours on a cluster of 200 PS3 game consoles.

(3) Even though the prefix of a signed certificate contains fields the attacker doesn't control --- the serial number and validity period (which is effectively a timestamp of when the cert was signed at the CA), RapidSSL fucked up and used a monotonically increasing serial number (!), so they could predict the CA's fields and build them into their collision.

(4) Even though generating the MD5 collision requires the certificates to include a large amount of random-looking data, there's a place in the "real" certificate and a different place in the "rogue" certificate to stash that data: the collision material in the "real" cert is hidden the the RSA modulus, which is random anyways, and the corresponding location in the "rogue" certificate is masked as a "Netscape Comment Field" (a "tumor") which browsers ignore.

All 4 of these things had to happen at the same time to make this doable:

(1) There's no practical break for SHA-1, which is what most CAs use.

(2) You have to be able to generate the collision within a short window of time to get the resulting product signed properly by the CA, so you need the new academic result (and the PS3s).

(3) If RapidSSL and FreeSSL had simply randomized the serial number, like everyone else, there'd be no way to predict the signed product of the request, and your collision wouldn't mean anything.

(4) You obviously have to play ASN.1 games to make the random collision fit into a semantically valid certificate.

They spent $700 generating certificate requests to pull this off; because RapidSSL allows requestors to reissue certs 20 times, each attempt costs $2.50.

You want to read:

http://www.win.tue.nl/hashclash/rogue-ca/

In particular, section 5.3.4 has the clearest description of MD5 collisions I've ever read, with a really excellent series of graphics.

IS THIS THE WORST THING THAT HAS EVER HAPPENED TO THE INTERNET EVER EVER?

No. Two years ago, Daniel Bleichenbacher demonstrated a pencil and paper attack on the RSA validation procedure used by OpenSSL. That attack required a mass software update. This one will hopefully just put RapidSSL out of business.

gojomo2• 18 years ago

This one will hopefully just put RapidSSL out of business.

I did not realize this until just now, but RapidSSL is owned by GeoTrust, which is owned by Verisign... so RapidSSL may not disappear in a puff of logic as one might hope.

Here's Verisign's report that they've discontinued MD5 and are offering free replacement certificates:

https://blogs.verisign.com/ssl-blog/2008/12/on_md5_vulnerabi...

JoshBourdaine• 18 years ago

There's some sensationalist stuff popping up:

"Yes, Trust In The PKI Is Broken" http://www.informationweek.com/blog/main/archives/2008/12/ye...

davidw• 18 years ago

Ben Laurie is (un)impressed:

http://www.links.org/?p=477

tptacek17• 18 years ago

Ben Laurie is demagoguing, poorly:

(1) The attack is extremely difficult to pull off.

(2) Critical details required to carry it out --- an academic breakthrough in MD5 collision-finding --- were actually withheld, meaning that no "zero-day" occurred.

(3) The "fix" for this attack is for RapidSSL to randomize serials and stop using MD5, both of which will happen; if you believe certificates from before today are vulnerable, that's an even stronger argument for publishing.

(4) The product of the attack was deliberately backdated to 2004 to prevent real-world exploitation.

(5) I may be wrong about this, but --- Ben Laurie himself helped zero-day the RSA signature validation flaw two years ago.

(6) Laurie is calling Arjen Lenstra a moron.

tptacek17• 18 years ago

RapidSSL's total lack of acknowledgement or response to this problem on their front page is not a huge confidence builder for me.

timf5• 18 years ago

I wonder what their $10,000 warranty applies to, I can't find any details on the site.

tptacek17• 18 years ago

The person who manages to get their "Live Chat" people to respond to questions about this (perhaps by asking as a "prospective customer concerned about stories in the news") is going win a Hacker News karma bonanza.

cscott3• 18 years ago

RapidSSL is owned by GeoTrust, which is owned by Verisign.

You can read all about GeoTrust's certificate practices here: http://www.geotrust.com/resources/cps/pdfs/GeoTrustCPS-Versi...

The results of their KPMG audit here: https://cert.webtrust.org/SealFile?seal=650&file=pdf

And their entry into Mozilla here: https://bugzilla.mozilla.org/show_bug.cgi?id=409236

tptacek17• 18 years ago

Of course, all the KPMG audit really says is "GeoTrust has a policy about checking the documentation of people who request certificates", and there's part of the problem: there's no way for a CA to make an attestation that they've implemented the technology competantly, because no third party will certify that attestation.

timf5• 18 years ago

If you just read:

"RapidSSL's total lack of acknowledgement or response to this problem on their front page"

See:

http://news.ycombinator.com/item?id=414836

tokenadult• 18 years ago

New York Times reporting on this:

http://bits.blogs.nytimes.com/2008/12/30/outdated-security-s...

Creating a rogue CA certificate with MD5 hash collisions

Related Stories