Breaking the FF3 Format-Preserving Encryption Standard over Small Domains

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 much larger than the code book (but using many tweaks). In this work, we give a new practical total break attack to the FF3 scheme (also known as BPS scheme). Our attack was successfully tested with small domains. 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. Our results show that FF1 does not offer a 128-bit security. Finally, we provide an easy and intuitive fix to prevent the FF3 scheme from our attack.