International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Three Third Generation Attacks on the Format Preserving Encryption Scheme FF3

Authors:
Ohad Amon , Tel Aviv University, Israel
Orr Dunkelman , University of Haifa Israel
Nathan Keller , Bar Ilan University, Israel
Eyal Ronen , Tel Aviv University, Israel
Adi Shamir , Weizmann Institute of Science, Israel
Download:
Search ePrint
Search Google
Conference: EUROCRYPT 2021
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 {\em 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.
BibTeX
@inproceedings{eurocrypt-2021-30931,
  title={Three Third Generation Attacks on the Format Preserving Encryption Scheme FF3},
  publisher={Springer-Verlag},
  author={Ohad Amon and Orr Dunkelman and Nathan Keller and Eyal Ronen and Adi Shamir},
  year=2021
}