The MILP-aided conditional differential attack and its application to Trivium
- PDF / 422,909 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 63 Downloads / 149 Views
The MILP-aided conditional differential attack and its application to Trivium Chen-Dong Ye1 · Tian Tian1
· Fan-Yang Zeng1
Received: 1 May 2020 / Revised: 5 September 2020 / Accepted: 5 November 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
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 (x, v) = γi |1 ≤ i ≤ N } be a set of conditions that we want to impose, where x = (x1 , x2 , . . . , xn ) (resp. v = (v1 , v2 , . . . , vn )) represents key (resp. public) variables and γi ∈ {0, 1} needs evaluating. Previous automatic conditional differential attacks evaluate γ1 , γ2 , . . . , γ 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 {γ1 , γ2 , . . . , γ 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. Keywords Conditional differential attacks · MILP · Trivium Mathematics Subject Classification 94A60
Communicated by P. Charpin.
B
Tian Tian [email protected] Chen-Dong Ye [email protected] Fan-Yang Zeng [email protected]
1
PLA Strategic Supporting Force Information Engineering University, Zhengzhou, China
123
C.-D. Ye et al.
1 Introduction Recently non-linear feedback shift registers (NLFSR) are widely used in lightweight cryptographic primitives, for example, the eSTREAM finalist Trivium [2], another eSTREAM finalist Grain-v1 [13] and the block cipher KATAN [3]. Observing that an input difference propagates slowly in an NLFSR, Knellwolf et al. in [14] proposed conditional differential attacks against NLFSR-based cryptosystems. The main idea of conditional differential attacks is imposing conditions on public/key variables to make the propagation of the difference as slow as possible. If the propagation of differences is effectively prevented, then key-recovery attacks or distinguishing attacks could be established depending on the conditions. There are three types of conditions. Type 0 conditions only involve public variables. Type 1 conditions involv
Data Loading...
