python passlib: what is the best value for "rounds"

encryption, pbkdf2, python

Solution

(passlib developer here)

The amount of time pbkdf2_sha512 takes is linearly proportional to it's rounds parameter (`elapsed_time = rounds * native_speed`). Using the data for your system, `native_speed = 12000 / .143 = 83916 iterations/second`, which means you'll need around `83916 * .350 = 29575 rounds` to get ~350ms delay.

Things are a little tricker for bcrypt, because the amount of time it takes is logarithmically proportional to it's rounds parameter (`elapsed_time = (2 ** rounds) * native_speed`). Using the data for your system, `native_speed = (2 ** 12) / .405 = 10113 iterations/second`, which means you'll need around `log(10113 * .350, 2) = 11.79 rounds` to get ~350 ms delay. But since BCrypt only accepts integer rounds parameters, so you'll need to pick `rounds=11` (~200ms) or `rounds=12` (~400ms).

All of this is something I'm hoping to fix in a future release of passlib. As a work in progress, passlib's mercurial repo currently contains a simple little script, choose_rounds.py, which takes care of choosing the correct rounds value for a given target time. You can download and run it directly as follows (it may take 20s or so to run):

$ python choose_rounds.py -h
usage: python choose_rounds.py <hash_name> [<target_in_milliseconds>]

$ python choose_rounds.py pbkdf2_sha512 350
hash............: pbkdf2_sha512
speed...........: 83916 iterations/second
target time.....: 350 ms
target rounds...: 29575  

$ python choose_rounds.py bcrypt 350
hash............: bcrypt
speed...........: 10113 iterations/second
target time.....: 350 ms
target rounds...: 11 (200ms -- 150ms faster than requested)
target rounds...: 12 (400ms -- 50ms slower than requested)

(edit: added response regarding secure minimum rounds...)

Disclaimer: Determining a secure minimum is a surprisingly tricky question - there are a number of hard to quantify parameters, very little real world data, and some rigorously unhelpful theory. Lacking a good authority, I've been researching the topic myself; and for off-the-cuff calculations, I've boiled the raw data down to a short formula (below), which is generally what I use. Just be aware that behind it are a couple of pages of assumptions and rough estimates, making it more of a Fermi Estimation than an exact answer :|

My rule of thumb (mid 2012) for attacking PBKDF2-HMAC-SHA512 using GPUs is:

 days * dollars = 2**(n-31) * rounds

- `days` is the number of days before the attacker has a 50/50 chance of guessing the password.

- `dollars` is the attackers' hardware budget (in $USD).

- `n` is the average amount of entropy in your user's passwords (in bits).

To answer your script-kiddie question: if an average password has 32 bits of entropy, and the attacker has a $2000 system with a good GPU, then at 30000 rounds they will need 30 days (`2**(32-31)*30000/2000`) to have a 50/50 chance of cracking a given hash. I'd recommend playing around with the values until you arrive at a rounds/days tradeoff that you're comfortable with.

Some things to keep in mind:

The success rate of a dictionary attack isn't linear, it's more of "long tail" situation, so think of the 50/50 mark as more of a half-life.

That `31` is the key factor, as it encodes an estimation of the cost of attacking a specific algorithm using a specific technology level. The actual value, `2**-31`, measures the "dollar-days per round" it will cost an attacker. For comparison, attacking PBKDF2-HMAC-SHA512 using an ASIC has a factor closer to `46` -- larger numbers mean more bang for the attacker's buck, and less security per round for you, though script kiddies generally won't have that kind of budget :)

Problem

from the passlib documentation For most public facing services, you can generally have signin take upwards of 250ms - 400ms before users start getting annoyed. so what is the best value for `rounds` in a login/registration if we consider that there is one call for the database for the login attempt, and it uses MongoDB with non-blocking call. (using Mongotor, and using the email as the `_id`, so it is by default indexed, the query is fast: 0.00299978256226 and of course tested with a database that has 3 records...) ``` import passlib.hash import time hashh = passlib.hash.pbkdf2_sha512 beg1 = time.time() password = hashh.encrypt("test", salt_size = 32, rounds = 12000) print time.time()- beg1 # returns 0.142999887466 beg2 = time.time() hashh.verify("test", password) # returns 0.143000125885 print time.time()- beg2 ``` now if i use half value: ``` password = hashh.encrypt("test", salt_size = 32, rounds = 4000) # returns 0.0720000267029 hashh.verify("test", password) # returns 0.0709998607635 ``` am using Windows 7 64 bits on Dell XPS 15 i7 2.0 Ghz NB: installed bcrypt, and of course, it's a real pain using it directly as its default values (`rounds = 12`): ``` hashh = passlib.hash.bcrypt beg1 = time.time() password = hashh.encrypt("test", rounds = 12) # returns 0.406000137329 print time.time()- beg1 beg2 = time.time() hashh.verify("test", password) # returns 0.40499997139 print time.time()- beg2 ``` half value: ``` password = hashh.encrypt("test", rounds = 12) # 0.00699996948242 wonderful? hashh.verify("test", password) # 0.00600004196167 ``` can you suggest me a good rounds value when using `pbkdf2_sha512` that will be good for production?

Original source