Compare two hashes with different salt I'm storing the salted hash of a credit card number in a database. What I'd like to be able to do is determine if two different entries in the same database correspond to the same credit card.

Specifically, let $C_1$ and $C_2$ be two credit card numbers (which may or may not be the same). Let $S_1$ and $S_2$ be two different salts. If $H_1 = hash(C_1, S_1)$, and $H_2 = hash(C_2, S_2)$, I need a function, $f$, such that $f(H_1, S_1, S_2) = f(H_2, S_1, S_2)$ if and only if (with very high probability) $C_1 = C_2$.

Can this be done securely?

Possible Solution

A friend of mine, who is a cryptographer, suggested the following:

Let $h(C, S) = g_1^{h_t(C)}g_2^{S}$ mod $p$, where $C$ is the credit card number, $h_t(C)$ is a "traditional" hash function, and $g_1$ and $g_2$ are generators that meet the Diffie-Hellman requirements, and $p$ is the corresponding prime.

If we do that, $f(H_1, S_1, S_2) = H_1g_2^{S_2}$ has the desired property.

A few questions:


Does this seem secure?
If I used a library, like the Bouncy Castle libs, to pick $p$, $g_1$, and $g_2$, would it be safe for a non-cryptographer to code this up? In other words, how easy would it be for a non-cryptographer to screw up the implementation in a non-obvious way?
Advantages or disadvantages of this compared to the two other solutions proposed below. I tend to favor this because I'm familiar with Diffie-Hellman, while the others involve some techniques with which I am not familiar. Additionally, I suspect that there are more libraries for Diffie-Hellman since it's old and popular.
Well, as others have said, you would not be able to do with a standard salted hash function.

However, if you were use a specially designed hash function (that allows this specific comparison), then it would be possible.

Here is a proof-of-concept idea, to show that it is possible:


Suppose $N$ was a large composite number of unknown factorization
Let our hash function be $h( C, Salt ) = hash(C) ^ {2hash(Salt)} \bmod N$ (where $hash$ is a function that converts strings into large integers, in a way where hashes of different strings don't have obvious relationships).  The factor 2 is there to prevent the Jacobi symbol of $h(C, Salt)$ from leaking any information.


This hash function is one-way, because reversing it is the RSA problem, and that's hard if we don't know the factorization of $N$.

And, we can compare hashes $h_1, h_2$ with salts $Salt_1, Salt_2$, we just check if $h_1 ^ {Salt_2} = h_2 ^ {Salt_1} \bmod N$.

And, if you're wondering "how do we get a value $N$ which we know is hard to factor, well, we can just grab an RSA-challenge number of the appropriate size.

Now, I'm not really advocating this method (the "hashes" are quite lengthy); however it does show that it is possible in principle.