Perry, I wish that the field of cryptography was as well advanced as the field of Bridge Building. A modern Bridge Builder can design a bridge that is easy to construct and will in fact last for 100 years. Unfortunately, modern Cryptography is like Bridge Building in the late 1800s. Back then, it was possible to build bridges that did last for 100 years but lots of cities refused to pay the extra costs in materials, labor and time to make a solid bridge, and as a result the bridges did not last. To make it worse, there was no systematic teaching of the best practices, so often no one would realize that they had build and/or bought a weak bridge until the day that it fell apart. The sad result of the state of the art in Cryptography is that we end up with situations like the one you described where it takes months to get agreement among Cryptographers and then it turns out that one of the other choices would have been better. Not surprisingly, the other choices often run slower than the initial choice. However, there is little guarantee that the second choice will resist all new attacks. One of the reasons that the IPsec authenticator was analyzed was that it had been chosen as the IPsec authenticator. As soon as a large organization picks a new authenticator, the researchers will try their hand on breaking that one. In the field of Cryptographic Engineering, we just don't have a well tested construct for authenticators. If the IPsec group was run by scientists instead of engineers, then they would consider cryptographic constructs that have "provable" security properties (e.g., faking this authenticator is as hard as factoring a Blum integer (a composite number with two strong primes)). The downside of having this kind of provable security is that the packet processing time would be enormous. You would loose all the benefits of a T1 connection to the Internet in order to get provable security on your authenticator or encryptor. Speaking for myself, I am glad that the IETF is run by engineers. The vitriol you spewed is quite justified. People at RSA and IBM both agreed that the IPsec authenticator would resist all known attacks. In fact, a fully conforment IPsec implementation will still resist the new attack because IPsec requires that the all keys be changed every 2**32 packets. However, this new attack makes Cryptographers nervous. Perhaps it could be extended to work with only 2**40 chosen packets in which case there is a noticeable chance of it succeeding with only 2**32 packets. Only further research will tell. Currently, the only way to get the MD5 key is to feed in 2**60 chosen messages of various lengths. Of course, this is another good reason to use different keys for the MD5 authenticator and packet encryption. Wisely, IPsec requires different keys for the authenticator and the encryptor. I also understand your being upset about not hearing about this attack the moment it was published. Actually, as soon as RSA Labs confirmed the weakness we did call some of the editors of the IPsec specifications to let them know about it. The consensus was that this was not a show stopper. The IPsec protocols could be rolled out as is. Later, once a better authenticator had been developed and tested, it could be substituted for the existing one. One of the excellent features of the IPsec specification is that new algorithms can be substituted easily (modulo a "small matter of programming"). Perhaps your main complaint is that it took time for the attack to be confirmed by other researchers before the issue was brought to the IPsec authors. That is another effect of the current state of the art in Cryptography, and an effect of the normal academic process. It takes time to understand and confirm a weakness, and it is necessary to confirm weaknesses (researchers make mistakes in designing attacks just like they make mistakes in designing ciphers). That's the way things are in "cryptography today". I guess my conclusion is to say "Sorry". Several professional cryptographers gave it their best shot, and the authenticator turned out to be somewhat weaker than expected. --Bob ______________________________ Reply Separator _________________________________ Subject: Re: Keyed-MD5, and HTTP-NG Author: perry@piermont.com at INTERNET Date: 10/31/95 5:25 PM "baldwin" writes:

Simon, There are a few different ways to add key material to MD5 to make it suitable as a shared-secret authenticator function. Some of these are less resistant to attacks than others. For example, the keyed MD5 mechanism that is part of the current IPsec specifications can be attacked using 2**60 chosen messages. Fortunately, the IPsec specs also require that the shared MD5 key be changed every 2**32 messages, so this attack is unlikely to succeed. Specifically, IPsec uses MD5 as follows: X = MD5(key | keypad | Message), where "|" means concatenation and the "keypad" pads out the key to 512 bits. Basically, this function is the same as standard MD5 with a different initialization vector for the compression operation on the first block of the message. RSA Labs recommends that a people use an authenticator like X = MD5(key1, MD5(key2, Message)). This resists the chosen plaintext attacks that were published at the crypto conference in Spring 1995.

Pardon me. The amount of vitriol I am going to spew is probably difficult for people to understand because most folks around here weren't following the keyed MD5 discussions during the IPSEC work and have no idea of the sort of crap the professional cryptographic community put us through. We spent months, and months, and months, and months, getting advice from every cryptographer on the planet. Every conceivable combination of pads, multiple keys, keys before the text, after, before and after, etc., was discussed over and over and over again. Finally, the folks at RSA and IBM both agreed that Hugo's scheme, the one we were putting in to place, was the best possible one. (Thats the one with the padded key.) What the flying hell are you doing telling us now, and indeed not even telling the IPSEC community but instead mumbling on cypherpunks, that you guys were in possession of information BEFORE the entire discussion in midsummer that indicated that your own advice was wrong? Perry