International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Attacks only Get Better: How to Break FF3 on Large Domains

Authors:
Viet Tung Hoang
David Miller
Ni Trieu
Download:
DOI: 10.1007/978-3-030-17656-3_4
Search ePrint
Search Google
Abstract: 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)$$O(N5) to $$O(N^{17/6})$$O(N17/6) for domain $$\mathbb {Z}_N \times \mathbb {Z}_N$$ZN×ZN. Concretely, DV’s attack needs about $$2^{50}$$250 operations to recover encrypted 6-digit PINs, whereas ours only spends about $$2^{30}$$230 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 $$\mathbb {Z}_N \times \mathbb {Z}_N$$ZN×ZN from $$O(N^3)$$O(N3) time to just $$O(N^{5/3})$$O(N5/3) time. We also generalize our attacks to a general domain $$\mathbb {Z}_M \times \mathbb {Z}_N$$ZM×ZN, allowing one to recover encrypted SSNs using about $$2^{50}$$250 operations. Finally, we provide some proof-of-concept implementations to empirically validate our results.
Video from EUROCRYPT 2019
Video provided under Creative Commons / CC BY 3.0
BibTeX
@article{eurocrypt-2019-29356,
  title={Attacks only Get Better: How to Break FF3 on Large Domains},
  booktitle={Advances in Cryptology – EUROCRYPT 2019},
  series={Advances in Cryptology – EUROCRYPT 2019},
  publisher={Springer},
  volume={11477},
  pages={85-116},
  doi={10.1007/978-3-030-17656-3_4},
  author={Viet Tung Hoang and David Miller and Ni Trieu},
  year=2019
}