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 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.
Updates
The versions can be obtained from [14], [15], and [16]- Performance results and analysis results have been added.
- A hash function proposal has been been added.
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:
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:
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.
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.
Previous Third Party Security Analyses of GIFT:
Latest Third Party Security Analyses of GIFT: Regarding GIFT-128 block cipher, several third-party security evaluations have continued to be published. With respect to linear attacks, the number of attacked rounds has increased significantly, but this does not change the fact that differential cryptanalysis remains more effective against GIFT-128. These attacks were discovered using automated evaluation tools and research on more efficient tools for the GIFT network have also been presented[17]. No progress has been made on differential cryptanalysis, and no new (unknown) cryptanalysis method has been discovered. This is a strong evidence of the reliability of GIFT-128. We give below some comments on a few references.
We recall that GIFT-128 has 40 rounds, while the best known attack can only reach 27 rounds (which does not apply to GIFT-COFB due to the data limitation, etc.). This leaves a very ample security margin.
Below, we summerize all the existing attacks against GIFT.In the Table below, Rounds with asterisk (*) are optimal results. SK – single-key, RK – related-key, LC – linear cryptanalysis, DC – differential cryptanalysis. All the other references of the attacks are available in Table 1 of [5].Setting |
Rounds |
Approach |
Prob. |
Time |
Data |
Mem. |
---|---|---|---|---|---|---|
Distinguisher | ||||||
SK | 11 | Integral | 1 | - | 2127 | - |
SK | 11* | Integral | 1 | - | 2127 | - |
SK | 9* | LC | 2-44 |
- | - | - |
SK | 10* | LC | 2-52 | - | - | - |
SK | 15 | LC | 2-109 | - | - | - |
SK | 16 | LC | 2-122 | - | - | - |
SK |
19 | LC | 2-117.43 | - | - | - |
SK | 19 | LC | 2-123.11 | - | - | - |
SK | 9* | DC | 2-45.4 | - | - | - |
SK | 10* | DC | 2-49.4 | - | - | - |
SK | 11* | DC | 2-54.4 | - | - | - |
SK | 12* | DC | 2-60.4 | - | - | - |
SK | 13* | DC | 2-67.8 | - | - | - |
SK | 14* | DC | 2-79 | - | - | - |
SK | 15* | DC | 2-85.415 | - | - | - |
SK | 16* | DC | 2-90.415 | - | - | - |
SK | 17* | DC | 2-96.415 | - | - | - |
SK | 18 | DC | 2-109 | - | - | - |
SK | 18* | DC | 2-103.415 | - | - | - |
SK | 19 | DC | 2-110.83 | - | - | - |
SK | 20 | DC | 2-121.415 | - | - | - |
SK | 20 | DC | 2-120.245 | - | - | - |
SK | 20 | DC | 2-121.813 | - | - | - |
SK | 21 | DC | 2-126.4 | - | - | - |
RK | 7 | DC | 2-15.83 | - | - | - |
RK | 10 | DC | 2-72.66 | - | - | - |
RK | 19 | Boomerang | 2-121.2 | - | - | - |
RK | 19 | Boomerang | 2-109.626 | - | - | - |
Key Recovery | ||||||
SK | 20 | LC | - | 2112.28 | 2126 | 265 |
SK | 22 | LC | - | 2117 | 2117 | 278 |
SK | 24 | LC | - | 2124.45 | 2122.55 | 2105 |
SK | 25 | LC | - | 2124.75 | 2126.77 | 296 |
SK | 22 | DC | - | 2114 | 2114 | 253 |
SK | 26 | DC | - | 2124.415 | 2109 | 2109 |
SK | 26 | DC | - | 2123.245 | 2123.245 | 2109 |
SK | 27 | DC | - | 2124.83 | 2123.53 | 280 |
RK | 21 | Boomerang | - | 2126.6 | 2126.6 | 2126.6 |
RK | 22 | Boomerang | - | 2112.63 | 2112.63 | 2112.63 |
RK | 23 | Rectangle | - | 2126.89 | 2112.31 | 2121.31 |
The provable security aspects of GIFT-COFB and its variants have been studied and updated since the last revision of our specification document. We list the relevant works below.
In addition to conventional cryptanalyses, GIFT-COFB receives third-party evaluation from different viewpoints.
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. Below, we provide the existing implementation results both on ASIC and FPGA.
ASIC Results
We first provide our first ASIC implementation for GIFT-COFB.
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 |
Datapath | Area | Latency | Power | Energy | Reference |
|
---|---|---|---|---|---|---|
Bits | GE | Cycles | µW | nJ | ||
SUNDAE-GIFT | 1 | 1201 | 92544 | 55.48 | 513.4 | [30] |
SAEAES | 1 | 1350 | 24448 | 84.47 | 206.5 | [30] |
ROMULUS | 1 | 1778 | 55431 | 82.28 | 456.1 | [30] |
SKINNY-AEAD | 1 | 3589 | 72960 | 143.7 | 1048 | [30] |
GIFT-COFB-SER-S | 1 | 1443 | 54784 | 50.11 | 275.8 | [31] |
GIFT-COFB-SER-F | 1 | 1485 | 51328 | 62.15 | 319.8 | [31] |
GIFT-COFB-SER-TI | 1 | 3384 | 51328 | 158.1 | 813.5 | [31] |
- FPGA Results
Variants |
Implementation Features |
# LUTs |
#FFs |
# Slices |
MHz |
Encryption AD+PT Throughput for Long Messages (Mbps) |
Reference |
---|---|---|---|---|---|---|---|
GIFT-COFB-VT-v1 | Basic Iterative | 1041 | 604 | 321 | 675 | 733.3 | [32] |
GIFT-COFB-GMU-v1 | Basic Iterative | 1223 | 887 | 379 | 263 | 821.1 | |
GIFT-COFB-GMU-v2 | 2 × Unrolled | 1,380 | 880 | 417 | 261 | 1590.9 | |
GIFT-COFB-GMU-v3 | 4 × Unrolled | 1,641 | 882 | 499 | 249 | 2897.5 | |
GIFT-COFB-GMU-v4 | 5 × Unrolled | 1,730 | 873 | 539 | 213 | 3029.3 | |
GIFT-COFB-GMU-v5 | 8 × Unrolled | 2,051 | 873 | 655 | 137 | 2922.7 | |
GIFT-COFB-GMU-v6 | 10 × Unrolled | 2363 | 872 | 696 | 110 | 2816.0 |
Software Implementations
The paper[9] adopts the fix-slicing strategy (will be presented at CHES 2020, software implementation codes can be found in[12]) to make a new representation of the GIFT-64 and GIFT-128 bit permutations that makes it efficient and simple to implement in software. This strategy indeed leads to very efficient one-block constant-time GIFT-128 implementations on 32-bit architectures such as ARM Cortex-M family of processors (79 cycles/ byte on ARM Cortex-M3), making GIFT-COFB one of the most efficient candidate according to microcontroller benchmarks[9] [11]. Using smaller architecture will not be an issue as we will actually save more operations comparatively, since part of the bit permutation can be done by proper unrolling and register scheduling. This is confirmed with 8-bit AVR benchmarks [10] [11] described below. Here GIFT-COFB is again ranked among the top candidates. Note that using exactly this implementation will also provide decent performance on recent high-end processors (and excellent performances if parallel computations of GIFT-COFB instances are considered and vector instructions are used).
Latest software implementation 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? Journal of Cryptology 2020 (vol 33(3), page 703-741), 2020.
- ^ 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, Avik Chakraborti, Akiko Inoue, Tetsu Iwata, Kazuhiko Minematsu, Mridul Nandi, Thomas Peyrin, Yu Sasaki, Siang Meng Sim, and Yosuke Todo. GIFT-COFB Final Round Updates. NIST LWC, Final Round Status Update, 2022. https://csrc.nist.gov/csrc/media/Projects/lightweight-cryptography/documents/finalist-round/status-updates/gift-cofb-update.pdf.
- ^ 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.
- ^ Alexandre Adomnicai, Zakaria Najm, and Thomas Peyrin. Fixslicing: A new GIFT representation. IACR Cryptol. ePrint Arch., 2020:412, 2020.
- ^ Sebastian Renner, Enrico Pozzobon, and Jürgen Mottok. NIST LWC Software Performance Benchmarks on Microcontrollers, 2020.
- ^ Rhys Weatherley. Lightweight Cryptography Primitives, 2020.
- ^ https://github.com/aadomn/gift
- ^ https://github.com/rweather/lightweight-crypto
- ^ Subhadeep Banik, Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, Mridul Nandi, Thomas Peyrin, Yu Sasaki, Siang Meng Sim, and Yosuke Todo. GIFT-COFB v1.0 Specification (NIST LWC First Round Submission). https://csrc.nist.gov/CSRC/media/Projects/Lightweight-Cryptography/documents/round-1/spec-doc/GIFT-COFB-spec.pdf.
- ^ Subhadeep Banik, Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, Mridul Nandi, Thomas Peyrin, Yu Sasaki, Siang Meng Sim, and Yosuke Todo. GIFT-COFB v1.0 Specification (NIST LWC Second Round Submission). https://csrc.nist.gov/CSRC/media/Projects/lightweight-cryptography/documents/round-2/spec-doc-rnd2/gift-cofb-spec-round2.pdf.
- ^ Subhadeep Banik, Avik Chakraborti, Tetsu Iwata, Kazuhiko Minematsu, Mridul Nandi, Thomas Peyrin, Yu Sasaki, Siang Meng Sim, and Yosuke Todo. GIFT-COFB v1.1 Specification (NIST LWC Final Round Submission). https://csrc.nist.gov/CSRC/media/Projects/lightweight-cryptography/documents/finalist-round/updated-spec-doc/gift-cofb-spec-final.pdf.
- ^ Seonggyeom Kim, Deukjo Hong, Jaechul Sung, and Seokhie Hong. Accelerating the Best Trail Search on AES-Like Ciphers. IACR ToSC 2022 (Vol 2, page 201-252). https://tosc.iacr.org/index.php/ToSC/article/view/9719/9247.
- ^ Ling Sun, Wei Wang, and Meiqin Wang. Addendum to Linear Cryptanalyses of Three AEADs with GIFT-128 as Underlying Primitives. IACR Cryptol. ePrint Arch., 2022:151, 2022.
- ^ Ling Sun, Wei Wang, and Meiqin Wang. Linear Cryptanalyses of Three AEADs withGIFT-128 as Underlying Primitives. IACR ToSC 2021 (Vol 2, page 199-221). https://tosc.iacr.org/index.php/ToSC/article/view/9719/9247.
- ^ CUI Yaxin, XU Hong, and QI Wenfeng. MILP-Based Linear Attacks on Round-Reduced GIFT. Chinese Journal of Electronics 2022 (Vol 31(1), page 89-98). https://tosc.iacr.org/index.php/ToSC/article/view/9719/9247.
- ^ Akram Khalesi and Zahra Ahmadian. Provably Minimum Data Complexity Integral Distinguisher Based on Conventional Division Property. IACR Cryptol. ePrint Arch., 2022:752, 2022.
- ^ Kai Hu, Thomas Peyrin, and Meiqin Wang. Finding All Impossible Differentials When Considering the DDT. IACR Cryptol. ePrint Arch., 2022:1034, 2022.
- ^ Anubhab Bakshi. Finding All Impossible Differentials When Considering the DDT. SECITC, 2020(page 41-54), 2020.
- ^ Mustafa Khairallah. Security of COFB against Chosen Ciphertext Attacks. IACR ToSC 2022 (Vol 1, page 138-157). https://tosc.iacr.org/index.php/ToSC/article/view/9719/9247.
-
^
Akiko Inoue, Kazuhiko Minematsu, and Tetsu Iwata. Analyzing the provable security bounds of
GIFT-COFB and photon-beetle. Fifth NIST Lightweight Cryptography Workshop
2022 (2022).
- ^ Akiko Inoue, Kazuhiko Minematsu, and Tetsu Iwata. Analyzing the provable security bounds of GIFT-COFB and photon-beetle. ACNS 2022 (vol 13269, page 67-84), 2022. https://tosc.iacr.org/index.php/ToSC/article/view/9719/9247.
- ^ Subhadeep Banik, Avik Chakraborti, Akiko Inoue, Tetsu Iwata, Kazuhiko Minematsu, Mridul Nandi, Thomas Peyrin, Yu Sasaki, Siang Meng Sim, and Yosuke Todo. GIFT-COFB. IACR Cryptol. ePrint Arch., 2020:738, 2020.
- ^ Shuai Liu, Jie Guan, and Bin Hu. Fault attacks on authenticated encryption modes for GIFT. IET Inf. Secur. (Vol 16(1), page 51–63), 2022
- ^ Reshma Rajan, Rupam Kumar Roy, Diptakshi Sen, and Girish Mishra. Deep Learning based Differential Distinguisher for Lightweight Cipher gift-cofb. Machine Intelligence and Smart Systems 2022 (page 397-406). Springer Nature Singapore, Singapore 2022
- ^ Fatih Balli, Andrea Caforio, and Subhadeep Banik. The Area-Latency Symbiosis: Towards Improved Serial Encryption Circuits. IACR TCHES 2021 (Vol 1, page 239-278).
- ^ Andrea Caforio, Daniel Collins, Subhadeep Banik, and Francesco Regazzoni. A Small GIFT-COFB: Lightweight Bit-Serial Architectures. IACR Cryptol. ePrint Arch., 2022:955, 2022.
- ^ Jens-Peter Kaps, William Diehl, Michael Tempelmeier, Farnoud Farahmand, Ekawat Homsirikamol, and Kris Gaj. A Comprehensive Framework for Fair and Efficient Benchmarking of Hardware Implementations of Lightweight Cryptography. IACR Cryptol. ePrint Arch., 2019:1273, 2019.
- ^ Rui Zong, Xiaoyang Dong, Huaifeng Chen, Yiyuan Luo, Si Wang, and Zheng Li. Towards Key-recovery-attack Friendly Distinguishers: Application to GIFT-128. IACR ToSC 2021 (Vol 1, page 156-184). https://tosc.iacr.org/index.php/ToSC/article/view/8836/8439.
- ^ Mustafa Khairallah. Weak Keys in the Rekeying Paradigm: Application to COMET 841 and mixFeed. IACR ToSC 2019 (Vol 4, page 272-289). https://tosc.iacr.org/index.php/ToSC/article/view/8465/8031
- ^ Mustafa Khairallah. Observations on the Tightness of the Security Bounds of GIFT-COFB and HyENA. IACR Cryptol. ePrint Arch., 2020:1463, 2020.
- ^ Zhe CEN, Xiutao FENG, Zhangyi Wang, and Chunping CAO. (–Withdrawn–) Forgery attack on the authentication encryption GIFT-COFB. IACR Cryptol. ePrint Arch., 2020:698, 2020.
- ^ Xiaolu Hou, Jakub Breier, and Shivam Bhasin. DNFA: Differential No-Fault Analysis 824 of Bit Permutation Based Ciphers Assisted by Side-Channel. IACR Cryptol. ePrint Arch., 2020:1554, 2020.
- ^ Kyoungbae Jang, Hyunjun Kim, Siwoo Eum, and Hwajeong Seo. Grover on GIFT. IACR Cryptol. ePrint Arch., 2020:1405, 2020.
- ^ Subodh Bijwe, Amit Kumar Chauhan, and Somitra Kumar Sanadhya. Quantum Search for Lightweight Block Ciphers: GIFT, SKINNY, SATURNIN. IACR Cryptol. ePrint Arch., 2020:1485, 2020.