Re: Digest Auth defending against replay

Paul raised a question about the security of keyed MD5. I don't have my files
avaliable because I'm at home recovering from a root canal which I had this mo
morning. so This is from memory:

We have discussed keyed digests at length in ron Rivest's reading group
on a number of occasions. There are a number of concerns.

1) Construction of a MAC with a digest function was not an anticipated
	use of a digest. Hence there are a number of weaknesses which
	could have been avoided if anticipated.

The most serious of these is the fact that the MD5 datapath is 128 bits,
the same as its output. This means that there are a number of collision attacks
which are not serious for the digital signature applications MD5 is designed for
but are serious for keyed digest, in particular there are a sequence of prefix 
and appending attacks.

This means that for most purposes one should "seal" the MAC using a one way
function. this is essentially where the MD5( MD5(x)) type constructions
appear. For reasons which I don't want to go into without a blackboard there
are padding and ordering constraints on the MAC construction which one
would like to use.

2) there is no strong theoretical basis for most uses of keyed digests to
	produce a MAC.

This is where recent work by Ran Carnetti and Phil Rogaway is very interesting.
Ran has done a lot of interesting work which is very interesting. I don't
believe he is ready to publish yet.


I would ideally wish to replace the method of constucting the digest, except 
that at the moment I can't provide a very good theoretical ground for the
change. When I suggested the construction in the first place I knew rather less
about keyed digests than I do now. The current construction is fortunately
not too bad and until there is a clear consensus on the best replacement I
would prefer to delay making a change.

Another reason to delay making a change is that there are better methods of 
constructing MACs than using a keyed digest. One suggestion made by Ron
is to change the mysterious constants #01234567, #89ABCDEF which MD5 uses
to initialize its registers. This provided a much better theoretical basis 
for the soundness of the MAC. Another way would be to adapt the other set
of constants MD5 uses - the aditive constants on each round.

If people are happy with this approach we could specify KD5, a variant of
MD5 especially designed for use as a keyed digest. Recent work on MD5 makes
me think that we might be best to work on SHA or something similar.
SHA is also a varian of MD4 but some of the design decisions are more 
appealing - especially the longer key length. In the medium term we can
probably expect a new digest proposal to be made. Processor technology
has changed recently making a 64 bit working unit very appealing. 


To sumarise the problem is too many options and consequently I don't feel that
now is the time to make a change. I would like the spec to tie the method of
digest construction to the algorithm however. Ie we are mot using MD5 as the
MAC we are using a keyed digest based on MD%. If we used SHA the method of
constructing the digest would probably change.

In general a message digest is a function of one variable, a keyed digest
is a function of two variables. These are different things

		Phill

Received on Tuesday, 27 February 1996 12:02:10 UTC