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

Viet Tung Hoang; David Miller; Ni Trieu

Paper 2019/244

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

Viet Tung Hoang, 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 to for domain . Concretely, DV's attack needs about operations to recover encrypted 6-digit PINs, whereas ours only spends about 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 from time to just time. We also generalize our attacks to a general domain , allowing one to recover encrypted SSNs using about operations. Finally, we provide some proof-of-concept implementations to empirically validate our results.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: A major revision of an IACR publication in EUROCRYPT 2019
Keywords: Format-preserving encryption attacks
Contact author(s): tvhoang @ cs fsu edu
History: 2019-08-25: last of 2 revisions; 2019-02-28: received; See all versions
Short URL: https://ia.cr/2019/244
License: CC BY

BibTeX

@misc{cryptoeprint:2019/244,
      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, Paper 2019/244},
      year = {2019},
      url = {https://eprint.iacr.org/2019/244}
}