Cryptology ePrint Archive: Report 2016/794

Message-recovery attacks on Feistel-based Format Preserving Encryption

Mihir Bellare and Viet Tung Hoang and Stefano Tessaro

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 $2^{21}$ examples for the FF3 NIST standard and $2^{25}$ 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.

Category / Keywords: secret-key cryptography / Format-preserving encryption, attacks

Original Publication (with minor differences): ACM CCS 2016

Date: received 19 Aug 2016, last revised 23 May 2017

Contact author: hviettung at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170524:030356 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]