5
$\begingroup$

A common method to mitigate the effect of rainbow tables is to add a string to the end of the user password before hashing, a process known as salting.

However, let’s say for example that someone uses a certain password across multiple websites which all salt their passwords, all use the same cryptographic hashing function, and are all have their database leaked.

Can having multiple salted hashes of the same password (and the associated plaintext salts), help an attacker break either pre-image or second pre-image resistance?

I.e. given this information, does an attacker have a better strategy than brute force?

If so, do different prevalent cryptographic hashing functions vary in their susceptibility to this kind of attack?

Also if so, is there a more optimal salting strategy that resists this kind of attack?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Are you wondering about theoretical breaks, or practical attacks that could be used for password cracking? Having a bunch of hashes of a password with different salts won't help an attacker, since they can still only attack one password at a time (multiplied by their parallelization abilities). $\endgroup$
    – forest ♦
    Jan 24 at 12:10
  • $\begingroup$ It's also worth adding that modern password hashing doesn't involve appending a salt to the password. Instead, it's a separate parameter. For example, with PBKDF2, it's used as the HMAC message, whereas the password is used as the HMAC key. $\endgroup$
    – samuel-lucas6
    Jan 24 at 12:45
  • $\begingroup$ @forest I wouldn’t be opposed to an answer to either. While attackers can still only test a single password at a time, I suppose the question is more about whether having multiple hashes of a salted password reduces the search space or reveals a more intelligent search strategy. $\endgroup$
    – Joshiepillow
    Jan 24 at 14:55
  • $\begingroup$ @samuel-lucas6 Huh. I wonder why that change was made. Are there are other problems caused by directly appending salts to the end of a password? $\endgroup$
    – Joshiepillow
    Jan 24 at 14:55
  • $\begingroup$ @Joshiepillow Each password will have a different salt is the key point, hence why just password hashes doesn't help. Now, if you know it's the same user based on their username/email, they can try the same password with the different salts, which will quickly confirm that the password has been reused. As for why the salt isn't appended, there are better ways of incorporating it using these algorithms. I'm guessing you're talking about SHA-256(password || salt) or similar, which should never be used because regular hash functions are extremely efficient for attackers to run. $\endgroup$
    – samuel-lucas6
    Jan 25 at 20:49

2 Answers 2

Reset to default
3
$\begingroup$

For all hash functions used for password hashing with a salt input that I know, no: having the same password hashed with multiple different hashes does not help an attacker. The best practical attack to find a working password (likely to be the original password) remains "brute force", or more precisely trying passwords, approximately from most to least likely of having been chosen by a user, on the (or one of the) password hash with the least computationally intensive entropy-stretching parameters like number of rounds.

For modern password hashes/key-streching functions (Argon2, scrypt), that follows from an explicit design goal, which includes making the output a pseudo-random function of the salt keyed by the password (or some superset of that).

For PBDKF2-HMAC-SHAx (not recommendable), that holds because the password is the key of HMAC. For other (not recommendable) iterated hashes, that essentially follows from first-preimage resistance of the underlying hash, thus remains true if that hash is MD5 and SHA-1 (which collision-resistance is broken).

Even if we take the pre-modern DES-based unix crypt(3) with 12-bit salt (quite insecure), detailed in PCS-TR88-138, that seems to hold, short of an improbable cryptanalytic attack on the modified DES.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Is it worth adding that if the username/email repeats in the different databases, the attacker does have a significant advantage? 'Database leaked' implies this to me, even if it wasn't directly asked in the question. $\endgroup$
    – samuel-lucas6
    Jan 26 at 12:56
  • $\begingroup$ @samuel-lucas6: I'm not sure about the significant advantage you are thinking about. One I see is that an attacker can use the database with the weakest entropy-stretching parameters, and that's alluded to in the answer. $\endgroup$
    – fgrieu ♦
    Jan 26 at 13:07
  • 1
    $\begingroup$ If the attacker cracks one hash and the username matches on different databases, they can try the cracked password to verify the hashes with different salts. They don't have to crack the other hashes, merely confirm the password. $\endgroup$
    – samuel-lucas6
    Jan 26 at 13:48
2
$\begingroup$

All cryptographic hash functions by default need to have preimage resistance.

They probably weaken preimage resistance but a really really tiny bit only.

At least that's what it is believed to be by cryptographers.

Maybe from $2^X$ to $2^{X-1}$ or so at the very best.

Also I have never heard of an attack against hash functions that utilizes "salts".

Moving from here we can see easily that this probably can't be used as an attack towards hash functions.

In a world where even bicliques against AES which reduce its effective strength from $2^{256}$ to $2^{254.4}$ are considered as "attacks" it is highly unlikely that it can ever have a potential to weaken the preimage resistance substantially.

It should have been already discovered and documented if this could be used as an attack against hash functions that's what I mean.

      Too Long Didn't Read

No practical attacks for sure, maybe even no theoretical attacks at all.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I haven't thought deeply about the question but stating that lowering resistance from $2^N$ to $2^{N/2}$ is lowering it by a little seems wrong to me. That's half the bitlength used to measure the resistance. Apply your characterization to AES, it would lower resistance to $2^{128}$ from $2^{256}.$ $\endgroup$
    – kodlu
    Jan 26 at 6:25
  • 1
    $\begingroup$ It seems I unfortunately made a mistake what I initially tried to mean was exactly as follows: "from 2^X to 2^(X-1) or so at the very best" [moderator note: that's now in the answer]. $\endgroup$
    – princeofmillerovo
    Jan 26 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.