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.

20 comments:

  1. Nice explanation. Thanks.

    ReplyDelete
  2. Has anyone asked why Target is storing the card number and pin data in the first place? As a PCI compliant merchant, my TOS explicitly prohibited this for any POS transactions.

    ReplyDelete
    Replies
    1. Maybe the attackers were able to intercept the transactions (instead of gaining access to some card data storage). This would explain why the stolen data also includes the CVV(1), which is also not supposed to be stored by the merchant.

      Delete
    2. I have been asking myself this question since Christmas! I had not read previously that CVV was stolen however, that too should not be stored. Correct? I thought this was just a US thing and thought - they cannot do that here (Europe) and the US seems less reliant on chip/pin combo. Target (I happen to be in one late Dec) have those lcd pads you scribe a signature into. I wondered also if that image was encrypted/stored but that was before I realised nobody at all checks signatures against cards in the US.

      When raising this with a friend, he chortled about writing on the LCD pads 'please check my photo ID' instead of his signature, and he is never asked.

      Is card cloning likely? (asks a PCI novice)




      Delete
  3. Format 2 is actually only used for EMV cards, and as far as I know, Target (USA) does not have EMV terminals. Please update the article.

    ReplyDelete
  4. Great article, thanks!

    Do you have any idea why asymmetric encryption is not used for (online) PIN encipherment? When used with proper random padding, it would seem much safer than relying on a shared key.

    ReplyDelete
    Replies
    1. Asymmetric encryption at scale needed for PIN processing is subject to man in the middle and is computationally expensive. Not a good option. Symmetric key encryption in the US for PIN is done right and doesn't offer offline attack vectors for anyone who holds the encrypted PIN block

      Delete
  5. Why would you you steal all those PIN blocks if you don't have the decryption keys?

    ReplyDelete
    Replies
    1. Depending on the type of attack, this might have simply been a side-effect from capturing and recording all transactions. Those include the magnetic stripe data as well as the enciphered PIN values which are verified by the credit card networks.

      Delete
  6. Also, formula 0 and 3 can be used in a replay attack....

    ReplyDelete
    Replies
    1. not in practice. Replay woudl only work with the same processor (who has those master PIN keys) and if the processor doesn't use a unique master key for that merchant (probably does). So you'd have to hack the processor just to replay those PINs with a fraudulent transaction. Can't be used for ATM transactions. And not sure what that gets you as an attacker (force a card to be used as debit with a transaction hack from inside a merchant?) when you can just use the Debit PAN for a credit transaction anywhere without such heroic efforts to replay the PIN.

      Delete
  7. It seems to me that the hackers are eminently able to recover the PINs without the encryption key.

    The fact that ECB has been used means that unless some kind of per encryption IV has been used, the same bytes will be used to XOR each of the PINs (or transformed PINs) which means that a single known plaintext can be used to recover the cipher values.

    This can be obtained by going to the store and making a purchase with a known card. Since the whole card details have been known, the PIN is easily reversed from the additional transformations based on the credit card number.

    Even without the easily obtainable single plaintext, you could recover by XORing ciphertext against ciphertext to get plaintext XORed with plaintext.

    ReplyDelete
    Replies
    1. You're probably thinking about a stream cipher or one of the "stream modes" of operation of a block cipher (CTR, OFB, CFB). The XOR attacks you describe do not apply to "block modes" like ECB or CBC.

      Delete
    2. This comment has been removed by the author.

      Delete
    3. You're right, I'm thinking of OFB or similar modes.

      Delete
  8. Format 0 does seem to have a small weakness: there may be cases where, for two different cards A and B, (PIN_A xor PAN_A) equals (PIN_B xor PAN_B). Even if each PAN is unique this may occur when they have a predictable pattern (e.g. sequential numbers) and the different bits correspond to the bits that differ between the PIN numbers.

    This will probably not be much of a problem here. But perhaps, with the right PIN padding and PAN generation schemes this may just allow the attackers to obtain some useful information from this huge collection of ciphertexts.

    ReplyDelete
    Replies
    1. That's an interesting thought! Based on some napkin calculations and Wikipedia's description of Format 0's padding scheme (and the format of credit card numbers), the probability of such a collision is rather low: The 12 rightmost digits of the PAN are used (10 of them in an unmodified way; two are XORed with PIN digits) and those are the ones that seem to vary the most among different cards.

      A "partial collision", i.e. similar plaintext blocks that vary only in some digits, aren't useful, since 3DES-ECB is supposed to destroy all such plaintext similarities (as well as trivial XOR relations).

      Even if such a "collision" should occur (PAN number digits 7-16 are equal for two card and PIN1 (+) PIN2 = 0), the attackers can still only learn a relation between the two PINs, and not the PINs themselves.

      Well, there might be a big "collision group" of multiple transactions that yield the same ciphertext, and the attackers could brute-force through such a group by printing cloned cards and trying each PIN from 0000 to 9999, burning something like 10000/3 cards in the process (half of that on average). They would then have the valid PINs to the rest of the cards in such a group. (The first two digits of all those cards would be equal; the last two digits would have a (reversable) XOR relation to the account numbers of both cards.)

      The chances of such a big collision group should (hopefully) be minimal; it would require over 1000 cards with exactly the same 10 rightmost account number digits and related PINs in the set. Even if not all of those 12 relevant decimal digits are chosen uniformly at random (e.g. due to customer-chosen PINs (birthdays and year numbers could reduce the amount of entropy) and common account number digits), that's very unlikely.

      Still, having to rely on this instead of using a proper encryption and padding method seems to be one of the "skirting the borders of idiocy" parts of PCI...

      Delete
  9. The PINs would be encrypted with 3DES and each transaction would have a unique derived key, rendering unique ciphertext for each transaction, even with the same PIN. See DUKPT: http://en.wikipedia.org/wiki/Derived_unique_key_per_transaction

    Encryption keys come in 3 levels, though my nomenclature is technically incorrect:
    Super Secret - The root key from which all downstream keys are derived
    Pinpad Key - a Derived key from the super secret unique to each pinpad
    Transaction Key - A unique key per transaction derived from the pinpad key

    The processor can decrypt any key derived from its super secret, but it is impossible (such is the claim) to go from a transaction key back to the pinpad key or the pinpad key back to the super secret. Hence the maximum risk from intercepted pin blocks is a single compromised pin for each key cracked. In the event a pinpad itself is compromised, the maximum risk is any pin entered into that individual pinpad.

    The data flow for an auth transaction typically looks something like:

    Pinpad -> (Plaintext Track/Auth Data / Encrypted PIN) -> POS Computer -> (Encrypted or Plaintext Auth/Track Data / Encrypted PIN) -> Backoffice Payment Computer (Auth/Track Data may be decrypted and re-encrypted on this system) -> (Encrypted Auth/Track Data / Encrypted PIN) -> Processing Cloud

    or

    Pinpad -> (Plaintext Track/Auth Data / Encrypted PIN) -> POS Computer -> (Encrypted Auth/Track Data / Encrypted PIN) -> Processing Cloud

    The two points where data is most commonly stolen is in POS computer memory or in backoffice payment system memory where the data is momentarily unencrypted. It can also be captured between POS computers and the backoffice payment system if it is not encrypted on the segment between the two. Both CVVs and encrypted PINs can be captured this way without ever being stored or resident in the system for more than the few ms required to perform the auth.

    ReplyDelete
  10. They can phone or phish the mark pretending to be the bank and ask them for their PIN, like emailing a link to change it 'please enter your old PIN and new PIN'. Only do it to the cards with the biggest limit to avoid mass spamming/detection

    ReplyDelete
  11. See "The unbearable lightness of PIN cracking", http://dl.acm.org/citation.cfm?id=1785622

    ReplyDelete