Cryptology ePrint Archive: Report 2016/407
MILP-Based Automatic Search Algorithms for Differential and Linear Trails for Speck
Kai Fu; Meiqin Wang; Yinghua Guo; Siwei Sun; Lei Hu
Abstract: In recent years, Mixed Integer Linear Programming (MILP) has been successfully applied in searching for differential characteristics and linear approximations in block ciphers and has produced the significant results for some ciphers such as SIMON (a family of lightweight and hardware-optimized block ciphers designed by NSA) etc.
However, in the literature, the MILP-based automatic search algorithm for differential characteristics and linear approximations is still infeasible for block ciphers such as ARX constructions.
In this paper, we propose an MILP-based method for automatic search for differential characteristics and linear approximations in ARX ciphers.
By researching the properties of differential characteristic and linear approximation of modular addition in ARX ciphers, we present a method to describe the differential characteristic and linear approximation with linear inequalities under the assumptions of independent inputs to the modular addition and independent rounds.
We use this representation as an input to the publicly available MILP optimizer Gurobi to search for differential characteristics and linear approximations for ARX ciphers.
As an illustration, we apply our method to Speck, a family of lightweight and software-optimized block ciphers designed by NSA, which results in the improved differential characteristics and linear approximations compared with the existing ones.
Moreover, we provide the improved differential attacks on Speck48, Speck64, Speck96 and Speck128, which are the best attacks on them in terms of the number of rounds.
Category / Keywords: Automatic Search, Differential Trail, Linear Trail, ARX, Speck
Original Publication (in the same form): IACR-FSE-2016
Date: received 24 Apr 2016
Contact author: mqwang at sdu edu cn
Available format(s): PDF | BibTeX Citation
Version: 20160425:191817 (All versions of this report)
Short URL: ia.cr/2016/407
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]