Optimal bcrypt work factor

Question

What would be an ideal bcrypt work factor for password hashing.

If I use a factor of 10, it takes approx .1s to hash a password on my laptop. If we end up with a very busy site, that turns into a good deal of work just checking people's passwords.

Perhaps it would be better to use a work factor of 7, reducing the total password hash work to about .01s per laptop-login?

How do you decide the tradeoff between brute force safety and operational cost?

Athalee

The cost thwarts offline attacks. When "online" you can use minimum delay between attempts (e.g. 5 seconds) to prevent a denial of service attack. – Sand

Duplicate on InformationSecurity: Recommended # of rounds for bcrypt – Reynold

For anyone interested, I just wrote a small Java CLI tool to test bcrypt performance on servers (which is obviously important for balancing security, server-load and response-times): github.com/cdraeger/hash-performance – Bathyscaphe

Answer 1

Remember that the value is stored in the password: $2a$(2 chars work)$(22 chars salt)(31 chars hash). It is not a fixed value.

If you find the load is too high, just make it so the next time they log in, you crypt to something faster to compute. Similarly, as time goes on and you get better servers, if load isn't an issue, you can upgrade the strength of their hash when they log in.

The trick is to keep it taking roughly the same amount of time forever into the future along with Moore's Law. The number is log2, so every time computers double in speed, add 1 to the default number.

Decide how long you want it to take to brute force a user's password. For some common dictionary word, for instance, your account creation probably already warned them their password was weak. If it's one of 1000 common words, say, and it takes an attacker 0.1s to test each, that buys them 100s (well, some words are more common...). If a user chose 'common dictionary word' + 2 numbers, that's over two hours. If your password database is compromised, and the attacker can only get a few hundred passwords a day, you've bought most of your users hours or days to safely change their passwords. It's a matter of buying them time.

http://www.postgresql.org/docs/8.3/static/pgcrypto.html has some times for cracking passwords for you to consider. Of course, the passwords they list there are random letters. Dictionary words... Practically speaking you can't save the guy whose password is 12345.

Passmore

This is really an excellent answer. I hadn't even considered the re-crypt on login idea. Thank you so much! – Athalee

How would the recrypt work? You would have to store the old bcrypt work cost somewhere so you can use it to log them in and then after validating their password you would update the hash and cost in the database? – Rabbinate

@JerrySaravia The beauty of bcrypt is that the cost is stored within the hash itself - so you don't need to store anything extra. Simply authenticate with the current hash, then immediately re-generate the hash with a different cost. Simple! – Peadar

@MarkLocker, Thanks Mark! It's a B[eautiful]crypt! But seriously, that makes things much easier and is a wonderful thing. – Rabbinate

Okay since I'm not allowed to edit it in because it's an "incorrect attempt to reply" (do you guys even read my edits?), allow me to comment the information instead. Example value: $2y$08$fJS4yx0i8kiOzIBIamZ51OWTMrzyE/4je34Oxhw.5xxp3Es7Ke32W. Reason I attempted to edit: It was unclear to me whether "2 chars work" was a digit or hex or something, had to test. Here is the test result for everyone else so you don't have to try it out yourself. – Misha

@MarkLocker "you don't need to store anything extra" On the other hand you could say you always store something extra whether you want it or not ;) – Misha

Answer 2

Short Version

The number of iterations that gives at least 250 ms to compute

Long Version

When BCrypt was first published, in 1999, they listed their implementation's default cost factors:

• normal user: 6
• super user: 8

A bcrypt cost of 6 means 64 rounds (2⁶ = 64).

They also note:

Of course, whatever cost people choose should be reevaluated from time to time

• At the time of deployment in 1976, crypt could hash fewer than 4 passwords per second. (250 ms per password)
• In 1977, on a VAX-11/780, crypt (MD5) could be evaluated about 3.6 times per second. (277 ms per password)

That gives you a flavor of the kind of delays that the original implementers were considering when they wrote it:

• ~250 ms for normal users
• ~1 second for super users.

But, of course, the longer you can stand, the better. Every BCrypt implementation I've seen used 10 as the default cost. And my implementation used that. I believe it is time for me to to increase the default cost to 12.

We've decided we want to target no less than 250ms per hash.

My desktop PC is an Intel Core i7-2700K CPU @ 3.50 GHz. I originally benchmarked a BCrypt implementation on 1/23/2014:

1/23/2014  Intel Core i7-2700K CPU @ 3.50 GHz

| Cost | Iterations        |    Duration |
|------|-------------------|-------------|
|  8   |    256 iterations |     38.2 ms | <-- minimum allowed by BCrypt
|  9   |    512 iterations |     74.8 ms |
| 10   |  1,024 iterations |    152.4 ms | <-- current default (BCRYPT_COST=10)
| 11   |  2,048 iterations |    296.6 ms |
| 12   |  4,096 iterations |    594.3 ms |
| 13   |  8,192 iterations |  1,169.5 ms |
| 14   | 16,384 iterations |  2,338.8 ms |
| 15   | 32,768 iterations |  4,656.0 ms |
| 16   | 65,536 iterations |  9,302.2 ms |

Future Proofing

Rather than having a fixed constant, it should be a fixed minimum.

Rather than having your password hash function be:

String HashPassword(String password)
{
   return BCrypt.HashPassword(password, BCRYPT_DEFAULT_COST);
}

it should be something like:

String HashPassword(String password)
{  
   /*
     Rather than using a fixed default cost, run a micro-benchmark
     to figure out how fast the CPU is.
     Use that to make sure that it takes **at least** 250ms to calculate
     the hash
   */
   Int32 costFactor = this.CalculateIdealCost();
   //Never use a cost lower than the default hard-coded cost
   if (costFactor < BCRYPT_DEFAULT_COST) 
      costFactor = BCRYPT_DEFAULT_COST;

   return BCrypt.HashPassword(password, costFactor);
}

Int32 CalculateIdealCost()
{
    //Benchmark using a cost of 5 (the second-lowest allowed)
    Int32 cost = 5;

    var sw = new Stopwatch();
    sw.Start();
    this.HashPassword("microbenchmark", cost);
    sw.Stop();

    Double durationMS = sw.Elapsed.TotalMilliseconds;

    //Increasing cost by 1 would double the run time.
    //Keep increasing cost until the estimated duration is over 250 ms
    while (durationMS < 250)
    {
       cost += 1;
       durationMS *= 2;
    }

    return cost;
}

And ideally this would be part of everyone's BCrypt library, so rather than relying on users of the library to periodically increase the cost, the cost periodically increases itself.

Sand

If I have passwords as autogenerated API token of 32 symbols, would using low factor be enough? It should not slow down API requests. – Brushwork

Answer 3

I've been trying to determine my optimal number of bcrypt salting rounds and wanted to post my findings. As others have pointed out, the ideal number of rounds depends on your hardware, your user's patience, and the hardware of potential attackers.

In the year 2023, running on a basic heroku dyno and then again on my local machine, I benchmarked how long it takes to do a hash operation for a range of different salt rounds:

salt rounds	heroku hash time	5600x hash time	crack weak pw (28 bits)	crack medium pw (37 bits)
7	13 ms	8 ms	12 days	17 years
8	24 ms	15 ms	23 days	32 years
9	47 ms	29 ms	1.5 months	63 years
10	90 ms	58 ms	3 months	126 years
11	181 ms	118 ms	6 months	256 years
12	367 ms	233 ms	1 years	long time
13	735 ms	461 ms	2 years	"
14	1422 ms	936 ms	4 years	"
15	2878 ms	1863 ms	8 years	"
16	5969 ms	3721 ms	16 years	"

The bits of entropy for the weak password based on the famous XKCD password comic

Factors to keep in mind:

• The crack time can be divided by the number of computers you have access to. Hackers with bot-nets or lots of funds can divide these crack times by orders of magnitude

• Crack time decreases over time. Hashed passwords that are leaked now might be able to be cracked very easily in 10 years time.

• A 5600X is far from the pinnacle of modern processing. A 7900X will be able to do this faster.

• This was done single-threaded, multithreading will make it faster.

Based on this data, I would advise a minimum of at least 10 rounds but would strongly suggest 11. 100-200 ms is a very short period of time for a user to wait, and if concurrent sign ins are causing lag, you should consider adding more horsepower to your backend. The most I would advise is 13 rounds. While it will be very secure, 700ms is a long time for users to wait to sign in. Between 10 and 13, it's going to be a judgement call that you, as a developer, need to make.

PS: I want to credit Ian Boyds very nice graph and very nice auto-scaling code. It is something everyone reading this should give consideration, but I also wanted to provide some up-to-date data on how long bcrypt actually takes in the current year, on current and common hardware.

Please comment if this answer goes out of date and I will try my best to get around to updating it.

Note: How do you calculate crack times?

To discuss this we first have to discuss password entropy. Very briefly: password entropy is calculated based on the system you use to pick a password. So if your password is a 4 digit pin, then there are only 10,000 possible PIN numbers you could choose. Your password therefore has an entropy of 10,000. This would typically be called 13 bits of entropy, since 10,000 ≈ 2¹³.

To determine how long an attacker would take to crack your password, all you need to determine is how many guesses they would take on average. For that 4 digit pin, they could guess it on the first try, or need 10,000 tries. But on average it will take an attacker 5,000 tries. So the time required to check a single password multiplied by the number of guesses required is the crack time.

Evangelia

Where did you get the information about crack times, that are presented in your table? I was searching the internet for an hour so far :D no good results :D – Percolation

@BendeguzGulyás Added a note on how the crack times were calculated. Also, I hadn't remembered to divide by 2 the first time I did them, so I fixed that. – Evangelia

Answer 4

The question was related to optimal and practical determination of cost factor for bcrypt password hashes.

On a system where you're calculating user password hashes for a server that you expect will grow in user population over time, why not make the duration of time that a user has had an account with your service the determining factor, perhaps including their login frequency as part of that determination.

Bcrypt Cost Factor = 6 + (Number years of user membership or some factor thereof) with an optional ceiling for total cost, perhaps modified in some way by the login frequency of that user.

Keep in mind though that using such a system or ANY system for determining cost factor effectively must include the consideration that the cost of calculating that hash could be used as a method of DDOS attack against the server itself by factoring in any method that increases the cost factor into their attack.

Accordant