- From: <hallam@w3.org>
- Date: Tue, 27 Feb 96 14:59:46 -0500
- To: Paul Leach <paulle@microsoft.com>
- Cc: hallam@w3.org, john@math.nwu.edu, http-wg%cuckoo.hpl.hp.com@hplb.hpl.hp.com, hallam@w3.org
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