Score:5

Crypto

Does having multiple salted hashes lower pre-image resistance?

Joshiepillow

1/23/24, 11:30 PM

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?

145

2 + 5

salt

preimage-resistance

forest

1/24/24, 12:10 PM

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).

samuel-lucas6

1/24/24, 12:45 PM

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.

Joshiepillow

1/24/24, 2:55 PM

@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.

Joshiepillow

1/24/24, 2:55 PM

@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?

samuel-lucas6

1/25/24, 8:49 PM

@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.

Score:3

Crypto

fgrieu

1/26/24, 9:23 AM

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.

+ 3

samuel-lucas6

1/26/24, 12:56 PM

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.

fgrieu

1/26/24, 1:07 PM

@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.

samuel-lucas6

1/26/24, 1:48 PM

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.

Score:2

Crypto

princeofmillerovo

1/26/24, 5:42 AM

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.

+ 2

kodlu

1/26/24, 6:25 AM

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}.$

princeofmillerovo

1/26/24, 8:20 AM

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].

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Does having multiple salted hashes lower pre-image resistance?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.