# HyENA AE Mode

HyENA (Hybrid feedback-based ENcryption with Authentication) mode of operation provides nonce-based authenticated encryption with associated data (AEAD). Traditionally, block cipher based sequential encryption modes use one of the following methods, namely plaintext feedback (PFB), ciphertext feedback (CFB), or output feedback (OFB). HyENA is a hybrid feedback based mode (HyFB) which is actually combined feedback of the message and the ciphertext block. Here the block cipher input is partially ciphertext feedback and partially plaintext feedback. HyENA primarily focuses on the hardware implementation cost. We aspire to minimize the state size overhead beyond the block cipher state (including the key schedule), and reduce the XOR counts. HyENA has several interesting features, most notably, it is single-pass (one block cipher call per data block), inverse-free (no need for block cipher decryption), and has very low state size approx. 1.5n + k for block cipher with n-bit block and k-bit key. All these features are quite desirable in NIST lightweight standardization process. We instantiate HyENA with an ultra-lightweight block cipher GIFT-128^{[2]}.

## Features

Here, we summarize the salient features and design rationale of HyENA.1. Optimal: HyENA requires (a + m + 1) many block cipher invocations to process an a block associated-data and m block message. This is the optimal number of non-linear primitive calls required for any nonce based authenticated encryption. This feature is particularly important for short messages from the perspective of energy consumption, which is directly dependent upon the number of non-linear 1 primitive calls.

2. Inverse-free: HyENA is an inverse-free authenticated encryption algorithm. Both encryption and verified decryption of the algorithm do not require any decryption call to the underlying block cipher. This reduces the overall hardware footprint significantly, especially in the combined encryption-decryption implementations.

3. Low State-size: HyENA requires a state size as low as 3n/2-bits along with the key state. For any nonce based constructions, this can be shown to be the optimal state size. COFB^{[1]} is the only other existing AE mode that has a state size of 3n/2-bits.

4. Low XOR-count: To achieve optimal, inverse-free authenticated ciphers with low state, a possible direction is to use the combined feedback approach where (i) the previous block cipher output is XORed with the plaintext to generate the ciphertext, and (ii) the next block cipher input is defined as the XOR of the plaintext with some linear function of the previous block cipher output. This technique was used in the popular authenticated encryption mode COFB [4]. It is easy to see that such combined feedback function require at least 2n-bits of XOR operations (when operated on n-bit data), along with some additional XOR operations required for the linear function mentioned above. On the contrary, in HyENA, we use the concept of hybrid feedback or HyFB, where the block cipher input is defined partially via ciphertext feedback and partially via plaintext feedback. This reduces the number of the XOR operations to only n-bits.

## Mode Specification

HyENA is a Rate-1 feedback based mode such that both the associate data A and the message M (both are 10 padded to full blocks) are divided into n-bit blocks and then each of the data blocks are processed sequentially by the block cipher. The feedback to the block cipher input are computed using combined feedback and partial masking with nonce based secret mask. After all the blocks of A and M are processed an additional block cipher call generates the tag. The structure of HyENA is more or less same as COFB except the underlying combined feedback function. We now describe HyENA with a concrete example. Lets assume that we are using the GIFT blockcipher with n = 128 and k =128. The HyENA authenticated encryption mode receives a k-bit encryption key K, an r-bit nonce N with r = 96 (authenticated but not encrypted), an arbitrary length associated data A (authenticated but not encrypted), and an arbitrary length message M (both authenticated and encrypted) as inputs, and returns a ciphertext C with |C| = |M| and a t-bit tag T with t = 128. The decryption algorithm receives K, A, N, C, T as inputs and returns M if C corresponds to T, otherwise rejects. The mode is depicted in Figure 1. The underlying feedback function processes full or partial data blocks in a different manner. Note that, all the blocks except the last one are processed with a full block feedback function and the last one with a partial block feedback function. The feedback function is illustrated in Figure 2.

## Security of HyENA

We provide a brief provable security argument for HyENA namely the security of HyENA against generic attacks (assuming the underlying block cipher is ideal, i.e. random permutation). The possible attack strategies along with a rough lower bound estimate on the data and time complexity of each strategy is given. In the following discussion:

_{e}and D

_{v}to account for the data complexity of encryption and decryption/verification queries.

**Privacy of HyENA:**

**Block matching in the Same Encryption Query-**If the two blocks belong to the same query, then they must have different indices and hence we can again bound the probability of full state collision by at most D

_{e}

^{2}/2

^{n}(for the upper part of the internal state, we have n/2-bit entropy from the second ciphertext block and for the lower part we have n/2-bit entropy from Δ and overall we have D

_{e}

^{2}internal blocks).

**Block matching in the Two Different Encryption Queries-**In this case, the two blocks belong to different query, in which case the nonce is different, and we can bound the probability of full state collisions, which is roughly D

_{e}

^{2}/2

^{n}.

**Integrity Security of HyENA:**

**Guessing a valid Tag-**: The adversary can simply guess the tag in each of the decryption queries. The probability of correct guess is roughly D

_{v}/2

^{n}.

**Block matching between an Encryption Query and a Decryption Query-**Some decryption query block might match some encryption query block. Now depending upon the type of encryption query block the adversary can have two approaches. In one approach, a decryption block mathches with a nonce queried during encryption queries. More formally, the decryption block matches with the initial internal state for an encryption query. For this case, the probability for this match is bounded by D

_{v}/2

^{n/2}. In the other approach the adversary can match a decryption block with a non-initial internal state for an encryption query. The probablity for this match is bounded by n/2D

_{v}/2

^{n/2}. The factor n comes from the possibility of n-multicollision in the lower part of the internal state during the encryption queries.

Below in Table, we provide the provable security bounds for the HyENA mode with n = 128 and assuming the adversary is nonce respecting (i.e, the adversary does not repeat nonce during encryption queries under the same key) and the underlying block cipher is a PRP. We remark that the security may even hold when the public nonce value is sampled uniformly at random from the nonce space for each encryption query. The table below summerizes the security claims for HyENA. The data and time limits indicate the amount of data and time required to make the attack advantage close to 1.

Mode | Privacy | Authenticity | ||
---|---|---|---|---|

Time | Data (in bytes) | Time | Data (in bytes) | |

HyENA | 2^{128} |
2^{64} |
2^{128} |
2^{58} |

Cryptanalysis of GIFT:

Several cryptanalytic results of GIFT can be found at ^{[2]} .

## References

**^**Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu and Mridul Nandi. Blockcipher-based Authenticated Encryption: How Small Can We Go?In Cryptographic Hardware and Embedded Systems - CHES 2017 - 19th International Conference, Taipei, Taiwan, September 25-28, 2017, Proceedings, pages 277–298, 2017.**^**Subhadeep Banik, Sumit Kumar Pandey, Thomas Peyrin, Yu Sasaki, Siang Meng Sim, and Yosuke Todo. GIFT: A small present - towards reaching the limit of lightweight encryption. In Cryptographic Hardware and Embedded Systems - CHES 2017 - 19th International Conference, Taipei, Taiwan, September 25-28, 2017, Proceedings, pages 321–345, 2017.