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?