1
$\begingroup$

I have seen FF1/FF3 being said that they preserve the same format as that of the plaintext. For example, if I encrypt a decimal number 1234 then its encrypted value is also a 4 digit decimal number. Both of them use the Feistel network. How are the round functions internally designed in each round of the structure to preserve the format of the data? I wanted to get to know how the design of internal functions helps preserve the format.

$\endgroup$
1
2
$\begingroup$

From 4.1 Representation of Character Strings of the NIST SP 800 38G Rev 1 draft spec that was mentioned in the comments:

The data inputs and outputs to the FF1 and FF3-1 encryption 286 and decryption functions must be finite sequences of numerals, i.e., numeral strings. If the data to be encrypted is formatted in an alphabet that is not already the set of base radix numerals, then each character must be represented by a distinct numeral in order to apply FF1 or FF3-1.

...

The choice and implementation of a one-to-one correspondence between a given alphabet and the set of base radix numerals that represents the alphabet is outside the scope of this publication.

This is not that clear yet, but very basically you need to canonically map your input data to a range [0, N), and back again during both encryption and decryption. This mapping is outside the scope, as it is of course specific to the data input specification.


If your data consists of multiple ranges then things get a bit more tricky. Very basically you first order the data (usually left to right), then you determine the base for each separate set of input ranges. Then the value in the range is created by multiplying the input range with the lower end bases.

I'll first show you how these $\text{encode}$ and $\text{decode}$ functions would work:

Let's say that the input ranges are for a digit - excluding zero - followed by a character in the uppercase ABC, i.e. [1-9][A-Z]. The base of the digits - excluding zero - is $9$, the base of the alphabet is of course $26$.

Now let's try to calculate the value for 7Z. If you follow these rules then the value you get is $6 \cdot 26 + 25 = 181$, where $6$ is the index of 7 in $[1, 9]$, $26$ is the base (the count of characters) in the ABC and $25$ is the index of Z in that ABC.

To map it back, you first perform $181 \bmod 26$, which should give you $25$ again, which gives you Z after de-indexing. Then you divide: $\big\lceil 181 / 26 \big\rceil$, and get back $6$ which is the index of 7 in the range $[1, 9]$.

Now we need to include encryption and decryption:

You can now perform FF1 or FF3 on the result, $181$ and get a different value. You can simply use the rules to encode this to your required representation.

So say that you have $\text{encode}(\text{"7Z"}) = 181$ and $\text{enc}_k(181) = 26$, then this will give you $\text{decode}(26) = "1A"$ which you can store. Then you reverse like this: $\text{decode}(\text{dec}_k(\text{encode}(\text{"1A"}))) = "7Z"$. The encode and decode parameters are specific to [1-9][A-Z].

Above tricks can easily be extended to any format for which the ranges are clear, and - when coded correctly - only multiplication & addition for are needed for encoding and only divide-with-remainder is needed for decoding. The encoding/decoding should take less than a microsecond when implemented correctly (for relatively small input sizes, for which FPE is commonly used).

$\endgroup$
1
  • 1
    $\begingroup$ "less than a microsecond" for the encoding before and after the encryption itself is correct for FF3-1 (and even ample if that's per digit), since FF3-1's block space is limited to 192-bit. For FF1 the limit seems to be 4Tib (512MiB), and for large block the time per digit will become much larger, since it grows with the number of digits, and proportionally so when using the algorithms in the spec and the answer. $\endgroup$
    – fgrieu
    Sep 24 at 15:20

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.