Masked Iterate-Fork-Iterate: A New Design Paradigm for Tweakable Expanding Pseudorandom Function

Many modes of operations for block ciphers or tweakable block ciphers do not require invertibility from their underlying primitive. In this work, we study fixed-length Tweakable Pseudorandom Function (TPRF) with large domain expansion, a novel primitive that can bring high security and significant performance optimizations in symmetric schemes, such as (authenticated) encryption. Our first contribution is to introduce a new design paradigm, derived from the Iterate-Fork-Iterate construction, in order to build n-to- \(\alpha n\) -bit ( \(\alpha \ge 2\) ), n-bit secure, domain expanding TPRF. We dub this new generic composition masked Iterate-Fork-Iterate \(\textsf{mIFI}\) . We then propose a concrete TPRF instantiation \(\textsf {ButterKnife} \) that expands an n-bit input to 8n-bit output via a public tweak and secret key. \(\textsf {ButterKnife} \) is built with high efficiency and security in mind. It is fully parallelizable and based on Deoxys-BC, the AES-based tweakable block cipher used in the authenticated encryption winner algorithm in the defense-in-depth category of the CAESAR competition. We analyze the resistance of ButterKnife to differential, linear, meet-in-the-middle, impossible differentials and rectangle attacks. A special care is taken to the attack scenarios made possible by the multiple branches. Our next contribution is to design and provably analyze two new TPRF-based deterministic authenticated encryption (DAE) schemes called \(\textsf{SAFE}\) and \(\textsf{ZAFE}\) that are highly efficient, parallelizable, and offer \((n+\min (n,t))/2\) bits of security, where n, t denote respectively the input block and the tweak sizes of the underlying primitives. We further implement \(\textsf{SAFE}\) with \(\textsf {ButterKnife} \) to show that it achieves an encryption performance of 1.18 c/B for long messages on Skylake, which is \(24\%\) faster than the comparable Crypto’17 TBC-based \(\textsf{ZAE}\) DAE. Our second candidate \(\textsf{ZAFE}\) , which uses the same authentication pass as \(\textsf{ZAE}\) , offers a similar level of speedup. Besides, we show that \(\textsf {ButterKnife} \) , when used in Counter Mode, is slightly faster than \(\textsf{AES}\) (0.55 c/B vs 0.63 c/B on Skylake).