## The MILP-aided conditional differential attack and its application to Trivium.(English)Zbl 1457.94198

Summary: Conditional differential attacks were proposed by S. Knellwolf et al. [Lect. Notes Comput. Sci. 6477, 130–145 (2010; Zbl 1253.94056)] 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(\mathbf{x,v})=\gamma_i\mid 1\le i\le N\}$$ be a set of conditions that we want to impose, where $$\mathbf{x}=(x_1,x_2,\ldots ,x_n)$$ (resp. $$\mathbf{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 out 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.

### MSC:

 94A60 Cryptography

### Keywords:

conditional differential attacks; MILP; Trivium

Zbl 1253.94056

### Software:

Gurobi; KATAN; SIMON; Grain; KTANTAN; Trivium
Full Text: