6

An attacker gets a list of hashed passwords. How does he know when he has cracked the password(s)? He can't try millions of times on the comprised account.

Attacker gets hashed password. How does he know that "pAssword" is the correct password and not "passwoRd"?

EDIT:

I'm so missing something basic. Let me make certain I understand it:

  1. The DBA takes my great password (pa$$word) and hashes it.
  2. Attacker gets list of passwords.
  3. Attacker tries "password." It gets hashed. He sees that hash-of-password does not equal my password. 3a. He tries hash-of-pa$$word. It gets hashed and he sees that the two are equal. Therefore he cracked my password.
  4. After a while (x amount of time) he has cracked (say) 90% of the passwords and then stops because of diminishing returns. (Unless he really wants MY password.)
  • 1
    if hash(pAssword) == obtained_hash, then pAssword is the password. Else if hash(passwoRd) == obtained_hash, then passwoRd is the password and so on unless you get hash(x) == obtained_hash or you run out of choices. – void_in May 18 '15 at 14:56
  • 1
    Note: when you hash password you are, theoretically, losing the uniqueness of the password. Hashing isn't injective so multiple possible texts have the same hash and all of them would grant access if used as password. – Bakuriu May 18 '15 at 18:50
  • Note that "it gets hashed" in step 3 happens on the box of the attacker, as the attacker knows how the database hashes the passwords. So the attacker can invest as much resources as he likes to be able to crack the passwords faster. Your database can not slow down the attacker by "limiting how fast it offers to hash". You will not notice a million of failed logins on the server. – Michael Karcher May 18 '15 at 18:58
  • Note: Some systems use a very slow hash function. Any reasonably safe system uses a different hash function per user, so if your password is cracked, my identical password is not cracked. There is a one-in-a-gazillion chance that two passwords have the same hash, in which case the hacker can access your account without knowing your true password. – gnasher729 May 18 '15 at 21:12
10

Yes, your steps appear to be correct. The attacker hashes lots of words or sequences of characters until she finds one which matches the target hash.

Pseudocode:

hashlist = [ "a235b8320c...", "688b4302c57f3...", ... ]
wordlist = file.readlines("/path/to/wordlist")
for each word in wordlist:
    h = hash(word)
    # is the hash of this word in the list of target hashes?
    if h in hashlist:
        print "Found: " + h + " = " + word

As muchaho requested, here's some pseudocode for how it'd work with unique salts:

hashlist = [ "salt1:a235b8320c...", "salt2:688b4302c57f3...", ... ]
wordlist = file.readlines("/path/to/wordlist")
for each h in hashlist:
    salt = split(h, ':')[0]
    h = split(h, ':')[1]
    for each word in wordlist:
        if hash(salt + word) == h:
            print "Found: " + salt + ":" + hash + " = " + word

Notice that, after adding a unique salt to each hash, we have to try each individual candidate word for each target hash, rather than just hashing all words and waiting for one to match a hash. This increases the bruteforce cost when you've got multiple hashes to crack, but most importantly prevents precomputation attacks such as rainbow tables.

  • This is made more complicated by the inclusion of salt on the hashes. There you have to brute force one password at a time and can't you the hashlist lookup. – Neil Smithline May 18 '15 at 18:13
  • @NeilSmithline Yes, that is true, but for simplicity's sake and to answer the specific question of how the attacker would know the right password for the hash, I didn't go into that. – Polynomial May 18 '15 at 19:00
  • @Polynomial would you be so kind and provide additional pseudocode for the more advanced case where salts have to be considered also? This pseudocode you provided is really straightforward to understand! – mucaho May 18 '15 at 21:30
  • 1
    @mucaho Added additional pseudocode as requested. – Polynomial May 18 '15 at 21:36
  • @Polynomial I don't know about you, but I'm pretty sure that's python – Snakes and Coffee May 18 '15 at 22:49

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.