0

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?

schroeder
  • 125,553
  • 55
  • 289
  • 326
Luz A
  • 31
  • 6
  • 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 04:13
  • What hashing algorithm was used? Is the salt used known? Is it per user or same for all users? Unanswerable without these facts – Ramhound Mar 25 '16 at 05:39
  • 3
    it might also be intersting to note that in the real world, attackers can test [billions](http://security.stackexchange.com/questions/43683/is-it-possible-to-brute-force-all-8-character-passwords-in-an-offline-attack) of passwords per second. – Jacco Mar 25 '16 at 07:47
  • @Jacco, only if the password is exclusively salted and not stretched, which appears to be the case for the OP. – SEJPM Mar 25 '16 at 11:32
  • @NeilSmithline No, is not homework. I'm studying this for a security project, I just want to make sure that I understand the concepts. – Luz A Mar 25 '16 at 14:40
  • @Ramhound I'm just assuming that the same salt is used for all passwords. – Luz A Mar 25 '16 at 14:41
  • @Jacco I know that is what happens in the real world, but I wanted to use a small number so I can understand the concept before moving to a practical example. – Luz A Mar 25 '16 at 14:42
  • If someone has or makes a rainbow table and get the hash of the password they could crack it in minutes or less. – cybernard Apr 24 '16 at 23:04

1 Answers1

2

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.

SEJPM
  • 9,540
  • 6
  • 37
  • 67
  • 4
    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](http://security.stackexchange.com/questions/43683/is-it-possible-to-brute-force-all-8-character-passwords-in-an-offline-attack). As an example, [350 billion guesses per second](http://arstechnica.com/security/2012/12/25-gpu-cluster-cracks-every-standard-windows-password-in-6-hours/) can be made against md5. – Jacco Apr 24 '16 at 12:33