11

First: I asked this question on stackoverflow and was kindly asked to post this here again. See the original question here.

According to the [early] doc pages of the new PHP 5.5 password hashing/encrypting API the used algorithm CRYPT_BLOWFISH is "strongest algorithm currently supported by PHP" (please do a full text search to find the quote on the page).

My question is: Can this be proven with some numbers, benchmarks etc. ?

According to the PHP's crypt() doc page CRYPT_BLOWFISH uses 22 char salt and generates a 60 char hash, and CRYPT_SHA512 uses a 16 char salt and generates a 118 char hash. Both algorithms have changeable cost factors, so at first view, SHA512 looks stronger (because longer).

Community
  • 1
Sliq
  • 259
  • 2
  • 9
  • 4
    Just a hunch: sha is designed to be fast, as it's for message integrity validation. Blowfish is designed to be slow, that's why it's awesome for passwords. – Maerlyn May 25 '13 at 19:54
  • -1 You have already received some good and satisfying answers at Stackoverflow. No need to cross-post. – Adi May 25 '13 at 20:08
  • @Maerlyn Yes, i know. You are throwing "hashing" and "password hashing/salting" together. It's the same comment every time. PHP's crypt() function clearly focuses on password hashing, but still gives the possibility to choose between a lot of different algorithms. I mean, there's no real documention on that, nothing explains which algo you should use and why. – Sliq May 25 '13 at 20:30
  • 3
    @Adnan it was closed as off-topic there and it would be good to have other looking for this security-related information to be able to find it on our site. – Jeff Ferland May 25 '13 at 20:34
  • 2
    @Adnan The answers on SO are rather weak and since it's closed nobody can post a better one. – CodesInChaos May 25 '13 at 22:20
  • @Maerlyn To bring this in a proveable, reproduceable relation: In my benchmarks, using the offical examples from the crypt() doc page, BLOWFISH wins as the slowest algorithm, but only very close to SHA512. 100 loops of hashing+salting with the standard cost factors are 1.9sec for BLOWFISH, 1.35sec for SHA512. Sorry, the "designed to be fast/slow" argument is not really valid here. And if we have a deeper look on the cost factors (can we compare "04" base-2 logarithm in blowfish to 5000 rounds in sha512 ?), i'm even more unsure if BLOWFISH is really slower than SHA512. – Sliq May 25 '13 at 22:28
  • 2
    Designed to be slow on highly parallel hardware, such as GPUs. Your test is only as relevant as the chance an attacker will use same or similar hardware you were to brute-force password hashes. By that account, it would take the time in your results to try a **single** possible input value. Clearly unfeasible, so the attacker would somehow try parallelizing this process. GPUs are an obvious choice, but (at least current hardware) fails being much faster with BLOWFISH because of large internal RAM table it uses. See [this answer](http://security.stackexchange.com/a/6415/20074) for more info. – TildalWave May 25 '13 at 22:55
  • Not sure if my thoughts are useful or not :-p, but even if BLOWFISH isn't slower for special hardware, using `crypt()`, to equal time-processing cost=10 (1024 rounds) of BLOWFISH, it took 40,000 rounds using SHA-512 using PHP's crypt method. A cost of 13 (8196) required 300,000 rounds of SHA-512. With that in mind, I think it is more likely that the average programmer would inadvertently choose a higher cost using BLOWFISH than they would using SHA512 since every increase doubles the time-cost. – Kevin Nelson Dec 19 '14 at 00:11

2 Answers2

13
  • we're talking about strongest for password hashing here. A good general purpose hash doesn't need to be a good password hash, and vice versa.
  • Length of the hash is irrelevant once it exceeds a certain threshold. A pre-image attack on an n bit hash costs 2n. For a 128 bit hash this is completely infeasible.

  • bcrypt using an exponential notation for cost and sha512-crypt using a linear notation is irrelevant. Comparing their CPU cost with default parameters is meaningless as well.

    In practice you choose a time budget, say 10ms. Then you adjust the cost factor of the hash to match that budget. So if an attacker used the same hardware as the defender, then all decent password hashes would be the same.

  • An attacker uses different hardware from the defender. The defender uses a standard CPU. The attacker uses at least a GPU, or if it's an advanced attacker perhaps an FPGA or ASIC.

    The difference between different hashes is how well they run on different kinds of hardware. BCrypt needs a few kilobytes of really fast memory. This works well with common CPUs, but doesn't work well with GPUs. So bcrypt is very GPU unfriendly. With FPGA the advantage of bcrypt is smaller, especially if it has integrated RAM. But it's still a bit better.

  • A a simple benchmark you could tune the candidate hashes to the same cost. Then run a GPU based password cracker, such as hashcat or john-the-ripper and check its performance. I expect bcrypt to have a much lower hashrate.
  • There is also another interesting password scheme called scrypt. It uses larger amounts of memory and if your time budget is large it's significantly better than bcrypt or SHA512-crypt.
CodesInChaos
  • 11,964
  • 2
  • 40
  • 50
1

The "mathematical proof" is you can choose N arbitrarily:

t(bcrypt) * (2^N) >> t(sha)

The final hash is all about avoiding collisions, so you're safe so long as

hash >> password

The salt is all about avoiding rainbow tables, so you're safe so long as

(rainbow table size) * (salt) >> (attacker storage space)
Enos D'Andrea
  • 1,097
  • 6
  • 14