Andreeva, E., Cogliati, B., Lallemand, V., Minier, M., Purnal, A., & Roy, A. (2024). Masked Iterate-Fork-Iterate: A New Design Paradigm for Tweakable Expanding Pseudorandom Function. In C. Pöpper & L. Batina (Eds.), Applied Cryptography and Network Security (pp. 433–459). Springer, Cham. https://doi.org/10.1007/978-3-031-54773-7_17
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-αn-bit (α≥2), n-bit secure, domain expanding TPRF. We dub this new generic composition masked Iterate-Fork-Iterate mIFI. We then propose a concrete TPRF instantiation ButterKnife that expands an n-bit input to 8n-bit output via a public tweak and secret key. 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 SAFE and 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 SAFE with 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 ZAE DAE. Our second candidate ZAFE, which uses the same authentication pass as ZAE, offers a similar level of speedup. Besides, we show that ButterKnife, when used in Counter Mode, is slightly faster than AES (0.55 c/B vs 0.63 c/B on Skylake).
en
Project title:
Semantische und kryptografische Grundlagen von Informationssicherheit und Datenschutz durch modulares Design: F 8500 (FWF - Österr. Wissenschaftsfonds)