首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 21 毫秒
1.
Nonlinear filter generators are commonly used as keystream generators in stream ciphers. A nonlinear filter generator utilizes a nonlinear filtering function to combine the outputs of a linear feedback shift register (LFSR) to improve the linear complexity of keystream sequences. However, the LFSR-based stream ciphers are still potentially vulnerable to algebraic attacks that recover the key from some keystream bits. Although the known algebraic attacks only require polynomial time complexity of computations, all have their own constraints. This paper uses the linearization of nonlinear filter generators to cryptanalyze LFSR-based stream ciphers. Such a method works for any nonlinear filter generators. Viewing a nonlinear filter generator as a Boolean network that evolves as an automaton through Boolean functions, we first give its linearization representation. Compared to the linearization representation in Limniotis et al. (2008), this representation requires lower spatial complexity of computations in most cases. Based on the representation, the key recoverability is analyzed via the observability of Boolean networks. An algorithm for key recovery is given as well. Compared to the exhaustive search to recover the key, using this linearization representation requires lower time complexity of computations, though it leads to exponential time complexity.  相似文献   

2.
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).  相似文献   

3.
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.  相似文献   

4.
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.  相似文献   

5.
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.  相似文献   

6.
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.  相似文献   

7.
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.  相似文献   

8.
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.  相似文献   

9.
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).  相似文献   

10.
In our constribution we explore a combination of local reduction with the method of syllogisms and the applications of generic guessing strategies in the cryptanalysis of the block cipher GOST. Our experiments show that GOST with 64/128/256 bit key requires at least 12/16/22 rounds to achieve full bit security against the method of syllogisms combined with the ??maximum impact?? strategy.  相似文献   

11.
Nonlinear feedback shift registers (NFSRs) are widely used in stream cipher design as building blocks. The cascade connection of NFSRs, known as an important architecture, has been adopted in Grain family of stream ciphers. In this paper, a new sufficient condition under which an NFSR cannot be decomposed into the cascade connection of two smaller NFSRs is presented, which is easy to be verified from the algebraic normal form (ANF) of the characteristic function. In fact, our results are also applicable to nonsingular Boolean functions, which actually improve a previous research of Rhodes [6] where the characteristic functions of NFSRs cannot be contained.  相似文献   

12.
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.  相似文献   

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

14.
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.  相似文献   

15.
In this paper, we propose a new loss-less symmetric image cipher based on the widely used substitution–diffusion architecture which utilizes chaotic standard and logistic maps. It is specifically designed for the coloured images, which are 3D arrays of data streams. The initial condition, system parameter of the chaotic standard map and number of iterations together constitute the secret key of the algorithm. The first round of substitution/confusion is achieved with the help of intermediate XORing keys calculated from the secret key. Then two rounds of diffusion namely the horizontal and vertical diffusions are completed by mixing the properties of horizontally and vertically adjacent pixels, respectively. In the fourth round, a robust substitution/confusion is accomplished by generating an intermediate chaotic key stream (CKS) image in a novel manner with the help of chaotic standard and logistic maps. The security and performance of the proposed image encryption technique has been analyzed thoroughly using various statistical analysis, key sensitivity analysis, differential analysis, key space analysis, speed analysis, etc. Results of the various types of analysis are encouraging and suggest that the proposed image encryption technique is able to manage the trade offs between the security and speed and hence suitable for the real-time secure image and video communication applications.  相似文献   

16.
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.  相似文献   

17.
Boolean functions with high nonlinearity and good autocorrelation properties play an important role in the design of block ciphers and stream ciphers. In this paper, we give a method to construct balanced Boolean functions of n variables, where n ≥ 10 is an even integer, satisfying strict avalanche criterion (SAC), and with high algebraic degree. Compared with the known balanced Boolean functions with SAC property, the constructed functions possess the highest nonlinearity and the best global avalanche characteristics property.  相似文献   

18.
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.  相似文献   

19.
布尔函数的代数免疫度是在流密码的代数攻击中所产生的重要概念.研究了代数免疫度为1的布尔函数,得到的主要结果有:对代数免疫度为1的布尔函数给出了一个谱刻画,给出了其个数的精确计数公式,最后给出了此类函数的非线性度的紧的上界.  相似文献   

20.
Register synthesis for multi-sequences has significance for the security of word-oriented stream ciphers. Feedback with carry shift registers (FCSRs) are promising alternatives to linear feedback shift registers for the design of stream ciphers. In this paper, we solve the FCSR synthesis problem for multi-sequences by two rational approximation algorithms using lattice theory. One is based on the lattice reduction greedy algorithm proposed by Nguyen and Stehlé (ACM Trans Algorithms (TALG) 5(4):46, 2009). The other is based on the LLL algorithm which is a polynomial time lattice reduction algorithm. Both of these rational approximation algorithms can find the smallest common FCSR for a given multi-sequence but with different numbers of known terms. When the number of sequences within the multi-sequence is less than or equal to 3, the former is suggested because it has better time complexity and fewer terms are needed. Otherwise, the latter will have better time complexity.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号