Date: Sun, 25 Apr 93 13:53:36 PDT Reply-To: Return-Path: Message-ID: Mime-Version: 1.0 Content-Type: text/plain From: surfpunk@osc.versant.com (cfrhqbpbyyvfvba) To: surfpunk@osc.versant.com (SURFPUNK Technical Journal) Subject: [surfpunk-0081] CRYPT: Pseudocollision in MD5; Pseudoencryption phone Recently rumor has gone around about whether MD5 has been solved. Here's a message from RSA about it. Then a parable about the clipper. Let me elaborate on the MD5 thing. Someone asks whether MD5's inverse problem or collision problem being solved would let others decrypt your messages. Perhaps indirectly, but really what it would allow you to do is to forge messages. If my friend Bob sends a secure message, he signs not the message, but rather its MD5 hash. If I wanted to send a message and sign it with his signature, to impersonate him, I would find one of his public messages with his signature. Then I could come up with a message that has the same hashing as his public message. This might involve just adding new space characters to the message I want him to sign. Then I copy his signature from his public message, and put it on my message. It works because it signs the same hash code. Because various control messages are also often signed with MD5, it may also let me create bogus certificates of public keys. Down this path there may be some ways of decrypting other people's messages, by providing them a public key that I can invert, but letting them think it is a public key that their friend can invert. But this is more indirect. Some people get upset that SURFPUNK doesn't give away enough secrets. So here's one: my face is one of those hidden in the cypherpunk article in the new issue of WIRED. strick ________________________________________________________________________ ________________________________________________________________________ Date: Fri, 23 Apr 93 17:15:07 PDT From: burt@RSA.COM (Burt Kaliski) To: rsaref-users@RSA.COM 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} ________________________________________________________________________ Thanks: iansmith@cc.gatech.edu (Ian Smith) Newsgroups: alt.privacy.clipper,sci.crypt Subject: A Parable. References: <1993Apr20.013747.4122@cs.sfu.ca> <1993Apr21.210353.15305@microsoft.com> Organization: Partnership for an America Free Drug scottmi@microsoft.com (Scott Miller (TechCom)) writes: >Stikes me that all this concern over the government's ability >to eavesdrop is a little overblown... what can't they do today? >My understanding is that they already can tap, listen, get access >exc. to our phone lines, bank records, etc. etc again. Well, they can't listen in on much of mine, since I already use cryptography for much of my electronic mail, and will start using it for my telephony as soon as practical. However, allow me to tell a parable. There was once a far away land called Ruritania, and in Ruritania there was a strange phenonmenon -- all the trees that grew in Ruritainia were transparent. Now, in the days when people had lived in mud huts, this had not been a problem, but now high-tech wood technology had been developed, and in the new age of wood, everyone in Ruritania found that their homes were all 100% see through. Now, until this point, no one ever thought of allowing the police to spy on someone's home, but the new technology made this tempting. This being a civilized country, however, warrants were required to use binoculars and watch someone in their home. The police, taking advantage of this, would get warrants to use binoculars and peer in to see what was going on. Occassionally, they would use binoculars without a warrant, but everyone pretended that this didn't happen. One day, a smart man invented paint -- and if you painted your house, suddenly the police couldn't watch all your actions at will. Things would go back to the way they were in the old age -- completely private. Indignant, the state decided to try to require that all homes have video cameras installed in every nook and cranny. "After all", they said, "with this new development crime could run rampant. Installing video cameras doesn't mean that the police get any new capability -- they are just keeping the old one." A wise man pointed out that citizens were not obligated to make the lives of the police easy, that the police had survived all through the mud hut age without being able to watch the citizens at will, and that Ruritania was a civilized country where not everything that was expedient was permitted. For instance, in a neighboring country, it had been discovered that torture was an extremely effective way to solve crimes. Ruritania had banned this practice in spite of its expedience. Indeed, "why have warrants at all", he asked, "if we are interested only in expedience?" A famous paint technologist, Dorothy Quisling, intervened however. She noted that people might take photographs of children masturbating should the new paint technology be widely deployed without safeguards, and the law was passed. Soon it was discovered that some citizens would cover their mouths while speaking to each other, thus preventing the police from reading their lips through the video cameras. This had to be prevented, the police said. After all, it was preventing them from conducting their lawful surveilance. The wise man pointed out that the police had never before been allowed to listen in on people's homes, but Dorothy Quisling pointed out that people might use this new invention of covering their mouths with veils to discuss the kidnapping and mutilation of children. No one in the legislature wanted to be accused of being in favor of mutilating children, but then again, no one wanted to interfere in people's rights to wear what they liked, so a compromise was reached whereby all homes were installed with microphones in each room to accompany the video cameras. The wise man lamented few if any child mutilations had ever been solved by the old lip reading technology, but it was too late -- the microphones were installed everwhere. However, it was discovered that this was insufficient to prevent citizens from hiding information from the authorities, because some of them would cleverly speak in languages that the police could not understand. A new law was proposed to force all citizens to speak at all times only in Ruritanian, and, for good measure, to require that they speak clearly and distinctly near the microphones. "After all", Dorothy Quisling pointed out, "they might be using the opportunity to speak in private to mask terrorist activities!" Terrorism struck terror into everyone's hearts, and they rejoiced at the brulliance of this new law. Meanwhile, the wise man talked one evening to his friends on how all of this was making a sham of the constitution of Ruritania, of which all Ruritanians were proud. "Why", he asked, "are we obligated to sacrifice all our freedom and privacy to make the lives of the police easier? There isn't any real evidence that this makes any big dent in crime anyway! All it does is make our privacy forfeit to the state!" However, the wise man made the mistake of saying this, as the law required, in Ruritanian, clearly and distinctly, and near a microphone. Soon, the newly formed Ruritanian Secret Police arrived and took him off, and got him to confess by torturing him. Torture was, after all, far more efficient than the old methods, and had been recently instituted to stop the recent wave of people thinking obscene thoughts about tomatoes, which Dorothy Quisling noted was one of the major problems of the new age of plenty and joy. ________________________________________________________________________ ________________________________________________________________________ The SURFPUNK Technical Journal is a dangerous multinational hacker zine originating near BARRNET in the fashionable western arm of the northern California matrix. Quantum Californians appear in one of two states, spin surf or spin punk. Undetected, we are both, or might be neither. ________________________________________________________________________ Send postings to , subscription requests to . MIME encouraged. Xanalogical archive access soon. Don't tell our lawyers. ________________________________________________________________________ ________________________________________________________________________