CryptoDB

David Miller

Publications

Year
Venue
Title
2019
EUROCRYPT
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.

Coauthors

Viet Tung Hoang (1)
Ni Trieu (1)