# 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: A**part 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 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.

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

_{e}and D

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

**Privacy of GIFT-COFB:**

**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 GIFT-COFB:**

**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 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) = (2

^{120}, 2

^{120}, 2

^{80}). 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

**^**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**^**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.**^**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.**^**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.**^**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.**^**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.**^**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.