Visible to the public Message-Recovery Attacks on Feistel-Based Format Preserving Encryption

TitleMessage-Recovery Attacks on Feistel-Based Format Preserving Encryption
Publication TypeConference Paper
Year of Publication2016
AuthorsBellare, Mihir, Hoang, Viet Tung, Tessaro, Stefano
Conference NameProceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security
Date PublishedOctober 2016
Conference LocationNew York, NY, USA
ISBN Number978-1-4503-4139-4
Keywordsattacks, Collaboration, composability, Encryption, format-preserving encryption, Human Behavior, information theoretic security, ios, iOS encryption, Metrics, pubcrawl, Resiliency, Scalability, theoretical cryptography, white box, white box cryptography

We give attacks on Feistel-based format-preserving encryption (FPE) schemes that succeed in message recovery (not merely distinguishing scheme outputs from random) when the message space is small. For \$4\$-bit messages, the attacks fully recover the target message using \$2textasciicircum1 examples for the FF3 NIST standard and \$2textasciicircum5 examples for the FF1 NIST standard. The examples include only three messages per tweak, which is what makes the attacks non-trivial even though the total number of examples exceeds the size of the domain. The attacks are rigorously analyzed in a new definitional framework of message-recovery security. The attacks are easily put out of reach by increasing the number of Feistel rounds in the standards.

Citation Keybellare_message-recovery_2016