Paper 2019/244

Attacks Only Get Better: How to Break FF3 on Large Domains

Viet Tung Hoang, David Miller, and Ni Trieu


We improve the attack of Durak and Vaudenay (CRYPTO'17) on NIST Format-Preserving Encryption standard FF3, reducing the running time from $O(N^5)$ to $O(N^{17/6})$ for domain $Z_N \times Z_N$. Concretely, DV's attack needs about $2^{50}$ operations to recover encrypted 6-digit PINs, whereas ours only spends about $2^{30}$ operations. In realizing this goal, we provide a pedagogical example of how to use distinguishing attacks to speed up slide attacks. In addition, we improve the running time of DV's known-plaintext attack on 4-round Feistel of domain $Z_N \times Z_N$ from $O(N^3)$ time to just $O(N^{5/3})$ time. We also generalize our attacks to a general domain $Z_M \times Z_N$, allowing one to recover encrypted SSNs using about $2^{50}$ operations. Finally, we provide some proof-of-concept implementations to empirically validate our results.

Available format(s)
Secret-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2019
Format-preserving encryptionattacks
Contact author(s)
tvhoang @ cs fsu edu
2019-08-25: last of 2 revisions
2019-02-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Viet Tung Hoang and David Miller and Ni Trieu},
      title = {Attacks Only Get Better: How to Break {FF3} on Large Domains},
      howpublished = {Cryptology ePrint Archive, Paper 2019/244},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.