Can hackers decrypt Target's PIN data?

Friday, December 27, 2013

Can hackers decrypt Target's PIN data?

Short answer: probably not.

Slightly longer answer: it depends on whether they have access to the encryption key, or to a machine that contains the encryption key.

In case you have no idea what I'm talking about: there was recently a massive credit card breach at Target. If you're like many people you probably heard about this three times. First in the news, then again in your email when Target notified you that you were a victim, and finally a third time when you checked your credit card bill. Not a proud day for our nation's retailers.

The news got a bit messier today when Target announced the thieves had also managed to get their hands on the PIN numbers of unfortunate debit card customers. But this time there's a silver lining: according to Target, the PIN data was encrypted under a key the hackers don't have.

Snyder said PIN data is encrypted at a retail location’s keypad with Triple-DES [3DES] encryption and that data remains encrypted over the wire until it reaches its payment processor. Attackers would have to have compromised the point-of-sale system and intercepted the PIN data before it is encrypted in order to have accessed it.

Several folks on Twitter have noted that 3DES is no spring chicken, but that's not very important. Aside from a few highly impractical attacks, there isn't much to worry about with 3DES. Moreover, PCI standards appear to mandate unique keys for every payment terminal, which means that the attackers would need to compromise the terminals themselves, or else break into the back-end payment processor. If Target is to be believed, this has not happened.

Others have pointed out that PINs are pretty short. For example, there are only 10,000 4-digit PINs -- so surely the attackers can "brute-force" through this space to figure out your PIN. The good news is that encryption is decidedly not the same thing as password hashing, which means this is unlikely to be a serious concern. Provided that Target is being proactive and makes sure to change the keys now.

Of course you shouldn't take my word for this. It helps to take a quick look at the PCI PIN encryption standards themselves. Before you encrypt a 4-digit PIN, the PIN is first processed and in some cases padded to increase the complexity of the data being encrypted. There are four possible encryption formats:

• Format 0. XOR the PIN number together with the Primary Account Number (PAN), usually the rightmost twelve digits of the card number, not including the last digit. Then encrypt the result using 3DES in ECB mode.
• Format 1. Concatenate the PIN number with a unique transaction number and encrypt using 3DES in ECB mode.
• Format 2. Pad with some fixed (non-random) padding, then encrypt in 3DES/ECB with a unique, derived per-transaction key (called a DUKPT). Update: only used for EMV cards.
• Format 3. Pad with a bunch of random bytes, then 3DES/ECB encrypt.

Notice that in each case the encryption is ECB mode, but in Formats 0, 1 and 3 the plaintext has been formatted in such a way that two users with PIN "1234" are unlikely to encrypt exactly the same value under the same key. For example, consider the Format 0 encryptions for two users with the same PIN (1234) but different PANs:

(PIN) 0x1234FFFFFFFF ⊕ (PAN) 0x937492492032 = 0x81406DB6DFCD
(PIN) 0x1234FFFFFFFF ⊕ (PAN) 0x274965382343 = 0x357D9AC7DCBC

Notice that the values being encrypted (at right) will be quite different. ECB mode has many flaws, but one nice feature is that the encryption of two different values (even under the same key) should lead to effectively unrelated ciphertexts. This means that even an attacker who learns the user's PAN shouldn't be able to decompose the encrypted PIN without knowledge of the key. Their best hope would be to gain access to the terminal, hope that it was still configured to use the same key, and build a dictionary -- encrypting every possible PIN under a specific user's PAN -- before they could learn anything useful about one user's key.

This does not seem practical.

The one exception to the above rule is Format 2, which does not add any unpredictable padding to the plaintext at all. While the PIN is padded out, but there are still exactly 10,000 possible plaintexts going into the encryption. PCI deals with this by mandating that the payment terminal derive a unique key per transaction, hopefully using a secure key derivation function. Update: this one probably isn't used by Target.

All of this is a long, dull way of saying that encryption is not like password hashing. Provided that you can keep the keys secret, it's perfectly fine to encrypt messages drawn from even small message spaces -- like PINs -- provided you're not an idiot about it. The PCI standards clearly skirt the borders of idiocy, but they mostly steer clear of disaster.

So in summary, Target debit card users are probably just fine. Until tomorrow, when we learn that the thieves also have the decryption keys. Then we can panic.