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…
- 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. - 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. - 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!
