Message-Recovery Attacks on Feistel-Based Format Preserving Encryption
| Title | Message-Recovery Attacks on Feistel-Based Format Preserving Encryption |
| Publication Type | Conference Paper |
| Year of Publication | 2016 |
| Authors | Bellare, Mihir, Hoang, Viet Tung, Tessaro, Stefano |
| Conference Name | Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security |
| Date Published | October 2016 |
| Publisher | ACM |
| Conference Location | New York, NY, USA |
| ISBN Number | 978-1-4503-4139-4 |
| Keywords | attacks, 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 |
| Abstract | 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. |
| URL | http://doi.acm.org/10.1145/2976749.2978390 |
| DOI | 10.1145/2976749.2978390 |
| Citation Key | bellare_message-recovery_2016 |