Lightweight Yet Nonce-Misuse Secure Authenticated Encryption for Very Short Inputs

We study authenticated encryption (AE) modes dedicated to very short messages, which are crucial for Internet of Things applications. One of the most popular class of AE is built on block ciphers, namely a mode of operation. The computational cost of a mode is typically measured by its rate, indicating the number of input blocks processed per block cipher call in asymptotic terms. While certain modes demonstrate efficiency in terms of rate, such as <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathsf { OCB}$ </tex-math></inline-formula>, this metric does not always accurately portray the total computational burden as it ignores overhead. Consequently, modes efficient in terms of rate may not always perform optimally with short messages. This observation motivates us to study modes that are efficient on short inputs rather than focusing on rate. Since the existing general-purpose AE modes need at least three block cipher calls for nonempty messages, we explore the design space for AE modes that use at most two calls. We propose a family of AE modes, dubbed <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ \mathsf {Manx}$ </tex-math></inline-formula>, which work when the total input length is less than <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2n$ </tex-math></inline-formula> bits, using an n-bit block cipher. Notably, the second construction of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ \mathsf {Manx}$ </tex-math></inline-formula> can encrypt almost n-bit plaintexts and saves one or two block cipher calls compared to standard modes, such as <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathsf { GCM}$ </tex-math></inline-formula> or <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathsf { OCB}$ </tex-math></inline-formula>, while preserving comparable provable security. In addition to the conventional security against nonce-respecting adversary, we prove that <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ \mathsf {Manx}$ </tex-math></inline-formula> have security against nonce-misusing adversary with a different security level for each family member. We also present benchmarks on popular 8/32-bit microprocessors, namely 8-bit AVR, 32-bit ARM Cortex-M0, and ARM Cortex-M4, using AES and lightweight block ciphers. Our results show the clear advantage of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ \mathsf {Manx}$ </tex-math></inline-formula> over the previous modes for such short messages. In particular, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ \mathsf {Manx2}$ </tex-math></inline-formula> has significant performance gain from the existing representative schemes thanks to the simple structure and parallelizability. For example, using AES-128, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ \mathsf {Manx2}$ </tex-math></inline-formula> is faster than <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathsf { OCB}$ </tex-math></inline-formula> by a factor of 1.5 to 1.7 to process a 64-bit nonce and a 120-bit plaintext.