Cryptology ePrint Archive: Report 2016/407

MILP-Based Automatic Search Algorithms for Diff erential 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 ]