Aggregated differentials and cryptanalysis of PP-1 and gost

In this paper we look at the security of two block ciphers which were both claimed in the published literature to be secure against differential crypt-analysis (DC). However, a more careful examination shows that none of these ciphers is very secure against... differential cryptanalysis, in particular if we consider attacks with sets of differentials. For both these ciphers we report new perfectly periodic (iterative) aggregated differential attacks which propagate with quite high probabilities. The first cipher we look at is GOST, a well-known Russian government encryption standard. The second cipher we look at is PP-1, a very recent Polish block cipher. Both ciphers were designed to withstand linear and differential cryptanalysis. Unhappily, both ciphers are shown to be much weaker than expected against advanced differential attacks. For GOST, we report better and stronger sets of differentials than the best currently known attacks presented at SAC 2000 [32] and propose the first attack ever able to distinguish 16 rounds of GOST from random permutation. For PP-1 we show that in spite of the fact, that its S-box has an optimal theoretical security level against differential cryptanalysis [17], [29], our differentials are strong enough to allow to break all the known versions of the PP-1 cipher.     

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.     

On Lai–Massey and quasi-Feistel ciphers

We introduce a new notion called a quasi-Feistel cipher, which is a generalization of the Feistel cipher, and contains the Lai–Massey cipher as an instance. We show that most of the works on the Feistel cipher can be naturally extended to the quasi-Feistel cipher. From this, we give a new proof for Vaudenay’s theorems on the security of the Lai–Massey cipher, and also we introduce for Lai–Massey a new construction of pseudorandom permutation, analoguous to the construction of Naor–Reingold using pairwise independent permutations. Also, we prove the birthday security of (2b−1)- and (3b−2)-round unbalanced quasi-Feistel ciphers with b branches against CPA and CPCA attacks, respectively.     

Light tails and the Hermitian dual polar graphs

This paper investigates ciphers where the set of encryption functions is identical to the set of decryption functions, which we call reflection ciphers. Equivalently, there exists a permutation P, named the coupling permutation, such that decryption under k corresponds to encryption under P(k). We study the necessary properties for this coupling permutation. Special care has to be taken of some related-key distinguishers since, in the context of reflection ciphers, they may provide attacks in the single-key setting. We then derive some criteria for constructing secure reflection ciphers and analyze the security properties of different families of coupling permutations. Finally, we concentrate on the case of reflection block ciphers and, as an illustration, we provide concrete examples of key schedules corresponding to several coupling permutations, which lead to new variants of the block cipher prince.     

Impossible differential cryptanalysis using matrix method

The general strategy of impossible differential cryptanalysis is to first find impossible differentials and then exploit them for retrieving subkey material from the outer rounds of block ciphers. Thus, impossible differentials are one of the crucial factors to see how much the underlying block ciphers are resistant to impossible differential cryptanalysis. In this article, we introduce a widely applicable matrix method to find impossible differentials of block cipher structures whose round functions are bijective. Using this method, we find various impossible differentials of known block cipher structures: Nyberg’s generalized Feistel network, a generalized CAST256-like structure, a generalized MARS-like structure, a generalized RC6-like structure, Rijndael structures and generalized Skipjack-like structures. We expect that the matrix method developed in this article will be useful for evaluating the security of block ciphers against impossible differential cryptanalysis, especially when one tries to design a block cipher with a secure structure.     

Provable security of block ciphers against linear cryptanalysis: a mission impossible?

In this paper, we are concerned with the security of block ciphers against linear cryptanalysis and discuss the distance between the so-called practical security approach and the actual theoretical security provided by a given cipher. For this purpose, we present a number of illustrative experiments performed against small (i.e. computationally tractable) ciphers. We compare the linear probability of the best linear characteristic and the actual best linear probability (averaged over all keys). We also test the key equivalence hypothesis. Our experiments illustrate both that provable security against linear cryptanalysis is not achieved by present design strategies and the relevance of the practical security approach. Finally, we discuss the (im)possibility to derive actual design criteria from the intuitions underlined in these experiments. F.-X. Standaert is a Postdoctoral researcher of the Belgian Fund for Scientific Research (FNRS).     

Design of Practical and Provably Good Random Number Generators

We present a construction for a family of pseudo-random generators that are very fast in practice, yet possess provable statistical and cryptographic unpredictability properties. Such generators are useful for simulations, randomized algorithms, and cryptography.Our starting point is a slow but high quality generator whose use can be mostly confined to a preprocessing step. We give a method of stretching its outputs that yields a faster generator. The fast generator offers smooth memory–time–security trade-offs and also has many desired properties that are provable. The slow generator can be based on strong one-way permutations or block ciphers. Our implementation based on the block cipher DES is faster than popular generators.     

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.     

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.     

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.     

Key alternating ciphers based on involutions

In this work, we study the security of Even–Mansour type ciphers whose encryption and decryption are based on a common primitive, namely an involution. Such ciphers possibly allow efficient hardware implementation as the same circuit is shared for encryption and decryption, and thus expected to be more suitable for lightweight environment in which low power consumption and implementation costs are desirable. With this motivation, we consider a single-round Even–Mansour cipher using an involution as its underlying primitive. The decryption of such a cipher is the same as encryption only with the order of the round keys reversed. It is known that such a cipher permits a birthday-bound attack using only construction queries, but whether it provides provable security in the range below the birthday bound has remained. We prove that the Even–Mansour cipher based on a random involution is as secure as the permutation-based one when the number of construction queries is limited by the birthday bound. In order to achieve security beyond the birthday bound, we propose a two-round Even–Mansour-like construction, dubbed \(\mathsf {EMSI}\), based on a single involution I using a fixed permutation \(\sigma \) in the middle layer. Specifically, \(\mathsf {EMSI}\) encrypts a plaintext u by computing

$$\begin{aligned} v=I\left( \sigma \left( I(u\oplus k_0)\right) \oplus k_1\right) \oplus k_2 \end{aligned}$$

with the key schedule \(\gamma =(\gamma _0,\gamma _1,\gamma _2)\) generating three round keys \(k_0=\gamma _0(k)\), \(k_1=\gamma _1(k)\) and \(k_2=\gamma _2(k)\) from an n-bit master key k. We prove that if the key schedule \(\gamma =(\gamma _0,\gamma _1,\gamma _2)\) satisfies a certain condition, and \(\sigma \) is a linear orthomorphism, then this construction is secure up to \(2^{\frac{2n}{3}}\) construction and permutation queries. \(\mathsf {EMSI}\) is the first construction that uses a single involution—a primitive weaker than a truly random permutation—and that provides security beyond the birthday bound at the same time. Encryption and decryption of \(\mathsf {EMSI}\) are the same except for the key schedule and the middle layer. Since encryption and decryption are both based on a common primitive, \(\mathsf {EMSI}\) is expected to be particularly suitable for modes of operation that use both encryption and decryption of the underlying block cipher such as OCB3.

     

Nonlinear diffusion layers

In the practice of block cipher design, there seems to have grown a consensus about the diffusion function that designers choose linear functions with large branch numbers to achieve provable bounds against differential and linear cryptanalysis. In this paper, we propose two types of nonlinear functions as alternative diffusing components. One is based on a nonlinear code with parameters (16,256,6) which is known as a Kerdock code. The other is a general construction of nonlinear functions based on the T-functions, in particular, two automatons with modular addition operations. We show that the nonlinear functions possess good diffusion properties; specifically, the nonlinear function based on a Kerdock code has a better branch number than any linear counterparts, while the automatons achieve the same branch number as a linear near-MDS matrix. The advantage of adopting nonlinear diffusion layers in block ciphers is that, those functions provide extra confusion effect while a comparable performance in the diffusion effect is maintained. As an illustration, we show the application of the nonlinear diffusion functions in two example ciphers, where a 4-round differential characteristic with the optimal number of active Sboxes has a probability significantly lower (\(2^{16}\) and \(2^{10}\) times, respectively) than that of a similar cipher with a linear diffusion layer. As a result, it sheds light upon an alternative strategy of designing lightweight building blocks.     

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.     

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.     

Design and statistical analysis of a new chaotic block cipher for Wireless Sensor Networks

Security issue is a vital and active topic in the research of Wireless Sensor Networks (WSN). After surveying the existing encryption algorithms for WSN briefly, we propose a new chaotic block cipher for WSN and then compare the performance of this cipher with those of RC5 and RC6 block ciphers. Simulation result demonstrates that better performance in WSN encryption algorithms can be achieved using the new cipher.     

Upper bound of the length of truncated impossible differentials for AES

On the provable security of a block cipher against impossible differential cryptanalysis, the maximal length of impossible differentials is an essential aspect. Most previous work on finding impossible differentials for AES, omits the non-linear component (S-box), which is important for the security. In EUROCRYPT 2016, Sun et al. showed how to bound the length of impossible differentials of a SPN “structure” using the primitive index of its linear layer. They proved that there do not exist impossible differentials longer than four rounds for the AES “structure”, instead of the AES cipher. Since they do not consider the details of the S-box, their bound is not feasible for a concrete cipher. With their result, the upper bound of the length of impossible differentials for AES, is still unknown. We fill this gap in our paper. By revealing some important properties of the AES S-box, we further prove that even though the details of the S-box are considered, there do not exist truncated impossible differentials covering more than four rounds for AES, under the assumption that round keys are independent and uniformly random. Specially, even though the details of the S-box and key schedule are both considered, there do not exist truncated impossible differentials covering more than four rounds for AES-256.     

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.     

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.     

Super-strong RKA secure MAC,PKE and SE from tag-based hash proof system

\(\mathcal {F}\)-related-key attacks (RKA) on cryptographic systems consider adversaries who can observe the outcome of a system under not only the original key, say k, but also related keys f(k), with f adaptively chosen from \(\mathcal {F}\) by the adversary. In this paper, we define new RKA security notions for several cryptographic primitives including message authentication code (MAC), public-key encryption (PKE) and symmetric encryption (SE). This new kind of RKA notions are called super-strong RKA securities, which stipulate minimal restrictions on the adversary’s forgery or oracle access, thus turn out to be the strongest ones among existing RKA security requirements. We present paradigms for constructing super-strong RKA secure MAC, PKE and SE from a common ingredient, namely Tag-based hash proof system (THPS). We also present constructions for THPS based on the k-linear and the DCR assumptions. When instantiating our paradigms with concrete THPS constructions, we obtain super-strong RKA secure MAC, PKE and SE schemes for the class of restricted affine functions \(\mathcal {F}_{\text {raff}}\), of which the class of linear functions \(\mathcal {F}_{\text {lin}}\) is a subset. To the best of our knowledge, our MACs, PKEs and SEs are the first ones possessing super-strong RKA securities for a non-claw-free function class \(\mathcal {F}_{\text {raff}}\) in the standard model and under standard assumptions. Our constructions are free of pairing and are as efficient as those proposed in previous works. In particular, the keys, tags of MAC and ciphertexts of PKE and SE all consist of only a constant number of group elements.     

Zero-correlation linear cryptanalysis of reduced-round LBlock

Zero-correlation linear attack is a new method developed by Bogdanov et al. (ASIACRYPT 2012. LNCS, Springer, Berlin, 2012) for the cryptanalysis of block ciphers. In this paper we adapt the matrix method to find zero-correlation linear approximations. Then we present several zero-correlation linear approximations for 14 rounds of LBlock and describe a cryptanalysis for a reduced 22-round version of LBlock. After biclique attacks on LBlock revealed weaknesses in its key schedule, its designers presented a new version of the cipher with a revised key schedule. The attack presented in this paper does not exploit the structure of the key schedule or S-boxes used in the cipher. As a result, it is applicable to both variants of the LBlock as well as the block ciphers with analogous structures like TWINE. Moreover, we performed simulations on a small variant LBlock and present the first experimental results on the theoretical model of the multidimensional zero-correlation linear cryptanalysis method.