Automatic Search for Linear Trails of the SPECK Family

Abstract

SPECK is a lightweight block cipher family designed by the U.S. National Security Agency and published in 2013. Although several cryptanalyses have been applied since then, no linear results have been proposed. In this paper, we apply Wallén’s enumeration algorithm to Matsui’s branch-and-bound framework and find the best correlations of SPECK reduced to various rounds, i.e. full rounds of SPECK-32 and 7/ 5/ 4/ 4 rounds of SPECK-48/ 64/ 96/ 128. Since the best 10-round correlation of SPECK-32 is as small as $2^{-17}$ already, SPECK-32 is immune to the 1-dimensional linear cryptanalysis. Moreover, we present several distinguishers and key recovery attacks as an application of the linear trails. Besides the search for linear trails, we also discuss possible implementations of the Wallén’s algorithm and provide an implementation which is faster than the straightforward implementations.

This work is supported by the National Basic Research Program of China (No. 2013CB338002).

1 Introduction

The SPECK family [1] is based on a Feistel-like structure and belongs to the ARX ciphers, i.e. primitives composed of modulo addition, bitwise rotation and bitwise XOR only. It is designed to provide optimal software performance on resource constrained devices and is comprised of five variants according to the block size. Despite of its simple structure, no cryptanalysis has threatened its security and particularly no linear cryptanalysis has been proposed due to the intrinsic property of modulo addition. The best previously published attacks are the improved differential cryptanalysis provided by Dinur at SAC 2014 [4].

Generally, good linear trails/approximations should be found in advance in order to launch linear attacks. A widely used approach to search for linear trails of block ciphers is the general framework proposed by Matsui at EUROCRYPT 1994 [8] and it is straightforward to apply as long as the linear approximation table (LAT) of sub-components is obtained. However, the complexity to compute the LAT varies greatly from cipher to cipher. In particular, the time/memory complexity of addition modulo $2^{n}$ is $O(2^{3n})$ for a plain enumeration which is nearly impractical even with $n=16$. Whereas the problem exists in the search for differential trails as well, Biryukov [2] has recently proposed a technique using partial differential distribution tables, called the threshold search, and successfully conquered this problem. Fortunately, Wallén has already provided an efficient algorithm to enumerate the LAT of modulo addition at FSE 2003 [10], thus linear approximations could be generated on the fly until it is necessary. The algorithm is further rediscovered in [9] using another approach and its efficiency has been proved by the application to SNOW 2.0 [9] and SOSEMANUK [3]. In case of possible confusions, it should be noted that another algorithm which determines the correlation of a given linear approximation with $O(\log (n))$ time was presented by Wallén in [10] as well. As the latter algorithm is never used in this paper, the Wallén’s algorithm in this paper always refers to the algorithm to enumerate the LAT.

By combining Wallén’s algorithm and Matsui’s branch-and-bound framework, we are able to find the best linear trail of SPECK-32 of full rounds and the best linear trail of SPECK-48/ 64/ 96/ 128 reduced to 7/ 5/ 4/ 4 rounds respectively, shown in Tables 1 and 2 where “$\ge$” denotes a lower bound of the best correlation. Since the data complexity of a 1-dimensional linear cryptanalysis is inversely proportional to the square of the correlation, the best 10-round correlation in Table 1 suggests that SPECK-32 is secure under this method. Indeed, the data complexity of a 1-dimensional linear cryptanalysis against SPECK-32 using the 10-round linear trail is $2^{34}$, greater than the size of the code book which is $2^{32}$. Moreover, we provide several distinguishers and key recovery attacks as an application of the linear trails. Yet, they do not pose a threat to SPECK and are worse than the differential cryptanalyses of Dinur. After all, this is the first linear cryptanalysis against the SPECK family, evaluating the security in a different perspective.

Table 1. Best correlations for SPECK-32

Table 2. Best correlations for SPECK48/ 64/ 96/ 128 (“$\ge$” indicates a lower bound)

We additionally find a set of necessary conditions for correlations to be non-zero which allows us to develop an alternative implementation of Wallén’s algorithm. According to experiments, this implementation is faster than straightforward implementations derived from the Wallén’s theorem and thus useful when called for a tremendous number of times.

The rest of this paper is organized as follows. Section 2 introduces SPECK, Matsui’s branch-and-bound framework and the previous Wallén’s results on linear approximation of modulo addition. Section 3 describes the search for linear trails on SPECK and the cryptanalytic results. Section 4 provides the alternative implementation of Wallén’s algorithm. Finally, Sect. 5 draws conclusions.

2 Preliminaries

2.1 Notions

2.2 Description of SPECK

SPECK is a family of block ciphers containing five variants according to the block size which can be further divided into ten variants regarding the key size. Each variant has two constants $\varsigma ,\tau$ depending on the block size, i.e. $\varsigma =7,\tau =2$ for SPECK-32 and $\varsigma =8,\tau =3$ otherwise. The i-th round function (Fig. 1) is defined by

$$\begin{aligned} \varvec{x}\left[ i+1\right]&\leftarrow \left( \left( \varvec{x}\left[ i\right] \ggg \varsigma \right) \boxplus \varvec{y}\left[ i\right] \right) \oplus \varvec{k}\left[ i\right] \\ \varvec{y}\left[ i+1\right]&\leftarrow \left( \varvec{y}\left[ i\right] \lll \tau \right) \oplus \varvec{x}\left[ i+1\right] \end{aligned}$$

where $\varvec{x}[i]$ and $\varvec{y}[i]$ denote the left and right block of the input respectively, and $\varvec{k}[i]$ is the round-key. The key schedule algorithm is omitted since it is irrelevant to the search, but it should be noted that the master key can be recovered with successive round-keys. For more details, please refer to [1].

Fig. 1.

The round function of SPECK

2.3 Automatic Search Framework

The following is an introduction to the general branch-and-bound search framework proposed by Matsui at EUROCRYPT 1994 [8] in the language of linear cryptanalysis.

To find the best correlation of r successive rounds B[r], the framework performs a recursive search from the knowledge of shorter rounds $B[1],\dots ,B[r-1]$ and an initial estimate $\hat{B}[r]$ such that ${|}{\hat{B}[r]}{|} <{|}{B[r]}{|}$. In the search phase, an s-round trail is kept only if

$$\begin{aligned} {|}{B[r-s]\prod _{i=1}^{s}c[i]}{|} >{|}{\hat{B}[r]}{|},1\le s\le r \end{aligned}$$

where c[i] denotes the correlation of the i-th round and B[0] is defined to be 1. $\hat{B}[r]$ is updated once the correlation of a r-round trail is better than $\hat{B}[r]$. Therefore, $B[r]=\hat{B}[r]$ when the search completes. Algorithm 1 is an overview where $Get\_Mask$ is a cipher dependent function to extend linear trails.

2.4 Linear Approximation of Modulo Addition

In this subsection, we briefly introduce Wallén’s results on linear approximations of addition modulo $2^{n}$ in [10, 11].

Definition 1

(Correlation). Let $\varvec{u}$ be the output mask of the modulo addition and $\varvec{v},\varvec{w}$ be the input masks. Then the correlation is defined by

$$\begin{aligned} c\left( \varvec{u},\varvec{v},\varvec{w}\right) \triangleq 2\Pr \left( \varvec{u}\cdot \left( \varvec{Z}_{1}\boxplus \varvec{Z}_{2}\right) \oplus \varvec{v}\cdot \varvec{Z}_{1}\oplus \varvec{w}\cdot \varvec{Z}_{2}=0\right) -1 \end{aligned}$$

where $\varvec{Z}_{1},\varvec{Z}_{2}$ are independent uniform distributed random variables.

The Enumeration Algorithm.

Theorem 1

[9, 11] Let $S^{0}(0,0)\triangleq \{null\}$, $S^{0}(n,k)=S^{1}(n,k)\triangleq \emptyset$ when $k<0$ or $k\ge n>0$, and

$$\begin{aligned} S^{0}(n,k)&\triangleq \left( S^{0}(n-1,k)\parallel \{0\}\right) \cup \left( S^{1}(n-1,k-1)\parallel \{1,2,4,7\}\right) \end{aligned}$$

(1)

$$\begin{aligned} S^{1}(n,k)&\triangleq \left( S^{0}(n-1,k)\parallel \{7\}\right) \cup \left( S^{1}(n-1,k-1)\parallel \{0,3,5,6\}\right) \end{aligned}$$

(2)

otherwise, where $S^{\star }\parallel {\varOmega }\triangleq \{\varvec{a}\parallel \varvec{b}\mid \varvec{a}\in S^{\star },\varvec{b}\in {\varOmega }\}$. Then

$$\begin{aligned} S(n,k)\triangleq \big \{(\varvec{u},\varvec{v},\varvec{w})\mid 4u_{i}+2v_{i}+w_{i}=&s_{i},i=0,\dots ,n-1,\\&\qquad \qquad \,\varvec{s}\in S^{0}(n,k)\cup S^{1}(n,k)\big \} \end{aligned}$$

is the set of all masks such that $c\left( \varvec{u},\varvec{v},\varvec{w}\right) =\pm 2^{-k}$.

Example 1

$S^{0}(n,0)=\{(0\cdots 0)\},S^{1}(n,0)=\{(0\cdots 07)\}$, thus $S(n,0)=\{((0\cdots 0),(0\cdots 0),(0\cdots 0)),((0\cdots 01),(0\cdots 01),(0\cdots 01))\}$ is the set of all masks such that $c\left( \varvec{u},\varvec{v},\varvec{w}\right) =\pm 1$.

As was pointed out by Wallén, the LAT of addition modulo $2^{n}$ can be enumerated using O(n) space via Theorem 1. A trivial implementation, called the top-down method in this paper, can be deduced as shown in Fig. 2(a) and Appendix A.1. However, it is inefficient in the sense that the same subtree will be generated for multiple times. Another possible implementation is the bottom-up method which is shown in Fig. 2(b) and Appendix A.2, i.e. starting from $S^{0}(0,0)$ and then computing S(1, 0) etc. While it also generates duplicate subtrees, surprisingly it is faster than the top-down method. (See Fig. 5 for the comparison)

Fig. 2.

The computational process of S(4, 2)

Common Prefix Mask vs. Correlation. This subsection serves for the alternative implementation of the above algorithm and may be skipped safely to understand the search.

Definition 2

(CPM). Let $\varvec{a},\varvec{b}\in \mathbb {F}_{2}^{n}$. If $n=2$, the common prefix mask of $\varvec{a},\varvec{b}$ is defined by

$$\begin{aligned} cpm_{2}\left( \varvec{a},\varvec{b}\right) =a_{1} \end{aligned}$$

If $n>2$, the common prefix mask of $\varvec{a},\varvec{b}$ is defined by

$$\begin{aligned} cpm_{n}\left( \varvec{a},\varvec{b}\right) =a_{n-1}\parallel cpm_{n-1}\left( \left( a_{n-2}\oplus a_{n-1}\cdot b_{n-2}\right) \parallel \varvec{a}',1\parallel \varvec{b}'\right) \end{aligned}$$

where $\varvec{a}'=\left( a_{n-3},\dots ,a_{0}\right)$ and $\varvec{b}'=(b_{n-3},\dots ,b_{0})$.¹

Lemma 1

[10] Let $\varvec{u},\varvec{v},\varvec{w}\in \mathbb {F}_{2}^{n}$ be defined as in Definition 1, $\varvec{\phi }=\varvec{v}\oplus \varvec{u},\varvec{\varphi }=\varvec{w}\oplus \varvec{u}$ be the input masks of the carry function, $\varvec{\gamma }=\varvec{v}\oplus \varvec{w}$ and $\varvec{\delta }=cpm_{n+1}(0\parallel \varvec{u},\left( 0\parallel \varvec{\gamma }\right) \oplus \varvec{1})$. Then

$$\begin{aligned} c\left( \varvec{u},\varvec{v},\varvec{w}\right) ={\left\{ \begin{array}{ll} \left( -1\right) ^{wt\left( \varvec{\delta }\varvec{\phi }\varvec{\varphi }\right) }2^{-wt\left( \varvec{\delta }\right) }, &{} \text {if }\varvec{\phi }=\varvec{\phi }\varvec{\delta }\text { and }\varvec{\varphi }=\varvec{\varphi }\varvec{\delta }\\ 0, &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

where wt is the hamming weight.

Example 2

Suppose $\varvec{u}=(1100),\varvec{v}=\varvec{w}=\left( 1000\right)$, then $\varvec{\phi }=\varvec{\varphi }=(0100),\varvec{\gamma }=\left( 0000\right)$ and $\varvec{\delta }=(0100)$. Thus, $c(\varvec{u},\varvec{v},\varvec{w})=-2^{-1}$.

3 Linear Results on SPECK

3.1 Details of the Search

In this section, we will concentrate on the design of $Get\_Mask$ which will be used to extend linear trails by Algorithm 1. Firstly, we recall the linear properties of branch, bitwise XOR and bitwise rotation.

Fig. 3.

The spread of linear masks

Property 1

Let $\varvec{\varGamma }_{1},\varvec{\varGamma }_{2},\varvec{\varGamma }_{3}$ be linear masks defined by Fig. 3(a), then the correlation is nonzero if and only if $\varvec{\varGamma }_{1}\oplus \varvec{\varGamma }_{2}\oplus \varvec{\varGamma }_{3}=\varvec{0}$.

Property 2

Let $\varvec{\varGamma }_{1},\varvec{\varGamma }_{2},\varvec{\varGamma }_{3}$ be linear masks defined by Fig. 3(b) then the correlation is nonzero if and only if $\varvec{\varGamma }_{1}=\varvec{\varGamma }_{2}=\varvec{\varGamma }_{3}$.

Property 3

Let $\varvec{\varGamma }_{1},\varvec{\varGamma }_{2}$ be linear masks defined by Fig. 3(c) then the correlation is nonzero if and only if $\varvec{\varGamma }_{2}=\varvec{\varGamma }_{1}\lll t$.

Let the linear masks of the i-th round be defined in Fig. 4. Accordingly,

$$\begin{aligned} \varvec{u}[i]&=\varvec{X}[i+1]\oplus \varvec{Y}[i+1]\\ \varvec{v}[i]&=\varvec{X}[i]\ggg \varsigma \\ \varvec{w}[i]&=\varvec{Y}[i]\oplus \left( \varvec{Y}[i+1]\ggg \tau \right) \end{aligned}$$

Thereupon,

and

If we enumerate $\varvec{X}[r+1]$ and $\varvec{Y}[r+1]$ directly, the complexity is at least $2^{2n}$ and it is a waste of efforts on masks with insignificant correlations at the initial stage. Since $\varvec{X}[r+1],\varvec{Y}[r+1]$ are uniquely determined by $\varvec{u}[r],\varvec{v}[r],\varvec{w}[r],\varvec{u}[r-1]$, it is equivalently and more efficiently to enumerate $\varvec{u}[r],\varvec{v}[r],\varvec{w}[r],\varvec{u}[r-1]$ using the Wallén’s algorithm. On the other hand, when $1\le i\le r-2$, $\varvec{u}[i]$ can be deduced from the two following rounds. As a result, we have presented a method to extend linear trails by appending one round to the front and Algorithm 2 is the corresponding implementation of $Get\_Mask$.

Fig. 4.

Masks of the i-th round

3.2 Search Results

The automatic search is applied to variants of all block sizes and the best correlations are presented in Tables 1 and 2. Since the quotient of the best correlations of successive rounds is quite regular, $\hat{B}[r]$ is set to $2^{-3}B[r-1]$ for most of the cases. However, not all searches can finish in a reasonable time period due to the huge size of the search space, even with a tight threshold (e.g. $\hat{B}[r]\approx B[r]$). Thus, the “$\ge$” in the Table 2 denotes the best correlation that has been found in this case, i.e. a lower bound.

3.3 Linear Distinguishers

A Linear Distinguisher identifies the nonuniformity of a cipher and generally converts to a hypothesis testing problem using statistical tools. In this and subsequent sections, we make the common assumption that the correlation of a linear approximation can be estimated by the correlation of a significant linear trail. Moreover, the data complexity to distinguish two probability distributions D and $D_{0}$ is estimated by $C\left( D,D_{0}\right) ^{-1}$ (see [5] for example) with the capacity

Since

and $\varvec{k}[i-1]\cdot \left( \varvec{X}[i]\oplus \varvec{Y}[i]\right)$ is constant, the absolute value of the correlation of

$$\begin{aligned} \varvec{x}[2]\cdot \varvec{X}[2]\oplus \varvec{y}[2]\cdot \varvec{Y}[2]\oplus \varvec{x}[2+r]\cdot \varvec{X}[2+r]\oplus \varvec{y}[2+r]\cdot \varvec{Y}[2+r] \end{aligned}$$

can be calculated from $\varvec{x}[1],\varvec{y}[1],\varvec{x}[2+r],\varvec{y}[2+r]$ without $\varvec{k}[1]$. In other words, a r-round linear trail can be transformed into a $(r+1)$-round linear distinguisher by appending one round to the front. Thus, we immediately obtain the results in Table 3.

Table 3. Linear distinguishers against the SPECK family

3.4 Key Recovery Attacks

For key recovery attacks, we adopt the $\chi ^{2}$ extension of Matsui’s Algorithm 2 which was presented by Hermelin et al. in [6] and does not require the distribution of the linear approximation for the correct key.

Let $h(\varvec{a})$ denote one plus the position of the most-significant one of $\varvec{a}$ and $\varvec{a}^{\boxplus }\triangleq 2^{h(\varvec{a})}-1$. Because

guessing $\varvec{k}[i]\varvec{v}[i]^{\boxplus }$ is enough to calculate

$$\begin{aligned} \varvec{x}[i]\cdot \varvec{X}[i]\oplus \varvec{y}[i]\cdot \varvec{Y}[i]&=(\varvec{x}[i]\ggg \varsigma )\cdot \varvec{v}[i]\oplus \varvec{y}[i]\cdot \varvec{Y}[i]\\&=\left( (\varvec{x}[i]\ggg \varsigma )\varvec{v}[i]^{\boxplus }\right) \cdot \varvec{v}[i]\oplus \varvec{y}[i]\cdot \varvec{Y}[i]\\&=\left( \left( \varvec{x}[i+1]\varvec{v}[i]^{\boxplus }\oplus \varvec{k}[i]\varvec{v}[i]^{\boxplus }\right) \underset{h\left( \varvec{v}[i]\right) }{\boxminus }\varvec{y}[i]\right) \cdot \varvec{v}[i]\oplus \varvec{y}[i]\cdot \\&\qquad \varvec{Y}[i] \end{aligned}$$

from $\varvec{x}[i+1],\varvec{y}[i+1]$. Therefore, if m rounds are appended to the back of a r-round distinguisher, then only

$$\begin{aligned} h(\varvec{v}[r+1])+(m-1)n&=h(\left( \varvec{u}[r]\oplus \varvec{Y}[r+1]\right) \ggg \varsigma )+(m-1)n\\&=h(\left( \varvec{u}[r]\oplus \left( \left( \varvec{w}[r]\oplus \varvec{Y}[r]\right) \lll \tau \right) \right) \ggg \varsigma )+(m-1)n\\&=h((\varvec{u}[r]\oplus (\left( \varvec{w}[r]\oplus \left( \varvec{u}[r-1]\oplus \left( \varvec{v}[r]\lll \varsigma \right) \right) \right) \lll \tau ))\ggg \\&\qquad \varsigma )+(m-1)n \end{aligned}$$

bits of key need to be guessed, i.e. $\varvec{k}[r+1]\varvec{v}[r+1]^{\boxplus },\varvec{k}[r+2],\dots ,\varvec{k}[r+m]$. Consequently, we have Table 4 where

and $\alpha ,\beta$ are missing detection and false alarm probabilities respectively. Moreover, the results may be improved by trails of smaller $h(\varvec{v}[r+1])$ or vectorial linear approximations. But it seems unable to be improved by the similar technique of [4] since the size of the equation derived from a sub-cipher is one bit instead of 2n bits in the case of 1-dimensional linear cryptanalysis.

Table 4. Key recovery attacks on the SPECK family

4 Another Implementation of Wallén’s Algorithm

In this section, we present another implementation of Wallén’s algorithm, called the CPM method, and compare the performance of different implementations. Firstly, a set of necessary conditions for correlations to be non-zero needs to be proved.

Lemma 2

Let $\varvec{u},\varvec{\gamma },\varvec{\delta }\in \mathbb {F}_{2}^{n}$. Then

$$\begin{aligned} \varvec{\delta }=cpm_{n+1}\left( 0\parallel \varvec{u},\left( 0\parallel \varvec{\gamma }\right) \oplus \varvec{1}\right) \Longleftrightarrow \varvec{\delta }=\left( \varvec{u}\oplus \left( \varvec{\gamma }\oplus \varvec{1}\right) \varvec{\delta }\right) \gg 1 \end{aligned}$$

Proof

“$\Longrightarrow$”. From Definition 2, it is clear that $\delta _{n-1}=0$ and $\delta _{i}=u_{i+1}\oplus (\gamma _{i+1}\oplus 1)\delta _{i+1},i=0,\dots ,n-2$.

“$\Longleftarrow$ ”. Suppose $\varvec{\delta }'=cpm_{n+1}(0\parallel \varvec{u},(0\parallel \varvec{\gamma })\oplus \varvec{1})$, then $\delta _{i}'=u_{i+1}\oplus (\gamma _{i+1}\oplus 1)\delta _{i+1}',i=0,\dots ,n-2$. Thus $\delta _{i}\oplus \delta _{i}'=(\gamma _{i+1}\oplus 1)(\delta _{i+1}\oplus \delta _{i+1}'),i=0,\dots ,n-2$. Finally, $\delta _{n-2}=\delta _{n-2}',\dots ,\delta _{0}=\delta _{0}'$ following from $\delta _{n-1}=\delta _{n-1}'=0$.    $\square$

Theorem 2

Let $\varvec{u},\varvec{v},\varvec{w},\varvec{\phi },\varvec{\varphi },\varvec{\delta }\in \mathbb {F}_{2}^{n}$ and $\varvec{\phi }=\varvec{v}\oplus \varvec{u},\varvec{\varphi }=\varvec{w}\oplus \varvec{u},\varvec{\gamma }=\varvec{v}\oplus \varvec{w}$. Then

$$\begin{aligned} \varvec{\delta }=cpm_{n+1}(0\parallel \varvec{u},(0\parallel \varvec{\gamma })\oplus \varvec{1}),c(\varvec{u},\varvec{v},\varvec{w})\ne 0 \end{aligned}$$

if and only if

$$\begin{aligned} \varvec{\phi } =\varvec{\phi }\varvec{\delta } \end{aligned}$$

(3)

$$\begin{aligned} \varvec{\varphi } =\varvec{\varphi }\varvec{\delta } \end{aligned}$$

(4)

$$\begin{aligned} \varvec{\gamma }\gg 1 =\left( \left( \varvec{u}\oplus \varvec{\delta }\right) \gg 1\right) \oplus \varvec{\delta } \end{aligned}$$

(5)

$$\begin{aligned} \varvec{0} =\left( \left( \varvec{u}\gg 1\right) \oplus \varvec{\delta }\right) \left( \left( \varvec{\delta }\oplus \varvec{1}\right) \gg 1\right) \end{aligned}$$

(6)

$$\begin{aligned} \varvec{0} =\left( \left( \varvec{v}\gg 1\right) \oplus \varvec{\delta }\right) \left( \left( \varvec{\delta }\oplus \varvec{1}\right) \gg 1\right) \end{aligned}$$

(7)

$$\begin{aligned} \varvec{0} =\left( \left( \varvec{w}\gg 1\right) \oplus \varvec{\delta }\right) \left( \left( \varvec{\delta }\oplus \varvec{1}\right) \gg 1\right) \end{aligned}$$

(8)

Proof

Proof of the only-if-part. Since $c\left( \varvec{u},\varvec{v},\varvec{w}\right) \ne 0$, (3) and (4) follow from Lemma 1 directly. According to Lemma 2, $\varvec{\delta }=(\varvec{u}\oplus (\varvec{\gamma }\oplus \varvec{1})\varvec{\delta })\gg 1$. Hence,

$$\begin{aligned} \left( \left( \varvec{u}\oplus \varvec{\delta }\right) \gg 1\right) \oplus \varvec{\delta }&=\left( \left( \varvec{u}\oplus \varvec{\delta }\right) \oplus \left( \varvec{u}\oplus \left( \varvec{\gamma }\oplus \varvec{1}\right) \varvec{\delta }\right) \right) \gg 1=\left( \varvec{\gamma }\varvec{\delta }\right) \gg 1\\&=\left( \left( \varvec{\phi }\oplus \varvec{\varphi }\right) \varvec{\delta }\right) \gg 1=\left( \varvec{\phi }\oplus \varvec{\varphi }\right) \gg 1={{\varvec{\gamma }}}\gg 1 \end{aligned}$$

Accordingly,

$$\begin{aligned} \varvec{0}&=\varvec{\gamma }\left( \varvec{\delta }\oplus \varvec{1}\right) =\left( \varvec{\gamma }\left( \varvec{\delta }\oplus \varvec{1}\right) \right) \gg 1=\left( \varvec{\gamma }\gg 1\right) \left( \left( \varvec{\delta }\oplus \varvec{1}\right) \gg 1\right) \\&=\left( \left( \left( \varvec{u}\oplus \varvec{\delta }\right) \gg 1\right) \oplus \varvec{\delta }\right) \left( \left( \varvec{\delta }\oplus \varvec{1}\right) \gg 1\right) \\&=\left( \left( \varvec{u}\gg 1\right) \oplus \varvec{\delta }\right) \left( \left( \varvec{\delta }\oplus \varvec{1}\right) \gg 1\right) \oplus ((\varvec{\delta }(\varvec{\delta }\oplus \varvec{1}))\gg 1)\\&=\left( \left( \varvec{u}\gg 1\right) \oplus \varvec{\delta }\right) \left( \left( \varvec{\delta }\oplus \varvec{1}\right) \gg 1\right) \end{aligned}$$

(3) implies $\left( \varvec{\phi }\left( \varvec{\delta }\oplus \varvec{1}\right) \right) \gg 1=\varvec{0}$, thus

(8) holds similarly.

Proof of the if-part. From (5),

$$\begin{aligned} \left( \left( \varvec{u}\oplus \varvec{\delta }\right) \gg 1\right) \oplus \varvec{\delta }&={{\varvec{\gamma }}}\gg 1=\left( \varvec{\gamma }\varvec{\delta }\right) \gg 1=\left( \varvec{u}\oplus \varvec{\gamma }\varvec{\delta }\oplus \varvec{\delta }\oplus \varvec{\delta }\oplus \varvec{u}\right) \gg 1\\&=\left( \left( \varvec{u}\oplus \left( \varvec{\gamma }\oplus \varvec{1}\right) \varvec{\delta }\right) \gg 1\right) \oplus \left( \left( \varvec{\delta }\oplus \varvec{u}\right) \gg 1\right) \end{aligned}$$

Therefore,

$$\begin{aligned} \varvec{\delta }=\left( \varvec{u}\oplus \left( \varvec{\gamma }\oplus \varvec{1}\right) \varvec{\delta }\right) \gg 1=cpm_{n+1}\left( 0\parallel \varvec{u},\left( 0\parallel \varvec{\gamma }\right) \oplus \varvec{1}\right) \end{aligned}$$

and the conclusion is derived from Lemma 1.    $\square$

We next discusses details of the CPM method under different scenarios.

Case 1: $\varvec{u}$ is known and fixed. Therefore, $\varvec{\delta }$ should satisfy (6) and $\delta _{i}$ is determined by $\delta _{i+1}$ for $0\le i<n-1$, i.e.

$$\begin{aligned} \delta _{i}={\left\{ \begin{array}{ll} 0,1 &{} \text {if }\delta _{i+1}=1\\ u_{i+1} &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

Recall that $\delta _{n-1}=0$, thus $\varvec{\delta }$ can be resolved bit by bit from left to right. But it should be noted that $\varvec{\delta }$ needs to be enumerated in the order of hamming weight according to Lemma 1. We adopt a deque (i.e. a data structure supporting push and pop in both front and back directions) for this purpose, and $\varvec{\delta }$ is pushed to the front whenever $\delta _{i-1}=0$ and is pushed to the back otherwise. Details are presented in Algorithm 3.

Given $\varvec{u}$ and $\varvec{\delta }$, the approximation is determined by two of $\varvec{v},\varvec{w}$ and $\varvec{\gamma }$. Obviously, $\varvec{\gamma }$ can be obtained from (5) except $\gamma _{0}$. Thus, the input masks are known once $\varvec{v}$ or $\varvec{w}$ is generated. Without loss of generality, we choose to generate $\varvec{v}$ and then calculate $\varvec{w}$ as $\varvec{w}=\varvec{v}\oplus \varvec{\gamma }$. According to (3),

$$\begin{aligned} v_{i}=\phi _{i}\oplus u_{i}={\left\{ \begin{array}{ll} 0,1 &{} \text {if }\delta _{i}=1\\ u_{i} &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

for $0\le i<n$. Hence, the bits of $\varvec{v}$ where $\varvec{\delta }$ equals one need to be traversed to generate all valid masks. As far as we know, the most efficient method to generate all tuples is the Gray code strategy [7] which flips one bit only in each iteration as shown in Appendix B. Also, this step may be customized for special purpose, e.g. generating the tuples by hamming weight. See Algorithm 4 for details.

Case 2: $\varvec{v}$ or $\varvec{w}$ is known and fixed. Suppose $\varvec{v}$ is known, then $\varvec{\delta }$ should satisfy (7). Thus, $\varvec{\delta }$ can be generated using the procedure $CPM\_Generate\_Delta$ with the parameter $\varvec{v}$ and thereupon $\varvec{u}$ can be determined by (6), i.e.

$$\begin{aligned} u_{i}={\left\{ \begin{array}{ll} 0,1 &{} \text {if }\delta _{i}=1\\ \delta _{i-1} &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

for $1\le i\le n-1$. Since $\phi _{0}\delta _{0}=\delta _{0}=\phi _{0}=v_{0}\oplus u_{0}$ according to (3), $u_{0}=v_{0}$ if $\delta _{0}=0$ and $u_{0}\in \{0,1\}$ otherwise. Finally, $\varvec{\gamma }$ and $\varvec{w}$ are determined by (5) and (4) as in Case 1.

Case 3: $\varvec{u},\varvec{v}$ or $\varvec{u},\varvec{w}$ are known and fixed. Suppose $\varvec{u},\varvec{v}$ are known, so $\varvec{\phi }=\varvec{v}\oplus \varvec{u}$ is known as well. And $\varvec{\delta }$ should satisfy (3), (6) and (7). Notice that the conditions may be incompatible and result in zero correlation. Indeed, since $\delta _{n-1}=0$, $\varvec{\delta }$ exists only if $\phi _{n-1}=0$. By (3) and (6), we have

$$\begin{aligned} \delta _{i}={\left\{ \begin{array}{ll} 0,1 &{} \text {if }\delta _{i+1}=1\text { and }\phi _{i}=0\\ 1 &{} \text {if }\delta _{i+1}=1\text { and }\phi _{i}=1\\ 1 &{} \text {if }\delta _{i+1}=0\text { and }u_{i+1}=1\\ 0 &{} \text {if }\delta _{i+1}=0\text { and }u_{i+1}=\phi _{i}=0\\ \bot &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

for $0\le i<n-1$ where $\bot$ means no solution. Consequently, $\varvec{\delta }$ can be solved using procedure similar to $CPM\_Generate\_Delta$. At last, $\varvec{\gamma }$ is resolved by (5) and $\varvec{w}=\varvec{v}\oplus \varvec{\gamma }$.

Case 4: $\varvec{v},\varvec{w}$ are known. Thus, $\varvec{\gamma }$ is fixed and $\varvec{\delta }$ should satisfy $\varvec{\gamma }\varvec{\delta }=\varvec{\gamma }$, (7) and (8). Similar to Case 3, $\varvec{\delta }$ exists only if $\gamma _{n-1}=0$, and

$$\begin{aligned} \delta _{i}={\left\{ \begin{array}{ll} 0,1 &{} \text {if }\delta _{i+1}=1\text { and }\gamma _{i}=0\\ 1 &{} \text {if }\delta _{i+1}=1\text { and }\gamma _{i}=1\\ 1 &{} \text {if }\delta _{i+1}=0\text { and }v_{i+1}=1\\ 0 &{} \text {if }\delta _{i+1}=0\text { and }v_{i+1}=\gamma _{i}=0\\ \bot &{} \text {otherwise} \end{array}\right. } \end{aligned}$$

for $0\le i<n-1$. Then, $\varvec{u}$ is calculated by (5) except that $u_{0}$ needs to satisfy

$$\begin{aligned} (u_{0}\oplus v_{0})\delta _{0}=u_{0}\oplus v_{0}\\ (u_{0}\oplus v_{0})\delta _{0}=u_{0}\oplus v_{0} \end{aligned}$$

Since $\gamma _{0}=v_{0}\oplus w_{0}=1\Rightarrow \delta _{0}=1$, then $u_{0}\in \{0,1\}$ if $\delta _{0}=1$ and $u_{0}=v_{0}=w_{0}$ otherwise.

Case 5: All Masks are Free. In this case, $\varvec{\delta }$ is generated first according to its hamming weight to ensure the order of approximations. Then, $\varvec{u}$ is obtained as in Case 2 without the constraint on $u_{0}$. At last, the procedure $CPM\_Generate\_$ Mask takes over. Refer to Algorithm 5 for details.

Obviously, the CPM method is not as elegant as the top-down/bottom-up method, but surprisingly it is faster for $n\ge 11$ according to Fig. 5 (note that the labels on y-axis increase exponentially). We believe better direct techniques to instantiate Theorem 1 exists, but $Generate'$ is the most effective implementation we can think of at present and is used to replace Generate in Algorithm 2.

Fig. 5.

The performance of generating $\bigcup _{k=0}^{n-1}S(n,k)$ Platform: 32-bit Win7 with Visual C++ 2015 CTP optimized by /Ox

5 Conclusions

In this paper, we presented a search for linear trails on the SPECK family via Wallén’s enumeration algorithm and Matsui’s branch-and-bound framework. The best correlation of full rounds of SPECK-32 was found as well as reduced rounds of other variants. According to the best 10-round correlation of SPECK-32 which is $2^{-17}$, SPECK-32 is immune to the 1-dimensional linear cryptanalysis. We further proposed the first linear distinguishers and key recovery attacks on the SPECK family which do not threaten the security of SPECK. Finally, a CPM implementation of the Wallén’s algorithm was presented which seems faster than the straightforward instantiations, i.e. the top-down and the bottom-up approaches.

Additional future work items include applying the threshold search [2] on SPECK, mounting vectorial linear cryptanalyses and implementing the search on other ARX ciphers.

Appendices

A Straightforward Implementations of Wallén’s Algorithm

The mode argument indicates whether $\varvec{u},\varvec{v},\varvec{w}$ are fixed and used hereafter.

1.1 A.1 The Top-Down Method

1.2 A.2 The Bottom-Up Method

B The Gray_Visit Procedure