[Burt Kaliski: Pseudocollisions in MD5]
James M Galvin <galvin@tis.com> Mon, 26 April 1993 06:46 UTC
Received: from ietf.nri.reston.va.us by IETF.CNRI.Reston.VA.US id aa08828; 26 Apr 93 2:46 EDT
Received: from CNRI.RESTON.VA.US by IETF.CNRI.Reston.VA.US id aa08824; 26 Apr 93 2:46 EDT
Received: from SLEEPY.TIS.COM by CNRI.Reston.VA.US id aa20834; 26 Apr 93 2:46 EDT
Received: from sleepy.tis.com by sleepy.TIS.COM id aa29565; 26 Apr 93 6:38 GMT
Received: from tis.com by sleepy.TIS.COM id aa29563; 26 Apr 93 2:32 EDT
Received: from TIS.COM by TIS.COM (4.1/SUN-5.64) id AA02089; Mon, 26 Apr 93 02:33:35 EDT
Message-Id: <9304260633.AA02089@TIS.COM>
Reply-To: James M Galvin <galvin@tis.com>
To: snmp-sec-dev@tis.com
Subject: [Burt Kaliski: Pseudocollisions in MD5]
Date: Mon, 26 Apr 1993 02:33:34 -0400
Sender: ietf-archive-request@IETF.CNRI.Reston.VA.US
From: James M Galvin <galvin@tis.com>
Here is some more information about the suggestion that MD5 is vulnerable. Jim ------- Forwarded Message Message-ID: <9304240015.AA04170@RSA.COM> Sender: pem-dev-relay@TIS.COM From: burt@RSA.COM (Burt Kaliski) To: pem-dev@TIS.COM Date: Fri, 23 Apr 93 17:15:02 PDT Subject: Pseudocollisions in MD5 Following is a short note commenting on den Boer and Bosselaers' recent work on the MD5 message-digest algorithm. Feel free to email questions or further comments. - -- Burt Kaliski RSA Laboratories - ---------------------------------------------------------------------- \documentstyle[12pt]{article} \begin{document} \title{On ``Pseudocollisions'' in the MD5 Message-Digest Algorithm} \author{Burton S. Kaliski Jr. \\ {\tt burt@rsa.com} \and Matthew J.B. Robshaw \\ {\tt matt@rsa.com} \and RSA Laboratories \\ 100 Marine Parkway \\ Redwood City, CA 94065} \date{April 23, 1993} \maketitle A message-digest algorithm maps a message of arbitrary length to a ``digest'' of fixed length, and has three properties: Computing the digest is easy, finding a message with a given digest---``inversion''---is hard, and finding two messages with the same digest---``collision''---is also hard. Message-digest algorithms have many applications, including digital signatures and message authentication. RSA Data Security's MD5 message-digest algorithm, developed by Ron Rivest \cite{rfc-md5}, maps a message to a 128-bit message digest. Computing the digest of a one-megabyte message takes as little as a second. While no message-digest algorithm can yet be {\em proved} secure, MD5 is believed to be at least as good as any other that maps to a 128-bit digest. Inversion should take about $2^{128}$ operations, and collision should take about $2^{64}$ operations. No one has found a faster approach to inversion or collision. Recent work by den Boer and Bosselaers \cite{den-boer-md5} presents a special kind of ``pseudocollision'' in MD5's internal compression function, which maps a 512-bit message block $x$ and a 128-bit input state $s$ to a 128-bit output state. They show how to find a message block $x$ and two related input states $s_1$ and $s_2$ that yield the same output state: $f(x,s_1)$ = $f(x,s_2)$. Their well-thought approach exploits structural properties of the collision function to find a pseudocollision in about $2^{16}$ operations, much less than one would expect. Practical implications of this pseudocollision work to the security of MD5 are not evident. While a real collision in MD5 implies a pseudocollision (or a ``pseudo-inversion''), a pseudocollision need not imply a real collision. Indeed, a real collision, since it involves two different messages, would almost always involve {\em different} message blocks $x_1$ and $x_2$ such that $f(x_1,s_1) = f(x_2,s_2)$, but the pseudocollisions have the same message blocks. Moreover, the input states $s_1$ and $s_2$ would generally be unrelated, but the pseudocollisions' input states are the same except for four bits. There does not seem to be any way to extend den Boer and Bosselaers' approach to anything beyond the special pseudocollisions, a limitation they readily admit. It is reasonable, therefore, to believe that MD5 remains secure. While den Boer and Bosselaers have found interesting structural properties in MD5, the properties seem only to lead to special pseudocollisions and not anything approaching real collisions. Further research, of course, will give a better understanding of the strengths of MD5 and other message-digest algorithms, with the eventual hope that such algorithms can, in some sense, be proved secure. \bibliographystyle{plain} \begin{thebibliography}{1} \bibitem{den-boer-md5} Bert den~Boer and Antoon Bosselaers. \newblock Collisions for the compression function of {MD5}. \newblock In {\it Advances in Cryptology --- Eurocrypt '93}, 1993. \newblock Preprint. \bibitem{rfc-md5} R.L. Rivest. \newblock {\it {RFC} 1321: The {MD5 Message-Digest Algorithm}}. \newblock Internet Activities Board, April 1992. \end{thebibliography} \end{document} ------- End of Forwarded Message
- [Burt Kaliski: Pseudocollisions in MD5] James M Galvin