We should have seen this comming.

SHA1, SHA2, SHA3, what’s the next hash I’m going to see.

The Feb 7 FWC.com article "Hashing out encription" first paragraph reads:

Federal agencies have been put on notice that National Institute ofStandards and Technology officials plan to phase out a widely usedcryptographic hash function known as SHA-1 in favor of larger andstronger hash functions such as SHA-256 and SHA-512.

A little further down William Blurr, a NIST security guru is quoted:

"There’s really no emergency here," Burr said. "But you should beplanning how you’re going to transition — whether you’re a vendor or auser — so that you can do better cryptography by the next decade."

So are we suprised by what appeared on Schneier’s Blog yesterday:

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 quietlycirculating a paper announcing their results:

  • collisions in the the full SHA-1 in 2**69 hash operations, muchless than the brute-force attack of 2**80 operations based on the hashlength.
  • collisions in SHA-0 in 2**39 operations.
  • collisions in 58-round SHA-1 in 2**33 operations.

This attack builds on previous attacks on SHA-0 and SHA-1, and is amajor, major cryptanalytic result. It pretty much puts a bullet intoSHA-1 as a hash function for digital signatures (although it doesn’taffect applications such as HMAC where collisions aren’t important).

The paper isn’t generally available yet. At this point I can’t tellif the attack is real, but the paper looks good and this is a reputableresearch team.

More details when I have them.

The combination of the two messages makes one wonder doesn’t it.

Anyway, my main worry about all this has to do with DNSSEC that uses RSA/SHA1 based signatures.

I am not a cryptanalist and I confess I know far less than I would like to know on this subject but I figure that given the pre-defined structure of the material being hashed (a RRset wich contains well defined fields that can only have well defined vallues such as type codes) an exploit would take more than 2^33 ops. I need education… How many orders of magnitude does one gain by needing structure?

Leave a Reply

Your email address will not be published. Required fields are marked *

*