# Known-Key Distinguishing and Partial-Collision Attacks on GFN-2 with SP F-Function

Authors: Deukjo Hong
Journal: Security and Communication Networks
 (2020)

---

## Abstract

We study known-key distinguishing and partial-collision attacks on GFN-2 structures with various block lengths in this paper. For 4-branch GFN-2, we present 15-round known-key distinguishing attack and 11-round partial-collision attack which improve previous results. We also present 17-round known-key distinguishing attack on 6-branch GFN-2 and 27-round known-key distinguishing attack on 8-branch GFN-2 and show that several partial-collision attacks are derived from them. Additionally, some attacks are valid under special conditions for theF-function.


---

## Body

## 1. Introduction

The notion of known-key attack was introduced by Knudsen and Rijmen in 2007 [1]. It uses a known-key distinguisher which holds with much higher probability than that under the uniform distribution. In 2011, Sasaki and Yasuda used the rebound technique [2] to construct known-key distinguishers for the Feistel network whose F-function consists of cryptographically strong S-boxes and an MDS matrix and showed that those distinguishers are converted into partial-collision attacks on hash modes [3]. Later, their results have been applied to variants of the Feistel network [4–6].Feistel network is the encryption structure of well-known block ciphers such as DES [7], SEED [8], and Camellia [9]. It has been researched for secure and efficient block cipher design. In [4], Kang et al. presented known-key attacks on three types of generalized Feistel network (GFN) proposed by Nyberg [10]. Particularly, Type-II GFN (GFN-2) is well-balanced like Feistel network and suitable for lightweight designs because the iteration of the relatively small F-function makes a large-block-length block cipher. So, it has been researched as an alternative of Feistel network, more than other types of GFN. It is often considered as one of design candidates in developing new block ciphers. In practice, the encryption structure of CLEFIA [11] is GFN-2, and HIGHT [12] adopted a slight variant of GFN-2. For this reason, it is important and useful to study and analyze the security of GFN-2.We define GFN-2 with the parameterst, a, and b. t is the number of branches, a is the number of S-boxes which the F-function consists of, and b is the length of input and output of the bijective S-box. In this paper, the byte length and the word length are defined as b bits and ab bits. The block length of GFN-2 with the parameters t, a, and b is abt bits. We restrict (a, b) to (4, 4), (4, 8), (8, 4), and (8, 8) and t to 4, 6, and 8, which are mainly used and considered in block cipher designs.In [4], Kang et al. analyzed only t = 4 cases of GFNs and assumed that the last-round function has no shuffle operation. They presented a 13-round known-key distinguishing attack on GFN-2 and 9-round 1-word and 2-word partial-collision attacks on Matyas-Meyer-Oseas and Miyaguchi-Preneel hash modes of GFN-2. In this paper, we improve the results for GFN-2 in [4] and also present known-key distinguishing and partial-collision attacks for the cases of t = 6 and t = 8. Our results are summarized as follows:(i)
For 4-branch GFN-2, we find a new 5-round inbound structure and make a 15-round known-key distinguishing attack. Assuming the last round has no shuffle operation, we show that a 11-round 3-word partial-collision attack is possible and that whena = 8, 15-round 1-word partial-collision attack is possible. Assuming the last round has the shuffle operation, we show that a 10-round 3-word partial-collision attack is possible and that when a = 8, 14-round 1-word partial-collision attack is possible.(ii)
For 6-branch GFN-2, we find a 7-round inbound structure and make a 17-round known-key distinguishing attack. Whena = 8, we show that a 19-round known-key distinguishing attack, a 17-round 2-word partial-collision attack without the last shuffle operation, and a 16-round 2-word partial-collision attack with the last shuffle operation are possible.(iii)
For 8-branch GFN-2, we find a 11-round inbound structure and make a 27-round known-key distinguishing attack which is extended to 29 rounds whena = 8. We show that a 21-round 5-word partial-collision attack without the last-round shuffle operation and a 20-round 5-word partial-collision attack with the last-round shuffle operation are possible and that a 21-round 2-word partial-collision attack with the last-round shuffle operation is possible when (a, b) ≠ (4, 8).Considering the wide applicability of GFN-2 as a structure of the cryptographic algorithm, our attacks are useful and helpful in designing a new block cipher or hash function based on GFN-2. The remainder of this paper is organized as follows: Section2 gives a brief description of GFN-2 structure and Matyas-Meyer-Oseas and Miyaguchi-Preneel mode and explains the inbound structure of F-function. Section 3 provides a general explanation of how to construct an inbound structure for GFN-2. From Section 4 to Section 6, we propose inbound structures, known-key distinguishers, and partial-collision attacks on GFN-2 for t = 4, 6, and 8. Finally, Section 7 concludes our work.


## 2. Preliminaries

### 2.1. Type-2 Generalized Feistel Network

Let the S-boxS: {0, 1}b ⟶ {0, 1}b be a nonlinear permutation on {0, 1}b. The notation Y = S(X) means that the output of the S-box is Y ∈ {0, 1}b on the input X ∈ {0, 1}b. Let the linear function P: ({0, 1}b)a ⟶ ({0, 1}b)a be the multiplication by a×a MDS matrix over GF (2b). The notation Y = (Y0,Y1,…,Ya−1) = P(X) = P(X0,X1,…,Xa−1) means that the output vector of P is Y = (Y0,Y1,…,Ya−1) on the input vector X = (X0,X1,…,Xa−1). For the S-box S and the linear function P, we define F: {0, 1}ab×{0, 1}ab as follows: for an input X = (X0,X1,…,Xa−1) ∈ ({0, 1}b)a and a subkey RK = (RK0,RK1,…,RKa−1) ∈ ({0, 1}b)a, Y = F(X, RK) = P(SX0+RK0,SX1+RK1), where + is the XOR (eXclusive OR) operation. Figure 1 depicts the example of F-function with a = 4.Figure 1
Structure ofF-function with a = 4.Lett ≥ 4 be an even integer and r be a positive integer. For r-round t-branch GFN-2, we define all subkeys RKi,j generated from a key K as RKi,j = (RKi,j0,RKi,j1,…,RKi,ja−1) ∈ ({0, 1}b)a for 0 ≤ i < r and 0 ≤ j < t/2. We define the shuffle operation σ as σ = (σ(0), σ(1), …, σ(t − 1)) = (t – 1, 0, …, t − 2). Then, we can give the following pseudocode which describes how the r-round t-branch GFN-2 encrypts a plaintext block X0 = (X0,0, X0,1, …, X0,t−1) ∈ ({0, 1}ab)t to Xr = (Xr,0, Xr,1, …, Xr,t−1) ∈ ({0, 1}ab)t:(i)
fori = 0, 1, …, r − 1 do:(ii)
forj = 0, 1, …, t − 1 do:(iii)
ifj is even:(iv)
Yj = Xi,j(v)
else:(vi)
Yj = Xi,j + F(Xi,j−1, RKi,(j−1)/2)(vii)
forj = 0, 1, …, t − 1 do:(viii)
Xi+1,σ(j) = YjThe indexi in the above pseudocode means the round order. Figure 2 depicts the i-th round function of GFN-2 with t = 8. Throughout this paper, we assume that the key K and the subkey RKi,j’s are known and fixed. Since subkey-XORing operations are not important in the description of our work, we omit the notation and explanation about subkeys for simplicity. For example, we replace F(Xi,j−1, RKi,(j−1)/2) with F(Xi,j−1).Figure 2
Structure ofF-function with a = 4.


### 2.2. Inbound Structure ofF-Function

A difference is the XOR between two values at the same position, and a differential trail is a set of all difference transitions in a block cipher. An inbound structure is a core part in rebound attack techniques [2] and is a set of all pairs satisfying a differential trail for a part of a block cipher. In order to give an easy explanation about inbound structure of F-function (ISF), we need to use the following notations of word difference forms:(i)
0: every byte in the word has the zero difference.(ii)
Δ1: one byte has a nonzero difference and the other bytes in the word have zero differences.(iii)
ΔP(1): the word has difference forms which are the output of P on the input Δ1. That is, P(Δ1) = ΔP(1).We assume that all subkeys are known and fixed and that the number of zero entries is almost equal to that of nonzero entries in the difference distribution table (DDT) of the S-box. We set the input and output difference forms of theF-function to ΔP(1) and Δ1, respectively. Then, for all possible differences with the form of (ΔP(1), Δ1) ∈ {0, 1}ab×{0, 1}ab, every S-box in the F-function meets nonzero input and output differences. For any choice of nonzero difference pair (α, β) ∈ {0, 1}b×{0, 1}b, we call it valid if there exists any input pair whose input difference is α and the corresponding S-box output difference is β. By the assumption of DDT, the ratio of valid input and output difference pairs is around 0.5. On average, for a valid input-output difference pair (α, β), the S-box has a single input pair (x1, x2) ∈ {0, 1}b×{0, 1}b satisfying x1 + x2 = α and S(x1) + S(x2) = β. For any fixed form ΔP(1), the number of input differences of the F-function satisfying ΔP(1) is 2b − 1. For any fixed form ΔP(1), the number of input differences of the F-function satisfying Δ1 is 2b − 1. Therefore, on average, the inbound structure of the F-function (ISF) with (ΔP(1), Δ1) contains (2b − 1)2 × 2−a×2a = (2b − 1)2 ≅ 22b.We take a look at the example of ISF witha = 4 in Figure 3. Let the input differences of the four S-boxes be α0, α1, α2, and α3, and let the corresponding output differences be β0, β1, β2, and β3. Let x0,0, x0,1, x1,0, x1,1, x2,0, x2,1, x3,0, and x3,1 be the inputs of the S-box satisfying(1)xi,0+xi,1=αi,Sxi,0+Sxi,1=βi,fori∈0,1,2,3.Figure 3
Differences in the inbound structure ofF-function with a = 4.Then, all the possible input pairs of theF-function are {(x0,0, x1,0, x2,0, x3,0), (x0,1, x1,1, x2,1, x3,1)}, {(x0,1, x1,0, x2,0, x3,0), (x0,0, x1,1, x2,1, x3,1)}, {(x0,0, x1,1, x2,0, x3,0), (x0,1, x1,0, x2,1, x3,1)}, …. That is, the number of possible input pairs of the F-function is 24. Therefore, the ISF contains about (2b − 1)2 pairs because the F-function has about (2b − 1)2×2−4 possible input-output difference pairs with the form (ΔP(1), Δ1).We assume that DDT of the S-box is given in advance and that DDT contains all possible input pairs for each input and output differences. Then, the complexity of the phase checking the validity of an input-output difference pair for the S-box is dominant in the computational complexity required for constructing the ISF. It is abouta×22b table lookups ≅22bF-function evaluations because the F-function consists of a S-boxes.


### 2.3. Matyas-Meyer-Oseas and Miyaguchi-Preneel Modes

Matyas-Meyer-Oseas (MMO) and Miyaguchi-Preneel (MP) modes belong to 12 secure PGV hash modes, [15] which invoke a single call of the underlying block cipher to build a compression for a Merkle-Damgård hash function. Note that a compression function takes a message block and an input chaining variable value to produce an output chaining variable value. In both of two hash modes, the input chaining variable which cannot be controlled by anyone becomes the key of the block cipher, the message block which can be controlled by anyone becomes the plaintext block of the block cipher, and the output chaining variable is produced by XORing the ciphertext block with the plaintext block and the key. See Figure4. Throughout this paper, we assume the hash mode of GFN-2 is MMO or MP whenever we explain partial-collision attacks.Figure 4
Matyas-Meyer-Oseas (left) mode and Miyaguchi-Preneel (right) mode.


## 2.1. Type-2 Generalized Feistel Network

Let the S-boxS: {0, 1}b ⟶ {0, 1}b be a nonlinear permutation on {0, 1}b. The notation Y = S(X) means that the output of the S-box is Y ∈ {0, 1}b on the input X ∈ {0, 1}b. Let the linear function P: ({0, 1}b)a ⟶ ({0, 1}b)a be the multiplication by a×a MDS matrix over GF (2b). The notation Y = (Y0,Y1,…,Ya−1) = P(X) = P(X0,X1,…,Xa−1) means that the output vector of P is Y = (Y0,Y1,…,Ya−1) on the input vector X = (X0,X1,…,Xa−1). For the S-box S and the linear function P, we define F: {0, 1}ab×{0, 1}ab as follows: for an input X = (X0,X1,…,Xa−1) ∈ ({0, 1}b)a and a subkey RK = (RK0,RK1,…,RKa−1) ∈ ({0, 1}b)a, Y = F(X, RK) = P(SX0+RK0,SX1+RK1), where + is the XOR (eXclusive OR) operation. Figure 1 depicts the example of F-function with a = 4.Figure 1
Structure ofF-function with a = 4.Lett ≥ 4 be an even integer and r be a positive integer. For r-round t-branch GFN-2, we define all subkeys RKi,j generated from a key K as RKi,j = (RKi,j0,RKi,j1,…,RKi,ja−1) ∈ ({0, 1}b)a for 0 ≤ i < r and 0 ≤ j < t/2. We define the shuffle operation σ as σ = (σ(0), σ(1), …, σ(t − 1)) = (t – 1, 0, …, t − 2). Then, we can give the following pseudocode which describes how the r-round t-branch GFN-2 encrypts a plaintext block X0 = (X0,0, X0,1, …, X0,t−1) ∈ ({0, 1}ab)t to Xr = (Xr,0, Xr,1, …, Xr,t−1) ∈ ({0, 1}ab)t:(i)
fori = 0, 1, …, r − 1 do:(ii)
forj = 0, 1, …, t − 1 do:(iii)
ifj is even:(iv)
Yj = Xi,j(v)
else:(vi)
Yj = Xi,j + F(Xi,j−1, RKi,(j−1)/2)(vii)
forj = 0, 1, …, t − 1 do:(viii)
Xi+1,σ(j) = YjThe indexi in the above pseudocode means the round order. Figure 2 depicts the i-th round function of GFN-2 with t = 8. Throughout this paper, we assume that the key K and the subkey RKi,j’s are known and fixed. Since subkey-XORing operations are not important in the description of our work, we omit the notation and explanation about subkeys for simplicity. For example, we replace F(Xi,j−1, RKi,(j−1)/2) with F(Xi,j−1).Figure 2
Structure ofF-function with a = 4.


## 2.2. Inbound Structure ofF-Function

A difference is the XOR between two values at the same position, and a differential trail is a set of all difference transitions in a block cipher. An inbound structure is a core part in rebound attack techniques [2] and is a set of all pairs satisfying a differential trail for a part of a block cipher. In order to give an easy explanation about inbound structure of F-function (ISF), we need to use the following notations of word difference forms:(i)
0: every byte in the word has the zero difference.(ii)
Δ1: one byte has a nonzero difference and the other bytes in the word have zero differences.(iii)
ΔP(1): the word has difference forms which are the output of P on the input Δ1. That is, P(Δ1) = ΔP(1).We assume that all subkeys are known and fixed and that the number of zero entries is almost equal to that of nonzero entries in the difference distribution table (DDT) of the S-box. We set the input and output difference forms of theF-function to ΔP(1) and Δ1, respectively. Then, for all possible differences with the form of (ΔP(1), Δ1) ∈ {0, 1}ab×{0, 1}ab, every S-box in the F-function meets nonzero input and output differences. For any choice of nonzero difference pair (α, β) ∈ {0, 1}b×{0, 1}b, we call it valid if there exists any input pair whose input difference is α and the corresponding S-box output difference is β. By the assumption of DDT, the ratio of valid input and output difference pairs is around 0.5. On average, for a valid input-output difference pair (α, β), the S-box has a single input pair (x1, x2) ∈ {0, 1}b×{0, 1}b satisfying x1 + x2 = α and S(x1) + S(x2) = β. For any fixed form ΔP(1), the number of input differences of the F-function satisfying ΔP(1) is 2b − 1. For any fixed form ΔP(1), the number of input differences of the F-function satisfying Δ1 is 2b − 1. Therefore, on average, the inbound structure of the F-function (ISF) with (ΔP(1), Δ1) contains (2b − 1)2 × 2−a×2a = (2b − 1)2 ≅ 22b.We take a look at the example of ISF witha = 4 in Figure 3. Let the input differences of the four S-boxes be α0, α1, α2, and α3, and let the corresponding output differences be β0, β1, β2, and β3. Let x0,0, x0,1, x1,0, x1,1, x2,0, x2,1, x3,0, and x3,1 be the inputs of the S-box satisfying(1)xi,0+xi,1=αi,Sxi,0+Sxi,1=βi,fori∈0,1,2,3.Figure 3
Differences in the inbound structure ofF-function with a = 4.Then, all the possible input pairs of theF-function are {(x0,0, x1,0, x2,0, x3,0), (x0,1, x1,1, x2,1, x3,1)}, {(x0,1, x1,0, x2,0, x3,0), (x0,0, x1,1, x2,1, x3,1)}, {(x0,0, x1,1, x2,0, x3,0), (x0,1, x1,0, x2,1, x3,1)}, …. That is, the number of possible input pairs of the F-function is 24. Therefore, the ISF contains about (2b − 1)2 pairs because the F-function has about (2b − 1)2×2−4 possible input-output difference pairs with the form (ΔP(1), Δ1).We assume that DDT of the S-box is given in advance and that DDT contains all possible input pairs for each input and output differences. Then, the complexity of the phase checking the validity of an input-output difference pair for the S-box is dominant in the computational complexity required for constructing the ISF. It is abouta×22b table lookups ≅22bF-function evaluations because the F-function consists of a S-boxes.


## 2.3. Matyas-Meyer-Oseas and Miyaguchi-Preneel Modes

Matyas-Meyer-Oseas (MMO) and Miyaguchi-Preneel (MP) modes belong to 12 secure PGV hash modes, [15] which invoke a single call of the underlying block cipher to build a compression for a Merkle-Damgård hash function. Note that a compression function takes a message block and an input chaining variable value to produce an output chaining variable value. In both of two hash modes, the input chaining variable which cannot be controlled by anyone becomes the key of the block cipher, the message block which can be controlled by anyone becomes the plaintext block of the block cipher, and the output chaining variable is produced by XORing the ciphertext block with the plaintext block and the key. See Figure4. Throughout this paper, we assume the hash mode of GFN-2 is MMO or MP whenever we explain partial-collision attacks.Figure 4
Matyas-Meyer-Oseas (left) mode and Miyaguchi-Preneel (right) mode.


## 3. Inbound Structure of GFN-2

We explore the inbound structures of GFN-2 (ISG2) which minimize nonzero difference words with the form Δ1. Such ISG2s have relatively long difference propagation in forward and backward directions and best attacks on hash modes. We suggest a general methodology to construct differential trails suitable for good ISG2s as follows:(1)
Set the round numberR of ISG2 to an intended positive integer.(2)
Select the number of ISFs and randomly choose the application positions of ISFs. For each chosen position, set the input and output differences of theF-function to ΔP(1) and Δ1, respectively.(3)
Use only the difference forms 0, Δ1, and ΔP(1) to propagate and adjust the differences from ISFs in forward and backward directions such that nonzero differences are minimized.(4)
Check whether the input and output differences of ISG2 have the minimum number of nonzero word differences with the form Δ1. If it is, return the differential trail; otherwise, go to Step (2).We assume that the position of nonzero byte in Δ1 is the same as that in P−1(ΔP(1)) and that all subkeys are known and fixed. Let “?” be an unknown difference. We use the notation “0,” “Δ1,” “ΔP(1),” and “?” to represent the difference forms. We make them correspond to binary codes 002, 012, 102, and 112. Then, the difference form of two consecutive words can be represented in hexadecimal digits like Table 1. For example, (Δ1, ΔP(1)) and (ΔP(1), Δ1) are 0×6 and 0×9, respectively.Table 1
Hexadecimal representation for two consecutive words.
0Δ1ΔP(1)?00x00x10x20x3Δ10x40x50x60x7ΔP(1)0x80x90xA0xB?0xC0xD0xE0xF


## 4. Attacks on 4-Branch GFN-2

### 4.1. 5-Round Inbound Structure

We make the 5-round inbound structure satisfying the differential trail in Figure5. It is represented as a hexadecimal vector (0×40, 0×81, 0×46, 0×91, 0×06, 0×10) by Table 1. The input state of ISG2 is X0 = (X0,0, X0,1, X0,2, X0,3) and the output state of the i-th round is Xi+1 = (Xi+1,0, Xi+1,1, Xi+1,2, Xi+1,3) for i ∈ {0, 1, 2, 3, 4}. Let ΔXi,j be the difference at Xi,j and let ΔF(Xi,j) be the difference at F(Xi,j). We use two ISFs to find pairs contained in the 5-round ISG2 according to the following steps:(1)
Apply the ISF to theF-function taking X1,0 as input. Store about 22b pairs satisfying the input difference with the form ΔP(1) and the output difference with the form Δ1 for the F-function, in a table named ISF-1.(2)
Apply the ISF to theF-function taking X3,0 as input, independently of Step (1). Store about 22b pairs satisfying the input difference with the form ΔP(1) and the output difference with the form Δ1 for the F-function, in a table named ISF-2.(3)
Choose a random value forX0,2 and compute F(X0,2). Then, compute X2,0 and F(X2,0) for all values of F(X1,0) in ISF-1.(4)
Choose a random value forX4,0 (=X5,3) and compute F(X4,0). Then, compute X2,2 and F(X2,2) for all values of F(X3,0) in ISF-2.(5)
For ΔF(X2,0) and ΔX1,0 from a pair (x1, x2) ∈ ISF-1 and for ΔX3,0 and ΔF(X2,2) from a pair (y1, y2) ∈ ISF-2, combine the pairs to {(x1, y1), (x2, y2)} if ΔF(X2,0) = ΔX3,0 and ΔX1,0 = ΔF(X2,2). For all the pairs in ISF-1 and all the pairs in ISF-2, store the combined pairs in a table named ISF-(1, 2). On average, ISF-(1, 2) contains 22b (combined) pairs.(6)
For all pairs in ISF-(1, 2), computeF(X1,2) and F(X0,0), and discard the pairs where the difference at F(X0,0) is not equal to the difference at X1,0. On average, 2b pairs survive.(7)
For all surviving pairs, computeF(X3,2) and F(X4,2), and discard the pairs where the difference at F(X4,2) is not equal to the difference at X3,0. On average, 1 pair survives.(8)
For all surviving pairs, computeX0,1, X0,3, X5,0, and X5,2, and store the resulting pairs in ISG2.Figure 5
Differential trail for the 5-round inbound structure of 4-branch GFN-2.For fixed values ofX0,1 and X5,3, the above 5-round ISG2 has one pair on average. The computational complexity required for constructing a 5-round ISG2 is estimated 9×22bF-function evaluations. We denote it by T ≅ 9·22bF. This estimation is based on the following:(i)
The construction of ISFs for Steps (1) and (2) requires 22bF because essentially, a single set of ISF can be applied to two positions.(ii)
The complexity of Step (3) is 22b+1F because F(X2,0) is computed for 22b+1 times.(iii)
The complexity of Step (4) is 22b+1F because F(X2,2) is computed for 22b+1 times.(iv)
The complexity of Step (6) is 22b+2F because F(X1,2) is computed for 22b+1 times and F(X0,0) is computed for 22b+1 times.(v)
The complexity of Step (7) is 2b+2F (=2×2×2bF) because F(X3,2) is computed for 2b+1 times and F(X4,2) is computed for 2b+1 times.So, if we chooseN random values of (X0,1, X5,3), the 5-round ISG2 contains N pairs and the corresponding complexity is NT.


### 4.2. Known-Key Distinguisher

We can get a differential trail in Table2 by propagating differences from the 5-round ISG2 in forward and backward directions. ΔXi = (ΔXi,0, …, ΔXi,3) is the representation of the difference of the state. ISG2 covers from ΔX0 to ΔX5, the backward propagation covers from ΔX−1 to ΔX−5, and the forward propagation covers from ΔX+1 to ΔX+5. The rebound attack framework calls this propagation, Outbound Phase [2]. In this phase, the transition between the input and output difference forms under the F-function is determined by the rule in Table 3.Table 2
Difference propagation from the 5-round inbound structure of 4-branch GFN-2.
iΔXi,0ΔXi,1ΔXi,2ΔXi,3–5??ΔP(1)?–4Δ1ΔP(1)??–3ΔP(1)?0Δ1–200Δ1ΔP(1)–10Δ1000Δ10001ΔP(1)00Δ12Δ10Δ1ΔP(1)3ΔP(1)00Δ1400Δ1ΔP(1)50Δ100+1Δ1000+2ΔP(1)00Δ1+3?0Δ1ΔP(1)+4?Δ1ΔP(1)?+5?ΔP(1)??Table 3
Transition between the input and output difference forms under theF-function in the outbound phase.
Input differenceOutput difference00Δ1ΔP(1)ΔP(1)???The differential trail in Table2 is represented as 0xFB ⟶ 0xEF by hexadecimal digits. In Table 2, the difference form at Xi,j is denoted by ΔXi,j. In the case of ideal cipher with the block length of abt bits, we explain how to find at least one pair satisfying 0xFB ⟶ 0xEF. Firstly, we make a set of 2babt-bit values such that all possible byte values appear at the nonzero byte difference, which is indicated by the difference form ΔP(1), and a randomly chosen constant value is at the zero byte differences. After applying the linear function P to the third words of the elements in the set, we get about 22b−1 pairs with the difference form (?, ?, ΔP(1), ?). Then, the output difference form is (?, ΔP(1), ?, ?) with the probability 2−(a−1)b, and we get 2(−a+3)b−1 = 22b−1×2−(a−1)b pairs satisfying 0×FB ⟶ 0×EF. Since a = 4 or a = 8 in the block cipher designs, (−a + 3)b − 1 is a negative integer. Therefore, we expect a pair satisfying 0xFB ⟶ 0xEF by repeating this work 2(a−3)b+1 = 1/2(−a+3)−1 times, and the complexity is 2(a−2)b+1 = 2b×2(a−3)b+1.In the case of 4-branch GFN-2, we can get one pair satisfying 0xFB ⟶ 0xEF with 9×22bF = 9×22b/30 because a pair contained in the 5-round ISG2 satisfies 0xFB ⟶ 0xEF, the complexity required in the computation of the outbound phase is negligible, and one evaluation of the 15-round 4-branch GFN-2 requires 30 evaluations of the F-function. When a = 4 or a = 8, the complexity in the case of GFN-2 is lower than that of the ideal cipher and so, 0xFB ⟶ 0xEF can be used as a valid 15-round known-key distinguisher. By the way, the attack advantage in the case of a = 4 is much smaller than that of a = 8.The summary of the attack complexity can be seen in Table4. The validity of the distinguishing attack has nothing to do with the existence of the shuffle operation in the last round, but we just write the distinguishing attack result in the case that the shuffle operation exists in the last round.Table 4
Known-key distinguishing andw-word partial-collision attacks on 4-branch GFN-2.
LRKKDwComp.Generic(a, b)Y15(0xFB, 0xEF)—22b−1.732(a−2)b+1All14(0xFB, 0xDB), (0x6F, 0xEF)123b−1.632ab/2(8, ∗)10(0xB1, 0x81), (0x06, 0xC6)324b−1.1523ab/2AllN15(0xFB, 0xB)123b−1.732ab/2(8, ∗)11(0xB1, 0x81)324b−1.2923ab/2All


### 4.3. Partial-Collision Attacks

The partial-collision attacks derived from Table2 are summarized in Table 4. The “L” column in Table 4 means the existence of the last shuffle operation; if the last shuffle operation exists, its entry is “Y”; otherwise, its entry is “N.” The “R” column means the number of attacked rounds. The “KKD” column means the known-key distinguisher used in each attack; the entry is written with the forms of input difference and output difference. The “w” column means the number of words colliding at the output chaining variable in the partial-collision attack. For the first attack in Table 4, its entry is written as “−” because it is a just distinguishing attack. The “Comp.” column means the complexity required for the known-key distinguishing attack or partial-collision attack on 4-branch GFN-2, and the “Generic” column means the complexity required for the known-key distinguishing attack on the ideal cipher with abt-bit block or the birthday attack on a random function with abt-bit output length. Finally, the “(a, b)” column means the value of (a, b) which makes the attack valid; its entry is written as “all” if the attack is valid for all values of (a, b); its entry is written as “(8, ∗)” if the attack is valid only for a = 8.The second attack in Table4 uses known-key distinguishers (?, ?, ΔP(1), ?) ⟶ (?, Δ1, ΔP(1), ?) or (Δ1, ΔP(1), ?, ?) ⟶ (?, ΔP(1), ?, ?), and we expect a 1-word partial collision by trying 2b pairs in ISG2. Since it covers 14 rounds, the complexity is estimated as 2b×(9×22b)/28 = 23b−1.63. This attack is valid only for a = 8 because the complexity is lower than 2ab/2 when a = 8.The third attack in Table4 uses known-key distinguishers (ΔP(1), ?, 0, Δ1) ⟶ (ΔP(1), 0, 0, Δ1) or (0, 0, Δ1, ΔP(1)) ⟶ (?, 0, Δ1, ΔP(1)), and we expect a 3-word partial collision by 22b pairs in ISG2. Since it covers 10 rounds, the complexity is estimated as 22b×(9×22b)/20 = 23b−1.15. This attack is valid for all values (a, b) ∈ {(4, 4), (4, 8), (8, 4), (8, 8)}.The fourth and fifth attacks in Table4 use known-key distinguishers (?, ?, ΔP(1), ?) ⟶ (?, ?, ΔP(1), ?) and (ΔP(1), ?, 0, Δ1) ⟶ (ΔP(1), 0, 0, Δ1), respectively, under the assumption that the last round has no shuffle operation. The complexity and validity of them are understood by the similar way to the second and third attacks.


## 4.1. 5-Round Inbound Structure

We make the 5-round inbound structure satisfying the differential trail in Figure5. It is represented as a hexadecimal vector (0×40, 0×81, 0×46, 0×91, 0×06, 0×10) by Table 1. The input state of ISG2 is X0 = (X0,0, X0,1, X0,2, X0,3) and the output state of the i-th round is Xi+1 = (Xi+1,0, Xi+1,1, Xi+1,2, Xi+1,3) for i ∈ {0, 1, 2, 3, 4}. Let ΔXi,j be the difference at Xi,j and let ΔF(Xi,j) be the difference at F(Xi,j). We use two ISFs to find pairs contained in the 5-round ISG2 according to the following steps:(1)
Apply the ISF to theF-function taking X1,0 as input. Store about 22b pairs satisfying the input difference with the form ΔP(1) and the output difference with the form Δ1 for the F-function, in a table named ISF-1.(2)
Apply the ISF to theF-function taking X3,0 as input, independently of Step (1). Store about 22b pairs satisfying the input difference with the form ΔP(1) and the output difference with the form Δ1 for the F-function, in a table named ISF-2.(3)
Choose a random value forX0,2 and compute F(X0,2). Then, compute X2,0 and F(X2,0) for all values of F(X1,0) in ISF-1.(4)
Choose a random value forX4,0 (=X5,3) and compute F(X4,0). Then, compute X2,2 and F(X2,2) for all values of F(X3,0) in ISF-2.(5)
For ΔF(X2,0) and ΔX1,0 from a pair (x1, x2) ∈ ISF-1 and for ΔX3,0 and ΔF(X2,2) from a pair (y1, y2) ∈ ISF-2, combine the pairs to {(x1, y1), (x2, y2)} if ΔF(X2,0) = ΔX3,0 and ΔX1,0 = ΔF(X2,2). For all the pairs in ISF-1 and all the pairs in ISF-2, store the combined pairs in a table named ISF-(1, 2). On average, ISF-(1, 2) contains 22b (combined) pairs.(6)
For all pairs in ISF-(1, 2), computeF(X1,2) and F(X0,0), and discard the pairs where the difference at F(X0,0) is not equal to the difference at X1,0. On average, 2b pairs survive.(7)
For all surviving pairs, computeF(X3,2) and F(X4,2), and discard the pairs where the difference at F(X4,2) is not equal to the difference at X3,0. On average, 1 pair survives.(8)
For all surviving pairs, computeX0,1, X0,3, X5,0, and X5,2, and store the resulting pairs in ISG2.Figure 5
Differential trail for the 5-round inbound structure of 4-branch GFN-2.For fixed values ofX0,1 and X5,3, the above 5-round ISG2 has one pair on average. The computational complexity required for constructing a 5-round ISG2 is estimated 9×22bF-function evaluations. We denote it by T ≅ 9·22bF. This estimation is based on the following:(i)
The construction of ISFs for Steps (1) and (2) requires 22bF because essentially, a single set of ISF can be applied to two positions.(ii)
The complexity of Step (3) is 22b+1F because F(X2,0) is computed for 22b+1 times.(iii)
The complexity of Step (4) is 22b+1F because F(X2,2) is computed for 22b+1 times.(iv)
The complexity of Step (6) is 22b+2F because F(X1,2) is computed for 22b+1 times and F(X0,0) is computed for 22b+1 times.(v)
The complexity of Step (7) is 2b+2F (=2×2×2bF) because F(X3,2) is computed for 2b+1 times and F(X4,2) is computed for 2b+1 times.So, if we chooseN random values of (X0,1, X5,3), the 5-round ISG2 contains N pairs and the corresponding complexity is NT.


## 4.2. Known-Key Distinguisher

We can get a differential trail in Table2 by propagating differences from the 5-round ISG2 in forward and backward directions. ΔXi = (ΔXi,0, …, ΔXi,3) is the representation of the difference of the state. ISG2 covers from ΔX0 to ΔX5, the backward propagation covers from ΔX−1 to ΔX−5, and the forward propagation covers from ΔX+1 to ΔX+5. The rebound attack framework calls this propagation, Outbound Phase [2]. In this phase, the transition between the input and output difference forms under the F-function is determined by the rule in Table 3.Table 2
Difference propagation from the 5-round inbound structure of 4-branch GFN-2.
iΔXi,0ΔXi,1ΔXi,2ΔXi,3–5??ΔP(1)?–4Δ1ΔP(1)??–3ΔP(1)?0Δ1–200Δ1ΔP(1)–10Δ1000Δ10001ΔP(1)00Δ12Δ10Δ1ΔP(1)3ΔP(1)00Δ1400Δ1ΔP(1)50Δ100+1Δ1000+2ΔP(1)00Δ1+3?0Δ1ΔP(1)+4?Δ1ΔP(1)?+5?ΔP(1)??Table 3
Transition between the input and output difference forms under theF-function in the outbound phase.
Input differenceOutput difference00Δ1ΔP(1)ΔP(1)???The differential trail in Table2 is represented as 0xFB ⟶ 0xEF by hexadecimal digits. In Table 2, the difference form at Xi,j is denoted by ΔXi,j. In the case of ideal cipher with the block length of abt bits, we explain how to find at least one pair satisfying 0xFB ⟶ 0xEF. Firstly, we make a set of 2babt-bit values such that all possible byte values appear at the nonzero byte difference, which is indicated by the difference form ΔP(1), and a randomly chosen constant value is at the zero byte differences. After applying the linear function P to the third words of the elements in the set, we get about 22b−1 pairs with the difference form (?, ?, ΔP(1), ?). Then, the output difference form is (?, ΔP(1), ?, ?) with the probability 2−(a−1)b, and we get 2(−a+3)b−1 = 22b−1×2−(a−1)b pairs satisfying 0×FB ⟶ 0×EF. Since a = 4 or a = 8 in the block cipher designs, (−a + 3)b − 1 is a negative integer. Therefore, we expect a pair satisfying 0xFB ⟶ 0xEF by repeating this work 2(a−3)b+1 = 1/2(−a+3)−1 times, and the complexity is 2(a−2)b+1 = 2b×2(a−3)b+1.In the case of 4-branch GFN-2, we can get one pair satisfying 0xFB ⟶ 0xEF with 9×22bF = 9×22b/30 because a pair contained in the 5-round ISG2 satisfies 0xFB ⟶ 0xEF, the complexity required in the computation of the outbound phase is negligible, and one evaluation of the 15-round 4-branch GFN-2 requires 30 evaluations of the F-function. When a = 4 or a = 8, the complexity in the case of GFN-2 is lower than that of the ideal cipher and so, 0xFB ⟶ 0xEF can be used as a valid 15-round known-key distinguisher. By the way, the attack advantage in the case of a = 4 is much smaller than that of a = 8.The summary of the attack complexity can be seen in Table4. The validity of the distinguishing attack has nothing to do with the existence of the shuffle operation in the last round, but we just write the distinguishing attack result in the case that the shuffle operation exists in the last round.Table 4
Known-key distinguishing andw-word partial-collision attacks on 4-branch GFN-2.
LRKKDwComp.Generic(a, b)Y15(0xFB, 0xEF)—22b−1.732(a−2)b+1All14(0xFB, 0xDB), (0x6F, 0xEF)123b−1.632ab/2(8, ∗)10(0xB1, 0x81), (0x06, 0xC6)324b−1.1523ab/2AllN15(0xFB, 0xB)123b−1.732ab/2(8, ∗)11(0xB1, 0x81)324b−1.2923ab/2All


## 4.3. Partial-Collision Attacks

The partial-collision attacks derived from Table2 are summarized in Table 4. The “L” column in Table 4 means the existence of the last shuffle operation; if the last shuffle operation exists, its entry is “Y”; otherwise, its entry is “N.” The “R” column means the number of attacked rounds. The “KKD” column means the known-key distinguisher used in each attack; the entry is written with the forms of input difference and output difference. The “w” column means the number of words colliding at the output chaining variable in the partial-collision attack. For the first attack in Table 4, its entry is written as “−” because it is a just distinguishing attack. The “Comp.” column means the complexity required for the known-key distinguishing attack or partial-collision attack on 4-branch GFN-2, and the “Generic” column means the complexity required for the known-key distinguishing attack on the ideal cipher with abt-bit block or the birthday attack on a random function with abt-bit output length. Finally, the “(a, b)” column means the value of (a, b) which makes the attack valid; its entry is written as “all” if the attack is valid for all values of (a, b); its entry is written as “(8, ∗)” if the attack is valid only for a = 8.The second attack in Table4 uses known-key distinguishers (?, ?, ΔP(1), ?) ⟶ (?, Δ1, ΔP(1), ?) or (Δ1, ΔP(1), ?, ?) ⟶ (?, ΔP(1), ?, ?), and we expect a 1-word partial collision by trying 2b pairs in ISG2. Since it covers 14 rounds, the complexity is estimated as 2b×(9×22b)/28 = 23b−1.63. This attack is valid only for a = 8 because the complexity is lower than 2ab/2 when a = 8.The third attack in Table4 uses known-key distinguishers (ΔP(1), ?, 0, Δ1) ⟶ (ΔP(1), 0, 0, Δ1) or (0, 0, Δ1, ΔP(1)) ⟶ (?, 0, Δ1, ΔP(1)), and we expect a 3-word partial collision by 22b pairs in ISG2. Since it covers 10 rounds, the complexity is estimated as 22b×(9×22b)/20 = 23b−1.15. This attack is valid for all values (a, b) ∈ {(4, 4), (4, 8), (8, 4), (8, 8)}.The fourth and fifth attacks in Table4 use known-key distinguishers (?, ?, ΔP(1), ?) ⟶ (?, ?, ΔP(1), ?) and (ΔP(1), ?, 0, Δ1) ⟶ (ΔP(1), 0, 0, Δ1), respectively, under the assumption that the last round has no shuffle operation. The complexity and validity of them are understood by the similar way to the second and third attacks.


## 5. Attacks on 6-Branch GFN-2

We make a 7-round ISG2 for 6-branch GFN-2, and the corresponding differential trail is represented as a hexadecimal vector (0×400, 0×801, 0×406, 0×811, 0×446, 0×991, 0×606, 0×011). We use four ISFs to find the pairs for the 7-round ISG2 according to the following steps:(1)
Apply ISFs to theF-functions taking X1,0, X3,0, X5,0, and X5,2 as inputs. Call them ISF-1, ISF-2, ISF-3, and ISF-4, respectively.(2)
Choose a random value forX0,2 to compute F(X0,2), and compute F(X2,0) for all values of F(X1,0) in ISF-1. Then, for ΔF(X2,0) associated to a pair (x1, x2) ∈ ISF-1 and for ΔX3,0 from a pair (y1, y2) ∈ ISF-2, combine the pairs to {(x1, y1), (x2, y2)} if ΔF(X2,0) = ΔX3,0. For all the pairs in ISF-1 and all the pairs in ISF-2, store the combined pairs in a table named ISF-(1, 2). On average, ISF-(1, 2) contains 23b = 22b×22b×2−b pairs.(3)
Choose a random value forX7,1 (=X6,2) to compute F(X6,2), and compute F(X4,4) for all values of F(X5,2) in ISF-4. Then, for ΔF(X4,4) associated to a pair (z1, z2) ∈ ISF-4 and for ΔX3,0 from a pair {(x1, y1), (x2, y2)} ∈ ISF-(1, 2), combine the pairs to {(x1, y1, z1), (x2, y2, z2)} ∈ if ΔF(X4,4) = ΔX3,0. For all pairs in ISF-4 and all pairs in ISF-(1, 2), store the combined pairs in a table named ISF-(1, 2, 4). On average, ISF-(1, 2, 4) contains 22b×23b × 2– b = 24b pairs.(4)
For each pair in ISF-(1, 2, 4), discard it if ΔX3,5 ≠ ΔX4,4. On average, ISF-(1, 2, 4) contains 24b×2−b = 23b pairs after this filtering.(5)
For each pair in ISF-(1, 2, 4), computeX3,4, X2,4, and X4,2, and discard the pair if ΔX2,4 ≠ ΔX4,2. On average, ISF-(1, 2, 4) contains 23b×2−b = 22b after this filtering.(6)
For all pairs {(x1, y1, z1), (x2, y2, z2)} in ISF-(1, 2, 4) and all pairs (v1, v2) in ISF-3, compute X3,2 and X4,0. Then, combine the pairs to {(x1, y1, z1, v1), (x2, y2, z2, v2)} if ΔX4,0 = ΔF(X3,0), and store the combined pairs in a table ISG2. On average, ISG2 contains 22b×22b×2−b = 23b pairs.(7)
For each pair in ISG2, computeX6,0 and F(X6,0) and then discard the pair if ΔX6,0 = 0 or ΔF(X6,0) ≠ ΔX5,2. On average, ISG2 contains 23b×2−b = 22b pairs after this filtering.(8)
For each pair in ISG2, computeF(X5,4) and F(X6,4), and then discard the pair if ΔF(X6,4) ≠ ΔX5,0. On average, ISG2 contains 22b×2−b = 2b pairs after this filtering.(9)
For each surviving pair in ISG2, compute the remaining parts includingF(X0,0), and discard the pair if ΔF(X0,0) ≠ ΔX1,0. On average, ISG2 contains 2b×2−b = 1 pair after this filtering.That is, for a fixedX0,2 and X7,1, we can find a pair for the 7-round ISG2 of 6-branch GFN-2. The complexity of the above procedure is about 24b+1F. It is based on the following and we can see that the complexity of Step (6) is dominant:(i)
The construction of ISFs for Step (1) requires 22bF.(ii)
The complexity of Step (2) is 22b+1F because F(X2,0) is computed for 22b+1 times.(iii)
The complexity of Step (3) is 22b+1F because F(X4,4) is computed for 22b+1 times.(iv)
The complexity of Step (5) is 3×23b+1F because X3,4 = F−1(X2,0 + X4,4), X2,4 = F−1(X1,0 + X3,4), and X4,2 = F−1 (X3,4 + X5,2) are computed for 23b+1 times, where we assume that the evaluation of F−1 requires the same complexity as F.(v)
The complexity of Step (6) is 24b+1F because X3,2 = F−1(X2,4 + X4,2) is computed for 22b+1 times and F−1(X3,2 + X5,0) is computed for 24b+1 times.(vi)
The complexity of Step (7) is 23b+1F because F(X6,0) is computed for 23b+1 times.(vii)
The complexity of Step (8) is 22b+2F because F(X5,4) and F(X6,4) are computed for 22b+1 times.(viii)
The complexity of Steps (4) and (9) is negligible compared to the other steps.Table5 summarizes known-key distinguishing and partial-collision attacks on 6-branch GFN-2, based on the 7-round ISG2. The first attack in Table 5 is a 19-round known-key distinguishing attack. The condition that a known-key distinguisher for 6-branch GFN-2 is valid for all values of (a, b) is that the distinguisher has more than two nonzero words in both input and output differences. The 17-round known-key distinguisher 0x6FF ⟶ 0xBFD is the longest one which is valid for all values of (a, b). Table 5 shows that the partial-collision attacks on 6-branch GFN-2 are valid only for a = 8.Table 5
Known-key distinguishing andw-word partial-collision attacks on 6-branch GFN-2.
LRKKDwComp.Generic(a, b)Y19(0xFBF, 0xFFE)—24b–4.832(a−2)b+1(8, ∗)17(0x6FF, 0xBFD)—24b–4.7622(a−1)b+1All16(0x6FF, 0x6EC), (0xBF1, 0xBFD)226b–4.592ab(8, ∗)N17(0x6FF, 0x6FF)226b–4.672ab(8, ∗)


## 6. Attacks on 8-Branch GFN-2

We make a 11-round ISG2 for 8-branch GFN-2, and the corresponding differential trail is represented as a hexadecimal vector (0 × 4000, 0 × 8001, 0 × 4006, 0 × 8011, 0 × 4046, 0 × 8191, 0 × 4606, 0 × 9011, 0 × 0046, 0 × 0190, 0 × 0600, 0 × 1000). The procedure finding a pair for the 11-round ISG2 of 8-branch GFN-2 is described as follows:(1)
Apply six ISFs to theF-functions taking X1,0, X3,0, X5,0, X5,4, X7,0, and X9,4 as inputs. Call them ISF-1, ISF-2, ISF-3, ISF-4, ISF-5, and ISF-6, respectively.(2)
Choose a random value forX0,2 to compute F(X0,2) for all values of F(X1,0) in ISF-1. Then, for ΔF(X2,0) associated to a pair (x1, x2) ∈ ISF-1 and for ΔX3,0 associated to a pair (y1, y2) ∈ ISF-2, combine the pairs to {(x1, y1), (x2, y2)} if ΔF(X2,0) = ΔX3,0. For all the pairs in ISF-1 and all the pairs in ISF-2, store the combined pairs in a table named ISF-(1, 2). On average, ISF-(1,2) contains 22b×22b×2−b = 23b pairs.(3)
Choose a random value forX11,3 to compute F(X8,6) for all values of F(X9,4) in ISF-6. Then, for ΔF(X8,6) associated to a pair (z1, z2) ∈ ISF-6 and for ΔX7,0 associated to a pair (v1, v2) ∈ ISF-5, combine the pairs to {(z1, v1), (z2, v2)} if ΔF(X8,6) = ΔX7,0. For all the pairs in ISF-6 and all the pairs in ISF-5, store the combined pairs in a table named ISF-(5, 6). On average, ISF-(5,6) contains 22b×22b×2−b = 23b pairs.(4)
Choose a random value forX8,5 to compute F(X7,6) and F(X6,0) for all the pairs in ISF-(5, 6). Then, discard the pairs from ISF-(5, 6) if ΔF(X6,0) ≠ ΔX7,0. On average, ISF-(5, 6) contains 23b×2−b = 22b pairs after this filtering.(5)
For ΔF(X5,0) associated to a pair (u1, u2) ∈ ISF-3 and for ΔX6,0 associated to a pair {(z1, v1), (z2, v2)} ∈ ISF-(5,6), combine the pairs to {(z1, v1, u1), (z2, v2, u2)} if ΔF(X5,0) = ΔX6,0. For all the pairs in ISF-3 and all the pairs in ISF-(5, 6), store the combined pairs in a table named ISF-(3, 5, 6). On average, ISF-(3, 5, 6) contains 22b×22b×2−b = 23b pairs.(6)
For all the pairs in ISF-(3, 5, 6), computeX6,6 = F−1(X7,6 + X5,0) and X8,4 = F−1(X7,6 + X9,4). Discard the pairs from ISF-(3, 5, 6) if ΔX6,6 ≠ ΔX8,4. On average, ISF-(3, 5, 6) contains 23b×2−b = 22b pairs.(7)
Choose a random value forX0,4 to compute F(X1,2), X2,2, and X4,0 for the pairs in ISF-(1, 2). For ΔX4,0 associated to a pair {(x1, y1), (x2, y2)} ∈ ISF-(1, 2) and for ΔX6,6 associated to a pair {(z1, v1, u1), (z2, v2, u2)} ∈ ISF-(3, 5, 6), combine the pairs to {(x1, y1, z1, v1, u1), (x2, y2, z2, v2, u2)} if ΔX4,0 = ΔX6,6. For all the pairs in ISF-(1, 2) and all the pairs in ISF-(3, 5, 6), store the combined pairs in a table named ISF-(1, 2, 3, 5, 6). On average, ISF-(1, 2, 3, 5, 6) contains 23b×22b×2−b = 24b pairs.(8)
For all the pairs in ISF-(1, 2, 3, 5, 6), computeF(X4,0). Discard the pairs from ISF-(1, 2, 3, 5, 6) if ΔF(X4,0) ≠ ΔX5,0. On average, ISF-(1, 2, 3, 5, 6) contains 24b×2−b = 23b pairs after this filtering.(9)
For all the pairs in ISF-(1, 2, 3, 5, 6), computeX5,6 = F−1(X6,6 + X4,0) and X4,6 = F−1(X5,6 + X3,0). Discard the pairs from ISF-(1, 2, 3, 5, 6) if ΔX4,6 ≠ ΔX2,0. On average, ISF-(1, 2, 3, 5, 6) contains 23b×2−b = 22b.(10)
For ΔF(X5,4) associated to a pair (q1, q2) ∈ ISF-4 and for ΔX4,6 associated to a pair {(x1, y1, z1, v1, u1), (x2, y2, z2, v2, u2)} ∈ ISF-(1, 2, 3, 5, 6), combine the pairs to {(x1, y1, z1, v1, u1, q1), (x2, y2, z2, v2, u2, q2)} if ΔF(X5,4) = ΔX4,6. For all the pairs in ISF-4 and all the pairs in ISF-(1, 2, 3, 5, 6), store the combined pairs in ISG2. On average, ISG2 contains 22b×22b×2−b = 23b.(11)
Compute the remaining parts. There are four filtering points with the ratio 2−b. Therefore, after all computations, on average, ISG2 contains 2−4b×23b = 2−b pairs.If the above procedure is repeated 2b times, we expect to find one pair for the 11-round ISG2 of 8-branch GFN-2. And, the complexity of Step (8) is 24b+1F and much more dominant than the other steps. Therefore, the complexity of obtaining one pair for the ISG2 is 25b+1F$. The attacks based on the ISG2 are summarized in Table 6. The third attack in Table 6 is valid for (a, b) = (4, 4), (8, 4), and (8, 8). So, we denote the corresponding entry of the “(a, b)” column by ¬(4, 8).Table 6
Known-key distinguishing andw-word partial-collision attacks on 8-branch GFN-2.
LRKKDwComp.Generic(a, b)Y29(0xFBFF, 0xEFFF)—25b−5.862(a−2)b+1(8, ∗)21(0x6FFF, 0xDBFF)—25b−5.7622(a−1)b+1All27(0xF01B, 0xC06F), (0x006F, 0xC1BF)225b−5.392ab¬(4, 8)20(0xF01B, 0xC01B), (0x006F, 0xC06F)527b−5.3225ab/2AllN21(0xF01B, 0xF01B)527b−5.3925ab/2All


## 7. Conclusion

In this paper, we analyzed the security of GFN-2 in the known-key setting. We improved the results of 4-branch GFN-2 presented in \cite{KangHoMoKwSuHo12}. We also presented the first known-key distinguishing and partial-collision attacks on 6-branch and 8-branch GFN-2 structures. We explained each attack such that the complexity and validity are easily understood. Our attacks do not mean that any block cipher with GFN-2 structure is insecure but can be useful and helpful in having an insight about the security of GFN-2 in known-key settings and in designing a new block cipher or hash function.



---

*Source: 8864102-2020-10-28.xml*