Two researchers, Betül Durak (Rutgers University) and Serge Vaudenay (Ecole Polytechnique Fédérale de Lausanne), have given NIST early notification of a cryptanalytic attack on the FF3 technique for format-preserving encryption (FPE). The researchers gave a presentation of their work at the ESC 2017 Conference in January, and the details of the attack are expected to be published in the coming year. FF3 is specified and approved in NIST Special Publication 800-38G as a mode of operation of the Advanced Encryption Standard (AES) block cipher algorithm. NIST has concluded that FF3 is no longer suitable as a general-purpose FPE method.

Whether the attack might be practical to execute on any given implementation of FF3 depends on whether the attacker can obtain the ciphertexts (encrypted values) for a sufficient number of chosen plaintexts. The attacker would have to obtain the ciphertexts for a significant fraction of the possible plaintexts, under any single choice for the 8-byte "tweak" input, and also for a similar number of plaintexts under a second, related tweak. The attacker would have to choose most of the plaintexts adaptively, i.e., based on previously obtained information. If the attack succeeded, it would likely recover the encryption of any plaintext under any tweak.

The computational complexity of the attack depends mostly on the size of the domain, i.e., number of possible input data (not including the tweak) that the implementation is designed to encrypt. The size of the domain is denoted by radixⁿ in the FF3 specification. For the choice of attack parameters that minimizes the collection of data (specifically, to radix^11n/12 plaintext-ciphertext pairs), the number of computational steps would be radix^5n/2.      

For example, if the confidential data are 9-digit decimal strings, like social security numbers, the number of steps would be approximately 2⁷⁵. Although in this case the level of computation might be prohibitive, FF3 clearly does not achieve the intended 128-bit security level. For any significantly smaller domains of confidential data--including the middle-six digits of credit card numbers, the format that FF3 was designed to encrypt--the level of computation for the attack might be practical for many attackers.

The researchers proposed a straightforward modification to FF3: require two particular bytes of the tweak to be set to zero, which in effect would reduce the size of the tweak from eight bytes to six bytes. Implementations that properly enforce this requirement should not be vulnerable to the attack. Alternative structures/conditions on the tweak might also preclude the attack.

NIST expects to revise Special Publication 800-38G after the details of the attack are published, either to change the FF3 specification, or to withdraw the approval of FF3. Comments on this decision may be submitted to EncryptionModes@nist.gov; a formal period of public comment will also be initiated when the draft revision is released.