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.

Figure 1: HyENA Mode of Authenticated Encryption for a associated data blocks and m message blocks

Full Block Process

Partial Block Process

Figure 2: Hybrid Feedback Function used in HyENA

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:

D denotes the total (both encryption and decryption) data complexity. This parameter quantifies the online resource requirements, and includes the total number of blocks (among all messages and associated data) processed through the underlying block cipher for a fixed master key. We use D_e and D_v to account for the data complexity of encryption and decryption/verification queries.

T denotes the time complexity. This parameter quantifies the offline resource requirements, and includes the total time required to process the offline evaluations of the underlying block cipher. Since one call of the block cipher can be assumed to take a constant amount of time, we generally take T as the total number of offline calls to the block cipher.

Privacy of HyENA:

In privacy attacks the adversary is concerned with distinguishing the HyENA mode with an ideal authenticated encryption scheme, by exploiting access to the encryption algorithm. In other words, we are interested in the usual IND-CPA security notion. The adversary can distinguish the mode from ideal if there is no randomness in some ciphertext (or tag) blocks. We follow the approach to match two block cipher inputs in the same encryption query or between two different encryption queries (with different nonces). For a pair of distinct encryption query blocks, the internal states matches. Then, the block that appears later will definitely have non-random behavior, though the adversary may not be able to detect it. In any case it is sufficient to bound the occurrence of this event. This is possible in the following ways:

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ⁿ (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² 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ⁿ.

Integrity Security of HyENA:

Here the adversary has to generate fresh ciphertext-tag pair (not obtained through encryption queries). To obtain a valid forgery, the adversary can take any of the following approaches.

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

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	2128	264	2128	258

Cryptanalysis of GIFT:

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

References