Skip to content

Instantly share code, notes, and snippets.

@mimoo

mimoo/fpe.md

Last active June 15, 2021 12:57
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mimoo/fa84d554680ab7a72ba23b5c2934e5cd to your computer and use it in GitHub Desktop.
Save mimoo/fa84d554680ab7a72ba23b5c2934e5cd to your computer and use it in GitHub Desktop.
Download ZIP
History of Format-Preserving Encryption
Raw
fpe.md

Introduction

Format Preserving Encryption (FPE) seems to have been invented principally to encrypt credit card numbers into something that looks like a credit card number. Effectively, FPE is a permutation over the domain of the input.

It seems like the main reason is legacy: a lot of databases where created with size and alphabet restrictions on the field of credit card numbers, other systems and applications were probably built to deal with similar restrictions in order to process or transport these credit card numbers. Since it was deemed (I'm guessing) too costly to improve things so that a ciphertext, an IV and an authentication tag could have been stored in there instead; instead rich banks threw money at the problem and cryptographers took the bait.

It seems like there are three ways to do it:

  • Prefix. Your input domain is very small: write the permutation yourself (01 => 10, 00 => 11, etc.). If you don't have imagination, use AES to encrypt your input domain, and truncate. Hopefully it creates a permutation.
  • Cycle walking. Your input domain is almost as large as the blocksize of AES: encrypt until you have leading zeros. Same with decryption.
  • Feistel Network. Your input domain is in between: you're fucked. Just kidding, you use a Feistel network.

Constructions:

  • 1981 - FIPS PUB 74: Guidelines for Implementing and Using the NBS Data Encryption Standard

a DES-based encryption method which keeps the format of plaintext and ciphertext the same was proposed, however, this standard was withdrawn, and accordingly, the technique should be considered archaic (source)

Ciphertext (data in encrypted form) bears roughly the same resemblance to plaintext (data in its original form) as a hamburger does to a T-bone steak. A social security number, encrypted using the DES encryption algorithm, not only does not resemble a social security number but will likely not contain any numbers at all. A database field which was defined to hold a nine-character social security number (eleven, if you want to include the hyphens) would not be able to store the DES-encrypted version of the data. A Visual Basic program would not read it. A graphical interface would not display it. There would be nothing that you could do with the encrypted social security number unless you had made extensive provisions for changes in data format throughout your application and physical database design

The authors provided a proposed solution, but no argument for the security of this method is given (source)

Consider the following problem: a company wishes to generate distinct and unpredictable ten-digit credit-card numbers. One way to accomplish this involves keeping a history of all previously-issued numbers. But the company wishes to avoid storing a large amount of sensitive information.

The prefix method constructs a random permutation in memory and uses it to encrypt data, but is only suitable for small domain (source)

The cycle-walking method can take effect on a limited class of sets, it encrypts plaintext with an existing block cipher repeatedly until cipher output falls in acceptable range, nonetheless, when the size of set is much smaller than 22m where 2m is the block cipher size, performance of cycle-walking will be much low. (source)

In 2008, Terence Spies first introduced the conception of format-preserving encryption and associated FPE with personally identifiable information (PII) protection: FPE can be used to encrypt sensitive data to upgrade database security in a way transparent to many applications. (source)

Encrypting Personally Identifiable Information (PII) in large databases has historically been difficult, because encrypting information typically implies expanding data and changing its format. Previous attempts to encrypt PII data like credit card numbers and Social Security Numbers without changing their format have used questionable cryptographic constructions.

the cost of modifying databases and applications to accommodate encrypted information

First, privacy-critical information like credit card numbers or Social Security Numbers are often used as keys or indices in databases, so randomization of these fields by encrypting data may require significant schema changes.

Second, applications may be written expecting data in a specific format; encryption will typically expand data and require a format change.

Spies has gone on to submit to NIST a proposed mechanism, FFSEM, which is the improved mode of generalized-feistel cipher (source)

Spies has gone on to submit to NIST a proposed mechanism, FFSEM, that combines cycle walking and an AES-based balanced Feistel network. (source)

The term format-preserving encryption is due to Terence Spies, Voltage Security’s CTO

FPE can enable a simpler migration path when encryption is added to legacy systems and databases, as required, for example, by the payment-card industry’s data security standard (PCI DSS). Use of FPE enables upgrading database security in a way transparent to many applications, and minimally invasive to others.

In the end of 2009, Bellare went on to put forward another improved FPE mode, FFX [8], it is an extension to FFSEM, adding in support for tweak, non-binary alphabet, and non-balanced split. In FFX, cycle-walking can be avoided in the setting of primary practical importance, encrypting decimal strings. (source)

In many applications, such as encryption of DateTime field in database, it is desirable to encrypt items from an arbitrarily sized set with the specified format described as “YYYY-MM-DD HH:MM:SS” onto that same set.

As the publication of PCI Data Security Standard (PCI DSS), consumers’ awareness of privacy issues has motivated many businesses to investigate methods to encrypt personally identifiable information, and FPE is the suitable solution. Up to now, some FPE modes have been proposed, such as FFSEM, FFX, RtE, etc. However, these modes are general approaches for complex domain but not for specific practical application in detail, and there are some important problems remaining unsolved, such as enciphering on arbitrary domains, efficiency and integrity authentication, etc.

Sensitive data like credit card number is often used as key in database, randomization of these fields may require significance schema changes. In addition that database system always allocates a fixed size space for each data type and requires that ciphertext must keep the same format as plaintext. Thus, the traditional block cipher cannot be applied here.

This Recommendation specifies two methods, called FF1 and FF3, for format-preserving encryption. Both of these methods are modes of operation for an underlying, approved symmetric-key block cipher algorithm.

Attacks:

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment