Proper credit card encryption for use in a blacklist

Question

I have a general encryption question. I have read through many of the encryption related questions here and I can't find any specifically addressing my concern.

This is the hypothetical scenario:

• I am storing credit card numbers in a database
• The numbers are either encrypted or hashed
• A public facing application checks if customer requests contain credit card information on a blacklist
• An attacker has compromised the database and the ability to add credit cards to the blacklist.

It may seems unrealistic that an attacker could add credit cards without knowing the encryption key, but one scenario is that they make a request to the public facing application which appears to be fraud and will get the credit card automatically blacklisted by the application which knows the encryption key (This is a huge simplification of reality).

I want a solution which provides the following:
1) Insert a blacklisted credit card with O(log(n)) work or less
2) Check if a credit card is on the blacklist with O(log(n)) work or less. For example a btree index can provide O(log(n)) lookup work.
3) Have the credit card numbers secured with either encryption or a hashing function so that if the data is compromised the numbers will not be usable.
4) The attacker is unable to check if the card is on the list, even though they can insert values and can see the encrypted/hashed values.

My question is closely related to Hashing a credit card number for use as a fingerprint but the selected answer says "When a new card comes in, we look it up by comparing it to a hashed + salted column. If it matches that existing column we know we can return the same unique number identifier". This solution is not acceptable as this would require an O(n) lookup time. In other words I would need to check every row in the blacklist to see if the number is on the list.

First proposed solution : Typical lazy programmer answer
Don't encrypt. These are just bad fraudulent numbers anyway.
Failure: Just because we think these are bad customer's does not mean we should make the numbers public. It also does not mean we correctly blacklist 100% of the time and furthermore, even if a customer is bad and committing fraud we still don't have the right to make their number public.

Second proposed solution : Hash the credit cards without salt
This provides quick insertion and quick lookup. Simply hash the card number again and check if the hashed value is on the list.
Failure: The problem is that the attacker can brute force credit cards by simply hashing random card numbers and checking if the value is on the list. This is a problem even with a slow hashing algorithm because the space of valid card numbers is low and each hash checks against potentially millions of rows on the blacklist (Remember this is a hypothetical situation. I am not actually storing millions of credit card numbers).

Third proposed solution: Hash with a unique salt for each row
This solution can be provided easily with crypt(3) or something similar. It seamlessly stores the salt in the hashed value. Now if the attacker tries to brute force numbers they will have to also brute force the salt. This makes the attack infeasible. Failure: Now performing a blacklist lookup takes O(n) work. We need to call the slow hashing function on each row and the performance becomes unacceptable.

Fourth proposed solution : Hash with a global salt stored outside the database (HMAC)
Now the attacker needs to use the public facing api to perform a hashing operation instead of being able to perform millions of offline hashes per second. The reason they can not perform an offline attack is that the global salt stored outside the database is long enough that the salt can not be brute forced.
Failure: There is still the fact that an insertion checks against potentially millions of existing rows and the credit card state space is small. The attacker can perform 1000's of requests a day and log the ones which resulted as a duplicate in the database. The duplicates are credit card numbers which were already in the blacklist

Fifth proposed solution: Security through obscurity
Failure: This is not real security. It is tempting, but with the assumption that the attacker has compromised the database there is a real chance they are an admin internal to the company and have access to whatever solution and algorithm we have implemented.

Sixth proposed solution: Make another smaller table.
When blacklisting a number store the hash of the full number with salt in table 1 and the hash of the last 4 digits in table 2 without salt (with duplicates removed). When checking if a number is blacklisted check table 2. In most cases there will not be a hit and the check is quick. In rare cases there will be a hit and then do a slow check over table 1.
Failure: If I am storing thousands of records there is a very likely chance that the last 4 digits exist on this list. 4 digits is 10000 unique combinations, and with 10000 card entries there a large chance there will be a hit resulting in a slow check. Further, the attacker will know that entries in table 2 will have at least one match in table 1. They can brute table 1 with only 10000 requests and now they have significantly reduced the search space for table 1. The post quoted 100,000,000 as the likely size of the possible credit card number space. Table 2 would effectively reduce this space to 100,000,000/10,000 = 10,000. This means the time to reverse one hash would be roughly the time it takes my application to do the check over table 1 (10,000 rows in table 1 would mean 10,000 slow hashes and a brute force would also be 10,000 slow hashes)

All the solutions also apply to encryption instead of hashing. The benefit of encryption is that now the attacker has to do their attacks online to the public facing application. This still does not solve the problem as pointed out in proposed solution 4. Further more the risk of encryption, instead of hashing, is that if the encryption key is compromised the attacker has all the plain text values right away. At least with hashing they would only be able to brute force some of the card numbers on the list.

I have also looked into tokenization https://securosis.com/assets/library/reports/Securosis_Understanding_DBEncryption.V_.1_.pdf and the same problem exists, just in duplicate tokens instead of duplicate hashes.

Please note I want something stronger than PCI-DSS compliance. Solution 2 is technically PCI_DSS compliant because a salt is not required https://www.pcisecuritystandards.org/documents/PCI_DSS_v3.pdf (PDF link)

Sorry for the long post. Does anyone know if this is possible?

Answer 1

This is a pretty tall order, OP, and I don't think it is possible to do it perfectly. Nonetheless here are a couple ideas.

The attacker is unable to check if the card is on the list, even though they can insert values and can see the encrypted/hashed values.

The answer to this is to insert false positives. If a card is to be blacklisted, compute a hash (or hash + crypt-- see below) composed of PAN. If it is not, compute the hash as PAN + a nonce. In both cases, insert a record. To check to see if the card is blacklisted, recompose the hash without the nonce and check for it.

This way, a hacker can see that a record is inserted, but the insertion itself doesn't tell him anything.

Have the credit card numbers secured with either encryption or a hashing function so that if the data is compromised the numbers will not be usable.

Hash the PAN + long, systemwide cryptographic pepper (secret salt)

The pepper will add enough entropy to make brute force impossible without knowing the key. Store the pepper outside of the database.

To check for a match, perform the hash on the PAN of interest, then search the table. Because the secrets are all systemwide, you should be able to leverage an index, including the nice B-tree index that gives you the O(log(n)) performance you are looking for.

Answer 2

The biggest problem I see with your question is: Have the credit card numbers secured with either encryption or a hashing function so that if the data is compromised the numbers will not be usable.

This is a problem because as @Bobson stated in the comments Even hashing credit card numbers is problematic. Given the restricted nature of valid card numbers, it's likely that there's only one valid number which hashes to a given hash.

At first I thought that this was because the search space was limited to [0-9]{15-16} or 1.11 x 10^16 ... which is kinda bad but at an offline attack rate of 1.29 days per card number ... its not end of the world bad. But after doing a bit more research I found that the problem is actually much worse than this.

The first number on your card: If it starts with 3, it is an American Express, Diner’s Club, or Carte Blanche; 4 is reserved for Visa, 5 for MasterCard, and 6 for Discover. The next five digits will indicate the card issuer such as the bank or credit union, as well as the type of credit card. So for example, all Citi AAdvantage Executive MasterCards will begin with 546616 with the 5 representing MasterCard, and the 46616 representing Citi as well as the fact that it is one of their American Airlines AAdvantage Executive cards. The remainder of the 16 digits (or 15, in the case of American Express), represent both the cardholder’s account number as well as one or more “check digits.” source

For 16-digit numbers, start with the first number on the left, and double each alternating number on the card. (For 15-digit numbers, start with the second number from the left.) Add any double-digit numbers so that they reduce to a single-digit number. (For example, if one of the numbers is 8, it doubles to 16, then you add 1 + 6 to get 7.) Next, add those together with the alternating numbers that you did not double. If the total you get is divisible by 10, the credit card number is likely valid. source

So this means that in the number 1222-2233-4444-4444 your search space is only slightly more than [0-9]{8} which would mean:

• 1.29 days per card - Assuming one thousand hashes per second (online attack)
• 1.11 ms per card - Assuming one hundred billion hashes per second (offline attack)

source

this problem gets even worse when you factor in how many cards are actually in circulation

Type of Credit Card 2000    2003    2007    2008    2010    2012
Visa                 255     283     321     304     240     261
Mastercard           200     267     279     260     171     174
Store                597     521     546     539     318     455
Oil Company           98      86      73      65      35      60
Discover              50      54      57      58      55      59
American Express      33      36      52      54      49      52
Other                192     185     166     160     124     106
Total              1,425   1,432   1,494   1,440     992   1,167

*cards in millions 

source

This means that unless you have an additional source of entropy that is not stored in the database (aka not salt) nor in the program doing the hash (aka not pepper) besides the card-number itself ... storing the credit card hashes at all is not advisable.

Answer 3

But what if a hacker gets access to my live database and is able to arbitrarily enter information into it...

You could (actually should) argue that if a person can add things to your database that you have bigger problems than the security of your blacklist - let's start with privilege escalation, admin super user hacking etc (it's much easier to add/remove cards from blacklists through your admin interface than through your database).

And if we're talking about an offline dump of your database getting stolen then it's your duty to keep the PANs safe. According to the PCI DSS council "the good enough for PAN safekeeping is" defined in Requirement 3: Protect stored cardholder data of the PCI DSS' "Requirements and Security Assessment Procedures":

3.4 Render PAN unreadable anywhere it is stored (including on portable digital media, backup media, and in logs) by using any of the following approaches:

• One-way hashes based on strong cryptography, (hash must be of the entire PAN)
• Truncation (hashing cannot be used to replace the truncated segment of PAN)
• Index tokens and pads (pads must be securely stored)
• Strong cryptography with associated key-management processes and procedures.

Note: It is a relatively trivial effort for a malicious individual to reconstruct original PAN data if they have access to both the truncated and hashed version of a PAN. Where hashed and truncated versions of the same PAN are present in an entity’s environment, additional controls must be in place to ensure that the hashed and truncated versions cannot be correlated to reconstruct the original PAN.

I would argue, though, that the note in the bottom implies that the PCI DSS council expected people to not salt their hashes. Read more about hashes & their security later.

Please note that all of the options I'm listing here are "good enough" per PCI DSS standards, in varying levels of usability and paranoia.

Option 1: use only the masked PAN

(and a masked PAN is first 6 and last 4 chars of a PAN)

Use the masked PAN for blacklisting. I have seen precious little cards in my history where 2 users came with the same masked PAN and different full PANs, perhaps it's rare enough to make it a Helpdesk and not a programming issue.

Option 2: use the masked PAN and the encrypted PAN

If you want to guard against this eventuality, use masked pan to grab a number of rows (usually 1, almost never 2), and then compare against a salted hashed PAN, a global salt will do. But at this point you might as well use the encrypted PAN too (decrypt & compare) because 99.99% of the time you will be comparing with just 1 record.

• Q: but this doesn't work for me, my masked PAN is just the Luhn digit! What can I do?
• A: then sorry, obviously you can't use this approach, just remember that the PCI council considers first 6 and last 4 to be the "masked PAN". You can still use hashing though, keep reading

Option 3: use the hashed PAN

No, you don't need to check O(n) records to do a verification. Use a table-level pepper and a database index and ditch the salt.

Hashes security is a another story altogether, but remember:

1. table-level strong pepper should be enough, salt isn't helpful so much because it gets stolen with the database
2. perform the hashing operation repeatedly, a number of times, a practice called stretching
3. store & use the pepper via an HSM

Take a look at this implementation to give you a general idea.

Does your HSM allow for such a scheme? Digests are generally poorly supported in hardware HSMs, so you can use normal 3DES/AES for the same thing.

• Q: I know this approach is probably stronger than the security of my admin's passwords but I still don't feel sure about this, it's software-stored peppers after all, and they're table-wide, it feels insecure
• A: OK - but remember - this is what PAN peppers are for - this approach is above and beyond what's required by PCI DSS - while row-level salts are something that makes rainbows attacks harder they're also something you steal together with the hashes themselves so their security is moot compared to something that's not stored in the database - like a database-level pepper - but OK, keep reading, you can extend this approach by applying your HSM to the problem

Option 3b: hashed + encrypted PAN

Use a 3DES or AES cipher (I just refer to them as "DES" in this section, don't be confused by this) in ECB mode or with fixed IV in CBC mode. For added security through obscurity you can encode something in the IV, such as parts of the PAN or, stronger - another cryptogram that's accessible only via the HSM (ECB encrypted PAN or its derivation comes to mind as a decent IV candidate).

Use the same technique as described before and as shown in the code sample I provided - with the global pepper - with or without the digest & under DES - this will make sure that if an attacker runs away with your database & your code base & your server setup that he will not be able to start a rainbow attack without breaking DES first and this is "impossible" because the DES keys are in the HSM.

Note that ECB and fixed IV CBC in this case is "good enough" because of the underlying randomness of the peppered and hashed material.

• Q: but I'm still not happy because ....
• A: well.. keep reading

But in the end...

I'm pretty sure you can't make the scheme more secure than this while still keeping the function it's supposed to do.

Security and usability are two polar opposites, don't go full paranoid mode, be smart. Full paranoid mode can backfire in interesting ways, from my experience, so far:

• I can already imagine that in your institution while you're looking for the perfect solution some lazy programmer implemented clear PANs in the database 6 months ago because the management was shouting - it's probably not like you're running without a blacklist all this time - I've seen this happen with a global e-Wallet provider - if this is your case - you're not alone
• a military intelligence institution and a bank with strong enforced passwords - passwords written on a post-it on the back-side of the keyboard and "not passwords.txt" file on the desktops, respectively
• a super-uber-PCI-DSS-got-nothing-on-this secured national bank in the EU with contactless PKCS11 wallets you carry on your person - being there as a third party contractor I found out they gave us "blank access" cards to all areas of the building and all computers because the "third party" module of the security software wasn't compatible with the "linux drivers" whatever that means
• a super-secure PCI DSS environment and a single "magic cable" "hidden" from the CSO sticking out of the secured box and into a router because the protocols didn't foresee mass hardware migrations in a secure closet with limited drawers
• same institution as the last point, a bug in the software in which first 8 chars of 10-20 PANs appeared in a log in a secure environment (by PCI standards). Someone would have encrypted the logs, but the CSO argued that it conflicts with some "ease of use clause" in the PCI specification and insisted that the issuers of the cards be contacted to blacklist the cards and reissue them because "they have been compromised", the backlash of the banks who were also partners was pretty understandable, this CSO lost his job eventually
• PIN cryptography, protection vs cloning Visa/MC cards is protected by 2-length DES keys with ECB, never broken cryptographicaly, but people write their PINs on cards because they're hard to remember and US still afaik by and large uses magstripe because EMV is hard to implement
• Mifare cards, single length DES encryption by-and-large - 10 billion chips, 150 million readers, only extended recently after successful breaches by AES with a key negotiation scheme which might as well have been written by a child (one party makes half a key which is concatenated to the other party's half-a-key instead of a proper full-length XORing scheme - and the initial key exchange when the master key is loaded into the card is still DES with a predefined 000..0000 key) - considered secure
• and let's remember https://xkcd.com/538/ :D

So yeah, if you're trying to be holier than Pope in relation to security, you do it at your own risk, don't be a fundamentalist, be smart. Focus your energy on securing your system where it matters most - and the blacklist almost certainly isn't it.

I'm guessing this because generally by the time you have a blacklist you already have a "secure card lookup mechanism" in place for the transactions, risk rules etc and the problem was, generally, solved months ago. And this isn't the case here.

PS get an online API and try a brute force "scan" (1$ authorizations) of 10.000 card numbers and see what the processor tells you about it. There are checks and balances against this in place, read:

• "VISA: Global Acquirer Risk Standards"
• "VISA: Global Brand Protection Program Guide for Acquirers"

to learn a bit more about them.

Answer 4

I think that this is a case where you should re-work the problem.

There's no getting around the ridiculously small space of valid PANs. ALL of your security comes from entropy (salt) and work (iterations), and you're asking for that for free. You won't get it for free.

The only way to speed it up is to try to make sure you don't have to do those computations most of the time, by making a sort of "pre filter." All possible pre-filters are equivalent in that they are probabilistic and cannot make guarantees on complexity. All of these pre-filters return only "possibly in set" and "not in set." They leak that data. You can't get around this.

A simpler,faster pre-filter like a bloom filter doesn't give you a bounded set to search, even though it has a nice fast running time of O(1). A two-table approach like in proposed solution #6 gives you the exact set to search, but is more complex - o(log(n)).

But wait - how is solution #6 equivalent to a bloom filter? Well, a bloom filter returns "0 to search" or "n to search." It tells you "not in set" or "possibly in set." What do we get out of the two-table solution?

Two tables exist: One with masked PAN (first 6 and last 4 digits), hashed with global salt, where each record points to rows in a full table with full PANs, hashed strongly with unique salts. You hash your incoming PAN's masked form and do an o(log(n)) search vs. the pre-filter table.

Now that we have done our o(log(n)) search, we end up with between 0-n possible hashes to compare against, and smaller numbers are much more likely. A match number of 0 is "definitely not in set," and 1+ is "possibly in set." Then you still have a (probably small) number of difficult computations to make to check against strong hashes.

Whether it is a bloom filter or an o(log(n)) two-table approach, or any other, all the work gets done somehow. You just can't cheat it. You can fine-tune it, but you can't cheat it.

Any other method is equivalent to this. Reducing the entropy by having an easy pre-lookup means reducing the problem space, which you then try to map to a larger problem space, which means that you are working with probabilities.

These are just the facts from an information theory standpoint. So, I suggest that you re-work the problem, not the solution.