SHA1 weakness benefits password crackers
Jens Steube, a co-author of the popular Hashcat password cracker, has discovered a weakness in the SHA1 cryptographic hashing technique that enables him to accelerate password cracking by about 20 per cent.
SHA1 always processes blocks of 512 bits (64 bytes). However, this data is expanded to 2,048 bits when the SHA1 hash value is generated – Steube calls this process "word expansion". Words are expanded via XOR operations, but some of these operations are redundant and can be eliminated. Using a few clever optimisations, the researcher managed to reduce the number of operations for a complete SHA1 calculation by about 20 per cent: instead of 880 operations, his optimised technique only required 694.
Incidentally, the weaknesses of the SHA1 hashing technique that have been identified over the past few years have nothing to do with the use of SHA1 in password storage. Successful attacks aim at creating collisions – those involve two sets of data that generate an arbitrary hash value which is identical for both sets. Password cracking, on the other hand, is about finding a specific data set that corresponds to a given hash value. However, no attack types that are faster than simply trying out all potential passwords are known to exist (except Time Memory Trade Offs, but these require huge amounts of hard disk space for their precomputed tables).
That simple SHA1 hashes are not a good choice for password storage is due to the fact that attackers can calculate a SHA1 hash and try out large numbers of passwords too quickly, even without Steube's latest optimisations. Optimised crackers can calculate many hundred million SHA1 hashes per second. Methods such as PBKDF2 or Bcrypt, on the other hand, are designed to require the largest possible amount of resources. In addition, BCrypt crackers are virtually unable to profit from GPUs due to the algorithm's high memory usage; only a few thousand BCrypt hashes per second are typically calculated.
Update (5/12/12 14:00): To call a way of accelerating the calculation of a SHA1 hash a weakness is at best an unfortunate word choice. After all, speed does feature on the list of desirable design aspects for cryptographic hashes, and that the implementation can be optimised in this respect does not constitute a vulnerability. While SHA1 password hashes may be cracked faster with the latest optimisations, SHA1 with or without optimisation remains generally unsuitable as a secure method for storing passwords. Considering the fact that SHA1 can be calculated many orders of magnitude faster than more suitable methods such as PBKDF2 or BCrypt, a 20% optimisation doesn't make a significant difference.