# 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:

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.
-
Not only can this not be done securely, but it also cannot be done. The entire purpose of salted hashes is to prevent this exact scenario. –  Stephen Touset Jul 12 '13 at 17:53
I don't follow. I thought the purpose was to prevent rainbow table attacks. It seems that the existence of f doesn't necessarily mean a rainbow table attack is now possible. Note that f doesn't reveal the credit card number, it just tells me if C1 = C2. If I had a rainbow table, I'd still have to compute f(table entry, salt) for each entry in the database, which isn't any faster than just computing the salted hash of every possible credit card, right? –  Oliver Jul 12 '13 at 18:00
Assume some method exists to determine if $C_a = C_b$ given $H_a = H(C_a, S_a)$, $H_b = H(C_b, S_b)$. Generate a rainbow table of all possible $C_i$ mapped to $H_i = H(C_i, 0)$. Compare $C_a$ against all $C_i$ using the method we assume exists. –  Stephen Touset Jul 12 '13 at 18:20
Salted hashes prevent rainbow attacks precisely by obscuring the relationship between any $C_a$ and $C_b$. It's the entire mechanism of action. –  Stephen Touset Jul 12 '13 at 18:25
If there was a method to compare two salted hashes for equality of their inputs, an attacker would be able to build a rainbow table with the salt set to zero for all entries. He could then use that method to compare his rainbow table against your list of salted hashes. –  Stephen Touset Jul 12 '13 at 18:28

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.

-
Nice. The only difficulty is indeed to find a hard to factor number $N$. The problem with selecting an RSA-challenge number is that it is hard to factor, but there is a trapdoor to your scheme: the factorization which is known to the person that generated the challenge (unless they forgot it, but can we be sure ?). In fact, this is a very nice question: is it possible to construct a provably hard to factor number in a way that does not construct the factors at the same time ? –  minar Jul 12 '13 at 20:43
@minar: That's exactly why I suggested the RSA-challenge numbers; that is, from a specific challenge dating started in 1991; see en.wikipedia.org/wiki/RSA_Challenge ); RSA Data Security (the company that generated the challenge) was quite clear at the time that they did not know the factorization themselves. –  poncho Jul 12 '13 at 20:56
If you are paranoid enough, you may not believe them :) –  minar Jul 12 '13 at 20:58
Beautiful!! Thanks! –  Oliver Jul 12 '13 at 21:24
@owlstead: I'm not sure either if I got this idea from elsewhere, or it just occurred to me. As for the performance, true, modexp is slow. On the other hand, when hashing a password, we often deliberately choose a slow hash function (e.g. PBKDF2); the question then becomes "how do we make modexp slow enough" (and the answer to that would be to make $hash(Salt)$ a sufficiently big integer; possibly much larger than $N$. –  poncho Jul 14 '13 at 16:30

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.

-
Note that salted hashes aren't a great mechanism for storing credit card numbers, which only have around 48 bits of entropy. This is well within brute-force range. Best is a slow salted hash, like PBKDF2, bcrypt, or scrypt. –  Stephen Touset Jul 12 '13 at 18:46
Isn't computing $f(C_a, C_i)$ for all $C_i$ the same amount of work as computing $Hash(C_i, Salt)$ for all credit card numbers? In other words, I don't see how the existence of the rainbow table makes cracking things any faster if $f$ exists. What am I missing. I definitely understand the concerns about using a fast hash and the small space of credit card #'s. –  Oliver Jul 12 '13 at 18:57
Notice that I said nothing about credit card numbers in my answer. This is a property of salted hashes themselves, not salted hashes when used on credit card numbers. Salted hashes do not allow what you are asking for. You indicated in your comments that you thought salted hashes prevent rainbow attacks. They do, and I am demonstrating that they do so precisely by preventing the sort of operation you would like to perform. –  Stephen Touset Jul 12 '13 at 19:06
I'm sorry I'm still not getting this. I really do appreciate the time you're putting in here. As I understand it, without a salt you can use a rainbow table to do an O(1) lookup of a hash. Thus the time required to crack a single hash is O(1). In your response, you say that with $f$ you can crack a hash by computing $f(C_a, C_i)$ for all $C_i$ which is $O(n)$, where $n$ is the number of credit cards in the world. Without $f$ you'd compute the salted hash of every credit card numbrer for a complexity of $O(n)$. Thus, the time to crack appears the same with or without $f$. What am I missing? –  Oliver Jul 12 '13 at 20:03
The "way they do it is by preventing the existing of" an easy-to-work-with way to compare the main hash inputs. $\:$ I believe the correct answer is "If $\hspace{.01 in}f$ can evaluated as fast as $h$ can, then slowing $h$ down further will only slow down precomputation.", which is far less definitive than "No, you cannot do this.". $\;\;\;$ –  Ricky Demer Jul 12 '13 at 21:48

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.

-
Thanks! This sounds really interesting. I don't know much about eliptic curve crypto, so I'm not sure if this does what I want, but this gives me a great place to start. –  Oliver Jul 12 '13 at 20:09
You could choose a database-wide triple workfactor,salt,memfactor and have H be given by $\hspace{.71 in}$ H(C) = maptopoint(scrypt(workfactor,salt,memfactor,C)) $\:$ . $\;\;\;$ –  Ricky Demer Jul 13 '13 at 0:31
If you use my suggestion for H, then the database-wide salt should be kept as secret as the pairs of group elements, so that one would need to compromise the database before one could start computing the scrypt values. $\:$ Independent of that, for minar's answer one would want to use a pairing that was slow to compute (however, I'm not aware of any such pairings). $\;\;\;$ –  Ricky Demer Jul 13 '13 at 0:47
Concerning the speed of pairings, it really depends what you call slow. Using PBC library (crypto.stanford.edu/pbc/times.html) you might get 100 pairings/seconds. With scrypt, things are of course going to vary depending on your parameters, but with the litecoin settings speeds on CPUs are about 2000 hashes/seconds (bitcointalk.org/index.php?topic=66811.0). –  minar Jul 13 '13 at 6:53

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.

-
I don't understand why you'd have to be able to "undo" the hash. For example, if hash(C1 || S1 || S2) == hash(C1 || S2 || S1) you can do this but you can't necessarily reverse the hash. The above doesn't work because order is important in hashing, but it's not obvious to me that this is impossible. –  Oliver Jul 12 '13 at 18:03