Must Format Preserving Encryption (FPE) be distinguishable from cardholder data for PCI?

Posted by David Gamey on 17 Apr 2015.

Previously we looked at Format Preserving Encryption (FPE) its characteristics and suitability for application in solutions intended for PCI DSS.  To recap, FPE is an encryption method that produces cryptograms that share many of the formatting characteristics of the plain text and has a wide range of potential applications beyond PCI.  The article showed that FPE can meet PCI requirements for strong encryption.  It also described concerns where (in some implementations of FPE) the encrypted data can so closely resemble cardholder data that it becomes indistinguishable from cardholder data.

The issue of indistinguishable vs. distinguishable data arises due to the specific formatting scheme implemented by the solution. It is perfectly feasible to honor enough formatting constraints (i.e. matching lengths first 6 digits, last 4 digits, and passing the Luhn test) to produce cryptograms that can be reasonably confused with PAN.  In fact such solutions will occasionally produce collisions with real PAN which cannot be prevented.  Distinguishability can be achieved by relaxing any of the formatting constraints or adding additional markers provides suitable mechanisms

This article will focus exclusively on the use of FPE under PCI DSS and will use examples with primary account numbers (PAN) although it can equally be applied to other cardholder and sensitive authentication data.  The following table illustrates some possibilities using a fictional PAN (starting with 8).

PAN (fictional)

Distinguishable

FPE cryptogram

Formatting Preserved / Notes

812345 888888 6780

No

812345 218292 6780

Preserves length, first 6, last 4, and Luhn

Yes

T 812345 743604 6780

Preserves length, first 6, last 4, and Luhn. Adds a prefix marker.

Yes

021104 175178 6780

Preserves length, last 4, and Luhn.

Yes

167193 320527 6780

Preserves length and last 4.

Yes

812345 74793105 6780

Preserves  first 6, last 4, and Luhn.  Increases length.

Yes

812345 385184 6780

Preserves length, first 6, last 4.  Luhn is off by a known amount.

Yes

812345 a2G3kq 6780

Preserves length, first 6, last 4. Alphanumeric middle.

As there is the potential that FPE solutions may require modifications to intermediate systems to accommodate distinguishable formats, FPE solution providers may need to offer a range of alternatives to their customers.

While the PCI web site currently does not explicitly mention FPE, the “Information Supplement: PCI DSS Tokenization Guidelines” (August 2011) and the “Tokenization Product Security Guidelines” (April 2015), provide the best public available on the issues of format preservation and distinguishability. These documents are relevant because they use a very broad definition of tokens that includes cryptographically reversible format preserving tokens (which sounds to us like it’s indistinguishable from FP encryption).

Both of these documents make the point that the users of these systems need to be able to tell the difference between PAN and tokens. The list of reasons includes:

  • Identifying malfunctions of the solution (i.e. failure to transform the data)
  • Ensuring important data is identified so that it can be adequately protected (i.e. scoping errors)

The table below illustrates key recommendations from both these documents.

Item

April 2015

August 2011

Vendor needs to provide a guidance document, e.g. a Tokenization Implementation Guide (TIG) ,to ensure that the solution can be securely implemented.

YES (i.e. a TIG)

YES

Vendor needs to provide a method or tool to facilitate distinguishing PAN from token

YES

YES

Provide guidance on probability and limits to an attacker guessing PAN from a token

YES

-

Examples show that fully format preserving tokens (i.e. length, first 6 digits, last 4, passing Luhn) are possible

YES

-

Addresses Scope Implications of tokens and indicates that tokens may be out-of-scope for PCI DSS

EXCLUDED

YES

Contains examples of PAN and Tokens

YES

YES

Responsibility for correct implementation rests with organization (e.g. merchant) and is part of their DSS (i.e.. either directly or through outsourcing)

-

YES

As these documents are guidance and best practices rather than standards and requirements, the question of distinguishability is likely to foster considerable debate about what is actually needed.  And while distinguishability may not be theoretically required at this point in time, we expect that it will be a practical requirement.  Because organizations using these solutions will need agreement from their assessors  on the scope of their DSS assessments, any organizations that implement tokens or cryptograms that are indistinguishable from PAN may find this data will be in-scope for PCI DSS. The practical reality of this guidance is that organizations wishing to implement format preserving technology will need to perform suitable due diligence on their solution choices and also that solution providers will need to ensure that they can support their customers. Specifically, they will need to address the question of  distinguishable FPE.

Updated on 2017-04-27 refer to NIST Announces Format-Preserving Encryption (FPE) Break