16 into 7 -- key space surprise

Before I got into developing process control software my first real job out of school was at a large regional retailer. I started out as a sysadmin, ( a place everyone in I.T. security and development should spend some time but that is a rant for another day). Over time I did more and more support and ultimately development for a few internal applications which landed me in front of PCI auditors once a year to discuss coding practices, testing, data storage and all those good things that really need to be thought through.

To be fair to the QSA folks, ( PCI compliance), they have to know a lot of stuff so the fact that no one picked this up doesn't surprise me.

---

When a company is storing the hashed values of the credit cards they process for validating other business processes most people don't get too worried because if this information is lost in a data breach the hackers will need to apply brute force to determine valid card numbers. This means generate every possible number combonation of 16 digits, 10^16, apply the hashing algorithm then scan the looted data looking for matches. 10 to the power of 16 will take decades if not centuries to work through so this seems pretty safe but like I said, the details are in the implementation.

Each bank issues cards with their own 4 digit prefix, and if you took a guess at the 20 most popular cards you'd probably have a good start on the database content. The attacker preseeds the top 20 prefixes in their number generator and they move from 10^16 to 10^12, big time savings by ruling out 10,000 incorrect starting places. This rules out 10^16 - 10^12=9999000000000000 combinations, which is 1/4 of all possible combinations.

The next little wrinkle comes from the way most apps present stored credit card data, it is ok to show the last 4 digits in clear text. Since you can't extract data from a hash there is usually a link from the hash to the last 4 digits, we now have only 8 digits to figure out. 10^16 is now 10^8.

There is one more wrinkle, and this is something seen in other crypto implmentations as well that becomes an achillies heel. The card brands use a public algorithm called luhn 10 that is used to validate the card as a possible card number before they start to process it. This effectively drops the number of possible numbers to be hashed down by an order of magnitude. If the card prefixes were random and data storage of 4 end digits was not in place moving from 16 to 15 wouldn't be such a big deal it's still huge. Business needs to get done though, so there are a number of very good reasons 8 of the 16 digits need to be visible, unfortunately that reduces the number of possible answers down to 10^7.

Cactus did the math and also tried it on his regular home computer. Brute-forcing one credit card takes several minutes. Assuming we have a database of 1 million cards and using something fairly fast and multiple threads all card numbers could be guessed via brute force in a few weeks, nothing like decades or centuries. The take-away here is securing all the data in an application is essential, even if people have been sold on the idea that it is safe because of encryption.