Keyed-MD5, and HTTP-NG

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.
        There are also some very fast MAC algorithms being proposed
these days.  As Phill Hallam mentioned, you may want to look at the
work of Phil Rogaway.  At a minimum, make sure that your standard
allows people to migrate from a current solution based on MD5 to a
future solution based on new functions.  However, I would be relunctant
to require new functions until they have had a chance to be tested
by the cryptographic research community.
                --Bob Baldwin

"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

Ooops...

Just gone off and read the papers again. The Keyed MD5 proposal currently described 
in one of the drafts is indeed one of those that was suggested in the cryptobytes 
article. I remember reading another calling itself "Keyed MD5" at the time of the 
rumpus Perry refered to.

The response that had been communicated back was that the IP sec work was going to 
standard anyway despite the objections. The suggestion which had started people off 
was that of MAC_a(x) = MD5(a.x.a). Nobody ever mentioned that IP sec had changed the 
construction (which is a good thing).

The point still stands however that there will have to be more than one algorithm 
supported and that HTTP-NG cannot assume that a particular algorithm or construction 
will be used. Keyed-MD5 is still an MD5 variant, there are good reasons to think that 
a keyed digest could be constructed which would be faster than a hash function.  

	Phill