From Combined to Hybrid: Making Feedback-based AE even Smaller

Abstract

In CHES 2017, Chakraborti et al. proposed COFB, a rate-1 sequential block cipher-based authenticated encryption (AE) with only 1.5n-bit state, where n denotes the block size. They used a novel approach, the so-called combined feedback, where each block cipher input has a combined effect of the previous block cipher output and the current plaintext block. In this paper, we first study the security of a general rate-1 feedback-based AE scheme in terms of its overall internal state size. For a large class of feedback functions, we show that the overlying AE scheme can be attacked in 2^r queries if the internal state size is n + r bits for some r ≥ 0. This automatically shows that a birthday bound (i.e. 2^n/2 queries) secure AE scheme must have at least 1.5n-bit state, whence COFB is almost-optimal (use 1.5n-bit state and provides security up to 2^n/2/n queries). We propose a new feedback function, called the hybrid feedback or HyFB, which is a hybrid composition of plaintext and ciphertext feedbacks. HyFB has a key advantage of lower XOR counts over the combined feedback function. This essentially helps in reducing the hardware footprint. Based on HyFB we propose a new AE scheme, called HyENA, that achieves the state size, rate, and security of COFB. In addition, HyENA has significantly lower XOR counts as compared to COFB, whence it is expected to have a smaller implementation as compared to COFB.