B# .NET Blog

A couple of months ago I did a post on "SHA-1 also insecure?". SHA-1 is one of today's hashing algorithms (hash function) that's widely used. Simply stated, a hash is a one-way function H that takes a variable-length message M as a parameter and returns a fixed-length hash value h, i.e. h = H(M). The idea of such a hash function is to produce a fingerprint that represents the original message, e.g. to be used in "authentication" of a message (checking a message's integrity against tampering for instance). Such a hash algorithm needs to meet three properties:

• One-way: it should be computationally infeasible to compute message M given the hash value h.
• Weak collision resistance: given a message M1 it should be computationally infeasible to find another different message M2 such that H(M1) = H(M2).
• Strong collision resistance: it should be computationally infeasible to find a pair of different messages (M1, M2) such that H(M1) = H(M2).

This week (Crypto 2005 conference in Santa Barbara, California), two papers have been published by Xiaoyun Wang from Shandong University (China) about finding collisions in SHA-0 and SHA-1 (well, these were already published before but have now been presented at the conference):

• Efficient Collision Search Attachs on SHA-0
• Finding Collisions in the Full SHA-1

The newly announced results (not yet in the papers) show that an attack of complexity 2⁶³ is possible and it's likely that the complexity is still going to drop. With a complexity of 2⁶³ finding SHA-1 collisions becomes feasible.