1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Why would you want such a thing? $\endgroup$ – Squeamish Ossifrage Nov 7 '17 at 19:11
  • $\begingroup$ I guess one may want such a thing to hash passwords, prevent password reuse and defeat rainbow tables. $\endgroup$ – user2233709 Nov 7 '17 at 19:47
  • $\begingroup$ indeed, those are viable options. But I don't have an implementation, just want to know if such technology exists. $\endgroup$ – aCryptoNewb Nov 7 '17 at 20:37
  • 1
    $\begingroup$ 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. $\endgroup$ – bmm6o Dec 8 '17 at 0:58
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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