Paper 2021/815

Linear Cryptanalysis of FF3-1 and FEA

Tim Beyne

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(N^{r/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 $\ge 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 $\mathbb{Z}/N\mathbb{Z}$.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published by the IACR in Crypto 2021
Keywords
Linear cryptanalysisFormat-preserving encryptionFF3-1FEA-1FEA-2
Contact author(s)
tim beyne @ esat kuleuven be
History
2021-06-16: received
Short URL
https://ia.cr/2021/815
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/815,
      author = {Tim Beyne},
      title = {Linear Cryptanalysis of FF3-1 and FEA},
      howpublished = {Cryptology ePrint Archive, Paper 2021/815},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/815}},
      url = {https://eprint.iacr.org/2021/815}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.