Hash algorithms are widely used to store passwords in a (relatively) secure manner by converting various length plaintexts into standard length scrambles in a manner that cannot mathematically be reversed. When a user logs on with a plaintext password, it is hashed and compared to the stored hashed database. The SHA1 hash, however, is no longer considered to be strong.
But if that isn’t already enough, researcher Jens Steube (aka Atom, developer of the HashCat password recovery program) presented a new method for cracking SHA1 at the Passwords^12 conference at Oslo university on Tuesday, improving crack effort by 21%. He did this by focusing on the word expansion phase of the SHA1 transformation. Its purpose is to generate a bigger volume of data out of the input data, and is, he says, “where the weakness is located in SHA1.”
Although cryptanalysts have claimed attacks on SHA1, there are none known to be in use. The only way to break such one-way hashes is to run plaintext guessed passwords against the algorithm until an identical hash is generated. This is brute forcing. Steube, however, “has found an algorithmic shortcut in SHA-1 calculation that makes the computation easier, thus reducing the time needed to successfully ‘brute force’ an attack,” comments Tal Be'ery in an Imperva blog today.
His technique, explained cryptographer Jean-Philippe Aumasson in an email to Ars Technica, “reduces the computational cost of testing candidate passwords when one is given the SHA1 hash of an unknown password. In mathematical terms, it does so by avoiding redundant operations – that is, operations that have to be performed regardless of the password tested."
The weakness is in the XOR function within the word expansion phase. “Logical instructions cannot overflow, but arithmetic ones can,” says Steube. “If the Word-Expansion had used ADD, it would have been impossible to exploit it,” he notes. Exploit it he does by precomputing the word expansion part of the transformation, and he provides a PERL script to automate the process. The result reduces the SHA1 instruction count from 828 to 694, an effort saving of 21.1%.
“Best option?” says Tal Be'ery. “Use a hash function from SHA-2 family, such as the SHA256.” And whichever hash function you chose, don't forget to salt it.