Creating a rogue CA certificate with MD5 hash collisions
phreedom.org
phreedom.org
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.
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.
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.
"Yes, Trust In The PKI Is Broken" http://www.informationweek.com/blog/main/archives/2008/12/ye...
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...
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
"RapidSSL's total lack of acknowledgement or response to this problem on their front page"
See:
http://www.gridvm.org/rogue-root-cas-because-of-md5-collisio...
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.
Anyhow, the program you want to check this out is Firefox itself: Preferences -> Advanced -> Encryption -> View Certificates -> Authorities -> "View" -> Details.
I removed the list from that link, anyhow. I didn't understand the 'sign predictably' part you pointed out, much appreciated.
I have root certificates in my browser that are valid from 1998 to 2018. It's not so easy to verify that this attack didn't already happen 5 or even 10 years ago.
Personally I think it's extremely unlikely, especially since the chosen prefix collision attack they used has only been public for less than two years, but how could you know for sure?
We're also focusing on the algorithm, but not really accounting for the fact that simply owning a cluster of PS3s doesn't give you the optimized math code that generates the birthday bits during the weekend window. That code is itself presumably harder to write than any zero-day exploit.
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.
Most customers will shrug their shoulders and try another site that doesn't throw a scary warning. Normal people don't report bugs.
> customers complaining that you're a fraud
You're right, this is a real problem. But blocking certificates outright isn't less of a problem.
Unpleasant errors scares away buyers. That is, Error + Credit Card = No Purchase
> Not revoking certificates will negate all the security of SSL.
Not true. The encryption part of the certificate is still there. However, the added assurance that you're really on the site you think is compromised.
But has the assurance part of SSL certificates actually reduced phishing? Stupid people will still put all their money in BankOfShmamerica.com as long as it looks sort of like the BankOfAmerica.com site and doesn't throw any errors.
So, is it 100% secure? No. Is there still a reasonably high barrier of entry to getting your CC number/bank login? Yes.
That's like saying if you were using one of the weak Debian ssh keys, you might as well be using telnet. It's simply not true. The effort to steal your info is at least an order of magnitude (if not more) higher, even with weak ssh keys. The same situation applies here.
The packets leaving your laptop are protected from being eavesdropped by third parties, but the party you're sending your banking password to is some asshole who now apparently runs a CA, and just issued a certificate telling your web browser he's your bank.
Under that scenario, then you've already lost your data (although I'd still hold it's better to have your CC stolen by one person, rather than two), so yes, that's bad. However, that's not the scenario that I've been discussing here. This thread came under the debate about the risks and issues with revoking all those certs immediately, versus not.
If you're saying, "we shouldn't do anything rash because certificates don't break encryption, only authentication", then you are perpetuating a really dangerous myth about SSL security.
I didn't gather a lot of information from the link you posted, but this doc on the SSL handshake ( http://docs.sun.com/source/816-6156-10/contents.htm ) to my eyes doesn't show why you wouldn't be able to trust your session keys.
Could you explain how session keys can be compromised?
In this case I could be falling for a fake site and sending them my CC data, instead of Amazon, however I'm still protected from my CC being stolen by guy who setup the coffee house Wifi router.
You cannot secure a conversation between two unrelated parties over the Internet without some form of authentication, to "break the tie" if the attacker presents their own keys/certificates.
I have great respect for your security knowledge, but your consistent black & white views and your assumption that anyone who doesn't share them doesn't understand the technology is frustrating.
If I own a coffee house router, or if I am simply sniffing un-encrypted wifi packets out of the air in the coffee house, logging traffic is extremely simple. I can log all traffic, or just traffic to http pages with names like login, or checkout, and I can do that very very very easily. It will log tons data automatically, and let me comb through it later. As a newbie to linux I could do that. The barrier preventing me from stealing the info you send over http is VERY low, and virtually anyone can do it.
The attack you describe is much more difficult to execute. The number of people who could make that attack is several orders of magnitude smaller than the previous attack. Hence my risk is several orders of magnitude smaller.
You're arguing that because skilled safe-crackers can open a safe, people should just leave their valuables on their lawn chairs out front. Security isn't black and white. Nothing will be 100% secure from every type of attack. It's a matter of raising the barrier of entry for an attack high enough that it's generally not worth the trouble.
There is no such thing as a purely-passive attacker. In reality, no serious attacker is even going to bother sniffing your traffic; they're going to redirect it.
We're not talking about the scenario where a very smart attacker is targeting me with this security hole. We're talking about the impact of not revoking the certificates in question. At which point there is a very very small possibility that I will be targeted by an active attacker with the know-how to exploit this issue. The rest of the time SSL will continue to work as designed and will protect me from wifi snoopers and suspect routers.
There absolutely are passive attackers. There are people running open wifi points that log http form submissions with a "password" field, and then try the same username/password on a few major sites (ebay, amazon, etrade, gmail, BoA, etc...) automatically (working on the assumption that people use the same login/password on the many non-ssl authed non-important sites as they do for their important accounts). Successful login data is marked. I have met people running these. It costs nothing, is fully automated, and has very little risk.
They may not be "serious attackers", but the likelihood of one of them getting your mom's eTrade info is much higher than an active attacker targeting your mom.
You're not interested in the risk of or protection against provided by SSL encryption for a simple and probably relatively common passive attack? Because those people are lazy or dumb, we can write them off entirely and say SSL provides no security if there's a potential CA related exploit? I get that it's not as interesting a situation to think about, but I think that logically you can prove that SSL provides an increased security over http to the end user, even if some certs could be compromised.
" (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).
(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. "
So you might be tricked into setting up encrypted communication to one of the (small) N groups that have the knowledge/budget to do a Sotirov attack, but at least you still won't have identity details hijacked by (large) M others, because even broken cert-checking protects against them.
Exactly! I'm sorry I wasn't communicating clearly enough.
http://bits.blogs.nytimes.com/2008/12/30/outdated-security-s...
(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.