Geeks With Blogs
ex-blog Information security world

From Bruce Schneier blog:

SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing.

The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper announcing their results:

  • collisions in the the full SHA-1 in 2**69 hash operations, much less than the brute-force attack of 2**80 operations based on the hash length.

  • collisions in SHA-0 in 2**39 operations.

  • collisions in 58-round SHA-1 in 2**33 operations

[Update] More information is available in the paper Collision Search Attacks on SHA1.

Eric Rescorla blogs next steps for hash functions:

Here are a few alternatives that might work:

  • Randomized hashing The whole reason why this attack works is that the attacker knows the exact message you're going to hash. If you prefix the message with a random value, this effectively defeats the attack. So, when you sign a message you would sign H(random || message) instead of H(message) [0]. In particular, CAs should immediately start using unpredictable serial numbers. [1]
  • A non-MDx-based hash function All of the major standard hash functions ultimately derive from MD4. It's possible to design hash functions based on block ciphers (see Tom Shrimpton's slides) for an overview. Unfortunately, as I understand it you can't prove security for these constructions in a realistic model of the underlying algorithm. However, there's some hope that you would have to make a pretty serious dent in that block cipher in order to break the hash.

BTW, Russian hash function GOST.R 34.11-94 was always based on block cipher GOST 28147-89.

[Update 03/02/2005] Valery Pryamikov provided good write-up in his Musings about practical implications of recent SHA-1 attack article

Posted on Wednesday, February 16, 2005 8:45 AM Security | Back to top

Copyright © John Doe | Powered by: