Truncated differential based known-key attacks on round-reduced SIMON

Abstract

At Crypto 2015, Blondeau, Peyrin and Wang proposed a truncated-differential-based known-key attack on full PRESENT, a nibble oriented lightweight block cipher with an SPN structure. The truncated difference they used is derived from the existing multidimensional linear characteristics. An innovative technique of their work is the design of a MITM layer added before the characteristic that covers extra rounds with a complexity lower than that of a generic construction. We notice that there are good linear hulls for bit-oriented block cipher SIMON corresponding to highly qualified truncated differential characteristics. Based on these characteristics, we propose known-key distinguishers on round-reduced SIMON block cipher family, which is bit oriented and has a Feistel structure. Similar to the MITM layer, we design a specific start-from-the-middle method for pre-adding extra rounds with complexities lower than generic bounds. With these techniques, we launch basic known-key attacks on round-reduced SIMON. We also involve some key guessing technique and further extend the basic attacks to more rounds. Our known-key attacks can reach as many as 29/32/38/48/63-rounds of SIMON32/48/64/96/128, which comes quite close to the full number of rounds. To the best of our knowledge, these are the first known-key results on the block cipher SIMON.

1 Introduction

Lightweight cryptographic primitives are designated for the implementation and protection in resource-constrained environments such as RFID tags. The wide use of smart cards and wireless sensor networks has largely stimulated the research on lightweight block ciphers. During the past decade or so, a large number of well designed lightweight block ciphers, such as PRESENT [11], mCrypton [29], LED [23], Prince [12], Piccolo [39], KLEIN [22], TWINE [42], KATAN & KTANTAN [13], HIGHT [24] etc., have been proposed providing reasonable trade-off between the performance and security.

In 2013, NSA proposed a new family of lightweight block ciphers named SIMON [5, 6]. As a Feistel structure based, bit oriented primitive, SIMON eliminated the commonly used S-box substitutions and its round function only consists of bitwise AND, XOR and rotation, leading to an optimized performance in hardware. Ever since its proposal, SIMON has drawn the attention of many researchers and the security evaluation of SIMON has become a hot topic in the community of cryptology. Various cryptanalysis methods have been used to analyze SIMON [1–4, 7, 14, 26, 34, 37, 38, 40, 41, 43, 44]. These results focus on the security of SIMON under the classical secret single-key model. It is noticeable that block ciphers are often adapted to build cryptographic hash functions with methods such as the PGV schemes [8, 33]. From this perspective, SIMON is a natural candidate to build lightweight compression functions and hash functions. Therefore, the resistance of SIMON against known-key attacks is in close relationship with the security of potential SIMON-based hash functions as is proved in [30].

Known-key attacks (also referred as known-key distinguishers) on block ciphers were introduced by Knudsen and Rijmen at Asiacrypt 2007 [25]. Unlike the setting of the conventional single-key model, the adversary in the known-key model knows the randomly drawn key that the cipher operates with. With the knowledge of the key, the adversary is supposed to find a non-random property that an ideal cipher (a randomly drawn permutation) should not have.

In the original [25], the authors used the integral property and successfully distinguished 7-round AES from a random permutation. This property works quite well on AES-like block ciphers so that many refinements and extensions emerged afterwards [20, 31, 36]. Recently at Asiacrypt 2014, Gilbert [21] eventually gives an integral-based known-key attack on full 10-round AES-128. Besides the integral, other non-random properties can be applied as well for constructing known-key attacks. There are known-key attacks using differential characteristics [27, 32], linear hulls [28], collisions [18, 19, 35] and so on.

Very recently at Crypto 2015, Blondeau, Peyrin and Wang [10] proposed a truncated differential based known-key attack on full PRESENT, an SPN-based, nibble oriented block cipher. The truncated differential characteristic they used was first given in [9] and is derived from some multidimensional linear approximations. Their innovative technique is the application of a meet-in-the-middle (MITM) layer. The MITM layer can not only pre-add extra rounds, but also collect conforming plaintexts deterministically. With some gradual matching algorithm, the complexity of this deterministic data collection in the MITM layer is much lower than that of the generic probabilistic method.

Our Contributions In this paper, we give an evaluation to the security of SIMON under the known-key model. More specifically, we show that the procedure as developed for the known-key distinguisher on full PRESENT in [10] can be applied to SIMON, despite its quite different design. To achieve this goal, we develop several specific methods to reach almost the full number of rounds of SIMON.

We derive truncated differential characteristics from some available linear hulls used previously in secret single-key attacks using the methods of [9]. Secondly, although the gradual matching technique cannot work for the bit oriented cipher SIMON, we still manage to find a way to pre-add a MITM layer and deterministically collect data with a lower complexity than the probabilistic generic method.

With the characteristics and the MITM layer, we manage to launch our basic known-key attacks on round-reduced SIMON of all versions. These basic attacks can reach at least as many rounds as the secret single-key recoveries and can distinguish the cipher from a random permutation with significant success probabilities.

The combination of truncated differentials and MITM has already enabled Blondeau et al. to attack full PRESENT, but this is not the case for SIMON. In order to extend the basic attacks to more rounds, we lend the idea of Gilbert in [21]. By involving some subkey guesses in the checking phase, we extend our basic attacks by 5–7 rounds. As is thoroughly discussed in [21], these extended attacks are non-generic and meaningful since they are “efficiently checkable”. Furthermore, thanks to the property of SIMON, the extended attacks share exactly the same success probabilities with their basic counterparts.

We summarize our main results in Table 1. There are 8 attacks numbered as Attack 1–8 using different characteristics and targeting at different SIMON versions. To the best of our knowledge, these are the first known-key results on SIMON. We also implemented Attacks 1–2 that are targeting at SIMON32 and their complexities are practical. The results are in accordance with our deductions, indicating the effectiveness of our attacks.

Table 1 The truncated differential based known-key attacks on round-reduced SIMON

Organization of the paper In Sect. 2, we introduce the theoretic basis and the general procedure of our attacks. It also involves a brief introduction to the SIMON block cipher. Then, we detail our basic truncated-differential based known-key attacks on SIMON in Sect. 3. We discuss the method of extending the basic attacks to more rounds in Sect. 4. The correctness of our attacks are practically verified in Sect. 5. Finally, we conclude the whole paper in Sect. 6.

2 Preliminary

In the first part of this section, we give an introduction to our theoretic basis, a combination of [10, 21]. Then, we describe the general procedure of the truncated-differential-based known-key attacks. In the 3rd part, we briefly introduce SIMON.

2.1 Combining two different known-key attacks

The basic idea of our known-key attacks on SIMON originates from the method on full PRESENT in [10]. Our extended attacks are following the criteria given in [21] where the author extended the basic attack on 8-round AES to the full 10-round version. Like all the attacks under the the known-key model, the adversaries in [10, 21] are given a white box access to an instance of the encryption function associated with a known random key and its inverse. But their purposes are slightly different.

The adversary in [21] aims at simultaneously controlling the inputs and the outputs of the block cipher to achieve a non-random property that cannot be acquired by replacing the block cipher with a random permutation within the same time complexity. As a formalization of the known-key model, [21] gives the concept of “T-Intractable Relation” which we cite as Definition 1.

Definition 1

(T-Intractable Relation [21]) Let $E : (K,X) \in \{0, 1\}^k\times \{0, 1\}^n \rightarrow E_K(X) \in \{0, 1\}^n$ denote a block cipher of block size n bits. Let $N \ge 1$ and ${\mathcal {R}}$ denote an integer and any relation over the set S of N-tuples of n-bit blocks. ${\mathcal {R}}$ is said to be T-intractable relatively to E if, given any algorithm ${\mathcal {A}}'$ that is given an oracle access to a perfect random permutation $\pi$ of $\{0, 1\}^n$ and its inverse, it is impossible for ${\mathcal {A}}'$ to construct in time $T' \le T$ two N-tuples ${\mathcal {X}}' = (X_i')$ and ${\mathcal {Y}}' = (Y_i' )$ such that $Y_i' = \pi (X_i')$, $i = 1\ldots N$ and ${\mathcal {X}}'{\mathcal {R}}{\mathcal {Y}}'$ with a success probability $p' \ge 1/2$ over $\pi$ and the random choices of ${\mathcal {A}}'$. The computing time $T'$ of ${\mathcal {A}}'$ is measured as an equivalent number of computations of E, with the convention that the time needed for one oracle query to $\pi$ or $\pi ^{-1}$ is equal to 1. Thus if $q'$ denotes the number of queries of ${\mathcal {A}}'$ to $\pi$ or $\pi ^{-1}$, $q' \le T'$.

Based on the T-Intractable Relation, [21] also gives a formal criterion for a non-generic and meaningful known-key attack and we cite it as Definition 2.

Definition 2

(Known-Key Distinguisher) Let $E : (K,X) \in \{0, 1\}^k\times \{0, 1\}^n \rightarrow E_K(X) \in \{0, 1\}^n$ denote a block cipher of block size n bits. A known-key distinguisher $({\mathcal {R}},{\mathcal {A}})$ of order $N \ge 1$ consists of (1) a relation ${\mathcal {R}}$ over the N-tuples of n-bit blocks; (2) An algorithm ${\mathcal {A}}$ that on input a k-bit key K produces in time $T_{{\mathcal {A}}}$, i.e. in time equivalent with $T_{{\mathcal {A}}}$ computations of E, an N-tuple ${\mathcal {X}} = (X_i)_{i=1,\ldots , N}$ of plaintext blocks and an N-tuple $Y = (Y_i)_{i=1,\ldots , N}$ of ciphertext blocks related by $Y_i=E_K(X_i)$, for which the following conditions must be met:

• (i) The relation ${\mathcal {R}}$ must be $T_{{\mathcal {A}}}$-intractable relatively to E.

• (ii) The validity of ${\mathcal {R}}$ must be efficiently checkable: this requirement is formalized by incorporating the time for checking whether two N-tuples are related by R in the computing time $T_{{\mathcal {A}}}$ of algorithm ${\mathcal {A}}$.

It is specifically claimed in [21] that the criterion (ii) is avoiding specifying an explicit upper bound on the time complexity for checking whether two N-tuples are related by ${\mathcal {R}}$. It is restricted that, in order to make the known-key attack non-generic, the time complexity for checking ${\mathcal {R}}$ should be no more than the N computations of E. The known-key attack on AES in [21] follows strictly the criteria in Definition 2. The integral-based property is suitable for the start-from-the-middle strategy, so that the adversary can construct the N-tuple input & output blocks with exactly N computations of E. Therefore, the relation chosen in [21] is definitely N-intractable. Besides, [21] stress that no information related to K should not provided when checking the relation ${\mathcal {R}}$, which is also necessary for making their extended attack on 10-round AES meaningful.

The scenario for the known-key attack on full PRESENT in [10] is quite straightforward. In [10], there is an oracle ${\mathcal {O}}$ that can be either a full PRESENT primitive $E_K$ (the master key K is known) or a random permutation $\pi$. The adversary needs to distinguish whether ${\mathcal {O}}=E_K$ or ${\mathcal {O}}=\pi$ with N queries of ${\mathcal {O}}$ at a success probability $P_S>50\,\%$. Although this known-key attack seems different from that of [21], we believe that they are not contradicting. The distinguisher of [10] is based on some truncated differential property. Following the interpretation of [21], the relation ${\mathcal {R}}$ of this attack can be described as:

Relation ${\mathcal {R}}$ in [10]: $(X_i)_{i=1,\ldots ,N}{\mathcal {R}}(Y_i)_{i=1,\ldots ,N}$ iff

• $X_1,\ldots , X_N$ share the same value at bits [52, 55]

• There are more than $\tau$ out of the $\left( {\begin{array}{c}N\\ 2\end{array}}\right)$ ciphertext pairs $(Y_i,Y_j)_{1\le i<j\le N}$ colliding at bits [52, 55]

The $\tau$ parameter is based on the truncated differential characteristics of PRESENT and is affected by the selection of N. This relation ${\mathcal {R}}$ of PRESENT is not suitable for the start-from-the-middle strategy in [21] and there is no characteristic that can cover all 31 rounds of PRESENT. As a result, [10] has to add a 7-round MITM layer before a 24-round truncated differential characteristic to collect the N input blocks needed. The procedure of the known-key attack on full PRESENT can be summarized into three phases as follows:

Preparation::

Collect the conforming N-tuple plaintexts ${\mathcal {X}}=(X_1,\ldots X_N)$

Construction::

Construct the N-tuple ciphertexts ${\mathcal {Y}}=(Y_1,\ldots , Y_N)$ by querying ${\mathcal {O}}$ as $Y_i={\mathcal {O}}(X_i)$ for $i=1,\ldots , N$.

Checking::

Check whether there is ${\mathcal {X}} {\mathcal {R}} {\mathcal {Y}}$. If there is ${\mathcal {X}} {\mathcal {R}} {\mathcal {Y}}$, make the judgment ${\mathcal {O}}=E_K$; otherwise, ${\mathcal {O}}=\pi$.

The probability of ${\mathcal {X}} {\mathcal {R}} {\mathcal {Y}}$ when ${\mathcal {O}}=E_K$ is denoted by $p_0$ and that when ${\mathcal {O}}=\pi$ is denoted by $p_1$. So the success probability of this known-key attack is $P_S=2^{-1}[p_0 +(1-p_1)]$. For full PRESENT, according to [10], there is $P_S=50.5\%$, higher than that of the random guess (50 %) so the attack is meaningful.

It might be doubtful that the preparation phase of this attack also involves the master key K and it requires some computations as well. But we insist that the ${\mathcal {R}}$-relation of [10] can still be regarded as N-intractable since the construction phase is still dominating the overall complexity and the N plaintext & ciphertext pairs are generated at the lowest possible complexity, which is exactly N queries to ${\mathcal {O}}$.

In our basic attacks on SIMON, we strictly follow the procedure in [10]. As to the extended attacks, the preparation and construction phases are typically unchanged while the checking phase will involve some key guesses making the complexity increase. But we can prove that this increment does not violate the criterion (ii) of Definition 2, so our extended attacks are still meaningful.

2.2 The truncated differential based known-key attack

We give a generalized description of the method derived in [10]. Some notations used throughout this paper are as follows:

$E_K$::

The block cipher controlled by the master key K.

n::

The block size of $E_K$.

$\pi$::

A random permutation. $\pi : {\mathbb {F}}_2^n\rightarrow {\mathbb {F}}_2^n$.

X::

A n-bit state is denoted by a capital letter (and similarly, the n-bit intermediate state after r processed encryption rounds of $E_K$).

X [i ]::

The i-th bit of the state X, where $i=0,1,\ldots , n-1$, from the LSB (the leftmost bit of X) to MSB (the rightmost bit of X).

${\mathcal {I}}$::

A sequence of indices ${\mathcal {I}}=(i_s,\ldots , i_1)$ where $0\le i_1<\ldots < i_s\le n-1$. Specifically, we denote the bit sequence $X[{\mathcal {I}}]=(X[i_s],\ldots , X[i_1])$.

$\oplus \,\wedge \,\vee \, \lll$::

Denote bitwise XOR by $\oplus$, AND by $\bigwedge$, OR by $\bigvee$, cyclic left rotation by $\lll$.

We consider that $E_K$ starts from $S_{r_0}$ (plaintext) and ends at $S_{r_2}$ (ciphertext). As set out in (1), the intermediate state $S_{r_1}$ divides $E_{K}$ into two parts: the T D part and the MITM part.

$$\begin{aligned} E_K: S_{r_0}\xrightarrow [E_K^{(0)}]{MITM} S_{r_1} \xrightarrow [E_K^{(1)}]{TD} S_{r_2} \end{aligned}$$

(1)

TD. A truncated differential characteristic is placed in the TD part. For two predefined sequences ${\mathcal {I}}_1$, ${\mathcal {I}}_2$,

$$\begin{aligned} {\mathcal {I}}_1= & {} (i_s,\ldots , i_1),\quad s\ge 1 \end{aligned}$$

(2)

$$\begin{aligned} {\mathcal {I}}_2= & {} (j_q,\ldots , j_1), \quad q\ge 1, \end{aligned}$$

(3)

the corresponding truncated differential characteristic can be described as Property 1.

Property 1

For two n-bit intermediate states $(S_{r_1},S_{r_1}')$ satisfying

$$\begin{aligned} S_{r_1}[{\mathcal {I}}_1]=S_{r_1}'[{\mathcal {I}}_1], \end{aligned}$$

(4)

the corresponding $(S_{r_2},S_{r_2}')$ after $r_2-r_1$ rounds of encryptions conform $S_{r_2}[{\mathcal {I}}_2]=S_{r_2}'[{\mathcal {I}}_2]$ with probability

$$\begin{aligned} P_{TD}=Pr\left\{ S_{r_2}[{\mathcal {I}}_2]=S_{r_2}'[{\mathcal {I}}_2] \right\} =2^{-q}\cdot (1+C), \quad C>0 \end{aligned}$$

(5)

where C is a parameter decided by the block cipher and the truncated differential characteristic itself.

If $(S_{r_2},S_{r_2}')$ are generated by a random permutation $\pi$, the probability $S_{r_2}[{\mathcal {I}}_2]=S_{r_2}'[{\mathcal {I}}_2]$ is apparently $2^{-q}<P_{TD}$. Therefore, if we can find sufficiently many pairs $(S_{r_1},S_{r_1}')$ conforming (4), we can utilize Property 1 to distinguish $E_K$ from a random permutation.

MITM. For a predefined ${\mathcal {I}}_0$ s.t. $|{\mathcal {I}}_0|=|{\mathcal {I}}_1|=s$, the MITM part aims at finding N plaintexts $S_{r_0}^{(1)},\ldots , S_{r_0}^{(N)}$ satisfying

$$\begin{aligned} \left\{ \begin{array}{rcl} S_{r_0}^{(i)}[{\mathcal {I}}_0] &{}=&{}Cst_0 \\ S_{r_1}^{(i)}[{\mathcal {I}}_1] &{}=&{}Cst_1 \end{array} \right. \quad i\in [1,N], \end{aligned}$$

(6)

where $Cst_0$ and $Cst_1$ are constant values of ${\mathbb {F}}_2^s$. In this way, $\left( {\begin{array}{c}N\\ 2\end{array}}\right) \approx N^2/2$ pairs conforming (4) are acquired. The trivial way to construct the structure (6) requires $2^s N$ trials of $S_{r_0}\rightarrow S_{r_1}$. This method is probabilistic rather than deterministic. Furthermore, the generic $2^s N$ computations of $S_{r_0}\rightarrow S_{r_1}$ are likely to exceed the N queries to ${\mathcal {O}}$, making our attacks unavailable. Therefore, the authors of [10] used the match in the middle strategy as shown in (7).

(7)

They start from the $S_{r_0}[{\mathcal {I}}_0]$ and $S_{r_1}[{\mathcal {I}}_1]$, and match at the Sub-Nibble layer in the middle. For the SPN structure based, nibble-oriented PRESENT, the Sub-Nibble layer is only 16 parallelised 4-bit Sboxes. The intermediate state $S_{r_m}$ ($r_0<r_m<r_1$) can be deduced nibble by nibble using the gradual matching technique [10]. After $S_{r_m}^{(1)},\ldots , S_{r_m}^{(N)}$ are acquired, the corresponding plaintexts $S_{r_0}^{(1)},\ldots , S_{r_0}^{(N)}$ can be deduced through partial decryptions. This method is deterministic. The complexity of the partial decryption is only about 0.5N, and the computations of $S_{r_0}\rightarrow S_{r_1}$ and the complexity of the gradual matching are even lower. So the overall complexity of this deterministic method is lower than the generic $2^s N$.

With the predefined ${\mathcal {I}}_0$, ${\mathcal {I}}_1$, ${\mathcal {I}}_2$, the relation of the known-key attack can be defined as

Relation ${{\mathcal {R}}}$: $(S_{r_0}^{(i)})_{i=1,\ldots ,N}{\mathcal {R}}(S_{r_2}^{(i)})_{i=1,\ldots ,N}$ iff

• $S_{r_0}^{(1)},\ldots , S_{r_0}^{(N)}$ share the same value $Cst_0$ at bits ${\mathcal {I}}_0$

• There are more than $\tau$ out of the $\left( {\begin{array}{c}N\\ 2\end{array}}\right)$ ciphertext pairs $(S^{(i)}_{r_2}, S^{(j)}_{r_2})_{1\le i<j\le N}$ colliding at bits ${\mathcal {I}}_2$

Following the description in Sect. 2.1, the 3 phases of the truncated-differential-based known-key attacks can be summarized as follows:

Preparation: Collect the N specific plaintexts:

• 1. Deduce the plaintexts $S_{r_0}^{(1)}, \ldots , S_{r_0}^{(N)}$ conforming (6).

Construction: Acquire the ciphertexts from the oracle:

• 2. Query the oracle for the ciphertexts $S_{r_2}^{(i)}={\mathcal {O}}(S_{r_0}^{(i)})$ for $i=1,\ldots , N$.

Checking: Check whether the plaintext & ciphertext pairs conform ${\mathcal {R}}$:

• 3. Count for $\psi$, the number of ciphertext pairs colliding on $S_{r_2}[{\mathcal {I}}_2]$:

  $$\begin{aligned} \psi :=\#\left\{ (S^{(i)}_{r_2}, S^{(j)}_{r_2}): S^{(i)}_{r_2}[{\mathcal {I}}_2]=S^{(j)}_{r_2}[{\mathcal {I}}_2], 1\le i<j\le N \right\} \end{aligned}$$

• 4. If $\psi >\tau$, we conclude ${\mathcal {O}}=E_K$; otherwise, ${\mathcal {O}}=\pi$.

Let $N_S=\left( {\begin{array}{c}N\\ 2\end{array}}\right) \approx N^2/2$ be the total number of ciphertext pairs. Apparently we have $\psi \le N_S$. We define the two probabilities $Pr_0$ and $Pr_1$ as

$$\begin{aligned}&Pr_0 := Pr\{\psi >\tau | {\mathcal {O}}=E_K\} \end{aligned}$$

(8)

$$\begin{aligned}&Pr_1 := Pr\{\psi \le \tau | {\mathcal {O}}=\pi \} . \end{aligned}$$

(9)

Since ${\mathcal {O}}$ can be either $E_K$ or $\pi$ with equal chances, the success probability of this known-key attack can be determined as

$$\begin{aligned} P_S=\frac{Pr_0+Pr_1}{2}. \end{aligned}$$

(10)

The known-key attack can only be regarded as “effective” when $P_S>0.5$. This requires a proper assignment of the $\tau$ value.

Equation (10) is a precise evaluation to the success probability $P_S$. But the parameters $Pr_0$ and $Pr_1$ defined in (8) and (9) are hard to acquire other than running the experiments for many times, which is impractical. Therefore, based on some rational assumptions, [9, 10] give a method to determine both $\tau$ and $P_S$ simultaneously with N, C, q. They assume that: for ${\mathcal {O}}=E_K$, the variable $\psi$ follows the normal distribution $Norm(\mu _R,\sigma _R^2)$; for ${\mathcal {O}}=\pi$, $\psi \sim Norm(\mu _W,\sigma _W^2)$ where

$$\begin{aligned} \left\{ \begin{array}{rcl} \mu _R&{}=&{}N_S\cdot 2^{-q}\cdot (1+C)\\ \mu _W&{}=&{}N_S\cdot 2^{-q} \end{array} \right. \quad \left\{ \begin{array}{rcl} \sigma ^2_R&{}=&{}N_S\cdot 2^{-q}\cdot (1+C)\cdot \left[ 1-2^{-q}(1+C)\right] \\ \sigma ^2_W&{}=&{}N_S\cdot 2^{-q}\cdot \left( 1-2^{-q} \right) \end{array} \right. \end{aligned}$$

(11)

According to [10], the success probability of this attack ($P_S$) is

$$\begin{aligned} P_S= {\varPhi }\left( \frac{\mu _R-\mu _W}{\sigma _R+\sigma _W}\right) \approx {\varPhi }\left( \frac{\sqrt{2^{-q}\cdot N_S}\cdot C}{2}\right) . \end{aligned}$$

(12)

and the $\tau$ parameter in Step 4 can be decided accordingly as:

$$\begin{aligned} \tau =\mu _R-\sigma _R\cdot {\varPhi }^{-1}(P_S)=\mu _W+ \sigma _W\cdot {\varPhi }^{-1}(P_S). \end{aligned}$$

(13)

The computations in the checking phase are negligible, so the overall complexity is dominated by the N queries to the oracle in the construction phase.

Although the computation of $P_S$ in (12) is only an approximation compared with (10), (12) is more suitable for theoretical deductions. Therefore, we use (12) to deduce the theoretic success probabilities in Table 1, as well as the $\tau$ value in (13). And, in Sect. 5, we use (10) to get the exact success probability with the experimentally acquired $Pr_0$ and $Pr_1$.

2.3 Brief introduction to SIMON

SIMON is a family of lightweight block ciphers with a Feistel structure. According to the block size n, we denote the 5 SIMON versions as $\mathrm{SIMON}n$ where $n=32/48/64/96/128$. The intermediate state $S_r$ consists of two $\frac{n}{2}$-bit words $x_{r+1}, x_r\in {\mathbb {F}}_2^{\frac{n}{2}}$ as $S_r=(x_{r+1}, x_r)$. Therefore we have $x_r=S_r[\frac{n}{2}-1,\ldots , 0]$ and $x_{r+1}=S_r[n-1,\ldots , \frac{n}{2}]$. The r-th ($r=0,1,\ldots$) round function of $\mathrm{SIMON}n$ is

$$\begin{aligned} S_r=(x_{r+1}, x_r) \xrightarrow []{r\hbox {-th Round}} S_{r+1}=(x_{r+2},x_{r+1})=(F(x_{r+1})\oplus x_r\oplus k_r, x_{r+1}) \end{aligned}$$

(14)

where $F:{\mathbb {F}}_{2}^{\frac{n}{2}}\rightarrow {\mathbb {F}}_{2}^{\frac{n}{2}}$,

$$\begin{aligned} F(x)=((x\lll 8)\wedge (x\lll 1)) \oplus (x\lll 2). \end{aligned}$$

(15)

The $k_r$ in (14) is the round key generated with the key schedule. The key schedule as well as other details of SIMON is not used in this paper and we refer interested readers to [5].

3 Basic known-key attacks on SIMON

The basic known-key attacks on SIMON follow the procedure summarized in Sect. 2.2. We first deduce the truncated differential for the TD part based on the existing linear approximations. Then, we introduce our deterministic method for constructing conforming plaintexts within the MITM part. In the third part, we describe the detailed procedure of our known-key attacks on different SIMON versions.

3.1 The truncated differential characteristics in the TD part

A large number of highly qualified linear characteristics for SIMON have been found in recent works. Based on these linear approximations, many (secret) single-key attacks are proposed.

We define the operation $\odot : {\mathbb {F}}_2^n\times {\mathbb {F}}_2^n\rightarrow {\mathbb {F}}_2$ as

$$\begin{aligned} X\odot Y:=\bigoplus _{i=0}^{n-1}\left( X[i]\wedge Y[i]\right) \end{aligned}$$

A n-bit word X can also be determined with the set ${\mathcal {B}}(X)$ containing all the indices of the active bits of X:

$$\begin{aligned} {\mathcal {B}}(X):=\left\{ i\in [0,n-1]: X[i]=1\right\} . \end{aligned}$$

and we have

$$\begin{aligned} X\odot Y=\bigoplus _{i\in {\mathcal {B}}(X)}Y[i] \end{aligned}$$

For a linear hull $({\varGamma }_1,{\varGamma }_2)$ of $F:{\mathbb {F}}_2^n\rightarrow {\mathbb {F}}_2^n$, its correlation, denoted by $\mathbf {cor}({\varGamma }_1,{\varGamma }_2)$, is defined as

$$\begin{aligned} \mathbf {cor}({\varGamma }_1,{\varGamma }_2):= & {} Pr\left[ ({\varGamma }_1\odot X)\oplus ({\varGamma }_2\odot F(X))=0 \right] \nonumber \\&-\,Pr\left[ ({\varGamma }_1\odot X)\oplus ({\varGamma }_2\odot F(X))=1 \right] \end{aligned}$$

If we have s linearly independent ${\varGamma }_1$’s, denoted by ${\varGamma }_1^{1},\ldots , {\varGamma }_1^{s}$, and q linearly independent ${\varGamma }_2$’s, denoted by ${\varGamma }_2^{1},\ldots , {\varGamma }_2^{q}$, any of the $2^{s+q}$ linear combinations $({\varGamma }_1^{(\nu _1,\ldots ,\nu _s)}, {\varGamma }_2^{(\omega _1,\ldots ,\omega _q)} )$ defined as

$$\begin{aligned} {\varGamma }_1^{(\nu _1,\ldots ,\nu _s)}= & {} \nu _1 {\varGamma }_1^{1}\oplus \ldots \oplus \nu _s {\varGamma }_1^{s}, \\ {\varGamma }_2^{(\omega _1,\ldots ,\omega _q)}= & {} \omega _1 {\varGamma }_2^{1}\oplus \ldots \oplus \omega _q {\varGamma }_2^{q} \end{aligned}$$

where $\nu _i,\omega _j\in \{0,1\}, i\in [1,s],j\in [1,q]$, can still be regarded as a linear approximation. Combining the $2^{s+q}$ linear approximations makes a multidimensional linear approximation which can be transformed to a truncated differential characteristic according to Theorem 1.

Theorem 1

[9] Let ${\mathbb {F}}_2^n={\mathbb {F}}_2^s\times {\mathbb {F}}_2^t={\mathbb {F}}_2^q\times {\mathbb {F}}_2^r$ and

$$\begin{aligned} F: {\mathbb {F}}_2^n\rightarrow {\mathbb {F}}_2^n, x=(x_s, x_t)\rightarrow (y_q,y_r) \end{aligned}$$

Given a multidimensional approximation $\left[ (a_s,0), (b_q,0)\right] _{{a_s\in {\mathbb {F}}_2^s},b_q\in {\mathbb {F}}^q_2}$ with capacity

$$\begin{aligned} C=\sum _{(a_s,b_q)\ne (0,0)}\mathbf {cor}^2\left[ (a_s\odot x_s) \oplus (b_q\odot y_q)\right] , \end{aligned}$$

and a truncated differential composed of $2^t$ input differences $(0,\sigma _t)\in \{0\}\times {\mathbb {F}}_2^t$, and $2^r$ output differences $(0,\gamma _r)\in \{0\}\times {\mathbb {F}}_2^r$ with probability

$$\begin{aligned} P_{TD}=\frac{1}{2^q}\sum _{(\sigma _t, \gamma _r )\in {\mathbb {F}}_2^t\times {\mathbb {F}}_2^r} {\mathbf {P}}\left[ (0,\sigma _t)\rightarrow (0,\gamma _r)\right] \end{aligned}$$

where ${\mathbf {P}}\left[ (0,\sigma _t)\rightarrow (0,\gamma _r)\right] =2^{-n} \# \left\{ x\in {\mathbb {F}}_2^n: F(x)\oplus F(x\oplus (0,\sigma _t))=(0,\gamma _r)\right\}$. We have

$$\begin{aligned} P_{TD}=2^{-q}(C+1). \end{aligned}$$

As to traditional linear hulls for SIMON, we have $s=q=1$ and Theorem 1 is still applicable as has been proved in [9]. Suppose that a linear hull $({\varGamma }_1, {\varGamma }_2)$ is placed at the TD part of $E_K$ in (1). Its correlation is $\mathbf {cor}({\varGamma }_1, {\varGamma }_2)$ defined as

$$\begin{aligned} \mathbf {cor}({\varGamma }_1, {\varGamma }_2)= & {} Pr\left[ ({\varGamma }_1\odot S_{r_1})\oplus ({\varGamma }_2\odot S_{r_2})=0 \right] \\&-Pr\left[ ({\varGamma }_1\odot S_{r_1})\oplus ({\varGamma }_2\odot S_{r_2})=1 \right] \end{aligned}$$

and its capacity can also be acquired as $C=2^{-1}\cdot \mathbf {cor}^2({\varGamma }_1, {\varGamma }_2)$. Then, according to Theorem 1, we can derive a truncated differential characteristic having Property 2.

Property 2

For a pair $(S_{r_1}, S_{r_1}')$ satisfying ${\varGamma }_1\odot S_{r_1}={\varGamma }_1 \odot S_{r_1}'$, their corresponding $(S_{r_2}, S_{r_2})$ will have the property

$$\begin{aligned} Pr\left[ {\varGamma }_2\odot S_{r_2}={\varGamma }_2 \odot S_{r_2}'\right] =P_{TD}=2^{-1}(1+C). \end{aligned}$$

In this way, all existing linear hulls of SIMON can be transformed to truncated differential characteristics that can be used for our known-key attacks.

3.2 The data collections in the MITM part

The MITM part of SIMON also aims at constructing plaintexts $S_{r_0}^{(1)},\ldots , S_{r_0}^{(N)}$ and their corresponding $S_{r_1}^{(1)},\ldots , S_{r_1}^{(N)}$ satisfying

$$\begin{aligned} \left\{ \begin{array}{ll} S_{r_0}^{(i)}[\lambda ]=0\\ {\varGamma }_1 \odot S_{r_1}^{(i)}=0 \end{array} \right. \quad i\in [1,N] \end{aligned}$$

(16)

where $\lambda \in [0,n-1]$ is a predefined index. Apparently, the probabilistic method for acquiring these plaintexts requires 2N queries of $S_{r_0}\rightarrow S_{r_1}$ and we are going to propose a deterministic method for data collections with lower complexity than the generic bound.

Unfortunately, there is no gradual matching for bit-oriented SIMON. Instead of matching in the middle, we use the start from the middle strategy as shown in (17),

$$\begin{aligned} S_{r_0}[\lambda ]\xleftarrow []{Decrypt} S_{r_m}\xrightarrow []{Encrypt} {\varGamma }_1\odot S_{r_1}. \end{aligned}$$

(17)

Our method is based on Observation 1

Observation 1

Let ${\mathbf {v}}=(v_0,\ldots , v_n)$ where $v_0,\ldots , v_n$ are boolean variables. Supposing that we have a boolean function F s.t.: for some $i\in [0,n]$, the algebraic normal form (ANF) of F can be regarded as:

$$\begin{aligned} F({\mathbf {v}})=v_i+G \end{aligned}$$

(18)

where $G\in {\mathbb {F}}_2[v_0,\ldots ,v_{i-1},v_{i+1},\ldots ,v_n]$ is irrelevant to the variable $v_i$. Then, we can nullify F by modifying ${\mathbf {v}}$ to ${\mathbf {v}}'$ defined as

$$\begin{aligned} {\mathbf {v}}'[j]=\left\{ \begin{array}{ll} {\mathbf {v}}[j],&{}j\ne i\\ G,&{}j=i \end{array} \right. \end{aligned}$$

(19)

With this modification, we have $F({\mathbf {v}}')=0$. In this case, we refer $v_i$ as a “linear variable” of F.

Linear variables do widely occur in primitives with low-degree updating functions. Dinur and Shamir have already used linear variables to nullify the crucial bits and successfully launched dynamic cube key recovery attacks on the stream cipher Grain-128 [15, 17].

Apparently, both of the two bits $S_{r_0}[\lambda ]$ and ${\varGamma }_1 \odot S_{r_1}$ in (17) are boolean functions of the intermediate state $S_{r_m}$. The knowledge of the whole ANF in (18) is essential for the key recoveries in [15, 17]. Even with very few rounds of iterations, the ANFs of SIMON’s intermediate bits will become extremely complicated which barricades us from further extensions. But in fact, the explicit expressions of the ANFs are unnecessary for our known-key attacks. We only need to know two indices u and v such that: $S_{r_m}[u]$ is a linear variable of ${\varGamma }_2\odot S_{r_1}$ and $S_{r_m}[v]$ is a linear variable of $S_{r_0}[\lambda ]$. Therefore, instead of deducing ANFs, we identify available pairs (u, v) in a probabilistic manner:

• 1. We define a sufficiently large integer T as the test strength (for example $T=2^{13}$).

• 2. For all of the (u, v) pairs, which is $n\cdot (n-1)$ in total, we do the following substeps:

  • (a) We run Algorithm 1 with inputs $\left( (u,v),T\right)$

  • (b) If Algorithm 1 returns 1, (u, v) is available with a probability $1-2^{-T}$; otherwise, (u, v) is unavailable with probability 1.

As can be seen from (15), the updating function of SIMON is only of degree 2 and its linear diffusion is also weak, enabling us to find linear variables after several rounds. Therefore, our MITM part for SIMON can pre-add at least 9 rounds to the truncated differential characteristics.

The plaintexts we need should conform (16) which is a 2-bit filter, so there are only $2^{n-2}$ available. With (u, v) settled (supposing that $0\le u<v\le n-1$), we claim that, for all $N\le 2^{n-2}$, we can deterministically collect N available plaintexts with $MITM(\lambda , {\varGamma }_1, u,v)$ described as in Algorithm 2.

The complexity of this data collection is no more than 1.5N computations of $S_{r_0}\rightarrow S_{r_1}$, lower than the generic bound 2N. Furthermore, since the ratio $(r_1-r_0)/(r_2-r_0)$ of our attacks is much smaller than $(1.5)^{-1}=\frac{2}{3}$, this 1.5N computations of $S_{r_0}\rightarrow S_{r_1}$ is significantly lower than that of the N queries of ${\mathcal {O}}$ in the construction phase. Step 2 of Algorithm 2 makes sure that the plaintexts are distinct for all $N\le 2^{n-2}$ and the procedure is deterministic.

3.3 The basic known-key attacks on SIMON

The truncated differential characteristics we used are derived from the existing linear hulls which have been verified by previous secret single-key attacks such as [2, 14]. According to Sect. 2.2, a truncated differential characteristic can be determined by the parameters: ${\varGamma }_1$, ${\varGamma }_2$, C and $r_2-r_1$. According to Sect. 3.2, the MITM part can be determined by the parameters: $\lambda$, u, v, $r_1-r_m$, $r_m-r_0$. The relation ${\mathcal {R}}$ of the basic attacks are defined as

Relation ${\mathcal {R}}$: $(S_{r_0}^{(i)})_{i=1,\ldots ,N}{\mathcal {R}}(S_{r_2}^{(i)})_{i=1,\ldots ,N}$ iff

• $S_{r_0}^{(1)},\ldots , S_{r_0}^{(N)}$ share the same value 0 at bit $\lambda$;

• There are more than $\tau$ out of the $\left( {\begin{array}{c}N\\ 2\end{array}}\right)$ ciphertext pairs $(S^{(i)}_{r_2}, S^{(j)}_{r_2})_{1\le i<j\le N}$ satisfying ${\varGamma }_2 \odot S^{(i)}_{r_2}={\varGamma }_2 \odot S^{(j)}_{r_2}$.

The attack procedure on $\mathrm{SIMON}n$ is as follows:

• 1. Collect N ($N\le 2^{n-2}$) plaintexts $S_{r_0}^{(1)},\ldots , S_{r_0}^{(N)}=MITM(\lambda , {\varGamma }_1, u,v)$ using Algorithm 2. (Preparation)

• 2. Query the oracle ${\mathcal {O}}$ for the ciphertexts $S_{r_2}^{(i)}={\mathcal {O}}(S_{r_0}^{(i)})$ for $i=1,\ldots , N$. (Construction)

• 3. Assign a counter $m=0$. (Checking)

• 4. For $i=1,\ldots , N$, if ${\varGamma }_2\odot S_{r_2}^{(i)}=0$, update $m\leftarrow m+1$. (Checking)

• 5. Assign $\psi \leftarrow \left( {\begin{array}{c}m\\ 2\end{array}}\right) +\left( {\begin{array}{c}N-m\\ 2\end{array}}\right)$. (Checking)

• 6. If $\psi >\tau$, make the judgment ${\mathcal {O}}=E_K$; otherwise, ${\mathcal {O}}=\pi$. (Checking)

The complexity of the construction phase is dominated by the N queries to the oracle ${\mathcal {O}}$ in Step 2, which is also the overall complexity of the whole known-key attack. The checking phase only involves the XOR operations of computing ${\varGamma }_2\odot S_{r_2}^{(i)}=0$ for $i=1,\ldots , N$ whose complexity is much lower than that of the construction phase.

The success probability $P_S$ and the $\tau$ parameter can be approximated with the method in Sect. 2.2.

Detailed parameters of our basic attacks are shown in Table 2. The attacks can mount to $r_2-r_0$ rounds, which is equal to the summation of the numbers in the 3rd, 4th and 11th column.

Table 2 Basic truncated differential based known-key attacks on $\mathrm{SIMON}n$ where n is the block size

4 Further extension of the basic attacks

In [21], Gilbert extends the basic 8-round attack on AES to 10 rounds by involving some subkey guesses in the checking phase. He proved that: as long as the complexity of the checking phase is significantly lower than that of the construction phase, the known-key distinguishers can still be meaningful. This criterion is formally stated in (ii) of Definition 2. [21] also stress the necessity of key guesses considering that no information related to the key should be provided in the checking phase.

We can also apply the method in [21] to extend the basic distinguishers forward and backward. After the extension, the block cipher $E_K$ in (1) is now transformed to (20)

$$\begin{aligned} E_K: S_{r_b}\xrightarrow [E_K^{(b)}]{BExt} S_{r_0}\xrightarrow [E_K^{(0)}]{MITM} S_{r_1} \xrightarrow [E_K^{(1)}]{TD} S_{r_2}\xrightarrow [E_K^{(f)}]{FExt}S_{r_f} \end{aligned}$$

(20)

where BExt is short for “Backward Extension” and FExt for “Forward Extension”.

In the extended attacks, we are still using the collision properties of the two bits $S_{r_0}[\lambda ]$ and ${\varGamma }_2\odot S_{r_2}$. To acquire these two bits, some subkey bits, $k_b$ and $k_f$, are to be guessed in the checking phase so that we can acquire $S_{r_0}[\lambda ]$ and ${\varGamma }_2\odot S_{r_2}$ through partial encryptions & decryptions denoted as

$$\begin{aligned} S_{r_0}[\lambda ]=P(k_b,S_{r_b}),\quad {\varGamma }_2\odot S_{r_2}=Q(k_f,S_{r_f}). \end{aligned}$$

(21)

The selection of $k_b$ makes sure that there is only one $\alpha \in \{0,1\}^{|k_b|}$ conforming $P(\alpha ,S_{r_b}^{(i)})=0$ for all $i=1,\ldots , N$. The correct assignment of $k_f$ should enable us to acquire the desired $\psi$ parameter at the lowest cost. The determinations of $k_b$ and $k_f$ are to be detailed in Sect. 4.2. The computation of P requires no more than $\frac{r_0-r_b}{r_f-r_b}$ computations while Q requires $\frac{r_f-r_2}{r_f-r_b}$. Therefore, the relation ${\mathcal {R}}$ of this attack is now transformed as

Relation ${\mathcal {R}}$: $(S_{r_b}^{(i)})_{i=1,\ldots ,N}{\mathcal {R}}(S_{r_f}^{(i)})_{i=1,\ldots ,N}$ iff there are bit strings $\alpha \in {\mathbb {F}}_2^{|k_b|}$ and $\beta \in {\mathbb {F}}_2^{|k_f|}$ conforming to:

• $P(\alpha , S_{r_b}^{(i)})=0$ for all $i=1,\ldots , N$;

• There are more than $\tau$ out of the $\left( {\begin{array}{c}N\\ 2\end{array}}\right)$ ciphertext pairs $(S^{(i)}_{r_f}, S^{(j)}_{r_f})_{1\le i<j\le N}$ satisfying $Q(\beta , S^{(i)}_{r_f})=Q(\beta , S^{(j)}_{r_f})$.

The procedure of this extended attack will be changed accordingly as follows:

• 1. Collect the N ($N\le 2^{n-2}$) intermediate states satisfying (16) and compute backward for their plaintexts $S_{r_b}^{(1)},\ldots , S_{r_b}^{(N)}$. (Preparation)

• 2. Query the oracle ${\mathcal {O}}$ for the ciphertexts $S_{r_f}^{(i)}={\mathcal {O}}(S_{r_b}^{(i)})$ for $i=1,\ldots , N$. (Construction)

• 3. Set a table ${\mathcal {T}}$ consisting of $2^{ |k_f|}$ counters and initiate them to 0 (${\mathcal {T}}[s]\leftarrow 0$ for all $s=0,\ldots , 2^{|k_b|+|k_f|}-1$). (Checking)

• 4. Initialize a flag ${\mathfrak {f}} \leftarrow 0$.

• 5. For the $\alpha =0,\ldots , 2^{|k_b|}-1$, we do the following substeps: (Checking)

  • (a) For all $i=1,\ldots , {N}$, if for any $P(\alpha , S_{r_b}^{(i)})\ne 0$, then continue.

  • (b) Assign ${\mathfrak {f}}\leftarrow 1$ and break;

• 6. For $\beta =0,\ldots , 2^{|k_f|}-1$, we do the following substeps: (Checking)

  • (a) Initialize a $m\leftarrow 0$.

  • (b) For all $i=1,\ldots , {N}$, if $Q(\beta ,S_{r_f}^{(i)})=0$, update $m\leftarrow m+1$.

  • (c) Update ${\mathcal {T}}[\beta ]\leftarrow \left( {\begin{array}{c}m\\ 2\end{array}}\right) +\left( {\begin{array}{c}N-m\\ 2\end{array}}\right)$.

• 7. Assign $\psi \leftarrow \max {\mathcal {T}}$. (Checking)

• 8. If $\psi >\tau$ and ${\mathfrak {f}}=1$, make the judgment ${\mathcal {O}}=E_K$; otherwise, ${\mathcal {O}}=\pi$. (Checking)

4.1 The complexity analysis of the extended attacks

The preparation and construction phases of the extended attack resemble that of the basic attack and the overall complexity is still dominated by the N times of ${\mathcal {O}}$ queries in the construction phase.

The complexity of the checking phase, denoted as $\theta$, is somewhat complicated. With the subkey bits $k_b$ and $k_f$ involved, the complexity of the checking phase has largely increased. The more extension $r_0-r_b$ ($r_f-r_2$) gets, the bigger the key length $|k_b|$ ($|k_f|$) will be and the complexity $\theta$ will grow accordingly. According to (ii) in Definition 2, the extended distinguishers can still be meaningful as long as the relation ${\mathcal {R}}$ is “efficiently checkable”. This criterion restricts that the complexity of the checking phase should be lower than that of the construction phase. In other words, we should make sure $\theta <N$.

The checking phase complexity $\theta$ can be estimated step by step. For the inappropriate assignment of $\alpha \in \{0,1\}^{|k_b|}$, Step 5.(a) will run averaging

$$\begin{aligned} 2^{-N}N+\sum _{i=1}^N (i2^i) \approx \frac{1}{1-2^{-1}}= 2 \end{aligned}$$

computations P before continuing to $\alpha +1$. Such an assignment of $\alpha$ can reach Step 5.(b) with a negligible probability $2^{-N}$. So the complexity of Step 2 is bounded by

$$\begin{aligned} \left[ 2\cdot (2^{|k_b|}-1)+N\right] \cdot \frac{r_0-r_b}{r_f-r_b}. \end{aligned}$$

Step 6 requires $2^{|k_f|}\cdot N$ computations of $S_{r_f}\rightarrow S_{r_2}$. So the overall complexity of the attack can be approximated as

$$\begin{aligned} \theta= & {} (2^{|k_b|+1}-2+ N)\cdot \frac{r_0-r_b}{r_f-r_b}+ 2^{|k_f|}\cdot N \cdot \frac{r_f-r_2}{r_f-r_b}\nonumber \\\approx & {} N\cdot \frac{2^{|k_f|}\cdot (r_f-r_2)+(r_0-r_b)}{r_f-r_b}+2^{|k_b|+1}\cdot \frac{r_0-r_b}{r_f-r_b} \end{aligned}$$

(22)

The memory complexity of the extended attacks is bounded by the size of ${\mathcal {T}}$ which is $2^{|k_f|}$.

In order to keep $\theta <N$, we restrict $k_b$ and $k_f$ to conform (23).

$$\begin{aligned} \left\{ \begin{array}{l} |k_b|<\log N\\ |k_f|<\log \frac{r_f-r_b}{r_f-r_2+r_0-r_b} \end{array} \right. \end{aligned}$$

(23)

4.2 Determine $k_b$ and $k_f$

For any extension $r_b$ and $r_f$, we need to determine the corresponding key bits $k_b$ and $k_f$ required for the computation of the targeted $S_{r_0}[\lambda ]$ and ${\varGamma }_2\odot S_{r_2}$ respectively. This involves analyzing the ANFs of the targeted bits and is similar to the method used by Dinur et al. in [15] to determine the key guesses for full Grain-128.

For the backward extension, we need to compute the targeted state bit $S_{r_0}[\lambda ]$ precisely and $k_b$ should be the subkey bits sufficient and necessary for the computation. The sufficiency requires that the knowledge of $k_b$ is well enough to acquire $S_{r_0}[\lambda ]$. The necessity restricts that: for any wrong guess of $k_b$, denoted as $\alpha$, it should be impossible for the N plaintexts to conform $P(\alpha , S_{r_b}^{(i)})=0$ for $i=1,\ldots , N$. The computation of the whole state $S_{r_0}$ involves the $\frac{n}{2}$-bit round keys, denoted as $K_{r_b},\ldots , K_{r_0-1}$ and obviously $k_b$ is only a part of them. We identify the $k_b$ by analyzing the ANF of $S_{r_0}[\lambda ]$ as follows.

For $i\in [r_b,r_0-1]$, we assign its j-th bit ($j\in [0,\frac{n}{2}-1]$) with a symbolic boolean variable $x_{\frac{n}{2}\cdot i+j}$ such that $K_i[j]=x_{\frac{n}{2}\cdot i+j}$. The n plaintext bits of $S_{r_0}$ are assigned to n boolean variables $v_0,\ldots , v_{n-1}$ such that $S_{r_b}[i]=v_i$ for $i=0,\ldots , n-1$. With this $S_{r_b}$ and round keys $K_{r_b},\ldots , K_{r_0-1}$, we run the encryption procedure of the first $r_0-r_b$ rounds and acquire the ANF of $S_{r_0}[\lambda ]$ which, following the notations in [16], can be represented as

$$\begin{aligned} S_{r_0}[\lambda ]= & {} P(k_b,S_{r_b})=f({\mathbf {x}},{\mathbf {v}})\nonumber \\= & {} \sum _{u=(u_0,\ldots , u_{n-1})\in {\mathbb {F}}_2^{n}}a_u M_u \end{aligned}$$

(24)

where ${\mathbf {v}}=(v_0,\ldots ,v_{n-1})$, ${\mathbf {x}}=(x_0,\ldots , x_{L})$ ($L=\frac{n}{2}\cdot (r_0-r_b)-1$), $M_u=\prod _{i=0}^{n-1} v_i^{u_i}$, $a_u=a_u({\mathbf {x}})\in {\mathbb {F}}_2[x_0,\ldots , x_L]$ and the function P is defined as (21). We also define $P^*(k_b,S_{r_b})=f^{*}({\mathbf {x}},{\mathbf {v}})$ as

$$\begin{aligned} {\hat{S}}_{r_0}[\lambda ]=P^*(k_b,S_{r_b})=f^{*}({\mathbf {x}},{\mathbf {v}})=f({\mathbf {x}},{\mathbf {v}})+a_0=\sum _{u\in {\mathbb {F}}_2^{n}\backslash \{0\}}a_u M_u. \end{aligned}$$

By analyzing the ANF of $f({\mathbf {x}},{\mathbf {v}})$ and $f^{*}({\mathbf {x}},{\mathbf {v}})$, we have the following observation.

Observation 2

For SIMON, we divide the set of indices $\{0,\ldots , L\}$ into three non-overlapping categories as follows:

• 1. Let ${\mathcal {X}}$ contain all the indices i s.t. the corresponding $x_i$’s affect $f^{*}({\mathbf {x}},{\mathbf {v}})$. Therefore, ${\mathcal {X}}$ can be defined as

  $$\begin{aligned} {\mathcal {X}}:=\left\{ i\in [0,L]: x_i\in f^{*}({\mathbf {x}},{\mathbf {v}}) \right\} \end{aligned}$$

  where $x_i\in f^{*}({\mathbf {x}},{\mathbf {v}})$ indicates that $x_i$ appears in the ANF $f^{*}({\mathbf {x}},{\mathbf {v}})$.

• 2. Let ${\mathcal {L}}_x$ be the set of indices l s.t. $l\notin {\mathcal {X}}$ and the key bits $x_l$ are linear variables of $f({\mathbf {x}},{\mathbf {v}})$. More formally, we define ${\mathcal {L}}_x$ as:

  $$\begin{aligned} {\mathcal {L}}_x:=\left\{ l\notin {\mathcal {X}}: f({\mathbf {x}},{\mathbf {v}})=x_l+\eta , \hbox { where }\eta \hbox { is irrelevant to }x_l \right\} . \end{aligned}$$

• 3. The remaining indices j are all categorized as $\overline{ {\mathcal {X}}\cup {\mathcal {L}}_x}$ and the corresponding key bits $x_j$ have no effect on the targeted bit.

We stress that such a categorization is suitable for all extended attacks on SIMON but we do not expect it to be available elsewhere. With Observation 2, we can define the set of index ${\mathcal {P}}$ as

$$\begin{aligned} {\mathcal {P}}:={\mathcal {X}}\cup \{l\} \end{aligned}$$

where l is an arbitrary element of ${\mathcal {L}}$. Then, we can have

$$\begin{aligned} k_b:=x_{{\mathcal {P}}}. \end{aligned}$$

For the correct encryptions, we have $S_{r_0}^{(i)}[\lambda ]=0$ for all $i=1,\ldots , N$. The correct guess of key bits $x_{{\mathcal {X}}}$ will ensure that ${\hat{S}}_{r_0}^{(i)}[\lambda ]=\delta$ for some static $\delta \in \{0,1\}$ and all of $i=1,\ldots , N$. Since $x_l$ is a linear variable of $f({\mathbf {x}},{\mathbf {v}})$ and $l\notin {\mathcal {X}}$, we know that $x_l$ can only affect the value $a_0$. So there must be one assignment of $x_l$ s.t. $a_0=\delta$. Therefore, this assignment of $x_l$ along with the correct guess of $x_{{\mathcal {X}}}$ will ensure that $S_{r_0}^{(i)}[\lambda ]=0$ for all $i=1,\ldots , N$.

The determination of $k_f$ is quite similar to that of $k_b$. We assign the ciphertext to ${\mathbf {v}}$ and the involved round keys $K_{r_b-1},K_{r_b-2},\ldots , K_{r_2}$ are assigned to ${\mathbf {y}}=(y_0,\ldots , y_{L'})$ where $L'=\frac{n}{2}\cdot (r_f-r_2)-1$. Then, the ANF of the targeted ${\varGamma }_2 \odot S_{r_2}$ can be represented as

$$\begin{aligned} {\varGamma }_2 \odot S_{r_2}= & {} Q(k_f, S_{r_f})=g({\mathbf {y}},{\mathbf {v}})\\= & {} \sum _{u\in {\mathbb {F}}_2^{n}}c_u M_u \end{aligned}$$

where $c_u=c_u({\mathbf {y}})\in {\mathbb {F}}_2[y_0,\ldots , y_{L'}]$. We also have

$$\begin{aligned} \widehat{{\varGamma }_2 \odot S_{r_2}}=Q^*(k_f, S_{r_f})=g({\mathbf {y}},{\mathbf {v}})+c_0 =\sum _{u\in {\mathbb {F}}_2^{n}\backslash \{0\}}c_u M_u. \end{aligned}$$

(25)

We can also divide the indices $\{0,\ldots , L'\}$ into ${\mathcal {Y}}$, ${\mathcal {L}}_y$ corresponding to the ${\mathcal {X}}$ and ${\mathcal {L}}_x$ in Observation 2. However, instead of $y_l\Vert y_{{\mathcal {Y}}}$ ($l\in {\mathcal {L}}_y$), we find that letting $k_f:=y_{{\mathcal {Y}}}$ is well enough for us to acquire the final $\psi$ parameter as is proved in Proposition 1.

Proposition 1

Supposing that $k_f=y_l\Vert y_{{\mathcal {Y}}}$ where $l\in {\mathcal {L}}_y$, then for any $\zeta \in {\mathbb {F}}_2^{|k_f|-1}$, we have

$$\begin{aligned} {\mathcal {T}}[y_l\Vert \zeta ]={\mathcal {T}}[(y_l+1)\Vert \zeta ] \end{aligned}$$

(26)

and the final $\psi$ cannot be affected by the correct guessing of $y_l$.

Proof

As to ${\mathcal {T}}[y_l\Vert \zeta ]$, we denote the set ${\mathcal {W}}(y_l,\zeta )$

$$\begin{aligned} {\mathcal {W}}(y_l,\zeta )=\left\{ i\in [1,N]: Q\left( y_l\Vert \zeta , S_{r_f}^{(i)}\right) =0\right\} \end{aligned}$$

so we have

$$\begin{aligned} {\mathcal {T}}[y_l\Vert \zeta ]=\left( {\begin{array}{c}|{\mathcal {W}}(y_l,\zeta )|\\ 2\end{array}}\right) + \left( {\begin{array}{c}N-|{\mathcal {W}}(y_l,\zeta )|\\ 2\end{array}}\right) . \end{aligned}$$

According to the definition of $y_l$, we know that $y_l$ is linear to the targeted bit ${\varGamma }_2 \odot S_{r_f}$ which means

$$\begin{aligned} Q\left( y_l\Vert \zeta , S_{r_f}^{(i)} \right) =Q\left( (y_l+1)\Vert \zeta , S_{r_f}^{(i)} \right) +1 \end{aligned}$$

for all $i\in [1,N]$. Therefore, we know that

$$\begin{aligned} {\mathcal {W}}(y_l+1,\zeta )= & {} \left\{ i\in [1,N]: Q\left( (y_l+1)\Vert \zeta , S_{r_f}^{(i)}\right) =0\right\} \\= & {} \left\{ i\in [1,N]: Q\left( y_l\Vert \zeta , S_{r_f}^{(i)}\right) =1\right\} \\= & {} \overline{{\mathcal {W}}(y_l,\zeta )} \end{aligned}$$

and $|{\mathcal {W}}(y_l+1,\zeta )|=N-|{\mathcal {W}}(y_l,\zeta )|$. So the ${\mathcal {T}}[ (y_l+1)\Vert \zeta ]$ satisfies

$$\begin{aligned} {\mathcal {T}}[ (y_l+1)\Vert \zeta ]= & {} \left( {\begin{array}{c}|{\mathcal {W}}(y_l+1,\zeta )|\\ 2\end{array}}\right) +\left( {\begin{array}{c}N-|{\mathcal {W}}(y_l+1,\zeta )|\\ 2\end{array}}\right) \\= & {} \left( {\begin{array}{c}N-|{\mathcal {W}}(y_l,\zeta )|\\ 2\end{array}}\right) + \left( {\begin{array}{c}|{\mathcal {W}}(y_l,\zeta )|\\ 2\end{array}}\right) \\= & {} {\mathcal {T}}[ y_l\Vert \zeta ] \end{aligned}$$

which proves (26). Since $\psi =\max {\mathcal {T}}$, there is some $\delta \in {\mathbb {F}}_2$, $\zeta \in {\mathcal {F}}_2^{|k_f|-1}$ satisfying

$$\begin{aligned} \psi ={\mathcal {T}}[ \delta \Vert \zeta ]={\mathcal {T}}[ (\delta +1)\Vert \zeta ]. \end{aligned}$$

This indicate that the assignment of $y_l$ cannot affect the final $\psi$ value of the extended attacks. $\square$

Proposition 1 make it safe for us to determine $k_f=y_{{\mathcal {Y}}}$. We show later that this property enables us to extend the basic attack forward by 1 round for free and the extended attacks share the same success probability $P_S$ with their corresponding basic attacks.

4.3 The success probability of the extended attacks

When $|k_f|=0$ (equivalently $r_f=r_2$), the only non-zero entry of ${\mathcal {T}}$ is ${\mathcal {T}}[k_b]$. In this situation, the $P_S$, as well as the parameter $\tau$, of this extended attack is equal to that of its basic counterpart.

For $|k_f|>0$ ($r_f>r_2$), the success probability is slightly complicated. We refer to the table ${\mathcal {T}}$ corresponding to ${\mathcal {O}}=E_K$ and ${\mathcal {O}}=\pi$ as ${\mathcal {T}}^{E_K}$, ${\mathcal {T}}^{\pi }$ respectively. According to [9], the maximum entries of ${\mathcal {T}}^{E_K}$ and ${\mathcal {T}}^{\pi }$, denoted by $\max {\mathcal {T}}^{E_K}$, $\max {\mathcal {T}}^{\pi }$, follows the normal distribution as (27).

$$\begin{aligned} \max {\mathcal {T}}^{E_K}\sim Norm(\mu _R, \sigma _R^2),\qquad \max {\mathcal {T}}^{\pi }\sim Norm(\mu _W,\sigma _W^2) \end{aligned}$$

(27)

As long as we can figure out the parameters $\mu _R$, $\mu _W$, $\sigma _R$, $\sigma _W$, we can evaluate the success probability $P_S$ of the extended known-key attacks using (12). The $\tau$ parameter can be acquired accordingly as (13).

We denote the density function of variable $X\sim Norm(\mu ,\sigma ^2)$ by $f_{\mu ,\sigma } (x)$ and the cumulative function as $F_{\mu , \sigma }(x)$. There are $2^{|k_f|}$ non-zero entries in ${\mathcal {T}}$, namely ${\mathcal {T}}[ 0],\ldots , {\mathcal {T}}[ k_f],\ldots , {\mathcal {T}}[ (2^{|k_f|}-1)]$. We have ${\mathcal {T}}^{E_K}[ k_f]\sim Norm(\mu _0, \sigma _0^2)$ where

$$\begin{aligned} \mu _0=N\cdot (2^{-1}+2^{-1}C),\qquad \sigma _0^2= N\cdot (2^{-2}-2^{-2}C^2) \end{aligned}$$

while the other $\beta \ne k_f$ satisfies ${\mathcal {T}}^{E_K}[ \beta ]\sim Norm(\mu _1, \sigma _1^2)$

$$\begin{aligned} \mu _1=2^{-1}N,\qquad \sigma _1^2=2^{-2}N. \end{aligned}$$

As to the random permutation $\pi$, the entry ${\mathcal {T}}^{\pi }[ \beta ]\sim Norm(\mu _1, \sigma _1^2)$ for all $\beta \in [0,2^{|k_f|}-1]$. Then, our targeted parameters $\mu _R$, $\mu _W$, $\sigma _R$, $\sigma _W$ can be acquired precisely with Propositions 2 and 3.

Proposition 2

The accumulative function of $\max {\mathcal {T}}^{E_K}$ satisfies

$$\begin{aligned} F_{\mu _R,\sigma _R}(x)=Pr\left\{ \max {\mathcal {T}}^{E_K}<x\right\} =F_{\mu _0,\sigma _0}(x)\cdot F_{\mu _1,\sigma _1}^{2^{|k_f|}-1}(x) \end{aligned}$$

and the corresponding density function is

$$\begin{aligned} f_{\mu _R,\sigma _R}(x)=f_{\mu _0,\sigma _0}(x)\cdot F_{\mu _1,\sigma _1}^{2^{|k_f|}-1}(x) +(2^{|k_f|}-1)\cdot f_{\mu _1,\sigma _1}(x)\cdot F_{\mu _0,\sigma _0}(x)\cdot F_{\mu _1,\sigma _1}^{2^{|k_f|}-2}(x). \end{aligned}$$

The parameters $\mu _R$ and $\sigma ^2_R$ can be computed as

$$\begin{aligned} \mu _R=\int _{-\infty }^{\infty }x\cdot f_{\mu _R,\sigma _R}(x) dx, \qquad \sigma ^2_R=\int _{-\infty }^{\infty }(x-\mu _R)^2\cdot f_{\mu _R,\sigma _R}(x) dx. \end{aligned}$$

Proposition 3

The accumulative function of $\max {\mathcal {T}}^{\pi }$ satisfies

$$\begin{aligned} F_{\mu _W,\sigma _W}(x)=Pr\left\{ \max {\mathcal {T}}^{\pi }<x\right\} =F_{\mu _1,\sigma _1}^{2^{|k_f|}}(x) \end{aligned}$$

and the corresponding density function is

$$\begin{aligned} f_{\mu _W,\sigma _W}(x)=2^{|k_f|}f_{\mu _1,\sigma _1}(x)\cdot F_{\mu _1,\sigma _1}^{2^{|k_f|}-1}(x). \end{aligned}$$

The parameters $\mu _W$ and $\sigma ^2_W$ can be computed as

$$\begin{aligned} \mu _W=\int _{-\infty }^{\infty }x\cdot f_{\mu _W,\sigma _W}(x) dx, \qquad \sigma ^2_W=\int _{-\infty }^{\infty }(x-\mu _W)^2\cdot f_{\mu _W,\sigma _W}(x) dx. \end{aligned}$$

Although the deductions of these parameters are quite straightforward, the complicated integrations are not easy to compute when $|k_f|>0$.

We increase the parameter $r_0-r_b$ from 1 and determine the corresponding $k_b$ with the method in Sect. 4.2. In this way, we can find the maximum $r_0-r_b$ whose $k_b$ does not violates the restriction in (23).

Table 3 Extended attacks on $\mathrm{SIMON}n$ where $n=32/48/64/96/128$ and the data complexity is $N=2^{n-2}$

After $r_0-r_b$ and $k_b$ are settled, we start from $r_f-r_2=1$ to identify the corresponding $k_f$.

For SIMON, the situation of $k_f$ is interesting. When we have $r_f-r_2=1$, using the method of Sect. 4.2, we have ${\mathcal {Y}}=\phi$ so the corresponding $k_f=y_{{\mathcal {Y}}}$ is an empty string so that $|k_f|=0$ so the size of the table ${\mathcal {T}}$ is 1 and ${\mathcal {T}}[0]$ is its only entry. Instead of computing ${\varGamma }_2\odot S_{r_f}$, we only need H defined

$$\begin{aligned} H^{(i)}:=H(S_{r_f}^{(i)})=\widehat{{\varGamma }_2\odot S_{r_f}^{(i)}},\quad i\in [1,N] \end{aligned}$$

where $\widehat{{\varGamma }_2\odot S_{r_f}^{(i)}}$ is defined as (25) and it can be acquired merely with the knowledge of the ciphertexts $S_{r_f}^{(i)}$. Let m be the number of i’s satisfying $H^{(i)}=0$. The corresponding $\psi$ value is

$$\begin{aligned} \psi =\max {\mathcal {T}}={\mathcal {T}}[0]=\left( {\begin{array}{c}m\\ 2\end{array}}\right) +\left( {\begin{array}{c}N-m\\ 2\end{array}}\right) . \end{aligned}$$

In this situation of $r_f-r_2=1$ and $|k_f|=0$, the extended attacks share the same $P_S$ with their corresponding basic attacks. For $r_f-r_2=2$, the $|k_f|$ grows dramatically and violates the restriction of (23), indicating a strong diffusion of the SIMON round function. Therefore, all the 8 attacks can only extend forward by 1 round. After the forward extension, the success probabilities remain unchanged.

The parameters of the extended attacks are listed in Table 3.

4.4 A tradeoff in the checking phase

For the plaintexts generated in the construction phase, the appropriate assignment of $k_b$ can ensure that $P(k_b,S_{r_b}^{(i)})=0$ for all $i=1,\ldots , N$. For the inappropriate assignments, this can happen with a probability $2^{-N}$. Since there are $2^{|k_b|}-1$ inappropriate assignments, the probability that one of them reaches Step 5.(b) of the extended attacks is $2^{|k_b|-N}$.

N is usually significantly larger than $|k_b|$ and it seems unnecessary for us to use all N plaintexts to filter out all the $2^{|k_b|}-1$ inappropriate assignments. Let $M=O(|k_b|)$ (for example $M=2|k_b|, 3|k_b|,\ldots$). Therefore, we can modify the relation ${\mathcal {R}}$ of the extended attack as

Relation ${\mathcal {R}}$: $(S_{r_b}^{(i)})_{i=1,\ldots ,N}{\mathcal {R}}(S_{r_f}^{(i)})_{i=1,\ldots ,N}$ iff there are bit strings $\alpha \in {\mathbb {F}}_2^{|k_b|}$ and $\beta \in {\mathbb {F}}_2^{|k_f|}$ conforming to:

• $P(\alpha , S_{r_b}^{(i)})=0$ for all $i=1,\ldots , M$;

• There are more than $\tau$ out of the $\left( {\begin{array}{c}N\\ 2\end{array}}\right)$ ciphertext pairs $(S^{(i)}_{r_f}, S^{(j)}_{r_f})_{1\le i<j\le N}$ satisfying $Q(\beta , S^{(i)}_{r_f})=Q(\beta , S^{(j)}_{r_f})$.

and the Step 5 of the extended attack should be changed accordingly as follows:

• 5. For the $\alpha =0,\ldots , 2^{|k_b|}-1$, we do the following substeps: (Checking)

  • (a) For all $i=1,\ldots , {M}$, if for any $P(\alpha , S_{r_b}^{(i)})\ne 0$, then continue.

  • (b) Assign ${\mathfrak {f}}\leftarrow 1$ and break;

The probability that an inappropriate assignment to reach Step 5.(b) is only $2^{|k_b|-M}$ which is still sufficiently low. But the complexity of the online phase can be reduced significantly.

5 Practical verifications

The complexities of Attacks 1–2 (the extended versions) on SIMON32 are practical ($N=2^{30}$). So we practically implement them to verify the correctness of our methods.

We first detail the procedure of Attack 2. For such a 29-round attack on SIMON32, we can assign

$$\begin{aligned} r_b=0, r_0=4, r_1=14, r_2=28, r_f=29. \end{aligned}$$

We assign the plaintext $S_0$ with boolean variables ${\mathbf {v}}=(v_{0},\ldots , v_{31})$ and the subkeys $K_0,\ldots , K_3$ with ${\mathbf {x}}=(x_0,\ldots , x_{63})$. By running the partial encryption, we acquire the ANF of $S_4[23]=f({\mathbf {x}},{\mathbf {v}})$. By analyzing $f({\mathbf {x}},{\mathbf {v}})$, we can acquire the two sets

$$\begin{aligned} {\mathcal {X}}= & {} \{2, 3, 4, 5, 6, 11, 12, 13, 15, 20, 21, 23, 29, 30, 38, 47\}\\ {\mathcal {L}}_x= & {} \{1, 19, 37, 55\} \end{aligned}$$

which are defined as Observation 2. We can define ${\mathcal {P}}={\mathcal {X}}\cup \{1\}$ and $k_b=x_{{\mathcal {P}}}$ so we have $|k_b|=17$.

For $k_f$, we first assign the ciphertext $S_{29}$ with boolean variables ${\mathbf {v}}=(v_0,\ldots , v_{31})$ and the subkey $K_{28}$ with ${\mathbf {y}}=(y_0,\ldots , y_{15})$. Then, the ANF of ${\varGamma }_2\odot S_{29}$ is

$$\begin{aligned} {\varGamma }_2\odot S_{29}=g({\mathbf {x}},{\mathbf {v}})=y_6 + v_{4} + v_{5}v_{14} + v_{8} + v_{22} \end{aligned}$$

so we have ${\mathcal {Y}}=\phi$ and $|k_f|=0$. Therefore, for any ciphertext $S_{29}^{(i)}$ ($i=1,\ldots , N$), we only need to compute

$$\begin{aligned} H(S_{29}^{(i)})=\bigoplus _{j\in \{4,8,22\}} (S_{29}^{(i)}[j])\oplus (S_{29}^{(i)}[5]\wedge S_{29}^{(i)}[14]) \end{aligned}$$

(28)

and compute the $\psi$ parameter. The relation ${\mathcal {R}}$ of Attack 3 can be defined as

Relation ${\mathcal {R}}$: $(S_{0}^{(i)})_{i=1,\ldots ,N}{\mathcal {R}}(S_{29}^{(i)})_{i=1,\ldots ,N}$ iff there are bit strings $\alpha \in {\mathbb {F}}_2^{17}$ conforming to:

• $P(\alpha , S_{0}^{(i)})=0$ for all $i=1,\ldots , N$;

• There are more than $\tau$ out of the $\left( {\begin{array}{c}N\\ 2\end{array}}\right)$ ciphertext pairs $(S^{(i)}_{29}, S^{(j)}_{29})_{1\le i<j\le N}$ satisfying $H(S^{(i)}_{29})=H( S^{(j)}_{29})$ where $H(\cdot )$ is defined as (28).

In order to acquire the highest $P_S$, we use the maximum data complexity $N=2^{30}$ and the corresponding $\tau =288230376027507000$ using (13). With all parameters settled, we run Attack 3. By modifying $S_9[15,8]$, we can nullify the $S_{4}[23]$ and ${\varGamma }_1\odot S_{14}=S_{14}[0]$, and collect the N plaintexts $S_0^{(1)},\ldots , S_0^{(N)}$. For the appropriate assignment of $k_b$, we have $P(k_b, S_0^{(i)})=0$ for all $i=1,\ldots , N$. For the inappropriate assignments $\alpha \in {\mathbb {F}}_2^{17}$, the event $P(\alpha , S_0^{(i)})=1$ appears within 20 different i attempts as has been verified by our experiments. Therefore, it is safe for us to set $M=3|k_b|=51$ and utilize the tradeoff in Sect. 4.4 for lowering the complexity of the checking phase. This tradeoff can only sacrifice the success probability by $2^{|k_b|-M}=2^{-34}$ which is still negligible. But the running time of Step 5.(a) can lower from $2^{30}$ to only 51.

With thousands of experiments, we are able to acquire the averaging $Pr_0\approx 29.56\,\%$ and $Pr_1\approx 78.66\,\%$ where $Pr_0$ and $Pr_1$ are defined as (8) (9) respectively. Since ${\mathcal {O}}$ has equal possibility to be $E_K$ or $\pi$, the experimentally acquired success probability of this known-key attack is $54.11\,\%$ according to (10), slightly lower than that of the theoretic $59.48\,\%$ but still significantly higher than 50 %. This indicates that our known-key attacks are effective.

Table 4 The parameters for attack 1–2 when $N=2^{30}$

The procedure of Attack 1 is the same so we just list the main parameters in Table 4. As can be seen, the experimentally acquired “Exp” is also close to the theoretic $P_S$.

To sum up, all our experiments are showing the significant success probabilities of Attack 1–2 and indicating the effectiveness of our methods.

6 Conclusion

In this paper, we develop and apply the latest known-key attacking techniques to round-reduced SIMON block cipher. Although our procedures follow a similar pattern as those by Blondeau, Peyrin and Wang, a number of specific methods have been elaborated to achieve known-key distinguishers for many rounds of SIMON. Our known-key attacks are able to mount up to 29/32/38/47/63 rounds for SIMON32/48/64/96/128 respectively, which comes relatively close to the full numbers of rounds. The security margin of SIMON under the known-key model is thus not as large as expected. Our findings do not affect the security of SIMON in a secret single-key scenario.