Paper 2019/1319

Automatic Search for the Linear (hull) Characteristics of ARX Ciphers: Applied to SPECK, SPARX, Chaskey and CHAM-64 (Full Version)

Mingjiang Huang and Liming Wang


Linear cryptanalysis is an important evaluation method for cryptographic primitives against key recovery attack. In this paper, we revisit the Walsh transformation for linear correlation calculation of modular addition, and an efficient algorithm is proposed to construct the input-output mask space of specified correlation weight. By filtering out the impossible large correlation weights in the first round, the search space of the first round can be substantially reduced. We introduce a new construction of combinational linear approximation table (cLAT) for modular addition with two inputs. When one input mask is fixed, another input mask and the output mask can be obtained by the \textit{Spliting-Lookup-Recombination} approach. We first split the $n$-bit fixed input mask into several sub-vectors, then, to find the corresponding bits of other masks, and in the recombination phase, pruning conditions can be used. By this approach, a large number of search branches in the middle rounds can be pruned. With the combination of the optimization strategies and the branch-and-bound search algorithm, we can improve the search efficiency for linear characteristics on ARX ciphers. The linear hulls for SPECK32/48/64 with higher average linear potential ($ALP$) than existing results have been obtained. For SPARX variants, a 11-round linear trail and a 10-round linear hull have been found for SPARX-64, a 10-round linear trail and a 9-round linear hull are obtained for SPARX-128. For Chaskey, a 5-round linear trail with correlation of $2^{-61}$ have been obtained. For CHAM-64, the 34/35-round optimal linear characteristics with correlation of $2^{-31}$/$2^{-33}$ are found.

Note: We added references [17,18] and added the comparison of relevant results.

Available format(s)
Secret-key cryptography
Publication info
Preprint. Minor revision.
SPECKSPARXChaskeyCHAMARXLinear cryptanalysisAutomatic searchBlock ciphers
Contact author(s)
huangmingjiang @ iie ac cn
2020-01-08: last of 2 revisions
2019-11-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mingjiang Huang and Liming Wang},
      title = {Automatic Search for the Linear (hull) Characteristics of ARX Ciphers: Applied to SPECK, SPARX, Chaskey and CHAM-64 (Full Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1319},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.