5
$\begingroup$

I came across the definition of Format-Preserving Encryption as firstly defined by the seminar paper Black and Rogaway. Based on their paper the FPE from prefix cipher is defined as follows (quoted from Wikipedia):

One simple way to create an FPE algorithm on ${0,...,N-1}$ is to assign a pseudorandom weight to each integer, then sort by weight. The weights are defined by applying an existing block cipher to each integer.

Can you help me understand the difference to monoalphabetic substitution, and what security is offered by this?

$\endgroup$

migrated from security.stackexchange.com Nov 12 '16 at 21:40

This question came from our site for information security professionals.

  • 4
    $\begingroup$ Shouldn't you ask this on the crypto stackexchange site? $\endgroup$ – Pascal Nov 11 '16 at 23:24
  • 2
    $\begingroup$ Related recent question about the sort-by-random-key construction: crypto.stackexchange.com/questions/41273/… $\endgroup$ – Ilmari Karonen Nov 13 '16 at 14:43
8
$\begingroup$

I cannot understand what is the difference with monoalphabetic substitution and what is the security offered.

A monoalphabetic cipher applies to individual symbols of the plaintext. But an FPE scheme works on the whole message as a unit. In the set {0,...,N-1} that you mention, N is the size of the message space—the number of distinct messages, not the number of distinct symbols; each number represents a distinct message, not a symbol of a message. So for example:

  1. For US Social Security numbers, which are 9 digits, N is one billion, and each number in the set {0,...,N-1} stands for a distinct SSN.
  2. Credit card numbers have 16 digits, but generally the first 6 and last 4 digits must be left in the clear, so the middle 6 are encrypted and N = one million.
    • But the 10 digits left in the clear are used as a "tweak" to the encryption, so that 123456 in the middle six encrypts to different values for different credit card numbers.

The way FPE works is (ignoring the "tweak" concept that I mentioned above):

  1. You define a bijective function between your message space and the set {0,...,N-1}. For SSNs, N = 1,000,000,000, and the bijective function just treats the 9-digit sequence as a decimal numeral with its most significant digits padded with zeroes.
  2. The FPE scheme gives you a bijective encryption function that takes a secret key and a number between {0,...,N-1} and outputs another number between {0,...,N-1}. (It also takes a tweak, but I'm ignoring that for simplicity.)

So to encrypt an SSN you convert the SSN into a number using the function from (1), encrypt that number using the FPE scheme, and convert the encrypted number to an encrypted SSN using the inverse of the function in (1). To decrypt you use the inverses of the functions.


One of the reasons why FPE scheme is defined in terms of sets {0,...,N-1} for user-chosen values of N is for flexibility; as long as you can define a bijection between your message space and such a set, you can use FPE to encrypt those values. For example, if you want to apply FPE to a database date field, you can't just read the date's sequence of digits as a number, because some such sequences of digits aren't valid dates (e.g., 2014-54-35), but the encryption could well output the number 20,145,435. But you can use date arithmetic to represent a date as a count of days since a reference "beginning of time," and then apply FPE using this bijection.


The security offered gets a bit more complex, but at the most basic level it is that the FPE is a pseudorandom permutation on the set {0,...,N-1}. Imagine a solution where instead of using a cipher, you had a big database where, for each plaintext Social Security number, you stored a unique, randomly chosen sequence of nine digits. The encryption operation would go somewhat like this. Given a plaintext P:

  1. Search the database for an entry that has P as its plaintext.
  2. If P is already associated with a ciphertext C, then return C;
  3. Otherwise, set C to some message chosen at random (using a true random number generator).
  4. Search the database for an entry that has C as its ciphertext.
  5. If C is already in the database, go to 3.
  6. Otherwise, store the entry (P, C) in the database, and return C.

FPE's basic security goal, put in simplified terms, is to be no worse than that in practice, from the point of view of an attacker who has doesn't have the encryption key but might have seen a subset of the plaintext/ciphertext pairs.

Note as well that there exist token vault solutions that work like the six-step sketch that I described—a database that associates plaintext with unique random values. So in another sense, the security goal of FPE is offer comparable practical security but at lower cost and better reliability and performance.

$\endgroup$
  • $\begingroup$ Yes. TL;DR: in monoalphabetic substitution, change of one plaintext character propagates only to the matching character of ciphertext, which allow attacks. In FPE, any such change propagates everywhere in the ciphertext, maximizing cryptographic strength. $\endgroup$ – fgrieu May 12 '17 at 17:08
-1
$\begingroup$

Mono alphabetic substitution ciphers are vulnerable to the following.

  1. It can be cracked using statistical analysis.
  2. Ciphertext for same plaintext will remain the same

Format Preserving encryption is not easy to crack using statistical analysis due to the PRN. As it is not a mono alphabetic substitution, similar inputs wouldn't result in similar ciphertext.

$\endgroup$
  • $\begingroup$ FPE also has the property that ciphertext for same plaintext will remain the same. Thus, FPE is also vulnerable to statistical analysis. The difference between monalphabetic substitution and FPE is simple the size of the alphabet. For FPE, the alphabet is the entire domain of plaintexts. $\endgroup$ – Yehuda Lindell Nov 13 '16 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.