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 CCS~2016, 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 SAC~2015. 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.