# Rotational-XOR Rectangle Cryptanalysis on Round-Reduced Simon

Authors: Bonwook Koo; Younghoon Jung; Woo-Hwan Kim
Journal: Security and Communication Networks
 (2020)

---

## Abstract

Recently, Ashur and Liu introduced theRotational-XOR-difference approach which is a modification of rotational cryptanalysis, for an ARX cipher Speck (Ashur and Liu, 2016). In this paper, we apply the Rotational-XOR-difference (RXD) approach to a non-ARX cipher Simon and evaluate its security. First, we studied how to calculate the probability of an RXD for bitwise AND operation that the round function of Simon is based on unlike Speck is on modular addition. Next, we prove that two RXD trails can be connected such that it becomes possible to construct a boomerang/rectangle distinguisher similar to the case using differential characteristics. Finally, we construct related-key rectangle distinguishers for round-reduced versions of Simon with block lengths of 32, 48, and 64, and we suggest a five- or six-round key recovery attack. To our knowledge, it is the first attempt to apply the notion of rotational cryptanalysis for a non-ARX cipher. Although our attack does not show the best results for Simon thus far, the attempt here to define and apply a new cryptanalytic characteristic is meaningful, and we expect further improvements and applications to other ciphers to be made in subsequent studies.


---

## Body

## 1. Introduction

In a cryptosystem for confidentiality, the block cipher is a necessary building block for core functionality. So, because the security of block ciphers affects the applicability of the algorithm and the usability of the cryptosystem which uses the cipher as well, the security of a block cipher should be evaluated comprehensively and precisely. Over the last decade, many researchers have studied various techniques by which to design outstanding lightweight ciphers. One notable result of such research stream is design paradigm is omitting S-box, such as ARX. ARX is a design methodology for secret key primitives which uses only modular Addition, Rotation, and eXclusive OR operations. A number of outperforming lightweight block ciphers, such as Threefish [1], Chaskey Cipher [2], HIGHT [3], Speck [4], LEA [5], and Sparx [6] are designed in this framework. Another design strategy is to use the bitwise AND operation for nonlinear part of an algorithm. Although this approach is somewhat less popular than ARX, outstanding hardware-oriented ciphers such as KATAN/KTANTAN [7], Simon [4], and Simeck [8] utilize this strategy.Rotational cryptanalysis was initially proposed to attack the block cipher Threefish, which is an internal permutation of the hash function Skein [9]. It was combined with the notion of a rebound attack considering the results of the best attack against Skein. Subsequently, the rotational probability was recalculated [10] considering the failure of the Markov assumption of chained modular additions, and a new calculating algorithm was applied to correct the results on BLAKE2 and to provide valid results on simplified Skein. Nevertheless, it appears to be difficult to apply rotational cryptanalysis to ciphers in which constant XOR is used for the enciphering procedure. This problem has remained unsolved until the following result is presented.Recently, Ashur and Liu proposed a new type of rotational cryptanalysis that can overcome the aforementioned disadvantage by injecting constants into states [11]. This new approach can be used to evaluate the security of ciphers with constant XOR in their encryption scheme. Therefore, they applied it to the block cipher Speck-32/64 and successfully constructed a seven-round distinguisher. To do this, they introduced the notion of the Rotational-XOR (RX) pair x⊕a1,x⋘γ⊕a2 and the associated rotational-XOR-differences (RXD) a1,a2,γ, where x is a random variable and a1anda2 are constants. In particular, they presented a closed formula for calculating the RX probability occurred upon a modular addition.In the present paper, we attempt to apply Ashur’s constant injecting approach to a non-ARX cipher Simon which is based on the bitwise AND operation. While Ashur and Liu demonstrated how to calculate the RX probability and how to propagate an RX pair through the modular addition, we present a closed formula for calculating the probability and propagation rule of an RX pair through a bitwise AND operation. We also find that the propagation of the RX pair due to the operations used in Simon is similar to those of the ordinary differential characteristics and we show that the probability of boomerang/rectangle characteristics using RXD can be calculated similarly to the boomerang/rectangle characteristic using the ordinary differential characteristics. Therefore, we can construct boomerang/rectangle characteristics using two RXD trails. We refer to this cryptanalysis with such characteristics asRotational-XOR boomerang (or rectangle) cryptanalysis. Our attack works in the related-key model in which the attacker uses ciphertexts encrypted with different but related keys because rotational cryptanalysis is naturally a related-key attack.Based on our results, we evaluate the security of several instances of Simon in the related-key model. Because our approach is more effective on ciphers with smaller block sizes, we apply it to Simon with a block length of less than or equal to 64. As a result, for some parameters, we could obtain results very close to the best results on Simon thus far. Table1 shows the results of our attacks compared to the results of other attacks.Table 1
Comparison of attack results on Simon.
Block/keyAttacksRoundsDataComputationReference32/64Differential22/32232257.9[12]Linear hull23/32231.19261.84[13]Impossible20/32232245.5[14]Zero correlation21/32232259.4[15]Correlated sequence27/323262.94[16]Related-key linear23/32246.3246.65[17]Related-key RX rectangle22/32230.5260.4This paper48/72Linear hull24/36247.92267.89[13]Zero correlation21/36248261.9[15]Related-key RX rectangle21/36247269.1This paper48/96Differential24/3624878.99[12]Linear hull25/36247.92289.89[13]Zero correlation22/36248280.5[15]Related-key linear28/36270.9271.07[17]Related-key RX rectangle24/36246.5292.3This paper64/96Differential29/4226386.94[12]Linear hull30/42263.53293.62[13]Zero correlation23/42264290.4[15]Related-key RX rectangle22/42262291.8This paper64/128Differential30/44263110.99[12]Linear hull31/44263.532120[13]Zero correlation24/442642116.8[15]Related-key linear34/44295.32295.5[17]Related-key RX rectangle25/44261.52123.0This paperAlthough our results are not the best records for Simon, our approach can be adopted to analyze other existing or future ciphers based on the bitwise AND. Examples include Simeck and KATAN/KTANTAN.The rest of this paper is organized as follows: in Section2, we define some of the notations used here and give brief introductions of rotational cryptanalysis, the rotational-XOR-difference, and boomerang/rectangle cryptanalysis. The RX probability and RX characteristics of Simon are described in Section 3. In Section 4, we present the RX rectangle attack on Simon, including the key recovery phase, and calculate the computational and data complexities of the attacks. Finally, Section 5 concludes the paper.


## 2. Preliminaries

### 2.1. Notations

In this paper, we use the following notations:(i)
wHx: Hamming weight of bit string x(ii)
x⊞y: modular addition of bit strings x and y(iii)
x∨y: bitwise OR of bit strings x and y(iv)
x∧y: bitwise AND of bit strings x and y(v)
x≪r: r bit left shift of a bit string x(vi)
x<r, x⋘r: r bit left rotation (cyclic shift) of a bit string x(vii)
x>r: r bit right rotation (cyclic shift) of a bit string x(viii)
x⟶: left rotation (cyclic shift) of a bit string x by a predefined γ, usually γ=1(ix)
x←: right rotation (cyclic shift) of a bit string x by a predefined γ, usually γ=1(x)
xi: i-th bit of a bit string x(xi)
x≺¯y means that every bit in y is larger or equal to the corresponding bit in x


### 2.2. Rotational Cryptanalysis

Since Khovratovich et al. introduced rotational cryptanalysis in 2010 [9], it has been used to evaluate symmetric key cryptographic primitives based on the ARX design framework [10, 18, 19]. Rotational cryptanalysis appears to be suitable for ARX ciphers because the rotational pair is preserved through rotations and XORes between variables and transformed by modular additions with high probability levels, unlike ciphers based on S-boxes.Rotational cryptanalysis exploits the nonrandom behavior of ciphertext pairs generated from the rotational plaintext pairsp0,p1,...,pm−1,p0⟶,p1⟶,...,pm−1⟶ where pi⟶=pi⋘γ for some integer γ (γ is typically selected to 1 for a higher probability). The probability that modular addition of two rotational pairs x,x⟶ and y,y⟶ is also a rotational pair is given by(1)Px⊞y⟶=x⟶⊞y⟶=141+2γ−n+2−γ+2−n,where n is the bit length of both x and y [20]. For a large n, that probability goes to 2−1.415 when γ=1 and to 2−2 when γ=n/2.However, XOR or modular addition with a constant destroys the rotational relationship of a pair when the constant cannot transform into itself byγ-bit rotation. So, the rotational cryptanalysis cannot be widely adopted in relation to the block cipher analysis.


### 2.3. Rotational-XOR-Difference

In 2016, Ashur and Liu introduced modified rotational cryptanalysis using the rotational-XOR-difference (RXD) to overcome the limitations caused by the constants and applied it to block cipher Speck [11]. They defined an RX pair as x⊕a1,x⟶⊕a2 and its RXD as a1,a2,γ. It is obvious that the RX pair is preserved even if some constant is XORed to the values of the pair. In addition, they proved the following Theorem 1, which shows us how to calculate the transition probability of RX pair through modular addition. We assume that γ=1 throughout this paper; hence, we let x⟶ denote x⋘1.Theorem 1 (Theorem1 in [11]).
Letx,y∈F2n represent independent uniform random variables. Let a1,a2,b1,b2,c1, and c2 be constants in F2n and δx,δy, and δz be the n−1 most significant bits of a1⟶⊕a2, b1⟶⊕b2, and c1⟶⊕c2, respectively. Then,(2)Px⊕a1⊞y⊕b1⊕c1⟶=x⟶⊕a2⊞y⟶⊕b2⊕c2=2−wHT⋅2−3,ifS⊕1≺¯T,2−wHT⋅2−1.415,else ifS≺¯T,0,otherwise,where T=δx⊕δz∨δy⊕δz≪1 and S=δx⊕δy⊕δz⊕δx⊕δy⊕δz≪1.
It is clear that the rotation of an RX pair is an RX pair and that the XOR of two RX pairs is also an RX pair.


### 2.4. Boomerang/Rectangle Characteristics

A boomerang attack [21] uses two differential characteristics Δ⟶Δ∗ for E0 and ∇⟶∇∗ for E1, whose probabilities are p and q, respectively, where the target block cipher E is a composition of subciphers E0 and E1, i.e., E=E1∘E0. If two plaintexts P and P′ such that P⊕P′=Δ satisfy(3)E0P⊕E0P′=Δ∗,with probability p and both(4)E1−1EP⊕E1−1EP⊕∇=∇∗,E1−1EP′⊕E1−1EP′⊕∇=∇∗,are satisfied with probability q2, then, clearly(5)E1−1EP⊕∇⊕E1−1EP′⊕∇=Δ∗.Hence,(6)E−1EP⊕∇⊕E−1EP′⊕∇=Δ,with probability p.Therefore, if we denoteE−1EP⊕∇ and E−1EP′⊕∇ as Q and Q′, we can distinguish E from the random permutation according to the distribution of Q⊕Q′, where P⊕P′=Δ and p2q2>2−n.A boomerang attack is an adaptive chosen-ciphertext attack that can be transformed into a known-plaintext attack based on the following rectangle distinguisher [22].Suppose that we have two pairs of plaintextP,P′ and Q,Q′ such that(7)P⊕P′=Q⊕Q′=Δ.In such a case, we have(8)E0P⊕E0P′=E0Q⊕E0Q′=Δ∗,with probability p2. Here, if we suppose that E0P⊕E0Q=∇∗ with probability 2−n, then we have(9)E0P′⊕E0Q′=∇∗,accordingly(10)EP⊕EQ=EP′⊕EQ′=∇,with probability q2.Thus, we can distinguishE from the random permutation using the distributions of EP⊕EQ and EP′⊕EQ′, if P⊕P′=Q⊕Q′=Δ and p2q22−n>2−2n.


### 2.5. Description of Simon

Simon [4] is a family of block ciphers which support various bit lengths of blocks and keys. For w = 16, 24, 32, 48, and 64, Simon-n/k has a block size of n=2w and a key size of k=2w, 3w, or 4w. Encryption of Simon involves iterations of the round transformations shown in Figure 1, where ∧ and ⊕ are bitwise AND and XOR, respectively. rki for i=1,2,... denotes the i-th round keys generated by one of the three key schedules shown in Figure 2 depending on the number of keywords, where c is equal to 2w−4 and zji is the i-th bit of zj, defined as follows.(11)z0=11111010001001010110000111001101111101000100101011000011100110...,z1=10001110111110010011000010110101000111011111001001100001011010...,z2=10101111011100000011010010011000101000010001111110010110110011...,z3=11011011101011000110010111100000010010001010011100110100001111...,z4=11010001111001101011011000100000010111000011001010010011101111....Figure 1
Round transformation of Simon.Figure 2
Three key schedules of Simon.More specific descriptions for each instance of Simon can be found in the literature [4].


## 2.1. Notations

In this paper, we use the following notations:(i)
wHx: Hamming weight of bit string x(ii)
x⊞y: modular addition of bit strings x and y(iii)
x∨y: bitwise OR of bit strings x and y(iv)
x∧y: bitwise AND of bit strings x and y(v)
x≪r: r bit left shift of a bit string x(vi)
x<r, x⋘r: r bit left rotation (cyclic shift) of a bit string x(vii)
x>r: r bit right rotation (cyclic shift) of a bit string x(viii)
x⟶: left rotation (cyclic shift) of a bit string x by a predefined γ, usually γ=1(ix)
x←: right rotation (cyclic shift) of a bit string x by a predefined γ, usually γ=1(x)
xi: i-th bit of a bit string x(xi)
x≺¯y means that every bit in y is larger or equal to the corresponding bit in x


## 2.2. Rotational Cryptanalysis

Since Khovratovich et al. introduced rotational cryptanalysis in 2010 [9], it has been used to evaluate symmetric key cryptographic primitives based on the ARX design framework [10, 18, 19]. Rotational cryptanalysis appears to be suitable for ARX ciphers because the rotational pair is preserved through rotations and XORes between variables and transformed by modular additions with high probability levels, unlike ciphers based on S-boxes.Rotational cryptanalysis exploits the nonrandom behavior of ciphertext pairs generated from the rotational plaintext pairsp0,p1,...,pm−1,p0⟶,p1⟶,...,pm−1⟶ where pi⟶=pi⋘γ for some integer γ (γ is typically selected to 1 for a higher probability). The probability that modular addition of two rotational pairs x,x⟶ and y,y⟶ is also a rotational pair is given by(1)Px⊞y⟶=x⟶⊞y⟶=141+2γ−n+2−γ+2−n,where n is the bit length of both x and y [20]. For a large n, that probability goes to 2−1.415 when γ=1 and to 2−2 when γ=n/2.However, XOR or modular addition with a constant destroys the rotational relationship of a pair when the constant cannot transform into itself byγ-bit rotation. So, the rotational cryptanalysis cannot be widely adopted in relation to the block cipher analysis.


## 2.3. Rotational-XOR-Difference

In 2016, Ashur and Liu introduced modified rotational cryptanalysis using the rotational-XOR-difference (RXD) to overcome the limitations caused by the constants and applied it to block cipher Speck [11]. They defined an RX pair as x⊕a1,x⟶⊕a2 and its RXD as a1,a2,γ. It is obvious that the RX pair is preserved even if some constant is XORed to the values of the pair. In addition, they proved the following Theorem 1, which shows us how to calculate the transition probability of RX pair through modular addition. We assume that γ=1 throughout this paper; hence, we let x⟶ denote x⋘1.Theorem 1 (Theorem1 in [11]).
Letx,y∈F2n represent independent uniform random variables. Let a1,a2,b1,b2,c1, and c2 be constants in F2n and δx,δy, and δz be the n−1 most significant bits of a1⟶⊕a2, b1⟶⊕b2, and c1⟶⊕c2, respectively. Then,(2)Px⊕a1⊞y⊕b1⊕c1⟶=x⟶⊕a2⊞y⟶⊕b2⊕c2=2−wHT⋅2−3,ifS⊕1≺¯T,2−wHT⋅2−1.415,else ifS≺¯T,0,otherwise,where T=δx⊕δz∨δy⊕δz≪1 and S=δx⊕δy⊕δz⊕δx⊕δy⊕δz≪1.
It is clear that the rotation of an RX pair is an RX pair and that the XOR of two RX pairs is also an RX pair.


## 2.4. Boomerang/Rectangle Characteristics

A boomerang attack [21] uses two differential characteristics Δ⟶Δ∗ for E0 and ∇⟶∇∗ for E1, whose probabilities are p and q, respectively, where the target block cipher E is a composition of subciphers E0 and E1, i.e., E=E1∘E0. If two plaintexts P and P′ such that P⊕P′=Δ satisfy(3)E0P⊕E0P′=Δ∗,with probability p and both(4)E1−1EP⊕E1−1EP⊕∇=∇∗,E1−1EP′⊕E1−1EP′⊕∇=∇∗,are satisfied with probability q2, then, clearly(5)E1−1EP⊕∇⊕E1−1EP′⊕∇=Δ∗.Hence,(6)E−1EP⊕∇⊕E−1EP′⊕∇=Δ,with probability p.Therefore, if we denoteE−1EP⊕∇ and E−1EP′⊕∇ as Q and Q′, we can distinguish E from the random permutation according to the distribution of Q⊕Q′, where P⊕P′=Δ and p2q2>2−n.A boomerang attack is an adaptive chosen-ciphertext attack that can be transformed into a known-plaintext attack based on the following rectangle distinguisher [22].Suppose that we have two pairs of plaintextP,P′ and Q,Q′ such that(7)P⊕P′=Q⊕Q′=Δ.In such a case, we have(8)E0P⊕E0P′=E0Q⊕E0Q′=Δ∗,with probability p2. Here, if we suppose that E0P⊕E0Q=∇∗ with probability 2−n, then we have(9)E0P′⊕E0Q′=∇∗,accordingly(10)EP⊕EQ=EP′⊕EQ′=∇,with probability q2.Thus, we can distinguishE from the random permutation using the distributions of EP⊕EQ and EP′⊕EQ′, if P⊕P′=Q⊕Q′=Δ and p2q22−n>2−2n.


## 2.5. Description of Simon

Simon [4] is a family of block ciphers which support various bit lengths of blocks and keys. For w = 16, 24, 32, 48, and 64, Simon-n/k has a block size of n=2w and a key size of k=2w, 3w, or 4w. Encryption of Simon involves iterations of the round transformations shown in Figure 1, where ∧ and ⊕ are bitwise AND and XOR, respectively. rki for i=1,2,... denotes the i-th round keys generated by one of the three key schedules shown in Figure 2 depending on the number of keywords, where c is equal to 2w−4 and zji is the i-th bit of zj, defined as follows.(11)z0=11111010001001010110000111001101111101000100101011000011100110...,z1=10001110111110010011000010110101000111011111001001100001011010...,z2=10101111011100000011010010011000101000010001111110010110110011...,z3=11011011101011000110010111100000010010001010011100110100001111...,z4=11010001111001101011011000100000010111000011001010010011101111....Figure 1
Round transformation of Simon.Figure 2
Three key schedules of Simon.More specific descriptions for each instance of Simon can be found in the literature [4].


## 3. Rotational-XOR-Differences for Simon

Unlike Speck, based on modular addition, Simon uses the bitwise AND for its round function, though this operation does not always preserve RX pairs. Consequently, here it is necessary to calculate the probability that two RX pairs are transformed into another RX pair through the bitwise AND operation.


### 3.1. Calculating the Probabilities of Rotational-XOR Pairs for the Bitwise AND Operation

Supposex⊕a1,x⟶⊕a2 and y⊕b1,y⟶⊕b2 are two input RX pairs of a bitwise AND operation. In such a case, the output pair is x⊕a1∧y⊕b1,x⟶⊕a2∧y⟶⊕b2. Let x⊕a1∧y⊕b1=z⊕c1 and x⟶⊕a2∧y⟶⊕b2=z˜⊕c2 for some constants c1 and c2. The probability that the output pair becomes an RX pair then becomes(12)Pz⟶=z˜=Px⊕a1∧y⊕b1⊕c1⟶=x⟶⊕a2∧y⟶⊕b2⊕c2.We can observe when the probability is nonzero and how to calculate the probability by Theorem2, under the assumption that two inputs of the bitwise AND are independent uniformly random variables.Theorem 2 (bitwise AND of two random variables).
Letx,y∈F2w represent independent uniformly random variables for some positive integer w, and let a1,a2,b1,b2,c1, and c2 be constants in F2w and δx=a1⟶⊕a2, δy=b1⟶⊕b2, and δz=c1⟶⊕c2. Then,(13)Px⊕a1∧y⊕b1⊕c1⟶=x⟶⊕a2∧y⟶⊕b2⊕c2=2−wHδx∨δy,ifδx∨δy∧δz,0,otherwise.Proof.
Letx⊕a1∧y⊕b1=z⊕c1 and x⟶⊕a2∧y⟶⊕b2=z˜⊕c2. In this case, we will calculate the probability that z˜=z⟶.
Because⊕ and ∧ are bitwise operations, it is clear that(14)z⟶=x⊕a1∧y⊕b1⊕c1⟶=x⟶⊕a1⟶∧y⟶⊕b1⟶⊕c1⟶=x⟶∧y⟶⊕x⟶∧b1⟶⊕a1⟶∧y⟶⊕a1⟶∧b1⟶⊕c1⟶,z˜=x⟶⊕a2∧y⟶⊕b2⊕c2=x⟶∧y⟶⊕x⟶∧b2⊕a2∧y⟶⊕a2∧b2⊕c2.
Therefore, now we calculate the probability that(15)z˜=z⟶⟹x⟶∧b1⟶⊕a1⟶∧y⟶⊕a1⟶∧b1⟶⊕x⟶∧b2⊕a2∧y⟶⊕a2∧b2=x⟶∧b1⟶⊕b2⊕y⟶∧a1⟶⊕a2⊕a1⟶∧b1⟶⊕a2∧b2=c1⟶⊕c2.
According to the definitions ofδx, δy, and δz, we have the following equations:(16)x⟶∧δy⊕y⟶∧δx⊕a1⟶∧b1⟶⊕a2∧b2=δz⟹x⟶∧δy⊕y⟶∧δx⊕0δx⊕a2∧δy⊕b2⊕a2∧b2=δz⟹x⟶∧δy⊕y⟶∧δx⊕δx∧δy⊕δx∧b2⊕δy∧a2δz.
At this point, we consider equation (16) in bit by bit. For each i∈0,1,...,w−1, if the i-th bits of δx and δy are 0, i.e., δxi=δyi=0, then the i-th bit of the left-hand side of equation (16) is 0; hence, the stipulations of the i-th bit of equation (16) are met only if δ3i=0 with a probability of 1. Otherwise, if δxi=0 and δyi=1, in this case, equation (16) implies x⟶i⊕a2i=δzi which is satisfied depending on x⟶i. Because we assume x be a uniform random variable, the probability that the requirements associated with the i-th bit of equation (16) are satisfied is 1/2. Similarly, if δxi=1 and δyi=0, the conditions of the i-th bit of equation (16) are met with a probability of 1/2 depending on y⟶i regardless of the value of δzi. The last case is one in which δxi=1 and δyi=1. In this case, (16) implies that x⟶i⊕y⟶i⊕1⊕a2i⊕b2i=δzi and the conditions of this equation are also satisfied with a probability of 1/2 regardless of the value of δzi because a2i and b2i are fixed values.
Thus, for some fixedδx, δy, and δz, if there exists i such that δxi=δyi=0 and δzi=1, the probability is then 0. Therefore, the probability is nonzero only if δxδy∧δz=δz. And for each i such that δxi∨δyi=1, the conditions of the i-th bit of (16) are met with a probability of 1/2. Therefore, the probability that the conditions of (16) are met (which we want to calculate) is 2−wHδx∨δy.
However, as shown in Figure1, the two inputs x and y of the bitwise AND operation in Simon are highly dependent on each other. Therefore, we need to calculate the probability more precisely. The following Theorem 3 is analogous to Theorem 3 for covering the Simon case and the case of j=7 is relevant to Simon-2w/k.Theorem 3.
(bitwise AND of two values from one random variable). Letx∈F2w be an uniformly random variable for a positive integer w and j≤w be a positive integer that does not divide w. Additionally, let a1,a2,c1, and c2 be constants in F2w and δx=a1⟶⊕a2 and δz=c1⟶⊕c2. In this case,(17)Px⊕a1∧x<j⊕a1<j⊕c1⟶=x⟶⊕a2∧x<j⟶⊕a2<j⊕c2=2−n+1,ifδx=2n−1,2−wHδx∨δx<j+wHT,else ifδx∨δx<j∧δz=δz,0,otherwise,where T=δx<j¯∧δx∧δx<2j.Proof.
Similar to the proof of Theorem3, we now calculate the probability that the following equation holds:(18)x⟶∧δx<j⊕x<j⟶∧δx⊕δx∧δx<j⊕δx∧a2<j⊕δx<j∧a2=δz,⇒δx∧δx<j⊕δx<j∧x⟶⊕a2⊕δx∧x⟶⊕a2<j=δz.
Here, we consider equation (18) in bit by bit.
For eachi∈0,1,...,w−1, if δxi=δx<ji=0, then(19)δzi=0,with a probability of 1.
Else ifδxi=0 and δx<ji=1, according to equation (18),(20)δzi=x⟶⊕a2i.
However, becausex⟶i would appear again when we define δz>ji, it is necessary to consider the subcases along with the value of δx>ji. If δx>ji=0, x⟶i does not contribute to the definition of δz>ji. Therefore, x⟶i can be regarded as a free random variable (which means it is not used to define other bits of δz); therefore, δzi can be 0 or 1 with a probability of 1/2. Otherwise (i.e., δx>ji=1), as δxi=0, δz>ji=x⟶⊕a2i and we have the relationship of δzi=δz>ji.
Otherwise, ifδxi=1 and δx<ji=0, similar to the above case, δzi is defined as a free random variable x⟶<ji when δx<2ji=0. On the other hand, δz<ji=x⟶⊕a2<ji and then we have the relationship of δzi=δz<ji.
Otherwise,δxi=1 and δx<ji=1, according to equation (18),(21)δzi=1⊕x⟶⊕a2⊕x⟶⊕a2<ji.
It is necessary to check for subcases forδx<2ji and δx>ji. We already know that δx<ji=1 and δxi=1. If δx<2ji∧δx>ji=0, δzi is defined as a free random variable, x⟶i, x⟶<ji, or both conditions apply. Hence, δzi is 0 or 1 with a probability of 1/2. Otherwise, δx<2ji=δx>ji=1; then, δz>ji is defined as x⟶>2ji and x⟶>ji, and δz<ji is defined according to x⟶i and x⟶<ji. This means that three bits of δz are defined as four independent bits of the random variable x⟶. Such chain ends with the bit of δz, which is independently defined except when δx=2n−1 because j∤n. Thus, every bit in the chain, including δzi, has a value of 0 or 1 with a probability of 1/2. If δx=2n−1, every single bit of δz is defined by two bits of x⟶ and they are related to each other. Hence, the probability that δz has some value is 2−n+1. Consequently, if δx>ji=0,δxi=1,δx>2ji=1 for some i, then the freedom of δzi and δz>ji is decreased by 1 bit and there are exactly wHδx<j¯∧δx∧δx<2j pairs of bits in δx.


### 3.2. Searching for the Rotational-XOR-Differences Trail of Simon

#### 3.2.1. How to Define the Rotational-XOR-Differences Trail

Because we letγ=1, the RXD of an RX pair x⊕a1,x⟶⊕a2 can be denoted as a1,a2,1. However, we use δx=a1⟶⊕a2 to calculate the probability of the occurrence of the bitwise AND of the RX pair regardless of the actual values of a1 and a2. Thus, we can redefine the RXD of an RX pair x⊕a1,x⟶⊕a2 as δx=a1⟶⊕a2 for the following reason.Let there be another RX pairy⊕b1,y⟶⊕b2 such that y⊕b1=x⊕a1 and y⟶⊕b2=x⟶⊕a2 for some random variable y≠x. In this case, we have(22)δy=b1⟶⊕b2=y⊕x⊕a1⟶⊕y⟶⊕x⟶⊕a2=a1⟶⊕a2=δx.This means that the relationship between the constants (i.e.,δ’s) is sufficient to represent the RX pair and thus is also sufficient to trace the transition of δ’s instead of RX pairs to search for an RXD trail. We also refer to this δ value as RXD and we denote an RXD trail from pair x⊕a1,x⟶⊕a2 to pair x⊕b1,x⟶⊕b2 such that δa=a1⟶⊕a2 and δb=b1⟶⊕b2 as δa⟶δb. To find a suitable RXD trail, we need to know how the RXDs are transformed by the operations used in the target cipher.Because Simon uses only three operations, XOR, rotation, and the bitwise AND, we can discuss these operations. An RXD is transformed by XOR as follows. Let there be two RX pairsx⊕a1,x⟶⊕a2 and y⊕b1,y⟶⊕b2, and δx=a1⊕a2 and δy=b1⊕b2. If a new variable z=x⊕y is introduced, two RX pairs x⊕a1,x⟶⊕a2 and y⊕b1,y⟶⊕b2 are XORed into an RX pair z⊕c1,z⟶⊕c2 such that c1=a1⊕b1 and c2=a2⊕b2. Because δx=a1⟶⊕a2 and δy=b1⟶⊕c2, we have(23)δz=c1⟶⊕c2=δx⊕δy.If a constantc is XORed into an RXD δ, the RX pair x⊕a1,x⟶⊕a2 is transformed into x⊕a1⊕c,x⟶⊕a2⊕c. Then, clearly,(24)δ′=a1⊕c⟶⊕a2⊕c=δ⊕c⟶⊕c.For the rotation operations, similar to the above case of XOR, ify=x<l, then δy=δx<l.The transition of an RXD by the bitwise AND is as follows. Letz=x∧y; then, every ω satisfying δx∨δy∧ω=ω could be δz with the probability given in Theorem 2 In the case of Simon, the random variables x and y are dependent on each other such that the ω values that could be δz differ lightly from the general case, as shown in Theorem 3


#### 3.2.2. Considerations

We took the following considerations into account during the search for the RXD trails of Simon.(1)
Round indices. The indices of start and end round of the characteristic should be specified because a rotational attack is basically in the related-key model and the δ values (RXDs) of the round keys vary according to the round constants zi’s XORed in the key schedule.(2)
Including Rounds with an RXD Probability of 1. If RXDs with two input words of encryption and k/w keywords for a round are all zero, we find some output RXD that is maximally k/w+2 rounds with a probability of 1. Thus, it is effective to search for RXD trails forward and backward beginning with such zero (or with a lower Hamming weight) states to find trails with a high probability.(3)
Maximizing the Probability of the Next Round. The probability of an RXD trail of a round is determined by the RXD of the left half of the input. Hence, if we can control the right half of the output of the current round, we can maximize the RX probability of the next round. According to Theorem 3, one input RXD can be transformed into several output RXDs through the bitwise AND, and because their probabilities are identical, we can choose one of them with a condition identical to that of the current round. Let δi,L and δi,R be the RXDs of the left and the right inputs of i-th round, respectively, and δKi be the δ value of the i-th round key. To maximize the RX probability of the i+1-th round, δi+1,L should have a lower Hamming weight. Because (25)δi+1,L=δi,R⊕δi,z⊕δi,L<2⊕δi,K,where δi,z is the RXD of the output of the bitwise AND in the i-th round, we can choose δi,z for which minimizes the Hamming weight of δi+1,L. Note that minimizing the Hamming weight of δi+1,L does not always guarantee the best RXD trail; however, we searched for RXD trails with such conditions in mind.


### 3.3. Rotational-XOR-Differences Trails of Simon

Putting the aforementioned considerations together, we searched for RXD trails with a high probability for Simon-32/64, 48/72, 48/96, 64/96, and 64/128. Initially, we let the pairs of both intermediate value and key state of the starting round have theδ values of Hamming weight 0 or 1. We then searched for the RXD trail with the maximum probability for each number of rounds by adding rounds forward and backward, while varying the starting round.As a result, we can find numerous trails with the maximum probability for various starting round indices. Therefore, we can construct rectangle characteristics using short trails with high probabilities with considering the round indices.


## 3.1. Calculating the Probabilities of Rotational-XOR Pairs for the Bitwise AND Operation

Supposex⊕a1,x⟶⊕a2 and y⊕b1,y⟶⊕b2 are two input RX pairs of a bitwise AND operation. In such a case, the output pair is x⊕a1∧y⊕b1,x⟶⊕a2∧y⟶⊕b2. Let x⊕a1∧y⊕b1=z⊕c1 and x⟶⊕a2∧y⟶⊕b2=z˜⊕c2 for some constants c1 and c2. The probability that the output pair becomes an RX pair then becomes(12)Pz⟶=z˜=Px⊕a1∧y⊕b1⊕c1⟶=x⟶⊕a2∧y⟶⊕b2⊕c2.We can observe when the probability is nonzero and how to calculate the probability by Theorem2, under the assumption that two inputs of the bitwise AND are independent uniformly random variables.Theorem 2 (bitwise AND of two random variables).
Letx,y∈F2w represent independent uniformly random variables for some positive integer w, and let a1,a2,b1,b2,c1, and c2 be constants in F2w and δx=a1⟶⊕a2, δy=b1⟶⊕b2, and δz=c1⟶⊕c2. Then,(13)Px⊕a1∧y⊕b1⊕c1⟶=x⟶⊕a2∧y⟶⊕b2⊕c2=2−wHδx∨δy,ifδx∨δy∧δz,0,otherwise.Proof.
Letx⊕a1∧y⊕b1=z⊕c1 and x⟶⊕a2∧y⟶⊕b2=z˜⊕c2. In this case, we will calculate the probability that z˜=z⟶.
Because⊕ and ∧ are bitwise operations, it is clear that(14)z⟶=x⊕a1∧y⊕b1⊕c1⟶=x⟶⊕a1⟶∧y⟶⊕b1⟶⊕c1⟶=x⟶∧y⟶⊕x⟶∧b1⟶⊕a1⟶∧y⟶⊕a1⟶∧b1⟶⊕c1⟶,z˜=x⟶⊕a2∧y⟶⊕b2⊕c2=x⟶∧y⟶⊕x⟶∧b2⊕a2∧y⟶⊕a2∧b2⊕c2.
Therefore, now we calculate the probability that(15)z˜=z⟶⟹x⟶∧b1⟶⊕a1⟶∧y⟶⊕a1⟶∧b1⟶⊕x⟶∧b2⊕a2∧y⟶⊕a2∧b2=x⟶∧b1⟶⊕b2⊕y⟶∧a1⟶⊕a2⊕a1⟶∧b1⟶⊕a2∧b2=c1⟶⊕c2.
According to the definitions ofδx, δy, and δz, we have the following equations:(16)x⟶∧δy⊕y⟶∧δx⊕a1⟶∧b1⟶⊕a2∧b2=δz⟹x⟶∧δy⊕y⟶∧δx⊕0δx⊕a2∧δy⊕b2⊕a2∧b2=δz⟹x⟶∧δy⊕y⟶∧δx⊕δx∧δy⊕δx∧b2⊕δy∧a2δz.
At this point, we consider equation (16) in bit by bit. For each i∈0,1,...,w−1, if the i-th bits of δx and δy are 0, i.e., δxi=δyi=0, then the i-th bit of the left-hand side of equation (16) is 0; hence, the stipulations of the i-th bit of equation (16) are met only if δ3i=0 with a probability of 1. Otherwise, if δxi=0 and δyi=1, in this case, equation (16) implies x⟶i⊕a2i=δzi which is satisfied depending on x⟶i. Because we assume x be a uniform random variable, the probability that the requirements associated with the i-th bit of equation (16) are satisfied is 1/2. Similarly, if δxi=1 and δyi=0, the conditions of the i-th bit of equation (16) are met with a probability of 1/2 depending on y⟶i regardless of the value of δzi. The last case is one in which δxi=1 and δyi=1. In this case, (16) implies that x⟶i⊕y⟶i⊕1⊕a2i⊕b2i=δzi and the conditions of this equation are also satisfied with a probability of 1/2 regardless of the value of δzi because a2i and b2i are fixed values.
Thus, for some fixedδx, δy, and δz, if there exists i such that δxi=δyi=0 and δzi=1, the probability is then 0. Therefore, the probability is nonzero only if δxδy∧δz=δz. And for each i such that δxi∨δyi=1, the conditions of the i-th bit of (16) are met with a probability of 1/2. Therefore, the probability that the conditions of (16) are met (which we want to calculate) is 2−wHδx∨δy.
However, as shown in Figure1, the two inputs x and y of the bitwise AND operation in Simon are highly dependent on each other. Therefore, we need to calculate the probability more precisely. The following Theorem 3 is analogous to Theorem 3 for covering the Simon case and the case of j=7 is relevant to Simon-2w/k.Theorem 3.
(bitwise AND of two values from one random variable). Letx∈F2w be an uniformly random variable for a positive integer w and j≤w be a positive integer that does not divide w. Additionally, let a1,a2,c1, and c2 be constants in F2w and δx=a1⟶⊕a2 and δz=c1⟶⊕c2. In this case,(17)Px⊕a1∧x<j⊕a1<j⊕c1⟶=x⟶⊕a2∧x<j⟶⊕a2<j⊕c2=2−n+1,ifδx=2n−1,2−wHδx∨δx<j+wHT,else ifδx∨δx<j∧δz=δz,0,otherwise,where T=δx<j¯∧δx∧δx<2j.Proof.
Similar to the proof of Theorem3, we now calculate the probability that the following equation holds:(18)x⟶∧δx<j⊕x<j⟶∧δx⊕δx∧δx<j⊕δx∧a2<j⊕δx<j∧a2=δz,⇒δx∧δx<j⊕δx<j∧x⟶⊕a2⊕δx∧x⟶⊕a2<j=δz.
Here, we consider equation (18) in bit by bit.
For eachi∈0,1,...,w−1, if δxi=δx<ji=0, then(19)δzi=0,with a probability of 1.
Else ifδxi=0 and δx<ji=1, according to equation (18),(20)δzi=x⟶⊕a2i.
However, becausex⟶i would appear again when we define δz>ji, it is necessary to consider the subcases along with the value of δx>ji. If δx>ji=0, x⟶i does not contribute to the definition of δz>ji. Therefore, x⟶i can be regarded as a free random variable (which means it is not used to define other bits of δz); therefore, δzi can be 0 or 1 with a probability of 1/2. Otherwise (i.e., δx>ji=1), as δxi=0, δz>ji=x⟶⊕a2i and we have the relationship of δzi=δz>ji.
Otherwise, ifδxi=1 and δx<ji=0, similar to the above case, δzi is defined as a free random variable x⟶<ji when δx<2ji=0. On the other hand, δz<ji=x⟶⊕a2<ji and then we have the relationship of δzi=δz<ji.
Otherwise,δxi=1 and δx<ji=1, according to equation (18),(21)δzi=1⊕x⟶⊕a2⊕x⟶⊕a2<ji.
It is necessary to check for subcases forδx<2ji and δx>ji. We already know that δx<ji=1 and δxi=1. If δx<2ji∧δx>ji=0, δzi is defined as a free random variable, x⟶i, x⟶<ji, or both conditions apply. Hence, δzi is 0 or 1 with a probability of 1/2. Otherwise, δx<2ji=δx>ji=1; then, δz>ji is defined as x⟶>2ji and x⟶>ji, and δz<ji is defined according to x⟶i and x⟶<ji. This means that three bits of δz are defined as four independent bits of the random variable x⟶. Such chain ends with the bit of δz, which is independently defined except when δx=2n−1 because j∤n. Thus, every bit in the chain, including δzi, has a value of 0 or 1 with a probability of 1/2. If δx=2n−1, every single bit of δz is defined by two bits of x⟶ and they are related to each other. Hence, the probability that δz has some value is 2−n+1. Consequently, if δx>ji=0,δxi=1,δx>2ji=1 for some i, then the freedom of δzi and δz>ji is decreased by 1 bit and there are exactly wHδx<j¯∧δx∧δx<2j pairs of bits in δx.


## 3.2. Searching for the Rotational-XOR-Differences Trail of Simon

### 3.2.1. How to Define the Rotational-XOR-Differences Trail

Because we letγ=1, the RXD of an RX pair x⊕a1,x⟶⊕a2 can be denoted as a1,a2,1. However, we use δx=a1⟶⊕a2 to calculate the probability of the occurrence of the bitwise AND of the RX pair regardless of the actual values of a1 and a2. Thus, we can redefine the RXD of an RX pair x⊕a1,x⟶⊕a2 as δx=a1⟶⊕a2 for the following reason.Let there be another RX pairy⊕b1,y⟶⊕b2 such that y⊕b1=x⊕a1 and y⟶⊕b2=x⟶⊕a2 for some random variable y≠x. In this case, we have(22)δy=b1⟶⊕b2=y⊕x⊕a1⟶⊕y⟶⊕x⟶⊕a2=a1⟶⊕a2=δx.This means that the relationship between the constants (i.e.,δ’s) is sufficient to represent the RX pair and thus is also sufficient to trace the transition of δ’s instead of RX pairs to search for an RXD trail. We also refer to this δ value as RXD and we denote an RXD trail from pair x⊕a1,x⟶⊕a2 to pair x⊕b1,x⟶⊕b2 such that δa=a1⟶⊕a2 and δb=b1⟶⊕b2 as δa⟶δb. To find a suitable RXD trail, we need to know how the RXDs are transformed by the operations used in the target cipher.Because Simon uses only three operations, XOR, rotation, and the bitwise AND, we can discuss these operations. An RXD is transformed by XOR as follows. Let there be two RX pairsx⊕a1,x⟶⊕a2 and y⊕b1,y⟶⊕b2, and δx=a1⊕a2 and δy=b1⊕b2. If a new variable z=x⊕y is introduced, two RX pairs x⊕a1,x⟶⊕a2 and y⊕b1,y⟶⊕b2 are XORed into an RX pair z⊕c1,z⟶⊕c2 such that c1=a1⊕b1 and c2=a2⊕b2. Because δx=a1⟶⊕a2 and δy=b1⟶⊕c2, we have(23)δz=c1⟶⊕c2=δx⊕δy.If a constantc is XORed into an RXD δ, the RX pair x⊕a1,x⟶⊕a2 is transformed into x⊕a1⊕c,x⟶⊕a2⊕c. Then, clearly,(24)δ′=a1⊕c⟶⊕a2⊕c=δ⊕c⟶⊕c.For the rotation operations, similar to the above case of XOR, ify=x<l, then δy=δx<l.The transition of an RXD by the bitwise AND is as follows. Letz=x∧y; then, every ω satisfying δx∨δy∧ω=ω could be δz with the probability given in Theorem 2 In the case of Simon, the random variables x and y are dependent on each other such that the ω values that could be δz differ lightly from the general case, as shown in Theorem 3


### 3.2.2. Considerations

We took the following considerations into account during the search for the RXD trails of Simon.(1)
Round indices. The indices of start and end round of the characteristic should be specified because a rotational attack is basically in the related-key model and the δ values (RXDs) of the round keys vary according to the round constants zi’s XORed in the key schedule.(2)
Including Rounds with an RXD Probability of 1. If RXDs with two input words of encryption and k/w keywords for a round are all zero, we find some output RXD that is maximally k/w+2 rounds with a probability of 1. Thus, it is effective to search for RXD trails forward and backward beginning with such zero (or with a lower Hamming weight) states to find trails with a high probability.(3)
Maximizing the Probability of the Next Round. The probability of an RXD trail of a round is determined by the RXD of the left half of the input. Hence, if we can control the right half of the output of the current round, we can maximize the RX probability of the next round. According to Theorem 3, one input RXD can be transformed into several output RXDs through the bitwise AND, and because their probabilities are identical, we can choose one of them with a condition identical to that of the current round. Let δi,L and δi,R be the RXDs of the left and the right inputs of i-th round, respectively, and δKi be the δ value of the i-th round key. To maximize the RX probability of the i+1-th round, δi+1,L should have a lower Hamming weight. Because (25)δi+1,L=δi,R⊕δi,z⊕δi,L<2⊕δi,K,where δi,z is the RXD of the output of the bitwise AND in the i-th round, we can choose δi,z for which minimizes the Hamming weight of δi+1,L. Note that minimizing the Hamming weight of δi+1,L does not always guarantee the best RXD trail; however, we searched for RXD trails with such conditions in mind.


## 3.2.1. How to Define the Rotational-XOR-Differences Trail

Because we letγ=1, the RXD of an RX pair x⊕a1,x⟶⊕a2 can be denoted as a1,a2,1. However, we use δx=a1⟶⊕a2 to calculate the probability of the occurrence of the bitwise AND of the RX pair regardless of the actual values of a1 and a2. Thus, we can redefine the RXD of an RX pair x⊕a1,x⟶⊕a2 as δx=a1⟶⊕a2 for the following reason.Let there be another RX pairy⊕b1,y⟶⊕b2 such that y⊕b1=x⊕a1 and y⟶⊕b2=x⟶⊕a2 for some random variable y≠x. In this case, we have(22)δy=b1⟶⊕b2=y⊕x⊕a1⟶⊕y⟶⊕x⟶⊕a2=a1⟶⊕a2=δx.This means that the relationship between the constants (i.e.,δ’s) is sufficient to represent the RX pair and thus is also sufficient to trace the transition of δ’s instead of RX pairs to search for an RXD trail. We also refer to this δ value as RXD and we denote an RXD trail from pair x⊕a1,x⟶⊕a2 to pair x⊕b1,x⟶⊕b2 such that δa=a1⟶⊕a2 and δb=b1⟶⊕b2 as δa⟶δb. To find a suitable RXD trail, we need to know how the RXDs are transformed by the operations used in the target cipher.Because Simon uses only three operations, XOR, rotation, and the bitwise AND, we can discuss these operations. An RXD is transformed by XOR as follows. Let there be two RX pairsx⊕a1,x⟶⊕a2 and y⊕b1,y⟶⊕b2, and δx=a1⊕a2 and δy=b1⊕b2. If a new variable z=x⊕y is introduced, two RX pairs x⊕a1,x⟶⊕a2 and y⊕b1,y⟶⊕b2 are XORed into an RX pair z⊕c1,z⟶⊕c2 such that c1=a1⊕b1 and c2=a2⊕b2. Because δx=a1⟶⊕a2 and δy=b1⟶⊕c2, we have(23)δz=c1⟶⊕c2=δx⊕δy.If a constantc is XORed into an RXD δ, the RX pair x⊕a1,x⟶⊕a2 is transformed into x⊕a1⊕c,x⟶⊕a2⊕c. Then, clearly,(24)δ′=a1⊕c⟶⊕a2⊕c=δ⊕c⟶⊕c.For the rotation operations, similar to the above case of XOR, ify=x<l, then δy=δx<l.The transition of an RXD by the bitwise AND is as follows. Letz=x∧y; then, every ω satisfying δx∨δy∧ω=ω could be δz with the probability given in Theorem 2 In the case of Simon, the random variables x and y are dependent on each other such that the ω values that could be δz differ lightly from the general case, as shown in Theorem 3


## 3.2.2. Considerations

We took the following considerations into account during the search for the RXD trails of Simon.(1)
Round indices. The indices of start and end round of the characteristic should be specified because a rotational attack is basically in the related-key model and the δ values (RXDs) of the round keys vary according to the round constants zi’s XORed in the key schedule.(2)
Including Rounds with an RXD Probability of 1. If RXDs with two input words of encryption and k/w keywords for a round are all zero, we find some output RXD that is maximally k/w+2 rounds with a probability of 1. Thus, it is effective to search for RXD trails forward and backward beginning with such zero (or with a lower Hamming weight) states to find trails with a high probability.(3)
Maximizing the Probability of the Next Round. The probability of an RXD trail of a round is determined by the RXD of the left half of the input. Hence, if we can control the right half of the output of the current round, we can maximize the RX probability of the next round. According to Theorem 3, one input RXD can be transformed into several output RXDs through the bitwise AND, and because their probabilities are identical, we can choose one of them with a condition identical to that of the current round. Let δi,L and δi,R be the RXDs of the left and the right inputs of i-th round, respectively, and δKi be the δ value of the i-th round key. To maximize the RX probability of the i+1-th round, δi+1,L should have a lower Hamming weight. Because (25)δi+1,L=δi,R⊕δi,z⊕δi,L<2⊕δi,K,where δi,z is the RXD of the output of the bitwise AND in the i-th round, we can choose δi,z for which minimizes the Hamming weight of δi+1,L. Note that minimizing the Hamming weight of δi+1,L does not always guarantee the best RXD trail; however, we searched for RXD trails with such conditions in mind.


## 3.3. Rotational-XOR-Differences Trails of Simon

Putting the aforementioned considerations together, we searched for RXD trails with a high probability for Simon-32/64, 48/72, 48/96, 64/96, and 64/128. Initially, we let the pairs of both intermediate value and key state of the starting round have theδ values of Hamming weight 0 or 1. We then searched for the RXD trail with the maximum probability for each number of rounds by adding rounds forward and backward, while varying the starting round.As a result, we can find numerous trails with the maximum probability for various starting round indices. Therefore, we can construct rectangle characteristics using short trails with high probabilities with considering the round indices.


## 4. Rotational Rectangle Attack on Simon

### 4.1. Rotational Rectangle Characteristic

In this section, we show that rotational-XOR-differences can be used to construct rectangle characteristics similar to differential characteristics by proving the following Theorem4.Theorem 4.
Lex and y be independent random variables and a1,a2,b1, and b2 be constants in F2n for some positive integer n. In addition, let x⊕a1,x⟶⊕a2 and y⊕b1,y⟶⊕b2 be RX pairs with δa=a1⟶⊕a2 and δb=b1⟶⊕b2. If x⊕a1,y⟶⊕b2 forms an RX pair with RXD δc, then y⊕b1,x⟶⊕a2 also forms an RX pair and its RXD is δd=δa⊕δb⊕δc.Proof.
Because we assumed thatx⊕a1,y⟶⊕b2 is an RX pair and that its RXD is δc, we can assume that(26)z⊕c1=x⊕a1,z⟶⊕c2=y⟶⊕b2,for a random variable z and for some constants c1 and c2 such that c1⟶⊕c2=δc.
We will show thaty⊕b1=z⊕d1,x⟶⊕a2=z⟶⊕d2 and d1⟶⊕d2=δa⊕δb⊕δc.
According to this assumption, we have(27)y⊕b2⟵=z⊕c2⟵,x⟶⊕a1⟶=z⟶⊕c1⟶.
Thus, we have(28)y⊕b1=z⊕c2⟵⊕b2⟵⊕b1,x⟶⊕a2=z⟶⊕c1⟶⊕a1⟶⊕a2.
Therefore, if we letd1=c2⟵⊕b2⟵⊕b1 and d2=c1⟶⊕a1⟶⊕a2, we then have(29)δd=d1⟶⊕d2=c2⊕b2⊕b1⟶⊕c1⟶⊕a1⟶⊕a2=δa⊕δb⊕δc.
Accordingly, the proof is complete.
With Theorem4 in mind, we introduce the rotational rectangle distinguisher as follows. Denote an encryption algorithm E with a key K by EK. Suppose that EK is a composition of E0K and E1K such that EK=E1K∘E0K. We have RXD trails δa⟶δb satisfied with probability p for E0 and δc⟶δd with probability q for E1.
Suppose thatP0,P1 and Q0,Q1 are plaintext pairs whose δ values are both δa. The probability that the pairs of intermediate values E0K0P0,E0K1P1 and E0K2Q0,E0K3Q1 are both RX pair and their δ values are both δb is p2.
According to Theorem4, if E0K0P0,E0K3Q1 is an RX pair and its RXD is δc′, then E0K2Q0,E0K1P1 is also an RX pair with RXD δc′⊕δa⊕δa=δc′. If δc=δc′, it holds(30)E1K0E0K0P0,E1K3E0K3Q1,E1K2E0K2Q0,E1K1E0K1P1,are both RX pairs with RXD δd with a probability of q2.
Because the probability thatδc=δc′ is 2−n for block length n, two RX pairs P0,P1 and Q0,Q1 with δa are transformed into two RX pairs:(31)E1K0E0K0P0,E1K1E0K1P1,E1K2E0K2Q0,E1K3E0K3Q1,according to EK0, EK1, EK2, and EK3 with a probability of p2⋅q2⋅2−n.
However, ifE is a random permutation, the probability that the resulting four values form two RX pairs both with the expected RXDs is 2−2n. Therefore, we can mount an RX rectangle attack when 2−2n<p2⋅q2⋅2−n.


### 4.2. Constructing RX Rectangle Distinguishers

We have found many RXD trails for each of the Simon parameters that correspond to the probabilities presented in Table2. Using these trails, we construct RX rectangle distinguishers by joining two RXD trails with consideration of round indices. As an example of Simon-32/64, we found that there exist eight-round RXD trails which start at eighth and sixteenth rounds. Therefore, we successfully combined them for the rectangle distinguisher with the maximum probability 2−6⋅2−62⋅2−32=2−56. However, for Simon-48/72, we did not find two eight-round trails that could be combined for a rectangle distinguisher to maximize the probability. Therefore, we use a nine-round trail starting at fifth round and a seven-round trail starting at fourteenth round for the rectangle distinguisher with a probability of 2−4⋅2−172⋅2−48=2−90. The number of rounds and the probability of the RX rectangle distinguisher for each of the Simon parameters are given in Table 3 and examples of RXD trails are presented in Tables 4 and 5.Table 2
Maximum probability of RXD trails for each number of rounds.
RoundSimon-32/64Simon-48/72Simon-48/96Simon-64/96Simon-64/1281∼511111612−412−4172−32−42−42−42−482−62−102−62−102−692−102−172−102−172−10102−142−202−162−242−16112−182−262−222−262−22122−222−322−292−322−29132−292−452−362−382−36142−342−522−432−452−4615——2−512−532−5416————2−6217————2−74Table 3
Combinations of trails for constructing the RX rectangle distinguisher.
Simon-Rounds (E0+E1=E)Probability32/648 + 8 = 162−6⋅2−62⋅2−32=2−5648/727 + 9 = 162−4⋅2−172⋅2−48=2−9048/969 + 9 = 182−10⋅2−102⋅2−48=2−88.64/968 + 9 = 172−10⋅2−172⋅2−64=2−11864/1289 + 10 = 192−10⋅2−162⋅2−64=2−116Table 4
RXD trails for rectangle distinguishers of Simon-32/64, 48/72, and 48/96.
Simon-32/64Simon-48/72Simon-48/96RoundRXDesRoundRXDesRoundRXDesRoundRoundRoundRoundRoundRoundStatesKeysStatesKeysStatesKeys80005801580015000005c50018f5000012000042c0011bc000039000000050005630000c000005a000071300001000004200000610000000000000700000230000c30000c1400000400001000000011000000000000800000100000200000615000000000004000004120000000000009000000000001000001160000000000000000001300000000000010000000000000000000170000000000000000001400000000000511000000000000000000180000000000000000001500050000f005120000000000000000041900000000000000000116f0110005—13000004000000c000052000000100000030000514c00015000004—21300001000001—160010004100051400000230000c30000521c00000900007100004170004001000001500000100000200000622800000c00000c000031800000004000416000000000001000001230000018000008000041900000000000017000000000000000000240000000000010000012000000000000018000000000000000000250000000000000000002100000000000019000000000000000004260000000000000000002200000000000120000004000000c00006270000000000000000002300010000300621c00016000004—280000000000000000042430020001—22——29000004000000c0000530c00015000004—Table 5
RXD trails for rectangle distinguishers of Simon-64/96 and 64/128.
Simon-64/96Simon-64/128RoundRXDesRoundRXDesRoundRoundRoundRoundStatesKeysStatesKeys153000000030000005f000000470000004200000118c00000001600000001300000003000000580000001000000042000000061700000001000000010000000590000000400000010000000001800000000000000010000000110000000000000000400000004190000000000000000000000001100000000000000000000000020000000000000000000000000120000000000000000000000002100000000000000000000000413000000000000000000000000220000000400000000c00000051400000000000000000000000223c000001500000004—15000000020000000060000005166000000d00000002—2300000006c5000014f500000016400000146000001260000002243000000c00000006a00000041700000041400000144000000225000000023000000c300000051800000010000000410000000526000000010000000200000006190000000400000010000000002700000000000000010000000120000000000000000400000004280000000000000000000000002100000000000000000000000029000000000000000000000000220000000000000000000000003000000000000000000000000423000000000000000000000000310000000400000000c00000052400000000000000000000000232c000001500000004—25000000020000000060000005266000000d00000002—


### 4.3. Key Recovery Attack and Complexity

In this section, we present the key recovery attack framework on Simon with block sizes of 32, 48, and 64 using the RX rectangle distinguishers.We assume the following:p and q denote the probabilities of RXD trails for E0 and E1, respectively, and p2⋅q2=2−m for each version of Simon. Therefore, the probabilities of RX rectangle distinguishers are 2−m+n.We addrt rounds on top and three rounds at the bottom of the distinguisher for each version of Simon. Thus, the numbers of attacked rounds are R=rd+rt+3, where rd is the number of rounds of distinguishers for each version of Simon. Consequently, we attack round-reduced Simon from the is-th round to the if=is+R−1-th round. The actual round indices of attacked rounds for each version of Simon can be found in Tables 4 and 5.We useN=2m+n+α/2+β plaintexts for adequate positive values α and β.δiL, δiR, and δiK denote the RXDs of the left half of an input, the right half of an input, and a round key of i-th round, respectively. δinitL||δinitR and δfinalLδfinalR are RXDs of an input and an output of the characteristic, respectively.


#### 4.3.1. Generation of Pairs

Because we addrt rounds on top, it is necessary to explain how to construct the quartets of the plaintexts for each key. We need to generate more than Nq=2m+n+α quartets to distinguish E from a random permutation when the expected number of right quartets is 2α. To generate more than Nq quartets, we need two sets of pairs which contains at least Np=2m+n+α/2 pairs.We generate the first set of pairs as follows. LetΩ be set of plaintexts. First, we select a random plaintext from Ω and let this value be x⊕a1 for a fixed a1. And then, we encrypt it for rt−1 rounds with a guessed subkey of K0 and let this value be y⊕b1. Next, we should define the intermediate value of the opposite side of a pair. By rotating y⊕b1 and adding an adequate RXD δ, the value is defined by y⟶⊕b1⟶⊕δ. Finally, we could have another plaintext of the pair by decrypting y⟶⊕b1⟶⊕δ for rt−1 rounds with subkeys of the related K1. If the decryption result which is considered as x⟶⊕a2 is in Ω again, then the two plaintexts and corresponding ciphertexts by K0 and K1, respectively, are regarded as an RX pair. Similarly, another set of pairs are generated from the Ω and subkeys of K2 and K3. The numbers of elements in Ω required to obtain Np pairs will be discussed later in terms of data complexity.


#### 4.3.2. Attack Procedure

The key recovery attack against Simon-n/k proceeds as follows. Let F denote the round function of Simon; i.e., Fx=x⋘2⊕x⋘1∧x⋘8. Note that we assume that rt=2 for Simon-48/72 and Simon-64/96; otherwise, rt=3.(1)
GenerateΩ of a sufficient size from the oracles.(2)
Guessrt−1n/2-bit subkeys rk0is,…,rk0is+rt−2 for K0, and for each guessed key, do the following:Calculate the corresponding related subkeysrk1is,…,rk1is+rt−2, rk2is,…,rk2is+rt−2, and rk3is,…,rk3is+rt−2, for K1, K2, and K3, respectively.For each elementxis in Ω, do the following:Encryptxis for rt−1 rounds with rk0is, …, rk0is+1 to obtain xis+rt−1 (rt−1round encryptions).Calculatexis+rt−1′ using xis+rt−1 and δinitL||δinitR.Decryptxis+rt−1′ for rt−1 rounds with rk1is, …, rk1is+1 to obtain xis′ (rt−1round decryptions).Ifxis′∈Ω, register xis,xis′ and their corresponding ciphertexts as a RX pair.For each elementyis in Ω, do the following:Encryptyis for rt−1 rounds with rk2is, …, rk2is+1 to obtain yis+rt−1 (rt−1round encryptions).Calculateyis+rt−1′ using yis+rt−1 and δinitL||δinitR.Decryptyis+rt−1′ for rt−1 rounds with rk3is, …, rk3is+1 to obtain yis′ (rt−1round decryptions).Ifyis′∈Ω, register yis,yis′ and their corresponding ciphertexts as a RX pair.Using two sets of pairs, construct a set of quartetsxis,xis′,yis,yis′, and for each quartet, do the following:For ciphertext pairsxif+1,yif+1′ and yif+1,xif+1′, calculate the δ values of Fxif+1,Fyif+1′ and Fyif+1,Fxif+1′. Using these values and δifK, calculate δif−1L. Then, first check that δfinalL is in the set of candidates for δif−1R calculated by δif−1L, δifL, and δif−1K. Second, check that δfinalR is in the set of candidates calculated for δfinalR by δif−1L, δif−2K, and δfinalL (filtering ratio2−2t0, three round decryptions).Guess then/2-bit key rk0if and calculate the related subkeys rk1if, rk2if, and rk3if, and for each guessed key, do the following:For the remaining quartets, decrypt one round forxif,xif′,yif,yif′. Using these values and δif−1K, calculate δif−2L and check that δif−2L=δfinalL. And check that δfinalR is in the set of candidates calculated for δfinalR by δif−1L, δif−2K, and δfinalL (filtering ratio2−2t1, three round decryptions).Guess then/2-bit key rk0if−1 and calculate the related subkeys rk1if−1, rk2if−1, and rk3if−1, and for each guessed keys, do the following:For the remaining quartets, decrypt one more round forxif−1,xif−1′,yif−1,yif−1′. Using δif−2K, calculate δif−2R and check δif−2R=δfinalR (filtering ratio2−2t2, two round decryptions).Increase the counter of the current guessed key by the number of remaining quartets.(3)
Sort the guessed keys by the number of remaining quartets and exhaustively search the remaining key bits using highly ranked guessed keys.The discard ratios for each filtering step are denoted byt0, t1, and t2. These would be determined by the exact RXDs of the characteristic and should satisfy t0+t1+t2<n.


#### 4.3.3. Data Complexity

The data complexity of this attack is estimated by the required number of elements inΩ. Using elements in Ω, we generate two sets of Np=2m+n+α/2 pairs so that we have Nq=2m+n+α quartets. Let l=m+n+α/2. We define pairs by choosing a text in Ω, encrypting it for the rt−1 round with a guessed key, adding some differences, and decrypting for rt−1 rounds with the related key. Therefore, we should assume that the processes after choosing a text are random permutations from 0,1n to 0,1n, for counting the required number of elements in Ω. The question is that if we have set Ω of random texts in 0,1n with 2l+β elements and a random permutation f of 0,1n, what is the condition of β such that we have more than 2l pairs x,fx where fx∈Ω. Because we assume that f is a random permutation,(32)Prfx∈Ω=2l+β2n=2l+β−n,for an x∈Ω. Therefore, the expected number of pairs that we could have is 2l+β×2l+β−n=22l+2β−n. Given that we would like to have more than 2l pairs, β should satisfy(33)22l+2β−n>2l.So, we could have a lower bound of theβ as follows:(34)n−l2<β.As we have assumed thatl=m+n+α/2, a straightforward computation gives the condition:(35)n−m−α4<β.Thus, if we choose the minimumβ, we can have the required number of pairs on average. Table 6 shows the data complexities of these attacks for each version of Simon.Table 6
Data and computational complexities for each version of Simon whenβ has the minimum value (α=2).
Simon-32/6448/7248/9664/9664/128n3248486464is539134if2623323428rt32323m2442405452R2221242225Data complexity (Ω)230.5247246.5262261.5Comp. complexity260.4269.1292.3291.82123.0


#### 4.3.4. Computational Complexity

At this stage, we calculate the computational complexities of this attack. At the beginning of the attack, we perform four rounds of encryption onN texts to define the pairs for each guessed n/2-bit key. We then filter out quartets with two rounds of decryption without key guessing. Next, we consume one round of encryption for each filtering step with n/2-bit key guessing. Finally, we should exhaustively search the remaining key bits. Therefore, we can estimate the computational complexity of this attack as follows while taking the above factors into account:(36)2rt−1n/2⋅4NR+3NpR+2n/2⋅2−2t0⋅3NpR+2n/2⋅2−2t0−2t1⋅2NpR.We have assumed thatN=2m+n+α/2+β and Np=2m+n+α/2. Therefore, if we apply these assumptions to equation (36), then we have the following formula for computational complexity:(37)1R2nrt+m+α+2β+4/2+3⋅2nrt+m+α/2+3⋅2nrt+1+m+α−4t0/2+2⋅2nrt+2+m+α−4t0−4t1/2.Table6 shows the computational complexities of these attacks as calculated using equation (37) along with the data complexities when α=2 and β has the minimum value. The filtering ratio t0, which is most crucial with regard to the computational complexity among the ratios, is affected by how many types of RXDs of the outputs that could be produced by the round function where δfinalL and a random δ value are the respective inputs. According to our investigation, t0>n/3 on average; thus, we assume that t0=t1=n/3.


#### 4.3.5. Signal-to-Noise Ratio and Success Probabilities

Similar to differential cryptanalysis, rotational cryptanalysis uses randomly selected dataset so the attack works with probability less than or equal to one. Thus, we should calculate the success probability of each attack to make sure the possibility of the attack. By an earlier literature [23], the success probability of differential cryptanalysis could be calculated using signal-to-noise (S/N) ratio. We adopt that methodology for calculating the success probability of our attacks. We use the following equation for estimating success probabilities:(38)PS=ΦμSN−Φ−11−2−aSN+1,where Φ is the cumulative distribution function of the standard normal distribution, μ denotes the number of right quartets, and we set the advantage a to 8. The S/N ratio SN is calculated as follows:(39)SN=2k0Pcharα0β0.In the above equation,k0 denotes the bit length of the target subkey, which is assumed to be equal to the bit length of the secret key. Pchar denotes probability of characteristic, which is 2−m+n. α0 is the average number of subkeys suggested by one analysed quartet. Since this attack generates Nq=2m+n+α quartets, α0=2k0/Nq. β0 is the ratio of filtering before key guessing but β0 is fixed to 1 for all attacks because there is no filtering before key guessing. Therefore, the S/N ratio SN is 2α, and thus, the success probability PS is 0.73 when α=2.


## 4.1. Rotational Rectangle Characteristic

In this section, we show that rotational-XOR-differences can be used to construct rectangle characteristics similar to differential characteristics by proving the following Theorem4.Theorem 4.
Lex and y be independent random variables and a1,a2,b1, and b2 be constants in F2n for some positive integer n. In addition, let x⊕a1,x⟶⊕a2 and y⊕b1,y⟶⊕b2 be RX pairs with δa=a1⟶⊕a2 and δb=b1⟶⊕b2. If x⊕a1,y⟶⊕b2 forms an RX pair with RXD δc, then y⊕b1,x⟶⊕a2 also forms an RX pair and its RXD is δd=δa⊕δb⊕δc.Proof.
Because we assumed thatx⊕a1,y⟶⊕b2 is an RX pair and that its RXD is δc, we can assume that(26)z⊕c1=x⊕a1,z⟶⊕c2=y⟶⊕b2,for a random variable z and for some constants c1 and c2 such that c1⟶⊕c2=δc.
We will show thaty⊕b1=z⊕d1,x⟶⊕a2=z⟶⊕d2 and d1⟶⊕d2=δa⊕δb⊕δc.
According to this assumption, we have(27)y⊕b2⟵=z⊕c2⟵,x⟶⊕a1⟶=z⟶⊕c1⟶.
Thus, we have(28)y⊕b1=z⊕c2⟵⊕b2⟵⊕b1,x⟶⊕a2=z⟶⊕c1⟶⊕a1⟶⊕a2.
Therefore, if we letd1=c2⟵⊕b2⟵⊕b1 and d2=c1⟶⊕a1⟶⊕a2, we then have(29)δd=d1⟶⊕d2=c2⊕b2⊕b1⟶⊕c1⟶⊕a1⟶⊕a2=δa⊕δb⊕δc.
Accordingly, the proof is complete.
With Theorem4 in mind, we introduce the rotational rectangle distinguisher as follows. Denote an encryption algorithm E with a key K by EK. Suppose that EK is a composition of E0K and E1K such that EK=E1K∘E0K. We have RXD trails δa⟶δb satisfied with probability p for E0 and δc⟶δd with probability q for E1.
Suppose thatP0,P1 and Q0,Q1 are plaintext pairs whose δ values are both δa. The probability that the pairs of intermediate values E0K0P0,E0K1P1 and E0K2Q0,E0K3Q1 are both RX pair and their δ values are both δb is p2.
According to Theorem4, if E0K0P0,E0K3Q1 is an RX pair and its RXD is δc′, then E0K2Q0,E0K1P1 is also an RX pair with RXD δc′⊕δa⊕δa=δc′. If δc=δc′, it holds(30)E1K0E0K0P0,E1K3E0K3Q1,E1K2E0K2Q0,E1K1E0K1P1,are both RX pairs with RXD δd with a probability of q2.
Because the probability thatδc=δc′ is 2−n for block length n, two RX pairs P0,P1 and Q0,Q1 with δa are transformed into two RX pairs:(31)E1K0E0K0P0,E1K1E0K1P1,E1K2E0K2Q0,E1K3E0K3Q1,according to EK0, EK1, EK2, and EK3 with a probability of p2⋅q2⋅2−n.
However, ifE is a random permutation, the probability that the resulting four values form two RX pairs both with the expected RXDs is 2−2n. Therefore, we can mount an RX rectangle attack when 2−2n<p2⋅q2⋅2−n.


## 4.2. Constructing RX Rectangle Distinguishers

We have found many RXD trails for each of the Simon parameters that correspond to the probabilities presented in Table2. Using these trails, we construct RX rectangle distinguishers by joining two RXD trails with consideration of round indices. As an example of Simon-32/64, we found that there exist eight-round RXD trails which start at eighth and sixteenth rounds. Therefore, we successfully combined them for the rectangle distinguisher with the maximum probability 2−6⋅2−62⋅2−32=2−56. However, for Simon-48/72, we did not find two eight-round trails that could be combined for a rectangle distinguisher to maximize the probability. Therefore, we use a nine-round trail starting at fifth round and a seven-round trail starting at fourteenth round for the rectangle distinguisher with a probability of 2−4⋅2−172⋅2−48=2−90. The number of rounds and the probability of the RX rectangle distinguisher for each of the Simon parameters are given in Table 3 and examples of RXD trails are presented in Tables 4 and 5.Table 2
Maximum probability of RXD trails for each number of rounds.
RoundSimon-32/64Simon-48/72Simon-48/96Simon-64/96Simon-64/1281∼511111612−412−4172−32−42−42−42−482−62−102−62−102−692−102−172−102−172−10102−142−202−162−242−16112−182−262−222−262−22122−222−322−292−322−29132−292−452−362−382−36142−342−522−432−452−4615——2−512−532−5416————2−6217————2−74Table 3
Combinations of trails for constructing the RX rectangle distinguisher.
Simon-Rounds (E0+E1=E)Probability32/648 + 8 = 162−6⋅2−62⋅2−32=2−5648/727 + 9 = 162−4⋅2−172⋅2−48=2−9048/969 + 9 = 182−10⋅2−102⋅2−48=2−88.64/968 + 9 = 172−10⋅2−172⋅2−64=2−11864/1289 + 10 = 192−10⋅2−162⋅2−64=2−116Table 4
RXD trails for rectangle distinguishers of Simon-32/64, 48/72, and 48/96.
Simon-32/64Simon-48/72Simon-48/96RoundRXDesRoundRXDesRoundRXDesRoundRoundRoundRoundRoundRoundStatesKeysStatesKeysStatesKeys80005801580015000005c50018f5000012000042c0011bc000039000000050005630000c000005a000071300001000004200000610000000000000700000230000c30000c1400000400001000000011000000000000800000100000200000615000000000004000004120000000000009000000000001000001160000000000000000001300000000000010000000000000000000170000000000000000001400000000000511000000000000000000180000000000000000001500050000f005120000000000000000041900000000000000000116f0110005—13000004000000c000052000000100000030000514c00015000004—21300001000001—160010004100051400000230000c30000521c00000900007100004170004001000001500000100000200000622800000c00000c000031800000004000416000000000001000001230000018000008000041900000000000017000000000000000000240000000000010000012000000000000018000000000000000000250000000000000000002100000000000019000000000000000004260000000000000000002200000000000120000004000000c00006270000000000000000002300010000300621c00016000004—280000000000000000042430020001—22——29000004000000c0000530c00015000004—Table 5
RXD trails for rectangle distinguishers of Simon-64/96 and 64/128.
Simon-64/96Simon-64/128RoundRXDesRoundRXDesRoundRoundRoundRoundStatesKeysStatesKeys153000000030000005f000000470000004200000118c00000001600000001300000003000000580000001000000042000000061700000001000000010000000590000000400000010000000001800000000000000010000000110000000000000000400000004190000000000000000000000001100000000000000000000000020000000000000000000000000120000000000000000000000002100000000000000000000000413000000000000000000000000220000000400000000c00000051400000000000000000000000223c000001500000004—15000000020000000060000005166000000d00000002—2300000006c5000014f500000016400000146000001260000002243000000c00000006a00000041700000041400000144000000225000000023000000c300000051800000010000000410000000526000000010000000200000006190000000400000010000000002700000000000000010000000120000000000000000400000004280000000000000000000000002100000000000000000000000029000000000000000000000000220000000000000000000000003000000000000000000000000423000000000000000000000000310000000400000000c00000052400000000000000000000000232c000001500000004—25000000020000000060000005266000000d00000002—


## 4.3. Key Recovery Attack and Complexity

In this section, we present the key recovery attack framework on Simon with block sizes of 32, 48, and 64 using the RX rectangle distinguishers.We assume the following:p and q denote the probabilities of RXD trails for E0 and E1, respectively, and p2⋅q2=2−m for each version of Simon. Therefore, the probabilities of RX rectangle distinguishers are 2−m+n.We addrt rounds on top and three rounds at the bottom of the distinguisher for each version of Simon. Thus, the numbers of attacked rounds are R=rd+rt+3, where rd is the number of rounds of distinguishers for each version of Simon. Consequently, we attack round-reduced Simon from the is-th round to the if=is+R−1-th round. The actual round indices of attacked rounds for each version of Simon can be found in Tables 4 and 5.We useN=2m+n+α/2+β plaintexts for adequate positive values α and β.δiL, δiR, and δiK denote the RXDs of the left half of an input, the right half of an input, and a round key of i-th round, respectively. δinitL||δinitR and δfinalLδfinalR are RXDs of an input and an output of the characteristic, respectively.


### 4.3.1. Generation of Pairs

Because we addrt rounds on top, it is necessary to explain how to construct the quartets of the plaintexts for each key. We need to generate more than Nq=2m+n+α quartets to distinguish E from a random permutation when the expected number of right quartets is 2α. To generate more than Nq quartets, we need two sets of pairs which contains at least Np=2m+n+α/2 pairs.We generate the first set of pairs as follows. LetΩ be set of plaintexts. First, we select a random plaintext from Ω and let this value be x⊕a1 for a fixed a1. And then, we encrypt it for rt−1 rounds with a guessed subkey of K0 and let this value be y⊕b1. Next, we should define the intermediate value of the opposite side of a pair. By rotating y⊕b1 and adding an adequate RXD δ, the value is defined by y⟶⊕b1⟶⊕δ. Finally, we could have another plaintext of the pair by decrypting y⟶⊕b1⟶⊕δ for rt−1 rounds with subkeys of the related K1. If the decryption result which is considered as x⟶⊕a2 is in Ω again, then the two plaintexts and corresponding ciphertexts by K0 and K1, respectively, are regarded as an RX pair. Similarly, another set of pairs are generated from the Ω and subkeys of K2 and K3. The numbers of elements in Ω required to obtain Np pairs will be discussed later in terms of data complexity.


### 4.3.2. Attack Procedure

The key recovery attack against Simon-n/k proceeds as follows. Let F denote the round function of Simon; i.e., Fx=x⋘2⊕x⋘1∧x⋘8. Note that we assume that rt=2 for Simon-48/72 and Simon-64/96; otherwise, rt=3.(1)
GenerateΩ of a sufficient size from the oracles.(2)
Guessrt−1n/2-bit subkeys rk0is,…,rk0is+rt−2 for K0, and for each guessed key, do the following:Calculate the corresponding related subkeysrk1is,…,rk1is+rt−2, rk2is,…,rk2is+rt−2, and rk3is,…,rk3is+rt−2, for K1, K2, and K3, respectively.For each elementxis in Ω, do the following:Encryptxis for rt−1 rounds with rk0is, …, rk0is+1 to obtain xis+rt−1 (rt−1round encryptions).Calculatexis+rt−1′ using xis+rt−1 and δinitL||δinitR.Decryptxis+rt−1′ for rt−1 rounds with rk1is, …, rk1is+1 to obtain xis′ (rt−1round decryptions).Ifxis′∈Ω, register xis,xis′ and their corresponding ciphertexts as a RX pair.For each elementyis in Ω, do the following:Encryptyis for rt−1 rounds with rk2is, …, rk2is+1 to obtain yis+rt−1 (rt−1round encryptions).Calculateyis+rt−1′ using yis+rt−1 and δinitL||δinitR.Decryptyis+rt−1′ for rt−1 rounds with rk3is, …, rk3is+1 to obtain yis′ (rt−1round decryptions).Ifyis′∈Ω, register yis,yis′ and their corresponding ciphertexts as a RX pair.Using two sets of pairs, construct a set of quartetsxis,xis′,yis,yis′, and for each quartet, do the following:For ciphertext pairsxif+1,yif+1′ and yif+1,xif+1′, calculate the δ values of Fxif+1,Fyif+1′ and Fyif+1,Fxif+1′. Using these values and δifK, calculate δif−1L. Then, first check that δfinalL is in the set of candidates for δif−1R calculated by δif−1L, δifL, and δif−1K. Second, check that δfinalR is in the set of candidates calculated for δfinalR by δif−1L, δif−2K, and δfinalL (filtering ratio2−2t0, three round decryptions).Guess then/2-bit key rk0if and calculate the related subkeys rk1if, rk2if, and rk3if, and for each guessed key, do the following:For the remaining quartets, decrypt one round forxif,xif′,yif,yif′. Using these values and δif−1K, calculate δif−2L and check that δif−2L=δfinalL. And check that δfinalR is in the set of candidates calculated for δfinalR by δif−1L, δif−2K, and δfinalL (filtering ratio2−2t1, three round decryptions).Guess then/2-bit key rk0if−1 and calculate the related subkeys rk1if−1, rk2if−1, and rk3if−1, and for each guessed keys, do the following:For the remaining quartets, decrypt one more round forxif−1,xif−1′,yif−1,yif−1′. Using δif−2K, calculate δif−2R and check δif−2R=δfinalR (filtering ratio2−2t2, two round decryptions).Increase the counter of the current guessed key by the number of remaining quartets.(3)
Sort the guessed keys by the number of remaining quartets and exhaustively search the remaining key bits using highly ranked guessed keys.The discard ratios for each filtering step are denoted byt0, t1, and t2. These would be determined by the exact RXDs of the characteristic and should satisfy t0+t1+t2<n.


### 4.3.3. Data Complexity

The data complexity of this attack is estimated by the required number of elements inΩ. Using elements in Ω, we generate two sets of Np=2m+n+α/2 pairs so that we have Nq=2m+n+α quartets. Let l=m+n+α/2. We define pairs by choosing a text in Ω, encrypting it for the rt−1 round with a guessed key, adding some differences, and decrypting for rt−1 rounds with the related key. Therefore, we should assume that the processes after choosing a text are random permutations from 0,1n to 0,1n, for counting the required number of elements in Ω. The question is that if we have set Ω of random texts in 0,1n with 2l+β elements and a random permutation f of 0,1n, what is the condition of β such that we have more than 2l pairs x,fx where fx∈Ω. Because we assume that f is a random permutation,(32)Prfx∈Ω=2l+β2n=2l+β−n,for an x∈Ω. Therefore, the expected number of pairs that we could have is 2l+β×2l+β−n=22l+2β−n. Given that we would like to have more than 2l pairs, β should satisfy(33)22l+2β−n>2l.So, we could have a lower bound of theβ as follows:(34)n−l2<β.As we have assumed thatl=m+n+α/2, a straightforward computation gives the condition:(35)n−m−α4<β.Thus, if we choose the minimumβ, we can have the required number of pairs on average. Table 6 shows the data complexities of these attacks for each version of Simon.Table 6
Data and computational complexities for each version of Simon whenβ has the minimum value (α=2).
Simon-32/6448/7248/9664/9664/128n3248486464is539134if2623323428rt32323m2442405452R2221242225Data complexity (Ω)230.5247246.5262261.5Comp. complexity260.4269.1292.3291.82123.0


### 4.3.4. Computational Complexity

At this stage, we calculate the computational complexities of this attack. At the beginning of the attack, we perform four rounds of encryption onN texts to define the pairs for each guessed n/2-bit key. We then filter out quartets with two rounds of decryption without key guessing. Next, we consume one round of encryption for each filtering step with n/2-bit key guessing. Finally, we should exhaustively search the remaining key bits. Therefore, we can estimate the computational complexity of this attack as follows while taking the above factors into account:(36)2rt−1n/2⋅4NR+3NpR+2n/2⋅2−2t0⋅3NpR+2n/2⋅2−2t0−2t1⋅2NpR.We have assumed thatN=2m+n+α/2+β and Np=2m+n+α/2. Therefore, if we apply these assumptions to equation (36), then we have the following formula for computational complexity:(37)1R2nrt+m+α+2β+4/2+3⋅2nrt+m+α/2+3⋅2nrt+1+m+α−4t0/2+2⋅2nrt+2+m+α−4t0−4t1/2.Table6 shows the computational complexities of these attacks as calculated using equation (37) along with the data complexities when α=2 and β has the minimum value. The filtering ratio t0, which is most crucial with regard to the computational complexity among the ratios, is affected by how many types of RXDs of the outputs that could be produced by the round function where δfinalL and a random δ value are the respective inputs. According to our investigation, t0>n/3 on average; thus, we assume that t0=t1=n/3.


### 4.3.5. Signal-to-Noise Ratio and Success Probabilities

Similar to differential cryptanalysis, rotational cryptanalysis uses randomly selected dataset so the attack works with probability less than or equal to one. Thus, we should calculate the success probability of each attack to make sure the possibility of the attack. By an earlier literature [23], the success probability of differential cryptanalysis could be calculated using signal-to-noise (S/N) ratio. We adopt that methodology for calculating the success probability of our attacks. We use the following equation for estimating success probabilities:(38)PS=ΦμSN−Φ−11−2−aSN+1,where Φ is the cumulative distribution function of the standard normal distribution, μ denotes the number of right quartets, and we set the advantage a to 8. The S/N ratio SN is calculated as follows:(39)SN=2k0Pcharα0β0.In the above equation,k0 denotes the bit length of the target subkey, which is assumed to be equal to the bit length of the secret key. Pchar denotes probability of characteristic, which is 2−m+n. α0 is the average number of subkeys suggested by one analysed quartet. Since this attack generates Nq=2m+n+α quartets, α0=2k0/Nq. β0 is the ratio of filtering before key guessing but β0 is fixed to 1 for all attacks because there is no filtering before key guessing. Therefore, the S/N ratio SN is 2α, and thus, the success probability PS is 0.73 when α=2.


## 4.3.1. Generation of Pairs

Because we addrt rounds on top, it is necessary to explain how to construct the quartets of the plaintexts for each key. We need to generate more than Nq=2m+n+α quartets to distinguish E from a random permutation when the expected number of right quartets is 2α. To generate more than Nq quartets, we need two sets of pairs which contains at least Np=2m+n+α/2 pairs.We generate the first set of pairs as follows. LetΩ be set of plaintexts. First, we select a random plaintext from Ω and let this value be x⊕a1 for a fixed a1. And then, we encrypt it for rt−1 rounds with a guessed subkey of K0 and let this value be y⊕b1. Next, we should define the intermediate value of the opposite side of a pair. By rotating y⊕b1 and adding an adequate RXD δ, the value is defined by y⟶⊕b1⟶⊕δ. Finally, we could have another plaintext of the pair by decrypting y⟶⊕b1⟶⊕δ for rt−1 rounds with subkeys of the related K1. If the decryption result which is considered as x⟶⊕a2 is in Ω again, then the two plaintexts and corresponding ciphertexts by K0 and K1, respectively, are regarded as an RX pair. Similarly, another set of pairs are generated from the Ω and subkeys of K2 and K3. The numbers of elements in Ω required to obtain Np pairs will be discussed later in terms of data complexity.


## 4.3.2. Attack Procedure

The key recovery attack against Simon-n/k proceeds as follows. Let F denote the round function of Simon; i.e., Fx=x⋘2⊕x⋘1∧x⋘8. Note that we assume that rt=2 for Simon-48/72 and Simon-64/96; otherwise, rt=3.(1)
GenerateΩ of a sufficient size from the oracles.(2)
Guessrt−1n/2-bit subkeys rk0is,…,rk0is+rt−2 for K0, and for each guessed key, do the following:Calculate the corresponding related subkeysrk1is,…,rk1is+rt−2, rk2is,…,rk2is+rt−2, and rk3is,…,rk3is+rt−2, for K1, K2, and K3, respectively.For each elementxis in Ω, do the following:Encryptxis for rt−1 rounds with rk0is, …, rk0is+1 to obtain xis+rt−1 (rt−1round encryptions).Calculatexis+rt−1′ using xis+rt−1 and δinitL||δinitR.Decryptxis+rt−1′ for rt−1 rounds with rk1is, …, rk1is+1 to obtain xis′ (rt−1round decryptions).Ifxis′∈Ω, register xis,xis′ and their corresponding ciphertexts as a RX pair.For each elementyis in Ω, do the following:Encryptyis for rt−1 rounds with rk2is, …, rk2is+1 to obtain yis+rt−1 (rt−1round encryptions).Calculateyis+rt−1′ using yis+rt−1 and δinitL||δinitR.Decryptyis+rt−1′ for rt−1 rounds with rk3is, …, rk3is+1 to obtain yis′ (rt−1round decryptions).Ifyis′∈Ω, register yis,yis′ and their corresponding ciphertexts as a RX pair.Using two sets of pairs, construct a set of quartetsxis,xis′,yis,yis′, and for each quartet, do the following:For ciphertext pairsxif+1,yif+1′ and yif+1,xif+1′, calculate the δ values of Fxif+1,Fyif+1′ and Fyif+1,Fxif+1′. Using these values and δifK, calculate δif−1L. Then, first check that δfinalL is in the set of candidates for δif−1R calculated by δif−1L, δifL, and δif−1K. Second, check that δfinalR is in the set of candidates calculated for δfinalR by δif−1L, δif−2K, and δfinalL (filtering ratio2−2t0, three round decryptions).Guess then/2-bit key rk0if and calculate the related subkeys rk1if, rk2if, and rk3if, and for each guessed key, do the following:For the remaining quartets, decrypt one round forxif,xif′,yif,yif′. Using these values and δif−1K, calculate δif−2L and check that δif−2L=δfinalL. And check that δfinalR is in the set of candidates calculated for δfinalR by δif−1L, δif−2K, and δfinalL (filtering ratio2−2t1, three round decryptions).Guess then/2-bit key rk0if−1 and calculate the related subkeys rk1if−1, rk2if−1, and rk3if−1, and for each guessed keys, do the following:For the remaining quartets, decrypt one more round forxif−1,xif−1′,yif−1,yif−1′. Using δif−2K, calculate δif−2R and check δif−2R=δfinalR (filtering ratio2−2t2, two round decryptions).Increase the counter of the current guessed key by the number of remaining quartets.(3)
Sort the guessed keys by the number of remaining quartets and exhaustively search the remaining key bits using highly ranked guessed keys.The discard ratios for each filtering step are denoted byt0, t1, and t2. These would be determined by the exact RXDs of the characteristic and should satisfy t0+t1+t2<n.


## 4.3.3. Data Complexity

The data complexity of this attack is estimated by the required number of elements inΩ. Using elements in Ω, we generate two sets of Np=2m+n+α/2 pairs so that we have Nq=2m+n+α quartets. Let l=m+n+α/2. We define pairs by choosing a text in Ω, encrypting it for the rt−1 round with a guessed key, adding some differences, and decrypting for rt−1 rounds with the related key. Therefore, we should assume that the processes after choosing a text are random permutations from 0,1n to 0,1n, for counting the required number of elements in Ω. The question is that if we have set Ω of random texts in 0,1n with 2l+β elements and a random permutation f of 0,1n, what is the condition of β such that we have more than 2l pairs x,fx where fx∈Ω. Because we assume that f is a random permutation,(32)Prfx∈Ω=2l+β2n=2l+β−n,for an x∈Ω. Therefore, the expected number of pairs that we could have is 2l+β×2l+β−n=22l+2β−n. Given that we would like to have more than 2l pairs, β should satisfy(33)22l+2β−n>2l.So, we could have a lower bound of theβ as follows:(34)n−l2<β.As we have assumed thatl=m+n+α/2, a straightforward computation gives the condition:(35)n−m−α4<β.Thus, if we choose the minimumβ, we can have the required number of pairs on average. Table 6 shows the data complexities of these attacks for each version of Simon.Table 6
Data and computational complexities for each version of Simon whenβ has the minimum value (α=2).
Simon-32/6448/7248/9664/9664/128n3248486464is539134if2623323428rt32323m2442405452R2221242225Data complexity (Ω)230.5247246.5262261.5Comp. complexity260.4269.1292.3291.82123.0


## 4.3.4. Computational Complexity

At this stage, we calculate the computational complexities of this attack. At the beginning of the attack, we perform four rounds of encryption onN texts to define the pairs for each guessed n/2-bit key. We then filter out quartets with two rounds of decryption without key guessing. Next, we consume one round of encryption for each filtering step with n/2-bit key guessing. Finally, we should exhaustively search the remaining key bits. Therefore, we can estimate the computational complexity of this attack as follows while taking the above factors into account:(36)2rt−1n/2⋅4NR+3NpR+2n/2⋅2−2t0⋅3NpR+2n/2⋅2−2t0−2t1⋅2NpR.We have assumed thatN=2m+n+α/2+β and Np=2m+n+α/2. Therefore, if we apply these assumptions to equation (36), then we have the following formula for computational complexity:(37)1R2nrt+m+α+2β+4/2+3⋅2nrt+m+α/2+3⋅2nrt+1+m+α−4t0/2+2⋅2nrt+2+m+α−4t0−4t1/2.Table6 shows the computational complexities of these attacks as calculated using equation (37) along with the data complexities when α=2 and β has the minimum value. The filtering ratio t0, which is most crucial with regard to the computational complexity among the ratios, is affected by how many types of RXDs of the outputs that could be produced by the round function where δfinalL and a random δ value are the respective inputs. According to our investigation, t0>n/3 on average; thus, we assume that t0=t1=n/3.


## 4.3.5. Signal-to-Noise Ratio and Success Probabilities

Similar to differential cryptanalysis, rotational cryptanalysis uses randomly selected dataset so the attack works with probability less than or equal to one. Thus, we should calculate the success probability of each attack to make sure the possibility of the attack. By an earlier literature [23], the success probability of differential cryptanalysis could be calculated using signal-to-noise (S/N) ratio. We adopt that methodology for calculating the success probability of our attacks. We use the following equation for estimating success probabilities:(38)PS=ΦμSN−Φ−11−2−aSN+1,where Φ is the cumulative distribution function of the standard normal distribution, μ denotes the number of right quartets, and we set the advantage a to 8. The S/N ratio SN is calculated as follows:(39)SN=2k0Pcharα0β0.In the above equation,k0 denotes the bit length of the target subkey, which is assumed to be equal to the bit length of the secret key. Pchar denotes probability of characteristic, which is 2−m+n. α0 is the average number of subkeys suggested by one analysed quartet. Since this attack generates Nq=2m+n+α quartets, α0=2k0/Nq. β0 is the ratio of filtering before key guessing but β0 is fixed to 1 for all attacks because there is no filtering before key guessing. Therefore, the S/N ratio SN is 2α, and thus, the success probability PS is 0.73 when α=2.


## 5. Conclusion

In this paper, we study how to apply cryptanalysis based on the rotational-XOR-difference approach to the block cipher Simon. We present a closed formula that is used to calculate the transition probability of an RXD trail according to the bitwise AND operation. Moreover, we demonstrate that we could construct the rectangle characteristic using RXD trails in a manner similar to how ordinary differential trails are used. Consequently, we could define a new RX rectangle attack and mount it onto some instances of the Simon family. Although our results are not the best for Simon to date, it is the first result for rotational cryptanalysis applied to a non-ARX cipher and it would be a worthwhile endeavor to attempt to improve our approach or to apply to other ciphers based on bitwise AND.


## 6. RXD Trails for Rectangle Distinguishers

Tables4 and 5 show actual RXD trails for which establish the rectangle distinguishers for each version of Simon, presented in Table 3.



---

*Source: 5968584-2020-07-22.xml*