Breaking the FF3 Format-Preserving Encryption Standard over Small Domains
Breaking the FF3 Format-Preserving Encryption Standard over Small Domains
复制标题
打破小域上的 FF3 格式保留加密标准
DOI：
10.1007/978-3-319-63715-0_23
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
S. Vaudenay
中科院分区：
文献类型：
--
作者：
F. Durak;S. Vaudenay
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(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\leqslant 2^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 \(N^{\frac{3}{2}} \left( \frac{N}{2} \right) ^{\frac{1}{6}}\) known plaintexts and time complexity \(O(N^{3})\). Our 4-round attack is simple to extend to five and more rounds with complexity \(N^{(r-5)N+o(N)}\). It shows that FF1 with \(N=7\) and FF3 with \(7\leqslant N\leqslant 10\) do not offer a 128-bit security. Finally, we provide an easy and intuitive fix to prevent the FF3 scheme from our \(O(N^{5})\) attack.
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(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\leqslant 2^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 \(N^{\frac{3}{2}} \left( \frac{N}{2} \right) ^{\frac{1}{6}}\) known plaintexts and time complexity \(O(N^{3})\). Our 4-round attack is simple to extend to five and more rounds with complexity \(N^{(r-5)N+o(N)}\). It shows that FF1 with \(N=7\) and FF3 with \(7\leqslant N\leqslant 10\) do not offer a 128-bit security. Finally, we provide an easy and intuitive fix to prevent the FF3 scheme from our \(O(N^{5})\) attack.