The Manx AE modes

Authenticated encryption for very short inputs

by Alexandre Adomnicăi

April 1st, 2023

Recently, I had the opportunity to assist Kazuhiko Minematsu and Junji Shikata on the design of new authenticated encryption (AE) modes, dubbed Manx, finely tuned for very short inputs. This blogpost gives a brief overview of this work, for more details please refer to our paper (to be presented at CT-RSA 2023).

How short inputs?

While there are a bunch of well-analyzed AE modes available on the shelf, they do not always constitute the optimal solution for every scenario. Consider for instance the case of Internet-of-Things (IoT) solutions that deal with tiny communication bandwidth (e.g. Sigfox and its 12-byte payload). Such solutions commonly rely on the Counter with CBC-MAC (CCM) mode for the encryption layer (e.g. Bluetooth Mesh, LoRaWAN, Sigfox) as it is easy to implement and does not require the cipher decryption function. On the other hand, it requires at least 4 calls to the internal block cipher to process non-empty messages. The most efficient general-purpose AE modes in this regard require at least 3 cipher calls, leading to the following question:

What AE modes are possible with at most 2 block cipher calls?

The aim of this work was to address this question by restricting the input to be at most $2n$ bits where $n$ refers to the block size. Note that the input does not only consist of the message $M$ to secure, but also comprises the nonce $N$ and the associated data $A$. By considering a 128-bit block cipher (e.g. AES), it means that we will be restricted to 256-bit (i.e. 32 bytes) inputs. Two proposals came out of research: Manx1 and Manx2 (as reference to Manx cats which have very short tails).

Encode-then-Encipher

We used the Encode-then-Encipher (EtE) scheme, introduced by Bellare and Rogaway, as a starting point. It can be seen as the most primitive AE mode, and works as follows in its single-block version. Given a nonce $N$, associated data $A$ and message $M$, it encrypts under key $K$ the input block $N \,||\, f(A, M)$ where $f$ is an injective encoding function. The verification of the ciphertext $C = E_K(N\,||\,f(A,M))$ is done by checking whether the most significant bits of $E^{-1}_K(C)$ equal $N$. While ultimately simple, the entire input cannot exceed $n$ which does not fit our requirements.

Manx1

Manx1 can be seen as an extension of EtE when combined with the XOR-Encrypt-XOR (XEX) mode. It allows to extend the input space from the above solution since a part of the encoding of $N$ and $A$ is used to generate a mask to be added to the input and output of EtE. EtE is now in charge of processing the message along with the remaining part of the encoding.

Can be instantiated with nonces larger than $n$ (useful for random nonce generation).
$|M|$ cannot exceed $n-\tau$ where $\tau$ refers to the authenticity security level in bits: it means that we are bounded to $\approx$ 64-bit messages for 64-bit authenticity security with a 128-bit block cipher.
The two block cipher calls are serial (it cannot take advantage of parallel implementations).

Manx2

Our other proposal Manx2 addresses the two drawbacks listed above by considering two distinct cases: tiny and short inputs. When processing tiny inputs (whose size does not exceed $n-2$) it mainly consists in EtE with a 2-bit domain separator. When processing short inputs, Manx2 produces two $n$-bit ciphertext blocks $C[1] = E_K\big(N \, || \, 0 \,||\, A \,||\, M[1]\big)$ and $C[2] = E_K\big(N \, || \, 1\,||\, \mathsf{pad}(M[2])\big)$. The verification consists in checking whether the $|N|$ most significant bits of $E^{-1}_K(C[1])$ and $E^{-1}_K(C[2])$ are the same, and if it leads to the right domain separator bits and associated data.

|M| is now up to $2n - 2|N| - |A| - 4$: when A is empty and N is 8-byte long, Manx2 can encrypt a plaintext about $n$ bits, which is not possible with Manx1.
The two block cipher calls can be computed in parallel.
For short messages, knowledge of the nonce is not necessary for the decryption: allows to save some bandwidth which is highly appreciable in the case of constrainted IoT networks.

Benchmark on microcontrollers

To assess the benefits of the Manx AE modes, we ran benchmarks on a 8-bit AVR ATmega128 and 32-bit ARM Cortex-M4 processors. As a point of comparison, we considered the GCM, CCM, and COFB operating modes, with AES-128 as the underlying block cipher. Manx-AES outperforms all of them up to 240% depending on the setting (i.e. input size) and computing platform. It also appears that Manx2 achieve better performance than Manx1, which makes it the favorite candidate between the two proposals. See Table 1 in our paper for more details.

Possible future improvements

As future work, we plan to extend the security analysis of the Manx AE modes to nonce-misuse cases and add more benchmarks with other block ciphers (e.g. GIFT-128). Hopefully this will be discussed in another blogpost!