By John Leyden
19th August 2005
Crypto researchers have discovered a new, much faster, attack against
the widely-used SHA-1 hashing algorithm. Xiaoyun Wang, one of the team
of Chinese cryptographers that demonstrated earlier attacks against
SHA-0 and SHA-1, along with Andrew Yao and Frances Yao, have
discovered a way to produce a collision in SHA-1 over just 263 hash
operations compared to 269 hash operations previously. A brute force
attack should take 280 operations.
One-way hashing is used in many applications such as creating
checksums used to validate files, creating digital certificates,
authentication schemes and in VPN security hardware. Collisions occur
when two different inputs produce the same output hash. In theory this
might be used to forge digital certificates but it shouldn't be
possible to find collisions except by blind chance. Wang and her team
have discovered an algorithm for finding collisions much faster than
brute force. The researchers released a paper (PDF) on their finding
at the Crypto 2005 conference in Santa Barbara, California earlier
"The SHA-1 collision search is squarely in the realm of feasibility,"
writes noted cryptographer Bruce Schneier in a posting to his web log.
"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 US National Institute of Standards and Technology (NIST) recently
advised the US government to phase out SHA-1 in favor of SHA-256 and
SHA-512. NIST is holding a workshop on the subject in late October. =AE
Sept 16-18th, 2005
San Diego, California