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

Abstract EN

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 concept 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 Splitting-Lookup-Recombination approach.

We first split the n-bit fixed input mask into several subvectors and then 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 a higher average linear potential (ALP) than existing results have been obtained.

For SPARX variants, an 11-round linear trail and a 10-round linear hull have been found for SPARX-64 and a 10-round linear trail and a 9-round linear hull are obtained for SPARX-128.

For Chaskey, a 5-round linear trail with a correlation of 2−61 has been obtained.

For CHAM-64, 34/35-round optimal linear characteristics with a correlation of 2−31/2−33 are found.