Improved (Related-key) Differential-based Neural Distinguishers for SIMON and SIMECK Block Ciphers

Table 2 presents the notations used in this paper.

Simon. The lightweight family of AND-RX block ciphers Simon was proposed by the National Security Agency (NSA) in 2013. It adopts the Feistel structure and the round function consists of bitwise AND ($\odot)$, bitwise XOR ($\oplus$) and cyclic left shift $\gamma$ bit ($S^{\gamma}$) operation composition. The designer provides ten versions, all marked as Simon$2n/mn$, where $2n$ represents the block size, $mn$ represents the key length, $n\in\{16,24,32,48,64\}$, $m\in\{2,3,4\}$. The round function of Simon algorithm is defined as:

The round keys are generated using a linear key schedule through the $K=(k_{m-1},k_{m-2},\ldots,k_{0})$. A more complete description can refer to paper [19].

Conversely, Simeck uses the non-linear key schedule which reuses the cipher’s round function to generate the round keys. A more complete description can be found in [20].

Differential cryptanalysis is a chosen-plaintext attack introduced by Biham and Shamir in [1]. It analyzes the effect of the difference of a plaintext pair on the difference of succeeding round outputs in an iterated cipher. Differential cryptanalysis is a widely used tool for the cryptanalysis of encryption algorithms and the development of new attacks due to its generality. Resistance to differential cryptanalysis became one of the basic criteria in the evaluation of the security of block ciphers.

For a specific cipher, the differential must be carefully selected to make the differential attack successful. This makes researchers need to study the internal process of the algorithm. The basic method is to track a path passed by a high probability differential at different stages of encryption. This is called differential characteristics in cryptography and is defined as follows.

For given differential characteristics, use the following definition to calculate its probability.

When the input difference undergoes a linear operation, it will be propagated through the operation with probability 1, and the output difference is deterministic, such as XOR ($\oplus$) and cyclic shift ($\lll,\ggg$) in the ARX operation. When the input difference passes through a non-linear operation, the difference propagation is often probabilistic.

Related-key differential cryptanalysis was introduced by Biham in  [21]. Unlike the single-key differentials that have differences only in the plaintexts, related-key differential distinguishers have differences in the master keys as well. It exploits the output differences given a pair of plaintexts $P$ and $P^{\prime}$ encrypted by a pair of related keys $K$ and $K^{\prime}$, respectively. Related-keys differential cryptanalysis is also one of the basic criteria in the evaluation of the security of block ciphers, which has successfully attacked many block ciphers, such as [22, 23, 24].

Convolutional neural network (CNN) is an important paradigm in deep learning. CNN is usually composed of the convolutional layer, non-linear layer, pooling layer and fully connected layer. According to the convolution dimension of the feature map, it can be divided into one-, two-, and three-dimensional convolutional neural network (i.e., 1D-CNN, 2D-CNN and 3D-CNN), where the 1D-CNN applies a convolution over a fixed (multi-)temporal input signal.

Convolution Layer (CONV). Convolution is the basic operation of CNN, and its main purpose is to extract features. The core task of CNN is to learn parameters to extract effective patterns. In the forward propagation, the training data will go through the convolution kernel with initial parameters to obtain the initial output. In the back propagation, a loss function will be applied to adjust the parameters to minimize the gap between the initial output and the target label. After several iterations, when the loss stabilizes, the training process will be finished. Note that in this paper we apply 1D-CNN, then the convolution layer can be denoted by Conv1D.

Non-linear layer. The main purpose of the non-linear layer is to introduce non-linear characteristics into the system. The most common non-linear layer in a CNN network is the rectified linear unit (ReLU) function, defined as $f(x)=max(0,x)$. Effectively, it removes negative values from an activation map by setting them to zero. It increases the nonlinear properties of the decision function and of the overall network without affecting the receptive fields of the convolution layer. Other functions are also used to increase nonlinearity, such as the sigmoid function. ReLU is often preferred to other functions because it trains the neural network several times faster without a significant penalty to generalization accuracy.

Fully connected layer (FC). The fully connected layer is generally located in the back layers of the network for performing the classification task. Usually, the input of the fully connected layer is the flatten feature map generated by convolution layer.

In addition, some functional layers may be used in CNN. For example, Batch Normalization (BN) can be applied after the convolution layer to reduce the internal covariate shift, which can effectively prevent the gradient disappearance problem and speed up network training.

Residual Network (ResNet) is one of the most representative CNNs, which was proposed by He et al. [25] in 2015. ResNet can train a deeper CNN model to achieve higher accuracy. The core idea is to establish “shortcuts (skip) connections” between the front layer and the back layer. It is composed of a series of residual blocks. A residual block can be expressed as:

It is divided into two parts: the direct mapping part and the residual part. $\mathcal{F}(x_{l})$ is the residual part, which is generally composed of two or three convolution operations. The activation functions of ReLU and BN can be rearranged to create a variety of residual block variants.

Squeeze-and-Excitation Network (SENet) is a new network structure proposed by Hu et al. that won the first place in ILSVRC 2017 classification competition [26]. The “Squeeze-and-Excitation” (SE) block adaptively recalibrates channel-wise feature responses by explicitly modelling interdependencies between channels. It can be integrated into standard architectures by insertion after the non-linearity following each convolution. In this paper, SE block is used directly with the residual network, i.e., the SE-ResNet network.

Data plays a very important role in deep learning, data preparation is a fundamental step for deep learning model development. Some researchers explored the use of multiple ciphertext pairs to improve the performance of differential-based neural distinguishers [17, 27, 28]. Some researchers also performed additional transformations on each pair of ciphertexts before feeding them into the network. Concretely, in Gohr’s work, the $n$-round NDs fed with data of form $(C_{l},C_{r},C_{l}^{\prime},C_{r}^{\prime})$. Subsequently, Benamira et al. [17] conjected the first convolution layer of Gohr’s neural network transforms the input $(C_{l},C_{r},C_{l}^{\prime},C_{r}^{\prime})$ into $(C_{l}\oplus C_{l}^{\prime},C_{l}\oplus C_{l}^{\prime}\oplus C_{r}\oplus C_{r}^{\prime},C_{l}\oplus C_{r},C_{l}^{\prime}\oplus C_{r}^{\prime})$ and a linear combination of those terms. In [28], Hou et al. designed the NDs model with multiple output differences as a sample, i.e., the $n$-round NDs fed multiple pairs with data of form $(C_{l}\oplus C_{l}^{\prime},C_{r}\oplus C_{r}^{\prime})\triangleq(\Delta_{L}^{r},\Delta_{R}^{r})$. In [18], Bao et al. accepted the $r$-round NDs fed with data of form $(C_{r},C_{r}^{\prime},\Delta_{R}^{r-1})$, where $\Delta_{R}^{r-1}=((C_{r}\lll 8)\odot(C_{r}\lll 1)\oplus(C_{r}\lll 2)\oplus C_{l})\oplus((C_{r}^{\prime}\lll 8)\odot(C_{r}^{\prime}\lll 1)\oplus(C_{r}^{\prime}\lll 2)\oplus C_{l}^{\prime})$ for Simon ciphers.

In this paper, we employ multiple ciphertext pairs with new data of form $(\Delta_{L}^{r},\Delta_{R}^{r},C_{l},C_{r},C_{l}^{\prime},C_{r}^{\prime},\Delta_{R}^{r-1},p\Delta_{R}^{r-2})$ to improve the performance of neural distinguishers (the reason for choosing this data format is given in Section 5.3). Then, the process of constructing a dataset can be described.

For the differential-neural distinguisher, first encrypt the $s$ plaintext pairs $((P,P^{\prime})^{1},(P,P^{\prime})^{2},\ldots,(P,P^{\prime})^{s})$ with a random key to get the $s$ ciphertext pairs. Then, use the $s$ ciphertext pairs to get the data:

where the set ${(\Delta_{L}^{r},\Delta_{R}^{r},C_{l},C_{r},C_{l}^{\prime},C_{r}^{\prime},\Delta_{R}^{r-1},p\Delta_{R}^{r-2})^{i}}$ of row $i$ is denoted by $\Omega^{i}$.

Finally, splice $\Omega^{i}$ and convert it into a string of binary as a sample, and each sample will be attached a label $Y$:

where $\Delta_{p}$ is a constant input difference. It examines how to select the $\Delta_{p}$ in Section 4.

Unlike differential-neural distinguisher, which uses a random key $K$ to encrypt the $s$ plaintext pairs, related-key differential-neural distinguisher uses a pair of keys $(K,K^{\prime})$ with a difference of $\Delta_{k}$ to encrypt the $s$ plaintext pairs.

We construct the dataset based on the above steps and set $s=8$. In the basic training process, the size of the training set is $2\times 10^{7}$, and the test set is $2\times 10^{6}$. Meanwhile, there is an independent key used for each sample. Therefore, the training set has $2\times 10^{7}$ corresponding random keys, and the test set has $2\times 10^{6}$ corresponding random keys.

A deep learning architecture is a multilayer stack of simple modules, most of which are subject to learning, and many of which compute non-linear input-output mappings. Each module in the stack transforms its input to increase both the selectivity and the invariance of the representation. With multiple non-linear layers, say a depth of 5 to 20, a system can implement extremely intricate functions of its inputs that are simultaneously sensitive to minute details.

Given the success of ResNet on Speck [16] and SENet on Simon [18], as well as their superior performance on classification tasks, we use the SE-ResNet network. As shown in Fig. 2, the network consists of three main components: input layer, iteration layer and predict layer. The input layer uses one Conv1D layer and two Dense layers to receive fixed length training data. In the iteration layer, use 5 SE-ResNet modules where each module contains two Conv1D layers and one SE block. To make the network learning more stable and alleviate the problem of gradient disappearance, a BN layer is applied after each Conv1D layer, and then followed by an activation layer with ReLU function. Finally, in predict layer, to make the data smoothly transform from the convolutional layer to the fully connected layer, we introduce a flatten layer to perform one-dimensional flattening of the data output from the convolutional layer. The fully connected layer consists of two Dense layers where each has 64 neurons and an output unit with only one neuron.

We set the batch size to 30000, cyclic learning rate $l_{i}=\alpha+\frac{(n-i)mod(n+1)}{n}\cdot(\beta-\alpha)$ with $\alpha=0.0001$, $\beta=0.003$, $n=29$ for epoch $i$, which is denoted as cyclic  ​lr$(30,0.003,0.0001)$. Adam [29] is used as the optimizer with mean squared error (MSE) loss function and L2 regularization parameterized by $c=0.00001$. Each dataset is trained with 120 epochs for the basic training method. The accuracy, TPR, and TNR of the ND are the average results after 5 repetitions.

Simon32/64

Note that for NDs fed with single ciphertext pairs, with multiple ciphertext pairs with the same label, one can directly obtain a combine-response distinguisher (CRD) using the formula (3) in [16]. Similar to the NDs fed with multiple ciphertext pairs, the CRDs’ accuracy improves quickly with increasing the number of ciphertext pairs. Therefore, we compare the accuracy of NDs with CRDs under the number of ciphertext pairs with the same label. Compared with [18], the accuracy of our NDs are improved.

In the second stage, the best network of the first stage is retained to recognize 12-round Simon32/64 with the input difference (0x0000,0x0040). For this stage, $2^{25}$ and $2^{23}$ examples are freshly generated for training and testing, respectively. The learning rate is $10^{-4}$ for 30 epochs.

Cyclical learning rates are also used for these training stages, the first and second stage both use a minimum learning rate of 0.0001 and a maximum of 0.001. All cycle lengths in these stages are set to 30 epochs. Eventually, the resulting ND achieves an accuracy of 0.5142.

In the first stage, the retained best 12-round distinguisher is trained and tested with 11-round $2^{25}$ and $2^{23}$ samples of Simon64/128 with the input difference (0x00000440,0x00000100). The number of epochs is 30 and the learning rate is $10^{-4}$. The learning rate scheduler used in this stage is cyclic  ​lr$(30,0.001,0.0001)$.

Then the best network from the first stage is trained in the second stage. The number of examples for training and for testing are $2^{25}$ and $2^{23}$, using 14-round Simon64/128 data with the input difference (0x00000000,0x00000040). This stage is done in 30 epochs with learning rate of $10^{-4}$. The learning rate scheduler used in this stage is cyclic  ​lr$(30,0.001,0.0001)$. Finally, the accuracy of the resulting ND is 0.5185.

We use the basic training method to train the related-key differential-neural distinguishers. Based on the plaintext difference (0x0000,0x0040) and the key difference (0x0000,0x0000,0x0000,0x0040), we enjoy 1, 0.9604, 0.6477, and 0.5262 accuracy for 10-, 11-, 12-, and 13-round RKNDs against Simon32/64, respectively.

Based on the plaintext difference (0x00000000,0x00000040) and the key difference (0x00000000,0x00000000,0x00000000,0x00000040), we build RKNDs cover to 12-, 13-, and 14-round with 0.9880, 0.8398, and 0.5788 accuracy for Simon64/128, respectively. To the best of our knowledge, this is the first successful application of the RKNDs against Simon-like ciphers.

In order to improve the accuracy of the ND, we introduce a new data format $(\Delta_{L}^{r},\Delta_{R}^{r},C_{l},C_{r},C_{l}^{\prime},C_{r}^{\prime},\Delta_{R}^{r-1},p\Delta_{R}^{r-2})$ suitable for the network architecture in this paper. Here, we explain the reason for choosing this data format. We mainly compare the effect of the different data format on the performance of the network based on the experiment of 9-, 10-, and 11-round NDs for Simon32/64.

We use the basic method to train the 9-, 10-, and 11-round NDs based the input difference (0x0000,0x0040), batch size 30000, and cyclic  ​lr$(30,0.003,0.0001)$. The results are presented in Table 5.

It shows that the NDs using data formats of $(C_{r},C_{r}^{\prime},\Delta_{R}^{r-1})$, $(\Delta_{L}^{r},\Delta_{R}^{r},C_{l},C_{r},C_{l}^{\prime},C_{r}^{\prime},\Delta_{R}^{r-1})$, $(\Delta_{L}^{r},\Delta_{R}^{r},C_{l},C_{r},C_{l}^{\prime},C_{r}^{\prime},\Delta_{R}^{r-1},p\Delta_{R}^{r-2})$ can achieve 11-round, and the accuracy with data format $(\Delta_{L}^{r},\Delta_{R}^{r},C_{l},C_{r},C_{l}^{\prime},C_{r}^{\prime},\Delta_{R}^{r-1},p\Delta_{R}^{r-2})$ is greater than others. This is the primary cause for using this data format in the paper.

Meanwhile, it is noted that the accuracy dropped when the $p\Delta_{R}^{r-2}$ component was deleted from the data format $(\Delta_{L}^{r},\Delta_{R}^{r},C_{l},C_{r},C_{l}^{\prime},C_{r}^{\prime},\Delta_{R}^{r-1},p\Delta_{R}^{r-2})$, i.e., the neural network benefits from providing data $p\Delta_{R}^{r-2}$. In fact, $p\Delta_{R}^{r-2}$ denotes the partial $\Delta_{R}^{r-2}$, and it can be determined without the round key when the ciphertext pair is given.

It is important to note that this comparison is only to show that the data format used in this paper better matches the current network for better performance. Different results may occur when the network is changed.

Simeck32/64

The first stage selects the best 10-round distinguisher to recognize 9-round Simeck32/64 with the input difference (0x0140,0x0080). Note that the most likely difference to appear three rounds after the input difference (0x0000,0x0040) is (0x0140,0x0080), and the probability is about $2^{-4}$.

It freshly generates $2^{25}$ and $2^{23}$ samples to train and test the distinguisher, respectively. This stage has 30 epochs and a learning rate of $10^{-4}$. The learning rate scheduler used in this stage is cyclic  ​lr$(30,0.001,0.0001)$.

The best network obtained from the first stage is retained to recognize 12-round Simeck32/64 with the input difference (0x0000,0x0040). The number of examples for training and for testing are $2^{25}$ and $2^{23}$, respectively. The number of epochs is 30 and the learning rate is $10^{-4}$. The learning rate scheduler used in this stage is cyclic  ​lr$(30,0.001,0.0001)$. Lastly, the ND produced has an accuracy of 0.5146.

In the first stage, the retained best 16-round distinguisher is trained and tested with 15-round $2^{25}$ and $2^{23}$ samples of Simeck64/128 with the input difference (0x0000140,0x00000080). The number of epochs is 30 and the learning rate is $10^{-4}$.

Then the best network from the first stage is trained in the second stage. The number of freshly generated examples for training and for testing are $2^{25}$ and $2^{23}$, using 18-round Simeck64/128 data with the input difference (0x00000000,0x00000040). This stage is done in 30 epochs with learning rate of $10^{-4}$.

Cyclical learning rates are used for these training stages, the first and second stage both use a minimum learning rate of 0.0001 and a maximum of 0.001. All cycle lengths in these stages are set to 30 epochs. As a final result, the ND produced has an accuracy of 0.5218.

For related-key differential-neural distinguishers, based on the input difference (0x0000,0x0040) and the key difference (0x0000,0x0000,0x0000,0x0040), it covers to 13-, 14-, and 15-round with 0.9950, 0.6679 and 0.5467 accuracy for Simeck32/64, respectively.

For Simeck64/128, based on the input difference (0x00000000,0x00000040) and the key difference (0x00000000,0x00000000,0x00000000,0x00000040), it cover to 18-, 19-, 20-, 21-, and 22-round with 0.9066, 0.7558, 0.6229, 0.5519, and 0.5180 accuracy for Simeck64/128, respectively. It can be seen the gap of RKNDs for Simon and Simeck is obvious, and Simon’s key-expansion algorithm offers better resistance. This is consistent with the conclusion that Lu et al. get using rotational-XOR cryptanalysis in [30].