Paper 2020/089

The MILP-Aided Conditional Differential Attack and Its Application to Trivium

Chen-Dong Ye, Tian Tian, and 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.