HyENA AE ModeHyENA (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.
FeaturesHere, 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 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 . 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.
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:
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:
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.
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.
|Time||Data (in bytes)||Time||Data (in bytes)|
Cryptanalysis of GIFT:
Several cryptanalytic results of GIFT can be found at  .
- 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.