Friday, August 19, 2005 9:52 PM
SHA-1 also insecure? (cont'd)
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):
The newly announced results (not yet in the papers) show that an attack of complexity 263 is possible and it's likely that the complexity is still going to drop. With a complexity of 263 finding SHA-1 collisions becomes feasible.Del.icio.us
| Digg It
Filed under: Security