Paper 2018/556

The Curse of Small Domains: New Attacks on Format-Preserving Encryption

Viet Tung Hoang, Stefano Tessaro, and Ni Trieu

Abstract

Format-preserving encryption (FPE) produces ciphertexts which have the same format as the plaintexts. Building secure FPE is very challenging, and recent attacks (Bellare, Hoang, Tessaro, CCS'16; Durak and Vaudenay, CRYPTO'17) have highlighted security deficiencies in the recent NIST SP800-38G standard. This has left the question open of whether practical schemes with high security exist. In this paper, we continue the investigation of attacks against FPE schemes. Our first contribution are new known-plaintext message recovery attacks against Feistel-based FPEs (such as FF1/FF3 from the NIST SP800-38G standard) which improve upon previous work in terms of amortized complexity in multi-target scenarios, where multiple ciphertexts are to be decrypted. Our attacks are also qualitatively better in that they make no assumptions on the correlation between the targets to be decrypted and the known plaintexts. We also surface a new vulnerability specific to FF3 and how it handles odd length domains, which leads to a substantial speedup in our attacks. We also show the first attacks against non-Feistel based FPEs. Specifically, we show a strong message-recovery attack for FNR, a construction proposed by Cisco which replaces two rounds in the Feistel construction with a pairwise-independent permutation, following the paradigm by Naor and Reingold (JoC,'99). We also provide a strong ciphertext-only attack against a variant of the DTP construction by Brightwell and Smith, which is deployed by Protegrity within commercial applications. All of our attacks show that existing constructions fall short of achieving desirable security levels. For Feistel and the FNR schemes, our attacks become feasible on small domains, e.g., 8 bits, for suggested round numbers. Our attack against the DTP construction is practical even for large domains. We provide proof-of-concept implementations of our attacks that verify our theoretical findings.

Note: our full-version with the detailed proofs

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. IACR-CRYPTO-2018
Keywords
Format-preserving encryptionattacks
Contact author(s)
hviettung @ gmail com
History
2018-10-15: last of 2 revisions
2018-06-04: received
See all versions
Short URL
https://ia.cr/2018/556
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/556,
      author = {Viet Tung Hoang and Stefano Tessaro and Ni Trieu},
      title = {The Curse of Small Domains: New Attacks on Format-Preserving Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2018/556},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/556}},
      url = {https://eprint.iacr.org/2018/556}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.