Generic Attack on Iterated Tweakable FX Constructions

Tweakable block ciphers are increasingly becoming a common primitive to build new resilient modes as well as a concept for multiple dedicated designs. While regular block ciphers define a family of permutations indexed by a secret key, tweakable ones define a family of permutations indexed by both a secret key and a public tweak. In this work we formalize and study a generic framework for building such a tweakable block cipher based on regular block ciphers, the iterated tweakable FX construction, which includes many such previous constructions of tweakable block ciphers. Then we describe a cryptanalysis from which we can derive a provable security upper-bound for all constructions following this tweakable iterated FX strategy. Concretely, the cryptanalysis of r rounds of our generic construction based on n-bit block ciphers with \(\kappa \)-bit keys requires \(\mathcal {O}(2^{\frac{r}{r+1}(n + \kappa )})\) online and offline queries. For \(r=2\) rounds this interestingly matches the proof of the particular case of \({\texttt {XHX2}}\) by Lee and Lee (ASIACRYPT 2018) thus proving for the first time its tightness. In turn, the \({\texttt {XHX}}\) and \({\texttt {XHX2}}\) proofs show that our generic cryptanalysis is information theoretically optimal for 1 and 2 rounds.