From Information to Intelligence

Hash function are a key component of any cryptosystem. The underlaying idea of a hash function is simple : it is a one way function used to generate a fixed length hash (signature) for a given entry. A hash function is secure if there is no mean to find a collosion for a given entry. In other word that you can’t craft a file that will have the same hash than a given file easily. Of course because hash have a fixed length, collision is unavoidable however until you can create a collision at will, hash function are “secure”. Among the numerous uses of theses signatures some typical example are file signature and binary integrity. The most well known hash function are the old md5 and the standardized SHA (SHA-1 for example).

At EUROCRYPT’05 Wand and al described a new class of attack on most hash function including MD4, M5, SHA-1, SHA-0. This attack allows an attacker to find a collision for any hash in a reasonnable amout of time. This make practical attacks against real protocol possible.

Wang message modification technique does not allow the attacker to choose the block that will collides. Hence you can’t simply switch one binary for an other. However the technique allows to have an arbitrary prefix, and the Merkel-Damgard construction allows to add a common suffix.

Putting all together it means that an attacker can choose a prefix and a suffix but have to somehow hide the collinding block. That is why real world application of this attack are not so obvious. Here is some real world application of such attack:

• Crafting document that have the same signature but a different display. This work only if the document have the ability to mask the colliding block. For example conditional display in PS or color change in PDF. Affected file type are Word, PDF, PS, TIFF. This have been Daum and al and Extended by Gebhardt and al
• Having two different X509 certificates for the same name but with a different RSA moduli by Lenstra and al
• Protocol authentification handshake attack : A recent attack show how to partially recover APOP password . APOP is defined in the POP3 protocol as a secure mean to perform authentification. This was discovered independently by G. Leurent and Y. Sasaki

As one can see the impact of this attack is important but the impact is not that big. File collision is a problem but a real signature protocol requiers that the hash is signed with the private key. This is even use on Linux package that now use GPGP signature. APOP attack is nice, but POP3 protocol is a clear text protocol and APOP is not the good way to secure it.

Now what ? There is two distinct directions : New hash functions and new attacks. New attacks may be found on web application that use hash for many purposes. Rootkit can also use it to become harder to detect. Hash function is still the part of the cryptography that evolve the more quickly.

Local link:

How to Break MD5 and Other Hash Functions by Xiaoyun Wang and Hongbo Yu

A Note on the Practical Value of Single Hash Collisions for Special File Formats by Max Gebhardt, Georg Illies, Werner Schindler

On the possibility of constructing meaningful hash collisions for public keys by Arjen Lenstra and Benne de Weger

Message Freedom in MD4 and MD5 Collisions. Application to APOP by G. Leurent