New results in biclique cryptanalysis of full round GIFT

Abstract

Security of a recently proposed bitwise block cipher GIFT is evaluated in this paper. In order to mount full round attacks on the cipher, biclique cryptanalysis method is applied. Both variants of the block cipher are attacked using Independent biclique approach. For recovering the secret keys of GIFT-64, the proposed attack requires 2^127.45 full GIFT-64 encryption and 2⁸ chosen plain texts. For recovering the secret keys of GIFT-128, the proposed attack requires 2^127.82 full GIFT-128 encryption and 2¹⁸ chosen plain texts. The attack complexity is compared with that of other attacks proposed previously. The security level of GIFT is also compared with that of the parent block cipher PRESENT, based on the analysis.

Keywords

Block cipher cryptanalysis biclique complexity

1 Introduction

The security required for information transactions has become extremely significant nowadays. Because of this reason light weight block cipher design has become a hot research topic which can offer excellent security to IoT exponents like wireless sensor networks, RFID etc. Some of the most popular block ciphers which claim excellent security in hardware/software, against different kinds of attacks are listed in [3 , 29]. In many cases the cipher may not possess as much security as claimed by the designers. Different methods and tools are available to gauge the security of block ciphers.

Linear [23] and differential cryptanalysis [9] are two conventional techniques used to evaluate the strength of ciphers. Both the methods exploit the weakness of substitution layer as well as permutation layer to retrieve the secret key of the cipher [13, 16 , 24]. However, it can be observed that most of the linear/ differential attacks can be applied only for reduced round analysis. Both methods do not evaluate the performance of key layer except in related key attacks [8]. With the help of related keys, the numbers of rounds which can be attacked is slightly increased, but still full round attacks are almost impossible on most of the ciphers.

Meet-in-the-middle attack [1, 5] is another method which offers excellent data complexity requirement. Still this method is considered as less efficient compared to linear, differential or integral attacks, since a large part of the cipher is to be kept independent of the selected key bits, which is difficult in most of the cases. But the application of bicliques along with meet-in-the-middle attacks, leads to excellent results. However, in this paper, concept of biclique is used along with ‘matching with precomputation’ instead of meet-in-the-middle attack, considering the convenience.

Biclique cryptanalysis is considered to be a new analysis method proposed by Khovratovich et al. [7]. This method is originated from splice and cut frame work [14 , 18] and developed for hash function cryptanalysis in the beginning. Later in 2011 Biclique method is applied by Bogdanov et al. [2] to propose a full round attack on AES. After that biclique method became well known for block cipher cryptanalysis and applied by cryptologists on various light weight block ciphers [6 , 26]. Biclique method exploits the weakness of permutation and key layers. Substitution layer properties are not analysed by this method.

The procedure of Biclique cryptanalysis in proposing attacks against any block cipher is almost similar. But the implementation of the attack depends on the structure of block cipher. Biclique attack mainly exploits the weakness of key layer and permutation layer. Even if GIFT is evolved from PRESENT an attack proposed on PRESENT is not applicable to GIFT since both key layer and permutation layer of PRESENT and GIFT are different. Formation of an effective biclique is very important since the complexity of attack is directly influenced by it. The data complexity of the attack is affected by the bits position at which the differential injected, performance of key and permutation layers and number of biclique rounds. The time complexity of the attack is mainly determined by the recomputation, which in turns determined by the performance of key and permutation layer and selection of differential bits. So an attacker proposes a biclique attack on a cipher only after examining the properties keenly. An attack proposed on a cipher is just irrelevant to another cipher.

Here biclique cryptanalysis is applied to the light weight block cipher GIFT [25]. Summary of the attacks carried out on GIFT is given in Table 1. Since GIFT is evolved from the block cipher PRESENT [3], details of latest biclique attacks proposed on PRESENT are also given in Table 1. A comparison of security levels of the two ciphers can be obtained from here. The unbalanced biclique attack proposed in [12] also attack full round GIFT but the data complexity is very high especially in the case of GIFT-128. Biclique attacks are done in two steps. First step is constructing the biclique. The second step can be either proposing a ‘Meet-in-the-Middle attack’ (MITM) or ‘Matching with precomputation’. The unbalanced Biclique attack proposed in [12] uses MITM as the second part where Matching with Precomputation is applied in this paper. Product of time complexity and data complexity is also shown in Table 1 just for comparison of performance. The product has lowest values for the attack proposed in this paper. The data complexity required for mounting a successful attack on GIFT-64 is 2⁸, which is the lowest among the data complexity required for the attacks listed here. The reason for the very low data complexity requirement for biclique attack proposed on GIFT-64 is the interleaved key bit additions. Out of 64 data bits in GIFT-64, key bits are added only to 32 data bits, which eliminates 32 Ex-OR gates and corresponding power dissipation in each round, but reduces the security level. Table 2 compares the security strength of GIFT with other block ciphers of key length 128 bits, based on biclique attacks proposed by various cryptologists.

Table 1
Attack complexity comparison of various attacks on GIFT

Cipher Reference, Year Type of attack No. of rounds Time complexity Data complexity Product of time and data complexity

GIFT - 64 [15], 2018 Differential 16 2⁸³ 2⁶² 2¹⁴⁵

[4], 2019 Differential 19 2¹¹² 2⁶³ 2¹⁷⁵

[28], 2019 RK-Boomerang 23 2^126.6 2^63.3 2^189.9

[12], 2019 Unbalanced Biclique 28(FULL) 2^122.88 2¹⁶ 2^138.66

This Paper Biclique 28(FULL) 2^127.45 2⁸ 2^135.45

GIFT - 128 [15], 2018 Differential 17 2¹¹⁵ 2⁶² 2¹⁷⁷

[4], 2019 Differential 23 2¹²⁰ 2¹²⁰ 2²⁴⁰

[28], 2019 RK-Boomerang 21 2^126.6 2^126.6 2^253.2

[12], 2019 Unbalanced Biclique 40(FULL) 2^118.38 2⁸⁰ 2^198.38

This Paper Biclique 40(FULL) 2^127.82 2¹⁸ 2^145.82

PRESENT - 80 [21], 2020 Biclique 31(FULL) 2^79.76 2²³ 2^102.76

PRESENT - 128 [19], 2012 Biclique 31(FULL) 2^127.81 2¹⁹ 2^146.81

Cipher	Reference, Year	Type of attack	No. of rounds	Time complexity	Data complexity	Product of time and data complexity
GIFT - 64	[15], 2018	Differential	16	2⁸³	2⁶²	2¹⁴⁵
	[4], 2019	Differential	19	2¹¹²	2⁶³	2¹⁷⁵
	[28], 2019	RK-Boomerang	23	2^126.6	2^63.3	2^189.9
	[12], 2019	Unbalanced Biclique	28(FULL)	2^122.88	2¹⁶	2^138.66
	This Paper	Biclique	28(FULL)	2^127.45	2⁸	2^135.45
GIFT - 128	[15], 2018	Differential	17	2¹¹⁵	2⁶²	2¹⁷⁷
	[4], 2019	Differential	23	2¹²⁰	2¹²⁰	2²⁴⁰
	[28], 2019	RK-Boomerang	21	2^126.6	2^126.6	2^253.2
	[12], 2019	Unbalanced Biclique	40(FULL)	2^118.38	2⁸⁰	2^198.38
	This Paper	Biclique	40(FULL)	2^127.82	2¹⁸	2^145.82
PRESENT - 80	[21], 2020	Biclique	31(FULL)	2^79.76	2²³	2^102.76
PRESENT - 128	[19], 2012	Biclique	31(FULL)	2^127.81	2¹⁹	2^146.81

Table 2

Security strength comparison of GIFT with other block ciphers of key length 128 bits, based on biclique attacks

Cipher	Reference	Key length (in bits)	Number of rounds	Time complexity	Data complexity
GIFT –64	This paper	128	Full(28)	2^127.45	2⁸
GIFT - 128	This paper	128	Full(40)	2^127.82	2¹⁸
LED -128	[19]	128	Full(48)	2^127.37	2⁶⁴
PICO -128	[11]	128	Full(32)	2^127.72	2⁴⁸
PRESENT –128	[19]	128	Full(31)	2^127.81	2¹⁹
Piccolo –128	[19]	128	Full(31)	2^127.35	2²⁴

This paper is organized as follows. Section 2 describes the structure and functioning of GIFT. Section 3 explains about the theory and steps of biclique cryptanalysis. The full round attack proposed on GIFT-64 is given in section 4 and the full round attack proposed on GIFT-128 is given in section 5. Section 6 concludes the article.

2 Description of GIFT

The block cipher GIFT proposed by S.Banik et al. [25] has two versions based on the number of data bits, denoted by GIFT-64 and GIFT-128, having 64 and 128 data bits respectively. Both versions have a key size of 128 bits. GIFT-64 performs one complete encryption through 28 rounds while GIFT-128 performs the same through 40 rounds. Each round consists of 3 operations called SubCells, PermBits, and AddRoundKey, which perform substitution, permutation and key addition respectively.

2.1 SubCells

The same invertible sbox GS is used for both versions of GIFT. Every nibble of the cipher state is substituted by the application of GS $w_{i} \leftarrow GS (wi), \forall i \in {0, . ., s - 1} .$

The inputs and corresponding outputs of the sbox in hexadecimal notation is given in Table 3.

Table 3
Specification of GIFT sbox

x 0 1 2 3 4 5 6 7

Gs(x) 1 a 4 c 6 f 3 9

x 8 9 a b c d e f

Gs(x) 2 d b 7 5 0 8 E

x	0	1	2	3	4	5	6	7
Gs(x)	1	a	4	c	6	f	3	9
x	8	9	a	b	c	d	e	f
Gs(x)	2	d	b	7	5	0	8	E

2.2 PermBits

After this operation, the intermediate cipher text bits are permuted, the details of which are given in [25].

2.3 AddRoundKey

For each round, round key and round constants are generated and added.

An n/2-bit round key RK is extracted from the key state, it is further partitioned into 2 s-bit words RK = U||V=us–1..u0||vs–1..v0, where s = 16,32 for GIFT-64 and GIFT-128 respectively.

For GIFT-64, U and V are Ex-ORed to {b_4i +1} and {b_4i} of the cipher state respectively.

B_4i +1 ← b_4i +1 ⊕ ui, b_4i ← b_4i ⊕ v_i, ∀ i ∈ {0,..,15}.

For GIFT-128, U and V are XORed to {b_4i +2} and {b_4i +1} of the cipher state respectively.

b_4i +2 ← b_4i +2 ⊕ u_i, b_4i +1 ← b_4i +1 ⊕ v_i, ∀ i ∈ {0,..,31}. For both versions of GIFT, a 6-bit round constant C = c₅c₄c₃c₂c₁c₀ are XORed into the cipher state at bit position 23, 19, 15, 11, 7 and 3 respectively

For both versions of GIFT, the key schedule and round constants are the same, but differ in key extraction. In each round, a round key is extracted from the key state before the key state update.

For GIFT-64, two 16-bit words of the key state are extracted as the round key RK = U||V. $U \leftarrow k 1, V \leftarrow k 0 .$

For GIFT-128, four 16-bit words of the key state are extracted as the round key RK = U||V. $U \leftarrow k 5 | | k 4, V \leftarrow k 1 | | k 0 .$

The key state is then updated as follows, k7||k6||..||k1||k0 ← k1 ⪢ 2||k0 ⪢ 12||..||k3||k2, where ⪢ i represents an i bits right rotation within a 16-bit word.

Using affine LFSR, round constants are generated and added.

3 Biclique cryptanalysis

Theory and step by step procedure of Biclique cryptanalysis is explained in this section. Complexity calculation is also detailed.

3.1 Steps in biclique cryptanalysis

Four steps are involved in biclique cryptanalysis which are explained in the following sections.

Key Space Partitioning: First the attacker has to select the biclique dimension d. If k is the key length, the entire key space is now divided into 2^k - 2d spaces of 2^2d keys.

Biclique Construction: A biclique is constructed by two groups of elements where all elements of one group is connected with all elements of other group. Let S consists of a group of elements and C consists of another group of elements, where each element of S is connected with each element of C . Now this system can be called as a biclique. In general, elements in C are represented by C_i and elements in S are represented by S_j where ∀ i,j ∈ {0,..,2^d –1}. If K[i, j] is the key which encrypt S_j to C_i, then the 3-tuple of sets [{S_j}, {C_i}, {K }] is called a d dimensional biclique B . Mathematically B is represented as $S_{j} \overset{K [i, j]}{\leftarrow} C_{i}$

Let K[0,0] be the base key, Δi be the forward differential and ∇j be the reverse differential, then a group of keys are defined as $K [i, j] = K [0, 0] \oplus Δ i \oplus \nabla j$

The attacker has to select forward and backward differentials carefully to mount an attack of lowest complexity. The schematic diagram of a Biclique is shown in Fig. 1.

Fig. 1

Schematic view of Biclique.

Bicliques are usually constructed at beginning or end of the cipher using a few numbers of rounds. Meet-in-the-middle attack or matching with pre-computation can be used, for attacking the remaining rounds. Based on the selection of differential type, two methods are used for biclique construction. Attacker can select either independent differential or interleaved differential. The bicliques applied in this paper are constructed using independent differentials.

Data Collection: The complete cipher E is now divided into 3 sub-ciphers E₁, E₂ and B in such a way that $P \overset{E_{1}}{\to} V \overset{E_{2}}{\to} S \overset{B}{\to} C$ (1) where P is the plain text, V and S are two internal states, and C is the cipher text. A decryption oracle is used to obtain plain text P from the cipher text C

Key Testing: Here the attacker check weather $P_{i} \overset{K [i, j]}{\leftarrow} S_{j} (through E_{1} and E_{2})$

Another key set is to be chosen and tested, if the attacker can’t find the right key element in the chosen key set.

3.2 Independent bicliques

Here an independent biclique is constructed over the subcipher B using two differentials, one in forward direction and the other in the backward direction. Using a 3-tuple set {S₀, C₀, K[0,0] }, the base computation is selected, given by $S_{0} \overset{K [0, 0]}{\leftarrow} C_{0}$

Which means cipher text C₀ is obtained by encrypting S₀ with base key K[0,0].

Now using the selected forward differentials Δ_i the base intermediate state S₀ is connected with all possible cipher texts C_i. Mathematically $S_{0} \overset{K [0, 0] \oplus Δ_{i}^{K}}{\to} C_{0} \oplus Δ_{i} = C_{i}$ Similarly using backward differential ∇j, the adversary connects cipher text C₀ with S_j. So $S_{j} = S_{0} \oplus \underset{j}{\nabla} \overset{K [0, 0] \oplus \nabla_{j}^{K}}{\leftarrow - - - - - - - - - - - -} C_{0}$

If no active non-linear operations are shared by the trails of forward differentials Δ_i and backward differentials Δ _j , then all the 2^d inputs differences Δ _j can be connected with the entire 2^d output differences Δ_i. $S_{0} \oplus \underset{j}{\nabla} \overset{K [0, 0] \oplus Δ_{i}^{K} \oplus \nabla_{j}^{K}}{\leftrightarrow} C_{0} \oplus Δ_{i} \forall i, j \in {0 . . 2^{d} - 1}$

From the above equations one can understand that the number of calculations is minimized. Mathematically, 2^2d keys can be tested using 2×2^d calculations, using independent bicliques of dimension d.

Here the length of the differentials depends on the number of rounds with which a full diffusion occurs. Biclique differential length is changed with the speed with which diffusion happens. In order to cover the remaining number of rounds, which is usually larger in number, matching with pre-computation is preferred to meet-in-the-middle attacks when the constructed biclique is short.

3.3 Matching with precomputation

Matching with pre-computation is used for the remaining rounds of the cipher other than biclique rounds. As shown in the Section 3.1, the cipher E is represented by Equation (1)

Suppose subcipher E₁ encrypts P and subcipher E₂ decrypts S. Both operations lead to the intermediate state V. The Equations (2), (3), (4), (5) and (6) give a mathematical representation of matching, which is done in different steps $P_{i} \overset{K [i, 0]}{\to} \vec{v_{i, 0}} (through sub cipher E_{1})$ (2) $\overset{\leftarrow}{v_{0, j}} \overset{K [0, j]}{\leftarrow} S_{j} (through sub cipher E_{2})$ (3)

2^d values are calculated from the operations represented by Equations (2) and (3). The results with intermediate values are stored in the memory. For the remaining 2^2d-2^d computations these stored values are used. $P_{i} \overset{K [i, j]}{\to} \vec{v_{i, j}} (through sub cipher E_{1})$ (4) $\overset{\leftarrow}{v_{i, j}} \overset{K [i, j]}{\leftarrow} S_{j} (through sub cipher E_{2})$ (5) $P_{i} \overset{K [i, j]}{\to} \vec{v_{i, j}} = = \overset{\leftarrow}{v_{i, j}} \overset{K [i, j]}{\leftarrow} S_{j}$ (6)

Only the part of key schedule and round transformation that differ from the stored values need to be recomputed. This approach effectively leads to reduced computational complexity.

3.4 Complexity calculation

From the above discussions it is evident that 2^k - 2d bicliques need to be constructed in order to cover the complete key space. The total complexity of a biclique attack is given by C_full = 2^k–2d (C_biclique+C_decrypt+C_precompute+C_recompute+C_falsepos), where

–C_biclique is the costs for the construction of a biclique,

–C_decrypt is the complexity of the oracle for the decryption of 2^d ciphertexts,

–C_precompute is the costs for the computation of intermediate stage V for 2^d computations using sub cipher E₁ and E₂

–C_recompute is the complexity of recomputing 2^2d values of the matching bits v_i,j in both directions,

–C_falsepos is the complexity for eliminating the false positives.

It can be observed that C_recompute dominates the time complexity among the 5 factors.

4 Biclique cryptanalysis of full round GIFT-64

An attacker has to find new bicliques by injecting proper differentials which leads to minimal time and data complexity in every new attack. In literature it can be seen that the same cryptanalysis procedure is applied by cryptologists repeatedly to find improvised results by proposing better attacks. The attack proposed in this paper brings better results in cryptanalysis of GIFT block cipher. In this section biclique cryptanalysis of GIFT-64 is presented.

4.1 Biclique construction and sub-cipher partitioning

A 4 dimensional Biclique is constructed using the last 5 rounds i.e., round 24 to round 28. In each round 32 key bits are Ex-ORed with the intermediate data.

Here two groups of key bits {k₆₄, k₆₅, k₈₄, k₈₅} and {k₁₀₄, k₁₀₅, k₁₂₄, k₁₂₅} are chosen for constructing Δ_i differential and Δ_j differential respectively, which injects a non-zero difference to the cipher, whereas all other key bits do not manipulate the cipher state. It is observed that an effective biclique, which can attack the full round GIFT-64, can be constructed using the above mentioned forward and backward differentials.

The whole cipher is divided into 3 sub-ciphers, as per Equation (1). The details of sub-ciphers and the bits matched are given in Table 4.

Table 4
GIFT -64 sub-cipher details and bits matched

Sub cipher Rounds covered Bits matched

E1 1-12 0, 1, 17, 18 (Round 12)

E2 13-23 0, 1, 17, 18 (Round 13)

B 24-28 –

Sub cipher	Rounds covered	Bits matched
E1	1-12	0, 1, 17, 18 (Round 12)
E2	13-23	0, 1, 17, 18 (Round 13)
B	24-28	–

The biclique constructed over the sub-cipher B for the rounds 24-28 is given in the Fig. 2. Each data bit is denoted by a single line and arrows show the direction. Red colour dots represent Δ_i key bit additions and blue colour dots represent ∇_j key bit additions. Zero difference key bit addition is represented by black dots. Since only 8 bits are affected by the Δ_i differential, the data complexity does not exceed 2⁸.

Fig. 2

Four Dimensional Biclique diagram of GIFT –64.

The data bit positions at which Δ_i and differentials inject non zero differences on biclique rounds are given in Table 5. The ‘-‘ symbol indicates that the differential key bits do not appear in that particular round. The bit positions are given in the ascending order.

Table 5

GIFT - 64 data bit positions at which non zero differential key bits appear

	Δ _i {k₆₄, k₆₅, k₈₄, k₈₅}	{k₁₀₄, k₁₀₅, k₁₂₄, k₁₂₅}
Round	Positions	Positions
24	-, -, -, -	9, 13, 48, 52
25	-, -, -, -	-, -, -, -
26	-, -, -, -	-, -, -, -
27	32, 33, 36, 37	-, -, -, -
28	-, -, -, -	0, 1, 4, 5

The plain text P is derived through a decryption oracle. The recomputation in forward and backward directions is performed according to blue/red lines as shown in Fig. 3. Number of active sboxes can be calculated from the same figure.

Fig. 3

Recomputation in forward and backward directions for GIFT-64.

4.2 Attack procedure

Pre-Computation: According to Equation (2) calculate value of four bits v₀, v₁, v₁₇ and v₁₈ of round 12 for each values of i, where i={0 ... 2^d-1}, from P_i and K[i,0] in forward direction. According to Equation (3) calculate value of four bits v₀, v₁, v₁₇ and v₁₈ of round 13 for each values of j, where j={0 ... 2^d-1}, from S_j and K[0,j] in backward direction.

–Forward computation: According to Equation (4) compute matching bits of v_i,j from Pi and K[i,j] in forward direction. Since forward differential key bits do not appear up to round 3, active sboxes appear from round 4 only, so that a maximum of 48 active sboxes are eliminated while calculating the forward recomputation complexity. C_decrypt is the complexity of the oracle for the decryption of 2^d cipher texts.

–Backward computation: According to Equation (5) compute matching bits of v_i,j from S_i and K[i,j] in backward direction.

Now we match four bits v₀, v₁, v₁₇ and v₁₈ using Equation (6). The adversary confirms the key bits just by validating the equation using the bits matched.

4.3 Time complexity calculation

C_full = 2^n–2d (C_biclique+C_decrypt+C_precompute+ C_recompute+C_falsepos),

Number of active sboxes in forward recomputation = 4 + 8+4×16 + 8+2 = 86

Number of active sboxes in backward recomputation = 4 + 4+7×16 + 8+2 = 130

Total number of active sbox = 216

Total number of sbox = 28×16 = 448

The time complexity calculation of GIFT-64 is given in Table 6.

Table 6
Complexity calculations for GIFT-64

Head Calculation Result

(Full GIFT-64 Enc.)

C_biclique 2×2⁴×5/28 2^2.52

C_decrypt 2⁴ 2⁴

C_precompute 2⁴×23/28 2^3.72

C_recompute 2⁸×216/448 2^6.95

C_falsepos 2^2 ×4 -4 2⁴

C_full 2^{128 - 2 ×4}(2^2.52 +2⁴ + 2^127.45

2^3.72 +2^6.95⁺ 2⁴)

Head	Calculation	Result
C_biclique	2×2⁴×5/28	2^2.52
C_decrypt	2⁴	2⁴
C_precompute	2⁴×23/28	2^3.72
C_recompute	2⁸×216/448	2^6.95
C_falsepos	2^2 ×4 -4	2⁴
C_full	2^{128 - 2 ×4}(2^2.52 +2⁴ +	2^127.45
	2^3.72 +2^6.95⁺ 2⁴)

5 Biclique cryptanalysis of full round GIFT-128

5.1 Biclique construction and sub-cipher partitioning

The biclique attack carried out on GIFT-128 is similar to the biclique attack proposed on GIFT-64. So here the attack is discussed briefly. Here also the whole cipher is divided into 3 sub ciphers, E1, E2 and B according to Equation (1).

The details of sub ciphers and the bits matched are given in Table 7. For matching, the bits are selected carefully in order to minimise the number of active sboxes. The biclique is constructed over the rounds 37, 38, 39 and 40. Δ _i differential and differential are constructed using the set of key bits {k₃₂, k₃₃, k₉₆, k₉₇} and {k₂, k₃, k₆₆, k₆₇} respectively. The bit positions at which the above selected group of key bits inject differences in biclique rounds are given in Table 8. The bit positions are given in the ascending order.

Table 7
GIFT - 128 sub-cipher details and bits matched

Sub cipher Rounds covered Bits matched

E1 1-18 0, 1, 2, 3 (Round 18)

E2 19-36 0, 1, 2, 3 (Round 19)

B 37-40 –

Sub cipher	Rounds covered	Bits matched
E1	1-18	0, 1, 2, 3 (Round 18)
E2	19-36	0, 1, 2, 3 (Round 19)
B	37-40	–

Table 8

GIFT - 128 data bit positions at which non zero differential key bits appear

	Δ_i {k₃₂, k₃₃, k₉₆, k₉₇}	∇_j{k₂, k₃, k₆₆, k₆₇}
Round	Positions	Positions
37	-, -, -, -	25, 26, 29, 30
38	17, 18, 21, 22	-, -, -, -
39	-, -, -, -	25, 29, 42, 46
40	17, 21, 34, 38	-, -, -, -

The biclique constructed over 4 rounds is shown in Fig. 4 and the recomputation along forward and backward directions are shown in Fig. 5. Since the forward differential affects only 18 bits, the data complexity does not exceed 2¹⁸.

Fig. 4

Four dimensional Biclique diagram of GIFT –128.

Fig. 5

Recomputation in forward and backward directions for GIFT-128.

5.2 Attack procedure

The attack procedure is the same as that given in section 4.2. The bits matched during the recomputation are v₀, v₁, v₂ and v₃ of rounds 18 and 19. Forward and backward re-computations of GIFT-128 are performed according to blue and red lines as shown in Fig. 5.

5.3 Time complexity calculation

C_full = 2^n–2d (C_biclique+C_decrypt+C_precompute+ C_recompute+C_falsepos),

Number of active sboxes in forward recomputation = 2 + 4+18 + 12×32 + 16 + 4 = 428

Number of active sboxes in backward recomputation = 4 + 16 + 13×32 + 16 + 4+1 = 457

Total number of active sbox = 885

Total number of sbox = 40×32 = 1280

The time complexity calculation of GIFT-128 is given in Table 9.

Table 9
Complexity calculations for GIFT-128

Head Calculation Result

(Full GIFT-128 Enc.)

C_biclique 2×2⁴×4/40 2^1.67

C_decrypt 2⁴ 2⁴

C_precompute 2⁴×36/40 2^3.85

C_recompute 2⁸×885/1280 2^7.47

C_falsepos 2^2 ×4 -4 2⁴

C_full 2^{128 - 2 ×4}(2^1.67 ⁺ 2⁴ ⁺ 2^3.85 2^127.82⁺ 2^7.47 ⁺ 2⁴)

Head	Calculation	Result
C_biclique	2×2⁴×4/40	2^1.67
C_decrypt	2⁴	2⁴
C_precompute	2⁴×36/40	2^3.85
C_recompute	2⁸×885/1280	2^7.47
C_falsepos	2^2 ×4 -4	2⁴
C_full	2^{128 - 2 ×4}(2^1.67 ⁺ 2⁴ ⁺ 2^3.85	2^127.82⁺ 2^7.47 ⁺ 2⁴)

6 Conclusion

The security strength of both variants of full round GIFT is evaluated using biclique cryptanalysis. The overall complexity of the attacks proposed in this paper is minimal according to our knowledge and belief. The attack complexities are also compared with that of other light weight block ciphers. It can be observed that the data complexities required for the attacks on both variants of GIFT are very small because key addition is performed only with half the number of intermediate data bits. This technique will reduce the area and power consumption of the cipher but considerably lower the security strength.

References

Bogdanov

and Rechberger

, A 3-Subset Meet-in-the-Middle Attack: Cryptanalysis of the Lightweight Block Cipher KTANTAN. In: A. Biryukov,G. Gong, D.R. Stinson, (eds.) SAC 2010. LNCS, Springer, Heidelberg vol. 6544,. pp. 229–240.

Bogdanov

, Khovratovich

and Rechberger

, Biclique Cryptanalysis of the Full AES. In: D.H. Lee, X. Wang (eds)Advances in Cryptology –ASIACRYPT2011, Lecture Notes in Computer Science, Springer, Berlin, Heidelberg7073 (2011), 344–371.

Bogdanov

, Knudsen

L.R.

and Leander

, PRESENT: An Ultra-Lightweight Block Cipher. In: P. Paillier, I. Verbauwhede (eds) Cryptographic Hardware and Embedded Systems –CHES 2007. Lecture Notes in Computer Science, Springer, Berlin, Heidelberg vol 4727. pp 450–466.

Zhu

, Dong

and Yu

, MILP-Based Differential Attack on Round-Reduced GIFT. In: Matsui M. (eds) Topics in Cryptology –CT-RSA 2019. CT-RSA 2019. Lecture Notes in Computer Science, (2019) vol 11405. Springer, Cham pp. 372–390.

Bouillaguet

, Derbez

and Fouque

, Automatic Search of Attacks on Round Reduced AES and Applications. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, Springer, Heidelberg, vol. 6841 pp. 169–187.

Hong

, Koo

and Kwon

, Biclique Attack on the Full HIGHT, ICISC 2011, LNCS 7259, Springer-Verlag, 2012. pp. 365–374.

Khovratovich

, Rechberger

and Savelieva

, Bicliques for preimages: attacks on Skein-512 and the SHA-2 family (2011), FSE 2012 LNCS 7549 pp. 244–263.

Biham

, Dunkelman

and Keller

, Related-Key Impossible Differential Attacks on AES-192. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS, Springer, Heidelberg 3860 (2006), 21–31.

Biham

and Shamir

, Differential cryptanalysis of DES-like cryptosystems. In A.J. Menezes, S.A. Vanstone, eds.: CRYPTO’90. Volume 537 of LNCS. Springer, Heidelberg 1991, pp. 2–21.

10.

Abed

, Forler

, List

, Lucks

and Wenzel

, Biclique Cryptanalysis of the PRESENT and LED Lightweight Ciphers, Cryptology ePrint Archive, Report 2012/591, 2012.

11.

Bansod

, Pisharoty

and Patil

A.J.

, PICO: An Ultra Lightweight and Low Power Encryption Design for Ubiquitous Computing, Defence Science Journal66(3) (2016), 259–265.

12.

Han

, Zhao

and Zhao

, Unbalanced Biclique cryptanalysisof full-round GIFT, IEEE Access7 (2019), 144425–144432. doi: 10.1109/ACCESS.2019.2945006.

13.

Mala

, Dakhilalian

and Rijmen

, Improved Impossible Differential Cryptanalysis of 7-Round AES-128. In: G. Gong, K.C. Gupta (eds) Progress in Cryptology - INDOCRYPT 2010. Lecture Notes in Computer Science, vol 6498. Springer, Berlin, Heidelberg (2010), pp. 282–291.

14.

Guo

, Ling

, et al., Advanced Meet-in-the-Middle PreimageAttacks: First Results on Full Tiger, and Improved Results onMD4 and SHA-2. In:M.Abe, (ed.)ASIACRYPT 2010. Springer Heidelberg LNCS, vol. 6477, pp. 56–75.

15.

Zhao

, et al., Differential analysis of lightweight block cipher gift, J. Cryptologic Res5(4) (2018), 335–343.

16.

Cho

J.Y.

, Linear Cryptanalysis of Reduced-Round PRESENT. In: J. Pieprzyk (eds) Topics in Cryptology - CT-RSA 2010. Lecture Notes in Computer Science, vol 5985. Springer, Berlin, Heidelberg (2010),pp. 302–317.

17.

Aoki

and Sasaki

, Meet-in-the-Middle Preimage Attacks Against Reduced SHA-0 and SHA-1. In: S. Halevi, (ed.) CRYPTO 2009. LNCS, Springer, Heidelberg 5677 (2009), 70–89.

18.

Aoki

and Sasaki

, Preimage Attacks on One-Block MD4, 63-StepMD5 andMore. In: R.M. Avanzi, L. Keliher, F. Sica, (eds.) SAC 2008. LNCS, Springer, Heidelberg 5381 (2009), 103–119.

19.

Jeong

and Kang

, Biclique cryptanalysis of lightweight block ciphers present, piccolo and led. IACR Cryptol. ePrint Arch. p. 621 (2012).

20.

Ohkuma

, Weak Keys of Reduced-Round PRESENT for Linear Cryptanalysis. In: M.J. Jacobson, V. Rijmen, R. Safavi-Naini (eds) Selected Areas in Cryptography. SAC 2009. Lecture Notes in Computer Science, Springer, Berlin, Heidelberg vol 5867. pp 249–265.

21.

Jithendra

K.B.

and Shahana

T.K.

, New Biclique Cryptanalysis on Full-Round PRESENT-80 Block Cipher. Springer Nature Journal of Computer Science. 1, 94 (2020). https://doi.org/10.1007/s42979-020-0103-z

22.

Çoban

, Karakoç

and Bizta¸s

Ö.

, Biclique Cryptanalysis of TWINE, Cryptology ePrint Archive, Report 2012/422, 2012.

23.

Matsui

, Linear Cryptanalysis Method for DES Cipher. In: Helleseth T. (eds) Advances in Cryptology —EURO-CRYPT ’93. EUROCRYPT 1993. Lecture Notes in Computer Science, Springer, vol 765. pp 386–397.

24.

Phan

R.C.

, W.: Impossible Differential Cryptanalysis of 7-round Advanced Encryption Standard (AES). Information Processing Letters, 91 (2004), 33–38.

25.

Banik

and Pandey

S.K.

, GIFT:Asmall 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. pp. 321–345.

26.

Chen

, Biclique Attack of the Full ARIA-256, Cryptology ePrint Archive, Report 2012/011, 2012.

27.

, Zhang

and Block

, A Light weight Block Cipher. In: Lopez J., Tsudik G. (eds) Applied Cryptography and Network Security. ACNS 2011. Lecture Notes in Computer Science, Springer, Berlin, Heidelberg vol 6715. pp 327–344.

28.

Liu

and Sasaki

, Related-Key Boomerang Attacks on GIFT with Automated Trail Search Including BCT Effect. In: J. Jang-Jaccard, F. Guo (eds) Information Security and Privacy. ACISP 2019. LNCS, vol 11547. Springer, Cham (2019), pp. 555–572.

29.

Gong

, Nikova

and Law

Y.W.

, KLEIN: A New Family of Lightweight Block Ciphers. In: A. Juels, C. Paar (eds) RFID. Security and Privacy. RFIDSec 2011. Lecture Notes in Computer Science, Springer, Berlin, Heidelberg vol 7055. pp 1–18.

New results in biclique cryptanalysis of full round GIFT

Abstract

Keywords

1 Introduction

2.1 SubCells

Table 3 Specification of GIFT sbox x 0 1 2 3 4 5 6 7 Gs(x) 1 a 4 c 6 f 3 9 x 8 9 a b c d e f Gs(x) 2 d b 7 5 0 8 E

2.3 AddRoundKey

3 Biclique cryptanalysis

3.1 Steps in biclique cryptanalysis

3.3 Matching with precomputation

4 Biclique cryptanalysis of full round GIFT-64

4.1 Biclique construction and sub-cipher partitioning

Table 4 GIFT -64 sub-cipher details and bits matched Sub cipher Rounds covered Bits matched E1 1-12 0, 1, 17, 18 (Round 12) E2 13-23 0, 1, 17, 18 (Round 13) B 24-28 –

4.3 Time complexity calculation

Table 6 Complexity calculations for GIFT-64 Head Calculation Result (Full GIFT-64 Enc.) Cbiclique 2×24×5/28 22.52 Cdecrypt 24 24 Cprecompute 24×23/28 23.72 Crecompute 28×216/448 26.95 Cfalsepos 22 ×4 -4 24 Cfull 2128 - 2 ×4(22.52 +24 + 2127.45 23.72 +26.95+ 24)

5.1 Biclique construction and sub-cipher partitioning

Table 7 GIFT - 128 sub-cipher details and bits matched Sub cipher Rounds covered Bits matched E1 1-18 0, 1, 2, 3 (Round 18) E2 19-36 0, 1, 2, 3 (Round 19) B 37-40 –

5.3 Time complexity calculation

Table 9 Complexity calculations for GIFT-128 Head Calculation Result (Full GIFT-128 Enc.) Cbiclique 2×24×4/40 21.67 Cdecrypt 24 24 Cprecompute 24×36/40 23.85 Crecompute 28×885/1280 27.47 Cfalsepos 22 ×4 -4 24 Cfull 2128 - 2 ×4(21.67 + 24 + 23.85 2127.82+ 27.47 + 24)

References

Table 3
Specification of GIFT sbox

x 0 1 2 3 4 5 6 7

Gs(x) 1 a 4 c 6 f 3 9

x 8 9 a b c d e f

Gs(x) 2 d b 7 5 0 8 E

Table 4
GIFT -64 sub-cipher details and bits matched

Sub cipher Rounds covered Bits matched

E1 1-12 0, 1, 17, 18 (Round 12)

E2 13-23 0, 1, 17, 18 (Round 13)

B 24-28 –

Table 7
GIFT - 128 sub-cipher details and bits matched

Sub cipher Rounds covered Bits matched

E1 1-18 0, 1, 2, 3 (Round 18)

E2 19-36 0, 1, 2, 3 (Round 19)

B 37-40 –