A little more than a week ago, I promised that I would follow up my article dealing with the impact on SSL and X.509 of recent advances in cryptanalysis of MD5 and SHA1 with some related information about what the impact is on the PKI-based signature and authentication schemes used in Notes and Domino. This is it.
Point number one: Notes and Domino don't use MD5 or SHA1 for either digital signature on documents or for certificates, so thepublication of the successful attack against SHA1 and demonstration of practical MD5 collisions are not immediately relevant. That's the good news. It's not all the news, however, and I think that an honest evaluation of a key aspect of Notes' and Domino's security comes down to this:
Do you feel lucky, cyberpunk?
That's if nothing changes.
I want to stress that, although I have some mathematical skills, I am not even close to being qualified as a cryptographer (or cryptologist, or whatever). I do not have detailed understanding of these algorithms, and I could be totally wrong, but nobody has proven that MD2 is any more secure than MD5 or SHA1, and from what I do understand about the design of these algorithms, if MD2 happens to be intrinsically stronger than MD5 or SHA1 it's simply a result of pure luck.
I once participated in a conversation with John G. Kemeny, the co-inventor of the BASIC programming language In addition to being a famous mathematician, he was an avid sports fan, and he was particularly interested in the statistics of "streaks" in sports. With few exceptions, he considered most streaks to be unremarkable. Joe DiMaggio's 56 game hitting streak was one of the exceptions. Most others, though, were simply expected results at the upper end of a predictable distribution curve. Here's a paraphrase of an exchange that occurred during that conversation:
"Professor, do you believe in luck?"
"Not within two standard deviations of the mean."
The point of this, of course, is that mathematicians are loathe to trust in luck. And what do we know about MD2? Well, it's a 128 bit hash, the same as MD5 and SHA1. It was designed before MD5, by the same person. MD2 was optimized for 8 bit computers, whereas MD5 was optimized for 32 bit computers. In MD2, the text is padded with a checksum before the hash is taken, as opposed being padded with it's own length as MD5 is, and it is known that collisions can be found if the checksum is omitted.
Let's re-phrase that. A very smart guy who knows an awful lot more about cryptography than just about anyone else, and who probably got smarter with more experience, designed MD5 to use larger operations on more powerful computers than MD2, and switched away from using a checksum as padding, undoubtedly with the idea that he was making a stronger hash even though it was the same length in bits. Now, in addition to the fact that MD5 is broken, we also know that the only thing keeping MD2 from being broken is the fact that it pads the input text with a checksum prior to computing the hash, and... as far as I know... there is no mathematical proof that the checksum does anything to improve the strength of the hash. That leaves me believing that only luck could account for MD2 being significantly stronger than MD5.
And it's probably not significantly stronger. It hasn't gotten the press attention, I guess because MD2 isn't all that widely used outside of Notes and Domino, but there is a result noted at the end of the Wikipedia article about MD2 that indicates that a proof has been published showing that MD2 collisions can be found in 226 fewer operations than a brute force attack. I.e., in an average of 2101 tries. This result is recent (last year), and while 2101 still seems like a pretty big number, progress in the attacks against MD5 and SHA1 has been moving quickly. The chances that MD2 will stand up to further analysis without reducing that work factor even farther seem very slim.
If MD2 falls to the level where a practical attack is possible, as it seems all too likely that it will, this is what it will mean for Notes and Domino:
Digital signatures will not be assurance of authorship of authenticity. It will be possible to clone a signed document, delete the signed data, and add new data, such that the signature remains valid, and use hide-whens to make the random looking stuff invisible -- so only a careful look at document properties would reveal the forgery.
It may be possible to forge ID files by taking an existing ID file and modifying it without invalidating the certificates. As the ID file format isn't public, we don't know whether it has variable length data areas or empty spaces within the signed portion that could be used by an attacker to squeeze in the data necessary to match a forgery to the original hash. (Note: we know that the ID file is variable length, as it can store secret encryption keys, but we don't know if the signed portion is variable length.) Not knowing is no assurance.
Getting back to the level of cryptographically-enforced security that we used to have (or thought we had... after all, certain agencies may very well have known about weaknesses in MD2 for a lot longer than the rest of us!), some sort of recertification process is going to be needed. The vast majority of us can probably consider it optional, but it's going to be a necessity in the highest-security applications.
1. Nathan T. Freeman07/04/2005 08:25:12 AM
Remember, Notes doesn't use the true public MD2 algorithm. So a successful attack against it in the public domain will not necessarily lead to vulnerabilities in the Notes/Domino world.
Not that this stuff shouldn't be worrying us.
2. Danny Lawrence07/04/2005 02:02:49 PM
Dirty Harry in the 24th century:
1) Go ahead, make my average planetary rotational period!
2) I know what you're thinking. "Did he fire six charges or only five?" Well, to tell you the truth, in all this excitement I kind of lost track myself. But being as this is a 44 megawatt, the most powerful hand aser in the universe, and would blow your head clean off, you've got to ask yourself a question: Do I feel lucky? Well, do ya, cyberpunk?