In spite of the research for a linear layer of Type-2 Generalized Feistel Network (Type-2 GFN) over more than 10 years, finding a good 32-branch permutation for Type-2 GFN is still a very hard task due to a huge search space. In terms of the diffusion property, Suzaki and Minematsu investigated the required number of rounds to achieve the full diffusion when the branch number is up to 16. After that, Derbez et al. presented a class of 32-branch permutations that achieves the 9-round full diffusion and they prove that this is optimal. However, this class is not suitable to be used in Type-2 GFN because it requires a large number of rounds to ensure a sufficient number of active S-boxes. In this paper, we present how to find a good class of 32-branch permutations for Type-2 GFN. To achieve this goal, we convert Type-2 GFN into a LBlock-like structure, and then we evaluate the diffusion property and the resistance against major attacks, such as differential, linear, impossible differential and integral attacks by an MILP. As a result, we present a good class of 32-branch permutations that achieves the 10-round full diffusion, ensures differentially/linearly active S-boxes of 66 at 19 round, and has the 18/20-round impossible differential/integral distinguisher, respectively. The 32-branch permutation used in WARP was chosen among this class.

Tweakable block cipher (TBC) is an extension of conventional block cipher. We study how to build a TBC based on generalized Feistel structure (GFS), a classical block cipher construction. While known dedicated TBC proposals are based on substitution-permutation network (SPN), GFS has not been used for building TBC. In particular, we take 64-bit GFS block cipher TWINE and try to make it tweakable with a minimum change. To find a best one from a large number of candidates, we performed a comprehensive search with a help of mixed integer linear programming (MILP) solver. As a result, our proposal TWINE is quite efficient, has the same number of rounds as TWINE with extremely simple tweak schedule.

(m+k,m)-functions with good cryptographic properties when 1≤k

An integral attack is one of the most powerful attacks against block ciphers. We propose a new technique for the integral attack called the Fast Fourier Transform (FFT) key recovery. When N chosen plaintexts are required for the integral characteristic and the guessed key is k bits, a straightforward key recovery requires the time complexity of O(N2k). However, the FFT key recovery only requires the time complexity of O(N+k2k). As a previous result using FFT, at ICISC 2007, Collard etal proposed that FFT can reduce the time complexity of a linear attack. We show that FFT can also reduce the complexity of the integral attack. Moreover, the estimation of the complexity is very simple. We first show the complexity of the FFT key recovery against three structures, the Even-Mansour scheme, a key-alternating cipher, and the Feistel structure. As examples of these structures, we show integral attacks against Prøst, AES, PRESENT, and CLEFIA. As a result, an 8-round Prøst P128,K can be attacked with about an approximate time complexity of 279.6. For the key-alternating cipher, a 6-round AES and a 10-round PRESENT can be attacked with approximate time complexities of 251.7 and 297.4, respectively. For the Feistel structure, a 12-round CLEFIA can be attacked with approximate time complexities of 287.5.

In this paper, we deal with upper bounds for the security of some Feistel networks. Such a topic has been discussed since the introduction of Luby-Rackoff construction. The Luby-Rackoff construction is unrealistic because its round functions must be chosen at random from the set of all functions. Knudsen dealt with a more practical construction whose round functions are chosen at random from a family of 2k randomly chosen functions, and showed an upper bound for the security by demonstrating generic key recovery attacks. However it is still difficult for designers to choose functions randomly. Then, this paper considers the security of some Feistel networks which have more efficient and practical round functions, and such Feistel networks are indeed used by some Feistel ciphers in practice. We show new properties using the relationship between plaintexts and ciphertexts. We propose new generic key recovery attacks by using our properties, and confirm the feasibility by implementing the attack on Feistel ciphers with small block sizes. As a result, we conclude that efficient and practical 6-round Feistel networks are not secure.

In this paper, generic attacks are presented against hash functions that are constructed by a hashing mode instantiating a Feistel or generalized Feistel networks with an SP-round function. It is observed that the omission of the network twist in the last round can be a weakness against preimage attacks. The first target is a standard Feistel network with an SP round function. Up to 11 rounds can be attacked in generic if a condition on a key schedule function is satisfied. The second target is a 4-branch type-2 generalized Feistel network with an SP round function. Up to 15 rounds can be attacked in generic. These generic attacks are then applied to hashing modes of ISO standard ciphers Camellia-128 without FL and whitening layers and CLEFIA-128.

The Generalized Feistel Structure (GFS) is one of the structures used in designs of blockciphers and hash functions. There are several types of GFSs, and we focus on Type 1 and Type 2 GFSs. The security of these structures are well studied and they are adopted in various practical blockciphers and hash functions. The round function used in GFSs consists of two layers. The first layer uses the nonlinear function. Type 1 GFS uses one nonlinear function in this layer, while Type 2 GFS uses a half of the number of sub-blocks. The second layer is a sub-block-wise permutation, and the cyclic shift is generally used in this layer. In this paper, we formalize Type 1.x GFS, which is the natural extension of Type 1 and Type 2 GFSs with respect to the number of nonlinear functions in one round. Next, for Type 1.x GFS using two nonlinear functions in one round, we propose a permutation which has a good diffusion property. We demonstrate that Type 1.x GFS with this permutation has a better diffusion property than other Type 1.x GFS with the sub-block-wise cyclic shift. We also present experimental results of evaluating the diffusion property and the security against the saturation attack, impossible differential attack, differential attack, and linear attack of Type 1.x GFSs with various permutations.

The Generalized Feistel Structure (GFS) generally uses the sub-block-wise cyclic shift in the permutation layer, the layer between the two F function layers. For Type 2 GFS, at FSE 2010, Suzaki and Minematsu showed that a better diffusion property can be obtained if one uses some other sub-block-wise permutation. In this paper, we consider Type 1, Type 3, Source-Heavy (SH), and Target-Heavy (TH) GFSs, and study if their diffusion properties can be improved by changing the sub-block-wise cyclic shift. For Type 1 GFS and Type 3 GFS, we show that better permutations in terms of diffusion exist. For SH and TH GFSs, we show that the diffusion property does not change even if we change the sub-block-wise cyclic shift. We also experimentally derive optimum permutations in terms of diffusion, and evaluate the security of the resulting schemes against saturation, impossible differential, differential, and linear attacks.

This article presents a differential fault analysis (DFA) technique using round addition for a generalized Feistel network (GFN) including CLEFIA and RC6. Here the term “round addition” means that the round operation executes twice using the same round key. The proposed DFA needs bypassing of an operation to count the number of rounds such as increment or decrement. To verify the feasibility of our proposal, we implement several operations, including increment and decrement, on a microcontroller and experimentally confirm the operation bypassing. The proposed round addition technique works effectively for the generalized Feistel network with a partial whitening operation after the last round. In the case of a 128-bit CLEFIA, we show a procedure to reconstruct the round keys or a secret key using one correct ciphertext and two faulty ciphertexts. Our DFA also works for DES and RC6.

We present attacks on the generalized Feistel schemes, where each round function consists of a subkey XOR, S-boxes, and then a linear transformation (i.e. a Substitution-Permutation (SP) round function). Our techniques are based on rebound attacks. We assume that the S-boxes have a good differential property and the linear transformation has an optimal branch number. Under this assumption, we firstly describe known-key distinguishers on the type-1, -2, and -3 generalized Feistel schemes up to 21, 13 and 8 rounds, respectively. Then, we use the distinguishers to make several attacks on hash functions where Merkle-Damgård domain extender is used and the compression function is constructed with Matyas-Meyer-Oseas or Miyaguchi-Preneel hash modes from generalized Feistel schemes. Collision attacks are made for 11 rounds of type-1 Feistel scheme. Near collision attacks are made for 13 rounds of type-1 Feistel scheme and 9 rounds of type-2 Feistel scheme. Half collision attacks are made for 15 rounds of type-1 Feistel scheme, 9 rounds of type-2 Feistel scheme, and 5 rounds of type-3 Feistel scheme.

We assume that the domain extender is the Merkle-Damgård (MD) scheme and he message is padded by a ‘1', and minimum number of ‘0' s, followed by a fixed size length information so that the length of padded message is multiple of block length. Under this assumption, we analyze securities of the hash mode when the compression function follows the Davies-Meyer (DM) scheme and the underlying block cipher is one of the plain Feistel or Misty scheme or the generalized Feistel or Misty schemes with Substitution-Permutation (SP) round function. We do this work based on Meet-in-the-Middle (MitM) preimage attack techniques, and develop several useful initial structures.

This paper describes a differential fault analysis (DFA) attack against CLEFIA. The proposed attack can be applied to CLEFIA with all supported keys: 128, 192, and 256-bit keys. DFA is a type of side-channel attack. This attack enables the recovery of secret keys by injecting faults into a secure device during its computation of the cryptographic algorithm and comparing the correct ciphertext with the faulty one. CLEFIA is a 128-bit blockcipher with 128, 192, and 256-bit keys developed by the Sony Corporation in 2007. CLEFIA employs a generalized Feistel structure with four data lines. We developed a new attack method that uses this characteristic structure of the CLEFIA algorithm. On the basis of the proposed attack, only 2 pairs of correct and faulty ciphertexts are needed to retrieve the 128-bit key, and 10.78 pairs on average are needed to retrieve the 192 and 256-bit keys. The proposed attack is more efficient than any previously reported. In order to verify the proposed attack and estimate the calculation time to recover the secret key, we conducted an attack simulation using a PC. The simulation results show that we can obtain each secret key within three minutes on average. This result shows that we can obtain the entire key within a feasible computational time.

Tweakable pseudorandom permutations have wide applications such as the disk sector encryption, and the underlying primitive for efficient MACs and authenticated encryption schemes. Goldenberg et al. showed constructions of a tweakable pseudorandom permutation based on the Feistel structure. In this paper, we explore the possibility of designing tweakable pseudorandom permutations based on the Generalized Feistel Structure. We show that tweakable pseudorandom permutations can be obtained without increasing the number of rounds compared to the non-tweakable versions. We also present designs that take multiple tweaks as input.

The design and analysis of block ciphers is an established field of study which has seen significant progress since the early 1990s. Nevertheless, what remains on an interesting direction to explore in this area is to design block ciphers with provable security against powerful known attacks such as differential and linear cryptanalysis. In this paper we introduce seven new block cipher structures, named Feistel-variant A, B, CLEFIA and MISTY-FO-variant A, B, C, D structures, and show that these structures are provably resistant against differential cryptanalysis. The main results of this paper are that the average differential probabilities over at least 2 rounds of Feistel-variant A structure and 1 round of Feistel-variant B structure are both upperbounded by p2, while the average differential probabilities over at least 5 rounds of CLEFIA, MISTY-FO-variant A, B, C and D structures are upperbounded by p4+2p5, p4, p4, 2p4 and 2p4, respectively, if the maximum differential probability of a round F function is p. We also give provable security for the Feistel-variant A, B and CLEFIA structures against linear cryptanalysis. Our results are attained under the assumption that all of components in our proposed structures are bijective. We expect that our results are useful to design block ciphers with provable security against differential and linear cryptanalysis.

To design secure blockciphers, estimating immunity against differential attack and linear attack is essential. Recently, Diffusion Switching Mechanism (DSM) is proposed as a design framework to enhance the immunity of Feistel structure against differential attack and linear attack. In this paper, we give novel results on the effect of DSM on three generalized Feistel structures, i.e. Type-I, Type-II and Nyberg's structures. We first show a method for roughly estimating lower bounds of a number of active S-boxes in Type-I and Type-II structures using DSM. Then we propose an improved search algorithm to find lower bounds for generalized structures efficiently. Experimental results obtained by the improved algorithm show that DSM raises lower bounds for all of the structures, and also show that Nyberg's structure has the slowest diffusion effect among them when SP-type F-functions are used.

It is known that a super-pseudorandom permutation can be constructed from a pseudorandom function f and two universal hash functions, h and h′. It is a four round Feistel permutation denoted by φ(hk,f,f,h′k′). In this paper, we show how to re-use the secret key for f in this construction. Specifically, we show that (1) the same key can be used for both h and h′, and (2) the key for h and h′can be derived from f. As a result, our construction requires only the key for f as a secret key, and it preserves computational efficiency and security. We show the full security proof of our construction. Also, we derive a similar result for a five round MISTY-type permutation.

It is known that a super-pseudorandom permutation on 2n bits can be obtained from a random function f on n bits and two bi-symmetric and AXU hash functions h1 and h2 on n bits. It has a Feistel type structure which is usually denoted by φ(h1,f, f, h2). Bi-symmetric and AXU hash functions h1,h2 are much weaker primitives than a random function f and they can be computed much faster than random functions. This paper shows that we can further weaken the condition on h1.

This letter examines outline measures of strength against the differential and linear cryptanalysis. These measures are useful to estimate the number of rounds giving an immune iterated cipher. This letter reports that the outline measures of strength are useful to relatively estimate the strength of generalized feistel ciphers.

Nyberg and Knudsen proved that the maximum average of differential probability (ADPmax) and the maximum average of linear probability (ALPmax) of Feistel cipher with over 4 rounds can be evaluated as ADPmax 2DCP2max and ALPmax 2LCP2max using the maximum of defferential characteristic probability (DCPmax) and the maximum of linear characteristic probability (LCPmax) per round. This paper shows ADPmax DCP2max and ALPmax LCP2max if the F function is a bijection and the Feistel cipher has more than 3 rounds. The results prove that Feistel ciphers are stronger against differential and linear cryptanalyses than previously thought. Combining this result with that of Luby and Rackoff, the implication is that the 3-round Feistel cipher could be used as a building block cipher for the construction of provable secure block cipher algorithm.