Breaking Credit Card Tokenization – Part 2

This is a continuation of a series of blog posts on the topic of breaking credit card tokenization systems. Please read the first post in this series to get up to speed on general terms and background information before digging into new attacks discussed in this post.

Side Channels

Side channels are unintended ways information can be observed in a system. Attackers can leverage side channels to make software divulge details that developers never intended. For a deeper dive on the subject, look at Shannon’s Information Theory to understand key ideas like entropy and signal-to-noise ratios. In this post, we will dig into a timing side channel attack against credit card tokenization systems.

Timing Side Channel Attacks

Developers are trained from day one to optimize software performance, such as storing only a single copy of data on disk and having the fewest round trips to a server as possible. Credit card tokenization system developers are no different. Why store the same credit card multiple times or query the database an extra time? Like the other attacks from part one of this series, the devil is in the details.

On an engagement of a large retail client, a tokenization service’s response time was observed as being roughly twice as long if the credit card number submitted to the service was brand new (i.e. never seen by the payment server previously). And what was even better: the response time was dependably regular, similar to the following table:

  Card Number  Response Time  Hit or Miss?

  4532439427560932  299 ms  Miss

  4024007169153730  133 ms  Hit!

  4556321093065423  302 ms  Miss

  4024007106121014  309 ms  Miss

  4532521667742500  289 ms  Miss

  4929848318025691  301 ms  Miss

  4916627955332031  333 ms  Miss

  4539409392051871  127 ms  Hit!

  4532748467822774  312 ms  Miss

  4509138606233639  299 ms  Miss

  4532572116633972  287 ms  Miss

  4539333865928896  290 ms  Miss

  4532178790252657  306 ms  Miss

  4556511435703208  124 ms  You Sunk My Battleship!

This response time data was the result of an algorithm similar to this pseudocode:

hash := sha256(salt + Credit Card)
dbResults := sql(select * from CC if hash=hash)
if (dbResults > 0): 
return dbResults[0]
else: 
    sql(insert into CC (CreditCard))
return hash

This would explain a new card number resulting in longer response times since it would query the database twice. To the attacker, it doesn’t matter why one conditional branch of the software is longer than the other, only that there is a clear signal in the noise. If the attacker can observe that unseen Primary Account Numbers (PANs) have a deterministically distinct response time than PANs already in the system, then an attacker can send in a batch of records and observe the distinctions in response times. Consider this attack as locating a Boolean true/false buried deep in the response time metadata.

Direct Exfiltration with Timing Attacks

Credit card data exfiltration via timing analysis is actually simple to do. The mechanics look a lot like the malicious insider abuse of correlating truncated credit card numbers discussed in the first post in this series - just brute force the service with 16 digit numbers that pass the Luhn check and set the stopwatch. Some environmental conditions may come into play, such as peak business times or maybe a node in the load balancer pool with degraded or damaged disks (anyone with a background in load testing would be very well adapted to pull off these types of attacks). Automation would look something like the following pseudo-code:

def findPan(truncatedPan, token):
    pans = generatePansFromTruncation(truncatedPan)
    foreach pan in pans:
        resultMS = timeTokenPost(pan)
        if (resultMS < 150):
            return pan
    return

It is important to note that this type of data exfiltration using solely the timing of the responses as the signal of a “legit” versus “not legit” credit card cannot provide the attacker with all of the details he needs to carry out fraud. The attacker still needs the billing address, which a malicious insider, like in the first post in this series, would have.

Using Timing Analysis to Validate Stolen Credit Cards

Another use for this type of attack is to perform QA checks on the most recent batches of breached credit card numbers floating around the darker parts of the web after a major retailer’s breach. So if an attacker steals credit card data from brick-and-mortar retailer A, it may be possible for a sufficient overlap in the customer base at online retailer B to validate the banks haven’t reissued the credit cards a couple months after the initial breach. Retailer B might want to wash their hands of any responsibility, citing retailer A’s initial breach, but retailer B didn’t do its customers any favors by having a timing side channel defect in in their credit card tokenization system.

Preventing Timing Attacks

Preventing timing attacks has a simple goal: make the response times of both code paths (credit card is already stored in the tokenization system versus new credit card) as indistinguishable as possible. This means developers need to unlearn what they learned in their very first programming class (and probably every class since): introduce intentional inefficiencies into the faster code path. Some developers may choose to create an arbitrary load (such as performing arithmetic operations) or introduce a sleep() call for a random amount of time nearly identical to average response time delta. However, a great solution (that DBAs won’t like) is to query the database the same number of times on both code paths, like this:

hash := sha256(salt + Credit Card)
dbResults := sql(select * from CC if hash=hash)
if (dbResults > 0): 
sql(select * from CC if hash=hash) //an extra db call
return dbResults[0]
else: 
    sql(insert into CC (CreditCard))
return hash

Input/Output (I/O) is the slowest link and is dependent upon the environment.  Introducing a hardcoded sleep() call may work for specific times of day, but if the database is slower or faster one day due to peak load or perhaps after an infrastructure upgrade, then the distinguishable side channel timing attack will return.

Stay Tuned

Stay tuned for more attacks against credit card tokenization systems in the rest of this blog series.

Read part 3.