26 August 2010

Cryptography (of PCI data) is Hard

I use to work in card payments and worked with the crypto, even participated in ASC X9F6.  One of the things that I thought about for over 6 years was how to encrypt the card number (personal account number - PAN).  Sixteen decimal digits - 31 bits of entropy max.  There are only a few initial numbers - 4 for Visa, 5 for Mastercard, etc - plus the cards for a given financial institution are all going to start w/ the same Bank ID Number (BIN).   The hard problem comes if you are using the PAN for the primary key in a database.  If not, you can usually find some other data to XOR it with.  But that data must not be predictable.

However, the ogre of PCI DSS compliance has driven everybody to smear a little soothing encryption on their pain.  The result is some crummy, non-X9F6 approved, encryption schemes.  The lid got ripped off that last week in Storefront Backtalk by Evan Schuman.  Everybody in retail and payment cards subscribes to and reads Storefront Backtalk.   So it really ruffled some feathers:


As an aside, we solved the PAN encryption as primary key problem by generating a random salt every time we generated a working storage encryption key.  We would encrypt them both w/ the KEK.  Then we'd XOR the salt with the PAN before encrypting or after decrypting it.  This effectively doubled the key strength.  The working storage encryption key was rotated at least annually.  The only hard part is that you can't take the system offline to rotate the keys, but we handled that by retrying w/ the old key for a record not found condition, assuming that the key rotation window was of short duration.

Meanwhile, the cryptographers have been developing format preserving encryption (FPE), led by Voltage.  If you haven't seen this, here is link to a paper about Voltage's FFX: http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffx/ffx-spec.pdf   This is off the proposed modes page: http://csrc.nist.gov/groups/ST/toolkit/BCM/modes_development.html

The PCI have been very nervous about this use of crypto, but since every Tom, Dick and Harriet in the point-of-sale business has been jumping on it, it is hard to stop.  Heartland Payment Systems has been beating the drum for this every time their CEO, Bob Carr, gets a chance to talk for the last two years.  X9F1, the cryptographer part of ASC X9F, has been glacially thinking about it, as has NIST CRSC, with no yea or nay yet.

Regardless of whether FPE is sound or not, encrypting the whole transaction without XORing it with unpredictable data is madness.  We'll have to see how this plays out.  After the RBS Worldpay breach a couple of years ago, where the crooks got malware on the payment system, sniffed the traffic to the hardware security module and built a dictionary attack against the PINs, it is clear that the bad guys have some decent cryptographers and cryptographic engineers in their midst.


Terence Spies said...


It's definitely true that cryptography is hard, but I think you've mischaracterized the strength of FPE here. As you said, the previous Storefront BackTalk post did ruffle feathers, but it did so because (as the author acknowledged), it contained some incorrect assertions about how encryption works. Walt had some good points, but equating cipher strength to the entropy available in the plaintext is just not correct. Ciphers are designed to handle these cases without losing strength or revealing key bits.

What you describe as XORing a random value with the PAN before encrypting is essentially creating a mode with an IV value that randomizes the encryption process. The XOR process is essentially the same process used by Cipher Block Chaining (CBC) mode, and has the randomizing effect. (Note that it does NOT double the key strength of the cipher, or at least I'm not aware of any proof that shows that these XORed bits contribute in the same way as cipher key bits.)

(As a side note, your computation of the entropy in a PAN is off. 16 decimal digits = 10^16, which is approximately 2^57, so there are about 57 bits of entropy in a PAN. The presence of a Luhn digit cuts this down by somewhat less than 3 bits.)

Regardless, in situations where there is minimal plaintext entropy, it can be important to randomize the encryption process, so that identical ciphertexts do not reveal that the plaintexts are identical. The FPE mode under consideration (FFX) contains a tweak parameter that has exactly that effect. THe algorithm can be supplied with random bits that will randomize the encryption algorithm in exactly the same way as an IV.

Calling FPE "crummy" ignores the work that has gone into this mode. The FFX design leverages research into provably secure cipher design that dates back to the mid-80s, and uses an internal structure that has been scrutinized by the crypto community since the 1970s. The BPS mode proposed by an independent set of French cryptographers comes to the same conclusions, and uses the same internal structure.

While the standardization process has not proceeded as fast one might like, this mode is under active consideration at a number of bodies, including X9F1, the cryptographic tools subcommittee of X9F.

Anonymous said...

Oh, dear, I did not mean to say that FPE is crummy. What I mean is that not all the ways end-to-end encryption is being done are good. My apologies. I actually have read the FPE spec, find it interesting, and have lots of respect for the authors. I look forward to either ASC X9F1 or NIST CRC approving it.

Thanks for pointing out the mistake in my entropy calculation. I did that awhile ago and just pull the number from memory. Shame on me - I should have done the math. :O)