Open AccessArticle

Linear Cryptanalysis of Reduced-Round Simeck Using Super Rounds

Reham Almukhlifi

^1,* and

Poorvi L. Vora

Department of Computer Science, Taibah University, Medina 42353, Saudi Arabia

Department of Computer Science, The George Washington University, Washington, DC 20052, USA

Author to whom correspondence should be addressed.

Cryptography 2023, 7(1), 8; https://doi.org/10.3390/cryptography7010008

Submission received: 14 December 2022 / Revised: 31 January 2023 / Accepted: 1 February 2023 / Published: 9 February 2023

(This article belongs to the Topic Trends and Prospects in Security, Encryption and Encoding)

Download

Browse Figures

Versions Notes

Abstract

The Simeck family of lightweight block ciphers was proposed by Yang et al. in 2015, which combines the design features of the NSA-designed block ciphers Simon and Speck. Previously, we proposed the use of linear cryptanalysis using super-rounds to increase the efficiency of implementing Matsui’s second algorithm and achieved good results on all variants of Simon. The improved linear attacks result from the observation that, after four rounds of encryption, one bit of the left half of the state of the cipher depends on only 17 key bits (19 key bits for the larger variants of the cipher). We were able to follow a similar approach, in all variants of Simeck, with an improvement in Simeck 32 and Simeck 48 by relaxing the previous constraint of a single active bit, using multiple active bits instead. In this paper we present improved linear attacks against all variants of Simeck: attacks on 19-rounds of Simeck 32/64, 28-rounds of Simeck 48/96, and 34-rounds of Simeck 64/128, often with the direct recovery of the full master key without repeating the attack over multiple rounds. We also verified the results of linear cryptanalysis on 8, 10, and 12 rounds for Simeck 32/64.

Keywords:

Simeck; linear cryptanalysis; super round

1. Introduction

Lightweight cryptography is one of the most active research areas in the cryptographic community. In the last decade, several lightweight block ciphers were designed, which aimed to work efficiently in constrained environments. Simeck is a family of lightweight block ciphers that combines design features from Simon and Speck, using a slightly modified round function of Simon with the Speck key schedule. The round function makes it vulnerable to most attacks on Simon, one of which is the improved linear attack proposed by us in [1], where we show that, after four rounds of Simon 32/64 encryption, one bit of the left half of the state depends on only 16 key bits, which is equal to the size of one round key. In the right half, one bit of the state depends only on seven key bits. We refer to the multiple rounds of encryption as a super round. We are able to construct a super round for Simeck in a similar way, due to the great similarity in their designs.

In this paper, we are able to improve upon the approach of [1] on Simeck 32/64 and Simeck 48/96, by using multiple super rounds and multiple active bits, while keeping the number of key bits to be guessed small enough. We present the direct application of the approach [1] on all variants of Simeck, and demonstrate the improvement for Simeck 32/64 and Simeck 48/96 (though the improved approach does not improve on our previous attacks on Simon).

1.1. Our Contributions

In this paper, we present an attack on reduced-round Simeck. In contrast to the original work by us on the use of a single super round and active bit [1], the approach here uses multiple super rounds and multiple active bits that enable us to attack more rounds on Simeck 48/96 and enhance the efficiency of the linear attack on Simeck 32/64. The work presented in [1] was demonstrated exclusively on Simon. The attack presented here is demonstrated exclusively on Simeck. It does not work on Simon because the rotation used in the round functions is different and Simeck’s makes it vulnerable to our attack.

The attack presented here on Simeck 32 has larger bias than if we were to apply the attack of [1]. We refer to the application of [1] to Simeck as single super round in the table below. We do not cite [1] in the table because the approach was applied only to Simon there. Instead, we cite the section in this paper (Section 7.1) where we report the results of applying [1] to Simeck.

1.2. Comparison with Other Work

We compare our results with Bagheri’s [2] best key recovery results, which were achieved using Matsui’s second algorithm. These are the best results that were obtained using the classical linear Matsui’s second algorithm without recourse to linear hull results. In both average-case and worst-case comparisons, we were able to go deeper in all variants of Simeck, see Table 1 and Table 2.

Note the following details:

The average case was a result of counting key bits involved in the XOR as a half bit. For the worst case, the key bits were counted as a single bit as in the literature.
We made changes to how the data complexity was computed in his work for a fair comparison. Furthermore, since we are using multiple linear approximations, we applied the capacity model [3] to both our work and his.

2. Simeck

2.1. Notations

We used the notation of [1]. Superscripts indicate a round number beginning with 0 for the first round. Subscripts indicate a bit number beginning with 0 for the leftmost bit. X represents input, and

X L

and

X R

represent the left-half and right-half inputs, respectively. For example,

X L_{5}^{0}

is the sixth bit from the left of the left-half input of the first round. Similarly,

k_{i}^{j}

is the i-th bit of the j-th round key, and

k_{1}^{0}

represents the second bit of the first round key.

Moreover,

P L

represents the left plaintext half, while

P R

represents the right plaintext half input to the cipher. Similarly,

C L

means the left ciphertext half and

C R

is the right ciphertext half, the final output of the cipher. Additionally, ⊕ represents bitwise exclusive OR (XOR) and & bitwise AND. Finally,

X ⋘ z

represents cyclic shifts to the left by z bits.

2.2. Description of Simeck

There are three versions of Simeck, each denoted by Simeck

2 n / m n

, where n is the word size, m is the number of key words and

2 n

is the block size. The following Table 3 shows the specification of other variants.

The round function (see Figure 1). is defined as:

(X L^{j + 1}, X R^{j + 1}) = R_{k^{j}} (X L^{j}, X R^{j}) = (X R^{j} \oplus F (X L^{j}) \oplus k^{j}, X L^{j}) .

(1)

where:

F (X L^{j}) = [(X L^{j}) & (X L^{j} ⋘ 5)] \oplus X L^{j} ⋘ 1)

(2)

The key schedule takes the master key K as an input and generates r subkeys

k^{0}, k^{1}, \dots k^{r - 1}

. The initial states of the feedback shift registers

(t_{2}, t_{1}, t_{0}, k_{0})

are initialized with the master key words. Then, the round function is applied to update the registers and generate the round keys. The updating process is defined as follows:

k_{i + 1} = t_{i}

t_{i + 3} = k_{i} \oplus f (t_{i}) \oplus C \oplus {(z_{j})}_{i}

, where

0 \leq i \leq T - 1

C = 2^{n} - 4

, n is the word size,

{(z_{j})}_{i}

is the i-th bit of

z_{j}

The sequence

z_{j}

for Simeck 32/64 and Simeck 48/96 is generated by the primitive polynomial

X^{5} + X^{2} + 1

with the initial states (1, 1, 1, 1, 1). For Simeck 64/128, the

z j

is generated by the primitive polynomial

X^{6} + X + 1

with the initial states (1, 1, 1, 1, 1, 1).

3. Related Work

Due to the similarities between the design of Simon and Simeck, most of the attacks that have been used against Simon are applicable to Simeck. Hence, the designers of Simeck have analyzed the security of the cipher against linear and differential cryptanalysis using the best attacks that have occurred against Simon. In [4], the authors evaluate the security of Simeck and conclude with the possibility of launching a differential attack over 19, 20, and 26 rounds of Simeck 32/64, 48 and 128 respectively. Similarly, they present a linear cryptanalysis and introduce attacks on 12, 15, and 19 rounds of Simeck 32/64, 48, and 128, respectively.

Bagheri [2] applied the classical linear attacks, which are also considered the best results using the classical linear cryptanalysis. Applying Matsui’s first algorithm, they were able to attack 14, 19, and 23 rounds of Simeck 32/64, 48/96, and 64/128, respectively. Moreover, they successfully presented attacks against 18, 24, and 27 rounds using Matsui’s second algorithm.

In 2016, Kölbl et al. [5] presented a comparison between Simon and Simeck in terms of the upper bounds of the linear and differential trails. Additionally, they presented differential attacks against 19, 26 and 33 rounds on Simeck 32, Simeck 48, and Simeck 64, respectively.

Soon after this, Qiao et al. [6], presented differential attacks using a new technique, named dynamic key guessing, to attack 22, 28 and 35 rounds on Simeck 32, Simeck 48, and Simeck 64, respectively.

Chin et al. [7] evaluated the security of Simeck against linear hull cryptanalysis, considered the best linear results on Simeck achieved using the linear hull approach. They were able to attack 23, 30 and 37 rounds on Simeck 32, Simeck 48, and Simeck 64, respectively.

Moreover, there have been more results using other cryptanalysis techniques, such as zero-correlation and integral attacks.

A powerful, recently proposed attack method is zero-correlation linear cryptanalysis [8], which relies on the use of linear trails with a probability of 0.5. In 2018, Zhang et al. [9] evaluated the security of Simeck against such an attack. Hence, they presented attacks on 20 rounds, 24 rounds and 27 rounds of Simeck 32, Simeck 48, and Simeck 64, respectively.

Moreover, Bagheri and Sadeghi [10] improved these results and presented better attacks using zero-correlation linear trails on Simeck 48 and Simeck 64. They were able to attack 27-round Simeck 48 and 31-round Simeck 64. In 2019, Chen et al. [11] provided improved results using an integral attack.

Side-channel and fault attacks are a powerful category of attacks that compromise the ciphers’ physical implementation to recover the secret key. Nalla et al. [12] described the first-fault attack on Simeck and demonstrated two models of fault attack; in both attacks, they recovered the n-bit last-round key. In 2020, Duc-Phong Le et al. [13] improved the former results for fault attacks and recovered the master key by injecting fewer faults into a single round of cipher. Hence, in [14], a new countermeasure algorithm is proposed, which can detect intelligent injection faults rather than random faults.

A growing interest in side-channel attacks has been noted, especially in the use of deep learning network technology. Various models have been developed and examined to improve the efficiency of side-channel analysis attacks [15]. Wu et al. [16] presented a side-channel attack using electromagnetic leakage data to recover the last-round key of Simeck 32/64.

Hence, the use of machine learning tools in cryptography is broader than just improving side-channel attacks. Recently, Baksi et al. [17] improved the framework proposed in [18] to find differential distinguishers for Simeck and Ascon. They presented multi-layer perceptron-based distinguishers for 9-round Simeck 32, and 14-round Simeck 64. By employing ML tools, they were able to reduce the search complexity of the classical differential distinguisher.

In the post-quantum era, many cryptography systems are threatened by powerful quantum computers. SIKE is one of the candidates that was submitted to the NIST post-quantum cryptography standardization process. The cipher can provide reliable security for the post-quantum era, in addition to the current environment. Tian et al. [19] designed an improved architecture to enhance the cipher’s implementation.

In 2020, the authors of [1] proposed an improved linear attack to significantly increase the recovery attack efficiency using Matsui’s second algorithm. The super round technique essentially works by partitioning the key into smaller parts; each part is sufficient to relate multiple bits of ciphertext to a single bit of plaintext. The efficiency of this technique depends on reducing the number of key bits that need to be guessed using linear approximations. The standard technique of extending a linear approximation with one round of decryption is usually achieved by guessing the full last round key. The proposed improved technique takes advantage of the fact that one bit of cipher text depends on only 16 key bits; instead of extending the linear approximation by one round, it can be extended by four rounds with the same cost.

The general method of applying Matsui’s second algorithm using super rounds, as described by us in [1], is deriving linear approximations that have a single bit of input —

X L_{i}^{4}

X R_{i}^{4}

and multiple bits of the cipher texts (see Figure 2).

4. Super Rounds and Super Keys for Simeck

We applied the super round technique to recover multiple round keys, including the master key for all variants of Simeck, and attack more rounds using Matsui’s second algorithm. The term super round, defined in [1], represents s-rounds of encryption of the cipher. In our analysis of Simeck, this represents a four-round encryption.

In the case of Simeck 32/64, there are two super rounds, as shown in Figure 3. There is a super round that represents the first four rounds, which requires a super key for the left half of 16 bits and has a single bit of the left half of the cipher text as the output. A similar super round that requires a super key for the right half of seven bits is shown on the right side of Figure 3. In the case of the other variants, Simeck48/96 and Simeck64/128, although they correspond to a larger block and key size, the construction of super rounds with the exact size of the super keys is applicable.

4.1. The Construction of Super Rounds and Derivations of Super Keys

In this section, we demonstrate the construction of the super rounds of Simeck 32/64. Recall Equation (1), describing the round function of Simeck:

(X L^{j + 1}, X R^{j + 1}) = R_{k^{j}} (X L^{j}, X R^{j}) = (X R^{j} \oplus F (X L^{j}) \oplus k^{j}, X L^{j})

which implies that:

\begin{matrix} X L_{i}^{j + 1} & = X R_{i}^{j} \oplus Z_{i}^{j} \oplus k_{i}^{j} = X L_{i}^{j - 1} \oplus Z_{i}^{j} \oplus k_{i}^{j} = X L_{i}^{j - 3} \oplus Z_{i}^{j - 2} \oplus k_{i}^{j - 2} \oplus Z_{i}^{j} \oplus k_{i}^{j} \end{matrix}

and, hence, that:

X L_{i}^{4} = X L_{i}^{0} \oplus Z_{i}^{1} \oplus k_{i}^{1} \oplus Z_{i}^{3} \oplus k_{i}^{3} = P L_{i} \oplus Z_{i}^{1} \oplus k_{i}^{1} \oplus Z_{i}^{3} \oplus k_{i}^{3}

Similarly,

\begin{matrix} X R_{i}^{j + 1} & = X L_{i}^{j} = X L_{i}^{j - 2} \oplus Z_{i}^{j - 1} \oplus k_{i}^{j - 1} = X R_{i}^{j - 3} \oplus Z_{i}^{j - 3} \oplus k_{i}^{j - 3} \oplus Z_{i}^{j - 1} \oplus k_{i}^{j - 1} \end{matrix}

and hence that:

X R_{i}^{4} = X R_{i}^{0} \oplus Z_{i}^{0} \oplus k_{i}^{0} \oplus Z_{i}^{2} \oplus k_{i}^{2} = P R_{i} \oplus Z_{i}^{0} \oplus k_{i}^{0} \oplus Z_{i}^{2} \oplus k_{i}^{2}

Recall Equation (2):

F (X L^{j}) = [(X L^{j}) & (X L^{j} ⋘ 5)] \oplus X L^{j} ⋘ 1)

which implies that:

Z_{i}^{j} = (X L_{i}^{j} & X L_{i + 5}^{j}) \oplus X L_{i + 1}^{j}

giving us:

\begin{matrix} Z_{i}^{0} & = (P L_{i} & P L_{i + 5}) \oplus P L_{i + 1} \\ Z_{i}^{1} & = [(Z_{i}^{0} \oplus k_{i}^{0} \oplus P R_{i}) & (Z_{i + 5}^{0} \oplus k_{i + 5}^{0} \oplus P R_{i + 5})] \oplus (Z_{i + 1}^{0} \oplus k_{i + 1}^{0} \oplus P R_{i + 1}) \\ Z_{i}^{2} & = [(Z_{i}^{1} \oplus k_{i}^{1} \oplus X R_{i}^{1}) & (Z_{i + 5}^{1} \oplus k_{i + 5}^{1} \oplus X R_{i + 5}^{1})] \oplus (Z_{i + 1}^{1} \oplus k_{i + 1}^{1} \oplus X R_{i + 1}^{1}) \\ = [(Z_{i}^{1} \oplus k_{i}^{1} \oplus P L_{i}) & (Z_{i + 5}^{1} \oplus k_{i + 5}^{1} \oplus P L_{i + 5})] \oplus (Z_{i + 1}^{1} \oplus k_{i + 1}^{1} \oplus P L_{i + 1}) \\ Z_{i}^{3} & = (v_{1} & v_{2}) \oplus v_{3} \end{matrix}

where:

\begin{matrix} v_{1} = & Z_{i}^{2} \oplus k_{i}^{2} \oplus X R_{i}^{2} & = & Z_{i}^{2} \oplus k_{i}^{2} \oplus X L_{i}^{1} & = & Z_{i}^{2} \oplus Z_{i}^{0} \oplus k_{i}^{0} \oplus P R_{i} \oplus k_{i}^{2} \\ v_{2} = & Z_{i + 5}^{2} \oplus k_{i + 5}^{2} \oplus X R_{i + 5}^{2} & = & Z_{i + 5}^{2} \oplus k_{i + 5}^{2} \oplus X L_{i + 5}^{1} & = & Z_{i + 5}^{2} \oplus Z_{i + 5}^{0} \oplus k_{i + 5}^{0} \oplus P R_{i + 5} \oplus k_{i + 5}^{2} \\ v_{3} = & Z_{i + 1}^{2} \oplus k_{i + 1}^{2} \oplus X R_{i + 1}^{2} & = & Z_{i + 1}^{2} \oplus k_{i + 1}^{2} \oplus X L_{i + 1}^{1} & = & Z_{i + 1}^{2} \oplus Z_{i + 1}^{0} \oplus k_{i + 1}^{0} \oplus P R_{i + 1} \oplus k_{i + 1}^{2} \end{matrix}

Finally,

\begin{matrix} X L_{i}^{4} = & Z_{i}^{3} \oplus k_{i}^{3} \oplus X R_{i}^{3} & = & Z_{i}^{3} \oplus k_{i}^{3} \oplus X L_{i}^{2} & = & Z_{i}^{3} \oplus k_{i}^{3} \oplus Z_{i}^{1} \oplus k_{i}^{1} \oplus P L_{i} \\ X R_{i}^{4} = & X L_{i}^{3} & = & X L_{i}^{1} \oplus Z_{i}^{2} \oplus k_{i}^{2} & = & P R_{i} \oplus k_{i}^{0} \oplus Z_{i}^{0} \oplus Z_{i}^{2} \oplus k_{i}^{2} \end{matrix}

4.2. The Super Key

There is a super key corresponding to each of the super rounds depicted in Figure 3. The following table lists the components of the left and right super keys, according to the equations described in Section 4.1.

From Table 4, it can be seen that the super key of the left half contains nine bits of

k^{0}

, in the form

k_{i + m}^{0}

for

m = 0, 1, 2, 5, 6, 7, 10, 11, 15

. In addition, five bits come from the super key of the right half, in the form

k_{i + m}^{0}

for

m = 0, 1, 5, 6, 10

. As a result of this redundancy, we can obtain nine copies, five copies of each bit of

k^{0}

, for every super key of the left and right half of the state, respectively.

After determining the 16 bits of

X L^{4}

and

X R^{4}

, we obtain:

14 copies of $k_{s}^{0}$
7 copies of $k_{s}^{0} \oplus k_{s + 1}^{1}$
2 copies of $k_{s}^{0} \oplus k_{s + 2}^{0} \oplus k_{s + 1}^{1} \oplus k_{s}^{2}$

for

s = 0, 1, 2, \dots, 15

Thus, by obtaining the 16 super keys for the left and right halves of Simeck32/64, we can estimate 48 independent key bits, consisting of

k^{0}

k^{1}

, and

k^{2}

. Furthermore, as in [1], we use the majority vote to determine the value of individual key bits. Hence, the final estimation of each bit presents with one of three states: correctly determined bits, incorrectly determined bits, and undetermined bits.

5. Linear Approximations for Simeck 32/64

In this section, we describe 8-round, 10-round, and 12-round attacks using super-rounds of Simeck 32/64. These attacks are similar to previous work [1] performed on Simon. At first, we discuss how to derive the required linear approximations. Note that the only non-linear expression in the Simeck round function is the bit-wise AND [2]. Thus, we can approximate the result of the bit-wise AND by 0 with a probability of 0.75 [20]. Hence, four equivalent approximations can be used:

\begin{matrix} A p p r o x i m a t i o n 1 & : P r [F (X L_{i}^{j + 1}) = X L_{i + 1}^{j}] = \frac{3}{4} \\ A p p r o x i m a t i o n 2 & : P r [F (X L_{i}^{j + 1}) = X L_{i + 1}^{j} \oplus X L_{i}^{j}] = \frac{3}{4} \\ A p p r o x i m a t i o n 3 & : P r [F (X L_{i}^{j + 1}) = X L_{i + 1}^{j} \oplus X L_{i + 5}^{j}] = \frac{3}{4} \\ A p p r o x i m a t i o n 4 & : P r [F (X L_{i}^{j + 1}) = X L_{i + 1}^{j} \oplus X L_{i}^{j} \oplus X L_{i + 5}^{j}] = \frac{1}{4} \end{matrix}

5.1. 8-Round Attack

Following the attack procedure of Simon presented in [1], we need to derive two linear approximations for the left- and right-half inputs. The approximations contain a single bit of input, related to a few output bits that occur after four rounds.

Using a four-round linear approximation that relates a single bit of the input, we used the super rounds to obtain a single bit of input and then concatenate it with the approximation. Figure 4 depicts the eight-round attack.

Given Approximation 1, we extracted a four-round linear approximation for the left half with bias

2^{- 5}

, as follows:

\begin{matrix} P L_{i} & = X L_{i}^{0} = X R_{i}^{1} \\ = F {(X R^{2})}_{i} \oplus X L_{i}^{2} \oplus k_{i}^{1} \\ \approx X R_{i + 1}^{2} \oplus X L_{i}^{2} \oplus k_{i}^{1} \\ = X R_{i + 1}^{2} \oplus X L_{i}^{2} \oplus k_{i}^{1} \\ = F {(X R^{3})}_{i + 1} \oplus X L_{i + 1}^{3} \oplus k_{i + 1}^{2} \oplus X R_{i}^{3} \oplus k_{i}^{1} \\ \approx X R_{i + 2}^{3} \oplus X L_{i + 1}^{3} \oplus k_{i + 1}^{2} \oplus X R_{i}^{3} \oplus k_{i}^{1} \\ = X R_{i, i + 2}^{3} \oplus X L_{i + 1}^{3} \oplus k_{i + 1}^{2} \oplus k_{i}^{1} \\ = F {(X R^{4})}_{i, i + 2} \oplus X L_{i, i + 2}^{4} \oplus k_{i, i + 2}^{3} \oplus X R_{i + 1}^{4} \oplus k_{i + 1}^{2} \oplus k_{i}^{1} \\ \approx X R_{i + 1, i + 3}^{4} \oplus X R_{i + 1}^{4} \oplus X L_{i, i + 2}^{4} \oplus k_{i, i + 2}^{3} \oplus k_{i + 1}^{2} \oplus k_{i}^{1} \\ = X R_{i + 3}^{4} \oplus X L_{i, i + 2}^{4} \oplus k_{i, i + 2}^{3} \oplus k_{i + 1}^{2} \oplus k_{i}^{1} \end{matrix}

(3)

Similarly, we extracted a four-round linear approximation that relates a single bit of the right-half input with bias =

2^{- 6}

\begin{matrix} P R_{i} & = X R_{i}^{0} = F {(X R^{1})}_{i} \oplus X L_{i}^{1} \oplus k_{i}^{0} \\ \approx X R_{i + 1}^{1} \oplus X L_{i}^{1} \oplus k_{i}^{0} \\ = F {(X R^{2})}_{i + 1} \oplus X L_{i + 1}^{2} \oplus k_{i + 1}^{1} \oplus X R_{i}^{2} \oplus k_{i}^{0} \\ \approx X R_{i + 2}^{2} \oplus X L_{i + 1}^{2} \oplus k_{i + 1}^{1} \oplus X R_{i}^{2} \oplus k_{i}^{0} \\ = X R_{i, i + 2}^{2} \oplus X L_{i + 1}^{2} \oplus k_{i + 1}^{1} \oplus k_{i}^{0} \\ = F {(X R^{3})}_{i, i + 2} \oplus X L_{i, i + 2}^{3} \oplus k_{i, i + 2}^{2} \oplus X L_{i + 1}^{2} \oplus k_{i + 1}^{1} \oplus k_{i}^{0} \\ \approx X R_{i + 1, i + 3}^{3} \oplus X L_{i, i + 2}^{3} \oplus k_{i, i + 2}^{2} \oplus X R_{i + 1}^{3} \oplus k_{i + 1}^{1} \oplus k_{i}^{0} \\ = X R_{i + 3}^{3} \oplus X L_{i, i + 2}^{3} \oplus k_{i, i + 2}^{2} \oplus k_{i + 1}^{1} \oplus k_{i}^{0} \\ = F {(X R^{4})}_{i + 3} \oplus X L_{i + 3}^{4} \oplus k_{i + 3}^{3} \oplus X R_{i, i + 2}^{4} \oplus k_{i, i + 2}^{2} \oplus k_{i + 1}^{1} \oplus k_{i}^{0} \\ = X R_{i, i + 2, i + 4}^{4} \oplus X L_{i + 3}^{4} \oplus k_{i + 3}^{3} \oplus k_{i, i + 2}^{2} \oplus k_{i + 1}^{1} \oplus k_{i}^{0} \end{matrix}

(4)

Therefore, we can append the super round to the four-round approximations Equations (3) and (4) to relate the plaintext to the single bit of super round output. Thus, we obtained an approximate relationship between plaintext, ciphertext, and super key bits. This extension enabled us to attack up to eight rounds without further reducing the bias. This gives us the following expressions:

\begin{matrix} X L_{i}^{4} \oplus X R_{i + 3}^{8} \oplus X L_{i, i + 2}^{8} = k_{i, i + 2}^{7} \oplus k_{i + 1}^{6} \oplus k_{i}^{5} \end{matrix}

(5)

\begin{matrix} X R_{i}^{4} \oplus X R_{i, i + 2, i + 4}^{8} \oplus X L_{i + 3}^{8} = k_{i + 3}^{7} \oplus k_{i, i + 2}^{6} \oplus k_{i + 1}^{5} \oplus k_{i}^{4} \end{matrix}

(6)

5.2. 10-Round Attack

By adding two rounds of decryption at the end of the 8-round attack, we could obtain a 10-round attack. This extension reuired us to guess a few bits of the last round key. Figure 5 depicts the 10-round linear attack.

Single-round decryption can be expressed with the following equation [1]:

\begin{matrix} X L^{j} & = X R^{j + 1} \\ X R^{j} & = F (X R^{j + 1}) \oplus X L^{j + 1} \oplus k^{j}, \end{matrix}

Therefore, the two rounds decryption can be written as follows:

\begin{matrix} X L^{j} & = F (X R^{j + 2}) \oplus X L^{j + 2} \oplus k^{j + 1} \\ X R^{j} & = F (F (X R^{j + 2}) \oplus X L^{j + 2} \oplus k^{j + 1}) \oplus X R^{j + 2} \oplus k^{j}, \end{matrix}

Recall Equation (7):

\begin{matrix} X L_{i}^{4} \oplus X R_{i + 3}^{8} \oplus X L_{i, i + 2}^{8} = k_{i, i + 2}^{7} \oplus k_{i + 1}^{6} \oplus k_{i}^{5} \end{matrix}

(7)

We rewrote

X^{8}

in terms of

X^{10}

, which gave us:

\begin{matrix} X L^{8} & = F (X R^{10}) \oplus X L^{10} \oplus k^{9} \\ X R^{8} & = F (F (X R^{10}) \oplus X L^{10} \oplus k^{9}) \oplus X R^{10} \oplus k^{8} \end{matrix}

(8)

By substituting the expression of

X L^{8}

and

X R^{8}

, we obtained:

\begin{matrix} X L_{i}^{4} \oplus X R_{i + 3}^{8} \oplus X L_{i, i + 2}^{8} = k_{i, i + 2}^{7} \oplus k_{i + 1}^{6} \oplus k_{i}^{5} \end{matrix}

\begin{matrix} X L_{i}^{4} \oplus F (X R_{i + 3}^{9}) \oplus X L_{i + 3}^{9} \oplus k_{i + 3}^{8} \oplus X R_{i, i + 2}^{9} = k_{i, i + 2}^{7} \oplus k_{i + 1}^{6} \oplus k_{i}^{5} \end{matrix}

\begin{matrix} X L_{i}^{4} \oplus (X R_{i + 3}^{9} & X R_{i + 8}^{9}) \oplus X R_{i + 4}^{9} \oplus X L_{i + 3}^{9} \oplus k_{i + 3}^{8} \oplus X R_{i, i + 2}^{9} = k_{i, i + 2}^{7} \oplus k_{i + 1}^{6} \oplus k_{i}^{5} \end{matrix}

Hence, the 10-round expression for the left-half is as follows:

\begin{matrix} X L_{i}^{4} \oplus (F (X R_{i + 3}^{10}) \oplus X L_{i + 3}^{10} \oplus k_{i + 3}^{9} & F (X R_{i + 8}^{10}) \oplus X L_{i + 8}^{10} \oplus k_{i + 8}^{9}) \oplus F (X R_{i + 4}^{10}) \oplus X L_{i + 4}^{10} \\ = k_{i + 4}^{9} \oplus X R_{i + 3}^{10} \oplus k_{i + 3}^{8} \oplus F (X R_{i, i + 2}^{10}) \oplus X L_{i, i + 2}^{10} \oplus k_{i, i + 2}^{9} = k_{i, i + 2}^{7} \oplus k_{i + 1}^{6} \oplus k_{i}^{5} \end{matrix}

(9)

Following the same approach, we extended the four-round linear approximation to the right half, and added two rounds of decryption:

\begin{matrix} X R_{i}^{4} \oplus X R_{i, i + 2, i + 4}^{8} \oplus X L_{i + 3}^{8} = k_{i + 3}^{7} \oplus k_{i, i + 2}^{6} \oplus k_{i + 1}^{5} \oplus k_{i}^{4} \end{matrix}

\begin{matrix} X R_{i}^{4} \oplus F (X R_{i, i + 2, i + 4}^{9}) \oplus X L_{i, i + 2, i + 4}^{9} \oplus k_{i, i + 2, i + 4}^{8} \oplus X R_{i + 3}^{9} \\ = k_{i + 3}^{7} \oplus k_{i, i + 2}^{6} \oplus k_{i + 1}^{5} \oplus k_{i}^{4} \end{matrix}

\begin{matrix} X R_{i}^{4} \oplus (X R_{i}^{9} & X R_{i + 5}^{9}) \oplus (X R_{i + 2}^{9} & X R_{i + 7}^{9}) \oplus (X R_{i + 4}^{9} & X R_{i + 9}^{9}) \\ \oplus X R_{i + 1, i + 3, i + 5}^{9} \oplus X L_{i, i + 2, i + 4}^{9} \oplus k_{i, i + 2, i + 4}^{8} \oplus X R_{i + 3}^{9} = k_{i + 3}^{7} \oplus k_{i, i + 2}^{6} \oplus k_{i + 1}^{5} \oplus k_{i}^{4} \end{matrix}

\begin{matrix} X R_{i}^{4} \oplus (X R_{i}^{9} & X R_{i + 5}^{9}) \oplus (X R_{i + 2}^{9} & X R_{i + 7}^{9}) \oplus (X R_{i + 4}^{9} & X R_{i + 9}^{9}) \oplus \\ X R_{i + 1, i + 5}^{9} \oplus X R_{i, i + 2, i + 4}^{10} = k_{i, i + 2, i + 4}^{8} \oplus k_{i + 3}^{7} \oplus k_{i, i + 2}^{6} \oplus k_{i + 1}^{5} \oplus k_{i}^{4} \end{matrix}

Thus, the 10-round linear expression for the right half is as follows:

\begin{matrix} X R_{i}^{4} \oplus (F (X R_{i}^{10}) \oplus X L_{i}^{10} \oplus k_{i}^{9} & F (X R_{i + 5}^{10}) \oplus X L_{i + 5}^{10} \oplus k_{i + 5}^{9}) \oplus \\ (F (X R_{i + 2}^{10}) \oplus X L_{i + 2}^{10} \oplus k_{i + 2}^{9} & F (X R_{i + 7}^{10}) \oplus X L_{i + 7}^{10} \oplus k_{i + 7}^{9}) \oplus \\ (F (X R_{i + 4}^{10}) \oplus X L_{i + 4}^{10} \oplus k_{i + 4}^{9} & F (X R_{i + 9}^{10}) \oplus X L_{i + 9}^{10} \oplus k_{i + 9}^{9}) \oplus \\ F (X R_{i + 1, i + 5}^{10}) \oplus X L_{i + 1, i + 5}^{10} \oplus k_{i + 1, i + 5}^{9} \oplus X R_{i, i + 2, i + 4}^{10} = \\ k_{i, i + 2, i + 4}^{8} \oplus k_{i + 3}^{7} \oplus k_{i, i + 2}^{6} \oplus k_{i + 1}^{5} \oplus k_{i}^{4} \end{matrix}

(10)

In addition to the 16 and 7 key bits required to obtain the input bits for the left and the right half, respectively, extra key bits were required to evaluate the Equations (9) and (10). Two key bits

k_{i + 3}^{9}

and

k_{i + 8}^{9}

were required to evaluate Equation (9) and six key bits

k_{i}^{9}

k_{i + 5}^{9}

k_{i + 2}^{9}

k_{i + 7}^{9}

k_{i + 4}^{9}

, and

k_{i + 9}^{9}

to evaluate Equation (10).

5.3. 12-Round Attack

Here, we extend the four-round linear approximations Equations (3) and (4) into seven-round linear approximations, using Equations (11) and (12) for the left and right half with biases

2^{- 10}

and

2^{- 12}

, respectively (see Table A1 and Table A2 for the derivation):

\begin{matrix} P L_{i} \oplus X R_{i, i + 4}^{7} \oplus X L_{i + 1}^{7} = k_{i + 1}^{6} \oplus k_{i, i + 2, i + 4}^{5} \oplus k_{i + 3}^{4} \oplus k_{i, i + 2}^{3} \oplus k_{i + 1}^{2} \oplus k_{i}^{1} \end{matrix}

(11)

\begin{matrix} P R_{i} \oplus X L_{i, i + 4}^{7} = k_{i, i + 4}^{6} \oplus k_{i + 1}^{5} \oplus k_{i, i + 2, i + 4}^{4} \oplus k_{i + 3}^{3} \oplus k_{i, i + 2}^{2} \oplus k_{i + 1}^{1} \oplus k_{i}^{0} \end{matrix}

(12)

Thus, we obtained the 11-round linear trails by appending the super round at the beginning of Equations (11) and (12), as follows:

\begin{matrix} X L_{i}^{4} \oplus X R_{i, i + 4}^{11} \oplus X L_{i + 1}^{11} = k_{i + 1}^{10} \oplus k_{i, i + 2, i + 4}^{9} \oplus k_{i + 3}^{8} \oplus k_{i, i + 2}^{7} \oplus k_{i + 1}^{6} \oplus k_{i}^{5} \end{matrix}

(13)

\begin{matrix} X R_{i}^{4} \oplus X L_{i, i + 4}^{11} = k_{i, i + 4}^{10} \oplus k_{i + 1}^{9} \oplus k_{i, i + 2, i + 4}^{8} \oplus k_{i + 3}^{7} \oplus k_{i, i + 2}^{6} \oplus k_{i + 1}^{5} \oplus k_{i}^{4} \end{matrix}

(14)

Then, we added one more round of decryption at the end of the 11-round trails and obtained the following 12-round trails for the left half:

\begin{matrix} X L_{i}^{4} \oplus X R_{i, i + 4}^{11} \oplus X L_{i + 1}^{11} \\ = k_{i + 1}^{10} \oplus k_{i, i + 2, i + 4}^{9} \oplus k_{i + 3}^{8} \oplus k_{i, i + 2}^{7} \oplus k_{i + 1}^{6} \oplus k_{i}^{5} \end{matrix}

\begin{matrix} X L_{i}^{4} \oplus F (X R_{i, i + 4}^{12}) \oplus X L_{i, i + 4}^{12} \oplus k_{i, i + 4}^{11} \oplus X R_{i + 1}^{12} \\ = k_{i + 1}^{10} \oplus k_{i, i + 2, i + 4}^{9} \oplus k_{i + 3}^{8} \oplus k_{i, i + 2}^{7} \oplus k_{i + 1}^{6} \oplus k_{i}^{5} \end{matrix}

\begin{matrix} X L_{i}^{4} \oplus (X R_{i}^{12} & X R_{i + 5}^{12}) \oplus (X R_{i + 4}^{12} & X R_{i + 9}^{12}) \oplus X R_{i + 5}^{12} \oplus X L_{i, i + 4}^{12} \\ = k_{i, i + 4}^{11} \oplus k_{i + 1}^{10} \oplus k_{i, i + 2, i + 4}^{9} \oplus k_{i + 3}^{8} \oplus k_{i, i + 2}^{7} \oplus k_{i + 1}^{6} \oplus k_{i}^{5} \end{matrix}

(15)

A similar process was followed to obtain the 11-round linear approximation for the right half:

\begin{matrix} X R_{i}^{4} \oplus X L_{i, i + 4}^{11} = k_{i, i + 4}^{10} \oplus k_{i + 1}^{9} \oplus k_{i, i + 2, i + 4}^{8} \oplus k_{i + 3}^{7} \oplus k_{i, i + 2}^{6} \oplus k_{i + 1}^{5} \oplus k_{i}^{4} \\ X R_{i}^{4} \oplus X R_{i, i + 4}^{12} = k_{i, i + 4}^{10} \oplus k_{i + 1}^{9} \oplus k_{i, i + 2, i + 4}^{8} \oplus k_{i + 3}^{7} \oplus k_{i, i + 2}^{6} \oplus k_{i + 1}^{5} \oplus k_{i}^{4} \end{matrix}

(16)

Figure 6 depicts the 12-round linear attack.

6. Experimental Verification

We conducted several experiments to verify the attacks presented in Section 5 and provide the experimental results presented in this section.

Recall the super key bits shown in Table 4, which come in three forms:

k_{i}^{0}

k_{i + 2}^{0} \oplus k_{i}^{1}

, or

k_{i}^{0} \oplus k_{i + 4}^{0} \oplus k_{i + 2}^{1} \oplus k_{i}^{2}

. We reused the notations that appeared in [1], for

B i t 1

B i t 2

B i t 3

and

B i t 4

. These four bits were determined using Equation (17).

\begin{matrix} \begin{matrix} k_{i}^{0} = B i t 1_{i} \\ k_{i}^{1} = B i t 2_{i} \oplus B i t 1_{i + 2} \\ k_{i}^{2} = B i t 1_{i} \oplus B i t 2_{i + 2} \oplus B i t 3_{i} \\ k_{i}^{9} = B i t 4_{i} \end{matrix} \end{matrix}

(17)

6.1. 8-Round Key Recovery Attack

To determine the data that were required to conduct the experiments, we followed Matsui’s rule [21], which suggests using some multiple of

b i a s^{- 2}

. Thus, the required data complexity for the eight-round attack is a multiple of

2^{- 6 * - 2}

. Therefore, we conducted 14 experiments with

2^{14}

plain text and cipher text pairs.

Table 5 shows that the estimates derived from evaluating the linear approximation of the right half did not improve the overall results. This is because of the low bias approximations used in this case. As the number of copies of

B i t 1

B i t 2

, and

B i t 3

increased, the accuracy of the estimation results also increased. Thus, the estimates of

B i t 1

are more accurate than those of

B i t 2

and

B i t 3

6.2. 10-Round Key Recovery Attack

Similar to the previous attack, we implemented a 10-round attack with 14 keys chosen at random and

2^{14}

P/C pairs. Table 6 shows that, compared to the results obtained in the 8-round attack, we obtained a different observation. The approximations of the right half improved the overall results, especially in the estimations of

k^{9}

; hence, every bit of

k^{9}

received six copies from the right-half evaluation, and only two copies from the left-half evaluation.

6.3. 12-Round Key Recovery Attack

We conducted three experiments regarding the 12-round attack using

2^{24}

P/C pairs, with keys chosen at random. Table 7 shows similar results to those of the eight-round attack. The combined estimation of both halves (left and right) did not enhance the results obtained using only the left-half estimations.

6.4. Experimental Results of 8-Round Attack without Approximations

Since Simeck is designed based on the Feistel structure, and an essential features of this design is that the same algorithm was used for encryption and decryption, an equivalent super-round of four rounds of decryption was also established. We can launch a meet-in-the-middle attack on eight-round linear cryptanalyses of Simeck 32/64 without any approximations, which is the same attack that was launched on Simon in the previous work [1].

Figure 7 depicts how the two super-rounds are connected to attack eight rounds of Simeck 32/64. We started with one super round in the forward direction and the second super round in the backward direction; hence, we could efficiently apply the meet-in-the-middle technique.

The first super round

F_{S 1}

starts with a plaintext and 17 key bits

K 1

, to produce a single bit of four-rounds encryption

X L_{i}^{4}

. Then, the second super round

F_{S 2}

takes the ciphertext and eight key bits

K 2

, and generates a single bit of four-rounds decryption. Following the procedure described in [1], we computed

F_{S 1}

and

F_{S 2}

for all possible values of the encryption and decryption super-keys for every bit i.

We conducted two experiments using only 48 plain text and cipher text pairs; we were able to retrieve the correct value of the 112 bits.

6.5. Summary of Experimental Results

Here, we provide a summary of our experimental results. See Table 8.

7. Projected Results Using Multiple Linear Cryptanalysis

This section presents two projected linear attacks; the first uses a single super-round, which is the direct application of the approach presented in [1], and the second is a new class of attacks where we use multiple super-rounds.

7.1. Linear Attacks Using a Single Super-Round

Here, we present a 19-round linear attack, a direct application of the original attack that we proposed in [1]. This is achieved by extending the 12-round linear approximations in Equation (18) and appending the super rounds of four rounds of encryption and three rounds of decryption.

To compute the data complexity, we first compute the capacity:

\begin{matrix} {\bar{c}}^{2} = 4 \times 16 \times 2^{- 18 \times 2} = 2^{6} \times {2^{- 18}}^{2} = 2^{- 30} \end{matrix}

Nine key bits must be estimated to add three rounds of decryption to the approximations for the left half:

Seven bits of $k_{i}^{19}$ for $i = 3, 8, 13, 0, 5, 2, 7$ ;
Two bits of the sum: $k_{i + 1}^{19} \oplus k_{i}^{18}$ for $i = 3, 8$ .

Twelve key bits must be estimated to add three rounds of decryption to the approximations for the right half:

Eight bits of $k_{i}^{19}$ for $i = 0, 5, 10, 2, 7, 12, 1, 6$ ;
Four bits of the sum: $k_{i + 1}^{19} \oplus k_{i}^{18}$ for $i = 0, 5, 2, 7$ .

The time complexity required for this attack to evaluate the approximations for the left half is

16 \times 2^{30} \times 2^{16} \times 2^{9} = 2^{59}

. For the right side, it is

16 \times 2^{30} \times 2^{7} \times 2^{12} = 2^{53}

. The overall complexity required to evaluate the two halves is

2^{59.02}

Hence, we can attack 20 rounds in the case of average-case computations by extending the 12-round linear approximations of Equation (18), appending a single super round of four rounds of encryption and adding four rounds of decryption.

We extended the seven-round linear characteristics in Equations (11) and (12) into the following 12-round linear approximations for the left and the right sides, with biases=

2^{- 18}

and

2^{- 19}

, respectively.

\begin{matrix} P L_{i} \oplus C R_{i + 3} \oplus C L_{i, i + 2, i + 4} = k_{i, i + 2, i + 4}^{11} \oplus k_{i + 1}^{10} \oplus k_{i, i + 4}^{9} \oplus k_{i, i + 4}^{7} \oplus k_{i + 1}^{6} \oplus k_{i, i + 2, i + 4}^{5} \\ \oplus k_{i + 3}^{4} \oplus k_{i, i + 2}^{3} \oplus k_{i + 1}^{2} \oplus k_{i}^{1} \\ P R_{i} \oplus C R_{i, i + 2} \oplus C L_{i + 3} = k_{i + 3}^{11} \oplus k_{i + 2, i, i + 4}^{10} \oplus k_{i + 1}^{9} \oplus k_{i, i + 4}^{8} \oplus k_{i, i + 4}^{6} \oplus k_{i + 1}^{5} \oplus k_{i, i + 2, i + 4}^{4} \\ \oplus k_{i + 3}^{3} \oplus k_{i, i + 2}^{2} \oplus k_{i + 1}^{1} \oplus k_{i}^{0} \end{matrix}

(18)

We compute the capacity for the system of approximations as follows:

\begin{matrix} {\bar{c}}^{2} = 4 \times 16 \times 2^{- 18 \times 2} = 2^{6} \times {2^{- 18}}^{2} = 2^{- 30} \end{matrix}

The super round costs on average 11.5 and 4.5 were appended for the left and the right half, respectively. Moreover, four rounds of decryption costs were appended by estimating, on average, 16 key bits and 18.5 key bits for the left- and right-half approximations, respectively.

Twenty-three key bits (16 bits on average) are needed to estimate the left-half approximations:

Fourteen bits of $k_{i}^{19}$ for $i = 3, 8, 13, 4, 2, 7, 9, 14, 0, 5, 10, 12, 1, 6$ , with each counted as a half bit.
Seven bits of the sum: $k_{i + 1}^{19} \oplus k_{i}^{18}$ for $i = 5, 13, 2, 7, 3, 58$ .
Two bits of the sum: $k_{i, i + 2}^{19} \oplus k_{i + 1}^{18} \oplus k_{i}^{17}$ , for $i = 3, 8$

Twenty-five key bits (18.5 bits on average) are required to estimate the right-half approximations:

Thirteen bits of $k_{i}^{19}$ for $i = 0, 5, 8, 10, 1, 6, 15, 11, 2, 7, 12, 3, 13$ , each counted as a half bit
Eight bits of the sum: $k_{i + 1}^{19} \oplus k_{i}^{18}$ for $i = 0, 5, 10, 2, 7, 12, 1, 6$ .
Four bits of the sum: $k_{i, i + 2}^{19} \oplus k_{i + 1}^{18} \oplus k_{i}^{17}$ , for $i = 0, 5, 2, 7$

Thus, the time complexity required to evaluate the approximations for the left half is

2^{4} \times 2^{30} \times 2^{11.5} \times 2^{16} = 2^{61.5}

, in addition to the complexity of evaluating the approximations for the right half =

2^{4} \times 2^{30} \times 2^{4.5} \times 2^{18.5} = 2^{57}

. Thus, the total time complexity is

2^{61.56}

7.2. Improved Linear Approximations for Simeck 32/64

The approximations used in the attack presented in Section 7.1 have a single bit of the input mask due to the constraint of incorporating only a single super-round. This constraint is relaxed in this work. We can improve the overall attack efficiency by deriving a linear approximation with multiple input masks, which means we can employ multiple super-rounds.

Therefore, we are able to derive this improved 13-round approximation with bias equal to

2^{- 18}

. (see Table A3 for the derivation).

\begin{matrix} P L_{i + 3} \oplus P R_{i, i + 2} \oplus X R_{i + 1}^{13} \oplus X L_{i, i + 4}^{13} \oplus k_{i, i + 4}^{10} \oplus k_{i + 1}^{9} \oplus k_{i, i + 2, i + 4}^{8} \\ \oplus k_{i + 3}^{7} \oplus k_{i, i + 2}^{6} \oplus k_{i + 1}^{5} \oplus k_{i}^{4} \oplus k_{i}^{2} \oplus k_{i + 1}^{1} \oplus k_{i, i + 2}^{0} \end{matrix}

(19)

7.3. Linear Attacks Using Multiple Super Rounds

Incorporating multiple super rounds enables us to enhance the time complexity of the attack. Here, we extend the 13-round linear trail (19) into a 19-round linear attack by appending six more rounds: four rounds of encryption, and two rounds of decryption.

The system of approximations has the following capacity:

\begin{matrix} {\bar{c}}^{2} = 4 \times 16 \times 2^{- 18 \times 2} = 2^{6} \times {2^{- 18}}^{2} = 2^{- 30} \end{matrix}

Thus, the data complexity for this attack is

2^{30}

The three super-rounds require that three super-keys are estimated, which consist of:

Fourteen bits of the last round key $k_{i}^{0}$ for $i = 10, 5, 14, 9, 4, 8, 3, 2, 13, 0, 1, 6, 7, 12$ , with each counted as a half bit.
Nine bits of the sum $k_{i + 1}^{0} \oplus k_{i}^{1}$ for $i = 9, 4, 13, 8, 3, 0, 5, 2, 7$ .
Two bits of the sum $k_{i, i + 2}^{0} \oplus k_{i + 1}^{1} \oplus k_{i}^{2}$ for $i = 3, 8$ .

The cost of appending three super-rounds (one for each input mask bit) is guessing 25 key bits. Additionally, two more key bits

k_{0, 5}^{18}

required estimation to append two decryption rounds. The time complexity for this attack is

2^{4} \times 2^{25} \times 2^{2} \times 2^{30} = 2^{61}

In the average-case complexity, we can add one more round of decryption to the 19-round attack and present a 20-round attack.

Nine key bits must be estimated to add three rounds of decryption:

Five bits of $k_{i}^{19}$ for $i = 0, 5, 10, 1, 6$ , with each counted as a half bit.
Four bits of the sum: $k_{i + 1}^{19} \oplus k_{i}^{18}$ for $i = 0, 5$ .

As a result, the average cost of appending three super-rounds is to guess 18 key bits, in addition to 6.5 key bits, to add three rounds of decryption; thus, the time complexity for this attack is

2^{4} \times 2^{30} \times 2^{18} \times 2^{6.5} = 2^{58.5}

Table 9 summarizes our results of Simeck 32/64 and compares them with the best results presented in [2]. We were able to go deeper by two rounds.

8. The Effect of Super Rounds on Larger Variants of Simeck

In contrast to Simon, the larger versions of Simeck have the same super keys with the same size. Therefore, we were able to attack larger number of rounds.

For Simeck 48, incorporating multiple super-rounds instead of a single super-round yields better results. We derived a 20-round linear approximation that has three active bits in the input mask and one bit of the output mask. We employ this approximation to attack 29-rounds of Simeck 48 by adding three super rounds (four rounds of encryption) at the beginning and five rounds of decryption at the end. This comes at the cost of guessing 41 key bits on average.

For Simeck 64, we derived a 25-round approximation and added nine rounds at both ends: four rounds of encryption and five rounds of decryption, at the cost of guessing 49 key bits on average. Thus we attack up to 34 rounds of this version of Simeck.

9. Discussion

The outcomes of this research have provided insight into the differences between Simon and Simeck; even though they are very similar in design, hence applying our attack model on reduced round Simeck results in better attacks on most of Simeck versions than on Simon. We are able to present linear cryptanalysis on 29-round Simeck 48/96 and 34-round Simeck 64/128, whereas in the case of Simon for the same versions, we are only able to attack 21-round and 25-round respectively. These improved results are caused by the rotational functions, which is the only difference between the two ciphers.

We observed in that experiments that we got the same number of master key bits in the 8-round and 12-round versions, but recovered more key bits with the 10-round attack. This is because

k_{9}

consists of some bits of the master key; see Appendix A for more details. Additionally, the 8-round versions of both Simon and Simeck are broken employing two super-rounds.

10. Conclusions and Future Work

This paper presents the results of applying the novel notion of super rounds presented in [1] on all versions of the Simeck lightweight block cipher. We presented experimental results on 8-round, 10-round, and 12 -rounds attacks on Simeck 32, and we recovered a large number of the master key bits with high accuracy. Theoretically, we present attacks on 20 rounds of Simeck 32, 29 rounds of Simeck 48 and 34 rounds of Simeck 64. Thus, relaxing the constraint of using only linear approximations with one active input mask enhances the efficiency of attack on Simeck 32 and enables us to present a better attack on Simeck 48.

In future work, it would be interesting to examine similar lightweight ciphers, such as Spix, and see if our attack using super-rounds are applicable. Another aspect that could be investigated is combining the proposed model with linear-differential cryptanalysis.

Author Contributions

R.A. led the work for her doctoral dissertation, contributing most of the effort. P.L.V. provided guidance. All authors have read and approved the final version of the manuscript.

Funding

This research was sponsored in part by NSF Award 1421373.

Conflicts of Interest

The authors declare no conflict of interest.

Appendix A. The Deduction of k 3 from k 9

Simeck key schedule generates r-4 more round keys from the 64-bit master key. Therefore, we are able to write the round keys in terms of the master key bits

k^{0}

k^{1}

k^{2}

, and

k^{3}

k^{9}

is generated as in Equation (A1), which is expressed in terms of the master key bits in Equation (A2).

k^{9} = k^{5} \oplus F (k^{6}) \oplus c \oplus {(z_{0})}_{5}

(A1)

Hence,

k^{3}

may be expressed in terms of

k^{0}

k^{1}

k^{2}

, and

k^{9}

as follows:

\begin{matrix} k^{9} & = k^{1} \oplus F (k^{2}) \oplus F (k^{2} \oplus f (k^{3})) \oplus C \oplus {(Z_{0})}_{1} \oplus C \oplus {(Z_{0})}_{2} \oplus C \oplus {(Z_{0})}_{5} \end{matrix}

(A2)

Recall the round function f:

F (X L^{j}) = [(X L^{j}) & (X L^{j} ⋘ 5)] \oplus X L^{j} ⋘ 1)

It is clear that f consists of the non-invertible bitwise AND; hence, we can assume that the output of f is zero:

\begin{matrix} F (X) & = (0^{n} \oplus X L^{j} ⋘ 1) \\ = X L^{j} ⋘ 1 \end{matrix}

(A3)

where

0^{n}

denotes a zero vector of n-bits.

We can write the inverse function as follows:

\begin{matrix} F^{- 1} (X) & = X ⋘ 1 \end{matrix}

(A4)

Therefore, to write

k^{9}

in terms of the master key, we apply (A4) in (A2):

\begin{matrix} k^{9} & = k^{1} \oplus f^{- 1} (k^{2}) \oplus f^{- 1} (k^{2} \oplus f^{- 1} (k^{3})) C \oplus {(Z_{0})}_{1} \oplus C \oplus {(Z_{0})}_{2} \oplus C \oplus {(Z_{0})}_{5} \\ = k^{1} \oplus (k^{2} ⋘ 1) \oplus (k^{2} ⋘ 1) \oplus (k^{3} ⋘ 2) \oplus C \oplus {(Z_{0})}_{1} \oplus C \oplus {(Z_{0})}_{2} \oplus C \oplus {(Z_{0})}_{5} \end{matrix}

(A5)

Appendix B. Derive 13-Round Linear Approximations for Simeck 32/64

Table A1. The sequence of approximations used to derive 13-round linear trails for the left-half of Simeck 32.

Active Bits in the Left Side	Active Bits in the Right Side	Used Approximation	Number of Approximations
0	-
-	0	1	1
0	1	1	1
1	0,2	1;1	2
0,2	3	1	1
3	0,2,4	3;1;1	3
0,2,4	1	1	1
1	0,4	3;1	2
0,4			0
	0,4	3;1	2
0,4	1	1	1
1	0,2,4	3;1;1	3
0,2,4	3

Table A2. The sequence of approximations used to derive 13 rounds for the right-half of Simeck 32.

Active Bits in the Left Side	Active Bits in the Right Side	Used Approximation	Number of Approximations
-	0	1	1
0	1	1	1
1	0,2	1:1	2
0,2	3	1	1
3	0,2,4	3;1;1	3
0,2,4	1	1	1
1	0,4	3;1	2
0,4	-
	0,4	3;1	2
0,4	1	1	1
1	0,2,4	3;1;1	3
0,2,4	3	1	1
3	0,2

Appendix C. Derive an Improved 13-Round Linear Approximations for Simeck 32/64

Table A3. The sequence of approximations used to derive a 13-round linear trails of Simeck 32.

Active Bits in the Left Side	Active Bits in the Right Side	Used Approximation	Number of Approximations
3	0, 2	1:1	2
0,2	1	1	1
1	0	1	1
0	-
0	1	1	1
	0	1	1
1	0,2	1;1	2
0,2	3	1	1
3	0,2,4	3;1;1	3
0,2,4	1	1	1
1	0,4	3;1	2
0,4	-
	0.4	3;1	2
0,4	1

Appendix D. Linear Cryptanalysis of Simeck 48/96 Using a Single Super Round

In contrast to Simon, the larger versions of Simeck have exact super keys of the same size. Therefore, we can attack up to 27 rounds of Simeck 48/96.

Appendix D.1. Linear Approximations for Simeck 48/96

We can extend the 12-round linear trail Equation (18) into 20-round linear expressions, with biases =

2^{- 27}

and

2^{- 28}

for the left half and right half, respectively (see Table A4 and Table A5 for more details):

\begin{matrix} P L_{i} \oplus X R_{i + 3}^{20} \oplus X L_{i, i + 2}^{20} = k_{i, i + 2}^{19} \oplus k_{i + 1}^{18} \oplus k_{i}^{17} \oplus k_{i}^{15} \oplus k_{i + 1}^{14} \oplus k_{i, i + 2}^{13} \oplus k_{i + 3}^{12} \oplus \\ k_{i, i + 4, i + 2}^{11} \oplus k_{i + 1, i + 5}^{10} \oplus k_{i, i + 4}^{9} \oplus k_{i, i + 4}^{7} \oplus k_{i + 1}^{6} \oplus k_{i, i + 2, i + 4}^{5} \oplus k_{i + 3}^{4} \oplus k_{i, i + 2}^{3} \oplus k_{i + 1}^{2} \oplus k_{i}^{1} \\ P R_{i} \oplus X R_{i, i + 2, i + 4}^{20} \oplus X L_{i + 3}^{20} = k_{i + 3}^{19} \oplus k_{i, i + 2}^{18} \oplus k_{i + 1}^{17} i \oplus k_{i}^{16} \oplus k_{i}^{14} \oplus k_{i + 1}^{13} \oplus k_{i, i + 2}^{12} \oplus k_{i + 3}^{11} \\ \oplus k_{i + 2, i, i + 4}^{10} \oplus k_{i + 1, i + 5}^{9} \oplus k_{i, i + 4}^{8} \oplus k_{i, i + 4}^{6} \oplus k_{i + 1}^{5} \oplus k_{i, i + 2, i + 4}^{4} \oplus k_{i + 3}^{3} \oplus k_{i, i + 2}^{2} \oplus k_{i + 1}^{1} \oplus k_{i}^{0} \end{matrix}

(A6)

Table A4. The sequence of approximations used to derive 20-round linear trails for the left-half of Simeck 48.

Active Bits on the Left Side	Active Bits on the Right Side	Used Approximation	Number of Approximations
0	-
-	0	1	1
0	1	1	1
1	0,2	1;1	2
0,2	3	1	1
3	0,2,4	3;1;1	3
0,2,4	1	1	1
1	0,4	3;1	2
0,4			0
	0,4	3;1	2
0,4	1	1	1
1	0,2,4	3;1;1	3
0,2,4	3	1	1
3	0,2	1;1	2
0,2	1	1	1
1	0	1	1
0	-
-	0	1	1
0	1	1	1
1	0,2	1;1	2
0,2	3

Table A5. The sequence of approximations used to derive 20 rounds for the right-half of Simeck 48.

Active Bits on the Left Side	Active Bits on the Right Side	Used Approximation	Number of Approximations
-	0	1	1
0	1	1	1
1	0,2	1:1	2
0,2	3	1	1
3	0,2,4	3;1;1	3
0,2,4	1	1	1
1	0,4	3;1	2
0,4	-
-	0,4	3;1	2
0,4	1	1	1
1	0,2,4	3;1;1	3
0,2,4	3	1	1
3	0,2	1;1	2
0,2	1	1	1
1	0	1	1
0	-
-	0	1	1
0	1	1	1
1	0,2	1;1	2
0,2	3	1	1
3	0,2,4

Appendix D.2. 28-Round Linear Attacks of Simeck 48/96

We can append four rounds encryption and four rounds decryption to the 20-round linear trails, and we get a 28-round linear attack.

To determine the number of plaintext and ciphertext pairs required, we compute the capacity:

\begin{matrix} {\bar{c}}^{2} = 4 \times 24 \times 2^{- 27 \times 2} = 2^{6} \times {2^{- 27}}^{2} = 2^{- 47.42} \end{matrix}

The key bits required guessing to add four rounds of decryption to the left half approximations are:

14 bits of $k_{i}^{27}$ , for $i = 3, 8, 13, 4, 7, 18, 9, 14, 0, 5, 10, 2, 6, 12$
9 bits of the sum $k_{i, i + 2}^{27} \oplus k_{i + 1}^{26}$ for $i = 3, 8, 13, 0, 5, 2, 7, 4, 9$
2 bits of the sum $k_{i, i + 2}^{27} \oplus k_{i + 1}^{26} \oplus k_{i}^{25}$ for $i = 3, 8$

The key bits required guessing to add four rounds of decryption to the right half approximations are:

18 bits of $k_{i}^{27}$ , for $i = 0, 5, 10, 15, 1, 6, 11, 2, 7, 12, 3, 8, 17, 13, 4, 9, 14, 19$
11 bits of the last round key $k_{i}^{26}$ for $i = 0, 5, 10, 2, 7, 12, 4, 9, 14, 1, 6$
6 bits of the sum $k_{i + 1}^{26} \oplus k_{i}^{25}$ for $i = 0, 5, 2, 7, 4, 9$

The complexity to evaluate the approximations for the left half is

2^{4.585} \times 2^{47.42} \times 2^{16} \times 2^{25} = 2^{93}

. In addition to the complexity for evaluating the right half approximations which is

2^{4.585} \times 2^{47.42} \times 2^{7} \times 2^{35} = 2^{94}

. Therefore the overall time complexity to mount a 28-round linear attack is

2^{94.58}

In the case of average-case computations, the complexity to evaluate the approximations for the left half is

24 \times 2^{47.42} \times 2^{11.5} \times 2^{18} = 2^{82.5}

. In addition to the complexity for right half approximations which is

24 \times 2^{47.42} \times 2^{4.5} \times 2^{26} = 2^{83.5}

. Therefore the overall time complexity to mount a 28-round linear attack is

2^{84.08}

Appendix E. Linear Cryptanalysis of Simeck 48/96 Using Multiple Super-Rounds

Here, we extend the 13-round linear approximation Equation (19) into a 20-round approximation (A7) with bias=

2^{- 27}

(see Table A6 for detailed derivation).

\begin{matrix} P L_{i + 3} \oplus P R_{i, i + 2} \oplus X R_{i}^{20} = k_{i}^{18} \oplus k_{i + 1}^{17} \oplus k_{i, i + 2}^{16} \oplus k_{i + 3}^{15} \oplus k_{i, i + 2, i + 4}^{14} \oplus k_{i, i + 4}^{10} \oplus \\ k_{i + 1}^{9} \oplus k_{i, i + 2, i + 4}^{8} \oplus k_{i + 3}^{7} \oplus k_{i, i + 2}^{6} \oplus k_{i + 1}^{5} \oplus k_{i}^{4} \oplus k_{i}^{2} \oplus k_{i + 1}^{1} \oplus k_{i, i + 2}^{0} \end{matrix}

(A7)

28-Round and 29-Round Linear Attacks of Simeck 48/96

Here, we describe an improved linear attack of 28-round of Simeck 48/96. We append the super rounds of four rounds of encryption and four rounds of decryption to the 20-round linear approximation.

The system of approximations has the following capacity:

\begin{matrix} {\bar{c}}^{2} = 4 \times 24 \times 2^{- 27 \times 2} = 2^{6} \times {2^{- 27}}^{2} = 2^{- 47.42} \end{matrix}

The components of three super-keys, a total of 26 key bits:

Fifteen bits of the last round key $k_{i}^{0}$ for $i = 10, 5, 14, 9, 4, 8, 3, 2, 18, 13, 0, 1, 6, 7, 12$ .
Nine bits of the sum $k_{i + 1}^{0} \oplus k_{i}^{1}$ for $i = 9, 4, 13, 8, 3, 0, 5, 2, 7$ .
Two bits of the sum $k_{i, i + 2}^{0} \oplus k_{i + 1}^{1} \oplus k_{i}^{2}$ for $i = 3, 8$ .

A single bit of the output mask represents one bit of the right half; hence, we can use our super-round to add four rounds of decryption. Adding four rounds of decryption requires the estimation of 16 key bits:

Nine bits of the last round key $k_{i}^{19}$ for $i = 7, 2, 11, 6, 1, 5, 0, 15, 10$ .
Five bits of the sum $k_{i + 1}^{19} \oplus k_{i}^{18}$ for $i = 6, 1, 10, 5, 0$ .
Two bits of the sum $k_{i, i + 2}^{19} \oplus k_{i + 1}^{18} \oplus k_{i}^{17}$ for $i = 0, 5$ .

Thus, the required time complexity for this attack is

2^{4.585} \times 2^{47.42} \times 2^{26} \times 2^{16} = 2^{94.005}

In the average-case complexity, we can add one more round of decryption to the 28-round linear attack; hence, we can attack up to 29 rounds of Simeck 48/96. The cost of adding five rounds of decryption, leading to a total of 28 key bits (22 bits on average):

Twelve bits of the last round key $k_{i}^{28}$ for $i = 0, 5, 10, 1, 6, 15, 11, 2, 7, 16, 12, 20$ , with each counted as a half bit.
Nine bits of the sum $k_{i + 1}^{28} \oplus k_{i}^{27}$ for $i = 7, 2, 11, 6, 1, 5, 0, 15, 10$ .
Five bits of the sum $k_{i, i + 2}^{28} \oplus k_{i + 1}^{27} \oplus k_{i}^{26}$ for $i = 6, 1, 10, 5, 0$ .
Two bits of the sum $k_{i + 3}^{28} \oplus k_{i, i + 2}^{27} \oplus k_{i + 1}^{26} \oplus k_{i}^{25}$ for $s i = 0, 5$ .

The cost of appending four rounds of encryption was, on average, reduced to the estimation of 18.5 key bits.

Table A6. The sequence of approximations used to derive 20 rounds of linear trails of Simeck 48.

Active Bits in the Left Side	Active Bits in the Right Side	Used Approximation	Number of Approximations
3	0, 2	1:1	2
0,2	1	1	1
1	0	1	1
0	-
0	1	1	1
	0	1	1
1	0,2	1;1	2
0,2	3	1	1
3	0,2,4	1;1;1	3
0,2,4	1	1	1
1	0,4	1;1	2
0,4	-
	0.4	1;1	2
0,4	1	1	1
1	0,2,4	3;1;1	3
0,2,4	3	1	1
3	0,2	1;1	2
0,2	1	1	1
1	0	1	1
0	-
-	0

Appendix F. Linear Cryptanalysis of Simeck 64/128 Using a Single Super-Round

Here, we present a 33-round linear attack of Simeck 64/128.

Appendix F.1. Linear Approximations for Simeck 64/128

We extend the 20-round linear expressions Equation (A8) into 25-round linear trails for the left and right half with biases

2^{- 34}

and

2^{- 36}

, respectively (see Table A7 and Table A8 for details):

\begin{matrix} P L_{i} \oplus X R_{i, i + 4}^{25} \oplus k_{i, i + 4}^{23} \oplus k_{i + 1}^{22} \oplus k_{i + 4, i, i + 2}^{21} \oplus k_{i + 3}^{20} \oplus k_{i, i + 2}^{19} \oplus k_{i + 1}^{18} \oplus k_{i}^{17} \oplus k_{i}^{15} \oplus k_{i + 1}^{14} \\ \oplus k_{i, i + 2}^{13} \oplus k_{i + 3}^{12} \oplus k_{i, i + 4, i + 2}^{11} \oplus k_{i + 1, i + 5}^{10} \oplus k_{i, i + 4}^{9} \oplus k_{i, i + 4}^{7} \oplus k_{i + 1}^{6} \oplus k_{i, i + 2, i + 4}^{5} \oplus k_{i + 3}^{4} \oplus k_{i, i + 2}^{3} \\ \oplus k_{i + 1}^{2} \oplus k_{i}^{1} \\ P R_{i} \oplus X R_{i + 1, i + 5}^{25} \oplus X L_{i, i + 4}^{25} \oplus k_{i, i + 4}^{24} \oplus k_{i, i + 4}^{22} \oplus k_{i + 1}^{21} \oplus k_{i, i + 2, i + 4}^{20} \oplus k^{19} \oplus k_{i, i + 2}^{18} \oplus k_{i + 1}^{17} \\ \oplus k_{i}^{16} \oplus k_{i}^{14} \oplus k_{i + 1}^{13} \oplus k_{i, i + 2}^{12} \oplus k_{i + 3}^{11} \oplus k_{i + 2, i, i + 4}^{10} \oplus k_{i + 1, i + 5}^{9} \oplus k_{i, i + 4}^{8} \oplus k_{i, i + 4}^{6} \oplus k_{i + 1}^{5} \\ \oplus k_{i, i + 2, i + 4}^{4} \oplus k_{i + 3}^{3} \oplus k_{i, i + 2}^{2} \oplus k_{i + 1}^{1} \oplus k_{i}^{0} \end{matrix}

(A8)

Table A7. The sequence of approximations used to derive 25-round linear trails for the left half of Simeck 64.

Active Bits in the Left Side	Active Bits in the Right Side	Used Approximation	Number of Approximations
0	-
-	0	1	1
0	1	1	1
1	0,2	1;1	2
0,2	3	1	1
3	0,2,4	3;1;1	3
0,2,4	1	1	1
1	0,4	3;1	2
0,4			0
	0,4	3;1	2
0,4	1	1	1
1	0,2,4	3;1;1	3
0,2,4	3	1	1
3	0,2	1;1	2
0,2	1	1	1
1	0	1	1
0	-
-	0	1	1
0	1	1	1
1	0,2	1;1	2
0,2	3	1	1
3	0,2,4	1;1;1	3
0,2,4	1	1	1
1	0,4	1;1	2
0,4	-
	0,4

Table A8. The sequence of approximations used to derive 25 rounds for the right half of Simeck 64.

Active Bits on the Left Side	Active Bits on the Right Side	Used Approximation	Number of Approximations
-	0	1	1
0	1	1	1
1	0,2	1:1	2
0,2	3	1	1
3	0,2,4	3;1;1	3
0,2,4	1	1	1
1	0,4	3;1	2
0,4	-
-	0,4	3;1	2
0,4	1	1	1
1	0,2,4	3;1;1	3
0,2,4	3	1	1
3	0,2	1;1	2
0,2	1	1	1
1	0	1	1
0	-
-	0	1	1
0	1	1	1
1	0,2	1;1	2
0,2	3	1	1
3	0,2,4	1;1;1	3
0,2,4	1	1	1
1	0,4	1;3	2
0,4	-
-	0,4	1;1	2
0,4	1,5

Appendix F.2. 34-Round Linear Attacks of Simeck 64/128

We produce a 34-round linear cryptanalysis by appending four rounds of encryption and five rounds of decryption to the 25-round linear approximations, as follows:

The capacity of the 25-round linear trail is:

\begin{matrix} {\bar{c}}^{2} = 4 \times 32 \times 2^{- 34 \times 2} = 2^{6} \times {2^{- 34}}^{2} = 2^{- 61} \end{matrix}

Forty-three key bits must be estimated to add five rounds of decryption to the left-half approximations:

Eighteen bits of $k_{i}^{33}$ for $i = 0, 5, 10, 1, 6, 11, 2, 7, 20, 16, 12, 4, 9, 14, 19, 24, 3, 8$ .
Thirteen bits of the last round key $k_{i}^{32}$ for $i = 0, 3, 10, 1, 6, 15, 11, 4, 9, 14, 5, 19, 2$ .
Eight bits of the sum $k_{i + 1}^{32} \oplus k_{i}^{31}$ for $i = 6, 1, 10, 5, 0, 14, 9, 4$ .
Four bits of the sum $k_{i, i + 2}^{32} \oplus k_{i + 1}^{31} \oplus k_{i}^{30}$ for $i = 0, 5, 9, 4$ .

Fifty-three key bits must be estimated to add five rounds of decryption to the right-half approximations:

Twenty-one bits of $k_{i}^{33}$ for $i = 15, 20, 10, 5, 6, 11, 2, 7, 1, 12, 8, 13, 4, 9, 14, 19, 16, 21, 3, 17, 0$ .
Seventeen bits of the last round key $k_{i}^{32}$ for $i = 1, 6, 11, 2, 7, 16, 12, 5, 10, 15, 20, 0, 4, 9, 14, 3, 8$ .
Eleven bits of the sum $k_{i + 1}^{32} \oplus k_{i}^{31}$ for $i = 7, 2, 11, 6, 1, 15, 10, 5, 0, 4, 9$ .
Four bits of the sum $k_{i, i + 2}^{32} \oplus k_{i + 1}^{31} \oplus k_{i}^{30}$ for $i = 6, 1, 10, 5$ .

Thus, the time complexity required to evaluate the left-half approximations is

2^{5} \times 2^{16} \times 2^{43} \times 2^{61} = 2^{125}

, in addition to the complexity required to evaluate the right-half approximations, which is

2^{5} \times 2^{7} \times 2^{53} \times 2^{61} = 2^{126}

. The overall time complexity is

2^{126.5}

In the case of average time computations, we can reduce the complexity of the 34-round linear attack and count some bits as a half bit. Thus, the time complexity required to evaluate the left-half approximations reduced to

2^{5} \times 2^{11.5} \times 2^{34} \times 2^{61} = 2^{111.5}

. Additionally, evaluating the right-half approximations requires the estimation of 53 key bits, on average, which reduced to 43; hence, the time complexity required to evaluate the right-half approximations is

2^{5} \times 2^{4.5} \times 2^{40.5} \times 2^{61} = 2^{112}

. The total complexity required to evaluate the two halves is

2^{112}

Appendix G. Linear Cryptanalysis of Simeck 64/128 Using Multiple Super Rounds

In this section, we apply the attack model using multiple super rounds.

Appendix G.1. Improved Linear Approximation for Simeck 64/128

We extended the 20-round linear approximation (A7) into a 25-round linear approximation (A9) with bias=

2^{- 35}

(see Table A9 for derivation).

\begin{matrix} P L_{i + 3} \oplus P R_{i, i + 2} \oplus X R_{i + 1}^{25} \oplus X L_{i, i + 2, i + 4}^{25} = k_{i, i + 2, i + 4}^{24} \oplus k_{i + 3}^{23} \oplus k_{i, i + 2}^{22} \oplus X R_{i + 1}^{23} \oplus k_{i}^{20} \oplus k_{i}^{18} \\ \oplus k_{i + 1}^{17} \oplus k_{i, i + 2}^{16} \oplus k_{i + 3}^{15} \oplus k_{i, i + 2, i + 4}^{14} \oplus k_{i, i + 4}^{10} \oplus k_{i + 1}^{9} \oplus k_{i, i + 2, i + 4}^{8} \oplus k_{i + 3}^{7} \oplus k_{i, i + 2}^{6} \oplus k_{i + 1}^{5} \\ \oplus k_{i}^{4} \oplus k_{i}^{2} \oplus k_{i + 1}^{1} \oplus k_{i, i + 2}^{0} \end{matrix}

(A9)

Appendix G.2. 33-Round and 34-Round Linear Attacks of Simeck 64/128 Using Multiple Super-Rounds

We extended the 25-round linear trail (A9), and added four rounds of encryption and four rounds of decryption; hence we could attack up to 33 rounds of Simeck 64/128.

The capacity of the 25-round linear trail is:

\begin{matrix} {\bar{c}}^{2} = 4 \times 32 \times 2^{- 35 \times 2} = 2^{7} \times {2^{- 35}}^{2} = 2^{- 63} \end{matrix}

Thus, the required data complexity is

2^{63}

To obtain the components of three super-keys, leading to a total of 26 key bits, four rounds of encryption must be added:

Fourteen bits of the last round key $k_{i}^{0}$ for $i = 10, 5, 14, 9, 4, 8, 3, 2, 18, 13, 0, 1, 6, 7, 12$ , with each counted as a half bit.
Nine bits of the sum $k_{i + 1}^{0} \oplus k_{i}^{1}$ for $i = 9, 4, 13, 8, 3, 0, 5, 2, 7$ .
Two bits of the sum $k_{i, i + 2}^{0} \oplus k_{i + 1}^{1} \oplus k_{i}^{2}$ for $i = 3, 8$ .

The cost of adding four rounds of decryption, leading to a total of 22 key bits, is as follows:

Thirteen bits of the last round key $k_{i}^{32}$ for $i = 7, 2, 11, 6, 1, 5, 0, 15, 10, 14, 3, 4, 9$ .
Seven bits of the sum $k_{i + 1}^{32} \oplus k_{i}^{31}$ for $i = 1, 6, 11, 0, 5, 4, 9$ .
Two bits of the sum $k_{i, i + 2}^{32} \oplus k_{i + 1}^{31} \oplus k_{i}^{30}$ for $i = 1, 6$ .

The time complexity for this attack is

2^{5} \times 2^{63} \times 2^{25} \times 2^{22} = 2^{115}

In the average-case complexity, we extend the 33-round attack by one more round and present a 34-round linear attack. Thus, we added five rounds of decryption. Five rounds of decryption were added, leading to a total of 39 key bits (30.5 bits on average):

Seventeen bits of the last round key $k_{i}^{33}$ for $i = 1, 6, 11, 16, 2, 7, 12, 21, 17, 0, 5, 10, 15, 4, 9, 14, 19$ , with each counted as a half bit.
Thirteen bits of the sum $k_{i + 1}^{33} \oplus k_{i}^{32}$ for $i = 7, 2, 11, 6, 1, 5, 0, 15, 10, 14, 3, 4, 9$ .
Seven bits of the sum $k_{i, i + 2}^{33} \oplus k_{i + 1}^{32} \oplus k_{i}^{30}$ for $i = 1, 6, 11, 0, 5, 4, 9$ .
Two bits of the sum $k_{i + 3}^{33} \oplus k_{i, i + 2}^{32} \oplus k_{i + 1}^{31} \oplus k_{i}^{30}$ for $s i = 1, 6$ .

The average time complexity required for this attack is

2^{5} \times 2^{63} \times 2^{18} \times 2^{30.5} = 2^{116.5}

Table A9. The sequence of approximations used to derive 25-round linear trails of Simeck 64.

Active Bits in the Left Side	Active Bits in the Right Side	Used Approximation	Number of Approximations
3	0, 2	1:1	2
0,2	1	1	1
1	0	1	1
0	-
0	1	1	1
	0	1	1
1	0,2	1;1	2
0,2	3	1	1
3	0,2,4	1;1;1	3
0,2,4	1	1	1
1	0,4	1;1	2
0,4	-
	0.4	1;1	2
0,4	1	1	1
1	0,2,4	3;1;1	3
0,2,4	3	1	1
3	0,2	1;1	2
0,2	1	1	1
1	0	1	1
0	-
-	0	1	1
0	1	1	1
1	0,2	1;1	2
0,2	3	1	1
3	0,2,4	3;1;1	3
0,2,4	1

References

Almukhlifi, R.; Vora, P. Linear Cryptanalysis of Reduced-Round Simon Using Super Rounds. Cryptography 2020, 4, 9. [Google Scholar] [CrossRef]
Bagheri, N. Linear Cryptanalysis of Reduced-Round SIMECK Variants. In Proceedings of the Progress in Cryptology—INDOCRYPT 2015—16th International Conference On Cryptology In India, Bangalore, India, 6–9 December 2015; Volume 9462, pp. 140–152. [Google Scholar] [CrossRef]
Biryukov, A.; Cannière, C.; Quisquater, M. On Multiple Linear Approximations. In Proceedings of the Advances in Cryptology—CRYPTO 2004, 24th Annual International Cryptology Conference, Santa Barbara, CA, USA, 15–19 August 2004; Volume 3152, pp. 1–22. [Google Scholar] [CrossRef]
Yang, G.; Zhu, B.; Suder, V.; Aagaard, M.; Gong, G. The Simeck Family of Lightweight Block Ciphers. In Proceedings of the Cryptographic Hardware and Embedded Systems—CHES 2015—17th International Workshop, Saint-Malo, France, 13–16 September 2015; Volume 9293, pp. 307–329. [Google Scholar] [CrossRef]
Kölbl, S.; Roy, A. A Brief Comparison of Simon and Simeck. In Proceedings of the Lightweight Cryptography for Security And Privacy—5th International Workshop, LightSec 2016, Aksaray, Turkey, 21–22 September 2016; Volume 10098, pp. 69–88. [Google Scholar] [CrossRef]
Qiao, K.; Hu, L.; Sun, S. Differential Security Evaluation of Simeck with Dynamic Key-guessing Techniques. In Proceedings of the 2nd International Conference on Information Systems Security and Privacy, ICISSP 2016, Rome, Italy, 19–21 February 2016; pp. 74–84. [Google Scholar] [CrossRef]
Qin, L.; Chen, H.; Wang, X. Linear Hull Attack on Round-Reduced Simeck with Dynamic Key-Guessing Techniques. In Proceedings of the Information Security And Privacy—21st Australasian Conference, ACISP 2016, Proceedings, Part II, Melbourne, VIC, Australia, 4–6 July 2016; Volume 9723, pp. 409–424. [Google Scholar] [CrossRef]
Bogdanov, A.; Rijmen, V. Linear hulls with correlation zero and linear cryptanalysis of block ciphers. Des. Codes Cryptogr. 2014, 70, 369–383. [Google Scholar] [CrossRef]
Zhang, K.; Guan, J.; Hu, B.; Lin, D. Security evaluation on Simeck against zero-correlation linear cryptanalysis. IET Inf. Secur. 2018, 12, 87–93. [Google Scholar] [CrossRef]
Sadeghi, S.; Bagheri, N. Improved zero-correlation and impossible differential cryptanalysis of reduced-round SIMECK block cipher. IET Inf. Secur. 2018, 12, 314–325. [Google Scholar] [CrossRef]
Li, H.; Ren, J.; Chen, S. Improved Integral Attack on Reduced-Round Simeck. IEEE Access 2019, 7, 118806–118814. [Google Scholar] [CrossRef]
Nalla, V.; Sahu, R.; Saraswat, V. Differential Fault Attack on SIMECK. In Proceedings of the Third Workshop on Cryptography and Security in Computing Systems, CS2@HiPEAC, Prague, Czech Republic, 20 January 2016; pp. 45–48. [Google Scholar] [CrossRef]
Le, D.; Lu, R.; Ghorbani, A. Improved fault analysis on SIMECK ciphers. J. Cryptogr. Eng. 2022, 12, 169–180. [Google Scholar] [CrossRef]
Dofe, J.; Frey, J.; Pahlevanzadeh, H.; Yu, Q. Strengthening SIMON Implementation Against Intelligent Fault Attacks. IEEE Embed. Syst. Lett. 2015, 7, 113–116. [Google Scholar] [CrossRef]
Benjamin, A.; Herzoff, J.; Babinkostova, L.; Serra, E. Deep Learning Based Side Channel Attacks on Lightweight Cryptography (Student Abstract). In Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, the Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022, Virtual Event, 22 February–1 March 2022; pp. 12911–12912. [Google Scholar]
Wu, C.; Zhang, H.; Xu, J.; Sun, S. Side Channel Attack of Lightweight Block Cipher Simeck Based on Deep Learning. In Proceedings of the 2019 IEEE 6th International Symposium on Electromagnetic Compatibility (ISEMC), Nanjing, China, 1–4 November 2019; pp. 1–5. [Google Scholar]
Baksi, A.; Breier, J.; Dasu, V.; Dong, X.; Yi, C. Following-up on Machine Learning Assisted Differential Distinguishers. (SILC Workshop, 2020). Available online: https://www.esat.kuleuven.be/cosic/events/silc2020/wp-content/uploads/sites/4/2020/10/Submission4.pdf (accessed on 24 January 2023).
Baksi, A.; Breier, J.; Chen, Y.; Dong, X. Machine Learning Assisted Differential Distinguishers For Lightweight Ciphers. In Proceedings of the Design, Automation & Test in Europe Conference & Exhibition, DATE 2021, Grenoble, France, 1–5 February 2021; pp. 176–181. [Google Scholar] [CrossRef]
Tian, J.; Wu, B.; Wang, Z. High-Speed FPGA Implementation of SIKE Based on an Ultra-Low-Latency Modular Multiplier. IEEE Trans. Circuits Syst. I Regul. Pap. 2021, 68, 3719–3731. [Google Scholar] [CrossRef]
Nyberg, K. Linear Approximation of Block Ciphers. In Proceedings of the Advances in Cryptology—EUROCRYPT’94, Workshop on the Theory and Application of Cryptographic Techniques, Perugia, Italy, 9–12 May 1994; Volume 950, pp. 439–444. [Google Scholar] [CrossRef]
Matsui, M. Linear Cryptanalysis Method for DES Cipher. In Proceedings of the Advances in Cryptology—EUROCRYPT’93, Workshop on the Theory And Application of Cryptographic Techniques, Lofthus, Norway, 23–27 May 1993; Volume 765, pp. 386–397. [Google Scholar] [CrossRef]

Figure 1. Simeck round function.

Figure 2. General form of linear attack with super rounds.

Figure 3. The super rounds.

Figure 4. 8-Round Linear Attack.

Figure 5. 10-Round Linear Attack.

Figure 6. 12-Round Linear Attack.

Figure 7. 8-Round attack without approximations.

Table 1. Comparison of previous results using Matsui’s second algorithm and multiple linear cryptanalysis (without recourse to linear hull) on Simeck.

Average-Case Computations
Simeck	Number of Rounds	Data Complexity	Time Complexity	Presented in
32/64	20-round	$2^{30}$	$2^{61.56}$	Section 7.1
	20-round	$2^{30}$	$2^{58.5}$	Section 7.3
	18-round	$2^{24}$	$2^{61.5}$	Bagheri [2]
48/96	28-round	$2^{47.42}$	$2^{84.08}$	Appendix D
	29-round	$2^{47.42}$	$2^{92.505}$	Appendix E
	23-round	$2^{41.42}$	$2^{95}$	Bagheri [2]
64/128	34-round	$2^{61}$	$2^{112}$	Appendix F
	34-round	$2^{63}$	$2^{116.5}$	Appendix G
	27-round	$2^{49}$	$2^{104}$	Bagheri [2]

Table 2. Comparison of previous results using Matsui’s second algorithm and multiple linear cryptanalysis (without recourse to linear hull) on Simeck.

Worst-Case Computations
Simeck	Number of Rounds	Data Complexity	Time Complexity	Presented in
32/64	19-round	$2^{30}$	$2^{59.02}$	Section 7.1
	19-round	$2^{30}$	$2^{61}$	Section 7.3
	18-round	$2^{24}$	$2^{72}$	Bagheri [2]
48/96	2-round	$2^{47.42}$	$2^{94.58}$	Appendix D
	28-round	$2^{47.42}$	$2^{94.005}$	Appendix E
	23-round	$2^{41.42}$	$2^{108}$	Bagheri [2]
64/128	34-round	$2^{61}$	$2^{126.5}$	Appendix F
	33-round	$2^{63}$	$2^{115}$	Appendix G
	27-round	$2^{53}$	$2^{134}$	Bagheri [2]

Table 3. Simeck parameters.

Block Size $2 n$	Key Size $mn$	Word Size n	Key Words m	Number of Rounds
Simeck 32	64	16	4	32
Simeck 48	96	24	4	36
Simeck 64	128	32	4	44

Table 4. Superkeys.

Super Key of the Left Half	Super Key of the Right Half
$k_{i}^{0} \oplus k_{i + 2}^{0} \oplus k_{i + 1}^{1} \oplus k_{i}^{2}$	$k_{i + 1}^{0} \oplus k_{i}^{1}$
$k_{i + 5}^{0} \oplus k_{i + 7}^{0} \oplus k_{i + 6}^{1} \oplus k_{i + 5}^{2}$	$k_{i + 6}^{0} \oplus k_{i + 5}^{1}$
$k_{i + 1}^{0} \oplus k_{i}^{1}$	$k_{i}^{0}$
$k_{i + 6}^{0} \oplus k_{i + 5}^{1}$	$k_{i + 1}^{0}$
$k_{i + 11}^{0} \oplus k_{i + 10}^{1}$	$k_{i + 6}^{0}$
$k_{i + 2}^{0} \oplus k_{i + 1}^{1}$	$k_{i + 5}^{0}$
$k_{i + 7}^{0} \oplus k_{i + 6}^{1}$	$k_{i + 10}^{0}$
$k_{i + 1}^{0}$
$k_{i}^{0}$
$k_{i + 2}^{0}$
$k_{i + 5}^{0}$
$k_{i + 6}^{0}$
$k_{i + 7}^{0}$
$k_{i + 10}^{0}$
$k_{i + 11}^{0}$
$k_{i + 15}^{0}$

Table 5. Comparison of 8-round attack results using the left half only and using both halves.

		Bits Correctly	Number of
Number of Rounds	Super Key Bits Estimated	Guessed	Experiments
		(Out of 16 Bits)	(Out of 14)
8-round (left half)	$B i t 1$	16	14
	$B i t 2$	16	10
	average number of bits guessed correctly = 15.7	15	4
		15	3
	$B i t 3$	14	2
	$B i t 3$	13	2
	average number of bits guessed correctly = 12.6	12	2
		11	3
		10	2
8-round (left and right halves)	$B i t 1$	16	14
	$B i t 2$	16	10
		15	3
	average number of bits guessed correctly = 15.6	14	1
		15	3
	$B i t 3$	14	2
	$B i t 3$	13	3
	average number of bits guessed correctly = 12.7	12	2
		11	2
		10	2

Table 6. Comparison of 10-round attack results using the left half only and using both halves.

		Bits Correctly	No. of
Number of Rounds	Super Key Bits Estimated	Guessed	Experiments
		(Out of 16 Bits)	(Out of 14)
10-round (left half)	$B i t 1$	16	14
	$B i t 2$	16	10
	average no. bits guessed correctly = 15.7	15	4
	$B i t 3$ average no. bits guessed correctly = 12.6	16	2
		14	4
		13	1
		11	5
		10	2
	$B i t 4$ average no. bits guessed correctly = 13	16	1
		15	1
		14	3
		13	4
		12	3
		11	2
10-round (left and right halves)	$B i t 1$	16	14
	$B i t 2$ average no. bits guessed correctly =15.7	16	11
		15	2
		14	1
	$B i t 3$ average no. bits guessed correctly = 12.6	16	2
		14	4
		13	1
		11	5
		10	2
	$B i t 4$ average no. bits guessed correctly = 15.5	16	9
		15	3
		14	2

Table 7. Comparison of 12-round attack results using the left half only and using both halves.

		Bits Correctly	No. of
Number of Rounds	Super Key Bits Estimated	Guessed	Experiments
		(Out of 16 Bits)	(Out of 3)
	$B i t 1$	16	3
12-round	$B i t 2$	16	3
(left half)	$B i t 3$	15	1
	average no. bits guessed correctly = 14.3	14	2
	$B i t 1$	16	3
12-round	$B i t 2$	16	3
(left and right halves)	$B i t 3$	15	1
	average no. bits guessed correctly = 14.3	14	2

Table 8. Summary of the experimental results.

Experimental	Super Key Bits	Master Key Bits	Data	Time	Success
Results	Recovered	Recovered	Complexity	Complexity	Probability
8-round	46–48 bits	46–48 bits	$2^{14}$	$2^{34.0028}$	$93 %$
10-round	62–64 bits	56–62 bits	$2^{14}$	$2^{36.044}$	$93.4 %$
12-round	46–48 bits	46–48 bits	$2^{24}$	$2^{44.0028}$	$96.45 %$
8-round without	112 bits	64 bits	$2^{5.58}$	$2^{30.58}$	$100 %$
approximations

Table 9. Comparison results on Simeck 32.

Average Case Computations
Simeck	Number of Rounds	Data Complexity	Time Complexity
32/64	Using Single Super Round Presented in Section 7.1
	20-round	$2^{30}$	$2^{61.56}$
	Using Multiple Super Rounds Presented in Section 7.3
	20-round	$2^{30}$	$2^{58.5}$
	Projections from data in [2]
	18-round	$2^{24}$	$2^{60.5}$

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

© 2023 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Almukhlifi, R.; Vora, P.L. Linear Cryptanalysis of Reduced-Round Simeck Using Super Rounds. Cryptography 2023, 7, 8. https://doi.org/10.3390/cryptography7010008

AMA Style

Almukhlifi R, Vora PL. Linear Cryptanalysis of Reduced-Round Simeck Using Super Rounds. Cryptography. 2023; 7(1):8. https://doi.org/10.3390/cryptography7010008

Chicago/Turabian Style

Almukhlifi, Reham, and Poorvi L. Vora. 2023. "Linear Cryptanalysis of Reduced-Round Simeck Using Super Rounds" Cryptography 7, no. 1: 8. https://doi.org/10.3390/cryptography7010008

APA Style

Almukhlifi, R., & Vora, P. L. (2023). Linear Cryptanalysis of Reduced-Round Simeck Using Super Rounds. Cryptography, 7(1), 8. https://doi.org/10.3390/cryptography7010008

Article Menu

Linear Cryptanalysis of Reduced-Round Simeck Using Super Rounds

Abstract

1. Introduction

1.1. Our Contributions

1.2. Comparison with Other Work

2. Simeck

2.1. Notations

2.2. Description of Simeck

3. Related Work

4. Super Rounds and Super Keys for Simeck

4.1. The Construction of Super Rounds and Derivations of Super Keys

4.2. The Super Key

5. Linear Approximations for Simeck 32/64

5.1. 8-Round Attack

5.2. 10-Round Attack

5.3. 12-Round Attack

6. Experimental Verification

6.1. 8-Round Key Recovery Attack

6.2. 10-Round Key Recovery Attack

6.3. 12-Round Key Recovery Attack

6.4. Experimental Results of 8-Round Attack without Approximations

6.5. Summary of Experimental Results

7. Projected Results Using Multiple Linear Cryptanalysis

7.1. Linear Attacks Using a Single Super-Round

7.2. Improved Linear Approximations for Simeck 32/64

7.3. Linear Attacks Using Multiple Super Rounds

8. The Effect of Super Rounds on Larger Variants of Simeck

9. Discussion

10. Conclusions and Future Work

Author Contributions

Funding

Conflicts of Interest

Appendix A. The Deduction of k 3 from k 9

Appendix B. Derive 13-Round Linear Approximations for Simeck 32/64

Appendix C. Derive an Improved 13-Round Linear Approximations for Simeck 32/64

Appendix D. Linear Cryptanalysis of Simeck 48/96 Using a Single Super Round

Appendix D.1. Linear Approximations for Simeck 48/96

Appendix D.2. 28-Round Linear Attacks of Simeck 48/96

Appendix E. Linear Cryptanalysis of Simeck 48/96 Using Multiple Super-Rounds

28-Round and 29-Round Linear Attacks of Simeck 48/96

Appendix F. Linear Cryptanalysis of Simeck 64/128 Using a Single Super-Round

Appendix F.1. Linear Approximations for Simeck 64/128

Appendix F.2. 34-Round Linear Attacks of Simeck 64/128

Appendix G. Linear Cryptanalysis of Simeck 64/128 Using Multiple Super Rounds

Appendix G.1. Improved Linear Approximation for Simeck 64/128

Appendix G.2. 33-Round and 34-Round Linear Attacks of Simeck 64/128 Using Multiple Super-Rounds

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI