What is Format Preserving Encryption and is it suitable for PCI DSS?
Posted by David Gamey on 23 Feb 2015.
Format Preserving Encryption or FPE is recent technology that is beginning to show up in payment solutions with the promise of simplifying PCI DSS compliance. If you are unfamiliar with FPE then you may be wondering what it is, if it is suitable for use with PCI, and if there are any caveats that you might need to be aware of. This article will address these questions and provide an introduction to FPE. We will not examine specific solutions in this space..
Broadly, FPE is a method of encrypting data in a way that the cipher text will maintain some of the format characteristics of original plain text. Whether you have a need to encrypt social insurance numbers, addresses, source code, or PCI Primary Account Numbers then FPE could be applied where you have constraints on the format of the cipher text. How similar the output and input formats are will depend on your specific requirements and the particular implementation. The obvious appeal of FPE is the potential to modify only the endpoints of the communication while leaving all intermediate systems and storage layouts unaltered. Coupled with the benefit of encryption and the potential to remove these systems from DSS scope the potential savings in time to compliance and reduced remediation costs are compelling to say the least.
By this point, many of you may be wondering if this is another ‘silver bullet’ solution that is too good to be true. And while there are no real silver bullets in PCI, we will show the answer is encouraging and FPE can facilitate compliance simplification albeit with a few caveats that you’ll need to be prepared for.
How can FPE keep PAN format and still be cryptography?
In the case of FPE, for PCI to get the most benefit the following must be preserved: length of PAN, BIN (first 6 digits), last 4 digits, and the Luhn 10 check digit. This leaves FPE with only the 6 middle digits to work with and of those only 1 out of 10 will work with the check digit. These are very tight parameters. Essentially, FPE uses the entire PAN and replaces the middle digits with a different random set of digits through a strong cryptographic process known as a pseudo-random permutation (PRP). At this point, only the card issuer can tell the difference between the original PAN and the cryptogram.
How can FPE pass PCI requirements for strong open cryptography?
While FPE could use a new cipher algorithm, it turns out that it can use an existing proven cipher like AES in a new way. This approach bypasses the need to prove out the new cipher and focuses on the simpler problem of a new mode. FPE is also not proprietary, it is based on a series of published papers that go back almost 20 years. And at least one implementation of FPE, called FFX, is being considered as an official AES mode by NIST.
At this point an illustration using some made up PAN-like numbers may help demonstrate. Aside from the non-PCI first digits chosen for these fictional PANs, these examples pass all the formatting requirements including Luhn. Different point-of-sale systems would produce different cipher texts.
Plain text “PAN”
FPE cipher text
812345 888888 6780
812345 218292 6780
987654 888888 3212
987654 460167 3212
FPE must overcome all of the normal encryption challenges like algorithms, key management, unique keys per end-point/device, and one more which arises when dealing with very small populations of plain texts. This is the sort of challenge that results in rainbow table and dictionary attacks (e.g. hashing of passwords or PAN) when a cryptosystem is improperly designed or implemented. It is important to know that FPE was specifically designed to address these challenges.
What’s the Catch?
Now that we see FPE is strong non-proprietary cryptography, you may be wondering what the caveats we alluded to are. The main wrinkle is that the PAN and FPE cipher texts cannot be distinguished except by the card issuer. This creates a number of complications for organizations wishing to use FPE in this form.
First, if any of this FPE cipher text is stored or captured by an organization this will complicate the process of out-of-scope validation. Many organizations use card discovery tools to find PAN in order to confirm scope, and ensure they’ve not missed anything. These tools simply can’t tell the plain text from the cipher text and any discovery will require these false alarms be thoroughly and defensibly explained. Short of relaxing some of the formatting requirements, we know of no tools that are provided to assist organizations with this task. While there is no PCI FPE guidance at this time the idea of ‘distinguishability’ is discussed in the PCI tokenization guidance and it should be discussed with any potential FPE vendor.
Second, if any of this FPE cipher text is compromised the organizations’ incident response team will need to be able to address it. Such a compromise will not become known through the normal card brand channels because the card numbers won’t work. However, it is possible that the organization might be faced with an extortion attempt by the criminal or a forced press disclosure that will demand a response. Faced with headlines about a possible card breach and published samples of numbers it may be difficult to convince the public that there was no real compromise.
Finally, there are some areas that are not clear and will likely benefit from some official guidance. FPE is not specifically addressed by PCI although it is mentioned in relation to P2PE. A number of questions come to mind such as how are people to deal with the possibility of a collision with a real PAN, or false alarms in card discovery, or compromises of FPE cipher text? Additional clarifications from the PCI Standards Council and/or the card brands would be welcome. This might even be a good topic for a special interest group.
In addition to these FPE specific issues, the usual PCI concerns relating to things like solution architecture, third party relationships, and division of responsibilities for requirements need to be addressed.
In conclusion, we hope that we have shown that FPE is a viable candidate for encryption under PCI with the potential to simplify compliance and, depending on the solution, to take some intermediate systems out of scope. As with all cryptography, we strongly recommend that organizations don’t develop or implement it themselves. Organizations also need to perform due diligence when selecting an FPE solution to ensure it is based on strong cryptography. We also hope that we have shown some unique caveats that organizations must be prepared to address if they adopt FPE.
Updated on 2015-03-02 to clarify audience and intent, elaborate on the challenges FPE addressed, and to touch on distinguishability.
Updated on 2017-04-27 refer to NIST Announces Format-Preserving Encryption (FPE) Break