7

Since the best example of pooled resource to crack hashes is the bitcoin network, currently churning through 2.14 ExaHashes/s.

I want to ask, if the resources of this network were pointed towards cracking blowfish, and (by extension) bcrypt, what would be the minimum cost factor to keep when protecting passwords using bcrypt?

Amin Shah Gilani
  • 171
  • 4
  • 7
    I'm pretty certain that the ASICs that compute SHA-256 hashes for Bitcoin are going to need serious redesigns to work on Blowfish encryption instead. Also, Blowfish was deliberately designed to be relatively front heavy (requiring lots of preprocessing when changing keys, but being fast for bulk encryption or decryption) as well as memory-intensive (it needs a little over 4 KB of RAM, almost all of that for the internal round subkeys), while to my knowledge, SHA-256 was not designed with any such goal. – user Dec 04 '16 at 17:24
  • 3
    I agree with @MichaelKjörling that we can't really take that network's hashing speed and convert it to a number that makes sense for the bcrypt hashing process. I thought about taking the hash speed of the network and converting that to iterations (despite them not being the same speed), and then calculating that back to a work factor. But the speed difference will be so large that the work factor will be unnecessarily inflated. Not to mention the delay introduced (minutes?) when logging into a system using that work factor probably isn't realistic for users to tolerate. – PwdRsch Dec 04 '16 at 18:32

2 Answers2

5

Short answer: if you compare the speeds on x86, the maximum cost in PHP of 31 (2^31 iterations) would be secure enough for a strong (random 8 char) password. Not that it would be usable, one hash would take ~ 200 hours to generate on a desktop.

Long answer: (large margin of error due to lack of accurate hash performance data, no specifics on password strength and lazy approximation.)

The cost of raw brute-force can vary with a factor of billions between a 6 letter password and a length 10 password with numbers and special chars. (26^6 = 3.0E+8 for lowercase, 94^10 = 5.3e+19 for mixalpha-num-all) Hashing speeds can vary with implementation.

So if the user picks one of the 1000 most commonly used passwords, it's as good as a 3 digit pin number, making the question practically irrelevant.

To this end, the answer is "as much as you can, we can't save everyone from themselves"

But let's make a back-of-the-napkin calculation to get an idea. Let's assume the database sets a strong minimum requirement of "as good as 8 random chars"

With a character set of all lower- and uppercase ASCII chars, all digits and special characters that would come to 6161234432565770 combinations

Now let's get an idea of the hashes' performance. The only side-by side comparison i could find that came close was this: https://pthree.org/2014/12/26/sha512crypt-versus-bcrypt/

It states that the default work factor of 10 is about equal to 80.000 rounds of SHA512crypt . Now SHA 512 only costs about 120% of the time 256 takes

So that makes bcrypt with cost(10) approximately equal to 100.000 rounds of SHA256.

BCrypt's cost is defined like this:

The two digit cost parameter is the base-2 logarithm of the iteration count for the underlying Blowfish-based hashing algorithm and must be in range 04-31, values outside this range will cause crypt() to fail

cost(10) = 2^10 = 1024 iterations. so bitcoin's algorithm SHA256 is about 100x faster per iteration. Assuming BitCoins network can do 2.14E+18 SHA256/second, that would come down to 2.14E+16 iterations of BCrypt/second. The keyspace of the length-8 random password in charset mixalpha-numeric-all is about 6.16E+16

  • So at 1 iteration, it could bruteforce such a password in < 3s. the minimum for PHP is a cost of 4, so 16 iterations.
  • At the default cost of 10, it would take nearly an hour.
  • At the maximum cost of 31 it would increase another 2^21 = 2097152 hours, which is a little under 240 years.

This is quite an infeasible brute-force, and could for the moment be considered secure.

The maximum amount of 'cost' in BCrypt would suffice against the entire current BitCoin network if the password is moderately strong.

However, the comparison of BCrypt vs SHA512 mentions cost(20) already takes > 3 minutes on a workstation, making such large costs impractical for now. extrapolating 2^12*3.12/60 =~ 213 hours

J.A.K.
  • 4,793
  • 13
  • 30
  • That's an odd table. How can the cost of cracking "40 char text" be on the order of 1/1000 of the cost of cracking "10 chars"? At the very least, you should tell us where you got those numbers from, and ideally how they were derived. – user Dec 04 '16 at 19:11
  • hmm. i plucked that table from another post, but it seems to have some inconsistencies. i think i'll remove it. – J.A.K. Dec 04 '16 at 19:13
2

Maybe you're asking the wrong question:

You don't want to be asking what work factor (iteration count) do I use? (with KDFs/adaptive hashing), you want to be asking how long will a single hash take? and compute the work factor back from that.

The answer to the latter is "as long as you can tolerate". More here by an expert https://security.stackexchange.com/a/3993/69959

So to answer your question you need to know the time the said network will take to compute a hash. Or more useful, the H/s for a given work factor. Bcrypt benchmarks are often quoted in terms of bcrypt(5) which is a work factor of 5. If you can get the H/s for bcrypt(5) of said network then you have a base to compare with alternative cracking benchmarks.

The best I've found for a on-premise device is this 8x GTX Titan X cudaHashcat Benchmark which will crack bcrypt(5) at a rate of 133 KH/s (at time of writing). This is a good base to compare to a distributed cracking network.

Just a note, distributed hash cracking is not new and we should assume that the powers that be will have many orders of magnitude more cracking power than anything publicly available.

You're asking what work factor to use to keep a password safe right?

Here is my personal rule:

Benchmark your bcrypt on a local dev machine and a web server node that your app will be deployed into. Then choose the longest tolerable (in terms of UX) time you are willing to subject your users to. For me this is about 1000ms (remember: signup and login screens; doesn't happen often). Then find the work factor which sits just inside that time and select the slowest of your local dev and prod box.

Community
  • 1
cottsak
  • 140
  • 9