Schierer Space

Although this is old news^[1] in the cryptography/security community, I find the topic interesting enough to spend a few minutes on. I got word of this issue from someone at work^[2], who said basically “Did you hear that somebody cracked the MD5 algorithm for SSL using a hash collision and used it to sign a certificate?”

Although that sounds like gibberish to most of us, it translates roughly as “Did you know the little lock icon in the corner of your web browser can no longer guarantee that you’re talking to who you think you are?”

Wait… don’t panic. It’s probably not as bad as it sounds, but there is reason for legitimate concern. Reputable signature authorities will quickly be revoking any signatures based on MD5, and replacing them with other more secure algorithms. In all likelihood, ‘bad’ certificates will be quickly detected and purged, but that could still put a lot of data at risk.

If all of that was gibberish, read on.

So what do corned beef and potatoes have to do with security anyhow?

A hash is a sequence of data that represents a larger chunk of data but is smaller. A hash is generated by an algorithm, or hash function, that processes the larger data in a particular way to produce a predictable result. In simple terms consider addition as a hash function. If I take the numbers 17,35,02,46 and 54, I can add them together and produce the result: 154. In decimal, the 5 starting numbers take 10 digits to represent, but the result is only 3! ^[3] Every time I take those numbers and add them, I will end up with the same result, so 154 is a very simple hash for the sequence 1735024654.
If my sequence had an error (or was made by an impostor), the result would generally be different. For most 10-digit sequences, ^[4] comparing the hash results will reveal that the sequence has changed, or is not legitimate. However, certain sequences (and in the case of my very weak addition algorithm there are many) will generate the SAME hash (e.g. 562144310 or 1241320267). This is called a “hash collision”. From a security perspective, this means that two different sequences are indistinguishable by looking at the hash.

So what does that mean for my browser’s little lock icon?

Well the lock indicates that the web browser and the website have established a secure, encrypted, connection. This prevents outside entities from viewing your data. So how does your browser know that it’s establishing a connection with the right site vs. establishing an encrypted connection with a bad guy? The site shares a ‘certificate’ which identifies it. The certificate is ‘signed’ by some authority that your browser trusts.^[5] So your browser knows that citibank.com is really associated with CitiBank, because the authority signed the certificate… This signature is a hash code.

So if the bad guy can generate a hash collision at will, then they can sign a certificate as if they are the trusted authority, right?

Exactly. Although all hashes have collisions,^[6] Certificates tend to live longer than a few days, so that essentially means that the algorithm is no longer secure. There are other algorithms which are more secure, and most authorities have switched over to the better ones (like SHA-1). Unfortunately, your browser is too dumb to know that it should stop trusting the MD5 certificates.

So should I stop using online banking?

No, in my opinion that would be silly. The attack is pretty far fetched for a couple of other reasons, and we’ll be seeing the signatory authorities moving away from MD5 quickly. The fact that they didn’t do so years ago when the threat was first identified is a bit discouraging. It took somebody to actually exploit the vulnerability to persuade them. My guess, and I don’t have much data to back this up, is that very few reputable secure websites will fail to supply a signature by another algorithm. I’ve checked my bank (USAA) and they are using both MD5 and SHA-1 to secure their site.

Can I tell my browser to stop using MD5 certs?

Maybe. I found a couple of sites with recommendations for changing FireFox’s behavior, but the advice is so conflicting I’m not going to link to it. There is also some discussion as to whether changing the browser behavior actually does anything, if the higher level certificates were faked. I don’t know enough to give useful advice so I’ll be mum on this issue.

1. The creation of a false certificate was presented at the end of 2008. [↩]
2. thanks Mark! [↩]
3. My brain is stuck in bytes, so I see that as 5 bytes becomes one! [↩]
4. That is to say, there are far more 10-digit sequences that generate a number OTHER than 154 then there are that generate 154. [↩]
5. You may have seen Microsoft updates come in that are called “Root Certificate Updates”. These Root Certificates are the trusted entities according to Microsoft. [↩]
6. I may be on shakey ground here, but I’m pretty sure this is true.) the issue is whether you can generate one at will and take advantage of them. MD5, an algorithm in common use by signature authorities, DOES have collisions and these collisions can be exploited algorithmically in a few days. ((I find it interesting that the researchers used 200 modified PlayStation 3s to do the heavy lifting. That’s a lot of integer number crunching! [↩]

This entry was posted on Saturday, March 21st, 2009 at 10:14 am and is filed under Computer / Tech. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.