A Real New Year's Hash

The New Year has just arrived and I'm reminded how, globally, we are all connected in ways that would have been impossible 20 years ago: it's almost hackneyed to say it again, but thanks to an amazing combination of infrastructure and technology, we can live, work and play from Mumbai to London and from Tokyo to New York City as one world in real-time. Of course, a lot of this is dependent on some of the basic building blocks we use being sound, and in the last few days one of these building blocks has come under attack: MD5 is on its last legs as a tool in the cryptographic toolbox.

I've been following the ins-and-outs of the recent, practical exploit of MD5 posted on Phreedom.org by Alexander Sotirov and some of the wake this has caused. Their claim (Alexander is one of seven researchers in the US, Switzerland and the Netherlands — and one of the other researchers, Arjen Lenstra, is a winner of the 2008 RSA Conference Award in Mathematics) is that they can create a collision attack that permits forgery of a valid certificate chain for digital certificates.

The two Root Certificate Authorities (CAs) owned and offered by RSA are based on SHA-1 and therefore are not vulnerable to this collision attack. We have not used MD5 in either of RSA's certificate authorities for over a dozen years. Read on for more details.

I've decided to write this in sections for different readers: some may want to know more about hashing, some may want to know what it means for RSA products and services and some may want the "net" or bottom line; so hopefully writing this way means you can jump to the part you care most about!

Making a Hash of IT

(Security experts may want to skip this next paragraph)

Hash algorithms (such as MD4 — now defunct — MD5 and the SHA family) allow a message to be "crunched" in such a way that it always produces a given, fixed-length output. A slight change in the original text should produce a radically different output. Given the infinite number of inputs and the finite number of outputs, there are always multiple inputs that have the same output — but hashing has always been used on the premise that finding two inputs for the same output is computationally extremely difficult (though not impossible) and impractical for building a real exploit.

As an interesting side note for trivia lovers like me, the term hash was apparently originally used by Hans Peter Luhn of IBM to mean "to chop and to mix" or "to hash."

What's the news?
The reported collision attack is effectively finding a practical pair of inputs and implementing an attack that can meaningfully exploit a cryptography-based business process (most of them!) in real-time. And here is where the work of Mr. Sotirov and company is particularly valuable: they have apparently developed a meaningful attack for exploiting the Internet public key infrastructure (PKI) that is dependent on MD5 as the hashing algorithm used to "sign" (it's not really a signature — it's much more "fingerprint-like" for integrity checking) digital certificates.

What does it mean for us all?
To begin with, this is not a cause for panic: yes, we depend on hash algorithms for the Internet "bar" to be hacked to remain high and we need trust for it to function as we want. However, I would point out that this is actually healthy behavior. Let's look at a few points...

1. This was done in responsible conditions, apparently. (note: I haven't spoken to the Phreedom.org team at this point and haven't looked deeply at their work — I wasn't at their Dec. 30 presentation at the Chaos Communications Congress in Berlin, either). It does look like a responsible post and solid, qualified work in controlled conditions — well published and well documented.
2. There are as yet no "in the wild" instances of this exploit that are known or documented, meaning you are safe at the moment. However, don't underestimate the speed with which the darker side of the Internet can mobilize: any independent software vendor, online retailer or service provider who is using MD5 needs to pay attention to this right now.
3. There are other hash algorithms — of course some implementations may take time to change what they use, but now the onus is on them to do so. Move to another algorithm now (such as SHA-2 or RIPEMD-160).

RSA Products and Services
Since 1996, RSA has been advocating not using MD5 as a hash algorithm (the bulletin advocating this is here). We have not used MD5 in either of RSA's certificate authorities for over a dozen years. Both of our certificate authorities’ default hash algorithm is SHA-1. Our CA’s are named “RSA 2048” and “Valicert Public Root”. I am surprised that the researchers claim that there is an RSA-issued certificate from 2008 that used MD5 since our own internal enumeration shows otherwise. Any references to “RSA” or “RSA Data Security” in their research may very well be out of date.

As a side note, there is a theoretical weakness in SHA-1, with no real world implementation. Preemptively, we have had plans in the works to move to SHA-2 as our standard.

Hashing it all Together
So, as we bid farewell to 2008 and watch the world move ahead into 2009, we see an old tool move out of the toolbox and be replaced by new ones. It's not the end of the world, and in fact it's a most healthy sign that we test our building blocks and improve on them. So long as the processes exist to swap out defunct modules, it's arguable that this isn't only inevitable but is also desirable for building a strong Internet that is getting stronger as it adapts and evolves.

For those of you who want some fun, there is also a competition put on by NIST for a SHA-3 algorithm. It's not as much fun as the apparent 200 PS3's that are clustered what Kevin Poulsen dubbed the "PlayStation Lab" used by the researchers, but it may be more rewarding in the long term!

Post A Comment

Your Name
Your Email	Publish email?: Yes No
Your Blog
Subject
Comment
Verification Word