5
$\begingroup$

I came across the definition of format-preserving encryption (FPE) as first defined in a seminal paper by Black and Rogaway. Based on their paper, FPE (or 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 between this and monoalphabetic substitution, and what security is offered by FPE?

$\endgroup$
3
  • 4
    $\begingroup$ Shouldn't you ask this on the crypto stackexchange site? $\endgroup$
    – Pascal
    Nov 11, 2016 at 23:24
  • 2
    $\begingroup$ Related recent question about the sort-by-random-key construction: crypto.stackexchange.com/questions/41273/… $\endgroup$ Nov 13, 2016 at 14:43
  • $\begingroup$ @Hashed The paper you cited answers your latter question of "...and what security is offered by FPE?" $\endgroup$
    – Patriot
    Aug 16, 2019 at 11:12

2 Answers 2

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$
1
  • $\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, 2017 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$
1
  • $\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$ Nov 13, 2016 at 6:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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