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