Format-preserving encryption

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.

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.

Conclusion

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.