Automatic Search for the Best Trails in ARX: Application to Block Cipher Speck

Alex Biryukov, Vesselin Velichkov, Yann Le Corre

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We propose the first adaptation of Matsui's algorithm for finding the best differential and linear trails to the class of ARX ciphers. It is based on a branch-and-bound search strategy, does not use any heuristics and returns optimal results. The practical application of the new algorithm is demonstrated on reduced round variants of block ciphers from the Speck family. More specifically, we report the probabilities of the best differential trails for up to 10, 9, 8, 7, and 7 rounds of Speck32, Speck48, Speck64, Speck96 and Speck128 respectively, together with the exact number of differential trails that have the best probability. The new results are used to compute bounds, under the Markov assumption, on the security of Speck against single-trail differential cryptanalysis. Finally, we propose two new ARX primitives with provable bounds against single-trail differential and linear cryptanalysis -- a long standing open problem in the area of ARX design.
Original languageEnglish
Title of host publicationFast Software Encryption
Subtitle of host publication23rd International Conference, FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected Papers
EditorsThomas Peyrin
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages22
ISBN (Electronic)978-3-662-52993-5
ISBN (Print)978-3-662-52992-8
Publication statusE-pub ahead of print - 20 Jul 2016
Event24th ACM SIGSOFT International Symposium on the Foundations of Software Engineering - Seattle, United States
Duration: 13 Nov 201618 Nov 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Berlin, Heidelberg
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameSecurity and Cryptology


Conference24th ACM SIGSOFT International Symposium on the Foundations of Software Engineering
Abbreviated titleFSE 2016
Country/TerritoryUnited States
Internet address

Cite this