For nonlinear feedback shift registers (NFSRs), their greatest common subfamily may be not unique. Given two NFSRs, the authors only consider the case that their greatest common subfamily exists and is unique. If th...For nonlinear feedback shift registers (NFSRs), their greatest common subfamily may be not unique. Given two NFSRs, the authors only consider the case that their greatest common subfamily exists and is unique. If the greatest common subfamily is exactly the set of all sequences which can be generated by both of them, the authors can determine it by Grobner basis theory. Otherwise, the authors can determine it under some conditions and partly solve the problem.展开更多
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”.展开更多
Impossible differential cryptanalysis is an important approach to evaluate the security of block ciphers. In EUROCRYPT 2016, Sun, et al. proved that there exists no impossible differential longer than four rounds for ...Impossible differential cryptanalysis is an important approach to evaluate the security of block ciphers. In EUROCRYPT 2016, Sun, et al. proved that there exists no impossible differential longer than four rounds for the AES structure where S-boxes are arbitrary. In DCC 2019, Wang,et al. proved that any differential is possible for 5-round AES, assuming that the round keys are independent and uniformly random. In ASIACRYPT 2020, Hu, et al. used automatic search to show that there exists no one-byte active impossible differential for 5-round AES-128 considering the relations of 3-round keys. By algebraic methods, this paper theoretically proves that there exists no one-byte active impossible differential for 5-round AES even considering the relations of all round keys. Firstly,the authors prove the independence of ten bytes in the consecutive four round keys under the key schedule of AES-128. Then 5-round AES is decomposed to three subfunctions and the propagations of the considered differences in these subfunctions are discussed. Finally, the authors prove that the considered differential trails can be connected by the ten bytes of round keys. Furthermore, for any given one-byte active differential, there are at least 2^(51) master keys such that the differential is possible for 5-round AES-128.展开更多
The cube attack proposed by Dinur and Shamir is one of the most important key-recovery attacks against Trivium.Recently division property based cube attacks have been extensively studied and significantly improved.In ...The cube attack proposed by Dinur and Shamir is one of the most important key-recovery attacks against Trivium.Recently division property based cube attacks have been extensively studied and significantly improved.In particular,the MILP modeling technique for the three-subset division property without unknown subset proposed by Hao,et al.at EUROCRYPT 2020 and the new technique with nested monomial predictions proposed by Hu,et al.at ASIACRYPT 2021 are best techniques to recover exact superpolies in division property based cube attacks.Consequently,at this state of the art,whether a superpoly can be recovered in division property based cube attacks is mainly decided by the scale of the superpoly,that is,the number of terms.Hence the choice for proper cubes corresponding to low-complexity superpolies is more critical now.Some effective cube construction methods were proposed for experimental cube attacks,but not applicable to division property based cube attacks.In this paper,the authors propose a heuristic cube criterion and a cube sieve algorithm,which can be combined with the three-subset division property to recover a number of superpolies.Applied to815-round Trivium,the authors recovered 417 superpolies from 441 cubes obtained by our algorithm of sizes between 41 and 48.The success rate is 94.56%.There are 165 non-constant superpolies with degree less than 14.In order to demonstrate the significance of the new algorithm,the authors tested the best superpoly recovery technique at EUROCRYPT 2020 using random cubes of similar sizes on 815-round Trivium.The experimental result shows that no cube could be completely recovered within a given period of time because the superpolies for random cubes are too complex.展开更多
The Grain-v1 stream cipher has been selected in the eSTREAM hardware finalists. In this paper, the authors derive a new distinguishing attack on Grain-v1 with 111 initialization rounds in a single-key setting. To achi...The Grain-v1 stream cipher has been selected in the eSTREAM hardware finalists. In this paper, the authors derive a new distinguishing attack on Grain-v1 with 111 initialization rounds in a single-key setting. To achieve this goal, the authors present two delicate strategies targeting an obvious distinguishing probability of the output difference of reduced Grain-v1. The authors show that conditional differential cryptanalysis of reduced Grain-v1 with 111 initialization rounds could mount a distinguishing attack with success probability about 0.8281 for all secret keys. It is also shown that when the attacking round further increases to 112 and 113, the distributions of the output differences are nearly random. Thus far, to the best of the authors' knowledge, the attack on Grain-v1 with 111 initialization rounds is the best single-key cryptanalytic result for reduced versions of Grain-vl in terms of the number of attacking rounds.展开更多
基金supported by the Natural Science Foundation of China under Grant Nos.61272042,61100202and 61170235
文摘For nonlinear feedback shift registers (NFSRs), their greatest common subfamily may be not unique. Given two NFSRs, the authors only consider the case that their greatest common subfamily exists and is unique. If the greatest common subfamily is exactly the set of all sequences which can be generated by both of them, the authors can determine it by Grobner basis theory. Otherwise, the authors can determine it under some conditions and partly solve the problem.
基金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”.
基金supported by the National Cryptography Development Fund of China under Grant Nos.MMJJ20170103 and MMJJ20180204.
文摘Impossible differential cryptanalysis is an important approach to evaluate the security of block ciphers. In EUROCRYPT 2016, Sun, et al. proved that there exists no impossible differential longer than four rounds for the AES structure where S-boxes are arbitrary. In DCC 2019, Wang,et al. proved that any differential is possible for 5-round AES, assuming that the round keys are independent and uniformly random. In ASIACRYPT 2020, Hu, et al. used automatic search to show that there exists no one-byte active impossible differential for 5-round AES-128 considering the relations of 3-round keys. By algebraic methods, this paper theoretically proves that there exists no one-byte active impossible differential for 5-round AES even considering the relations of all round keys. Firstly,the authors prove the independence of ten bytes in the consecutive four round keys under the key schedule of AES-128. Then 5-round AES is decomposed to three subfunctions and the propagations of the considered differences in these subfunctions are discussed. Finally, the authors prove that the considered differential trails can be connected by the ten bytes of round keys. Furthermore, for any given one-byte active differential, there are at least 2^(51) master keys such that the differential is possible for 5-round AES-128.
基金supported by the National Natural Science Foundation of China under Grant No.61672533。
文摘The cube attack proposed by Dinur and Shamir is one of the most important key-recovery attacks against Trivium.Recently division property based cube attacks have been extensively studied and significantly improved.In particular,the MILP modeling technique for the three-subset division property without unknown subset proposed by Hao,et al.at EUROCRYPT 2020 and the new technique with nested monomial predictions proposed by Hu,et al.at ASIACRYPT 2021 are best techniques to recover exact superpolies in division property based cube attacks.Consequently,at this state of the art,whether a superpoly can be recovered in division property based cube attacks is mainly decided by the scale of the superpoly,that is,the number of terms.Hence the choice for proper cubes corresponding to low-complexity superpolies is more critical now.Some effective cube construction methods were proposed for experimental cube attacks,but not applicable to division property based cube attacks.In this paper,the authors propose a heuristic cube criterion and a cube sieve algorithm,which can be combined with the three-subset division property to recover a number of superpolies.Applied to815-round Trivium,the authors recovered 417 superpolies from 441 cubes obtained by our algorithm of sizes between 41 and 48.The success rate is 94.56%.There are 165 non-constant superpolies with degree less than 14.In order to demonstrate the significance of the new algorithm,the authors tested the best superpoly recovery technique at EUROCRYPT 2020 using random cubes of similar sizes on 815-round Trivium.The experimental result shows that no cube could be completely recovered within a given period of time because the superpolies for random cubes are too complex.
基金supported by the National Natural Science Foundation of China under Grant Nos.61521003and 61672533the National Cryptography Development Fund of China under Grant No.MMJJ20170103
文摘The Grain-v1 stream cipher has been selected in the eSTREAM hardware finalists. In this paper, the authors derive a new distinguishing attack on Grain-v1 with 111 initialization rounds in a single-key setting. To achieve this goal, the authors present two delicate strategies targeting an obvious distinguishing probability of the output difference of reduced Grain-v1. The authors show that conditional differential cryptanalysis of reduced Grain-v1 with 111 initialization rounds could mount a distinguishing attack with success probability about 0.8281 for all secret keys. It is also shown that when the attacking round further increases to 112 and 113, the distributions of the output differences are nearly random. Thus far, to the best of the authors' knowledge, the attack on Grain-v1 with 111 initialization rounds is the best single-key cryptanalytic result for reduced versions of Grain-vl in terms of the number of attacking rounds.