Friday, August 19, 2005 9:52 PM bart

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 | Technorati | Blinklist | Furl | reddit | DotNetKicks

Filed under:

Comments

No Comments