Creating a rogue CA certificate with MD5 hash collisions(phreedom.org)
phreedom.org
Creating a rogue CA certificate with MD5 hash collisions
http://www.phreedom.org/research/rogue-ca/
9 comments
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.
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.
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.
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.
There's some sensationalist stuff popping up:
"Yes, Trust In The PKI Is Broken" http://www.informationweek.com/blog/main/archives/2008/12/ye...
"Yes, Trust In The PKI Is Broken" http://www.informationweek.com/blog/main/archives/2008/12/ye...
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...
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...
RapidSSL's total lack of acknowledgement or response to this problem on their front page is not a huge confidence builder for me.
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
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
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.
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
"RapidSSL's total lack of acknowledgement or response to this problem on their front page"
See:
http://news.ycombinator.com/item?id=414836
I wonder what their $10,000 warranty applies to, I can't find any details on the site.
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.
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...
http://www.gridvm.org/rogue-root-cas-because-of-md5-collisio...
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.
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.
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.
Then nothing in that list is relevant, either.
Anyhow, the program you want to check this out is Firefox itself: Preferences -> Advanced -> Encryption -> View Certificates -> Authorities -> "View" -> Details.
Anyhow, the program you want to check this out is Firefox itself: Preferences -> Advanced -> Encryption -> View Certificates -> Authorities -> "View" -> Details.
There were too many to check out manually that way, so I exported as pem and extracted sigalg.
I removed the list from that link, anyhow. I didn't understand the 'sign predictably' part you pointed out, much appreciated.
I removed the list from that link, anyhow. I didn't understand the 'sign predictably' part you pointed out, much appreciated.
[deleted]
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?
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.
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.
Yes. Moreover, this is cited in the author's paper as a countermeasure against the attack. The attack required them to make a series of requests to probe and then prime the serial number to the value they picked for their "colliding machine", which takes days to run.
What about prior discovery that occurred before all the other certificate authorities began to harden against theoretical attacks like this? MD5 based signatures and monotonically increasing certificate serial numbers used to be the rule, not the exception.
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?
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?
They're also using an unpublished variant of the chosen-prefix attack, which presumably is what allows them to win the weekend race to generate a collision with a predicted timestamp/serial pair.
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.
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.
Browser makers should ban any root CA using MD5 very, very soon.
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.
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.
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?
> Customers complaining that your SSL certificate is invalid
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.
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.
I don't understand your logic. Revoking certificates will cause unpleasant SSL errors. Not revoking certificates will negate all the security of SSL. How could those two problems be comparable?
> Revoking certificates will cause unpleasant SSL errors.
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.
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.
If you think "the encryption part of the certificate" is still there, you don't really understand how SSL works. Without a secure certificate, you can't trust your SSL session keys. See:
http://news.ycombinator.com/item?id=277284
http://news.ycombinator.com/item?id=277284
"the encryption part of the certificate" is still there as far as the wifi packets leaving your laptop are concerned, and as far as the poorly/maliciously configured linux router in the backroom of the coffee shop are concerned.
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.
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.
tptakec is 100% correct, but I like to explain stuff to people:
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.
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.
The scenario under discussion (at least I as understood it from this particular thread of comments) is if we don't revoke all the compromisable certs. The scenario is NOT that I am connected to an attacker who has successfully used this attack against me.
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.
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 to mitigate an attack that requires Arjen Lenstra and a specially tuned cluster of PS3s to accomplish", then that makes sense.
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.
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.
You made the same point a few minutes ago, and I replied to it; long story short, you're not correct.
You're right - I've never implemented SSL, and as such don't know the minutia of the algorithm.
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?
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?
It doesn't make a difference whether the communication is encrypted if you can't verify with whom you are communicating.
That's decidedly untrue.
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.
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.
Unfortunately, you too are misunderstanding how SSL works. If you own the coffee house WiFi router, you can decrypt any SSL session that traverses your network that doesn't use valid certificates. You simply need to inject your own certificate into the SSL session and fix a session key.
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.
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.
Actually, I'm not.
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.
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.
Out of all the hypothetical scenarios you could have chosen, you picked one where it is not only possible to intercept your encrypted data but really quite obvious how to do it.
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.
A sweeping revocation wouldn't work, as you can only revoke certifcates that have not been tampered with. You must issue a SHA-1 certificate to everyone and then change every piece of software that uses certificates not to trust certificates with an MD5 hash in the trust chain. If someone else has successfully performed this attack, he might posses a CA certificate that is valid until 2038 and you have no way to know about it until he uses it against you.
I'd suggest browsers, via an update, stop accepting certificates using known vulnerable hashing routines.
And root CA's should stop using MD5 even sooner.
New York Times reporting on this:
http://bits.blogs.nytimes.com/2008/12/30/outdated-security-s...
http://bits.blogs.nytimes.com/2008/12/30/outdated-security-s...
Ben Laurie is (un)impressed:
http://www.links.org/?p=477
http://www.links.org/?p=477
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.
(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.
[deleted]
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.