05-02-2013, 10:27 AM
Format-preserving encryption
Format-preserving.docx (Size: 24.62 KB / Downloads: 35)
Restricted field lengths or formats
One motivation for using FPE comes from the problems associated with integrating encryption into existing applications. Suppose that you want to encrypt the 16-digit credit card number 1234567812345670. Using other modes of the AES algorithm like ECB or CBC will transform a credit card number into a large, fixed-length, binary value.
Generating pseudorandom unique tokens
Another practical application is the generation of pseudorandom unique tokens in a fixed format. For example, suppose product serial numbers need to be "randomly" generated, but must be unique and exactly 10 digits long. For this purpose, start with a sequence (0, 1, 2, ...) and apply to each sequence value a FPE cipher on the domain {0000000000,...,9999999999}. The encrypted value becomes the product serial number.
Comparison to truly random permutations
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 not O(N)).
Comparison to block ciphers
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
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
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.
The FPE constructions of Black and Rogaway
Implementing FPE with security provably related to that of the underlying block cipher was first undertaken in a paper by cryptographers John Black and Phillip Rogaway,[1] which described three ways to do this. They proved that each of these techniques is as secure as the block cipher that is used to construct it. This means that if the AES algorithm is used to create an FPE algorithm, then the resulting FPE algorithm is as secure as AES because an adversary capable of defeating the FPE algorithm can also defeat the AES algorithm. So if we assume that AES is secure, then the FPE algorithms constructed from it are also secure. In all of the following, we use E to denote the AES encryption operation that is used to construct an FPE algorithm and F to denote the FPE encryption operation.