Blog

# Ancient Format-Preserving Encryption in FIPS 74

Although the Format-Preserving Encryption algorithms that Phil Rogaway invented are very useful for encrypting data in a way that makes integrating encryption with legacy applications and complex IT environments particularly easy, it turns out that he wasn't the first to do this. An old, retired NIST document that describes how to use the DES encryption algorithm actually described a way to do it.

The NIST document that does this is the retired FIPS 74, "Federal Information Processing Standards Publication 1981 Guidelines for Implementing and Using the NBS Data Encryption Standard." This document is so old that it even refers to NIST as the National Bureau of Standards (NBS), a name that hasn't been used since 1988. FIPS 74 was withdrawn in 2005, so this technique should probably be considered obsolete. Here's how it works.

Suppose that we want to encrypt a credit card number that has 16 digits. The FIPS 74 technique encrypts one digit at a time. To do this it creates four bits that are XORed with the four bits that represent a digit. These four bits come from the lowest four bits of the output of a DES encryption. If the result of the XOR operation isn't a valid digit, then the next lowest four bits of the DES output are tried, etc. If all 16 of the four-bit values in the DES output don't give a valid digit, then the binary value 1001 is XORed with the plaintext input to get the ciphertext output. A new output of a DES encryption is used for each digit. Here's a diagram that shows how this works. This can easily be extended to more than digits. FIPS 74 describes techniques for encrypting both alphanumerics and arbitrary alphabets.

This technique seems to be fairly slow. Each digit it will take an average of (10/16)(1) + (6/16)(10/16)(2) + (6/16)2(10/16)(3) + … + (6/16)14(10/16)(15) + (6/16)15(16) = 1.6 DES encryptions to encrypt, so that it will take an average of 25.6 DES encryptions to encrypt a single 16-digit credit card number.

Curiously, it looks like NIST hasn't defined a similar way to do Format-Preserving Encryption with AES. Maybe there's really no need to do that because there exist other techniques that have strong proofs of security. The fact that a Format-Preserving Encryption technique was included in FIPS 74 makes me think that there was an interest in the technology well before the PCI DSS increased the level of interest in encryption. Is the FIPS 74 technique used anywhere these days?