If I have two different MD5 password hashes with two different salts (the salts are known), is there any way to cryptographically deduce if the two passwords match? Other than brute force password cracking, that is.

• @Azxdreuwa the latter :) – Jonas Bjork Jun 27 '18 at 22:47

No, if it is possible then it defeats the purpose of using salts. For example, one can build one rainbow table, mapping each possible password together with a fixed salt value to a hash value. Then given another salt value and password hash, one can find the password in the table if what you asked is possible.

Cryptographic hash functions have 2 properties (lets use h() to represent one hash function):

• Strong collision-free: It is (hard) impossible to find in polynomial time x, y such that h(x) = h(y);

• Weakly collision-free: If you are given x it is impossible to find in polynomial time y such that h(x) = h(y)

This will also happen even if x = (password + salt1) and y = (password + salt2). There is no way to relate h(x) and h(y) because h(x) != h(y) (different). And since computing the inverse is not possible in polynomial time it will be impossible to relate them (unless $\text{P}=\text{NP}$).

Even if you know x, h(x) and h(y) it would be hard to get y and salt2.

However MD5 and SHA-1 are not strongly collision-free. But they are still weakly collsion-free. They should not be used.

• Although this does answer the question and is theoretically sound you may want to explain in more terms how this relates to the question; there seems to be a gap between the level of the question and the answer... – Maarten Bodewes Jun 26 '18 at 16:16
• The non-invertability of commonly used hash functions has nothing to do with P=NP. We have no idea what the optimal complexity of that problem is, we just don't know how to do it. P=NP is a red herring pretty much everywhere in cryptography. – Gilles 'SO- stop being evil' Jun 26 '18 at 20:05

No, this practice would not reduce the safety of your two identical passwords.

The reason is because a secure hash should has an important property call avalanche effect which means if an input is changed slightly, the output changes significantly. Thus, the result of hash(salt1 + password) is dramatically different with the the result of hash(salt2 + password).

• deduce -> reduce? – Maarten Bodewes Jun 26 '18 at 16:17
• Yes, you are right. I mean reduce, not deduce. Just corrected that. Thank you :) – Walt Lin Jun 26 '18 at 23:51