Nonlinear feedback shift registers(NFSRs)are widely used as building blocks in the design of stream ciphers.Let NFSR(f)be an NFSR with the characteristic function f and let G(f)be the set of output sequences of NFSR(f...Nonlinear feedback shift registers(NFSRs)are widely used as building blocks in the design of stream ciphers.Let NFSR(f)be an NFSR with the characteristic function f and let G(f)be the set of output sequences of NFSR(f).For a given NFSR(f),if there exists an affine Boolean function l such that G(l)?G(f),then G(l)is called an affine sub-family of NFSR(f).In this paper,by skillfully combining previous ideas,the authors give a new upper bound on the order of affine sub-families of NFSR(f).Compared with the four known bounds,the bound is better than three of them,and in some cases is also better than the rest one.展开更多
The stability of Non-Linear Feedback Shift Registers(NFSRs)plays an important role in the cryptographic security.Due to the complexity of nonlinear systems and the lack of efficient algebraic tools,the theorems relate...The stability of Non-Linear Feedback Shift Registers(NFSRs)plays an important role in the cryptographic security.Due to the complexity of nonlinear systems and the lack of efficient algebraic tools,the theorems related to the stability of NFSRs are still not well-developed.In this paper,we view the NFSR with periodic inputs as a Boolean control network.Based on the mathematical tool of semi-tensor product(STP),the Boolean network can be mapped into an algebraic form.Through these basic theories,we analyze the state space of non-autonomous NFSRs,and discuss the stability of an NFSR with periodic inputs of limited length or unlimited length.The simulation results are provided to prove the efficiency of the model.Based on these works,we can provide a method to analyze the stability of the NFSR with periodic input,including limited length and unlimited length.By this,we can efficiently reduce the computational complexity,and its efficiency is demonstrated by applying the theorem in simulations dealing with the stability of a non-autonomous NFSR.展开更多
Trivium is an international standard of lightweight stream ciphers(ISO/IEC 29192-3:2012).In this paper,the Trivium-like NFSRs,a class of Galois NFSRs generalized from the Galois NFSR of Trivium,are studied from the pe...Trivium is an international standard of lightweight stream ciphers(ISO/IEC 29192-3:2012).In this paper,the Trivium-like NFSRs,a class of Galois NFSRs generalized from the Galois NFSR of Trivium,are studied from the perspective of Fibonacci NFSRs.It is shown that an n-stage Trivium-like NFSR cannot be equivalent to an n-stage Fibonacci NFSR,which is proved by showing the existence of“collision initial states”.As an intermediate conclusion,a necessary and sufficient condition for a kind of linear degeneracy of a Trivium-like NFSR is obtained from the persepective of interleaved sequences.Moreover,the smallest stage number of a Fibonacci NFSR that can generate all the output sequences of an n-stage Trivium-like NFSR is shown to be greater than n-7 and this value is no less than 371=287+min{93,84,111}specifically for the 288-stage Galois NFSR used in Trivium.These results contradict the existence of a equivalent Fibonacci model of Trivium NFSR of small stage,which implies that Trivium algorithm possesses a fair degree of immunity against“structure attack”.展开更多
Observability ensures that any two distinct initial states can be uniquely determined by their outputs,so the stream ciphers can avoid unobservable nonlinear feedback shift registers(NFSRs)to prevent the occurrence of...Observability ensures that any two distinct initial states can be uniquely determined by their outputs,so the stream ciphers can avoid unobservable nonlinear feedback shift registers(NFSRs)to prevent the occurrence of equivalent keys.This paper discusses the observability of Galois NFSRs over finite fields.Galois NFSRs are treated as logical networks using the semi-tensor product.The vector form of the state transition matrix is introduced,by which a necessary and sufficient condition is proposed,as well as an algorithm for determining the observability of general Galois NFSRs.Moreover,a new observability matrix is defined,which can derive a matrix method with lower computation complexity.Furthermore,the observability of two special types of Galois NFSRs,a full-length Galois NFSR and a nonsingular Galois NFSR,is investigated.Two methods are proposed to determine the observability of these two special types of NFSRs,and some numerical examples are provided to support these results.展开更多
Nonlinear feedback shift register(NFSR)is one of the most important cryptographic primitives in lightweight cryptography.At ASIACRYPT 2010,Knellwolf et al.proposed conditional differential attack to perform a cryptana...Nonlinear feedback shift register(NFSR)is one of the most important cryptographic primitives in lightweight cryptography.At ASIACRYPT 2010,Knellwolf et al.proposed conditional differential attack to perform a cryptanalysis on NFSR-based cryptosystems.The main idea of conditional differential attack is to restrain the propagation of the difference and obtain a detectable bias of the difference of the output bit.QUARK is a lightweight hash function family which is designed by Aumasson et al.at CHES 2010.Then the extended version of QUARK was published in Journal of Cryptology 2013.In this paper,we propose an improved conditional differential attack on QUARK.One improvement is that we propose a method to select the input difference.We could obtain a set of good input differences by this method.Another improvement is that we propose an automatic condition imposing algorithm to deal with the complicated conditions efficiently and easily.It is shown that with the improved conditional differential attack on QUARK,we can detect the bias of output difference at a higher round of QUARK.Compared to the current literature,we find a distinguisher of U-QUARK/D-QUARK/S-QUARK/C-QUARK up to 157/171/292/460 rounds with increasing 2/5/33/8 rounds respectively.We have performed the attacks on each instance of QUARK on a 3.30 GHz Intel Core i5 CPU,and all these attacks take practical complexities which have been fully verified by our experiments.As far as we know,all of these results have been the best thus far.展开更多
基金supported by the National Natural Science Foundation of China under Grant Nos.61872383,61379139,and 11701553part by the Strategic Priority Research Program of the Chinese Academy of Sciences under Grant No.XDA06010701+2 种基金supported by National Postdoctoral Program for Innovative Talents(BX201600188)China Postdoctoral Science Foundation Funded Project(2017M611035)Young Elite Scientists Sponsorship Program by CAST(2016QNRC001).
文摘Nonlinear feedback shift registers(NFSRs)are widely used as building blocks in the design of stream ciphers.Let NFSR(f)be an NFSR with the characteristic function f and let G(f)be the set of output sequences of NFSR(f).For a given NFSR(f),if there exists an affine Boolean function l such that G(l)?G(f),then G(l)is called an affine sub-family of NFSR(f).In this paper,by skillfully combining previous ideas,the authors give a new upper bound on the order of affine sub-families of NFSR(f).Compared with the four known bounds,the bound is better than three of them,and in some cases is also better than the rest one.
基金This work is supported by the National Natural Science Foundation of China(Grants Nos.61672020,U1803263,61662069,61762068,31560622,31260538,30960246,31672385,71761029)Project funded by China Postdoctoral Science Foundation(2013M542560,2015T81129)+6 种基金A Project of Shandong Province Higher Educational Science and Technology Program(No.J16LN61)Inner Mongolia Colleges and Universities Scientific and Technological Research Projects(Grant No.NJZC17148)CERNET Innovation Project(No.NGII20161209)Natural Science Foundation of Inner Mongolia Autonomous Region of china(No.2017MS0610,No.2017MS717)Program for Young Talents of Science and Technology in Universities of Inner Mongolia Autonomous Region(No.NJYT-18-A13)Inner Mongolia Key Laboratory of economic data analysis and mining China-Mongolia Scientific Research Capacity Building of Incubator,Joint Laboratory and Technology Transfer Center,Education research project of national finance and economics(No.MZCJYB1803)Postgraduate research and innovation project of Inner Mongolia university of finance and economics.
文摘The stability of Non-Linear Feedback Shift Registers(NFSRs)plays an important role in the cryptographic security.Due to the complexity of nonlinear systems and the lack of efficient algebraic tools,the theorems related to the stability of NFSRs are still not well-developed.In this paper,we view the NFSR with periodic inputs as a Boolean control network.Based on the mathematical tool of semi-tensor product(STP),the Boolean network can be mapped into an algebraic form.Through these basic theories,we analyze the state space of non-autonomous NFSRs,and discuss the stability of an NFSR with periodic inputs of limited length or unlimited length.The simulation results are provided to prove the efficiency of the model.Based on these works,we can provide a method to analyze the stability of the NFSR with periodic input,including limited length and unlimited length.By this,we can efficiently reduce the computational complexity,and its efficiency is demonstrated by applying the theorem in simulations dealing with the stability of a non-autonomous NFSR.
基金supported by the National Natural Science Foundation of China under Grant Nos.12371526,61872383,61802430,and 62202494。
文摘Trivium is an international standard of lightweight stream ciphers(ISO/IEC 29192-3:2012).In this paper,the Trivium-like NFSRs,a class of Galois NFSRs generalized from the Galois NFSR of Trivium,are studied from the perspective of Fibonacci NFSRs.It is shown that an n-stage Trivium-like NFSR cannot be equivalent to an n-stage Fibonacci NFSR,which is proved by showing the existence of“collision initial states”.As an intermediate conclusion,a necessary and sufficient condition for a kind of linear degeneracy of a Trivium-like NFSR is obtained from the persepective of interleaved sequences.Moreover,the smallest stage number of a Fibonacci NFSR that can generate all the output sequences of an n-stage Trivium-like NFSR is shown to be greater than n-7 and this value is no less than 371=287+min{93,84,111}specifically for the 288-stage Galois NFSR used in Trivium.These results contradict the existence of a equivalent Fibonacci model of Trivium NFSR of small stage,which implies that Trivium algorithm possesses a fair degree of immunity against“structure attack”.
基金the National Natural Science Foundation of China(No.61877036)。
文摘Observability ensures that any two distinct initial states can be uniquely determined by their outputs,so the stream ciphers can avoid unobservable nonlinear feedback shift registers(NFSRs)to prevent the occurrence of equivalent keys.This paper discusses the observability of Galois NFSRs over finite fields.Galois NFSRs are treated as logical networks using the semi-tensor product.The vector form of the state transition matrix is introduced,by which a necessary and sufficient condition is proposed,as well as an algorithm for determining the observability of general Galois NFSRs.Moreover,a new observability matrix is defined,which can derive a matrix method with lower computation complexity.Furthermore,the observability of two special types of Galois NFSRs,a full-length Galois NFSR and a nonsingular Galois NFSR,is investigated.Two methods are proposed to determine the observability of these two special types of NFSRs,and some numerical examples are provided to support these results.
基金This work was supported by the National Natural Science Foundation of China(Grant No.61872359,62122085 and 61936008)the National Key R&D Program of China(Grant No.2020YFB1805402),and the Youth Innovation Promotion Association of Chinese Academy of Sciences.
文摘Nonlinear feedback shift register(NFSR)is one of the most important cryptographic primitives in lightweight cryptography.At ASIACRYPT 2010,Knellwolf et al.proposed conditional differential attack to perform a cryptanalysis on NFSR-based cryptosystems.The main idea of conditional differential attack is to restrain the propagation of the difference and obtain a detectable bias of the difference of the output bit.QUARK is a lightweight hash function family which is designed by Aumasson et al.at CHES 2010.Then the extended version of QUARK was published in Journal of Cryptology 2013.In this paper,we propose an improved conditional differential attack on QUARK.One improvement is that we propose a method to select the input difference.We could obtain a set of good input differences by this method.Another improvement is that we propose an automatic condition imposing algorithm to deal with the complicated conditions efficiently and easily.It is shown that with the improved conditional differential attack on QUARK,we can detect the bias of output difference at a higher round of QUARK.Compared to the current literature,we find a distinguisher of U-QUARK/D-QUARK/S-QUARK/C-QUARK up to 157/171/292/460 rounds with increasing 2/5/33/8 rounds respectively.We have performed the attacks on each instance of QUARK on a 3.30 GHz Intel Core i5 CPU,and all these attacks take practical complexities which have been fully verified by our experiments.As far as we know,all of these results have been the best thus far.
