pseudocollisions in md following is a short note commenting on den boer and bosselaers recent work on the md message digest algorithm feel free to email questions or further comments burt kaliski rsa laboratories documentstyle pt article begin document title on pseudocollisions in the md message digest algorithm author burton s kaliski jr tt burt rsa com and matthew j b robshaw tt matt rsa com and rsa laboratories marine parkway redwood city ca date april 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 md message digest algorithm developed by ron rivest cite rfc md maps a message to a 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 md is believed to be at least as good as any other that maps to a bit digest inversion should take about operations and collision should take about operations no one has found a faster approach to inversion or collision recent work by den boer and bosselaers cite den boer md presents a special kind of pseudocollision in md s internal compression function which maps a bit message block x and a bit input state s to a bit output state they show how to find a message block x and two related input states s and s that yield the same output state f x s f x s their well thought approach exploits structural properties of the collision function to find a pseudocollision in about operations much less than one would expect practical implications of this pseudocollision work to the security of md are not evident while a real collision in md 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 and x such that f x s f x s but the pseudocollisions have the same message blocks moreover the input states s and s 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 md remains secure while den boer and bosselaers have found interesting structural properties in md 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 md and other message digest algorithms with the eventual hope that such algorithms can in some sense be proved secure bibliographystyle plain begin thebibliography bibitem den boer md bert den boer and antoon bosselaers newblock collisions for the compression function of md newblock in it advances in cryptology eurocrypt newblock preprint bibitem rfc md r l rivest newblock it rfc the md message digest algorithm newblock internet activities board april end thebibliography end document
