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.
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].
Use of FPE in the financial industry for protecting payment card data faces a number of challenges:
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:
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].
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.
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.
The following references provide background on FPE and its role in PCI compliance.