Paper 2017/521
Breaking the FF3 FormatPreserving Encryption Standard Over Small Domains
F. Betül Durak and Serge Vaudenay
Abstract
The National Institute of Standards and Technology (NIST) recently published a FormatPreserving Encryption standard accepting two Feistel structure based schemes called FF1 and FF3. Particularly, FF3 is a tweakable block cipher based on an 8round Feistel network. In CCS~2016, Bellare et. al. gave an attack to break FF3 (and FF1) with time and data complexity $O(N^5\log(N))$, which is much larger than the code book (but using many tweaks), where $N^2$ is domain size to the Feistel network. In this work, we give a new practical total break attack to the FF3 scheme (also known as BPS scheme). Our FF3 attack requires $O(N^{\frac{11}{6}})$ chosen plaintexts with time complexity $O(N^{5})$. Our attack was successfully tested with $N\leq2^9$. It is a slide attack (using two tweaks) that exploits the bad domain separation of the FF3 design. Due to this weakness, we reduced the FF3 attack to an attack on 4round Feistel network. Biryukov et. al. already gave a 4round Feistel structure attack in SAC~2015. However, it works with chosen plaintexts and ciphertexts whereas we need a knownplaintext attack. Therefore, we developed a new generic knownplaintext attack to 4round Feistel network that reconstructs the entire tables for all round functions. It works with $N^{\frac{3}{2}} \left( \frac{N}{2} \right)^{\frac{1}{6}}$ known plaintexts and time complexity $O(N^{3})$. Our 4round attack is simple to extend to five and more rounds with complexity $N^{(r5)N+o(N)}$. It shows that FF1 with $N=7$ and FF3 with $7\leq N\leq10$ do not offer a 128bit security. Finally, we provide an easy and intuitive fix to prevent the FF3 scheme from our $O(N^{5})$ attack.
Metadata
 Available format(s)
 Publication info
 Published by the IACR in CRYPTO 2017
 Keywords
 FormatPreserving EncryptionFeistel NetworksTweakable EncryptionCryptanalysis
 Contact author(s)
 durakfbetul @ gmail com
 History
 20170605: received
 Short URL
 https://ia.cr/2017/521
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/521, author = {F. Betül Durak and Serge Vaudenay}, title = {Breaking the FF3 FormatPreserving Encryption Standard Over Small Domains}, howpublished = {Cryptology ePrint Archive, Paper 2017/521}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/521}}, url = {https://eprint.iacr.org/2017/521} }