Security of message authentication codes in the presence of key-dependent messages

In recent years, the security of encryption and signature schemes in the presence of key-dependent plaintexts received attention, and progress in understanding such scenarios has been made. In this article we motivate and discuss a setting where an adversary can access tags of a message authentication code (MAC) on key-dependent message inputs, and we propose a way to formalize the security of MACs in the presence of key-dependent messages (KD?EUF). Like signature schemes, MACs have a verification algorithm, and hence the tagging algorithm must be stateful. We present a scheme MAC-ver which offers KD?EUF security and also yields a forward-secure scheme.     

Improved meet-in-the-middle attacks on reduced-round Kalyna-128/256 and Kalyna-256/512

Kalyna is an SPN-based block cipher that was selected during the Ukrainian National Public Cryptographic Competition (2007–2010) and its slight modification was approved as the new encryption standard of Ukraine. In this paper, we focus on the key-recovery attacks on reduced-round Kalyna-128/256 and Kalyna-256/512 with the meet-in-the-middle method. The differential enumeration technique and key-dependent sieve technique which are popular to analyze AES are used to attack them. Using the key-dependent sieve technique to improve the complexity is not an easy task, we should build some tables to achieve this. Since the encryption procedure of Kalyna employs pre- and post-whitening operations using addition modulo \(2^{64}\) applied on the state columns independently, we carefully study the propagation of this operation and propose an addition plaintext structure to solve this. For Kalyna-128/256, we propose a 6-round distinguisher, and achieve a 9-round (out of total 14-round) attack. For Kalyna-256/512, we propose a 7-round distinguisher, then achieve an 11-round (out of total 18-round) attack. As far as we know, these are currently the best results on Kalyna-128/256 and Kalyna-256/512.     

Relating Differential Distribution Tables to Other Properties of of Substitution Boxes

Due to the success of differential and linear attacks on a large number of encryption algorithms, it is important to investigate relationships among various cryptographic, including differential and linear, characteristics of an S-box (substitution box). After discussing a precise relationship among three tables, namely the difference, auto-correlation and correlation immunity distribution tables, of an S-box, we develop a number of results on various properties of S-boxes. More specifically, we show (1) close connections among three indicators of S-boxes, (2) a tight lower bound on the sum of elements in the leftmost column of its differential distribution table, (3) a non-trivial and tight lower bound on the differential uniformity of an S-box, and (4) two upper bounds on the nonlinearity of S-boxes (one for a general, not necessarily regular, S-box and the other for a regular S-box).     

On unbalanced Feistel networks with contracting MDS diffusion

Though unbalanced Feistel networks (UFN) are widely considered as an alternative to balanced Feistel networks (BFN) and substitution?Cpermutation networks (SPN) in symmetric cryptography, little has been known yet about their resistance against differential and linear cryptanalysis. In this work, we tackle the problem at the example of d-branch SP-type UFNs with contracting MDS diffusion (dCUFN-SP). Under some restrictions on the contracting MDS matrices over multiple rounds, we prove lower bounds on the number of differentially active S-boxes for dCUFN-SP with ${d\in\{3,4\}}$ and on the number of linearly active S-boxes for dCUFN-SP with d ?? 3. As opposed to SPNs and BFNs, the number of differentially active S-boxes for such constructions does not directly translate to an upper bound on the probability of differential trails. So we provide a thorough analysis of single-round differentials that yields an upper bound on the probability of a differential trail. It is also shown that the efficiency level of dCUFN-SP is comparable to that of BFNs and SPNs with respect to differential and linear cryptanalysis.     

An extended method for obtaining S-boxes based on three-dimensional chaotic Baker maps

Tang et al. proposed a novel method for obtaining S-boxes based on the well-known two-dimensional chaotic Baker map. Unfortunately, some mistakes exist in their paper. The faults are corrected first in this paper and then an extended method is put forward for acquiring cryptographically strong S-boxes. The new scheme employs a three-dimensional chaotic Baker map, which has more intensive chaotic characters than the two-dimensional one. In addition, the cryptographic properties such as the bijective property, the nonlinearity, the strict avalanche criterion, the output bits independence criterion and the equiprobable input/output XOR distribution are analyzed in detail for our S-box and revised Tang et al.’s one, respectively. The results of numerical analysis show that both of the two boxes can resist several attacks effectively and the three-dimensional chaotic map, a stronger sense in chaotic characters, can perform more smartly and more efficiently in designing S-boxes.     

A new counting method to bound the number of active S-boxes in Rijndael and 3D

Security against differential and linear cryptanalysis is an essential requirement for modern block ciphers. This measure is usually evaluated by finding a lower bound for the minimum number of active S-boxes. The 128-bit block cipher AES which was adopted by National Institute of Standards and Technology (NIST) as a symmetric encryption standard in 2001 is a member of Rijndael family of block ciphers. For Rijndael, the block length and the key length can be independently specified to 128, 192 or 256 bits. It has been proved that for all variants of Rijndael the lower bound of the number of active S-boxes for any 4-round differential or linear trail is 25, and for 4r (\(r \ge 1\)) rounds 25r active S-boxes is a tight bound only for Rijndael with block length 128. In this paper, a new counting method is introduced to find tighter lower bounds for the minimum number of active S-boxes for several consecutive rounds of Rijndael with larger block lengths. The new method shows that 12 and 14 rounds of Rijndael with 192-bit block length have at least 87 and 103 active S-boxes, respectively. Also the corresponding bounds for Rijndael with 256-bit block are 105 and 120, respectively. Additionally, a modified version of Rijndael-192 is proposed for which the minimum number of active S-boxes is more than that of Rijndael-192. Moreover, we extend the method to obtain a better lower bound for the number of active S-boxes for the block cipher 3D. Our counting method shows that, for example, 20 and 22 rounds of 3D have at least 185 and 205 active S-boxes, respectively.     

Construction of highly nonlinear resilient S-boxes with given degree

We provide two new construction methods for nonlinear resilient S-boxes with given degree. The first method is based on the use of linear error correcting codes together with highly nonlinear S-boxes. Given a [u, m, t + 1] linear code where u = n?d?1, d > m, we show that it is possible to construct (n, m, t, d) resilient S-boxes which have currently best known nonlinearity. Our second construction provides highly nonlinear (n, m, t, d) resilient S-boxes which do not have linear structure, then an improved version of this construction is given.     

A method to calculate differential uniformity for permutations

We introduce a search algorithm to find permutation S-boxes with low differential uniformity, high nonlinearity and high algebraic degree, which play important roles in block ciphers. Inspired by the results of our search algorithm, we propose a method to calculate differential uniformity for permutations. We establish a sufficient condition for differentially 4-uniform permutations based on our method and construct some example classes of differentially 4-uniform permutations.     

A block cipher with dynamic S-boxes based on tent map

In this paper, a block encryption scheme based on dynamic substitution boxes (S-boxes) is proposed. Firstly, the difference trait of the tent map is analyzed. Then, a method for generating S-boxes based on iterating the tent map is presented. The plaintexts are divided into blocks and encrypted with different S-boxes. The cipher blocks are obtained by 32 rounds of substitution and left cyclic shift. To improve the security of the cryptosystem, a cipher feedback is used to change the state value of the tent map, which makes the S-boxes relate to the plaintext and enhances the confusion and diffusion properties of the cryptosystem. Since dynamic S-boxes are used in the encryption, the cryptosystem does not suffer from the problem of fixed structure block ciphers. Theoretical and experimental results indicate that the cryptosystem has high security and is suitable for secure communications.     

A novel method of S-box design based on chaotic map and composition method

An efficient algorithm for obtaining random bijective S-boxes based on chaotic maps and composition method is presented. The proposed method is based on compositions of S-boxes from a fixed starting set. The sequence of the indices of starting S-boxes used is obtained by using chaotic maps. The results of performance test show that the S-box presented in this paper has good cryptographic properties. The advantages of the proposed method are the low complexity and the possibility to achieve large key space.     

On complexity of round transformations

A modern block cipher consists of round transformations, which are obtained by alternatively applying permutations (P-boxes) and substitutions (S-boxes). Clearly, the most important attribute of a block cipher is its security. However, with respect to the hardware implementation, a good block cipher has to have a reasonable complexity as well. In this paper, we study complexity of round transformations satisfying some basic security criteria. There are several ways to define the complexity of a round transformation, and to choose “necessary” security criteria. It turns out, that for our purpose, it is suitable to view a round transformation as a single Boolean function, not separating it into S-boxes and P-boxes. We require that the Boolean function F possesses some fundamental properties imposed on each block cipher for security reasons; namely, we require that the function is a strictly non-linear bijection and that it has a good diffusion. The total number of variables in the normal algebraic form of the component functions of F is taken as its complexity. We find the minimum complexity of such functions, and this way we establish a lower bound on complexity of all round transformations. To show that the lower bound is the best possible, we construct a round transformation F^′ attaining the bound. We stress that it is not an aspiration of this paper to construct a round transformation which would be of practical use; F^′ is useful only from the theoretical point of view.     

The design of composite permutations with applications to DES-like S-boxes

This paper presents an iterative construction method for building composite permutations. Its efficiency is based on the concepts of pre-computation and equivalence classes. Equivalence class representatives of permutations on four bits are pre-computed. These class representatives can serve as input to the construction method, however, the results are also of independent interest for applications in cryptography. A well-known example of a cryptosystem using composite permutations for its Substitution boxes (S-boxes) is the Data Encryption Standard (DES). Throughout the paper, DES-like S-boxes are defined as mappings satisfying all design criteria as disclosed by one of the designers of DES. All permutations on four bits with DES-like properties are identified. Starting with pre-computed representatives of classes with such permutations, two iterations of a specialized version of the algorithm are applied to obtain bounds on the minimum differential uniformity and minimum non-linear uniformity of DES-like S-boxes. It is established that the two values cannot be less than eight, and that DES-like S-boxes for which the values are both equal to 12 do exist. In addition, if the non-linear uniformity of each of the four permutations in a DES-like S-box is at most six, as in all DES S-boxes, then its non-linear uniformity cannot be less than ten and its minimum differential uniformity equals 12.     

A novel method for designing S-boxes based on chaotic maps

A method for obtaining cryptographically strong 8 × 8 S-boxes based on chaotic maps is presented and the cryptographical properties such as bijection, nonlinearity, strict avalanche criterion, output bits independence criterion and equiprobable input/output XOR distribution of these S-boxes are analyzed in detail. The results of numerical analysis also show that the S-boxes proposed are of the above properties and can resist the differential attack. Furthermore, our approach is suitable for practical application in designing cryptosystem.     

A method for designing dynamical S-boxes based on discretized chaotic map

A method for obtaining dynamically cryptographically strong substitution boxes (S-boxes) based on discretized chaotic map is presented in this paper. The cryptographical properties such as bijection, nonlinearity, strict avalanche, output bits independence and equiprobable input/output XOR distribution of these S-boxes are analyzed in detail. The results of numerical analysis show that all the criteria for designing good S-box can be met approximately. As a result, our approach is suitable for practical application in designing block cryptosystem.     

A combined DCA: GA for constructing highly nonlinear balanced boolean functions in cryptography

Substitution boxes, aka S-boxes, are a key component of modern crypto-systems. Several studies and developments were carried out on the problem of building high-quality S-boxes in the last few years. Qualities of such boxes, such as nonlinearity and balance, steer the robustness of modern block ciphers. This work is concerned with the construction of highly nonlinear balanced Boolean functions. A deterministic optimization model which is the minimization of a polyhedral convex function on a convex polytope with 0–1 variables is introduced. A local deterministic optimization approach called DCA (Difference of Convex functions Algorithm) is investigated. For finding a good starting point of DCA we propose two versions of a combined DCA–GA (Genetic Algorithm) method. Numerical simulations prove that DCA is a promising approach for this problem. Moreover the combination of DCA–GA improves the efficiency of DCA and outperforms other standard approaches.     

Generalized Feistel networks revisited

This work deals with the classification, security and efficiency of generalized Feistel networks (GFNs) with 4 lines. We propose a definition of a GFN, essentially limiting consideration to Feistel-type constructions with domain-preserving F-functions and rotation by one line between rounds. Under this definition, we demonstrate that there are only two non-contracting representatives in the class of 4-line GFNs up to equivalence, namely, the type-I and type-II GFNs that avoid obvious differential effects. We propose to instantiate the GFNs with SPS-functions (two substitution layers separated by a permutation layer) instead of single SP-functions (one substitution-permutation layer only). We prove tight lower bounds on the number of differentially and linearly active functions and S-boxes in such ciphers. We show that the instantiation with SPS-functions using MDS diffusion provides a proportion of differentially and linearly active S-boxes by up to 33 and 50 % higher than that with single SP-functions for type-I and type-II GFNs, respectively, if the same matrix is used in all rounds. Moreover, we present the upper bounds on the differential and the linear hull probability for the type-II GFNs with SPS-functions. This opens up the possibility of designing more efficient block ciphers based on GFN structure.     

Towards the optimality of Feistel ciphers with substitution-permutation functions

We explore the optimality of balanced Feistel ciphers with SP-type F-functions with respect to their resistance against differential and linear cryptanalysis. Instantiations of Feistel ciphers with the wide class of (SP) \(^u\) and (SP) \(^u\) S F-functions are considered: one F-function can contain an arbitrary number of S-box layers interleaved with linear diffusion. For the matrices with maximum diffusion, it is proven that SPS and SPSP F-functions are optimal in terms of the proportion of active S-boxes in all S-boxes—a common efficiency metric for substitution-permutation ciphers. Interestingly, one SP-layer in the F-function is not enough to attain optimality whereas taking more than two S-box layers does not increase the efficiency either.     

A combinatorial problem related to sparse systems of equations

Nowadays sparse systems of equations occur frequently in science and engineering. In this contribution we deal with sparse systems common in cryptanalysis. Given a cipher system, one converts it into a system of sparse equations, and then the system is solved to retrieve either a key or a plaintext. Raddum and Semaev proposed new methods for solving such sparse systems common in modern ciphers which are combinations of linear layers and small S-boxes. It turns out that the solution of a combinatorial MaxMinMax problem provides an upper bound on the average computational complexity of those methods. In this paper we initiate the study of a linear algebra variation of the MaxMinMax problem. The complexity bound proved in this paper significantly overcomes conjectured complexity bounds for Gröbner basis type algorithms.     

具有最高代数次数的2n元n维Bent函数的构造

本文给出了代数次数达到最高的一类布尔置换的代数标准形 ;并用m序列的状态转移矩阵和所得置换 ,构造了一类代数次数达到最高的 2n元n维Bent函数 ,用这类函数所构造的S盒具有较高的安全强度 .     

Concatenating Indicators of Flats for Designing Cryptographic Functions

Boolean functions with good cryptographic characteristics are needed for the design of robust pseudo-random generators for stream ciphers and of S-boxes for block ciphers. Very few general constructions of such cryptographic Boolean functions are known. The main ones correspond to concatenating affine or quadratic functions. We introduce a general construction corresponding to the concatenation of indicators of flats. We show that the functions it permits to design can present very good cryptographic characteristics.