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.     

LINEAR PROVABLE SECURITY FOR A CLASS OF UNBALANCED FEISTEL NETWORK

A structure iterated by the unbalanced Feistel networks is introduced. It is showed that this structure is provable resistant against linear attack. The main result of this paper is that the upper bound of r-round （r≥2m） linear hull probabilities are bounded by q^2 when around function F is bijective and the maximal linear hull probabilities of round function F is q. Application of this structure to block cipher designs brings out the provable security against linear attack with the upper bounds of probabilities.     

A new cryptosystem based on chaotic map and operations algebraic

Based on the study of some existing chaotic encryption algorithms, a new block cipher is proposed. The proposed cipher encrypts 128-bit plaintext to 128-bit ciphertext blocks, using a 128-bit key K and the initial value x₀ and the control parameter mu of logistic map. It consists of an initial permutation and eight computationally identical rounds followed by an output transformation. Round r uses a 128-bit roundkey K^(r) to transform a 128-bit input C^(r-1), which is fed to the next round. The output after round 8 enters the output transformation to produce the final ciphertext. All roundkeys are derived from K and a 128-bit random binary sequence generated from a chaotic map. Analysis shows that the proposed block cipher does not suffer from the flaws of pure chaotic cryptosystems and possesses high security.     

Group theoretic properties of Rijndael-like ciphers

We provide conditions for which the round functions of an ?-bit Rijndael-like block cipher generate the alternating group on the set {0,1}^?. These conditions show that the class of Rijndael-like ciphers whose round functions generate the alternating group on their message space is large, and includes both the actual Rijndael and the block cipher used by the compression function of the Whirlpool hash function. The result indicates that there is no trapdoor design for a Rijndael-like cipher based on the imprimitivity of the group action of its proper round functions which is difficult to detect.     

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.     

Generic cryptographic weakness of k-normal Boolean functions in certain stream ciphers and cryptanalysis of grain-128

This paper considers security implications of k-normal Boolean functions when they are employed in certain stream ciphers. A generic algorithm is proposed for cryptanalysis of the considered class of stream ciphers based on a security weakness of k-normal Boolean functions. The proposed algorithm yields a framework for mounting cryptanalysis against particular stream ciphers within the considered class. Also, the proposed algorithm for cryptanalysis implies certain design guidelines for avoiding certain weak stream cipher constructions. A particular objective of this paper is security evaluation of stream cipher Grain-128 employing the developed generic algorithm. Contrary to the best known attacks against Grain-128 which provide complexity of a secret key recovery lower than exhaustive search only over a subset of secret keys which is just a fraction (up to 5%) of all possible secret keys, the cryptanalysis proposed in this paper provides significantly lower complexity than exhaustive search for any secret key. The proposed approach for cryptanalysis primarily depends on the order of normality of the employed Boolean function in Grain-128. Accordingly, in addition to the security evaluation insights of Grain-128, the results of this paper are also an evidence of the cryptographic significance of the normality criteria of Boolean functions.     

Linear hulls with correlation zero and linear cryptanalysis of block ciphers

Linear cryptanalysis, along with differential cryptanalysis, is an important tool to evaluate the security of block ciphers. This work introduces a novel extension of linear cryptanalysis: zero-correlation linear cryptanalysis, a technique applicable to many block cipher constructions. It is based on linear approximations with a correlation value of exactly zero. For a permutation on n bits, an algorithm of complexity 2 ^n-1 is proposed for the exact evaluation of correlation. Non-trivial zero-correlation linear approximations are demonstrated for various block cipher structures including AES, balanced Feistel networks, Skipjack, CLEFIA, and CAST256. As an example, using the zero-correlation linear cryptanalysis, a key-recovery attack is shown on 6 rounds of AES-192 and AES-256 as well as 13 rounds of CLEFIA-256.     

An improvement on the complexity of factoring read-once Boolean functions

Read-once functions have gained recent, renewed interest in the fields of theory and algorithms of Boolean functions, computational learning theory and logic design and verification. In an earlier paper [M.C. Golumbic, A. Mintz, U. Rotics, Factoring and recognition of read-once functions using cographs and normality, and the readability of functions associated with partial k-trees, Discrete Appl. Math. 154 (2006) 1465-1677], we presented the first polynomial-time algorithm for recognizing and factoring read-once functions, based on a classical characterization theorem of Gurvich which states that a positive Boolean function is read-once if and only if it is normal and its co-occurrence graph is P₄-free.In this note, we improve the complexity bound by showing that the method can be modified slightly, with two crucial observations, to obtain an O(n|f|) implementation, where |f| denotes the length of the DNF expression of a positive Boolean function f, and n is the number of variables in f. The previously stated bound was O(n²k), where k is the number of prime implicants of the function. In both cases, f is assumed to be given as a DNF formula consisting entirely of the prime implicants of the function.     

Group classification of a family of second-order differential equations

We find the group of equivalence transformations for equations of the form y^″=A(x)y^′+F(y), where A and F are arbitrary functions. We then give a complete group classification of this family of equations using a direct method of analysis, together with the equivalence transformations.     

Cryptanalysis of the Stream Cipher LEX

Biryukov (The Design of a Stream Cipher LEX, Proceedings of Selected Areas in Cryptography, 2006 Springer, pp 67–75, 2007) presented a new methodology of stream cipher design called leak extraction. The stream cipher LEX, based on this methodology and on the AES block cipher, was selected to round 3 of the eSTREAM competition. The suggested methodology seemed promising, and LEX, due to its elegance, simplicity, and performance, was expected to be selected to the eSTREAM portfolio. In this article we present a key recovery attack on LEX. The attack requires about 2⁴⁰ bytes of key-stream produced by the same key (possibly under many different IVs), and retrieves the secret key in time of about 2¹⁰⁰ AES encryptions. Following a preliminary version of our attack, LEX was discarded from the final portfolio of eSTREAM.     

Optimal collision security in double block length hashing with single length key

The idea of double block length hashing is to construct a compression function on 2n bits using a block cipher with an n-bit block size. All optimally secure double block length hash functions known in the literature employ a cipher with a key space of double block size, 2n-bit. On the other hand, no optimally secure compression functions built from a cipher with an n-bit key space are known. Our work deals with this problem. Firstly, we prove that for a wide class of compression functions with two calls to its underlying n-bit keyed block cipher collisions can be found in about \(2^{n/2}\) queries. This attack applies, among others, to functions where the output is derived from the block cipher outputs in a linear way. This observation demonstrates that all security results of designs using a cipher with 2n-bit key space crucially rely on the presence of these extra n key bits. The main contribution of this work is a proof that this issue can be resolved by allowing the compression function to make one extra call to the cipher. We propose a family of compression functions making three block cipher calls that asymptotically achieves optimal collision resistance up to \(2^{n(1-\varepsilon )}\) queries and preimage resistance up to \(2^{3n(1-\varepsilon )/2}\) queries, for any \(\varepsilon >0\). To our knowledge, this is the first optimally collision secure double block length construction using a block cipher with single length key space. We additionally prove this class of functions indifferentiable from random functions in about \(2^{n/2}\) queries, and demonstrate that no other function in this direction achieves a bound of similar kind.     

Key-Dependent S-Boxes and Differential Cryptanalysis

Key-dependent S-boxes gained some prominence in block cipher design when Twofish became an AES finalist. In this paper we make some observations on how the cryptanalyst might work with key-dependent S-boxes, we begin to develop a framework for the differential cryptanalysis of key-dependent S-boxes, and we introduce some basic techniques that were used in an analysis of reduced-round Twofish.     

Tweaking a block cipher: multi-user beyond-birthday-bound security in the standard model

In this paper, we present a generic construction to create a secure tweakable block cipher from a secure block cipher. Our construction is very natural, requiring four calls to the underlying block cipher for each call of the tweakable block cipher. Moreover, it is provably secure in the standard model while keeping the security degradation minimal in the multi-user setting. In more details, if the underlying blockcipher E uses n-bit blocks and 2n-bit keys, then our construction is proven secure against multi-user adversaries using up to roughly \(2^n\) time and queries as long as E is a secure block cipher.     

Lower estimates of circuit complexity in the basis of antichain functions

The antichain function is a characteristic function of an antichain in the Boolean cube. The set of antichain functions is an infinite complete basis. We study the computational complexity of Boolean functions over an antichain functional basis. In this paper we prove an asymptotic lower bound of order $\sqrt n $ for the computational complexity of a linear function, a majority function, and almost all Boolean functions of n variables.     

The expectation and variance of the joint linear complexity of random periodic multisequences

The linear complexity of sequences is one of the important security measures for stream cipher systems. Recently, in the study of vectorized stream cipher systems, the joint linear complexity of multisequences has been investigated. By using the generalized discrete Fourier transform for multisequences, Meidl and Niederreiter determined the expectation of the joint linear complexity of random N-periodic multisequences explicitly. In this paper, we study the expectation and variance of the joint linear complexity of random periodic multisequences. Several new lower bounds on the expectation of the joint linear complexity of random periodic multisequences are given. These new lower bounds improve on the previously known lower bounds on the expectation of the joint linear complexity of random periodic multisequences. By further developing the method of Meidl and Niederreiter, we derive a general formula and a general upper bound for the variance of the joint linear complexity of random N-periodic multisequences. These results generalize the formula and upper bound of Dai and Yang for the variance of the linear complexity of random periodic sequences. Moreover, we determine the variance of the joint linear complexity of random periodic multisequences with certain periods.     

A pointwise gradient estimate in possibly unbounded domains with nonnegative mean curvature

We prove a pointwise gradient bound for bounded solutions of Δu+F^′(u)=0 in possibly unbounded proper domains whose boundary has nonnegative mean curvature.We also obtain some rigidity results when equality in the bound holds at some point.     

On the collision and preimage security of MDC-4 in the ideal cipher model

We present a collision and preimage security analysis of MDC-4, a 24-years-old construction for transforming an n-bit block cipher into a 2n-bit hash function. We start with MDC-4 based on one single block cipher, and prove that any adversary with query access to the underlying block cipher requires at least \(2^{5n/8}\) queries (asymptotically) to find a collision. For the preimage resistance, we present a surprising negative result: for a target image with the same left and right half, a preimage for the full MDC-4 hash function can be found in \(2^n\) queries. Yet, restricted to target images with different left and right halves, we prove that at least \(2^{5n/4}\) queries (asymptotically) are required to find a preimage. Next, we consider MDC-4 based on two independent block ciphers, a model that is less general but closer to the original design, and prove that the collision bound of \(2^{5n/8}\) queries and the preimage bound of \(2^{5n/4}\) queries apply to the MDC-4 compression function and hash function design. With these results, we are the first to formally confirm that MDC-4 offers a higher level of provable security compared to MDC-2.     

Fuzzy prime Boolean filters and their operations in IMT L-algebras

Some characterizations of fuzzy prime Boolean filters of IMT L-algebras are given. The lattice operations and the order-reversing involution on the set PB(M) of all fuzzy prime Boolean filters of IMT L-algebras are defined. It is showed that the set PB(M) endowed with these operations is a complete quasi-Boolean algebra (a distributive complete lattice with an order-reversing involution). It is derived that the algebra M=F, which is the set of all cosets of F, is isomorphic to the Boolean algebra {0; 1} if F is a fuzzy prime Boolean filter. By introducing an adjoint pair on PB(M), it is proved that the set PB(M) is also a residuated lattice.     

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.