Paper 2021/1154

1, 2, 3, Fork: Counter Mode Variants based on a Generalized Forkcipher

Elena Andreeva, Amit Singh Bhati, Bart Preneel, and Damian Vizar

Abstract

A multi-forkcipher (MFC) is a generalization of the forkcipher (FC) primitive introduced by Andreeva et al. at ASIACRYPT'19. An MFC is a tweakable cipher that computes $s$ output blocks for a single input block, with $s$ arbitrary but fixed. We define the MFC security in the ind-prtmfp notion as indistinguishability from $s$ tweaked permutations. Generalizing tweakable block ciphers (TBCs, $s = 1$), as well as forkciphers ($s=2$), MFC lends itself well to building simple-to-analyze modes of operation that support any number of cipher output blocks. Our main contribution is the generic CTR encryption mode GCTR that makes parallel calls to an MFC to encrypt a message $M$. We analyze the set of all 36 ``simple and natural'' GCTR variants under the nivE security notion by Peyrin and Seurin from CRYPTO'16. Our proof method makes use of an intermediate abstraction called tweakable CTR (TCTR) that captures the core security properties of GCTR common to all variants, making their analyses easier. Our results show that many of the schemes achieve from well beyond birthday bound (BBB) to full $n$-bit security under nonce respecting adversaries and some even BBB and close to full $n$-bit security in the face of realistic nonce misuse conditions. We finally present an efficiency comparison of GCTR using $\mathsf{ForkSkinny}$ (an MFC with $s=2$) with the traditional CTR and the more recent CTRT modes, both are instantiated with the $\mathsf{SKINNY}$ TBC. Our estimations show that any GCTR variant with $\mathsf{ForkSkinny}$ can achieve an efficiency advantage of over $20\%$ for moderately long messages, illustrating that the use of an efficient MFC with $s\geq 2$ brings a clear speed-up.