Wang, Yu, and Yin, the team of Chinese cryptographers that successfully broke SHA-0 and SHA-1, announced new results against SHA-1 yesterday at Crypto's rump session. (Actually, Adi Shamir announced the results in their name, since she and her student did not receiveU.S. visas in time to attend the conference.)

Shamir presented few details -- and there's no paper -- but the time complexity of the new attack is 2^63. (Their previous result was 2^69; brute force is 2^80.) He did say that he expected Wang and her students to improve this result over the next few months. The modifications to their published attack are still new, and more improvements are likely over the next several months. There is no reason to believe that 2^63 is anything like a lower limit.

But an attack that's faster that's faster than 2^64 is a significant milestone. We've already done massive computations with complexity 2^64. Now that the SHA-1 collision search is squarely in the realm of feasibility, some research group will try to implement it. Writing working software will both uncover hidden problems with the attack, and illuminate hidden improvements. And while a paper describing an attack against SHA-1 is damaging, software that produces actual collisions is even more so.

The story of SHA-1 is not over. Again, I repeat the saying I've heard comes from inside the NSA: "Attacks always get better; they never get worse."

The link for this article located at Schneier on Security is no longer available.