0
$\begingroup$

A FPE preserves the format. There is a correspondence between the format of the ciphertext and the plaintext.

Given that a message in some binary enconded format can easily be divded in some l blocks of n bits which will be encrypted to l blocks of n bits I would call (some necessary padding issues ignored) pretty much a format preserving encryption).

Is this true? Are block ciphers considered to be FPE?

Or are the ciphers working on blocks which have a disparity of the input->output ratio of either block numbers and block size?

$\endgroup$
4
$\begingroup$

The formal definition of a block cipher is a function $$ E_K(P) := E(K, P): \{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^n $$

The input and output spaces are by definition n-bit blocks, so the operation of the cipher in Electronic Code Book (ECB) mode is technically "format preserving".

That is not however what "Format Preserving Encryption" (FPE) generally refers to, nor does it mean that all block ciphers modes of operation are format preserving, nor that all symmetric encryption functions are format preserving.

NIST SP800-38G, which recommends FPE modes of operation for block ciphers, defines FPE as "Given any finite set of symbols, like the decimal numerals, FPE transforms data that is formatted as a sequence of the symbols in such a way that the encrypted form of the data has the same format and length as the original data." In other words FPE is a function

$$ E_K(P) := E(K, P): K \times M \rightarrow M $$

where M is not necessarily a block of bits. For example M could be a 16-digit credit card number, or a Social Security Number. The ciphertext - rather than being a block of bits - will have the same size and alphabet as the input; that is it will look like a credit card number or SSN.

A typical use of FPE is to selectively add data encryption to fields within legacy messages without modifying the message format or the validation functions of your legacy systems.

Many block cipher modes of operation cause ciphertext expansion - where the ciphertext is larger that the plaintext - are are not format preserving. Any mode that includes a checksum or requires a message-unique Initialisation Vector (IV) will cause ciphertext expansion.

$\endgroup$
  • $\begingroup$ thanks! The potential "breaking of FPE" due to addition of IV and alike is understood. Also the definition of block cipher is exhaustive. Partly my question was also wondering if E(K,P): K x {0,1}^n -> {0,1}^(n+x(K)) would exists? $\endgroup$ – humanityANDpeace Nov 11 '14 at 11:38
3
$\begingroup$

Is this true? Are block ciphers considered to be FPE?

Well not exactly . Its something more than block ciphers. Of course block ciphers are integral to FPE. Some times we need to preserve the lengths but some times we need to preserve the lengths of encoded strings. Lets see some examples.

Informally, In order to preserve the formats of input data types we need ranking functions (along with length preserving encryption schemes). Ranking functions, as the researchers say[2], is a folklore approach to preserve the formats of the data types. Well there is something else called as Cycle Walking but that is not efficient.

Now lets see different examples,

  • An IPv4 address could be ranked as a 32 bits integer. The ranked integer is then encrypted using a block cipher like FNR to result in another 32 bits integer. The resultant cipher text is converted back to dotted notation of IPv4 address in order to preserve the format. Similar thing could be done for SSNs, Credit Card Numbers(need to trim the LUHN check sum while ranking etc)
  • Since IPv6 address is 128 bits in length traditional AES-128 itself could be used to both encrypt and preserve the IPv6 address format. So here AES itself is the length preserving block cipher.

  • Input data types such as Email addresses the ranking technique does not hold good though. A trivial approach to preserve the formats of email addresses is to encrypt user id and domain separately but that may not be secure enough.

  • Now if we have to encrypt words in an English dictionary and lets define format preservation here means encryption of an english word should result in a legitimate english word again then ranking could be enumerating all the words from $A-Z$ from $0 - 10^6$ assuming there are $10^6$ words. So we need approximately $20$ bits (since $10^6 \approx 2^{20}$). We need block cipher that preserves $20$ bit size. So the nuance now is we dont necessarily preserve the length of the input string (but preserve the length of enumerated string) but preserve the format since our definition of format preserving is the ciphertext should be english word again.

We have seen above different examples that helps understand the nuances between block ciphers and their usage in preserving formats of input types.

$\endgroup$

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.