PlayStation hammers a nail into the lid of MD5's coffin

Since 2004, security researchers have known that the MD5 hash algorithm suffered from certain cryptographic weaknesses. However, during a recent talk given at the 25th Chaos Communication Congress (25C3), a team of researchers showed the world just how dangerous these weaknesses have become.

Before I dive into the researchers' new attack, let me offer a refresher on some cryptography concepts required for understanding this attack. Let's start with cryptographic hash functions. A cryptographic hash function is a mathematical algorithm that returns a unique, fixed-length value (a hash) for any data fed into the algorithm. A specific hash value should only uniquely match one specific data set. In other words, if you feed different data into the algorithm, each different data set should always produce a unique hash value. Furthermore, if you make even the slightest change to a data set and send it through the algorithm again, its hash should change.

In cryptology, the properties of a hash prove useful in helping you ensure the integrity of data (an important part of the CIA triad). For instance, suppose you want to make sure a file you send your friend doesn't get altered in transit. You would run it through a hashing algorithm before sending it, and notify your friend of the result. When the friend receives the data, she can run the data through the same algorithm you used. If the file's hash result matches on both the sending and receiving ends, you know the file arrived without any changes. On the other hand, if the hashes differ, you know the file changed during transit. Many of the secure connections you make over the Internet -- from VPN tunnels to logging onto e-commerce sites -- use cryptographic hash algorithms somewhere behind the scenes to help ensure the integrity of the connection.

The MD5 hash algorithm is just one of many hash algorithms that cryptographers have created. Why so many? Well, not every hash algorithm is created equal; some are weaker than others; some are more suited for specific purposes or even specific computer processors. Remember, the value of a hash algorithm depends on its ability to create unique hash values for data sets. If two different data sets fed through the same algorithm generate the same hash, in crypto-land, this situation is called a hash collision. That hash algorithm can no longer guarantee the integrity of a data set. I like to say the algorithm has gone from "cryptographic" to "craptogryphic."

Frankly, there is no perfect hashing algorithm. They all suffer from potential collisions. However, the best designed and most secure hash algorithms make it computationally infeasible for attackers to find collisions -- that is, until some crazy smart mathematician comes along and discovers a short-cut.

All that background leads us up to what happened with the MD5 hash algorithm in 2004. Xiaoyun Wang (a crazy smart mathematician) published an attack that made it much more feasible for attackers to find collisions in MD5 hashes. This paper began the end of the MD5 hash algorithm. However, these types of cryptographic algorithms tend to take a long time to die. A mathematician's theoretical attack on an algorithm doesn't always translate into practical attacks. But that's where this new attack enters the picture.

At the 25th Chaos Communication Congress (25C3), a group of researchers leveraged MD5 collision vulnerabilities in a practical attack. They exploited the collision flaws to create a fake certificate. When you visit secure web sites, your web browser relies on digital certificates to insure the legitimacy of the web site. Those certificates are typically created and issued by trusted third parties, each known individually as a Certificate Authority (CA). In order to prove a certificate's validity, the issuing CA signs the certificates it issues with its digital signature. And therein lies the rub: the digital signatures CAs use to sign certificates are created using hashing algorithms, and some CAs still use weak MD5 signatures.

The group of researchers found a CA that still issued MD5-signed certificates. They bought a few such certs from the CA. Then they looked for collisions in the CA's digital signature. The 2004 MD5 collision attacks I mentioned earlier speeds along this MD5 cracking process; however, that attack is still computationally expensive. So the researchers set up a super-computing cluster made up of 200 networked Playstation 3s (PS3). With their PS3 cluster, the researchers were able to find a collision for CA's MD5 signature within a day, thus creating a rogue CA signature.

What does all this mean to you? Simply put, you can't trust the legitimacy of any website you visit if it only uses an MD5-signed certificate. If an attacker can leverage the MD5 collision flaws to create rogue CA certificates, the attacker can use these fake certificates to seemingly legitify any domain or web site. This provides the attacker an invaluable tool for phishing attacks. He can trick your web browser into thinking it really has a legitimate, digitally signed, secure connection to any web site the attacker wants to spoof.

So how can you fix this? If you're a normal user, the problem isn't one you can fix. The CAs that still issue MD5-signed certificates need to switch to a stronger hashing algorithm (for example, SHA). Most of the CAs vulnerable to this attack have already started doing so. In the meantime, pay close attention to the URLs you visit. The URL should really match the site you think you're visiting.

For administrators, this attack should prompt you to start phasing MD5 out of your network. Potentially, the MD5 algorithm could be used in many ways within your network. You might have VPN tunnels that rely on MD5. Some Host-based Intrusion Detection Systems (HIDS) use MD5 signatures to test the authenticity of files. You may even have configured your SSH server to accept MD5 signatures for login. Admittedly, the MD5 collision vulnerability doesn't affect all these systems with equal severity. Nonetheless, I highly recommend you at least begin to phase out MD5. This research has proven MD5 attacks feasible. The researcher's PS3 cluster has solidly hammered home a nail into the lid of MD5's craptogryphic coffin. //