The goal of format-preserving encryption (FPE) is to preserve the format of the plaintext in the ciphertext. This means that if you are encrypting a credit card number, the resulting ciphertext would resemble a credit card number as well. This is useful when dealing with legacy applications whose database schema cannot be updated to support more modern techniques. Sounds great, right? Wrong. In this article I will make the case for why a modern authenticated encryption scheme should always be preferred when possible.
FPE considered harmful
No matter how good an FPE implementation is, it can never fully meet the goals of modern security, by definition. Because format is being preserved, this implies length is preserved as well. And if length is preserved, then there is no room for a nonce or authentication tag. The severe consequences of this limitation are listed below.
Without a nonce, reliable semantic security cannot be achieved1. Encrypting identical plaintexts results in identical ciphertexts, which is a leak of semantic information.
Without an authentication tag, tampering goes by undetected. Imagine an adversary tampering with an FPE-protected credit card number in a database. The application will decrypt the number to some random-looking credit card number and happily chug along with it, without any indication that it was tampered with!
An adversary could potentially swap values between rows in a database, and the consuming application will happily decrypt the mismatched data and use it. For example, consider the swapping of tax IDs between two customers. This is flat-out unacceptable in most applications that I can think of.
I once had someone tell me "there is no business value to an attacker in data protected with FPE". This is blatantly incorrect, and hopefully the above list of disadvantages makes this exceedingly clear. Applications absolutely need to be designed with active adversaries in mind. Designing applications without considering active adversaries is dangerous and ignorant.
The solution should be obvious: use authenticated encryption. It might be tempting to think that we could simply apply an authenticated encryption scheme per-field, but this would carry with it non-negligible space and time overhead. Calculating and storing a nonce and 128-bit authentication tag per tiny field is bad design. In fact, I would even argue that FPE itself carries with it a performance penalty since it operates on tiny, independent fields. Simply put, field-level encryption is bad design, regardless of technique. The correct solution is to encrypt data in bigger chunks (e.g. fixed-size chunks or entire records). If each record is 8 KiB in size for example, then the space and time overhead of the per-record nonce and tag is negligible. Listed below are several important advantages that authenticated encryption provides over FPE.
Because each record has a unique nonce, semantic security is achieved: even if two identical records are saved, the ciphertexts are completely uncorrelated.
If even a single bit gets flipped in a record, the application can trivially detect and reject it thanks to the authentication tag.
Thanks to metadata support, records can be bound to a specific context to protect against swapping attacks.
FPE is appropriate only for legacy applications whose database schema cannot be updated to support a modern authenticated encryption scheme. It can never fully meet the goals of modern security, by definition. It is a last resort. Don't protect at the field level; do protect at the record level.