Paper 2016/409

Automatic Search for the Best Trails in ARX: Application to Block Cipher \textsc{Speck}

Alex Biryukov, Vesselin Velichkov, and Yann Le Corre


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 \textsc{Speck} family. More specifically, we report the probabilities of the best differential trails for up to 10, 9, 8, 7, and 7 rounds of \textsc{Speck32}, \textsc{Speck48}, \textsc{Speck64}, \textsc{Speck96} and \textsc{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 \textsc{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.

Available format(s)
Publication info
Published by the IACR in FSE 2016
Contact author(s)
alex biryukov @ uni lu
vesselin velichkov @ uni lu
yann lecorre @ uni lu
2016-04-25: received
Short URL
Creative Commons Attribution


      author = {Alex Biryukov and Vesselin Velichkov and Yann Le Corre},
      title = {Automatic Search for the Best Trails in ARX: Application to Block Cipher \textsc{Speck}},
      howpublished = {Cryptology ePrint Archive, Paper 2016/409},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.