# Multiple parties must encrypt and get the same result

Hopefully this question is not too simple - I did some research but with encryption I really don't want to make a mistake.

Our scenario is that multiple groups need to encrypt a number and arrive at the same result.

This is because they want to use credit card numbers to search for documents, but we are only willing to store an encrypted version of the number as a search index.

I believe a one way hashing function of some sort would be best, salted somehow.

Would this be secure, given that:

• We are storing a masked version of each number too (roughly half the number is visible, i.e. the non-personal details)
• An attacker could have an account and therefore know their own plaintext

AES-256 was discussed as it's fairly standard in the banking industry but I don't know if it's appropriate here - we would be unable to use a random salt or initialisation vector.

It may be better to accept the full number as a search term and encrypt server side, but for various reasons I don't believe this will be possible.

Thanks.

-
Do they need to always arrive at different results when they start with different numbers? $\hspace{1.22 in}$ –  Ricky Demer Aug 22 '13 at 8:54
Yes - but for now we can assume a very low chance hash collision is probably acceptable, as users can view the documents to find what they are looking for. –  Nick P Aug 22 '13 at 9:01
Do you want to defend against a brute-force search by an attacker who knows the system-wide key $\hspace{.01 in}$? $\;\;\;\;\;$ –  Ricky Demer Aug 22 '13 at 9:08
with half the number visible you have 8 digits that are unknown (for a 16 digit number), quite easy to brute force –  ratchet freak Aug 22 '13 at 10:21
Are the hashes (and the 8 digits stored in plain) public information, or can you keep them hidden on your own servers and only allow on-line existence queries? That would significantly affect the options you'll have. –  Ilmari Karonen Aug 22 '13 at 13:01

Your approach is absolutely not secure.

The problem is mathematical, not technical. The search space is simply too small. There are only a finite possible number of values for an account number, and all an attacker has to do is try them all. If his output matches your stored value, he learns the account number. The technology choice of hashing with SHA-256 or encrypting with AES makes no difference.

Account numbers are 16 digits, so it looks like an attacker has to test $10^{16}$ possible values. To a specially crafted application running on a massively parallel processor like a graphics card, that's no longer a big number. (Machines capable of executing 348 billion hashes per second are now being built by hobbyists.) But account numbers don't have that much uncertainty. Valid BIN numbers reduce the attackers job by a factor of a hundred thousand. In your case you said you are keeping half the number visible (masking the other half), so the search space drops to $10^{8}$ possible tests. I can also use the Luhn check digit to recover an additional hidden digit, meaning I only have to try $10^{7}$ possible numbers.

And I'm just making a guess here, based on the statement that you're revealing "roughly half" the number. I assume you're revealing the last four digits, because you probably print those on your receipts and don't consider them secret. And I assume you're revealing the first four digits, because they're the Bank Identification Number (BIN). But BINs are actually six assigned digits, and given the first four I can probably determine the next two with a fairly high degree of certainty (there are far less than the 999,999 valid BINs suggested by the range). So knowing 10 digits plus the Luhn algorithm gives me $10^{5}$ uncertain digits. That's only a hundred thousand attempts, and I can spin through that many tests in a second on my PC without even invoking the graphics card!

The secure approach is to use a service to replace the account number with a non-mathematically-derived value, commonly called a token. Inside the secure service is where you would place the encrypted account number and perform your look-ups. An auto-generated sequence number is fine for this. Instead of giving each group the algorithm to look up an account number on their own, you grant them access to the service.

The service would need to be strongly protected against unauthenticated and unauthorized access, with audit logs tracing whoever is using it. If someone wants to run a million tests, at least you have the chance to detect them.

Also see the PCI Guidelines for advice on handling "multi-use tokens" which is this type of use.

-
The OP could also use format-preserving encryption, which gives decent provable security when encrypting very short strings. The paper 'Format-preserving Encryption by Bellare et al. is a good starting point. –  pg1989 Aug 22 '13 at 19:31
FPE is good if you're trying to fit 16 encrypted bytes in the place of 16 cleartext bytes. But that's not the problem they're trying to solve. They're trying to produce identical encrypted values for each account number, as he stated that multiple teams need to "arrive at the same result", so they could correlate or index encrypted account numbers. That requirement precludes random IVs or salts that would prevent such an attack. –  John Deters Aug 22 '13 at 19:38
So basically, "that's not the problem they're trying to solve, except that it is."$\hspace{.02 in}$? $\hspace{1.61 in}$ –  Ricky Demer Aug 22 '13 at 19:51
No, it answers a question about encryption, but doesn't solve the security problem of the possible account number space being easily searchable. –  John Deters Aug 22 '13 at 19:54
Does your suggestion come any closer to solving that security problem? $\:$ –  Ricky Demer Aug 22 '13 at 19:59