[Content-MD5 and Message Digest Authentication.], MD5 broken.
hallam@w3.org
Fri, 26 Apr 96 14:26:10 -0400
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