Compare two hashes with different salt

Question

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:

1. Does this seem secure?
2. 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?
3. 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.

Answer 1

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.

Answer 2

No, you cannot do this. The entire purpose of a salted hash is to obscure the relationship between identical plaintexts and their hashes. Hashes' resistance to rainbow table attacks also relies on this feature.

Let there be two plaintexts $P_a, P_b$, two salts $S_a$, $S_b$ such that $S_a \neq S_b$, and two salted hashes $C_a = H(P_a, S_a)$, $C_b = H(P_b, S_b)$. Assume there exists a function $f(C_a, C_b)$ that returns true if $P_a$ = $P_b$.

As an attacker, say you want to determine the plaintext $P_a$ for some hash $C_a$. Compute $C_i=H(P_i, 0)$ and store the pair $C_i$, $P_i$ for all possible plaintexts $P_i$ (known as a "rainbow table"). You can now attack the hash $C_a$ with your rainbow table by calculating $f(C_a, C_i)$ for all $C_i$. When $f(C_a, C_i)$ is true, look up the corresponding plaintext in your rainbow table.

Answer 3

I am wondering whether this is completely impossible if you are willing to interpret Hash in a very broad sense and use pairing-based cryptography. Stephen mentioned in a comment that the entropy of the credit card is low, so we should not rely too much on it in any solution.

What I am considering is the following. Assume for simplicity that we have access to a symmetric pairing $e$ on an elliptic curve $E$, $P_0$ a point that generates $E$ and a hash to curve function $H$. For a credit card number $C$ and a salt $S$ (with large entropy, ideally $S$ is a random integer modulo the order of the curve), compute and store the pair $(S\cdot H(C),S\cdot P_0)$, note that the salt value $S$ is not stored.

To verify that a given credit card number $C$ corresponds to a stored pair, check whether $e(S\cdot H(C),P_0)=e(H(C),S\cdot P_0))$. To check whether two distinct pairs correspond to the same $C$, compare $e(S_1\cdot H(C),S_2\cdot P_0)$ and $e(S_2\cdot H(C),S_1\cdot P_0).$

From a security point of view, you can still do exhaustive search on credit card numbers to find which $C$ correspond to a given pair, but since each verification is done via a pairing, it is not going to be really easy.

I know that this is out of the salted hash model suggested in the question, but depending on your exact requirements, it might be useful.

Answer 4

No, you won't be able to do this.

The whole point of using salts in your hashes is to prevent two identical objects from hashing to the same thing. You want those two elements to be hashed in a way that an attack won't be able to tell if they are the same or different.

You would have to be able to "undo" the hash with the given the salt to do what you want, which is obviously not something good functions let you do.