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?

  • 1
    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
  • 5
    Is this a homework assignment? – Neil Smithline Mar 25 '16 at 4:13
  • 3
    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

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.

  • 3
    Let's not forget that the amount of password that can be computed per second depends on the hashing algorithm used. When using a fast hashing algorithm, it will be easy to crack. As an example, 350 billion guesses per second can be made against md5. – Jacco Apr 24 '16 at 12:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.