Format-preserving encryption

From Wikipedia, the free encyclopedia
  (Redirected from Format-Preserving Encryption)
Jump to: navigation, search

In cryptography, format-preserving encryption (FPE) refers to encrypting in such a way that the output (the ciphertext) is in the same format as the input (the plaintext). The meaning of "format" varies. Typically only finite domains are discussed, for example:

  • To encrypt a 16-digit credit card number so that the ciphertext is another 16-digit number.
  • To encrypt an English word so that the ciphertext is another English word.
  • To encrypt an n-bit number so that the ciphertext is another n-bit number. (That's actually the definition of an n-bit block cipher.)

For such finite domains, and for the purposes of the discussion below, the cipher is equivalent to a permutation of N integers {0, ... , N−1} where N is the size of the domain.

The motivation for FPE[edit]

Restricted field lengths or formats[edit]

One motivation for using FPE comes from the problems associated with integrating encryption into existing applications, with well-defined data models. A typical example would be a credit card number, such as 1234567812345670 (16 bytes long, digits only).

Adding encryption to such applications might be challenging if data models are to be changed, as it usually involves changing field length limits or data types. For example, output from a typical block cipher would turn credit card number into a hexadecimal hexadecimal (e.g.0x96a45cbcf9c2a9425cde9e274948cb67, 34 bytes, hexadecimal digits) or Base64 value (e.g. lqRcvPnCqUJc3p4nSUjLZw==, 24 bytes, alphanumeric and special characters), which will break any existing applications expecting the credit card number to be a 16-digit number.

Apart from simple formatting problems, using AES-128-CBC, this credit card number might get encrypted to the hexadecimal value 0xde015724b081ea7003de4593d792fd8b695b39e095c98f3a220ff43522a2df02. In addition to the problems caused by creating invalid characters and increasing the size of the data, data encrypted using the CBC mode of an encryption algorithm also changes its value when it is decrypted and encrypted again. This happens because the random seed value that is used to initialize the encryption algorithm and is included as part of the encrypted value is different for each encryption operation. Because of this, it is impossible to use data that has been encrypted with the CBC mode as a unique key to identify a row in a database.

FPE attempts to simplify the transition process by preserving the formatting and length of the original data, allowing a drop-in replacement of plaintext values with their cryptograms in legacy applications.

Generating pseudorandom numbers[edit]

Format Preserving Encryption(FPE) is capable of generating unique and inimitable numbers. The main purpose of FPE is to encrypt a file in such a way that both the original and transformed file should be in same format. So if a sequence of numbers starting from 11111 to 88888 is created, then FPE takes the first value which is 11111 and encrypts this into a different five digit number. This process continues until the input reads the last value which is 88888. All the encrypted values are unique and random. These numbers are used as a serial key for a product.

Comparison to truly random permutations[edit]

Although a truly random permutation is the ideal FPE cipher, for large domains it is infeasible to pre-generate and remember a truly random permutation. So the problem of FPE is to generate a pseudorandom permutation from a secret key, in such a way that the computation time for a single value is small (ideally constant, but most importantly smaller than O(N)).

Comparison to block ciphers[edit]

An n-bit block cipher (such as AES) technically is a FPE on the set {0, ..., 2n-1}. If you need an FPE on one of these standard sized sets (where n=128, 192, 256) you may as well use a block cipher of the right size.

However, in typical usage, a block cipher is used in a mode of operation that allows it to encrypt arbitrarily long messages, and with an initialization vector as discussed above. In this mode, a block cipher is not a FPE.

Definition of security for FPE's[edit]

In cryptographic literature (see most of the references below), the measure of a "good" FPE is whether an attacker can distinguish the FPE from a truly random permutation. Various types of attackers are postulated, depending on whether they have access to oracles or known ciphertext/plaintext pairs.

FPE algorithms[edit]

In most of the approaches listed here, a well-understood block cipher (such as AES) is used as a primitive to take the place of an ideal random function. This has the advantage that incorporation of a secret key into the algorithm is easy. Where AES is mentioned in the following discussion, any other good block cipher would work as well.

An example of FPE algorithm is FNR (Flexible Naor and Reingold).[1]

Acceptance of FPE algorithms by standards authorities[edit]

An approach based on one of these techniques has been accepted[2] by NIST for consideration as an approved mode of the AES algorithm under the name "The FFX Mode of Operation for Format-Preserving Encryption" (defined in [3]). FFX is a proposed mode of AES specified in NIST 800-38G. FFX mode is also in standards processes under ANSI X9 as X9.119 and X9.124. VISA has also issued guidance on the use of Format Preserving Encryption in Data Field Encryption Version 1.0 .

References[edit]

  1. ^ Sashank Dara, Scott Fluhrer. "Flexible Naor and Reingold". Cisco Systems Inc. 
  2. ^ NIST Block Cipher Modes Development 
  3. ^ Mihir Bellare, Phillip Rogaway, Terence Spies: The FFX Mode of Operation for Format-Preserving Encryption http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffx/ffx-spec.pdf