# 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.

## 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

### 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

1. ^ Morris Dworkin. Recommendation for Block Cipher Modes of Operation – Methods and Techniques. In NIST Special Publication 800-38A, National Institute of Standards and Technology, U. S. Department of Commerce (2001).
2. ^ Avik Chakraborti, Nilanjan Datta, Mridul Nandi, Kan Yasuda. Beetle Family of Lightweight and Secure Authenticated Encryption Ciphers. In IACR Trans. Cryptogr. Hardw. Embed. Syst. 2018(2) (2018) 218-241.
3. ^ Avik Chakraborti, Nilanjan Datta, Mridul Nandi, Kan Yasuda. Beetle Family of Lightweight and Secure Authenticated Encryption Ciphers. In IACR Cryptology ePrint Archive 2018 (2018) 805.
4. ^ NIST FIPS 197. Advanced Encryption Standard (AES). In NIST Federal Information Processing Standards Publication 197, National Institute of Standards and Technology, U. S. Department of Commerce (2001).
5. ^ Ray Beaulieu, Douglas Shors, Jason Smith, Stefan Treatman-Clark, Bryan Weeks, Louis Wingers. The Simon and Speck Block Ciphers on AVR 8-bit Microcontrollers. In LightSec 2014 (2014) 3-20.
6. ^ Ray Beaulieu, Douglas Shors, Jason Smith, Stefan Treatman-Clark, Bryan Weeks, Louis Wingers. SIMON and SPECK: Block Ciphers for the Internet of Things. In IACR Cryptology ePrint Archive 2015 (2015) 585.
7. ^ Bonwook Koo, Dongyounh Roh, Hyonjin Kim, Younghoon Jung, Donggeon Lee, Daesung Kwon. CHAM: A Family of Lightweight Block Ciphers for Resource-Constrained Devices. In ICISC 2017 (2017) 3-25.
8. ^ Mustafa Khairallah. Weak Keys in the Rekeying Paradigm: Attacks on COMET-128 and mixFeed. In Cryptology ePrint Archive 2019 (2019) 888.