5

An attacker want's access to a specific account, he doesn't know the password.

  • It's a high entropy password. +128bits
  • The attacker has the hash for the password (Assuming OWASP suggested bcrypt with cost 12)
  • The attacker has a list with n hashes that HE KNOWS are hashes for the same password he is looking for. (He magically knows, just bear with me)

Does the list of hashes makes it easier for the attacker to gain access to the password? (Either by guessing the password of finding a collision) Or is the difficulty the same as if he had a single hash?

I'm aware it's an unlikely scenario, I'm just trying to understand more about the risks of exposed hashes.

I have very little understanding of InfoSec and hash functions, but it seems to me that the hash list makes no difference for trying to crack the password, but it could improve the chances for the attacker to find a collision. If my assumption is correct, how large would the list have to be, for it to become a realistic problem? (Ballpark estimates are fine)

Luc
  • 32,378
  • 8
  • 75
  • 137
Justcurious
  • 175
  • 1
  • 6
  • 1
    Are you familiar with the concept of rainbow tables? See http://project-rainbowcrack.com/index.htm for more information. – CorruptedHeapScapeGoat Mar 15 '21 at 12:44
  • I know what they are, but isn't this mitigated by the salt in the bcrypt hash? – Justcurious Mar 15 '21 at 15:45
  • I think you are still [oversimplifying the 128 bit](https://security.stackexchange.com/a/246119/86735). No one can reach 128-bit on a single target. And, you still consider the collision as a threat to password finding. No! Collisions are not related to password finding. – kelalaka Mar 15 '21 at 22:24
  • 2
    By "a list with n hashes", do you mean a set of hashes for different salts and the same algorithm, or do you mean different algorithms? – throx Mar 16 '21 at 02:40
  • 1
    Is `n` big enough to cover a large fraction of the possible salts? – Joshua Mar 16 '21 at 15:51
  • If you hash a password 1 million times, it will give the same result 1 million times. Can you elaborate on this list of n hashes? – cjnash Mar 16 '21 at 16:34
  • 2
    OP is talking about having the same password hashed `n` times but with `n` distinct salts. – ThoriumBR Mar 16 '21 at 17:57

4 Answers4

17

It makes no difference, and the scenario makes no sense at all.

If you think about the salt and oversimplify it, it's just a string concatenated with the password, and that makes the password different. So you will never have n hashes for the same password, you will have n hashes for n different passwords.

Even one bit changed on a salt makes the hash completely different (due to the Avalanche effect), so the attacker sits on a pile of random, useless data.

ThoriumBR
  • 51,983
  • 13
  • 131
  • 149
  • Thank you for the answer. Wouldn't the list increase the chances of finding a collision though? – Justcurious Mar 15 '21 at 15:59
  • 1
    No. It will not change anything. In practice, this is having a bunch on hashes for random strings. – ThoriumBR Mar 15 '21 at 18:05
  • 1
    You could get multiple hashes of the password if, for example, the target system has upgraded its security. You might start with MD5, then SHA-1, then iterated SHA-1, then bcrypt. – Mark Mar 15 '21 at 21:03
  • 4
    @ZeCarioca to clarify, it does increase the likelihood of finding a collision with _a_ hash, because you're looking for more possible matches - the reason is doesn't matter is that a collision with one hash tells you nothing about the other hashes. Additionally, finding a collision tells you nothing about the original password, so there is no increase in risk. – Tim Mar 16 '21 at 01:10
  • @Tim that analysis assumes an ideal hash algorithm that perfectly embodies the Avalanche Effect. Real-world hash functions aren't so perfect, and to me that's what makes the original question interesting. – Ken Williams Mar 17 '21 at 02:33
  • @ThoriumBR - I believe the OP knows that a given input string will only hash to a single output string, it seems like he/she is explicitly talking about multiple salts with a single password creating multiple hash outputs. – Ken Williams Mar 17 '21 at 02:36
12

The most likely scenario for having multiple hashes of the same password is if the target system has had its security upgraded over time. For example, it might have started out using plain MD5, which got replaced with SHA-1 when collision attacks on MD5 were found, then upgraded to iterated SHA-1 when the developer was informed that SHA-1 was too fast, and finally replaced with a proper password hash such as bcrypt.

In this case, security is only as strong as the weakest hash. The collision attacks on MD5 and SHA-1 don't give any help in finding the password (finding the password is a preimage attack), so the best available attack is brute-forcing the either the MD5 hash or the SHA-1 hash, whichever is faster.

Mark
  • 34,513
  • 9
  • 86
  • 135
3

Given the scenario you set up, no. A recommended algorithm will use salt, and the purpose of salt is to make it so that attacking 100 hashes takes 100 times as much work as attacking one hash.

If you somehow know that those 100 hashes are all of the same password, then you don't need to try each candidate password against all of them; any one will do. But your best strategy is still just to take one of them and attack it — or choose a random one for each attempt, it doesn't matter. But you gain nothing from having lots of them. If one of the hashes uses a weaker algorithm or has a lower work factor than the others, then your best approach is to make all of your attempts against that one and ignore the others.

hobbs
  • 640
  • 4
  • 8
1

Multiple hashes are not going to help with a brute force attack. It is completely illogical, because if you guess the correct password, then each one of the of the hashes verify. Conversely, if you guess the wrong password, then none of the hashes verify. Therefore, you can reject wrong guesses by checking that just one of the hashes fails to verify.

For that purpose, you should choose the weakest hash. For instance, if you have 100 different hashes of which 99 use SHA256, and the last one uses DES crypt, then of course you just crack the crypt one and forget the others.

Now if those N hashes are all of equal type, there might be something interesting there. The only way you can have N different hashes of the same password with the same method is that the salts are different. Thus, you have a database of salt/hash pairs for the same password which you don't know. There could be some cryptanalytic attack on the hash function which somehow takes advantage of having numerous known salt/hash pairs for the same password.

Kaz
  • 2,293
  • 16
  • 17
  • "There could be some cryptanalytic attack on the hash function which somehow takes advantage of having numerous known salt/hash pairs for the same password" - that seems like the essence of the original question, indeed to me that seems like the interesting part. – Ken Williams Mar 17 '21 at 02:37