Too Much Encrypt = Cyberthief Gift
Written by Walter ConwayA 403 Labs QSA, PCI Columnist Walt Conway has worked in payments and technology for more than 30 years, 10 of them with Visa.
Encrypt every part of your payment data and you may be giving your least favorite cyberthief a beautifully wrapped gift. That’s the secret dare not spoken aloud in security circles, and it was hinted at—albeit obliquely—by the PCI Council in its latest update.
Although it can be considered cryptographer heresy to suggest that encryption is ever a bad thing, if it’s applied to certain fields, encryption may actually sharply undermine security by making it much easier to break the encryption key. And when that happens, the whole gig is up.
PCI requires retailers and processors to protect the electronic cardholder data they store. The most common approach to that protection: using strong encryption on the primary account number (PAN), along with such data as the cardholder name, the service code and the expiration date.
But there’s sometimes an unintended result: Encrypting all your data may actually make you more vulnerable to a data breach. A sophisticated attacker knows to focus on small fields with a limited number of possible values. That makes an encrypted card expiration date a perfect target for cyberthieves.
The expiration date is a four-character field. Because most payment cards expire within 36 to 48 months, that field has a relatively small number of possibilities. A sophisticated group of bad guys could attack your encryption by focusing on it. And successfully decrypting the expiration date could give that group the keys to unlocking–and compromising–your entire database.
Page 1 of Navigating PCI DSS defines cardholder data as the PAN plus “other data obtained as part of a payment transaction.” That other data includes cardholder name, the service code and the expiration date. All of this data must be protected if it is stored in conjunction with the PAN, per PCI DSS requirements. When you look at this table of proposed changes, note the subtle distinction that states only the PAN, not all cardholder data, has to be protected per Requirement 3.4.
That requirement only obliges you to “render the PAN unreadable anywhere it is stored.” In practice, this requirement usually means encrypting the data. Most retailers and processors encrypt their entire cardholder database, including name, service code and expiration date, in addition to the PAN. It is this process of encrypting all cardholder data that not only causes additional work but may actually make you more vulnerable to a data breach.
My colleagues and I–and I’m sure many other QSAs, too–are aware of this situation. We have started discussing with our clients whether they should focus their encryption on PAN data exclusively. Certainly you need to protect all cardholder data. But you only need to apply Requirement 3.4 to the PAN data.
I was very pleased to see the PCI Council highlight this distinction between the PAN and the rest of cardholder data in the latest summary of changes to PCI DSS 2.0. The very first entry in the table of proposed changes is “Clarify that PCI DSS Requirements 3.3 and 3.4 apply only to PAN.”
I believe the Council is telling retailers and processors to use encryption wisely. The Council is reflecting the fact that the bad guys do not attack encrypted data directly because the strong encryption is too good. Instead, the bad guys attack the encryption keys, which is why there are so many PCI requirements surrounding key management. When you encrypt a small field with a limited number of possible values, like the expiry date, you risk giving a determined (and sophisticated) attacker a potential route to compromising your entire cardholder database.
What should a retail CIO do? My suggestion (and the PCI Council’s, I believe) is that you take a fresh look at your encryption policies and practices. If you are encrypting all of your cardholder data and/or any non-mandatory fields, scrutinize your total data protection and your key management processes to see if it may be better to encrypt only the PAN data.
In fact, it may be a good idea to rethink all of your encryption practices. For example, some retailers may be encrypting only the first 12 digits or just the middle eight, and then storing the rest in clear text. In such cases, the same attack vector I described here would apply; your encryption practices reduce the total number of possible outcomes and unintentionally provide an attack surface for the bad guys.
What do you think? Do you encrypt all your cardholder data? Leave a comment or send me an E-mail at wconway@403labs.com.
-Marc
August 19th, 2010 at 7:48 am
If the argument is that bigger data fields having more possible permutations are harder to decrypt, it seems logical to merge the 4 key fields (PAN, Name, Svc Code + Expiration Date) into one large field and encrypt it as one field. This avoids leaving the weak calf (expiration date) isolated for the wolves to attack.
August 19th, 2010 at 1:32 pm
Great article. This was something we found during our R&D cycle when determining the best was to encrypt CHD in our database. Another factor that played into our decision was the encryption algorithm itself — different algorithms work better (and some worse) on small data sets. We found that 3DES, the dominant payment industry encryption algorithm, works very poorly for small data fields due to repeatable patterns in the limited data set (I know there is a better term to describe this, I just cannot think of it at this time). What I mean by this is that if you encrypt a series of sequential PANS with a key, the resulting encrypted data will be very similar (hypothetical example, 3DES is stronger than this simplistic example):
Clear PAN –> Encrypted PAN
4000000000000000 –> Rg4ielrEEtj4Typ1
4000000000000001 –> Rg4ielrEEtj4Typa
4000000000000002 –> Rg4ielrEEtj4TypX
4000000000000003 –> Rg4ielrEEtj4Typ8
4000000000000004 –> Rg4ielrEEtj4Typj
4000000000000005 –> Rg4ielrEEtj4TypI
Note, that only the last character is different in the clear AND in the encrypted result. This gives a hacker an attack vector. Do to this, we chose Blowfish for this layer of encryption. Our sample looked something like this (again, simplified):
Clear PAN –> Encrypted PAN
4000000000000000 –> RDrk39fgBr9eRPde
4000000000000001 –> 94Kffe3EdkE85Tfd
4000000000000002 –> 84481gr84Vl0dppQ
4000000000000003 –> cd0d83mmr2yrWeeR
4000000000000004 –> MBtr94kf3DF3452e
4000000000000005 –> 0Ee65lKMN341ldZe
Now there are way around this to compensate for this weakness, but it is something that needs to be considered. On a side note, we also tested AES and in this specific test, the results were similar to 3DES.
Another factor to worry about, especially when dealing with PANs, is to look at exactly what is encrypted and what is not. In our example, for reporting purposes, we store truncated PAN information unencrypted. When we did this we realized that if we encrypted the entire PAN, the unencrypted information would open another attack vector so we opted to only encrypt the non-truncated PAN data.
August 19th, 2010 at 2:19 pm
There is absolutely no value in encrypting these small fields of data in the first place. Implement RBAC and auditing and call it a day.
The reality is that there are so few values for an expiration date that if you give someone a one-way hash they can derive the value in seconds so there is no value in hashing it really either.
There doesn’t appear to be a “safe” way to protect this data with hashing or encryption if the same logic and key is also applied to the PAN. Perhaps taking the 4 fields mentioned above by Rob and encrypting with a different key than the PAN is an approach.
Some may argue there is a way to prepend it at the front of the PAN then do some bit shifting on it before it is encrypted.
Reality is there aren’t many ways to take a small bit a data with few reasonable values and block probable clear text analysis from drastically reducing the possible key space.
128 bits of common sense is stronger in this case.
Also consider the use of use of encryption stronger than 128 bits on data that is only 128 bits long. This also reduces security drastically for a similar reason.
Organizations would be well served to hire a encryption specialist when deciding where and how to use encryption. Knowing where and how to do the application of technology is in many cases as important than the technology selected.
Compare and contrass this situation to the vulnerabilities found in WEP for a moment. These number remind me of IV’s in the problem they have, but are worse yet because there are fewer valid numbers.
Failure to look at history and learn from the lessons taught by failures like the WEP protocol can allow history to repeat itself.
On a related note, how many organizations must now simply hope there aren’t many cybertheives with wiress packet traces from 10 years ago sitting around on a hard drive……
August 19th, 2010 at 6:01 pm
I was thinking similarly to Rob, however, implementing that may not be feasible for everyone. Interesting topic – thanks Walt!
August 20th, 2010 at 12:34 am
Walt,
First, before you get discouraged, I want to let you know I consider it a good thing that people like you are thinking about attacks. A good, novel attack could be a game changer. But while your approach could produce some minor information leakage of expiration dates in a poorly designed implementation, it will not leak information about the key material.
What you are describing is called a known plaintext attack, and all widely used modern cryptographic algorithms are studied to determine how well they preserve the secrecy of the key material in case of this kind of attack.* There are actually three levels of attacks that algorithms must be secured against: unknown plaintext (attacker doesn’t know what was encrypted but has the ciphertext), known plaintext (attacker knows exactly what was encrypted and has the ciphertext), and chosen plaintext (attacker gets to choose what is encrypted, encrypt whatever he wants as many times as he wants, and examine the ciphertext output.)
Where your attack can give up a bit of information is that if I know my expiration date is January 2012 and it encrypts to 1111aaaa2222bbbb, I know that every entry of 1111aaaa2222bbbb in the table will also be an encrypted expiration date of January 2012. For that matter, the same issue exists with PANs – if I use my card twice in the same location and it is encrypted the same way both times, an attacker could use the information for traffic analysis. Put another way, this is exactly the operation of “multi-use tokens”, and retailers use this information for traffic analysis.
Your attack is closely related to some of the attacks the Allies used decrypting the German Enigma system, where they used it against the communication and password exchange protocols of the German cipher operators.
But the threat is now well understood, and cryptographic algorithms provide a standard way to protect against it. That is done by using an Initialization Vector (IV) and choosing a secure operational mode (not ECB) for the cipher. An IV is a block of random data the same size as the encryption block size, and it becomes your first encrypted block. In any of the chaining modes of operation, this first block of random data is mixed in with the data before the next block is encrypted in order to produce the second block, which is your real data encrypted, but is now randomized. When you decrypt, you simply skip the first block you decrypt, as it’s the random IV value you started with, and begin with the next block. Every new encryption must use a new random IV, as repeated use of the IV defeats the purpose.
Using an IV isn’t overly important for protecting the not-very-valuable expiration date, but it would be critical if you were to encrypt something with high value, such as a PIN. Otherwise, you could seed the data with specific PINs, then harvest all the data looking for matches to your known encrypted PINs.
* The best public cryptanalysis of 3DES leveraging known plaintext requires knowing 2^32 plaintexts and takes 2^113 operations. And there simply aren’t 2^32 possible values for expiration dates: in a hundred years, there are less than 2^11. See Stefan Lucks research paper Attacking Triple Encryption, available at http://th.informatik.uni-mannheim.de/People/Lucks/papers/pdf/3des.pdf.gz
You can continue to sleep soundly, at least for tonight.
August 20th, 2010 at 8:28 am
@Steve Sommers In your example, isn’t the problem that you’re treating the PAN as a string, then encrypting the string without using a block chaining mode (i.e. you’re encrypting each block of data independently) without an initialization vector?
August 20th, 2010 at 2:55 pm
Agree with A Reader (“First, before you get discouraged, I want to let you know….”) and he got to it before me. I’d be less concerned about the size of the input, and more concerned about the IV and the consideration of a brute force attack (or other types of cryptanalysis).
August 20th, 2010 at 3:12 pm
This article is just plain wrong, but it also may give us some insight into what the industry really needs.
“A reader” got this exactly right: in crypto terminology, just because you can do a chosen-plaintext attack does not mean that you can do a key recovery attack. So even if you can build a table of valid plain-cipher pairs for expiration dates, for example, that does not mean that you can use that information to recover the key used to calculate those ciphertexts. This means that the fundamental premise of the article is totally wrong. But that’s not surprising, because encryption is a tricky subject that’s often inaccessible to non-specialists.
There are several definitions for security for encryption, for example. The most common of these is IND-CPA security, which essentially means that you can’t create a table of matched plain-cipher pairs and use that table to do a dictionary attack against ciphertext.
Unfortunately, the precise definition of IND-CPA security is fairly incomprehensible to non-specialists, so you can’t really expect them to spend the time and effort to understand it. If you’re not a crypto specialist, look at the Wikipedia article on IND-CPA security and see if its definition makes sense to you:
http://crypto.cs.uiuc.edu/wiki/index.php/IND-CPA_security
There’s another notion of the security of encryption that’s called “perfect secrecy,” and that’s really the security model that tokenization systems try to attain. Unfortunately, this definition is also fairly incomprehensible to non-specialists, so even though tokenization systems violate the assumptions of the security model that they’re trying to meet, that’s not clear to most people.
So if the subtleties of encryption aren’t clear to a QSA, what it’s probably telling us is that there’s a need for some sort of industry forum in which QSAs and others can ask experts about these things in a way that won’t make them feel foolish.
I’ve found that having a few beers with the sales people selling crypto products is a fairly effective way to do give them a chance to ask questions about exactly how their technology works and why it’s secure, but that approach probably doesn’t scale very well. Maybe that industry forum would be a better approach.
August 20th, 2010 at 10:14 pm
I think it would be interesting to discuss where these errors and misconceptions propagated from and how to prevent this from happening in the first place.
* is the training enough ?
* is misinformation compromising hard truths and established facts by taking advantage of lack of domain knowledge ?
* are the qualifications sufficient for task ?
* is there a mechanism in place to permit questions like those raised in the article to be addressed quickly and accurately on a continuous education basis?
Learning about the subtle nature of many PCI requirements, combined with having to know deeply about complex and varied merchant and payment system environments and the need to have strong security knowledge is a significant and daunting task for many.
On the other hand, correctness is critically important for obvious reasons: Of course there’ security and risk, but if QSA’s are drawing incorrect conclusions they may not only risk their credibility and confuse a merchant about security, but could inadvertently lead a merchant to making significant investment decisions which they shouldn’t have to fund at all.
How do we address this ? Training may not be enough. The erroneous scenario described this article is not unlike many of the misleading or incorrect posts in the various Q&A forums out there blended in amongst legitimate ones. Many in training classes may not want to ask “silly” question in a peer group setting due to simple fear of embarrassment – even if sadly getting the answer is critical to the ability to perform proper assessment duties.
Time perhaps for a new approach to training ? Time for an approach to permit questions, doubts or concerns that may arise like this to be dealt with promptly and authoritatively by industry and standards bodies to the benefit of the whole PCI community?
August 22nd, 2010 at 1:30 am
Mark,
Those are great observations. And I think they reinforce my point why I maintain that current PCI regulations are fated to never be successful at safeguarding cardholder data, at least not while sensitive data exists unencrypted in the merchants’ systems.
You know (probably better than anyone posting here) how much study and work it takes to become a competent cryptographer. I think we can agree that there aren’t enough of them to study every retailer’s security architecture to the degree required to insure that data is protected at a theoretically secure level every step of the way.
And if we can’t adequately protect every system, the bad guys will continue to prey on the weak ones. The internet makes it easy to attack thousands of sites at once. With about seven million card accepting merchants out there, the poorly protected are plentiful.
The only way to “scale up” the relatively few competent cryptographers that exist to meet such a demand is to have them provide a secure design that everyone will share. An open, publicly reviewed design, one that incorporates the lessons learned from 30 years of fraud and failed attempts. We need a design that will be attacked mercilessly prior to deployment. A secret cabal gave us CAP, and the system has proven vulnerable to fraud. It’s now time for a public design, one that scales, one that’s properly versioned and upgradeable, yet not so flexible that it can be twisted into unforeseen combinations.
So this circles back to the argument I’ve been making for years. Cryptography has to occur only at the endpoints of the transactions, and that cryptography must be designed and standardized at a top level.
The transactions must be protected before entering the merchants’ systems. Cryptography has to occur on customer owned equipment (key fobs, smart cards, whatever) issued by the banks. The merchants can’t be trusted to provide any aspect of the secure equipment (secure PIN pads can be faked, etc.) And the customers can’t be trusted to maintain their own equipment, so banking activities must be air-gap isolated from other consumer systems, such as smart phones.
This removes the handling of raw, unsecured data from all the untrustworthy, gullible middlemen. The retailer requests payment, and the customer authorizes the payment transaction on their handheld device that was issued to them by their bank. The authorization is given to the retailer (via RF, contacts, whatever), who passes it to the bank for approval. The authorization is tied to the cardholder and merchant, and is good for a single transaction. Disrupting the authorization would prevent the merchant from getting paid, so the merchants would still have incentive to secure their systems, but since the risk of copying or stealing the authorization is zero, as it can only be used to pay the merchant one time, the cardholder is always kept safe.
Retailers are good at marketing, but are not specialists at security. Banks are good at security, but not at talking. The associations are good at protocols, and getting the parties talking. We have all the right players, we just need the will to change the status quo.
August 23rd, 2010 at 1:09 pm
Unfortunately, I rarely encounter QSAs that have the fundamental training to understand good cryptographic implementations. The article is a great demonstration of the misinformation circulating in the QSA community.
I agree with many of the posters above – Luther, Mark, Branden, and the anonymous A reader.
Walt, I feel bad saying this, but writing this article which is just fundamentally wrong and passing it off as insightful and authoritative does the security community a disservice. I’m sure your intentions were good-natured.
The reality is that encrypting data with a decent implementation in the payment space almost immediately eliminates the feasibility of a cryptographic attack against the plaintext data and the encryption keys. It becomes many times (many many many times) simpler to generate every single card value, including every single service code, card code, expiration value, etc and use those generated values to perpetrate some sort of validation attack. Validation attacks work great. And because the card issuers do things like not checking certain data elements when presented for authorization, it becomes easy for attackers to use that data.
My perspective, after being involved in some of the committees working on changes, on the clarifications around 3.3 and 3.4 is that encrypting expiration and other easily guessable data elements has little value.
August 23rd, 2010 at 2:41 pm
Some folks are beating up Walt on this, but I want to come to his defense here.
Firstly, the poster comments here about resistance to known plaintext attacks are, of course, correct. However, the sense I keep getting is that “these attacks aren’t realistic against modern cryptosystems.” They are not effective against modern cryptosystems *when those systems are implemented correctly*.
The problem is, as has been pointed out here, is a lot of people don’t know enough about *how* to implement the cryptosystem. They know they want to use something like AES. However, they have no sense of key management, selection of IVs, etc.
Look at WEP. Weak IVs were in part responsible for its downfall (I don’t want to get into a religious war as to the core of the issue, let’s just leave it as “IVs are part of the problem”). I’ve seen people use constant IVs, which totally defeats the purpose.
If you are doing silly things in your crypto setup, managing keys poorly, and doing other things to reduce potential keyspace and/or leak information, you should stop doing them when feasible to do so.
I don’t think Walt is doing a disservice. If anything, maybe he got a few people to take a look at what they are doing, and change how they look at things, as well as boning up on crypto.
August 23rd, 2010 at 4:59 pm
@Dave
I agree with your points on implementation. I think the big problem here is that the article doesn’t make a case for evaluating implementations…the article makes a case for not encrypting data in the first place. And the information about attacks is misleading and inaccurate. The article assumes that all implementations are susceptible to known, unknown, and chosen plaintext attacks, and that those attacks lead the attackers to the keys. This is simply not the case.
As the anonymous ‘A reader’ points out there aren’t even enough plaintexts available to lead an attacker to be able to choose the right key if the target is the expiration field.
Think about the scenario…
There are how many possible legitimate values for YYMM? That’s not too hard to calculate, but does get a little tricky thinking about YY. MM is easy. There are 12 possibilities for MM. There are 100 possibilities for YY (00-99). But in reality, this is a much smaller number because values above 49 are rarely seen on issued cards (there are exceptions). But let’s just take the maximum…
That leaves us with 12*100 or 1200 possible YYMM combinations. Encrypting such a small space seems pointless unless you want to guarantee the extra effort it will take for an attacker to just guess those values. 1200 known plaintexts is nowhere near the number of plaintexts needed to attack a key.
The article makes some good general statements like “it may be a good idea to rethink all of your encryption practices” or “I believe the Council is telling retailers and processors to use encryption wisely.” But the article also makes statements that are inaccurate like “And successfully decrypting the expiration date could give that group the keys to unlocking–and compromising–your entire database” and “if it’s applied to certain fields, encryption may actually sharply undermine security by making it much easier to break the encryption key.”
Sorry that it seems like the posts are beating up on Walt. I’m certainly not trying to bash, but the article contains inaccurate information and it seems to me to be based entirely on these inaccuracies. Not calling that out is only going to further this misunderstanding of cryptosystems and attacks. I’m sure Walt meant well and perceived (hopefully he sees that his premise isn’t accurate given the information in the comments) a threat that he felt needed to be addressed. I’m all for raising awareness in the community.
August 24th, 2010 at 11:47 am
I have to agree with the majority of the commenters here that the original premise of the article just doesn’t hold. For any modern cipher, having an arbitrary number of plain text/cipher text pairs gives an attacker no path to recovering the key. Your symmetric cipher’s resistance against a Chosen Plaintext Attack is the last thing you need to worry about when designing and operating a secure system.
No doubt that it’s good to have people re-examine their security policies, but I think there is a case to be made that worrying about CPAs against your symmetric cipher is a red herring.
August 24th, 2010 at 5:31 pm
@P, My example was very basic and did not include a CBC or an init vector BUT there are times when these cannot always be used. If the application needs to lookup the data by the PAN (or whatever the encrypted data is), this would not be possible using CBC & and init vector.
The next argument would be to store a hash for lookup purposes. But having a hash of the PAN sitting along side the encrypted PAN opens another potential attack vector similar to the expiration date discussion we are having here — even bigger since the hash has much more resolution than the expiration date.
August 25th, 2010 at 1:34 pm
@Steve Sommers
I think that your testing might have misled your conclusions about what cipher to choose. Changes, regardless of how much changed down to single bits, in the plaintext will result in a new random ciphertext for AES, DES, TDES, 2TDES, or Blowfish for that matter. That’s one of the criteria for a “good” algorithm. ECB, while susceptible to dictionary attacks, still produces random values. Two plaintexts, even related, will result in two random ciphertexts. In the example in the article, even using ECB would not reveal key material when encrypting short lengths. You would be able to build a dictionary if you had an encryption oracle, or were able to capture ciphertexts, but that still wouldn’t lead you to the key.
I would be interested in reading about the attack you describe in your last post “But having a hash of the PAN sitting along side the encrypted PAN opens another potential attack vector.” Can you post a link to an abstract or article that describes this attack? I am not aware of any attacks that reveal information about plaintext data or key material by analyzing hashed values in conjunction with ciphertexts using the same plaintexts as sources.
August 25th, 2010 at 5:21 pm
@Marc,
What Mr. Sommers may have encountered in his 3DES experiments could easily be explained if he encrypted account numbers using ECB mode. 3DES is a 64-bit block cipher, meaning it encrypts data in groups of 8 bytes. Two Visa account numbers starting with the same eight digits, such as 4123456700000017 and 41234567000000029, would yield identical 64-bit first blocks of ciphertext, although the second and third blocks would be different.
If his experiment included sequential debit card numbers that ranged into the 18 or 19 digit PAN length, the results would be even more striking. If the first 16 digits matched the first two blocks would be identical, differing only by the third block.
Finally, he misinterpreted patterns in the results as a weakness in the cipher, instead of in that particular implementation. They should have been seen as a warning or cross-check that something else is wrong, as 3DES is successfully used to protect all manner of secure data millions of times every day. If an industry-accepted secure algorithm is not yielding secure results, it’s not because it suddenly became a weak cipher.
August 27th, 2010 at 9:17 am
I enjoyed this article and the discussion very much. Thanks to everyone.
August 27th, 2010 at 10:25 am
I hadn’t read all the additional articles before offering my kudos. Now I am even more thankful for all the discussions.
There are a lot of thoughts that have come out of reading this discussion, but for the sake of time I will summarize as follows ….
• There is probably nothing more terrifying to a retail manager than the thought of all his customers’ data ending up for sale on the Internet. It is probably what keeps most CIO’s up at night, even more than the thought of a system crash on Christmas Eve.
• No online data is ever completely “safe”. The only way to prevent unauthorized use is to never put it online. If it is online, it will be put into clear text at some point and at that time it is totally vulnerable regardless of how much you have done to protect it. (Can you say “screen print”.)
• Encryption should be left to the experts. This does not mean retail managers should not have a high level understanding, but they must rely on certification and vulnerability tests to validate their implementations. It also means there is an opportunity for implementation modules with clear API’s that give casual users the means for implementing secure environments.
• Because of the nature of the subject, writing about it can be challenging. There will always be people trying to develop new techniques. Unlike the encryptor, who must put their work into “stone”, the decrytpor is constantly trying new methods to break in.
Gotta go now ….