1. Attacks Only Get Better: How to Break FF3 on Large Domains 2019 Attacks Eurocrypt FPE
    Viet Tung Hoang, David Miller and Ni Trieu
    [View PDF on eprint.iacr.org]
    [Show BibTex Citation]

    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, Report 2019/244},
    year = {2019},
    note = {\url{https://eprint.iacr.org/2019/244}},
    }

We improve the attack of Durak and Vaudenay (CRYPTO’17) on NIST Format-Preserving Encryption standard FF3, reducing the running time from O(N5) to O(N17/6) for domain ZN×ZN. 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 ZN×ZN from O(N3) time to just O(N5/3) time. We also generalize our attacks to a general domain ZM×ZN, allowing one to recover encrypted SSNs using about 2^50 operations. Finally, we provide some proof-of-concept implementations to empirically validate our results.

  1.