Breaking Credit Card Tokenization – Part 1
December 09, 2015
This is the first in a series of blog posts on the topic of breaking credit card tokenization systems and is the written version of several conference presentations I have given on this subject. This post will address the core terms and history before digging into one of the attacks we have successfully executed against some of our retail clients’ tokenized payment systems. Other attack techniques that we have also successfully executed against clients’ systems will follow in future posts.
Note that none of the attacks discussed in this series are cryptographic attacks on the generation of tokens. Instead, all are attacks against the integration of tokenized payment services with another front-end retail application.
About Credit Card Truncation
Long before the idea of tokenization came along, PCI-DSS approved the storage of a credit card’s six-digit prefix representing the issuing bank and the credit card’s four-digit suffix. This is called “truncation” in PCI parlance. Essentially, all a merchant needs to eliminate is the middle six digits (six-digit prefix + four-digit suffix = 10 digits), as shown in the figure below:
Computational Complexity of the Middle Six Digits
At first glance, the worst case for brute force guessing the middle six digits from a truncated credit card number appears to be 106 (or 1,000,000) tries. However, credit card numbers implement the Luhn Algorithm (http://en.wikipedia.org/wiki/Luhn_algorithm), also known as the “mod 10” or “modulus 10” algorithm, which uses the last digit in the card number as a check digit. This reduces the potential brute force guesses by an order of magnitude—reducing the worst case to 105 (or 100,000) tries. The average case is 50,000 tries and the best case, of course, is a single lucky guess. Offline brute force attacks of a password with such low computational complexity is a trivial task, but in most credit card tokenization scenarios, brute forcing those middle six digits requires an online attack, which is considerably more difficult.
About Credit Card Tokenization
A common practice with PCI compliant merchants is to reduce PCI scope by eliminating the full 16-digit credit card number from commerce systems, only storing a “token” that represents the credit card. This process is known as “credit card tokenization” in PCI parlance. The ultimate benefit to the merchant is the reduction of PCI compliance scope and risks related to breaching the outward facing point of sale systems.
There are several implementation variants to credit card tokenization. Some tokens are surrogate numbers 16 digits long so that they fit in the same space already allocated to “real” credit cards in legacy point of sale systems. Other tokens are longer, requiring modification of the commerce system to contain them, and can be based on salted cryptographic hashes of the original card number, or just extremely random identifiers.
The most common implementations rely on the full credit card processing and storage capabilities of large payment gateway service providers. However, some larger enterprises have chosen to implement their own payment tokenization systems internally, typically hosted in a DMZ, separated away from the commerce systems to reduce PCI scope. In those scenarios, enterprises have essentially turned a small portion of themselves into tokenized payment gateway service providers and are choice targets for tokenization exploits.
The enterprise “DIY” version is the target of this blog series, although some of the attack techniques could possibly carry over into the commercial tokenization services offered by payment gateways.
Regardless of the architecture, if a full credit card number is transmitted to a system component, that component is IN PCI SCOPE. For almost a decade now, I have explained this as “PCI cooties, you touch it, you’ve got it.” This is important to remember when considering the attacks described in this series.
For the purpose of this blog series, the term “malicious insider” will mean an employee or contractor of the merchant who has access to the front-end retail application, but is unauthorized to access the back-end payment system that contains the full 16 digit Primary Account Numbers (PANs) that correspond with tokens. These insiders may be in system admin, developer, DBA, or similar roles within the merchant and will likely have access to truncated PANs, customer billing information (names, addresses, phones, etc.), and, of course, tokens. They also have the ability to observe the front-end talking to the tokenized systems.
The Ideal Defense Against Malicious Insiders
The ideal defensive position is to implement credit card tokenization such that the malicious insider’s ability to attack is identical with brute forcing truncated PANs. This could entail a malicious insider exfiltrating customer billing information, truncated PANs, and expiration dates, then performing online attempts to place transactions at other merchants. Fifty thousand failed transactions later (on average), perhaps they’ll get the card number right, and perhaps that card will have some available balance for causing damage. However, this is a noisy attack where the payment gateway and the banks will implement their fraud checks. This is a very safe place to be as a tokenized merchant.
The Worst Case Defense Against Malicious Insiders
This worst-case scenario is only applicable to payment gateways exposing a tokenization API, or to those enterprises that run their own centralized instance of a tokenization service internally, and mirrors an engagement with a retail client (names, URLs, and parameters changed to protect the innocent, of course). Suppose an internet-facing commerce application (store.example.com) embeds a call to a web API in a special PCI DMZ that takes a credit card as input similar to this request:
POST /api/generateCcToken HTTP/1.1
HTTP/1.1 200 OK
We can assume the hash is concatenated or salted with secret values only a select few may have, so offline attacks are basically pointless. They aren’t impossible, just implausible. Since this call to /api/generateCcToken was on a different server and DNS domain (payment.example.com) in the PCI DMZ, separate from the main application (store.example.com), no authenticated session cookies accompanied it. In other words, all requests to this service were essentially anonymous. Even if front-end application (store.example.com) set its cookies to the parent domain (example.com), the session data could not be shared between the store and payment service, because it blurs the lines of segmentation and likely passes the “PCI cooties” from the payment server to the store. Once the payment server generated the hashes, they lived in a database accessible to business users, through an internal web app, for legitimate sales and customer support reasons. The users could search on name, expiration date, and other transaction metadata, revealing the hashes and truncated PAN. See where this is going yet?
If a malicious insider would target a specific tokenized credit card record, extracting the truncating PANs and metadata, that malicious insider could interrogate the /api/generateCcToken service by iterating through all of the possible 105 permutations of valid credit card numbers that satisfy the Luhn check until the output matches the hash stored in the front-end application’s database. One hundred thousand queries all at once in a row might raise some eyebrows (or it might not, depending upon the monitoring and size of the environment), but 100,000 queries spread out over days or weeks might not, especially if more than one tokenized credit card is targeted, and if multiple source hosts can be used to further anonymize the requests (think: botnet). Since this API call only generates the tokenized credit card record and does not attempt to actually authorize a credit transaction through a payment provider’s merchant account, the bank’s fraud system would never come into play. If the enterprise’s internal tokenization system processes thousands of legitimate requests per day or more, it would be fairly easy for an attacker to “slow burn” the service to harvest the credit cards without detection.
Of course, this is why PCI DSS requirement 3.4 has this nice warning:
Note: It is a relatively trivial effort for a malicious individual to reconstruct original PAN data if they have access to both the truncated and hashed version of a PAN. Where hashed and truncated versions of the same PAN are present in an entity’s environment, additional controls should be in place to ensure that the hashed and truncated versions cannot be correlated to reconstruct the original PAN.
By correlating hashed and truncated versions of a given PAN, a malicious individual may easily derive the original PAN value. Controls that prevent the correlation of this data will help ensure that the original PAN remains unreadable.
A Better Solution
Consider if the request looked like this:
POST /api/generateCcToken HTTP/1.1
Assuming that the “authToken” parameter is encrypted with a key that is shared by the front-end e-commerce system and the payment service, and that the decrypted contents contain a unique identifier and some sort of time-to-live value, then the payment server could implement throttling and immediately identify and block bad actors. Essentially, this is a federated authentication solution to the prior problem, and federation is certainly not a novel idea. However, tokenized payment services in large enterprises commonly fail to implement proper hand-off authentication between the services. This solution won’t eliminate all abuse of the tokenization system, but it will considerably reduce its likelihood.
Stay tuned for more attacks against credit card tokenization systems in upcoming posts to this blog series.