Cryptology ePrint Archive: Report 2019/244

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

Viet Tung Hoang and David Miller and Ni Trieu

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)$ 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.

Category / Keywords: secret-key cryptography / Format-preserving encryption, attacks

Original Publication (with major differences): IACR-EUROCRYPT-2019

Date: received 27 Feb 2019, last revised 1 Mar 2019

Contact author: tvhoang at cs fsu edu

Available format(s): PDF | BibTeX Citation

Version: 20190301:140702 (All versions of this report)

Short URL: ia.cr/2019/244


[ Cryptology ePrint archive ]