Security Evaluation of Feistel-Based Format-Preserving Encryption Against Small-Domain Attacks

Abstract

Format-preserving encryption (FPE) enables encryption while preserving the format of the underlying data, and is therefore useful for protecting structured data such as identifiers, account numbers, and decimal strings. Many practical FPE schemes are based on Feistel networks and are intended for use over small or structured domains. However, in such domains, attacks whose complexities depend on the domain size can become relevant. In this paper, we examine small-domain attacks on Feistel-based FPE schemes and evaluate their impact on FF1, FF3, FF3-1, $\textsf {FEA}$ -1, and $\textsf {FEA}$ -2. The attacks considered include message-recovery attacks, round-function-recovery attacks, dedicated slide attacks on FF3, differential attacks, linear attacks, and related-domain attacks. We analyze the security of the five schemes over representative binary and decimal string domains, and identify the conditions under which the attacks affect their claimed security levels. The results show that the security of Feistel-based FPE depends on the domain size, the number of rounds, the tweak schedule, and the amount of data available under a fixed key. We also discuss countermeasures based on increasing the number of rounds, restricting deployment to sufficiently large domains, and limiting the amount of data encrypted under a fixed key. These results provide practical guidance for the secure deployment of Feistel-based FPE schemes over small domains.