NIST Update to Format Preserving Encryption Standard affects PCI Use Cases

Last month NIST announced they were seeking feedback on a proposed updated guidance for FPE. More formally this is SP 800-38G rev 1 "Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption". The draft is open for comment until April 15th 2019. The draft as written may cause problems for organizations using FPE to encrypt payment cards. If you provide or use an FPE solution for protecting payment card data you should review this and provide feedback.

I would like to thank researchers Hoang and Vaudenay for providing clarifications and insight into their valuable work. However, the opinions are our own.

FPE's Problem in the Payment Card Space

If you aren't familiar with FPE, please take a moment to read our quick history of FPE below.

Researchers have identified vulnerabilities in all NIST approved FPE modes where the domain size is small. In English, this means that you can't use FPE safely to encrypt small data elements. Additionally, other findings have led to changes in the underlying algorithm for FF3 (now called FF3-1) [5]. The domain size for both FF1 and FF3 in SP 800-38G was required to be at least one hundred and recommended to be at least one million" [5]. In this update "the recommendation was strengthened to a requirement: the minimum domain size for FF1 and FF3-1 in Draft SP 800-38G Revision 1 is one million". [5].

FPE/Payment Card Challenges

Use of FPE in the financial industry for protecting payment card data faces a number of challenges:

• The domain may be too small if PAN is constrained by first 6, last 4, and Luhn. This is because the Luhn check invalidates 90% of middle six digits of a 16 digit number.
• The new recommendations, mean that if FPE should not be used on smaller values such as payment card security codes (CVN, CAV2, CVC2, CID, or CVV2 ) or PIN.
• Research suggests that FPE seems weaker than NIST's intended 128 bits of security.
• Solutions in the field have long life spans.
• Merchants and solution providers would prefer not to have to replace existing solutions they consider relatively new.
• The rapid progress of researchers in improving attacks calls into question the robustness of the solution.
• Organizations may need to start thinking about the risk in specific use-cases.

Questions for NIST and the PCI SSC

We know that some FPE solutions preserve all aspects of payment card formatting and don't meet the minimum domain strength of one million in the drafted update. What we don't know:

1. Can NIST safely reduce the minimum domain size to accommodate this use case?
2. Will PCI continue to support solutions that do not align to NIST?
3. And if so, how and for how long?

Is FPE Broken or Bent?

It's difficult enough for the average person to understand encryption, let alone to understand the implications of any "breaks" cryptographers find. Often research takes years to reach the point where things are unsafe and falling apart. Long before that things become bent and practical fixes, work-arounds, and limited use cases can be used to buy time.

A case in point, the serious weaknesses in SSLv3 using Cipher-Block-Chaining modes of encryption took more than a decade to fall apart. Eventually researchers were able to demonstrate practical exploitation with attacks like BEAST and POODLE. Afterward, migration away from SSL was largely accomplished in a few years. A few very limited use-cases are still practically safe [3]. They are being deprecated but get more time to migrate. For some time now, nobody should be doing anything new with SSL/CBC.

FPE isn't yet broken in a practical sense but it's definitely bent. The state of the art has advanced very quickly. The research today casts doubt on the long term viability of FPE in general use cases even if some use cases remain safe. NIST isn't going to fix FPE if it's totally broken. However, the fix they choose may err on the side of being safe.

As an analogy, when cryptographic breaks happen there usually isn't an imminent fire. Don't panic but don't ignore it either. Take a look around, assess the situation, and start planning for an alternative or possible exit. Make no mistake that a fire still may be coming. Just understand that it may be a decade away.

Many of the of the recommendations we made after the 2017 announcement in the weakness of FF3 still apply [2].

The Problem of Distinguishability

FPE and other format preserving technologies like FP-tokens, and FP-random-masking, that preserves the first 6, last 4 and Luhn runs into a slightly messy practical problem that has nothing to do with the strength of the cipher [4].

We believe that solution providers should clearly indicate what FP technologies their solutions use. This is not because we believe FPE is bad. But instead because this will help minimize the chance of their customers being caught scrambling if this FP data is discovered or exposed.

A Quick History of FPE

Format Preserving Encryption (FPE) is an interesting a relatively recent technology with a wide range of applications. FPE has been widely adopted to encrypt payment card numbers.

FPE can encrypt a valid payment card number to similar but different number matching attributes like the same first 6 and last 4 digits with a valid check digit (Luhn) and reverse the process.

If you're skeptical that it sounds like snake-oil, it isn't [1]. Research backing FPE goes back over 20 years. NIST began to consider FPE around 2010-2011 when private industry began making proposals. NIST approved a standard by 2016. But they hedged their bets throughout the process by considering three similar variations of FPE known as FF1, FF2, and FF3. FF2 did not survive to approval.

FPE has been subject to intense scrutiny by researchers. By 2017 FF3 was in trouble and NIST effectively put that mode on hold [7] until it could be fixed [5], [6].

Researchers have made some impressive advances in attacks against NIST's FPE and some alternative FP ciphers [8], [9], [10]. In particular the very recent paper on attacking FF3 on large domains [8] has hopefully been addressed in FF3-1.

Learn More

The following references provide background on FPE and its role in PCI compliance.

Articles

1. What is Format Preserving Encryption and is it suitable for PCI DSS? https://controlgap.com/blog/format-preserving-encryption/
2. Seven Things You Can Do To Deal With The Recent Format Preserving Encryption (FPE) Compromise https://controlgap.com/blog/7-things-to-do-with-fpe-break/
3. The Extension of the Sunset of SSL. Safe and unsafe use cases https://controlgap.com/blog/sunset-ssl-extended/
4. Must Format Preserving Encryption (FPE) be distinguishable from cardholder data for PCI? https://controlgap.com/blog/format-preserving-encryption-and-cardholder-data/

NIST

5. Request for comment (2019) https://csrc.nist.gov/news/2019/nist-requests-comments-on-draft-sp-800-38g-rev-1
6. Revision 1 draft to FPE standard (2019) https://csrc.nist.gov/publications/detail/sp/800-38g/rev-1/draft
7. Recent Cryptanalysis of (FPE mode) FF3 (April 2017) https://csrc.nist.gov/News/2017/Recent-Cryptanalysis-of-FF3

Research

8. Attacks Only Get Better:How to Break FF3 on Large Domains. Hoang, Miller, Trieu (2019) https://eprint.iacr.org/2019/244
9. The Curse of Small Domains: New Attacks on Format-Preserving Encryption. Hoang, Tessaro, Trieu (2018) https://eprint.iacr.org/2018/556
10. Breaking the FF3 Format-Preserving Encryption Standard Over Small Domains. Durak, Vaudenay (2017) https://eprint.iacr.org/2017/521