Linear Cryptanalysis of FF3-1 and FEA

Abstract

Improved attacks on generic small-domain Feistel ciphers with alternating round tweaks are obtained using linear cryptanalysis. This results in practical distinguishing and message-recovery attacks on the United States format-preserving encryption standard FF3-1 and the South-Korean standards FEA-1 and FEA-2. The data complexity of the proposed attacks on FF3-1 and FEA-1 is (O) over tilde (Nr/2-1.5), where N-2 is the domain size and r is the number of rounds. For example, FF3-1 with N = 10(3) can be distinguished from an ideal tweakable block cipher with advantage >= 1/10 using 2(23 )encryption queries. Recovering the left half of a message with similar advantage requires 2(24) data. The analysis of FF3-1 serves as an interesting real-world application of (generalized) linear cryptanalysis over the group Z/NZ.