# Security Cryptanalysis of NUX for the Internet of Things

Authors: Yu Liu; Xiaolei Liu; Yanmin Zhao
Journal: Security and Communication Networks
 (2019)

---

## Abstract

In order to adopt the restricted environment, such as radio frequency identification technology or sensor networking, which are the important components of the Internet of Things, lightweight block ciphers are designed. NUX is a 31-round iterative ultralightweight cipher proposed by Bansodet al. In this paper, we examine the resistance of NUX to differential and linear analysis and search for 1~31-round differential characteristics and linear approximations. In design specification, authors claimed that 25-round NUX is resistant to differential and linear attack. However, we can successfully perform 29-round differential attack on NUX with the 22-round differential characteristic found in this paper, which is 4 rounds more than the limitation given by authors. Furthermore, we present the key recovery attack on 22-round NUX using a 19-round linear approximation determined in this paper. Besides, distinguishing attack, whose distinguisher is built utilizing the property of differential propagation through NUX, is implemented on full NUX with data complexity 8.


---

## Body

## 1. Introduction

The Internet of Things is defined as a variety of devices and technologies such as sensors, radio frequency identification (RFID) technology, global positioning systems, infrared sensors, laser scanners, and gas sensors. Its essence is to use RFID technology to realize the automatic identification of items, the interconnection, and sharing of information through the computer Internet. In this kind of new cryptography environment, RFID technology and sensor networking have similar properties, such as weak computation abilities, small storage spaces, and strict power constraints. Therefore, traditional block ciphers are not suitable for this kind of extremely constrained environment. Hence, lightweight block ciphers are put forward for restricted environment and have shown importance in various applications. Recently, copious lightweight block ciphers are designed to maintain security under limited resource conditions, such as PRESENT [1], LBlock [2], and PRINCE [3]. And many cryptographers are concerned about the security of lightweight block ciphers.Differential analysis, which is a chosen-plaintext attack, is proposed by Biham and Shamir to analyze DES [4]. Differential analysis studies probability propagation property in the encryption/decryption process. This method seeks for high probability differential characteristics to perform a distinguishing attack or a key-recovery attack. Later, linear analysis, which is the duality of differential analysis and is a known-plaintext attack, is presented by Matsui in EUROCRYPT’93 [5]. Similarly, linear analysis studies the linear relationship between plaintexts and ciphertexts and finds linear approximations with high probability to build a distinguisher or carry out a key-recovery attack. In addition, these two methods are the most popular cryptanalysis methods nowadays. They have been used to analyze many ciphers and should be taken into consideration for designing a new cipher scheme [6–11].NUX is a 31-round iterative lightweight block cipher proposed by Bansodet al. [12] which adopts generalized Feistel structure. And it supports 64-bit blocks and 80/128-bit keys. For the version with 128-bit key, the author pointed out that NUX needs 1022 GEs, which is less than all existing ciphers. In terms of security, they expected that NUX could resist differential/linear analysis. They examined the resistance of NUX against differential/linear cryptanalysis. At last, they showed that NUX cipher with no less than 25 round is enough to resist linear or differential attack. Besides, a biclique attack on NUX is presented in [12].Our Contribution  (i)
1~31-round differential characteristics of NUX are searched for, and 10 25-round differential characteristics are found with probability 2-71, which are better than the one with probability limitation 2-90 given in the design script, shown in Table 1. (ii)
The resistance to the linear analysis for1~31-round NUX is examined, and 48 25-round linear approximations are presented with absolute value of bias to be 2-41 better than the limitation on bias presented in the design script, which is 2-66, depicted in Table 1. (iii)
For full NUX, the probability of the best differential characteristic is2-88, and the absolute value of bias for the best linear approximation is 2-50, which are described in Table 1. (iv)
Using 22-round differential characteristic with probability2-58 obtained in this paper, 29-round differential attack is performed with time, data, and memory complexity to be 2121.73 29-round encryptions and 261 and 296 bytes, respectively. Furthermore, based on a 19-round linear approximation with bias to be 2-30, 25-round linear attack is executed with time complexity 2126 25-round encryptions, data complexity 263.7, and memory complexity 270 bytes. Till now, these two attacks are the best differential attack and best linear attack, respectively. A summary of our attacks is given in Table 2. (v)
Utilizing the property of difference propagation through NUX, distinguishing attack can be implemented on full NUX with data complexity 8, which is depicted in Table2.Table 1
Comparison of tails on NUX.
Method Rounds Probability/bias Reference Differential 25 2 - 90 [12] 25 2 - 71 Section3.1 31 2 - 88 Section3.1  Linear 25 2 - 66 [12] 25 2 - 41 Section4.1 31 2 - 50 Section4.1Table 2
Summary of attacks on NUX.
Attack type Rounds Time Date Memory (Bytes) Reference Differential 25 - 290 - [12] 29 2 121.73 2 61 2 96 Section3.2  Linear 25 - 2132 - [12] 25 2 126 2 63.7 2 70 Section4.2  Distinguishing 31 8 8 0 Section5The organization of the paper is as follows. The notations and description of NUX are given in Section2. Section 3 shows the differential characteristics and differential attack on 29-round NUX. In Section 4, the linear approximations and linear attack on 25-round NUX are introduced. Section 5 describes distinguishing attacks between full NUX and random permutations. Finally, Section 6 concludes the paper.


## 2. Preliminaries

This section will list notations and operations used in this paper and describe NUX.


### 2.1. Notations and Operations

(i)
{ 0,1 } n: The set of strings with n bits length. (ii)
x [ i ]: The i-th bit of x, if x∈{0,1}n. (iii)
x [ i : j ]: The j-th bit to i-th bit of x, if x∈{0,1}n. (iv)
x [ i , j ]: The i-th and j-th bits of x, if x∈{0,1}n. (v)
x ∥ y: Concatenation of x and y, if x,y∈{0,1}n. (vi)
⋙: Right cyclic shift operation. (vii)
⋘: Left cyclic shift operation. (viii)
⊕: XOR operation.


### 2.2. Description of NUX

NUX is a 31-round ultralightweight cipher based on generalized Feistel network. It supports a key length of 128/80 bits and a block length of 64 bits. The round function is illustrated in Figure1.Figure 1
The round function of NUX.There are two F-functionsF1 and F2, which are constructed by four 4×4 S-boxes and a circular shift operator. The S-box is represented in Table 3. Then F1 and F2 can be depicted as follows: (1)F1x=Sx7:4∥Sx3:0∥Sx15:12∥Sx11:8,F2x=Sx2:0∥x15∥Sx14:11∥Sx10:7∥Sx6:3.Table 3
S-box used in NUX.
x 0 1 2 3 4 5 6 7 8 9 a b c d e f  S(x) e 7 8 4 1 9 2 f 5 a b 0 6 c d 3The 64-bit input of thei-th round, Xi, is divided into 4 blocks of 16 bits, named Xi4, Xi3, Xi2, and Xi1, respectively. (2)Xi=Xi4∥Xi3∥Xi2∥Xi1,and then there are the following formulas: (3)Xi+14=PXi2,Xi+13=PXi1⋙3⊕F1Xi2⊕rki′,Xi+12=PXi4⋘8⊕F2Xi3⊕rki,Xi+11=PXi3,where P is a 16-bit permutation, which is depicted in Table 4.Table 4
Bit permutation table P in NUX.
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  P(i) 15 11 7 3 2 14 10 6 5 1 13 9 8 4 0 12After 31 rounds, the ciphertext will be acquired asX314∥X313∥X312∥X311. The key schedule is omitted and interested readers are referred to [12] for more details about NUX.


## 2.1. Notations and Operations

(i)
{ 0,1 } n: The set of strings with n bits length. (ii)
x [ i ]: The i-th bit of x, if x∈{0,1}n. (iii)
x [ i : j ]: The j-th bit to i-th bit of x, if x∈{0,1}n. (iv)
x [ i , j ]: The i-th and j-th bits of x, if x∈{0,1}n. (v)
x ∥ y: Concatenation of x and y, if x,y∈{0,1}n. (vi)
⋙: Right cyclic shift operation. (vii)
⋘: Left cyclic shift operation. (viii)
⊕: XOR operation.


## 2.2. Description of NUX

NUX is a 31-round ultralightweight cipher based on generalized Feistel network. It supports a key length of 128/80 bits and a block length of 64 bits. The round function is illustrated in Figure1.Figure 1
The round function of NUX.There are two F-functionsF1 and F2, which are constructed by four 4×4 S-boxes and a circular shift operator. The S-box is represented in Table 3. Then F1 and F2 can be depicted as follows: (1)F1x=Sx7:4∥Sx3:0∥Sx15:12∥Sx11:8,F2x=Sx2:0∥x15∥Sx14:11∥Sx10:7∥Sx6:3.Table 3
S-box used in NUX.
x 0 1 2 3 4 5 6 7 8 9 a b c d e f  S(x) e 7 8 4 1 9 2 f 5 a b 0 6 c d 3The 64-bit input of thei-th round, Xi, is divided into 4 blocks of 16 bits, named Xi4, Xi3, Xi2, and Xi1, respectively. (2)Xi=Xi4∥Xi3∥Xi2∥Xi1,and then there are the following formulas: (3)Xi+14=PXi2,Xi+13=PXi1⋙3⊕F1Xi2⊕rki′,Xi+12=PXi4⋘8⊕F2Xi3⊕rki,Xi+11=PXi3,where P is a 16-bit permutation, which is depicted in Table 4.Table 4
Bit permutation table P in NUX.
i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15  P(i) 15 11 7 3 2 14 10 6 5 1 13 9 8 4 0 12After 31 rounds, the ciphertext will be acquired asX314∥X313∥X312∥X311. The key schedule is omitted and interested readers are referred to [12] for more details about NUX.


## 3. Differential Attack on 29-Round NUX

In this section, how to search for differential characteristics of NUX will be described. And then a key-recovery attack is conducted on 29-round NUX.


### 3.1. Differential Characteristics of NUX

To search for the differential characteristic of NUX, the different propagation between round functions should be considered. And how differences propagate through S-boxes should also be taken into account. When a difference passes through an S-box, the output difference and probability are determined by looking up the XOR difference distribution table (DDT) of the S-box.Algorithm1 is designed to search for differential characteristics of NUX, and notations used in this algorithm are depicted in Figure 2. From the structure of NUX, it is obvious that the probability of one round can be 1; that is, all the 8 S-boxes are passive. So a special n-1-round differential characteristic, (Δ03=Δ02=0), is chosen, and one-round differential characteristic with probability 1 is added to catch n-round differential characteristics. Meanwhile, Δi4 and Δi3, which lie in the two branches on the left side, will not affect Δi2 and Δi1, the two branches on the right side, during propagation in NUX. So differences of two branches on the left or right are set to 0, and the difference propagation in the other two branches will be focused on during the encryption process. In this way, the number of active S-boxes is always no more than 4 in one round, which can make the probability of the differential characteristic as large as possible. The results of our search algorithm are listed in Table 5.Table 5
Differential characteristics of NUX.
Rounds Probability Number of tails 2 2 - 2 192 3 2 - 4 56 4 2 - 6 4 5 2 - 7 1 6 2 - 9 2 7 2 - 11 2 8 2 - 15 8 9 2 - 15 1 10 2 - 20 16 11 2 - 24 24 12 2 - 28 4 13 2 - 31 8 14 2 - 37 4 15 2 - 41 18 16 2 - 45 2 17 2 - 46 1 18 2 - 49 4 19 2 - 52 4 20 2 - 53 2 21 2 - 58 48 22 2 - 58 2 23 2 - 63 32 24 2 - 67 49 25 2 - 71 10 26 2 - 73 4 27 2 - 75 4 28 2 - 79 16 29 2 - 79 2 30 2 - 84 32 31 2 - 88 48Algorithm 1:Algorithm for differential characteristic on NUX.
Input: S-box S, Probability threshold PrLim[30]. Output: A differential trail with the best probability. ( 1 ) Generate the DDT of S-box. ( 2 ) Store all 2, 4 and the corresponding input/output differences in DDT in the table DDTP ( 3 )  for Each of 8 S-boxes in the first round do ( 4 )  for all non-zero entities in DDT do ( 5 )    if S-box is in F2  then ( 6 )     Δ13=ΔX1h⋘3, Δ14=Δ12=Δ11=0. ( 7 )     Store them in Rin[1]. ( 8 )    else ( 9 )     Δ12=ΔX1l⋙8, Δ14=Δ13=Δ11=0. ( 10 )     Store them in Rin[1]. ( 11 )    Calculate Δ04, Δ03, Δ02, Δ01, and store them in Rin[0]. ( 12 )    Calculate Δ24, Δ23, Δ22, Δ21, and store them in Rin[2]. ( 13 )    The probability is recorded as Pr[1]. ( 14 )  for  i←2 to 30  do ( 15 )    if  Δi4=Δi3=0  then ( 16 )    ΔXil=Δi2⋘8 ( 17 )    Travel DDTP to get ΔYil and its corresponding probability PrRnd ( 18 )    else if  Δi2=Δi1=0  then ( 19 )    ΔXih=Δi3⋙3 ( 20 )    Travel DDTP to get ΔYih and the corresponding probability PrRnd ( 21 )    Keep Pr[i-1]×PrRnd, which greater than threshold PrLim[i] ( 22 )    Calculate Δi+14, Δi+13, Δi+12, Δi+11, and store them in Rin[i+1]. ( 23 )    Pr[i]⇐Pr[i-1]×PrRnd ( 24 )  for Each of 8 S-boxes in the first round do ( 25 )  for all non-zero entities in DDT do ( 26 )    Find the largest Pr[i] and store it in PrMax[i] ( 27 )    Output different characteristics with probability PrMax[i]Figure 2
Differential representation of NUX.Furthermore, the minimal numbers of active S-boxes of 1~5-round differential characteristics are shown in the design manuscript [12]. So the minimal number of active S-boxes is also studied, and the minimum active S-boxes of 4 5-round differential characteristics are less than the ones given in [12], which are presented in Table 6.Table 6
Minimal number of active S-boxes from differential characteristic.
Number of active S-boxes Reference Rounds 1 2 3 4 5 [12] 0 1 2 5 9 Section3.1 0 1 2 3 3


### 3.2. Differential Attack on NUX

A 22-round differential characteristic is chosen with probability to be2-58, which is shown in Table 7, and 7 rounds are extended forward. The description is given in Figure 3. There are Δ04=0x0400, Δ223=0x2080, and Δ03=Δ02=Δ01=Δ224=Δ222=Δ221=0x0000 according to the 22-round differential distinguisher. Then Δ234=Δ233=0x0000, Δ231=0x0050, and Δ232 satisfy the form as (00∗∗∗00∗∗∗000∗∗0), where ∗∈{0,1} can be deduced. And the output difference of the 28-th round is Δ294=Δ293=0x0000. X232, X232′, X231, and X231′ can be gotten by 6-round decryption. So rk23′, rk24, rk25′, rk26, rk27′, and rk28 should be guessed and denoted by Kguess. The attack process is described as follows:(1)
CollectN pairs of plaintext (P,P′) satisfying P⊕P′=(Δ04,Δ03,Δ02,Δ01) and their corresponding ciphertext pairs (C,C′).(2)
Initialize232 counters V[0],V[1],…,V[232-1] and reset them.(3)
For each plaintext pair(P,P′), check whether its ciphertext pair (C,C′) satisfies (C⊕C′)[63:32]=0x00000000. If the ciphertext pair meets the formula, x=(C⊕C′)[31:0] and V[x]++.(4)
Initialize296 counters Vk[0],Vk[1],...,Vk[296-1] and reset them.(5)
Guess 96-bit keyKguess, and decrypt x to obtain X232, X232′, X231, and X231′. Check whether X232⊕X232′ and X231⊕X231′ are equal to Δ232 and Δ231. If the conditions are met, then let y=X232∥X232′∥X231∥X231′.(6)
Usey to calculate X224⊕X224′ and X223⊕X223′. If X224⊕X224′=Δ224 and X223⊕X223′=Δ223, Vk[Kguess]++.(7)
Set advantagea to be 51, which implies that the top 245 absolute values in Vk are kept. For each remaining key, we guess the remaining 58-bit subkey and calculate the master key. Finally, we test the key by trail encryptions.Table 7
22-Round differential characteristic of NUX.
Roundsi Δ i 4 Δ i 3 Δ i 2 Δ i 1 Probability 0 0400 0000 0000 0000 1 1 0000 0000 0080 0000 2 - 3 2 0040 0001 0000 0000 2 - 2 3 0000 0000 0010 8000 2 - 3 4 0004 1000 0000 0000 2 - 2 5 0000 0000 0002 0100 2 - 2 6 0800 6002 0000 0000 2 - 5 7 0000 0000 003b 0811 2 - 5 8 c80c 2b30 0000 0000 2 - 7 9 0000 0000 0480 4236 2 - 5 10 2040 0600 0000 0000 2 - 3 11 0000 0000 0005 2002 2 - 2 12 8080 0003 0000 0000 2 - 2 13 0000 0000 0040 8800 2 - 2 14 0400 0030 0000 0000 2 - 2 15 0000 0000 0008 4004 2 - 3 16 0008 3000 0000 0000 2 - 2 17 0000 0000 0000 0110 1 18 0000 4800 0000 0000 2 - 3 19 0000 0000 0020 0201 2 - 2 20 4000 0500 0000 0000 2 - 3 21 0000 0000 0000 2020 1 22 0000 2080 0000 0000 ∗Figure 3
Differential attack of 29-round NUX.If setN=260, then about 228 pieces of data enter step (5), which means 2124 6-round encryptions, that is, 2121.7 29-round encryptions. The complexity of step (7) is 2103 29-round encryptions. So the total time complexity of this attack is about 2121.73 29-round encryptions.The countersVk require storing 296 bytes, so the memory complexity for the attack is 296 bytes. The data complexity is 261.The success ratePS=Φ(pNSN-Φ-1(1-2-a)/SN+1)=98.71 by [13].


## 3.1. Differential Characteristics of NUX

To search for the differential characteristic of NUX, the different propagation between round functions should be considered. And how differences propagate through S-boxes should also be taken into account. When a difference passes through an S-box, the output difference and probability are determined by looking up the XOR difference distribution table (DDT) of the S-box.Algorithm1 is designed to search for differential characteristics of NUX, and notations used in this algorithm are depicted in Figure 2. From the structure of NUX, it is obvious that the probability of one round can be 1; that is, all the 8 S-boxes are passive. So a special n-1-round differential characteristic, (Δ03=Δ02=0), is chosen, and one-round differential characteristic with probability 1 is added to catch n-round differential characteristics. Meanwhile, Δi4 and Δi3, which lie in the two branches on the left side, will not affect Δi2 and Δi1, the two branches on the right side, during propagation in NUX. So differences of two branches on the left or right are set to 0, and the difference propagation in the other two branches will be focused on during the encryption process. In this way, the number of active S-boxes is always no more than 4 in one round, which can make the probability of the differential characteristic as large as possible. The results of our search algorithm are listed in Table 5.Table 5
Differential characteristics of NUX.
Rounds Probability Number of tails 2 2 - 2 192 3 2 - 4 56 4 2 - 6 4 5 2 - 7 1 6 2 - 9 2 7 2 - 11 2 8 2 - 15 8 9 2 - 15 1 10 2 - 20 16 11 2 - 24 24 12 2 - 28 4 13 2 - 31 8 14 2 - 37 4 15 2 - 41 18 16 2 - 45 2 17 2 - 46 1 18 2 - 49 4 19 2 - 52 4 20 2 - 53 2 21 2 - 58 48 22 2 - 58 2 23 2 - 63 32 24 2 - 67 49 25 2 - 71 10 26 2 - 73 4 27 2 - 75 4 28 2 - 79 16 29 2 - 79 2 30 2 - 84 32 31 2 - 88 48Algorithm 1:Algorithm for differential characteristic on NUX.
Input: S-box S, Probability threshold PrLim[30]. Output: A differential trail with the best probability. ( 1 ) Generate the DDT of S-box. ( 2 ) Store all 2, 4 and the corresponding input/output differences in DDT in the table DDTP ( 3 )  for Each of 8 S-boxes in the first round do ( 4 )  for all non-zero entities in DDT do ( 5 )    if S-box is in F2  then ( 6 )     Δ13=ΔX1h⋘3, Δ14=Δ12=Δ11=0. ( 7 )     Store them in Rin[1]. ( 8 )    else ( 9 )     Δ12=ΔX1l⋙8, Δ14=Δ13=Δ11=0. ( 10 )     Store them in Rin[1]. ( 11 )    Calculate Δ04, Δ03, Δ02, Δ01, and store them in Rin[0]. ( 12 )    Calculate Δ24, Δ23, Δ22, Δ21, and store them in Rin[2]. ( 13 )    The probability is recorded as Pr[1]. ( 14 )  for  i←2 to 30  do ( 15 )    if  Δi4=Δi3=0  then ( 16 )    ΔXil=Δi2⋘8 ( 17 )    Travel DDTP to get ΔYil and its corresponding probability PrRnd ( 18 )    else if  Δi2=Δi1=0  then ( 19 )    ΔXih=Δi3⋙3 ( 20 )    Travel DDTP to get ΔYih and the corresponding probability PrRnd ( 21 )    Keep Pr[i-1]×PrRnd, which greater than threshold PrLim[i] ( 22 )    Calculate Δi+14, Δi+13, Δi+12, Δi+11, and store them in Rin[i+1]. ( 23 )    Pr[i]⇐Pr[i-1]×PrRnd ( 24 )  for Each of 8 S-boxes in the first round do ( 25 )  for all non-zero entities in DDT do ( 26 )    Find the largest Pr[i] and store it in PrMax[i] ( 27 )    Output different characteristics with probability PrMax[i]Figure 2
Differential representation of NUX.Furthermore, the minimal numbers of active S-boxes of 1~5-round differential characteristics are shown in the design manuscript [12]. So the minimal number of active S-boxes is also studied, and the minimum active S-boxes of 4 5-round differential characteristics are less than the ones given in [12], which are presented in Table 6.Table 6
Minimal number of active S-boxes from differential characteristic.
Number of active S-boxes Reference Rounds 1 2 3 4 5 [12] 0 1 2 5 9 Section3.1 0 1 2 3 3


## 3.2. Differential Attack on NUX

A 22-round differential characteristic is chosen with probability to be2-58, which is shown in Table 7, and 7 rounds are extended forward. The description is given in Figure 3. There are Δ04=0x0400, Δ223=0x2080, and Δ03=Δ02=Δ01=Δ224=Δ222=Δ221=0x0000 according to the 22-round differential distinguisher. Then Δ234=Δ233=0x0000, Δ231=0x0050, and Δ232 satisfy the form as (00∗∗∗00∗∗∗000∗∗0), where ∗∈{0,1} can be deduced. And the output difference of the 28-th round is Δ294=Δ293=0x0000. X232, X232′, X231, and X231′ can be gotten by 6-round decryption. So rk23′, rk24, rk25′, rk26, rk27′, and rk28 should be guessed and denoted by Kguess. The attack process is described as follows:(1)
CollectN pairs of plaintext (P,P′) satisfying P⊕P′=(Δ04,Δ03,Δ02,Δ01) and their corresponding ciphertext pairs (C,C′).(2)
Initialize232 counters V[0],V[1],…,V[232-1] and reset them.(3)
For each plaintext pair(P,P′), check whether its ciphertext pair (C,C′) satisfies (C⊕C′)[63:32]=0x00000000. If the ciphertext pair meets the formula, x=(C⊕C′)[31:0] and V[x]++.(4)
Initialize296 counters Vk[0],Vk[1],...,Vk[296-1] and reset them.(5)
Guess 96-bit keyKguess, and decrypt x to obtain X232, X232′, X231, and X231′. Check whether X232⊕X232′ and X231⊕X231′ are equal to Δ232 and Δ231. If the conditions are met, then let y=X232∥X232′∥X231∥X231′.(6)
Usey to calculate X224⊕X224′ and X223⊕X223′. If X224⊕X224′=Δ224 and X223⊕X223′=Δ223, Vk[Kguess]++.(7)
Set advantagea to be 51, which implies that the top 245 absolute values in Vk are kept. For each remaining key, we guess the remaining 58-bit subkey and calculate the master key. Finally, we test the key by trail encryptions.Table 7
22-Round differential characteristic of NUX.
Roundsi Δ i 4 Δ i 3 Δ i 2 Δ i 1 Probability 0 0400 0000 0000 0000 1 1 0000 0000 0080 0000 2 - 3 2 0040 0001 0000 0000 2 - 2 3 0000 0000 0010 8000 2 - 3 4 0004 1000 0000 0000 2 - 2 5 0000 0000 0002 0100 2 - 2 6 0800 6002 0000 0000 2 - 5 7 0000 0000 003b 0811 2 - 5 8 c80c 2b30 0000 0000 2 - 7 9 0000 0000 0480 4236 2 - 5 10 2040 0600 0000 0000 2 - 3 11 0000 0000 0005 2002 2 - 2 12 8080 0003 0000 0000 2 - 2 13 0000 0000 0040 8800 2 - 2 14 0400 0030 0000 0000 2 - 2 15 0000 0000 0008 4004 2 - 3 16 0008 3000 0000 0000 2 - 2 17 0000 0000 0000 0110 1 18 0000 4800 0000 0000 2 - 3 19 0000 0000 0020 0201 2 - 2 20 4000 0500 0000 0000 2 - 3 21 0000 0000 0000 2020 1 22 0000 2080 0000 0000 ∗Figure 3
Differential attack of 29-round NUX.If setN=260, then about 228 pieces of data enter step (5), which means 2124 6-round encryptions, that is, 2121.7 29-round encryptions. The complexity of step (7) is 2103 29-round encryptions. So the total time complexity of this attack is about 2121.73 29-round encryptions.The countersVk require storing 296 bytes, so the memory complexity for the attack is 296 bytes. The data complexity is 261.The success ratePS=Φ(pNSN-Φ-1(1-2-a)/SN+1)=98.71 by [13].


## 4. Linear Attack on 25-Round NUX

Linear approximations of NUX are searched for in this section, and the 25-round key-recovery attack is performed on NUX using a 19-round linear approximation.


### 4.1. Linear Approximations of NUX

To search for linear approximations of NUX, how masks propagate through S-boxes should be taken into account. When a mask passes through an S-box, the linear approximation table (LAT) of the S-box is looked up to determine the output mask and bias. Algorithm2 searches for linear approximations of NUX and notations used in this algorithm are depicted in Figure 4.Algorithm 2:Algorithm for linear approximations on NUX.
Input: S-box S, Bias threshold ϵLim[30]. Output: A linear approximation with the best bias. Data: The number of active S-boxes in i rounds Sactive[i]. The number of active S-boxes of the i-th roundSactivei. ( 1 ) Generate the LAT of S-box. ( 2 ) Store all 2, 4 and the corresponding input/output masks in LAT in the table LATP ( 3 )  for Each of 8 S-boxes in the first round do ( 4 )  for all non-zero entities in LAT do ( 5 )   if S-box is in F2  then ( 6 )     Γ14=ΓY1h⋙8, Γ13=Γ12=Γ11=0. ( 7 )     Store them in Rin[1]. ( 8 )    else ( 9 )     Γ11=ΓY1l⋘3, Γ14=Γ13=Γ12=0. ( 10 )      Store them in Rin[1]. ( 11 )    Calculate Γ04, Γ03, Γ02, Γ01, and store them in Rin[0]. ( 12 )    Calculate Γ24, Γ23, Γ22, Γ21, and store them in Rin[2]. ( 13 )    Update Sactive[1] to be 1. ( 14 )    The bias is recorded as ϵ[1]. ( 15 )  for  i←2 to 30  do ( 16 )    if  Γi4=Γi3=0  then ( 17 )     ΓYil=Γi1⋙3 ( 18 )     Travel LATP to get ΓXil, Sactivei and its corresponding bias ϵRnd ( 19 )    else if  Γi2=Γi1=0  then ( 20 )      ΓYih=Γi4⋘8 ( 21 )      Travel LATP to get ΓXih, Sactivei and the corresponding bias ϵRnd ( 22 )    Compute the total bias, and keep ones greater than threshold ϵLim[i] ( 23 )    Calculate Γi+14, Γi+13, Γi+12, Γi+11, and store them in Rin[i+1]. ( 24 )    Update the number of active S-boxes Sactive[i] and bias ϵ[i] ( 25 )  for Each of 8 S-boxes in the first round do ( 26 )  for all non-zero entities in DDT do ( 27 )    Find the largest ϵ[i] and store it in ϵMax[i] ( 28 )    Output linear approximations with bias ϵMax[i]Figure 4
Linear representation of NUX.The bias of one round can be1/2, which can be obtained from the structure of NUX; that is, all the 8 S-boxes are passive. So special (n-1)-round linear approximations are chosen, which satisfy (Γ04=Γ01=0), and one-round linear approximation with bias 1 is added to catch n-round linear approximations. Similar to searching for differential characteristics, there is only one active S-box in the first round of n-1 rounds. Meanwhile, Γi4 and Γi3, which lie in the two branches on the left side, will not affect Γi2 and Γi1, the two branches on the right side, during propagation in NUX. So the linear propagation on the left or right is taken into consideration, and differences of the other two branches are set to 0. In this way, the number of active S-boxes is always no more than 4 in one round, which can make the absolute value of the linear approximation bias as large as possible. The results of the search algorithm are listed in Table 8.Table 8
Linear approximations of NUX.
Rounds Bias Number of tails 2 2 - 2 288 3 2 - 3 300 4 2 - 4 13 5 2 - 5 2 6 2 - 6 4 7 2 - 10 13 8 2 - 11 62 9 2 - 12 6 10 2 - 15 70 11 2 - 16 11 12 2 - 18 70 13 2 - 19 4 14 2 - 20 2 15 2 - 22 4 16 2 - 24 16 17 2 - 26 4 18 2 - 27 4 19 2 - 30 16 20 2 - 31 4 21 2 - 33 8 22 2 - 35 60 23 2 - 37 21 24 2 - 39 25 25 2 - 41 48 26 2 - 43 103 27 2 - 44 4 28 2 - 46 7 29 2 - 48 54 30 2 - 49 4 31 2 - 50 2Moreover, the minimal numbers of active S-boxes of 1~5-round linear approximations are shown in the design manuscript [12]. And the minimal number of active S-boxes is also considered, and the minimum active S-boxes of 3~5-round linear approximations are less than the ones given in [12], which are presented in Table 9.Table 9
Minimal number of active S-boxes from linear approximation.
Number of active S-boxes Reference Rounds 1 2 3 4 5 [12] 0 1 4 9 13 Section4.1 0 1 2 3 3


### 4.2. Linear Attack on NUX

Utilizing obtained linear approximations, a key-recovery attack can be applied to 25-round NUX using a 19-round linear approximation with bias2-30, which is described in Table 10. The 19-round linear approximation is put from the 4th to the 22th round of NUX, extending 3 rounds both backward and forward. The 25-round key-recovery attack is shown in Figure 5.Table 10
19-Round linear approximation of NUX.
Roundsi Γ i 4 Γ i 3 Γ i 2 Γ i 1 Bias 0 0000 1040 0000 0000 2 - 1 1 0000 0000 0000 0500 2 - 2 2 0001 4040 0000 0000 2 - 2 3 0000 0000 0020 0600 2 - 2 4 5100 0440 0000 0000 2 - 4 5 0000 0000 8404 2028 2 - 3 6 100a a080 0000 0000 2 - 3 7 0000 0000 0206 3000 2 - 3 8 000a 2002 0000 0000 2 - 2 9 0000 0000 0202 0800 2 - 2 10 000a 0020 0000 0000 2 - 2 11 0000 0000 0202 4010 2 - 3 12 a000 0a00 0000 0000 2 - 2 13 0000 0000 4040 0200 2 - 2 14 1400 0400 0000 0000 2 - 3 15 0000 0000 0084 0448 2 - 3 16 01c3 8048 0000 0000 2 - 4 17 0000 0000 9023 0180 2 - 2 18 d800 4004 0000 0000 2 - 3 19 0000 0000 044c 24af ∗Figure 5
Linear attack of 25-round NUX.According to the linear approximation, there areΓ34=Γ32=Γ31=Γ224=Γ223=0x0000, Γ33=0x1040, Γ222=0x044c, and Γ221=0x24af. Furthermore, the following formula can be gotten: (4)Γ34·X34⊕Γ33·X33⊕Γ22·X32⊕Γ31·X31⊕Γ224·X224⊕Γ223·X223⊕Γ222·X222⊕Γ221·X221=Γ33·X33⊕Γ222·X222⊕Γ221·X221=κwhere X33 can be calculated through 3-round encryption by guessing 26-bit subkeys, which are denoted by Kbefore including rk0′, rk1[15,13,10,8,7,5,2,0], and rk2′[15,7]. Besides, X222 and X221 are obtained by 3-round decryption, which involves 40-bit subkeys, namely, rk22′[15,14,13,10,7,4,2,0], rk23, and rk24′. For the sake of simplicity, rk22′[15,14,13,10,7,4,2,0] and rk23 are denoted by Kmid. In the following, the attack process is depicted. (1)
CollectN plaintext/ciphertext pairs.(2)
Initialize266 counters V0[0],V0[1],…,V0[266-1] and reset them.(3)
Guess 26-bit keyKbefore.(4)
For each plaintext/ciphertext pair, calculatex=X33[12,6]∥C4∥C3∥C2∥C1. Then V0[x]++.(5)
Initialize234 counters V1[0],V1[1],...,V1[234-1] and reset them.(6)
Guess 16-bit keyrk24′.(7)
For everyx, calculate y=X33[12,6]∥X242∥X241. Then V1[y]+=V0[x].(8)
Initialize266 counters Vk[0],Vk[1],…,Vk[266-1] and reset them.(9)
Guess 24-bit keyKmid.(10)
For everyy, calculate X222[10,6,3,2] and X222[13,10,7,5,3,2,1,0]. Then compute z=Γ33·X33⊕Γ222·X222⊕Γ221·X221. If z=0, then Vk[Kbefore∥rk24′∥Kmid]+=V1[y]; otherwise, decrease the counter by V1[y].(11)
Set the advantagea to be 17, which means that the top 249 absolute values in Vk are kept. For each remaining key, we guess 77-bit subkey to determine the master key. And then we test the key by trail encryptions.IfN=263.7, then the time complexity of step (3), step (5), and step (7) is about 289.7 3-round encryption, 2108 1-round decryption, and 2100 2-round encryption, respectively. Besides, the complexity of step (11) is 2126 25-round encryption. Hence, the total time complexity of this attack is about 2126 25-round encryption.Both the countersV0 and Vk need 269 bytes to store, so the memory complexity for the attack is 270 bytes. The data complexity is 263.7.The success ratePS=Φ(2N·|ϵ|-1+N/2nΦ-1(1-2-a-1))=88.21 by [14].


## 4.1. Linear Approximations of NUX

To search for linear approximations of NUX, how masks propagate through S-boxes should be taken into account. When a mask passes through an S-box, the linear approximation table (LAT) of the S-box is looked up to determine the output mask and bias. Algorithm2 searches for linear approximations of NUX and notations used in this algorithm are depicted in Figure 4.Algorithm 2:Algorithm for linear approximations on NUX.
Input: S-box S, Bias threshold ϵLim[30]. Output: A linear approximation with the best bias. Data: The number of active S-boxes in i rounds Sactive[i]. The number of active S-boxes of the i-th roundSactivei. ( 1 ) Generate the LAT of S-box. ( 2 ) Store all 2, 4 and the corresponding input/output masks in LAT in the table LATP ( 3 )  for Each of 8 S-boxes in the first round do ( 4 )  for all non-zero entities in LAT do ( 5 )   if S-box is in F2  then ( 6 )     Γ14=ΓY1h⋙8, Γ13=Γ12=Γ11=0. ( 7 )     Store them in Rin[1]. ( 8 )    else ( 9 )     Γ11=ΓY1l⋘3, Γ14=Γ13=Γ12=0. ( 10 )      Store them in Rin[1]. ( 11 )    Calculate Γ04, Γ03, Γ02, Γ01, and store them in Rin[0]. ( 12 )    Calculate Γ24, Γ23, Γ22, Γ21, and store them in Rin[2]. ( 13 )    Update Sactive[1] to be 1. ( 14 )    The bias is recorded as ϵ[1]. ( 15 )  for  i←2 to 30  do ( 16 )    if  Γi4=Γi3=0  then ( 17 )     ΓYil=Γi1⋙3 ( 18 )     Travel LATP to get ΓXil, Sactivei and its corresponding bias ϵRnd ( 19 )    else if  Γi2=Γi1=0  then ( 20 )      ΓYih=Γi4⋘8 ( 21 )      Travel LATP to get ΓXih, Sactivei and the corresponding bias ϵRnd ( 22 )    Compute the total bias, and keep ones greater than threshold ϵLim[i] ( 23 )    Calculate Γi+14, Γi+13, Γi+12, Γi+11, and store them in Rin[i+1]. ( 24 )    Update the number of active S-boxes Sactive[i] and bias ϵ[i] ( 25 )  for Each of 8 S-boxes in the first round do ( 26 )  for all non-zero entities in DDT do ( 27 )    Find the largest ϵ[i] and store it in ϵMax[i] ( 28 )    Output linear approximations with bias ϵMax[i]Figure 4
Linear representation of NUX.The bias of one round can be1/2, which can be obtained from the structure of NUX; that is, all the 8 S-boxes are passive. So special (n-1)-round linear approximations are chosen, which satisfy (Γ04=Γ01=0), and one-round linear approximation with bias 1 is added to catch n-round linear approximations. Similar to searching for differential characteristics, there is only one active S-box in the first round of n-1 rounds. Meanwhile, Γi4 and Γi3, which lie in the two branches on the left side, will not affect Γi2 and Γi1, the two branches on the right side, during propagation in NUX. So the linear propagation on the left or right is taken into consideration, and differences of the other two branches are set to 0. In this way, the number of active S-boxes is always no more than 4 in one round, which can make the absolute value of the linear approximation bias as large as possible. The results of the search algorithm are listed in Table 8.Table 8
Linear approximations of NUX.
Rounds Bias Number of tails 2 2 - 2 288 3 2 - 3 300 4 2 - 4 13 5 2 - 5 2 6 2 - 6 4 7 2 - 10 13 8 2 - 11 62 9 2 - 12 6 10 2 - 15 70 11 2 - 16 11 12 2 - 18 70 13 2 - 19 4 14 2 - 20 2 15 2 - 22 4 16 2 - 24 16 17 2 - 26 4 18 2 - 27 4 19 2 - 30 16 20 2 - 31 4 21 2 - 33 8 22 2 - 35 60 23 2 - 37 21 24 2 - 39 25 25 2 - 41 48 26 2 - 43 103 27 2 - 44 4 28 2 - 46 7 29 2 - 48 54 30 2 - 49 4 31 2 - 50 2Moreover, the minimal numbers of active S-boxes of 1~5-round linear approximations are shown in the design manuscript [12]. And the minimal number of active S-boxes is also considered, and the minimum active S-boxes of 3~5-round linear approximations are less than the ones given in [12], which are presented in Table 9.Table 9
Minimal number of active S-boxes from linear approximation.
Number of active S-boxes Reference Rounds 1 2 3 4 5 [12] 0 1 4 9 13 Section4.1 0 1 2 3 3


## 4.2. Linear Attack on NUX

Utilizing obtained linear approximations, a key-recovery attack can be applied to 25-round NUX using a 19-round linear approximation with bias2-30, which is described in Table 10. The 19-round linear approximation is put from the 4th to the 22th round of NUX, extending 3 rounds both backward and forward. The 25-round key-recovery attack is shown in Figure 5.Table 10
19-Round linear approximation of NUX.
Roundsi Γ i 4 Γ i 3 Γ i 2 Γ i 1 Bias 0 0000 1040 0000 0000 2 - 1 1 0000 0000 0000 0500 2 - 2 2 0001 4040 0000 0000 2 - 2 3 0000 0000 0020 0600 2 - 2 4 5100 0440 0000 0000 2 - 4 5 0000 0000 8404 2028 2 - 3 6 100a a080 0000 0000 2 - 3 7 0000 0000 0206 3000 2 - 3 8 000a 2002 0000 0000 2 - 2 9 0000 0000 0202 0800 2 - 2 10 000a 0020 0000 0000 2 - 2 11 0000 0000 0202 4010 2 - 3 12 a000 0a00 0000 0000 2 - 2 13 0000 0000 4040 0200 2 - 2 14 1400 0400 0000 0000 2 - 3 15 0000 0000 0084 0448 2 - 3 16 01c3 8048 0000 0000 2 - 4 17 0000 0000 9023 0180 2 - 2 18 d800 4004 0000 0000 2 - 3 19 0000 0000 044c 24af ∗Figure 5
Linear attack of 25-round NUX.According to the linear approximation, there areΓ34=Γ32=Γ31=Γ224=Γ223=0x0000, Γ33=0x1040, Γ222=0x044c, and Γ221=0x24af. Furthermore, the following formula can be gotten: (4)Γ34·X34⊕Γ33·X33⊕Γ22·X32⊕Γ31·X31⊕Γ224·X224⊕Γ223·X223⊕Γ222·X222⊕Γ221·X221=Γ33·X33⊕Γ222·X222⊕Γ221·X221=κwhere X33 can be calculated through 3-round encryption by guessing 26-bit subkeys, which are denoted by Kbefore including rk0′, rk1[15,13,10,8,7,5,2,0], and rk2′[15,7]. Besides, X222 and X221 are obtained by 3-round decryption, which involves 40-bit subkeys, namely, rk22′[15,14,13,10,7,4,2,0], rk23, and rk24′. For the sake of simplicity, rk22′[15,14,13,10,7,4,2,0] and rk23 are denoted by Kmid. In the following, the attack process is depicted. (1)
CollectN plaintext/ciphertext pairs.(2)
Initialize266 counters V0[0],V0[1],…,V0[266-1] and reset them.(3)
Guess 26-bit keyKbefore.(4)
For each plaintext/ciphertext pair, calculatex=X33[12,6]∥C4∥C3∥C2∥C1. Then V0[x]++.(5)
Initialize234 counters V1[0],V1[1],...,V1[234-1] and reset them.(6)
Guess 16-bit keyrk24′.(7)
For everyx, calculate y=X33[12,6]∥X242∥X241. Then V1[y]+=V0[x].(8)
Initialize266 counters Vk[0],Vk[1],…,Vk[266-1] and reset them.(9)
Guess 24-bit keyKmid.(10)
For everyy, calculate X222[10,6,3,2] and X222[13,10,7,5,3,2,1,0]. Then compute z=Γ33·X33⊕Γ222·X222⊕Γ221·X221. If z=0, then Vk[Kbefore∥rk24′∥Kmid]+=V1[y]; otherwise, decrease the counter by V1[y].(11)
Set the advantagea to be 17, which means that the top 249 absolute values in Vk are kept. For each remaining key, we guess 77-bit subkey to determine the master key. And then we test the key by trail encryptions.IfN=263.7, then the time complexity of step (3), step (5), and step (7) is about 289.7 3-round encryption, 2108 1-round decryption, and 2100 2-round encryption, respectively. Besides, the complexity of step (11) is 2126 25-round encryption. Hence, the total time complexity of this attack is about 2126 25-round encryption.Both the countersV0 and Vk need 269 bytes to store, so the memory complexity for the attack is 270 bytes. The data complexity is 263.7.The success ratePS=Φ(2N·|ϵ|-1+N/2nΦ-1(1-2-a-1))=88.21 by [14].


## 5. Distinguishing Attack on NUX

Generally speaking, the distinguishing attack is a kind of test algorithm, which tries to perform the nonrandom behavior in cryptographic system. A distinguishing attack needs to find a distinguisher, which makes cryptographic algorithm different from random permutation. When analyzing NUX, we find a distinguisher with probability 1, that is, a deterministic distinguisher to distinguish NUX from a random permutation.In Section3, it has been pointed out that the two branches on the right side will not affect the two on the right side during difference propagation in NUX. Then, for the full-round NUX, when the input difference (Δ04,Δ03,Δ02,Δ01) is (0,0,∗,∗), the output difference (Δ314,Δ313,Δ312,Δ311) satisfies the form of (∗,∗,0,0), shown in Figure 6, that is, (0,0,∗,∗)⟶31-roundPr=1(∗,∗,0,0). However, the probability of the output difference to be (∗,∗,0,0) is Prrandom=2-32 for random permutations, when the input difference is (0,0,∗,∗). So 4 pairs of plaintexts are chosen, which are (Pi,Pi′), (0≤i≤3), and Pi⊕Pi′=(0,0,∗,∗), and the corresponding ciphertexts (Ci,Ci′) are checked to determine whether they satisfy Ci⊕Ci′=(∗,∗,0,0). The probability of obtaining such input/output differences is 1 for NUX, while it is 2-128 for a random permutation. Therefore, we can distinguish NUX from a random permutation. Besides, there is another distinguisher with probability 1, which is (∗,∗,0,0)⟶31-roundPr=1(0,0,∗,∗) and can be used to perform a distinguishing attack like the one described before. So we will not explore it here.Figure 6
31-Round differential distinguisher of NUX.Since only 4 pairs of plaintexts are used in the distinguishing attack, the data complexity is8. And the attack needs no storage. In other words, the complexity of memory is 0. The time complexity is 8 31-round encryptions.


## 6. Conclusions

NUX is a 31-round iterative ultralightweight cipher, which is suitable for extremely constrained environment and is applied to the Internet of Things. In this paper, differential and linear trails are searched for 1~31-round NUX, which are better than those proposed in design specification. Moreover, a key-recovery attack on 29-round NUX is given with the 22-round differential characteristic found in the paper, whose time, data, and memory complexities are 2121.73 29-round encryptions and 261 and 296 bytes, respectively. Meanwhile, using 22-round differential characteristic obtained in the paper, 29-round differential attack is performed with time, data, and memory complexities to be 2126 25-round encryptions and 263.7 and 270 bytes, respectively. Furthermore, a distinguishing attack can be implemented on full NUX with data complexity 8. Results in this paper are the best ones on NUX till now.



---

*Source: 2062697-2019-06-12.xml*