Welcome to the resource topic for 2020/089
Title:
The MILP-Aided Conditional Differential Attack and Its Application to Trivium
Authors: Chen-Dong Ye, Tian Tian, Fan-Yang Zeng
Abstract:Conditional differential attacks were proposed by Knellwolf et al. at ASIACRYPT 2010 which targeted at cryptographic primitives based on non-linear feedback shift registers. The main idea of conditional differential attacks lies in controlling the propagation of a difference through imposing some conditions on public/key variables. In this paper, we improve the conditional differential attack by introducing the mixed integer linear programming (MILP) method to it. Let J=\{f_i(\boldsymbol{x},\boldsymbol{v})=\gamma_i| 1\le i\le N\} be a set of conditions that we want to impose, where \boldsymbol{x}=(x_1,x_2,\ldots,x_n) (resp. \boldsymbol{v}=(v_1,v_2,\ldots,v_n)) represents key (resp. public) variables and \gamma_i \in\{0,1\} needs evaluating. Previous automatic conditional differential attacks evaluate \gamma_1,\gamma_2,\ldots,\gamma_N just in order with the preference to zero. Based on the MILP method, conditions in J could be automatically analysed together. In particular, to enhance the effect of conditional differential attacks, in our MILP models, we are concerned with minimizing the number of 1’s in \{\gamma_1,\gamma_2,\ldots,\gamma_N\} and maximizing the number of weak keys. ~~~We apply our method to analyse the security of Trivium. As a result, key-recovery attacks are preformed up to the 978-round Trivium and non-randomness is detected up to the 1108-round Trivium of its 1152 rounds both in the weak-key setting. All the results are the best known so far considering the number of rounds and could be experimentally verified. Hopefully, the new method would provide insights on conditional differential attacks and the security evaluation of Trivium.
ePrint: https://eprint.iacr.org/2020/089
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .