A critical problem in the cube attack is how to recover superpolies efficiently.As the targeting number of rounds of an iterative stream cipher increases,the scale of its superpolies becomes larger and larger.Recently...A critical problem in the cube attack is how to recover superpolies efficiently.As the targeting number of rounds of an iterative stream cipher increases,the scale of its superpolies becomes larger and larger.Recently,to recover massive superpolies,the nested monomial prediction technique,the algorithm based on the divide-and-conquer strategy,and stretching cube attacks were proposed,which have been used to recover a superpoly with over ten million monomials for the NFSR-based stream ciphers such as Trivium and Grain-128AEAD.Nevertheless,when these methods are used to recover superpolies,many invalid calculations are performed,which makes recovering superpolies more difficult.This study finds an interesting observation that can be used to improve the above methods.Based on the observation,a new method is proposed to avoid a part of invalid calculations during the process of recovering superpolies.Then,the new method is applied to the nested monomial prediction technique and an improved superpoly recovery framework is presented.To verify the effectiveness of the proposed scheme,the improved framework is applied to 844-and 846-round Trivium and the exact ANFs of the superpolies is obtained with over one hundred million monomials,showing the improved superpoly recovery technique is powerful.Besides,extensive experiments on other scaled-down variants of NFSR-based stream ciphers show that the proposed scheme indeed could be more efficient on the superpoly recovery against NFSR-based stream ciphers.展开更多
Cube attacks, proposed by Dinur and Shamir at EUROCRYPT 2009, have shown huge power against stream ciphers. In the original cube attacks, a linear system of secret key bits is exploited for key recovery attacks. Howev...Cube attacks, proposed by Dinur and Shamir at EUROCRYPT 2009, have shown huge power against stream ciphers. In the original cube attacks, a linear system of secret key bits is exploited for key recovery attacks. However, we find a number of equations claimed linear in previous literature actually nonlinear and not fit into the theoretical framework of cube attacks. Moreover, cube attacks are hard to apply if linear equations are rare. Therefore, it is of significance to make use of probabilistic linear equations, namely nonlinear superpolys that can be approximated by linear expressions effectively. In this paper, we suggest a way to test out and utilize these probabilistic linear equations, thus extending cube attacks to a wider scope. Concretely, we employ the standard parameter estimation approach and the sequential probability ratio test （SPRT） for linearity test in the preprocessing phase, and use maximum likelihood decoding （MLD） for solving the probabilistic linear equations in the online phase. As an application, we exhibit our new attack against 672 rounds of Trivium and reduce the number of key bits to search by 7.展开更多
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.展开更多
基金National Natural Science Foundation of China(62372464)。
文摘A critical problem in the cube attack is how to recover superpolies efficiently.As the targeting number of rounds of an iterative stream cipher increases,the scale of its superpolies becomes larger and larger.Recently,to recover massive superpolies,the nested monomial prediction technique,the algorithm based on the divide-and-conquer strategy,and stretching cube attacks were proposed,which have been used to recover a superpoly with over ten million monomials for the NFSR-based stream ciphers such as Trivium and Grain-128AEAD.Nevertheless,when these methods are used to recover superpolies,many invalid calculations are performed,which makes recovering superpolies more difficult.This study finds an interesting observation that can be used to improve the above methods.Based on the observation,a new method is proposed to avoid a part of invalid calculations during the process of recovering superpolies.Then,the new method is applied to the nested monomial prediction technique and an improved superpoly recovery framework is presented.To verify the effectiveness of the proposed scheme,the improved framework is applied to 844-and 846-round Trivium and the exact ANFs of the superpolies is obtained with over one hundred million monomials,showing the improved superpoly recovery technique is powerful.Besides,extensive experiments on other scaled-down variants of NFSR-based stream ciphers show that the proposed scheme indeed could be more efficient on the superpoly recovery against NFSR-based stream ciphers.
文摘Cube attacks, proposed by Dinur and Shamir at EUROCRYPT 2009, have shown huge power against stream ciphers. In the original cube attacks, a linear system of secret key bits is exploited for key recovery attacks. However, we find a number of equations claimed linear in previous literature actually nonlinear and not fit into the theoretical framework of cube attacks. Moreover, cube attacks are hard to apply if linear equations are rare. Therefore, it is of significance to make use of probabilistic linear equations, namely nonlinear superpolys that can be approximated by linear expressions effectively. In this paper, we suggest a way to test out and utilize these probabilistic linear equations, thus extending cube attacks to a wider scope. Concretely, we employ the standard parameter estimation approach and the sequential probability ratio test （SPRT） for linearity test in the preprocessing phase, and use maximum likelihood decoding （MLD） for solving the probabilistic linear equations in the online phase. As an application, we exhibit our new attack against 672 rounds of Trivium and reduce the number of key bits to search by 7.
基金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.
