From root Fri Apr 23 18:09:11 1993 Return-Path: Received: by sqwest.west.sq.com (5.65c/IDA-AIX32) id AA19289; Fri, 23 Apr 1993 18:09:10 -0700 Received: from RSA.COM by van-bc.wimsey.com with smtp (Smail3.1.28.1 #12) id m0nmYNw-0000V6C; Fri, 23 Apr 93 17:46 PDT Received: by RSA.COM id AA04197; Fri, 23 Apr 93 17:17:14 PDT Message-Id: <9304240017.AA04197@RSA.COM> Date: Fri, 23 Apr 93 17:15:07 PDT From: burt@RSA.COM (Burt Kaliski) To: rsaref-users@RSA.COM Subject: Pseudocollisions in MD5 Sender: rsaref-users-request@RSA.COM Status: OR 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}