# Comparing different hashes to confirm they came from the same string

Is there any safe hashing algorithm that returns a different hash each time (like bcrypt) but has the possibility to compare 2 different hashes and determine that they were hashed from the same password/string without knowing this password/string?

• Why would you want such a thing? – Squeamish Ossifrage Nov 7 '17 at 19:11
• I guess one may want such a thing to hash passwords, prevent password reuse and defeat rainbow tables. – user2233709 Nov 7 '17 at 19:47
• indeed, those are viable options. But I don't have an implementation, just want to know if such technology exists. – aCryptoNewb Nov 7 '17 at 20:37
• If the "determine" step is efficient, it seems to undo the benefit of the different (salted?) hash output. Given the hashed password, I could check if it was compatible with the hash of "qwerty", i.e. use my pre-computed hash dictionary. – bmm6o Dec 8 '17 at 0:58

Here's a thought; we work in a pairing-friendly elliptic curve where the discrete log problem is hard, and we generate a 'hash' of a value $p$ [1] by selecting a random value $r$, and outputting the two points $(rG, rpG)$.

Then, given two such hashes $(rG, rpG)$ and $(r'G, r'p'G)$, we can check if they are hashes of the same password by computing the two pairing operations $e(rG, r'p'G)$ and $e(r'G, rpG)$. If $p = p'$, then both values will be the same, namely the value $e(G, G)^{rr'p}$.

Reversing the hash, that is, given $(rG, rpG)$, recover $p$, is a discrete log problem, this is assumed to be hard.

And, given a long list of hash passwords $(rG, rpG), (r'G, r'p'G), (r''G, r''p''G), ...$, there doesn't appear to be any obvious way to compare all of then against an attacker chosen password with less than $O(n)$ pairing operations or point multiplications.

The attacker can test a single hash $(rG, rpG)$ against a test password $p'$ by checking if $p'(rG) = rpG$; however with any such primitive where there is a primitive to compare hashes, the attacker could perform this test by hashing the password $p'$ and using the comparison primitive to see if that hash matches the one under test, and so this is not a vulnerability.

[1] The value $p$ might be a conventional hash of the actual password; that detail isn't important for this idea.

Noting that I would not call such a hash function safe, if you knew that the strings you wanted to check were less than $2^b$ in number, you could use a strong (pseudo)random permutation $$\pi:\{0,1\}^b \rightarrow \{0,1\}^b$$ (so you could hide the string or the index to the string) and a hash function $H$ with $n$ bit output (with $2^{n/2}$ bit security against collisions) and output the $n+b$-bit vector: $$(H(X) \mathbin\Vert \pi(X))$$ where $\pi$ should be chosen to hide things such as weight of the vector (a plain bit permutation wouldn't do).

• How does this prevent an adversary from performing offline guessing attacks by evaluating $\pi$ when they compromise the password database? – Squeamish Ossifrage Nov 7 '17 at 22:23