To improve the complexity of the differential-linear cryptanalysis, we refine a partitioning technique recently proposed by Biham and Carmeli to improve the linear cryptanalysis of addition operations. We also propose an analogue improvement of differential cryptanalysis of addition operations. Roughly speaking, these techniques reduce the data complexity of linear and differential attacks, at the cost of more processing time per data. It can be seen as the analogue for ARX ciphers of partial key guess and partial decryption for SBox-based ciphers.
When applied to the differential-linear attack against Chaskey, this partitioning technique greatly reduces the data complexity, and this also results in a reduced time complexity. While a basic differential-linear attack on 7 round takes 2^78 data and time (respectively 2^35 for 6 rounds), the improved attack requires only 2^48 data and 2^67 time (respectively 2^25 data and 2^29 time for 6 rounds).
We also show an application of the partitioning technique to FEAL-8X, and we hope that this technique will lead to a better understanding of the security of ARX designs.Category / Keywords: secret-key cryptography / Differential cryptanalysis, linear cryptanalysis, ARX, addition, partitioning, Chaskey, FEAL Original Publication (in the same form): IACR-EUROCRYPT-2016 Date: received 8 Oct 2015, last revised 22 Feb 2016 Contact author: Gaetan Leurent at inria fr Available format(s): PDF | BibTeX Citation Version: 20160222:234403 (All versions of this report) Short URL: ia.cr/2015/968 Discussion forum: Show discussion | Start new discussion