How long will it take to break a salted password?

Question

Let's say that I have a system where all passwords must be 8 characters long and each character can be any 32 different values. All my passwords are hashed with a salt.

I can test 64 passwords per second and I have a dictionary of 2^30 common passwords with 1/4 probability. The password file has 256 password hashes.

I know that I have 32^8 possible passwords, right? and that the probability of finding a password in the dictionary is 1/4 and 3/4 probability that is not there.

So I have this: (2^29/4)+(3*2^39/4) that is, the amount of work required to crack one particular password. And to know how long will I take to crack it, I need to divide that amount by 64, right?

Can you tell me if I am wrong or not?

Answer 1

OK, let's slowly walk through this.

We have 32 possible characters at each of the 8 positions within the passwords. This yields 32^8=2^40 possible passwords overall. From this set of passwords there's a subset of size 2^30 from which the password will be with probability of 1/4 and not with probability 3/4. This means you'll first try the small subset and get a hit with expected probability of 1/4 and thereby have expected workload for this of 1/4 * 2^29. Now you test the remaining passwords which are of size 2^39-2^29 which is roughly 2^39. You now test those with a probability of 3/4 and thereby your overall workload becomes 2^27+3*2^37. If all 256 passwords in your password file have the same salt, your workload doesn't increase and if they do have different salts, you need to multiply (2^27+3*2^37) with the number of distinct salts s. Now you can test 64 passwords per second and thereby you divide your amount by that number and get (2^22+3*2^32)*s seconds or roughly 150k years per distinct salt.