Xiaoyun Wang, one of the team of Chinese cryptographers that
successfully broke SHA-0 and SHA-1, along with Andrew Yao and Frances
Yao, announced new results against SHA-1 at Crypto's rump
session. (Actually, Adi Shamir announced the results in their name,
since she and her student did not receive U.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 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."
Details of the SHA break:
<http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html>
NIST's Hash Function Workshop, to be held in late October:
<http://www.csrc.nist.gov/pki/HashWorkshop/index.html>
Effects of the attack on S/MIME, TLS, and IPsec:
<http://www.educatedguesswork.org/movabletype/archives/2005/07/deploying
_a_new.html> or <http://tinyurl.com/cz4lf>
Xiaoyun Wang's two papers from Crypto:
Efficient Collision Search Attacks on SHA-0
<http://202.194.5.130/admin/infosec/download.php?id=1>
Finding Collisions in the Full SHA-1
<http://202.194.5.130/admin/infosec/download.php?id=2>
The rest of her papers:
<http://www.infosec.sdu.edu.cn/people/wangxiaoyun.htm>
Story of them being denied visas to attend the conference:
<http://www.schneier.com/blog/archives/2005/08/chinese_cryptog.html>
<http://www.navyseals.com/community/articles/article.cfm?id=7757>
