Hashing passwords: SHA-512 can be stronger than bcrypt (by doing more rounds)

On a server, user passwords are usually stored in a cryptographically secure way, by running the plain passwords through a one-way hashing function and storing its output instead. A good hash function is irreversible.

Leaving dictionary attacks aside and by using salts, the only way to find the original input/password which generated its hash, is to simply try all possible inputs and compare the outputs with the stored hash (if the hash was stolen). This is called bruteforcing.

Speed Hashing

With the advent of GPU, FPGA and ASIC computing, it is possible to make bruteforcing very fast - this is what Bitcoin mining is all about, and there’s even a computer hardware industry revolving around it. Therefore, it is time to ask yourself if your hashes are strong enough for our modern times.

bcrypt was designed with GPU computing in mind and due to its RAM access requirements doesn’t lend itself well to parallelized implementations. However, we have to assume that computer hardware will continue to become faster and more optimized, therefore we should not rely on the security margin that bcrypt’s more difficult implementation in hardware and GPUs affords us for the time being.

For our real security margin, we should therefore only look at the so-called “variable cost factor” that bcrypt and other hashing functions support. With this feature, hashing function can be made arbitrarily slow and therefore costly, which helps deter brute-force attacks upon the hash.

This article will investigate how you can find out if bcrypt is available to you, and if not, show how to increase the variable cost factor of the more widely available SHA-512 hashing algorithm.

Do you have bcrypt?

If you build your own application (web, desktop, etc.) you can easily find and use bcrypt libraries (e.g. Ruby, Python, C, etc.).

However, some important 3rd party system programs (Exim, Dovecot, PAM, etc.) directly use glibc’s crypt() function to authenticate a user’s password. And glibc’s crypt(), in most Linux distributions except BSD, does NOT implement bcrypt! The reason for this is explained here.

If you are not sure if your Linux distribution’s glibc supports bcrypt (man crypt won’t tell you much), simply try it by running the following C program. The function crypt() takes two arguments:

char *crypt(const char *key, const char *salt);

For testing, we’ll firstly generate a MD5 hash because that is most certainly available on your platform. Add the following to a file called crypttest.c:

#include <stdio.h>
#include <crypt.h>

int main(void) {
 char *hashed;
 hashed = crypt("xyz", "$1$salthere");
 puts(hashed);
 return 0;
}

Suppose xyz is our very short input/password. The $1$ option in the salt argument means: generate a MD5 hash. Type man crypt for an explanation.

Compile the C program:

gcc -o crypttest -lcrypt crypttest.c

Run it:

./crypttest

The output:

$1$salthere$BEMucfLXR/yP5di4BYptX1

Next, in the C program change $1$ to $6$ which means SHA-512 hash. Recompile, run, and it will output:

$6$salthere$X.eZx5ScCKO4mHW1o5dqLB77qtuUtbgVr52N1LGVHWONeoav/p77GEcJ4zytaMk8cesMiF2rKL7weLzp3BUlq1

Next, change $6$ to $2a$ which means bcrypt. Recompile, run, and the output on my distribution (Debian) is:

Segmentation fault

So, on my Debian system, I’m out of luck. But, I’ll simply use more rounds of SHA-512 to make hash bruteforcing arbitrarily costly. It turns out that SHA-512 (bcrypt too) supports an arbitrary number of rounds.

More rounds of SHA-512

glibc’s crypt() allows specification of the number of rounds of the main loop in the algorithm.  This feature is strangely absent in the man crypt documentation, but is documented here. glibc’s default of rounds for a SHA-512 hash is 5000. You can specify the number of rounds as an option in the salt argument. We’ll start with 100000 rounds.

In the C program, pass in as argument salt the string $6$rounds=100000$salthere . Recompile and measure the execution time:

time ./crypttest

Output:

$6$rounds=100000$salthere$F93c6wdBjaMn9c8VY.ZBPJfA2vsk1z.YmEJhm8twyUY/zPbZpdm73hQ2ePb.vTeu0d014pB076S1JW3VCCfhj.
real 0m0.048s

It took 48 milliseconds to generate this hash. Let’s increase the rounds by a factor of 10, to 1 million:

time ./crypttest

Output:

$6$rounds=1000000$salthere$9PJ4NaW6zmi/iuQdVtOvFXB3wdtNC7k5GOHRtnEtpJAMdBJ7asunZpCuqfjyx2vZdqRRaS/z33EXI9Z.nkNEb.
real 0m0.455s

We see that generation of one hash took 10 times longer, i.e. about half a second. It seems to be a linear relationship.

Glibc allows setting the cost factor (rounds) from 1000 to 999,999,999.

The Proof lies in the Bruteforcing

Remember that above we have chosen the input/password xyz (length 3). If we only allow for the characters [a-z], we get 26³ possibilities, or 17576 different passwords to try. With 48 ms per hash (100000 rounds) we expect the bruteforcing to have an upper limit of about 17576 x 0.048 s = 843 seconds (approx. 14 minutes).

We will use a hash solver called hashcat to confirm the expected bruteforcing time. Hashcat can use GPU computing, but I’m missing proper OpenCL drivers, so my results come from slower CPU computing only. But that doesn’t matter. The crux of the matter is that the variable cost factor (rounds) directly determines the cracking time, and it will have to be adapted to supposed computer hardware that might do the cracking.

Now we’re going to solve above SHA-512 hash (password/input was xyz) which was calculated with 100000 rounds:

./hashcat64.bin --force -m 1800 -a 3 '$6$rounds=100000$salthere$F93c6wdBjaMn9c8VY.ZBPJfA2vsk1z.YmEJhm8twyUY/zPbZpdm73hQ2ePb.vTeu0d014pB076S1JW3VCCfhj.'

$6$rounds=100000$salthere$F93c6wdBjaMn9c8VY.ZBPJfA2vsk1z.YmEJhm8twyUY/zPbZpdm73hQ2ePb.vTeu0d014pB076S1JW3VCCfhj.:xyz

Session.Name...: hashcat
Status.........: Cracked
Input.Mode.....: Mask (?1?2?2) \[3\]
Hash.Target....: $6$rounds=100000$salthere$F93c6wdBjaMn9c8...
Hash.Type......: sha512crypt, SHA512(Unix)
Time.Started...: Fri Sep 9 21:34:38 2016 (13 mins, 30 secs)
Speed.Dev.#1...: 52 H/s (13.42ms)
Recovered......: 1/1 (100.00%) Digests, 1/1 (100.00%) Salts
Progress.......: 42024/80352 (52.30%)
Rejected.......: 0/42024 (0.00%)
Restore.Point..: 412/1296 (31.79%)

Note that it took about 14 minutes to find the plaintext password xyz from the hash, which confirms above estimation.

Now let’s try to crack a bcrypt hash of the same input xyz which I generated on this website:

./hashcat64.bin --force -m 3200 -a 3 '$2a$08$wOT24w1Ki.or5CACwuAqR.D933N4GcwdV6zsWbmUQWB6UXsgY8KVi'

$2a$08$wOT24w1Ki.or5CACwuAqR.D933N4GcwdV6zsWbmUQWB6UXsgY8KVi:xyz

Session.Name...: hashcat
Status.........: Cracked
Input.Mode.....: Mask (?1?2?2) \[3\]
Hash.Target....: $2a$08$wOT24w1Ki.or5CACwuAqR.D933N4GcwdV6...
Hash.Type......: bcrypt, Blowfish(OpenBSD)
Time.Started...: Fri Sep 9 13:59:46 2016 (3 mins, 30 secs)
Speed.Dev.#1...: 222 H/s (11.13ms)
Recovered......: 1/1 (100.00%) Digests, 1/1 (100.00%) Salts
Progress.......: 44800/80352 (55.75%)
Rejected.......: 0/44800 (0.00%)
Restore.Point..: 640/1296 (49.38%)

Note that bcrypt’s cost factor in this example is 08 (see bcrypt’s documentation for more info on this). The bruteforce cracking time of the same password took only 3 minutes and 30 seconds. This is about 3 times faster than the SHA-512 example, even though bcrypt is frequently described as being slow. This variable cost factor is often overlooked by bloggers who too quickly argue for one or the other hash function.

Conclusion

bcrypt is suggested in many blog posts in favor of other hashing algorithms. I have shown that by specifying a variable cost factor (rounds) to the SHA-512 algorithm, it is possible to arbitrarily increase the cost of bruteforcing the hash. Both SHA-512 and bcrypt can therefore be not said to be faster or slower than the other.

The variable cost factor (rounds) should be chosen in such a way that even resourceful attackers will not be able to crack passwords in a reasonable time, and that the number of authenticating users to your server won’t consume too much CPU resources.