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.     

Zero-correlation attacks: statistical models independent of the number of approximations

Multiple and multidimensional zero-correlation linear cryptanalysis have been two of the most powerful cryptanalytic techniques for block ciphers, and it has been shown that the differentiating factor of these two statistical models is whether distinct plaintexts are assumed or not. Nevertheless, questions remain regarding how these analyses can be universalized without any limitations and can be used to accurately estimate the data complexity and the success probability. More concretely, the current models for multiple zero-correlation (MPZC) and multidimensional zero-correlation (MDZC) cryptanalysis are not valid in the setting with a limited number of approximations and the accuracy of the estimation for data complexity can not be guaranteed. Besides, in a lot of cases, using too many approximations may cause an exhaustive search when we want to launch key-recovery attacks. In order to generalize the original models using the normal approximation of the \(\chi ^2\)-distribution, we provide a more accurate approach to estimate the data complexity and the success probability for MPZC and MDZC cryptanalysis without such approximation. Since these new models directly rely on the \(\chi ^{2}\)-distribution, we call them the \(\chi ^{2}\) MPZC and MDZC models. An interesting thing is that the chi-square-multiple zero-correlation (\(\chi ^{2}\)-MPZC) model still works even though we only have a single zero-correlation linear approximation. This fact puts an end to the situation that the basic zero-correlation linear cryptanalysis requires the full codebook under the known-plaintext attack setting. As an illustration, we apply the \(\chi ^{2}\)-MPZC model to analyze TEA and XTEA. These new attacks cover more rounds than the previous MPZC attacks. Moreover, we reconsider the multidimensional zero-correlation (MDZC) attack on 14-round CLEFIA-192 by utilizing less zero-correlation linear approximations. In addition, some other ciphers which already have MDZC analytical results are reevaluated and the data complexities under the new model are all less than or equal to those under the original model. Some experiments are conducted in order to verify the validity of the new models, and the experimental results convince us that the new models provide more precise estimates of the data complexity and the success probability.     

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.     

Resistance of a CAST-Like Encryption Algorithm to Linear and Differential Cryptanalysis

Linear cryptanalysis and differential cryptanalysis are two recently introduced, powerful methodologies for attacking private-key block ciphers. In this paper, we examine the application of these two cryptanalysis techniques to a CAST-like encryption algorithm. It is shown that, when randomly generated substitution boxes (s-boxes) are used in a CAST-like encryption algorithm, the resulting cipher is resistant to both the linear attack and the differential attack.     

The (related-key) impossible boomerang attack and its application to the AES block cipher

The Advanced Encryption Standard (AES) is a 128-bit block cipher with a user key of 128, 192 or 256 bits, released by NIST in 2001 as the next-generation data encryption standard for use in the USA. It was adopted as an ISO international standard in 2005. Impossible differential cryptanalysis and the boomerang attack are powerful variants of differential cryptanalysis for analysing the security of a block cipher. In this paper, building on the notions of impossible differential cryptanalysis and the boomerang attack, we propose a new cryptanalytic technique, which we call the impossible boomerang attack, and then describe an extension of this attack which applies in a related-key attack scenario. Finally, we apply the impossible boomerang attack to break 6-round AES with 128 key bits and 7-round AES with 192/256 key bits, and using two related keys we apply the related-key impossible boomerang attack to break 8-round AES with 192 key bits and 9-round AES with 256 key bits. In the two-key related-key attack scenario, our results, which were the first to achieve this amount of attacked rounds, match the best currently known results for AES with 192/256 key bits in terms of the numbers of attacked rounds. The (related-key) impossible boomerang attack is a general cryptanalytic technique, and can potentially be used to cryptanalyse other block ciphers.     

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).     

Generalization of Matsui’s Algorithm 1 to linear hull for key-alternating block ciphers

We consider linear approximations of an iterated block cipher in the presence of several strong linear approximation trails. While the effect of such trails in Matsui’s Algorithm 2, also called the linear hull effect, has been previously studied by a number of authors, their effect on Matsui’s Algorithm 1 has not been investigated until now. The goal of this paper is to fill this gap and examine how to generalize Matsui’s Algorithm 1 to work also on linear hulls. We restrict to key-alternating ciphers and develop a mathematical framework for this kind of attacks. The complexity of the attack increases with the number of linear trails that have significant contribution to the correlation. We show how to reduce the number of trails and thus the complexity using related keys. Further, we illustrate our theory by experimental results on a reduced round version of the block cipher PRESENT.     

不可能差分密码分析研究进展

不可能差分分析作为差分分析的一种变体,是一种简单有效的密码分析方法,也是目前最常用的密码分析方法之一.该方法一经提出就得到了广泛应用,被用于分析大量的算法和密码结构.尤其是近年来对AES的攻击,得到了一系列非常好的攻击结果,使得不可能差分分析已成为对AES最有效的攻击方法之一.系统介绍了不可能差分分析的原理、常用技巧和攻击方法,并总结了目前的研究现状和已取得的攻击结果.最后,分析了不可能差分攻击的优缺点及其在设计和分析分组密码方面的作用.     

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.     

On Weaknesses of Non–surjective Round Functions

We propose a new attack on Feistel ciphers with a non-surjective round function such as the CAST cipher family and LOKI91. We extend the attack towards block ciphers that use a non-uniformly distributed round function and apply the extended attack to the CAST family. This attack demonstrates that the round function of a Feistel cipher with six to eight rounds needs to be surjective and sufficiently uniform.     

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.     

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.     

Notions and relations for RKA-secure permutation and function families

The theory of designing block ciphers is mature, having seen significant progress since the early 1990s for over two decades, especially during the AES development effort. Nevertheless, interesting directions exist, in particular in the study of the provable security of block ciphers along similar veins as public-key primitives, i.e. the notion of pseudorandomness (PRP) and indistinguishability (IND). Furthermore, recent cryptanalytic progress has shown that block ciphers well designed against known cryptanalysis techniques including related-key attacks (RKA) may turn out to be less secure against RKA than expected. The notion of provable security of block ciphers against RKA was initiated by Bellare and Kohno, and subsequently treated by Lucks. Concrete block cipher constructions were proposed therein with provable security guarantees. In this paper, we are interested in the security notions for RKA-secure block ciphers. In the first part of the paper, we show that secure tweakable permutation families in the sense of strong pseudorandom permutation (SPRP) can be transformed into secure permutation families in the sense of SPRP against some classes of RKA (SPRP–RKA). This fact allows us to construct a secure SPRP–RKA cipher which is faster than the Bellare–Kohno PRP–RKA cipher. We also show that function families of a certain form secure in the sense of a pseudorandom function (PRF) can be transformed into secure permutation families in the sense of PRP against some classes of RKA (PRP–RKA). We can exploit it to get various constructions secure against some classes of RKA from known MAC algorithms. Furthermore, we discuss how the key recovery (KR) security of the Bellare–Kohno PRP–RKA, the Lucks PRP–RKA and our SPRP–RKA ciphers relates to existing types of attacks on block ciphers like meet-in-the-middle and slide attacks. In the second part of the paper, we define other security notions for RKA-secure block ciphers, namely in the sense of indistinguishability (IND) and non-malleability, and show the relations between these security notions. In particular, we show that secure tweakable permutation families in the sense of IND (resp. non-malleability) can be transformed into RKA-secure permutation families in the sense of IND (resp. non-malleability).     

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.     

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.     

Constructing Symmetric Ciphers Using the CAST Design Procedure

This paper describes the CAST design procedure for constructing a family of DES-like Substitution-Permutation Network (SPN) cryptosystems which appear to have good resistance to differential cryptanalysis, linear cryptanalysis, and related-key cryptanalysis, along with a number of other desirable cryptographic properties. Details of the design choices in the procedure are given, including those regarding the component substitution boxes (s-boxes), the overall framework, the key schedule, and the round function. An example CAST cipher, an output of this design procedure, is presented as an aid to understanding the concepts and to encourage detailed analysis by the cryptologic community.     

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.     

Critique of the related-key attack concept

In a related-key attack, an attacker seeks to discover the secret key by requesting encryptions under keys related to the secret key in a manner chosen by the attacker. We describe a new related-key attack against generic ciphers, requiring just O(1) work to distinguish a cipher from random, and O(key length) to completely recover the secret key. This attack applies within a model which was not previously known to be vulnerable, undermining the theoretical foundation of the related-key attack concept. We propose a new definition of related-key security, which prevents all known generic attacks including this new attack. We discuss the theoretical consequences of this new definition.     

Linear Frameworks for Block Ciphers

Inthis paper we generalize the structure of the ciphers Shark, Square, BKSQ, Crypton and Rijndael. We show that the linearcomponents play an essential role in the effect of the nonlinearS-boxes in providing resistance against differential and linearcryptanalysis and provide upper bounds for the probability ofdifferential characteristics and the correlation of linear approximationsfor the general structure. We show how good linear componentscan be constructed efficiently from Maximum-Distance Separablecodes. The presented block cipher structure can make optimaluse of a wide range of processor word lengths and its parallelismallows very fast dedicated hardware implementations. Cipherswith variable block length can be constructed by varying certainparameters in the presented structure.