Improved Linear Cryptanalysis of Reduced-Round SIMON-32 and SIMON-48

Abstract

In this paper we analyse two variants of SIMON family of light-weight block ciphers against variants of linear cryptanalysis and present the best linear cryptanalytic results on these variants of reduced-round SIMON to date.

We propose a time-memory trade-off method that finds differential/linear trails for any permutation allowing low Hamming weight differential/linear trails. Our method combines low Hamming weight trails found by the correlation matrix representing the target permutation with heavy Hamming weight trails found using a Mixed Integer Programming model representing the target differential/linear trail. Our method enables us to find a 17-round linear approximation for SIMON-48 which is the best current linear approximation for SIMON-48. Using only the correlation matrix method, we are able to find a 14-round linear approximation for SIMON-32 which is also the current best linear approximation for SIMON-32.

The presented linear approximations allow us to mount a 23-round key recovery attack on SIMON-32 and a 24-round Key recovery attack on SIMON-48/96 which are the current best results on SIMON-32 and SIMON-48. In addition we have an attack on 24 rounds of SIMON-32 with marginal complexity.

This work was done while the author was a postdoc at the Technical University of Denmark

Javad Alizadeh, Mohammad Reza Aref and Nasour Bagheri were partially supported by Iran-NSF under grant no. 92.32575.

Praveen Gauravaram is supported by Australian Research Council Discovery Project grant number DP130104304.

Appendices

A Steps of the Key Recovery Attack on SIMON-32/64

Table 3. Step 1 of key recovery attack on SIMON-32/64

Table 4. Step 2 of key recovery attack on SIMON-32/64

Fig. 1.

Adding some rounds to the 14-round linear hull for SIMON-32 / K (Color figure online).

Table 5. Step 3 of key recovery attack on SIMON-32/64

Table 6. Step 4 of key recovery attack on SIMON-32/64

Table 7. Step 5 of key recovery attack on SIMON-32/64

B Steps of the Key Recovery Attack on SIMON-48/96

$$\begin{aligned} \mathcal {V}_j&\!\!=\!\!&(X^{i}_L)[2,6,14,22] \!\oplus \! (X^{i}_R) [0] \!\oplus \! (K^i)[2,6,14,22] \!\oplus \! (K^{i-1})[0,4,12,20] \!\oplus \! (K^{i-2})[2,18] \\ \mathcal {W}_j= & {} (X^{i+18}_L)[0] \oplus (X^{i+18}_R) [2,6,14,16,22] \oplus (K^{i+19})[2,6,14,16,22] \\&\oplus (K^{i+20})[0,4,12,20] \oplus (K^{i+21})[2,18] \oplus (K^{i+22})[0] \end{aligned}$$

Fig. 2.

Adding some rounds to the 17-round linear hull for SIMON-48 / 96 (Color figure online).

Table 8. Step 1 of key recovery attack on SIMON-48/96

Table 9. Step 2 of key recovery attack on SIMON-48/96

Table 10. Step 3 of key recovery attack on SIMON-48/96

C MIP Experiments

Table 11 shows the 30 sub approximations that have been used to estimate the squared correlations of the lower class trails. The experiments where the MIP solutions are limited to 512 trails per approximation took exactly 70125.382718 seconds which is less than 20 hrs using a standard laptop.

Table 12 shows the 30 sub approximations that have been used to estimate the squared correlations of the upper class trails. The experiments where the MIP solutions are limited to 512 trails per approximation took exactly 62520.033249 seconds which is less than 18 hrs using a standard laptop.

Table 11. Lower Class Trails found through our time-memory trade-off method, $c^2_{i1} \equiv$ the squared correlation of the ith 11-round linear approximation with light trails found through the correlation matrix, $c^2_{i2} \equiv$ the squared correlation of the ith 6-round linear approximation with heavy trails found through the MIP method, $c^2_{i1}c^2_{i2}\equiv$ is the squared correlation of the ith 17-round linear approximation and $\sum c^2_{i1}c^2_{i2}$ is the total estimated squared correlation of the lower class trails of our 17-round linear hull after including $i \le 30$ linear approximations

Table 12. Upper Class Trails found through our time-memory trade-off method, $c^2_{i1} \equiv$ the squared correlation of the ith 6-round linear approximation with heavy trails found through the MIP method, $c^2_{i2} \equiv$ the squared correlation of the ith 6-round linear approximation with light trails found through the correlation matrix, $c^2_{i1}c^2_{i2}\equiv$ is the squared correlation of the ith 17-round linear approximation and $\sum c^2_{i1}c^2_{i2}$ is the total estimated squared correlation of the upper class trails of our 17-round linear hull after including $i \le 30$ linear approximations