CryptoDB
Attacks only Get Better: How to Break FF3 on Large Domains
| Authors: | |
|---|---|
| Download: |
|
| 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
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
}