Cryptology ePrint Archive: Report 2021/335

Three Third Generation Attacks on the Format Preserving Encryption Scheme FF3

Ohad Amon and Orr Dunkelman and Nathan Keller and Eyal Ronen and Adi Shamir

Abstract: Format-Preserving Encryption (FPE) schemes accept plaintexts from any finite set of values (such as social security numbers or birth dates) and produce ciphertexts that belong to the same set. They are extremely useful in practice since they make it possible to encrypt existing databases or communication packets without changing their format. Due to industry demand, NIST had standardized in 2016 two such encryption schemes called FF1 and FF3. They immediately attracted considerable cryptanalytic attention with decreasing attack complexities. The best currently known attack on the Feistel construction FF3 has data and memory complexity of ${O}(N^{11/6})$ and time complexity of ${O}(N^{17/6})$, where the input belongs to a domain of size $N \times N$.

In this paper, we present and experimentally verify three improved attacks on FF3. Our best attack achieves the tradeoff curve $D=M=\tilde{O}(N^{2-t})$, $T=\tilde{O}(N^{2+t})$ for all $t \leq 0.5$. In particular, we can reduce the data and memory complexities to the more practical $\tilde{O}(N^{1.5})$, and at the same time, reduce the time complexity to $\tilde{O}(N^{2.5})$.

We also identify another attack vector against FPE schemes, the related-domain attack. We show how one can mount powerful attacks when the adversary is given access to the encryption under the same key in different domains, and show how to apply it to efficiently distinguish FF3 and FF3-1 instances.

Category / Keywords: secret-key cryptography / cryptanalysis, Format-Preserving Encryption, FF3

Original Publication (in the same form): IACR-EUROCRYPT-2021

Date: received 15 Mar 2021

Contact author: eyal ronen at cs tau ac il

Available format(s): PDF | BibTeX Citation

Version: 20210317:142710 (All versions of this report)

Short URL: ia.cr/2021/335