[Content-MD5 and Message Digest Authentication.], MD5 broken.

Appoloigies to the list for reopening a closed issue, but the circumstances have 
changed substantially.


Problem
-------

 I have been given a demonstration of a successful cryptanalitic attack against 
a slightly modified MD5 compressor function. This attack allows an attacker to 
create a message that has a given MD5' value. While the attack is presently 
against a modified version of MD5 the full attack appears to be merelty a matter 
of additional CPU. at present the attack takes about 50 MIPS days.


Consequences
------------

The consequences for Message Digest Authentication cannot be assesed at this 
point. I strongly suspect that the construction used is resistant to the 
cryptanalisis but require more details.

The consequences for the Message-MD5 tag are on the surface not as serious since 
the current use for the tag is as a pure checksum. It is not difficult to 
imagine later schemes which would depend on the cryptographic security of the 
checksum. For example a cache scheme which exchanges lists of signed headers 
without entity bodies.

On a more practical level, MD5 is likely to fall out of use over the next few
years. I expect that SHA will replace it, at least in the interim. SHA is 
resistant to similar attacks against MD4 and against differential cryptanalisis 
while MD5 is not.


Solution
--------

At present it appears that we cannot forward the Message Digest authentication 
draft in its present form. We could simply replace MD5 with SHA and strongly 
recommend its use.


For Content-MD5 I don't believe that the arguments for compatibility with the 
MIME spec are now valid. The breaking of the MD5 algorithm makes it unlikely 
that this specification will be widely adopted in its current form.

We can fix the problem by simply introducing an algorithm parameter. Ie:-

Content-Digest: 2A1238912371239587; alg=SHA

This change was strongly recommended by Ron Rivest, author of MD5.


If we don't make this change I suspect that in HTTP/1.2 we will be either 
carrying a little used "orphan" tag or we will be presenting the following:-


Content-MD5: 2A1238912371239587; alg=SHA

This construction is likely to break for obvious reasons.


Section 10.13 will need modification. I suggest that the spirit of the change be 
"this is how to do things if you are using MD5". The references to RFC 1864 can 
still stand. We are simply adding in an option to use other algorithms.


Code
----

SHA is avaliable form the following locations:

SHA.ZIP - Secure Hash Algorithm, written by Peter Gutmann in 1992.
ftp.dsi.unimi.it:/pub/security/crypt/code/SHS.tar.gz (this first one contains a 
file with the Peter Gutmann
implementation) 
ftp.dsi.unimi.it:/pub/security/crypt/code/gillogly-sha.tar.gz
ftp.dsi.unimi.it:/pub/security/crypt/code/sha.tar.gz
ftp.informatik.uni-hamburg.de:/pub/virus/texts/crypto/shs.zip 


Or if you want other goodies try :
http://www.openmarket.com/techinfo/applied.htm


		Phill

Received on Friday, 26 April 1996 11:35:56 UTC