A team of security researchers and academics has broken a core piece of internet technology. They made their work public at the 25th Chaos Communication Congress in Berlin today. The team was able to create a rogue certificate authority and use it to issue valid SSL certificates for any site they want. The user would have no indication that their HTTPS connection was being monitored/modified.
This attack is possible because of a flaw in MD5. MD5 is a hashing algorithm; each unique file has a unique hash. In 2004, a team of Chinese researchers demonstrated creating two different files that had the same MD5 hash. In 2007, another team showed theoretical attacks that took advantage of these collisions. The team focused on SSL certificates signed with MD5 for their exploit.
The first step was doing some broad scans to see what certificate authorities (CA) were issuing MD5 signed certs. They collected 30K certs from Firefox trusted CAs. 9K of them were MD5 signed. 97% of those came from RapidSSL.
Having selected their target, the team needed to generate their rogue certificate to transfer the signature to. They employed the processing power of 200 Playstation 3s to get the job done. For this task, it’s the equivalent of 8000 standard CPU cores or $20K of Amazon EC2 time. The task takes ~1-2 days to calculate. The tricky part was knowing the content of the certificate that would be issued by RapidSSL. They needed to predict two variables: the serial number and the timestamp. RapidSSL’s serial numbers were all sequential. From testing, they knew that RapidSSL would always sign six seconds after the order was acknowledged. Knowing these two facts they were able to generate a certificate in advance and then purchase the exact certificate they wanted. They’d purchase certificates to advance the serial number and then buy on the exact time they calculated.
The cert was issued to their particular domain, but since they controlled the content, they changed the flags to make themselves an intermediate certificate authority. That gave them authority to issue any certificate they wanted. All of these ‘valid’ certs were signed using SHA-1.
If you set your clock back to before August 2004, you can try out their live demo site. This time is just a security measure for the example and this would work identically with a certificate that hasn’t expired. There’s a project site and a much more detailed writeup than this.
To fix this vulnerability, all CAs are now using SHA-1 for signing and Microsoft and Firefox will be blacklisting the team’s rogue CA in their browser products.
Well lets hope bad people cannot afford 200 PS3’s.
How many Xboxs would this take?
http://www.ps3focus.com/archives/40
200 PS3’s would have produced more productive work.
If they had just folded for Stanford.
http://folding.stanford.edu/
Expensive way to just say: “I told you so”.
If MD5 is so broken, why use it. Now that’s
proven beyond a doubt. It still won’t change things. Until BILLIONS are lost, Status-Quo will
be the norm.
The topic is misleading. This does not “completely” break SSL. It only breaks SSL certs signed with MD5.
It does completely break MD5… but it’s been broken for years.
now do CSA so i can watch tv
What a waste of a PS3! Dont people do normal things like play with their PS3 anymore? Oh I know what I’ll do I’ll go out and buy 200 PS3’s because I cant afford a CRAY-1 Supercomputer, then I’ll waste hours of time trying to develop a flaw in rapidshares SSL certificates because hacking into RapidSSL is so k-rad and uber pwn.
actually its things like this that makes gaming on a ps3 pointless. CRAY-‘s are not the only super computer and if im correct that particular type of super computer is rather aged at the time of your post. Dont mean to say i told ya so but some one needed to
The threat is very real because a foundational break in the MD5 algorithm being used to falsify a certificate is a legitimate break in SSL (an entire protocol).
Still, it’s a limited break in that the number of potential collisions is limited. That doesn’t make me any more comfortable about it.
This does make me wonder about SHA1. The original SHA algorithm was made available by the NSA and was replaced with a slight alteration to it that the NSA claimed made it more secure. They didn’t elaborate on it, though.
Needless to say, selecting the SHA1 algorithm for certificate signing appears to be the intelligent way to go for now.
200 PS3 x 400 US $ = $80,000
yet it “Takes $20k worth of amazon EC2 time”.
I really don’t see the draw for using PS3s. I’d bet some FPGAs could do it just as fast and cheaper. Or some cheap CPUs driving fast and wide GPUs (like a set of 260GTX) via CUDA.
The speed may not actually matter. so what if you wait a week or two to crack it, the exploit is still valid is it not?
so all I gotta do is buy 199 more ps3’s and I can do that eh?
imagine the heat that that damn rack produces
@epicelite (et. al): Don’t need to buy anything. Distribute client software and say it’s doing something benign like calculating pi, listening for extraterrestrials, or participating in RSA encryption contests. Claim it’s a contest and even offer a small monetary prize.
::Points at the post above::
Whatever happened to the comment monitoring system? I believe it was just a few guys looking over things and making sure it was not stupid crap, but …
Anyways, yes, very interesting. I suppose I should be happy that they released this as they did. That firefox is blacklisting them etc. However I can’t help wishing that they had just started signing certificates for anyone who wants them with this. Allowing all sorts of fun.
Also how did they time their purchases so precisely?
that means our credit card data is no longer safe?
naw i think the CC info is still safe… i mean how many crackers do you know that have $80k to blow on 200 ps3’s? haha food for thought
this note is misleading and causing misunderstandings, ssl has not been broken (not the protocol as a whole), though it’s something serious… and this doesn’t mean the credit cards data (or any other information) is “no longer safe”. fortunately main players in the scenario seem to make the right moves to try to solve this problem
Fair Play to them but just one little question, WHY?
There as so many better things you could do with £40000.
Bit of an expensive way to say I told you so…
everyone keeps brushing this off by saying that its a waste to buy so many PS3’s for this purpose
did it ever occur to you that perhaps, just maybe, they got the ps3’s to make a general purpose computing cluster… duh!
this project only took 1-2 days to execute on the ps3s… seems pretty likely that they didn’t buy the ps3s for that purpose solely
@wtfisthatthingdude: Better question: how many crackers have access to an army of zombie computers that could be easily switched from DDoSing to serious number crunching? Food for thought.
agreed with alexsfox, the PS3 is known to be a rounded powerful system when used in clusters. It was a while back, but I remember some College professor/students got 8 together and made a 64-core system, quite useful really.
To the lame kids asking about XBox: the PS3 is a totally distinct superparallel computer architecture using the Cell Broadband Engine, a new generation chip architecture.
Meaning: PS3 is the tops. XBox is just lame.
To the people asking about the cost: I guess if you’re living in mom and dads basement you don’t have this cash. If you’re an adult, you can maybe sell your car, no? And for mafia criminal, 80k is just change.
I’m almost positive alexsfox is right.
Plus an experiment like this one is not a waste of money at all. What is everyone going to do if sha1 is next? Their relatives would flip in their graves.
I think it is a bit misleading to say whether a hash function is broken or not. Pick any hash algorithm and you will find all of them will produce collisions at some point. It’s a matter of these algorithms having weak or strong resistance to collisions, that’s all. MD5 was found to be weaker than expected. Oh well, life goes on.
I’m still waiting to hear how MD5 was broken? Everyone should know that MD5 allows for collisions. This shouldn’t shock anyone working with it. This was part of the design. It was never meant to be an encryption, only a hash that was good enough to quickly figure that you had the right content.
So theoretically you could do the same thing for any hash algorithm, given enough computing power.
I bet Google could fuck some shit up.
Why should they work for Stanford.
Doesn’t the Stanford has already enough money to buy enough PC’s or PS3’s ?
I hate when they use MY PC or PS3 without telling me what is this about.
I hate this whole GRAND THEFT PROTEIN Project or how else you call.. folding@home etc.
The bad is Stanford could use your machine for something that it might not be that good.
I AM NOT SAYING OR ASSUMING THAT THEY DO.. but in the end WHO would ask you or who would tell you anyway.
How long until our current method of navigating the web seems as quaint as picking up the phone and asking the operator (whose name is Linda; she’s our neighbor) to connect us with Johnny down at the general store?
@blind:
Hash algorithms are supposed to be one-way. That is, you shouldn’t be able to generate a plaintext that will produce a desired hash any faster than random guessing. It’s been shown that this is possible with MD5, and even possible with selected plaintext and only small modifications. Makes it completely useless for cryptographic purposes.
In other words, 200 PS3s were sold this holiday season.
Seriously, MD5 is not as secure as people think. There has been several projects that have successfully cracked it.
Yes, this means that SSL is broken. They could forge a certificate for any domain name that browsers happily accept. So yes, credit card stuff could easily be sniffed in a man-in-the-middle attack.
I’m glad they found SOME use for PS3’s :D
Well lets hope bad people cannot afford 200 PS3’s.
Posted at 9:49 am on Dec 30th, 2008 by epicelite
don’t worry, good people can’t afford them so we’re safe. :D
@MachineHead
I totally agree with you..
FPGAS are quite capable at solving encryptions.
Research on this subject has been going on for years now, since 2005 I believe, and the theory has been proved many times. This time they made it into a practical attack and all of a sudden it’s world news.
The cluster used has been around for over a year, and has built slightly after Dr. Mueler @ NC State made the cluster with 8 of them. Besides generating MD5, it’s also been used to predict the outcome of the presedential elections back in 2007 (I forget if they were right). More info here: http://www.win.tue.nl/~bdeweger/PS3Lab/
The fact they managed to find a CA cert that even used MD5, and that this cert’s auto signing was so predictable as to predict possible hashes is of course serious business, but not that big a deal on an internet-wide scale.
The fact that it’s only one Cert, but that they call it BREAKING THE INTERNET is just ridiculous and costs them all kudos they might have gotten.
If they used Wiis they could have cracked any hash algorithm using their Wiimotes, BANG!!!
md5 was not used to predict the elections, they were only showing how feasible is to create several different files but all with the same hash value (finding collisions), so they were using the hash value as prove of the prediction, but since all the files with the different names had the same hash, they were playing on the safe side.
i agree with johny a that they didn’t break the internet at wide scale, though an important test, they showed us how people in IT sometimes can be so careless in implementing technologies by using flawed algorithms and bad practices
So *this* is who bought all the PS3s! I was wondering who the owner(s) was/were. you’ve gotta appreciate the irony that games developers still cannot get to grips with the hardware but you can do this as well as Folding@home. Maybe next time around, Sony might want to release a games console instead of a flying car…
Really sony has sold 200 PS3???!!!!
May be.. !!!!!!!
Fantastic news!!
So all I have to do is buy 200 PS3…
The post is not really relevant, this operation do not break ssl but md5, so many years before many research break this algo…
Jules
http://www.openprox.info
Surely they could have just used 10 PS3’s and waited a week or two? ;-)
true, this experiment did not *break* ssl, but it found a workaround by breaking md5, so ssl would be rendered useless since they have their own little ca to churn out certificates for them
wow… I was looking for the same from past one hour… thanks for the post, it’s really great.
– Sohail
http://iMobile.us
Shame it still has no games.
quote from sam:
“”
Needless to say, selecting the SHA1 algorithm for certificate signing appears to be the intelligent way to go for now.
“”
ferguson, schneier recommend in their book “practical cryptography” not to use sha-1 because of its low security level. They argue very plausible that using
$hash = sha-256(sha-256($text));
should be used to create a save hash.
*edit*
sorry for doubleposting. my english is not the best :-S
“… to create a secure hash” (german word for secure and save is the same)
and I was not finished: I wanted to know why recommending sha-1 if their are more secure algorithms available.
So, this took 200 ps3s, one of the most powerful commercial computers on the market to crack the encryption. That means that it is pretty secure for modern standards, but in 5 years, the computing power of 200 ps3s will be a little more accessible and the system will be broken.
really koolz man,
@wraith
A system that can be broken in 1-2 days by 200 PS3s is not “pretty secure”, it is extremely insecure.
A system is considered as “pretty secure” if the only practically feasible known attack is brute force attack, and if the key (or in this case, the hash) is long enough to resist months or even years to a brute force attack of a cluster of tens of thousands of computers.