Publication

Breaking The FF3 Format-Preserving Encryption Standard Over Small Domains

Abstract

The National Institute of Standards and Technology (NIST) recently published a Format-Preserving Encryption standard accepting two Feistel structure based schemes called FF1 and FF3. Particularly, FF3 is a tweakable block cipher based on an 8-round Feistel network. In CCS2016, Bellare et. al. gave an attack to break FF3 (and FF1) with time and data complexity O(N5log(N))O(N^5\log(N)), which is much larger than the code book (but using many tweaks), where N2N^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(N116)O(N^{\frac{11}{6}}) chosen plaintexts with time complexity O(N5)O(N^{5}). Our attack was successfully tested with N29N\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 4-round Feistel network. Biryukov et. al. already gave a 4-round Feistel structure attack in SAC2015. However, it works with chosen plaintexts and ciphertexts whereas we need a known-plaintext attack. Therefore, we developed a new generic known-plaintext attack to 4-round Feistel network that reconstructs the entire tables for all round functions. It works with N32(N2)16N^{\frac{3}{2}} \left( \frac{N}{2} \right)^{\frac{1}{6}} known plaintexts and time complexity O(N3)O(N^{3}). Our 4-round attack is simple to extend to five and more rounds with complexity N(r5)N+o(N)N^{(r-5)N+o(N)}. It shows that FF1 with N=7N=7 and FF3 with 7N107\leq N\leq10 do not offer a 128-bit security. Finally, we provide an easy and intuitive fix to prevent the FF3 scheme from our O(N5)O(N^{5}) attack.

About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.