SHA-1 brute-force attack trimmed by 21% – paper from Oslo password hacking conference

Two months ago, we wrote about the conclusion of the NIST Cryptographic Hash Algorithm Competition.

The winner was Keccak – now officially dubbed SHA-3.

Despite the formal ratification of this new standard, NIST’s earlier hashes remain commonly used. Indeed, we can expect to see SHA-1 and SHA-2 in the wild for years – possibly even for decades.

SHA-1, in particular, is still widely encountered in password hashing.

Password hashing is where you use a cryptographic hash function in some part of your password archival system to create a one-way function.

A one-way function is a process that’s easy to compute in one direction, but complex – or, better yet, computionally infeasible – to work out in reverse.

So, if you store one-way password hashes instead of the actual passwords, attackers who steal your database can’t directly recover those passwords. They have to try password after password themselves, until they get lucky.

→ Using a one-way function to store passwords is not a replacement for keeping your password database secure. It’s additional security that offers a touch of defence-in-depth, just in case your server does get broken into.

Because one-way functions can’t be computed in reverse, cracking cryptographically-hashed passwords is inevitably a brute-force affair. It means computing a one-way function over and over again.

As a result, password cracking experts put a lot of effort into improving the performance of widely-used password hashing algorithms, notably including SHA-1.

In June 2012, for example, researchers magnum and JimF (Jim Fougeron) contributed code to the password cracker John the Ripper that boosted raw SHA-1 password hashing speeds by 80%.

And, for the same release, Tavis Ormandy came up with an optimised implementation offering a 115% performance improvement, albeit limited to passwords under 15 characters.

→ Password crackers are easily abused. You probably want to control their use inside your organisation. But they have a legitimate defensive purpose: to find poor password hygiene on your own network before the bad guys do.

Now, Jens Steube, author of the pasword cracking tools in the hashcat family, has added to the optimisations against SHA-1 when cracking passwords.

Steube described his work in a paper at the recent Passwords^12 conference in Oslo, Norway.

Steube’s password cracking improvements reduce by 21% the number of computer instructions needed to compute a SHA-1 hash. This may allow previous optimisations – such as the the ones described above – to be tweaked yet further for additional speed.

Steube noticed that SHA-1’s “inner loop” can be usefully slimmed down if you are repeatedly computing hashes from input data in which only the first input word (32 bits, or four bytes) changes each time.

For a password attack, this can easily be arranged.

Greatly oversimplified, the SHA-1 algorithm consumes its input in blocks of sixteen 32-bit words (512 bits, or 64 bytes), mixing each block into a cumulative hash of five 32-bit words (160 bits, or 20 bytes).

for block in blocks() do
   for i = 17 to 80 do
      -- each step here extends the original 16-word input
      -- block to 80 words by adding one word made by mixing 
      -- together four of the previous sixteen words.     
      block[i] = minimixtogether(block,i)
   end
   
   for i = 1 to 80 do
      -- each step here mixes one of the words from the 80-word
      -- "extended block" into the five-byte hash accumulator
      hash = giantmixtogether(block,i)
   end
end

The giantmixtogther() function that scrambles the extended input into the hash uses a range of different operations, including NOT, AND, OR, XOR, ADD and ROL (rotate left).

But the minimixtogether() function used to condition the input data uses only XOR and ROL. Because of its relative simplicity, Steube found a way to skip the minimixtogether() loop, and to calculate the “expanded” input values block[17] to block[80] directly inside the giantmixtogether() loop.

Steube’s method still needs some precalculation, but multiple separate hash evaluations can share this precalculated data if only the first block (i.e. the first four characters) of the input has changed.

If you were hashing a randomly-selected series of files, for example, this would do you no good.

But when conducting a brute force attack against passwords, it’s a simple matter to put your input into a suitable sequence so that the first four characters change most rapidly, followed by the rest of the password. (Just imagine a car odometer with the digits reversed.)

If you can do this, then implemeting Steube’s tweaks will make your code run 25% faster. Just like that.

And there you have it: yet another reminder that security is an arms race.