# How long will it take to break a salted password?

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?

• Is this DES over EBCDIC data? – Phil Lello Mar 24 '16 at 23:05
• Not really, is just that I'm trying to understand the probabilities of cracking a password. In the system, I have a password p and a salt s, and I hashed this values to obtain: y=h(p, s) – Luz A Mar 24 '16 at 23:08
• ... and you're wrong, unless after finding a password you carry on a test other possibilities just in case – Phil Lello Mar 24 '16 at 23:09
• Is this a homework assignment? – Neil Smithline Mar 25 '16 at 4:13
• it might also be intersting to note that in the real world, attackers can test billions of passwords per second. – Jacco Mar 25 '16 at 7:47

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.