Friday, December 27, 2013

Target: just 'cause it's 3DES doesn't mean it's secure

In a blogpost referring to the recent breach of millions of debit cards, Target claims there is no danger, because the PIN is encrypted with Triple-DES at the terminal, and decrypted at the payment processor. Since hackers stole only the encrypted PINs, Target claims the debit card info is useless to the hackers.

This is wrong. Either Target doesn't understand cybersecurity, or they are willfully misleading the public, or they are leaving out important details. In all probability, it's the last item: they left out the detail of there being salt.

Yes, Triple-DES cannot be broken by hackers. If they don't have the secret key, they can't decrypt the PIN numbers. But here's the deal: hackers can get PINs without decrypting them, because two identical PINs decrypt to the same value.

For example, let's say that the hacker shopped at Target before stealing the database. The hacker's own debit card information will be in the system. Let's say the hacker's PIN was 8473. Let's say that this encrypts to 98hasdHOUa. The hacker now knows that everyone with the encrypted PIN of "98hasdHOUa" has the same pin number as him/her, or "8473". Since there are only 10,000 combination of PIN numbers, the hacker has now cracked 1000 PIN numbers out of 10 million debit cards stolen.

This just gets one debit card. The hacker can crack the rest using the same property. The hacker simply starts at PIN number "0000", and then using online sites, starts using that number, trying one card at a time, until s/he gets a hit. On average, the hacker will have to try 10,000 before a good result is found. Once found, all debit cards with the same encrypted PIN of "0000" are moved aside to the "known" category. The hacker then repeats the process with "0001", "0002", and so on for all combinations.

This process is further simplified by the fact that some PIN numbers are vastly more common than others. People choose simply patterns (like "0000"), birthdays, and so on. The hacker can create a popularity distribution among the cracked PINs. Since "1234" is the most popular PIN number, the hacker can look at the most popular encrypted PIN and try that first. It'll probably work, but if not, s/he can try the next most popular encrypted PIN, until a match for 1234 is found. The top most popular 100 PINs can be discovered with only a few thousand attempts, giving over a million cracked debit cards to work with. This is something that can be done even if a person had to stand in front of an ATM for hours trying one card after another.

One way to correct this is to salt the encryption, such as using the credit card number as part of the key that encrypts the PIN, or as part of additional data prepended to the PIN. Done this way, every PIN number now decrypts to a different value. If they did this, then it would indeed be the same as if no PIN information were stolen at all.

As Mathew Greene describes, the Payment Card Industry (PCI) standards indeed call for salt, so this is probably what Target did.

It's nice that Target gives intermediate results of their investigation. Transparency like this should be commended. But they should just give us the raw information, like the specific PCI standard they follow, without the marketing spin about whether it's secure or not. I suppose I should've just known the PCI standard off the top of my head and filled in the blanks myself, but when I see incomplete info like this, it makes me distrust their honesty/competence instead.

Attila-Mihaly Balazs said...

To their defense, it is possible that they used a different key for each PIN and depending on the KDF, 3DES might be secure under those conditions.

I don't think this is the case, but just mentioning for completeness :-)

Also, see this post which just came up in my RSS reader: http://blog.cryptographyengineering.com/2013/12/can-hackers-decrypt-targets-pin-data.html

Brian B. said...

Except that PIN block format 0, which salts the PIN block with the account number, has been mandated by the networks for years. Identical PINs from different cards will yield different encrypted PIN blocks, making rainbow table type attacks useless.

JoachimV said...

The attacks described here are not possible and reflect a misunderstanding of how PINs are encrypted and the infrastructures, standards, labs, and certifications that go into PIN security. Wish we had such requirements for hashing storage of passwords.

PCI PIN and PCI PTS requires unique keys per device at a minimum and prevents the ability to try all possible PINs with trial and error. ANS X9.24 part 1 Annex A specifies DUKPT (Derived Unique Key Per Transaction) which derives a unique key for each PIN encryption. Almost all processors in the US use this standard for PIN encryption with ISO standard PIN blocks. Using either or both of these standards, it is not possible to rainbow table these blocks. They are not subject to the same attacks that affected Adobe passwords (which didn't follow best practices).

All the scholarly papers describing attacks on encrypted PIN blocks also recognize this fact and instead describe attacks against systems, not the data.

allen vondleslang said...

On average, wouldn't it be 5000 attempts (rather than 10,000)? Assuming even distribution, the first attempt has a 1/10,000 chance and the 10,000th attempt - if it gets that far - has 100% chance. Another factor to consider is that PINs are not equally distributed - so if they tried the popular combinations first, they probably would filter out a large chuck quickly.

Unknown said...

JoachimV is correct about DUKPT. Each PIN read uses a unique key used for asymmetric encryption. Only the credit card processor holds the keys needed to decrypt.

Additionally, you can't just brute force guess PINs against the encrypted PIN block. Think about it for a second. That would require the keys because this is actual encryption. This isn't like cracking passwords where you have a hash and brute force guess until the hash is the same.

Unknown said...

JoachimV is correct about DUKPT. Each PIN read uses a unique key used for asymmetric encryption. Only the credit card processor holds the keys needed to decrypt.

Additionally, you can't just brute force guess PINs against the encrypted PIN block. Think about it for a second. That would require the keys because this is actual encryption. This isn't like cracking passwords where you have a hash and brute force guess until the hash is the same.