Cryptographic expert Bruce Schneier has reported that the SHA-1 hashing algorithm (define) , upon which several major applications such as SSL (define) and PGP (define) depend for secure digital signing, has been broken.
While the computing resources needed to defeat the protection SHA-1 provides remain impressive and out of the reach of most, the discovery set a few experts back, including a security technology group manager at the National Institute of Standards and Technology (NIST) who as recently as last week declared SHA-1 secure for the foreseeable future.
SHA-1 is used to generate digital signatures. By processing a message or file with SHA-1, applications produce a hashed version of the data called a digest file. The hash, or digest, is much smaller than the original file. In theory, the hashes from no two signed files should ever be the same, meaning a file or message that’s been tampered with will yield a different hash from the original. Cases where two differing files produce the same hash are referred to as a “collision.”
According to Schneier, a team of Chinese researchers who previously demonstrated weaknesses in the MD5 hashing algorithm (define) have demonstrated that they can produce a collision in SHA-1-hashed data much sooner than previously suspected: within 269 hashing operations instead of 280.
The computing hardware needed to generate a collision is still out of reach of all but several governmental agencies, and it would take an impractical amount of time to generate a collision, but the researchers’ demonstration proves to the cryptographic community that it’s time to look for SHA-1’s replacement, since most researchers assume that attacks against a given algorithm will improve over time.
Faith in SHA-1 was such that William Burr, a security technology group manager at the National Institute of Standards and Technology (NIST), said just last week that the algorithm had not been broken “and there is not much reason to suspect that it will be soon.” NIST has recommended that SHA-1 remain in use through 2010. That timetable will, no doubt, change.
