Big News In Electronic Signatures

The cryptography world was all abuzz last week with news from a conference in Santa Barbara about new discoveries related to the most popular message digest (a.k.a. cryptographic hash) algorithms. As soon as I heard this news, I got in touch with my cousin, whom I unashamedly admit is the truly smart one in the family, and whom I rightly suspected was in attendance at the Santa Barbara conference. She reassured me right off the bat that there's no call for panic, but that the news I had heard was in fact true. Now, I see that Bruce Schneier, one of the top authorities inthe crypto field, has weighed in with the opinion that it's time for a new standard in hash functions.

The issue is that cryptography researchers have proven that it is possible to locate a hash collision for either the MD5 or SHA-0 algorithms in reasonable time on an ordinary desktop machine. Or in my cousin's more plain language: "MD5 and SHA-0 are broken".

Let's, however, be a bit careful in how we're defining "broken". The goal of cryptographic hash algorithms is to use all the information in a large string to compute a much shorter string, such that no mathematical trick can do better (on average) than a brute force search in locating another large string for which the same algorithm will yield exactly the same short string. Collisions are expected for any hash algorithm, but for a 128 bit digest (which is what both MD5 and SHA-0 generate), one should have to look at an unreasonably large number of long strings to find a pair that generate the same short string. Note that it's not 2¹²⁷ strings that one has to look at, which is what one might easily but naively assume. It's 2⁶⁴ for the same reason that you only have to have 23 people in a room -- not 183 -- in order to have an even probability that two people in the room share the same birthday. Still, 2⁶⁴ is really big number. What's been proven, though, is that there are approaches that can do significantly better than a brute force search, so you can find a collision by looking at significantly fewer than 2⁶⁴ strings if you're smart about what strings you look at. It is in that respect -- that MD5 and SHA-0 fail to meet the goal of being subject only to attacks that are no better than brute force -- that they are "broken".

Why do we care about this at all? It's because cryptographic hashes are what makes electronic signatures work. A hash is computed from a document, and the resulting bits are then encrypted with the creator's private key. To verify the signature, the creator's public key is used to decrypt the hash value, and then the hash is re-computed from the received text. If the two hashes match, the signature must be valid, because we know that the creator's private key must have been used to compute the encryption of the hash.

So, what are the implications for the product that has been using electronic signature longer than anything else on the mass market, and which has the largest installed base of PKI users in the world: IBM Lotus Notes and Domino? There are three areas of potential concern: Notes electronic signatures, SSL, and S/MIME.

The latter two concerns are industry-wide, not just issues for Lotus, because MD5 may be used by any vendor's implementation of either SSL or S/MIME. SHA-1, however, is much more common as a hash algorithm in the Internet protocols, and while SHA-1 is quite closely related to MD5 -- and it is therefore reasonble to presume that it might be vulnerable to the same type of attacks as MD5 -- there have not yet been any demonstrations that it actually is vulnerable. Not yet.

Furthermore, it is important to realize that the techniques used against MD5 and SHA-0 do not yet constitute practical attacks. The algorithms are broken because they don't meet the very rigorous standards set by the crypto community for hashes, but that does not necessarily mean that the algorithms don't still meet all the practical requirements of even the most extreme security environments. (SHA-1, by the way, was developed by the NSA, so it has as good a pedigree as any algorithm in existence.) The only thing that has been proven is that it is possible to find two messages that collide. That, however, is actually a very different thing than proving that it is possible to find a collision for a specific given message; and that, too, is a very different thing than proving that it is possible to find a "plausible" collision -- meaning one that looks like it could be a legitimate message and is therefore a useful forgery. It's going to be much harder to to prove that the current attacks can be used to find plausible collisions for specific messages, and in any case the compute time requirements will undoubtedly be several orders of magnitude higher for that.

It's clear that the industry does have breathing room, at least for now. IBM will certainly be able to keep up with the rest of the industry in adapting SSL and S/MIME to new and improved hashes.

As for Notes electronic signatures, the good news there is that they are not based on either MD5, SHA-0 or SHA-1. My understanding is that Lotus uses MD2, which despite the fact that it is closer to MD5 in name than SHA-1, is actually mathmatically less related to MD5 than SHA-1 is. It seems to me, therefore, although I do not pretend to be an expert on the subject, that it is probably somewhat less likely that the MD5 and SHA-0 attacks will be quickly extended to MD2 than they will be to SHA-1. If that's true, then there's even less reason to fly into a panic about Notes electronic signature than there is about SSL or S/MIME. Still, though, with someone as well respected as Bruce Schneier is in the field of cryptography stating that it is time to move to stronger standards, and pointing to the already existing stronger standards such as SHA-512 as being a mere stopgap along the way, I imagine that something better than MD2 is going to be needed in the long run. too. How long that might be, I can't tell you. I can tell you, however, that I know for a fact that IBM has some very smart people thinking about this already. I know this because, shortly after getting in touch with my cousin, I also got in touch with a friend at IBM, and I got a prompt and reassuring response.