8

If you have multiple hashes of a password, all hashed with the same hash function, is it possible to use this to speed up retrieval of the original password in any way?

(I found the question "is it easier to get the original password if you have multiple hashes of it", but that seems to be talking about multiple hashes of the same password but created with different hash functions.)

19

A pure hash function is deterministic, which means that if you hash any given value, you should always get the same hash out. 5f4dcc3b5aa765d61d8327deb882cf99 is always the MD5 hash of "password". You can try it on different machines, with MD5 implementations written in different languages, and, assuming they are correct implementations, you should always get the same hash from calling md5("password") or the specific language equivalent.

However, that is a really bad property to have in a password storage system. To mix things up, better password storage methods use a salt. In that case, the string being hashed is changed for each record. Instead of everyone who used "password" getting the same output hash, the hash is generated of "password+salt" (or "salt+password", "pass+salt+word", or any other merging. Doesn't matter for this question), so you get a bunch of distinct hashes:

  • b305cadbb3bce54f3aa59c64fec00dea - passwordsalt
  • 67a1e09bb1f83f5007dc119c14d663aa - saltpassword
  • 9eee04c6cecbc87f7699823f559b820d - passsaltword

As can be seen, there aren't any particular common features in these, even using the MD5 hashing algorithm, which is a bad choice for password storage. (The pair of "b"s at positions 8 and 9 in the first two are just coincidental).

This is because MD5 is implements the "avalanche" effect - the change of a single input bit will cause a significant amount of the output to change (ideally about 50% for various analysis reasons).

All this combined means that even with the short salt used above, the only way to determine that the word "password" is in the three hash inputs is to try out all the possibilities.

This is dependent on the hash function used - you could construct a hash function where adding a similar salt resulted in a similar change to the output (so "passwordsalt" and "passwordsals" only vary by a small amount when hashed), but that isn't typical for hash functions used for password storage.

Furthermore, modern password storage recommendations suggest the use of something like bcrypt or scrypt, both of which generate a strong salt as part of the hash initialisation:

  • $2a$08$WCUycJKlopCnpbAoYIQBj.wlsQA3iC2QhLOBpMMVZZtSO8hsXP1SW
  • $2a$08$8s89Oz3AsJ.Dv.HAjIGKC.JdZJwzQUAkSX7Mels1Cc6Zwter.z7NO
  • $2a$08$r5lrQviZKBDgLS4z8OKVWOnlza16.tLDCqjq8pdQ1wY.iDSldXCFW

All of these are hashes of "password" - and having all three doesn't help you at all.

  • All of these are hashes of "password" - and having all three doesn't help you at all. Not in this context, but those are easily attackable. ;) – Mark Buffalo Nov 3 '15 at 17:53
  • 3
    @MarkHulkalo True, but your only way to find it out was to try out common passwords with the same salt! Having three different hashes and being told they are the same password was unhelpful – Matthew Nov 3 '15 at 19:18
6

A cryptographic hash function is a deterministic function, so if you hash several times the same password with the same function, you should get the same output. Or, said otherwise, if you do not always get the same output, then this means that the function is a password-hashing function, with some injected randomness known as a "salt".

If the password-hashing function is decent and properly used (e.g. it is bcrypt), then no, having several hashes won't help. To see this, consider that, formally speaking, a password-hashing function is not one function, but a complete family of functions, the salt being really the choice of a specific function within that family. With distinct salts, you get distinct functions, that are supposed to be "really different" from each other, so that no computational shortcut exists to allow computing N hashes for less than N times the cost of computing one. (It is in fact atrociously difficult to write down that property in a mathematically correct formalism, but the summary above should suffice for this answer.)

Thus, you can have attack speed-ups only when a salt value is reused. Good salts are chosen such that they are unique, which is in fact easy if the salts are chosen randomly and are large enough. Furthermore, in your case, if a salt value was reused for the same password then you get the same hash as previously, and this does not gain anything at all.

Of course, if the password-hashing function at hand does something weird and inexpert, then anything goes. My answer is for good password-hashing functions.

4

As the other answers have said, running the same password through the same hashing algorithm will always produce the same hash. But we can also take your question literally, in which case there is still a useful (and different) answer...

Let's say you've managed to obtain a large list of hashed passwords from a compromised server. You want to recover some of the passwords, and you're not particularly bothered which ones. This objective is realistic - your list might also contain matching usernames and/or email addresses, and you want to come up with credentials that will work on other unrelated sites (e.g. the victim's email account, or Paypal account).

Password strengths vary wildly. Some people use long random-like strings. Others use very common words e.g. "password". This fact makes it possible to perform attacks in less time than a full brute force search. See for example dictionary attacks and rainbow tables.

If you find two identical hashes in your list, then it is almost certain that they were generated from the same password. Assuming the hashes belong to two genuinely independent users, then that tells you that the password must be a fairly weak one, as by definition it is unlikely two people would independently think of an identical strong password. This makes the password a good candidate for something like a dictionary based attack.

So, in the context of a wider list of hashes, having multiple of the same can help you retrieve an original faster, because it reveals statistical information about it.

  • Very good point. In fact, this has been used to get more passwords in conjunction with multiple password hints: Adobe password crossword - if they had salted passwords, this wouldn't work. – Matthew Nov 4 '15 at 8:50
  • Obligatory xkcd link. – a CVn Nov 4 '15 at 9:52
  • Good point! Sadly (for me), the scenario is that I have a service user with a long gone password, and a set of wildly different hashes (apparently of the type "Cisco-IOS SHA-256") all representing the same password. Because reasons, it seems that the least slow and troublesome way forward is to find a way to retrieve this password. – popq Nov 5 '15 at 14:06

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.