ffx-spec.pdf

1 Introduction

This specification document describes FFX, a mechanism for format-preserving encryption (FPE).

database.

The encryption algorithm of FFX takes in a key K, a plaintext X,and a tweak T . The plain-

text is taken over an arbitrary alphabet Chars. Assuming that n = |X| is a supported length,

FFX.Encrypt will produce—deterministically—a ciphertext Y = FFX.Encrypt

One can recover X from Y by way of X = FFX.Decrypt

imbalance split(n) in the Feistel network, and the round function F.

As example instantiations of FFX, we consider enciphering (i) binary strings of 8–128 bits, or

(ii) decimal strings of 4–36 digits. In Appendices A and B we specify parameter sets, denoted A2

and A10, to enable these task. Both employ a round function derived from AES. The fully instan-

tiated schemes would be denoted FFX-A2 and FFX-A10.

2

there being multiple instantiations (that is, parameter choices). It further reflects that FFX is an

outgrowth of, and extension to, the FFSEM specification earlier submitted to NIST by Spies [28].

The current draft replaces that contribution. Compared to it, FFX is more general, adding in

support for tweaks, non-binary alphabets, and non-balanced splits. Cycle-walking can now be

avoided in the setting of primary practical importance, encrypting decimal strings.

While this document does not attempt to explain or survey all of the cryptographic results relating

to FFX, their existence—and indeed the entire history of results concerning Feistel networks—

While FFX can, in principle, be used to encipher character strings of arbitrary length, the mecha-

nism is intended for message spaces smaller than that of AES (2

strings, other techniques would seem to be preferable. In particular, EME2 [9] can encipher binary

strings of any length n>128.

An earlier version of this specification document, version 1.0, was provided to NIST in November

2009. The substantive change we have made since that version is the addition of a parameter profile

for binary strings, A2.

See Figure 1 for an illustration of FFX, Figure 2 for a description of the parameters on which FFX

are called characters. The number of characters radix in Chars is referred to as the radix of the

alphabet. Example radix values are 2, 10, and 26, corresponding to bits, digits, and uppercase

English letters. It is required that radix ≥ 2.

If a user wishes to encrypt over a non-numeric alphabet, say {a,...,z}, she must set up a bijective

mapping between this alphabet and Chars = {0,...,radix − 1} via which her inputs and outputs

can be regarded as numeric values, as required for our algorithms.

A string is a finite sequence of characters from Chars.By | X | we denote the length of string X,

the number of characters in it. For example, X = 00326 is a string of length | 00326 | = 5. Note

first four rounds are shown. The divided boxes on the left are used to illustrate the re-partitioning of a

string; for example, string B

No such re-partitioning occurs on the right, but strings get two names instead. All boxed strings are over

that leading zeros are counted just like any other character. By Chars

over Chars having any length. If X, Y ∈ Chars