GIFT-COFB Authenticated Encryption

GIFT-COFB instantiates the COFB (COmbined FeedBack) block cipher based AEAD mode with the GIFT block cipher.GIFT-COFB primarily focuses on the hardware implementation size. Here, we consider the overhead in size, thus the state memory size beyond the underlying block cipher itself (including the key schedule) is the criteria we want to minimize, which is particularly relevant for hardware implementation. An initial version of GIFT-COFB was presented in[1][2] and this latest version of GIFT-COFB is a minor modification over the original COFB mode.


Features

1. Block cipher based AE mode with high rate but with small memory: GIFT-COFB can be implemented with a very low state size of only 1.5n+k (n be the block cipher state size and k be the key length) as well as it achieves the optimal rate of 1.

2. High Security Bound: Use of combined feedback uplifts the security level. The bound increased to almost birthday bound.

3. Highly Flexible Mode: GIFT-COFB achieves high Flexibility. It is easy to fit any block cipher into this structure. This depicts that, when used with lighter block ciphers, it consumes lower hardware footprints.

4. Inverse-Free: GIFT-COFB is an inverse-free authenticated encryption algorithm. Both encryption and decryption algorithms do not require any decryption call to the underlying block cipher. This significantly reduces the overall hardware footprint in combined encryption-decryption implementations.

5. Low Overhead: Apart from the block cipher call it requires just 5n/2-bit XOR per block of data + 1-bit right rotation of an n/4-bit state, which seems to be a very small overhead.

6. Low number of block cipher calls: GIFT-COFB requires only a+m+1 many primitive invocations to process an a block associateddata and an m block message.

7. Short message Efficiency :  The optimality on the number of calls and low overhead help it to get very high performance for short messages.

GIFT-COFB Specification

GIFT-COFB is a block cipher based AEAD design that uses GIFT-128 as the underlying blockcipher. GIFT-COFB receives an (1) 128-bit encryption key K, (2) an 128-bit nonce N, (3) an associated data A of arbitrary length, (4) and a message M of arbitrary length as inputs, and returns a (5) ciphertext C of same length as that of the message, and (6) an 128-bit tag T. Below is the figure for the GIFT-COFB mode.

GIFT-COFB for a associated data blocks and m message blocks

GIFT Block Cipher

In this design, we use the 128-bit block cipher version of GIFT and the details are given in[3].


Recommended Instantiations

We propose a construction GIFT-COFB with the underlying block cipher as the only parameter. The block cipher can be chosen by the following recommendation.

  • n: Length of the block cipher state in bits. The recommended choice is n = 128.
  • τ : Length of the tag in bits. The recommended choice is τ = 128.
  • Block cipher E: The recommended choice of E is the block cipher GIFT-128.
  • Rationale

    1. Choice of the Mode: GIFT-COFB is a block cipher based authenticated encryption scheme that uses GIFT-128 as the underlying block cipher and GIFT-COFB can be viewed as an efficient integration of the COFB mode and GIFT-128 block cipher. GIFT-128 maintains an 128-bit state and 128-bit key. To be precise, GIFT is a family of block ciphers parametrized by the state size and the key size and all the members of this family are lightweight and can be efficiently deployed on lightweight applications. COFB mode on the other hand, computes of "COmbined FeedBack" (of block cipher output and data block) to uplift the security level. This actually helps us to design a scheme with low state size and eventually to have a low state implementation. This technique actually resist the attacker to control the input block and next block cipher input simultaneously. Overall, a combination of GIFT and COFB can be considered to be one of the most efficient lightweight, low state block cipher based AEAD construction.

    2. Choice of the block cipher: GIFT is considered to be one of the lightest design existing in the literature. It is denoted as "Small PRESENT" as the design rationale of GIFT follows that of PRESENT[4] . However, GIFT has got rid of several well known weaknesses existing in PRESENT with regards to linear cryptanalysis. Overall GIFT promises much increased efficiency (both lighter and faster) over PRESENT. GIFT is a very simple design that outperforms even SIMON and SKINNY for round based implementations. It consists of very simple operations such that the total hardware footprint is almost consumed by the underlying and the cipher storage. The design is somewhat "optimal" as a weaker S-box (than GIFT S-box) would lead to a weaker design. The linear layer is completely free for a round-based implementation in hardware (consisting of simply bit-wiring) and the constants are generated thanks to a very lightweight LFSR. The key schedule is also very 21 light, simply consisting of shifts.

    Security of GIFT-COFB

    Security claims for GIFT-COFB are summarized in the table below.
    Construction State Size (bits) IND-CPA (bits) INT-CTXT (bits)
    GIFT-COFB 192 (excluding key state) 64 58

    We provide a brief provable security argument for GIFT-COFB namely the security of GIFT-COFB 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 De and Dv 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 GIFT-COFB:
    In privacy attacks the adversary is concerned with distinguishing the GIFT-COFB 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 De2/2n (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 De2 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 De2/2n.
    • Integrity Security of GIFT-COFB:
    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 Dv/2n.
  • 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 Dv/2n/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/2Dv/2n/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 GIFT-COFB 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 GIFT-COFB. The data and time limits indicate the amount of data and time required to make the attack advantage close to 1.

    Security Analysis of GIFT: The security analysis of GIFT-128 is provided in Section 4 of [5]. Here we highlight several important features.

  • Differential cryptanalysis: Zhu et al. applied the mixed-integer-linear-programming based differential characteristic search method for GIFT-128 and found an 18-round differential characteristic with probability 2-109 [7] , which was further extended to a 23-round key recovery attack with complexity (Data, T ime, Memory) = (2120, 2120, 280). We expect that full (40) rounds are secure against differential cryptanalysis.
  • Linear cryptanalysis: GIFT-128 has a 9-round linear hull effect of 2-45.99, which means that we would need around 27 rounds to achieve correlation potentially lower than 2-128. Therefore, we expect that 40-round GIFT-128 is enough to resist against linear cryptanalysis.
  • Integral attacks: The lightweight 4-bit S-box in GIFT may allow efficient integral attacks. The bit-based division property is evaluated against GIFT128 by the designers, which detected a 11-round integral distinguisher.
  • Meet-in-the-middle attacks: Meet-in-the-middle attack exploits the property that a part of key does not appear during a certain number of rounds. The designers and the follow-up work by Sasaki[6] showed the attack against 15-rounds of GIFT-64 and mentioned the difficulty of applying it to GIFT-128 because of the larger ratio of the number of subkey bits to the entire key bits per round; each round uses 32 bits and 64 bits of keys per round in GIFT-64 and GIFT-128, respectively, while the entire key size is 128 bits for both.
  • Hardware Implementations

    The GIFT-COFB mode was designed with rate 1, that is every message block is processed only once. Such designs are not only beneficial for throughput, but also energy consumption. However the design does need to maintain an additional 64 bit state, which requires a 64-bit register to additionally included in any hardware circuit that implements it. Although this might not be energy efficient for short messages, in the long run GIFT-COFB performs excellently with respect to energy consumption. The GIFT block cipher was designed with a motivation for good performance on lightweight platforms. The roundkey additon for the cipher is over only half the state and the keyschedule being only a bit permutation does not require logic gates. These characteristics make the GIFT well suited for lightweight applications. In fact as reported in [3], among the block ciphers defined for 128-bit block size GIFT-128 has the lowest hardware footprint and very low energy consumption. Thus GIFT-COFB combines the best of both the advantages of the design ideologies. The figure below describes the component wise break up of different hardware components.
    Implementation results for GIFT-COFB is given below.
    Block Cipher Area (GE) Power (μ W) Energy (nJ)
    A M A M A M
    0 BYTE 16 BYTE 0 BYTE 16 BYTE 0 BYTE 16 BYTE
    GIFT-128 3927 156.3 1.31 2.00 2.69

    Software Implementations

    Results will be given later.

    References

    1. ^ 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
    2. ^ Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, and Mridul Nandi. Blockcipher-based authenticated encryption: How small can we go? To appear at the Journal of Cryptology.
    3. ^ 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.
    4. ^ Andrey Bogdanov, Lars R. Knudsen, Gregor Leander, Christof Paar, Axel Poschmann, Matthew J. B. Robshaw, Yannick Seurin, and C. Vikkelsoe. PRESENT: An Ultra-Lightweight Block Cipher. In CHES 2007, pages 450-466, 2007.
    5. ^ Subhadeep Banik, Sumit Kumar Pandey, Thomas Peyrin, Siang Meng Sim, Yosuke Todo, and Yu Sasaki. Gift: A small present. Cryptology ePrint Archive, Report 2017/622, 2017. https://eprint.iacr.org/2017/622.
    6. ^ Yu Sasaki. Integer linear programming for three-subset meet-in-the-middle attacks: Application to gift. In Atsuo Inomata and Kan Yasuda, editors, Advances in Information and Computer Security, pages 227-243, Cham, 2018. Springer International Publishing.
    7. ^ Baoyu Zhu, Xiaoyang Dong, and Hongbo Yu. Milp-based differential attack on round-reduced gift. Cryptology ePrint Archive, Report 2018/390, 2018. https://eprint.iacr.org/2018/390.