International Association
for Cryptologic Research

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.