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.)
4
  • 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, 2015 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, 2015 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. May 18, 2015 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, 2015 at 21:12

1 Answer 1

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.

6
  • 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. May 18, 2015 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, 2015 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, 2015 at 21:30
  • 1
    @mucaho Added additional pseudocode as requested.
    – Polynomial
    May 18, 2015 at 21:36
  • @Polynomial I don't know about you, but I'm pretty sure that's python May 18, 2015 at 22:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .