About how fast can you brute force PBKDF2?

Question

After the linkedin password hash leak, I've been looking at our password hashing. We using Django 1.4 which uses PBKDF2, which is great and a step up from the previous SHA1.

However I'm curious how easily one could brute force that. I'm looking at our password complexity rules, and am wondering how fast it'd take to do (say) 8 length lower case ascii letters.

This guide to cracking the LinkedIn password hash, has someone doing 430 million sha1 hashes per second on a GPU. http://erratasec.blogspot.ie/2012/06/linkedin-vs-password-cracking.html What kinda speeds would you get for PBKDF2?

Does anyone have any rough/back-of-the-envelope/ballpark figures for how fast one could brute force PBKDF2?

Answer 1

There is a writeup over at agilebits from February that does the napkin calculations. The abridged version:

As a ball park figure, I'm going to say 10,000 PBKDF2 iterations leads to tens of or hundred of milliseconds to test a password for a very high-end consumer system. What we are doing with PBKDF2 is reducing things from a million tests per second to a few hundred. This is taking into account specialized software that makes use of multiple cores and multiple GPUs.

So taking your erratasec article that benchmarks 430 million SHA-1 hashes per second on a gpu as a baseline - the agilebits article shows metrics that suggest PBKDF2 with 10k iterations would bring that down to around 100k tests per second.

Far from scientific, but gets us in the ballpark...

Answer 2

Specialised hardware, such as used in bitcoin mining, can perform upwards of 50 billion hashes per second (as of early 2013. It's a moving target as hardware gets faster).

If you do 1,000 iterations of PBKDF2 then that will cut the attack down from 50 billion per second to 50 million per second. 10,000 iterations will be 5 million per second.

A typical web server however will not be anywhere near that fast. It's going to be a lot slower for you. You need to do some testing on your own production server and may find 10,000 iterations is too slow.

So it's not really about how fast PBKDF2 can be brute forced, it's about fast your server can verify a PBKDF2 password. You need to decide how long you think it should take (half a second? a tenth of a second? a hundredth of a second?) and then adjust the number of PBKDF2 rounds to suit that.

Also consider the strength of the passwords used by your customers. If they all have excellent passwords, then it really doesn't matter what hashing system you use. If they are all using terrible passwords then PBKDF2 is not good enough to protect them - you would need to get more exotic such as the hardware salted hash Apple uses in the iPhone to try and turn a 4 digit number into something that has at least some security (basically they force all hashing to be performed by a dedicated hardware chip, which is deliberately slow. move the data to any other hardware and it is impossible to decrypt).

Assuming the password is not in a dictionary (most passwords are), then the password strength is calculated by multiplying the number of possible characters in the alphabet by itself one hibe for each character. So if a password has letters (26 character alphabet) and digits (another 10 characters) then you have a 36 character alphabet, and if it's 6 characters long you multiply it by itself 6 times.

So a 6 digit alphanumeric password is 36*36*36*36*36*36, or if you prefer: 36^6. That gives you about 2.1 billion possible passwords... generally we assume the hacker will find the real password about half way through, so call it 1 billion.

If you are using PBKDF2 and have 1,000 iterations, then a hacker with specialised hardware will guess 1 billion passwords in about 20 seconds. That's not very good security at all.

You can improve security by either using more rounds of PBKDF2 (which will slow your website down) or by convincing your users to have better passwords. Simply by switching to 7 digits instead of 6, or by adding upper-case letters or even symbols, they will dramatically improve their security.

Wolfram Alpha is useful for doing the math: ((36 ^ 6) / 50 million) seconds where 36 is the size of the alphabet and 6 is the length of the password, and 50 million is the number of guesses per second a hacker can use (50 million is a serious attacker going after PBKDF2 with 1,000 rounds).

How many passwords are there in your database? If it takes 20 seconds to crack individual password, will that me 30 days of math or 30 years? It depends how many customers you have.