### Cryptanalysis of Feistel-Based Format-Preserving Encryption

Orr Dunkelman, Abhishek Kumar, Eran Lambooij, and Somitra Kumar Sanadhya

##### Abstract

Format-Preserving Encryption (FPE) is a method to encrypt non-standard domains, thus allowing for securely encrypting not only binary strings, but also special domains, e.g., social security numbers into social security numbers. The need for those resulted in a few standardized constructions such as the NIST standardized FF1 and FF3-1 and the Korean Standards FEA-1 and FEA-2. Moreover, there are currently efforts both in ANSI and in ISO to include such block ciphers to standards (e.g., the ANSI X9.124 discussing encryption for financial services). Most of the proposed FPE schemes, such as the NIST standardized FF1 and FF3-1 and the Korean Standards FEA-1 and FEA-2, are based on a Feistel construction with pseudo-random round functions. Moreover, to mitigate enumeration attacks against the possibly small domains, they all employ tweaks, which enrich the actual domain sizes. In this paper we present distinguishing attacks against Feistel-based FPEs. We show a distinguishing attack against the full FF1 with data complexity of $2^{60}$ 20-bit plaintexts, against the full FF3-1 with data complexity of $2^{40}$ 20-bit plaintexts. For FEA-1 with 128-bit, 192-bit and 256-bit keys, the data complexity of the distinguishing attack is $2^{32}$, $2^{40}$, and $2^{48}$ 8-bit plaintexts, respectively. The data complexity of the distinguishing attack against the full FEA-2 with 128-bit, 192-bit and 256-bit is $2^{56}$, $2^{68}$, and $2^{80}$ 8-bit plaintexts, respectively. Moreover, we show how to extend the distinguishing attack on FEA-1 and FEA-2 using 192-bit and 256-bit keys into key recovery attacks with time complexity $2^{136}$ (for both attacks).

Available format(s)
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Differential CryptanalysisFormat Preserving EncryptionFF1FF3-1FEA-1FEA-2
Contact author(s)
eranlambooij @ gmail com
orrd @ cs haifa ac il
History
Short URL
https://ia.cr/2020/1311

CC BY

BibTeX

@misc{cryptoeprint:2020/1311,
author = {Orr Dunkelman and Abhishek Kumar and Eran Lambooij and Somitra Kumar Sanadhya},
title = {Cryptanalysis of Feistel-Based Format-Preserving Encryption},
howpublished = {Cryptology ePrint Archive, Paper 2020/1311},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1311}},
url = {https://eprint.iacr.org/2020/1311}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.