COMET: COunter Mode Encryption with authentication Tag

COunter Mode Encryption with authentication Tag, or COMET in abbreviation, is a block cipher mode of operation that provides authenticated encryption with associated data functionality. At a very high level, it can be viewed as a mixture of CTR^[1] and Beetle^[2][3] modes of operation. Currently, COMET is among the round 1 candidates of NIST Lightweight Cryptography Standardization Project.

Features

Some of the standout features of COMET are as follows:

• 1. Small state size: COMET is designed to achieve minimum state size. It achieves minimal state size, in the sense that the only state it requires (apart from some auxiliary bits) is used for the block cipher, i.e. $(n+\kappa)$-bit state. We believe that this is the smallest possible state size for nonce-based AEAD schemes with security level and data processing rate comparable to that of COMET.
• 2. Inverse free: COMET is inverse free, i.e. it does not require the decryption algorithm of the underlying block cipher. This helps in reducing the hardware and software footprints for combined implementations.
• 3. Efficiency: COMET is nonce-based, which helps in keeping the design single pass. This is beneficial in both hardware and software. The block ciphers in different variants of COMET are chosen in such a way that the overall instantiations allow for efficient implementation in their respective categories.
• 4. Dynamic key updation: In COMET no two blocks share the same key non-trivially. In other words each block is processed with a distinct key with overwhelming probability. This helps in mitigating certain side-channel attacks, as the adversary gains very little side-channel information due to the often change in key.
• 5. Design simplicity: The design of COMET is extremely simple. Apart from the block cipher invocation, it only requires shift and XOR operations.

Mode of Operation

Parameters:

The COMET mode of operation for authentication encryption is primarily parametrized by the block size $n$ of the underlying block cipher, where $n \in \{64,128\}$. We simply write COMET-$n$ to denote COMET with block size $n$. The secondary parameters of COMET include, the key size $\kappa$, nonce size $r$, and tag size $t$. These secondary parameters are set according to the value of $n$ in the following manner.

• • COMET-$128$: Here $\kappa=128$, $r=128$ and $t=128$.
• • COMET-$64$: Here $\kappa=128$, $r=120$ and $t=64$.

Note that all values are given in bits. Apart from the above mentioned parameters, COMET sets some additional parameters, which are described in the formal specification.

Encryption/Decryption Process:

Figure 1 illustrates the major components of the encryption/decryption process. As mentioned before, COMET is an amalgamation of CTR and Beetle modes of operation. The basic data processing flow is quite similar to the Beetle mode, where an $(n+\kappa)$-bit permutation is replaced with a block cipher with $n$-bit block and $\kappa$-bit key. The key bits, which can also be viewed as the capacity of this makeshift permutation, are updated in such a way that no two block share the same key non-trivially. This is done by encoding each block index within its key, which is somewhat inspired from the CTR mode. The complete specification is available here.

Figure 1: Schematic diagram of different modules used in the encryption algorithm of COMET for non empty associated data and plaintext. From top to bottom and left to right, we have the following modules: nonce processing in COMET-$128$; nonce processing in COMET-$64$; tag generation; associated data processing; and plaintext processing. See the formal specification file for more detailed description.

Instantiations

COMET is instantiated with three block ciphers, AES^[4], Speck^[5][6], and CHAM^[7]. The instantiations corresponding to AES and Speck are specifically oriented towards microcontroller applications, and the CHAM based instantiations are oriented towards hardware implementations.

Software-oriented Instances:

• 1. COMET-$128$_AES-$128/128$: This version uses AES-$128$ block cipher in COMET-$128$ mode. [Primary Recommendation]
• 2. COMET-$128$_Speck-$64/128$: This version uses Speck-$64/128$ block cipher in COMET-$64$ mode.

Hardware-oriented Instances:

• 1. COMET-$128$_CHAM-$128/128$: This version uses CHAM-$128/128$ block cipher in COMET-$128$ mode.
• 2. COMET-$128$_CHAM-$64/128$: This version uses CHAM-$64/128$ block cipher in COMET-$64$ mode.

Rationale

The primary motivation behind COMET is the design of a lightweight (in hardware/software state/memory footprint) yet adequately efficient and secure AEAD mode of operation for block ciphers. Particularly, our goal is to keep minimal state size, and then aim for better performance and security. For this we start with the design paradigm of Beetle, a sponge variant, and think of ways to replace the internal permutation call with a block cipher call. For $ b \geq 1 $, suppose, $ P: \{0,1\}^b \to \{0,1\}^b $ is a permutation over $ \{0,1\}^b $. Now, for $ b = n + \kappa $ and $ (x,z) \in \{0,1\}^n \times \{0,1\}^\kappa $, we define $ P(x,z) := (E(z,x),\varphi(z)) $ where $ E $ is a block cipher with $ n $-bit block size and $ \kappa $-bit key size, and $ \varphi $ is a permutation over $ \{0,1\}^\kappa $. Now if $ \varphi $ is light and efficient then one can expect that this definition of $ P $ will be more efficient then a larger permutation over $ \{0,1\}^{b} $, as it may require more rounds to mix $ b $ bits. In order to keep $ \varphi $ light we use an encoding of the block position (motivated by the CTR mode) to permute and generate the next block key. Combining the two elements: state size reduction following Beetle paradigm, and efficient and light key updation using encoding of block position following CTR paradigm, we get a mode with a small state ($ (n+\kappa) $ bits) and high security ($ 2^n $ data and $ 2^\kappa $ time complexity).

Nonce Usage:

COMET makes a single pass over the input associated data and plaintext to reduce the latency in producing the ciphertext. In general, single pass AEAD's use a non-repeating nonce to generate a (possibly uniform) random state for each encryption query. COMET also follows the same paradigm and is secure in \textit{nonce respecting} scenario, i.e. each nonce should be used to encrypt a single message in the lifetime of the key.

Choice of Nonce-based Initialization:

COMET employs nonce-based initialization (see Figure 1) at the start to generate a random state (initial key and input). This is done while restricting the number of block cipher calls to 1, so as to keep minimal overhead. Depending upon the variants, namely, COMET-$128$ and COMET-$64$, we employ two different approaches in this step:

• State Derivation in COMET-$128$: In this case the input nonce is encrypted with the master key to get a nonce derived key and the master key is used as the initial input. This helps in two respects: first, the security of the mode can be shown in more relaxed security models \cite{GueronL17}; second, the underlying block cipher is only required to be related-key secure under without replacement key derivation.
• State Derivation in COMET-$64$: In this case, the block size is smaller than the nonce size, which makes it difficult to process the nonce in one go. Since the focus of COMET-$64$ is more towards, state size reduction, we sacrifice a little bit in terms of security. Here the master key is XORed with the input nonce to generate the initial key and the encryption of $ 0 $ under master key is used as the initial input.

Choice of $ \varphi $ Function:

We need that the $ \varphi $ function should have a large period, so that within an encryption query there is no collision in the key input of each block. Multiplication by primitive element $ \alpha $ has this property. In this case two block keys can be same only if the input length goes beyond $ 2^{64} $. So we choose $ \alpha $ multiplication as our choice of $ \varphi $. Note that, it is also expected to resist the existing related-key attack strategies based on key difference.

Choice of $ \varrho $ Function:

Like Beetle, we need that both $ \varrho(x) $ and $ \varrho(x) \oplus x $ should be invertible for all $ x $. We choose a variant of the $ \varrho $ function used in Beetle, in order to reduce the number of shift and swap operations.

Security

Table 1: Security claims for COMET family of AEAD.

Security of the COMET mode of operation:

Table 1 summarized the security claims for concrete recommendations based on the COMET mode of operation. The security claims hold under nonce-respecting model, i.e., the adversary cannot repeat nonce inputs in encryption queries. The security claims are based on full round AES-$128/128$, CHAM-$128/128$, CHAM-$64/128$, Speck-$64/128$, and we do not claim any security for COMET with round-reduced variants of these block ciphers.

Schemes based on COMET-$128$ are secure, in confidentiality and integrity sense while data complexity is less than $2^{64}$ bytes and time complexity is less than $2^{119}$.

Schemes based on COMET-$64$ are secure, in confidentiality sense while data complexity is less than $2^{64}$ bytes and time complexity is less than $2^{119}$; and in integrity sense while data complexity is less than $2^{45}$ bytes and time complexity is less than $2^{112}$.

Security of the underlying block ciphers:

All the block ciphers used in the COMET submission are well-known and fairly well-studied. Since, the COMET mode of operation is based on rekeying, we have carefully chosen block ciphers with a good amount of published related-key analysis which further improves the confidence on the security of these block ciphers. Some relevant cryptanalysis papers are mentioned in the specification file available here.

Third Party Analyses:

A summary of all published third party analyses on COMET is given below.

• 1. ePrint Report 2019/888: Khairallah^[8] claims a forgery attack on COMET-$128$ mode in roughly $2^{68}$ bytes data complexity and negligible time complexity. The same attack is extended to recover the key in roughly $2^{68}$ bytes data complexity and $2^{65}$ time complexity. This attack does not violate the security of COMET-$128$ as it breaches the data complexity limit.

References