Andreeva, E., Bhati, A. S., Preneel, B., & Vizár, D. (2021). 1, 2, 3, Fork: Counter Mode Variants based on a Generalized Forkcipher. IACR Transactions on Symmetric Cryptology, 2021(3).
DOI: 10.46586/tosc.v2021.i3.1-35 Metadata
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 ForkSkinny (an MFC with s = 2) with the traditional CTR and the more recent CTRT modes, both are instantiated with the SKINNY TBC. Our estimations show that any GCTR variant with ForkSkinny can achieve an efficiency advantage of over 20% for moderately long messages, illustrating that the use of an efficient MFC with s ≥ 2 brings a clear speed-up.

Andreeva, E., Roy, A., & Sauer, J. F. (2021). Interpolation Cryptanalysis of Unbalanced Feistel Networks with Low Degree Round Functions. In Selected Areas in Cryptography (pp. 273–300). Springer LNCS.
DOI: 10.1007/978-3-030-81652-0_11 Metadata ⯈Fulltext (preprint)
Abstract: In recent years a new type of block ciphers and hash functions over a (large) field, such as MiMC and GMiMC, have been designed. Their security, particularly over a prime field, is mainly determined by algebraic cryptanalysis techniques, such as Gröbner basis and interpolation attacks. In SAC 2019, Li and Preneel presented low memory interpolation attack against the MiMC and Feistel-MiMC designs. In this work we answer the open question posed in their work and show that low memory interpolation attacks can be extended to unbalanced Feistel networks (UFN) with low degree functions, and in particular to the GMiMC design. Our attack applies to UFNs with expanding and contracting round functions keyed either via identical (univariate) or distinct round keys (multivariate). Since interpolation attacks do not necessarily yield the best possible attacks over a binary extension field, we focus our analysis on prime fields Fp . Our next contribution is to develop an improved technique for a more efficient key recovery against UFNs with expanding round function. We show that the final key recovery step can be reduced not only to the gcd but also to the root finding problem. Despite its higher theoretical complexity, we show that our approach has a particularly interesting application on Sponge hash functions based on UFNs, such as GMiMCHash. We illustrate for the first time how our root finding technique can be used to find collision, second preimage and preimage attacks on (reduced round) members of the GMiMCHash family. In addition, we support our theoretical analysis with small-scale experimental results.

Andreeva, E., Bhattacharyya, R., & Roy, A. (2021). Compactness of Hashing Modes and Efficiency Beyond Merkle Tree. In Lecture Notes in Computer Science (pp. 92–123). Springer.
DOI: 10.1007/978-3-030-77886-6_4 Metadata ⯈Fulltext (preprint)
Abstract: We revisit the classical problem of designing optimally efficient cryptographically secure hash functions. Hash functions are traditionally designed via applying modes of operation on primitives with smaller domains. The results of Shrimpton and Stam (ICALP 2008), Rogaway and Steinberger (CRYPTO 2008), and Mennink and Preneel (CRYPTO 2012) show how to achieve optimally efficient designs of 2n-to-n-bit compression functions from non-compressing primitives with asymptotically optimal 2n/2−ϵ -query collision resistance. Designing optimally efficient and secure hash functions for larger domains ( >2n bits) is still an open problem. To enable efficiency analysis and comparison across hash functions built from primitives of different domain sizes, in this work we propose the new compactness efficiency notion. It allows us to focus on asymptotically optimally collision resistant hash function and normalize their parameters based on Stam´s bound from CRYPTO 2008 to obtain maximal efficiency. We then present two tree-based modes of operation as a design principle for compact, large domain, fixed-input-length hash functions. 1. Our first construction is an Augmented Binary Tree (ABR) mode. The design is a (2ℓ+2ℓ−1−1)n -to-n-bit hash function making a total of (2ℓ−1) calls to 2n-to-n-bit compression functions for any ℓ≥2 . Our construction is optimally compact with asymptotically (optimal) 2n/2−ϵ -query collision resistance in the ideal model. For a tree of height ℓ , in comparison with Merkle tree, the ABR mode processes additional (2ℓ−1−1) data blocks making the same number of internal compression function calls. 2. With our second design we focus our attention on the indifferentiability security notion. While the ABR mode achieves collision resistance, it fails to achieve indifferentiability from a random oracle within 2n/3 queries. ABR+ compresses only 1 less data block than ABR with the same number of compression calls and achieves in addition indifferentiability up to 2n/2−ϵ queries. Both of our designs are closely related to the ubiquitous Merkle Trees and have the potential for real-world applicability where the speed of hashing is of primary interest.

Andreeva, E., Deprez, A., Bermudo Mera, J. M., Karmakar, A., & Purnal, A. (2021). Optimized Software Implementations for the Lightweight Encryption Scheme ForkAE. In Smart Card Research and Advanced Applications (pp. 68–83). Springer.
DOI: 10.1007/978-3-030-68487-7_5 Metadata ⯈Fulltext (preprint)
Abstract: In this work we develop optimized software implementations for ForkAE, a second round candidate in the ongoing NIST lightweight cryptography standardization process. Moreover, we analyze the performance and efficiency of different ForkAE implementations on two embedded platforms: ARM Cortex-A9 and ARM Cortex-M0. First, we study portable ForkAE implementations. We apply a decryption optimization technique which allows us to accelerate decryption by up to 35%. Second, we go on to explore platform-specific software optimizations. In platforms where cache-timing attacks are not a risk, we present a novel table-based approach to compute the SKINNY round function. Compared to the existing portable implementations, this technique speeds up encryption and decryption by 20% and 25%, respectively. Additionally, we propose a set of platform-specific optimizations for processors with parallel hardware extensions such as ARM NEON. Without relying on parallelism provided by long messages (cf. bit-sliced implementations), we focus on the primitive-level ForkSkinny parallelism provided by ForkAE to reduce encryption and decryption latency by up to 30%. We benchmark the performance of our implementations on the ARM Cortex-M0 and ARM Cortex-A9 processors and give a comparison with the other SKINNY-based schemes in the NIST lightweight competition - SKINNY-AEAD and Romulus.

Andreeva, E., Bhati, A. S., & Vizár, D. (2021). Nonce-Misuse Security of the SAEF Authenticated Encryption Mode. In Selected Areas in Cryptography (pp. 512–534). Springer LNCS.
DOI: 10.1007/978-3-030-81652-0_20 Metadata ⯈Fulltext (preprint)
Abstract: ForkAE is a NIST lightweight cryptography candidate that uses the forkcipher primitive in two modes of operation - SAEF and PAEF - optimized for authenticated encryption of the shortest messages. SAEF is a sequential and online AEAD that minimizes the memory footprint compared to its alternative parallel mode PAEF, catering to the most constrained devices. SAEF was proven AE secure against nonce-respecting adversaries. Due to their more acute and direct exposure to device misuse and mishandling, in most use cases of lightweight cryptography, nonce reuse presents a very realistic attack vector. Furthermore, many lightweight applications mandate security for their online AEAD schemes against block-wise adversaries. Surprisingly, a very few NIST lightweight AEAD candidates come with provable guarantees against these security threats. In this work we investigate the provable security guarantees of SAEF when nonces are repeated under a refined version of the notion of online authenticated encryption OAE given by Fleischmann et al. in 2012. Using the coefficient H technique we show that, with no modifications, SAEF is OAE secure up to the birthday security bound, i.e., up to 2n/2 processed blocks of data, where n is the block size of the forkcipher. The implications of our work is that SAEF is safe to use in a block-wise fashion, and that if nonces get repeated, this has no impact on ciphertext integrity and confidentiality only degrades by a limited extent up to repetitions of common message prefixes.

Andreeva, E., Lallemand, V., Purnal, A., Reyhanitabar, R., Roy, A., & Vizár, D. (2019). Forkcipher: A New Primitive for Authenticated Encryption of Very Short Messages. In Lecture Notes in Computer Science (pp. 153–182). Springer LNCS.
DOI: 10.1007/978-3-030-34621-8_6 Metadata ⯈Fulltext (preprint)
Abstract: Highly efficient encryption and authentication of short messages is an essential requirement for enabling security in constrained scenarios such as the CAN FD in automotive systems (max. message size 64 bytes), massive IoT, critical communication domains of 5G, and Narrowband IoT, to mention a few. In addition, one of the NIST lightweight cryptography project requirements is that AEAD schemes shall be "optimized to be efficient for short messages (e.g., as short as 8 bytes)". In this work we introduce and formalize a novel primitive in symmetric cryptography called forkcipher. A forkcipher is a keyed primitive expanding a fixed-lenght input to a fixed-length output. We define its security as indistinguishability under a chosen ciphertext attack (for n-bit inputs to 2n-bit outputs). We give a generic construction validation via the new iterate-fork-iterate design paradigm. We then propose ForkSkinny as a concrete forkcipher instance with a public tweak and based on SKINNY: a tweakable lightweight cipher following the TWEAKEY framework. We conduct extensive cryptanalysis of ForkSkinny against classical and structure-specific attacks. We demonstrate the applicability of forkciphers by designing three new provably-secure nonce-based AEAD modes which offer performance and security tradeoffs and are optimized for efficiency of very short messages. Considering a reference block size of 16 bytes, and ignoring possible hardware optimizations, our new AEAD schemes beat the best SKINNY-based AEAD modes. More generally, we show forkciphers are suited for lightweight applications dealing with predominantly short messages, while at the same time allowing handling arbitrary messages sizes. Furthermore, our hardware implementation results show that when we exploit the inherent parallelism of ForkSkinny we achieve the best performance when directly compared with the most efficient mode instantiated with SKINNY.