From: "baldwin" <baldwin@RSA.COM (Robert W. Baldwin)>
Date: Thu, 2 Nov 1995 12:29:40 +0800
To: baldwin@RSA.COM (Robert W. Baldwin)
Subject: Re: Keyed-MD5, and HTTP-NG
Message-ID: <9510018152.AA815244951@snail.rsa.com>
MIME-Version: 1.0
Content-Type: text/plain


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