PCI-DSS and Encrypting Card Numbers

OK, I'm about to do something dumb and talk about cryptography and cryptanalysis. I'm an expert in neither of these things. But despite the fact that somebody smarter than me should be telling you this, you're stuck with me, and I think I have a point. So here goes.

I had a bit of an "A-ha!" moment earlier today around PCI-DSS, specifically requirement 3.4 from v1.2 of the standard. Here's the relevant language from that requirement:

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

• One-way hashes based on strong cryptography
• Truncation
• Index tokens and pads (pads must be securely stored)
• Strong cryptography with associated key-management processes and procedures

The bottom line is that this requirement fails to provide adequate protection to card numbers. Here's why.

Truncation and tokenized strings with pads have limited use cases. In the case of truncating card numbers, PCI-DSS recommends only storing the last 4 digits of the card number. You wouldn't choose truncation for a program that validates a card number because there would be too great a potential for false matches. It would only be helpful for including in receipts, billing statements, and for use in validating a customer identity in conjunction with other demographic information. Database tokens only provide adequate protection in environments where there is a multi-user or multi-app security model, and if there are flaws in the applications that have access to the pads, then your data is pwned.

So for the sake of maximum versatility and security, you're likely (or your software vendor is likely) to opt for hashing or encryption. But you still have a serious problem. While one-way hashes like SHA and block ciphers like AES can provide good protection to many forms of plaintext, credit cards aren't one of them. That's right, the problem isn't actually in the way you encrypt credit card numbers, it's that credit card numbers make for lousy plaintext to begin with.

Take for example the following row of data from my hypothetical e-commerce application's cardholder table:

LNAME,FNAME,CTYPE,EXP,HASH,LASTFOUR
Melson,Paul,DISCOVER,06/2009,e4b769607856a2f30b57fd26079dfefb,1111

In this case, we have what we need to use the card, except the card number is hashed with MD5. (Ignore what you know about MD5 collisions for a moment, since this problem also exists for SHA or any other method of encrypting the card number.) If we calculate the possible number of values that could be on the other side of that hash, it would be 10^16, or about 10,000 trillion for the 16-digit card number. That's roughly twice as many possibilities as an 8-character complex password (96^8), which is an acceptable keyspace size, but also completely doable for a tool like John The Ripper.

But if you know credit card numbers, then you've already realized that it's even worse than that. The first 4-6 digits of the card number are a misnomer in calculating keyspace. There aren't 1 million actual possible values. Since that row from my e-commerce app's database told me the card issuer, I know within 4-5 guesses the first two to four digits of the card number, and the last four are right there as well for inclusion on statements, etc. In this case, since it's a Discover card, we already know that the card number is 6011XXXXXXXX1111. Now we've cut the possible values we must guess in half, from 10^16 down to 10^8, which is a mere 100 million possibilities. There are other clever things we can do if it's encrypted with a stream cipher like RC4 or FISH, because we know the beginning and end values of the plaintext. But guess what? It's cheaper and easier to brute-force it even if lousy crypto is used. Even on the scale of millions of records. Even with salting, it's still worth it to brute-force the middle digits.

But wait, there's more! As if publicly known prefix values weren't enough, credit card numbers are also designed to be self-checking. That is to say, the numbers contain something like a checksum that, when a known algorithm is applied to the 7-digit account number, 3 digits of which we know from our last-four field, can be used to validate the card number. This was designed as an anti-fraud mechanism that would allow cards to be checked without a need to communicate with a clearinghouse. But this algorithm allows us to only generate valid account numbers, combined with partially-known prefixes, to reduce the keyspace significantly. And since this is a known algorithm I can (and someone already has) very easily write a tool that combines a brute-force password cracker with a credit card generator.

The bottom line is that, because of the already-partially-known nature of credit card numbers, simply encrypting card numbers inside a database or extract file is insufficient protection. The PCI Security Standards Council should revisit this requirement and modify it to, at the very least, require symmetric-key block ciphers and disallow stream ciphers and one-way hashes. But even then, I suspect, encrypted card numbers will be at risk. Certainly row-level encryption of card numbers should not qualify for "safe harbor" when it comes to breach notification laws.

PS - Extra credit if you crack the full card number from the hash above and post it below.