Score:2

FPE Limitations and Scope of FPE

br flag

Do you think the format preserving encryption(FPE) schemes have any limitation with respect to other conventional block ciphers? Do FPE have a wide range of applications to be a future research area?

Score:2
my flag

Do you think the format preserving encryption(FPE) schemes have any limitation with respect to other conventional block ciphers?

Actually, one can view an FPE scheme as a generalization of a conventional block cipher. After all, a conventional block cipher is fixed to a specific block size; with FPE, we can use any block size we find convenient (for example, the entire message).

Do FPE have a wide range of applications to be a future research area?

I believe so. One nice thing about FPE (with a tweak; most FPE schemes allow one) is that it is easy to construct an AEAD scheme that is quite misuse tolerant:

  • To encrypt, you'd take the message $M$, and append $k$ zeros and $\ell$ random bits (or nonce; the decryptor will recover these bits and so they can be used as a sequence number if needed). Encrypt that with the FPE scheme, using the AAD as the tweak.

  • To decrypt, you decrypt with the FPE scheme using the AAD as the tweak; parse the result, and check if the $k$ zeros appear at the end.

It should be obvious that this is a secure AAD scheme (assuming that the FPE scheme is secure). In addition:

  • If the sender uses bad randomness for its $\ell$ random bits, it becomes a deterministic scheme where the adversary can determine if the same message was sent twice, but can't determine anything beyond that.

  • If the receiver forgets to check the $k$ zeros, then this becomes a fully garbling scheme, where the adversary can change the decrypted message into something random, but can't do anything beyond that. This is in contrast to many AEAD schemes, where if the decryptor forgets to check the tag, then the encryption becomes malleable (and the AAD is essentially ignored).

So, if this is so wonderful, what's the drawback? Well, one major one is performance - the current FPE schemes are quite slow, and so this straight-forward design isn't used. A better performing (but still secure) FPE scheme would make this far more attactive.

Another obvious drawback is that FPE cannot be implemented in a "one-pass" manner (where we process the message in parts); this is convenient when we need to handle large messages; however it should be obvious that being able to do misuse-tolerant encryption (where lack of nonce entropy leaks only whether the messages were identical) is incompatible with one-pass encryption, and that being able to do misuse-tolerant decryption (where forgetting to check the integrity check allows an active attacker only to randomize the plaintext) is incompatible with one-pass decryption.

Score:1
ng flag

Limitations (also present in a normal block cipher like AES)

  • One limitation of Format Preserving Encryption is that it's deterministic: the same plaintext always leads to the same ciphertext. And by an entropy argument, that must be if all plaintexts that fit the format are possible. This in turn prevents meeting the criteria of resistance to Chosen Plaintext Attack.
  • Another limitation of FPE as practiced is that it's symmetric: a secret (typically, the same) is needed on the encryption side. That's necessary for security of low-entropy plaintext, which is the typical payload of FPE.

Perspectives, starting from the easy

  1. When there are restriction to the plaintext w.r.t. the format, it's easy to somewhat remedy the first bullet point, and even get somewhat Authenticated FPE. For example, when encrypting a credit card number plus expiry date, at least the number's last digit (a checksum) and date field, and to a degree the first 6 digits (identifying the emitter) allow to squeeze some info usable for IV or authentication.
  2. For high-enough entropy payload (say 128-bit), it is feasible to define asymmetric FPE secure within the limits of the first bullet point. It's easy to get this from a trapdoor permutation such as RSA, but this particular one is of limited practical interest for FPE, because FPE is primarily motivated by small payload. The challenge is trapdoor permutation over a smaller interval, say a few hundred bits. I wish I knew the sate of that art.
Maarten Bodewes avatar
in flag
Wasn't there also a problem with the message size for specific forms of FPE where it needs to be larger than a specific number of bits?
fgrieu avatar
ng flag
@MaartenBodewes: I don't see what you mean in your second comment. We know how to achieve essentially perfect FPE for any interval, for the symmetric breed with identical keys (or any key deducible from the other). Perhaps enrich your comment, since you can!
poncho avatar
my flag
The same two limitations you list would also apply to AES; the AES block cipher is also deterministic and is symmetric.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.