Keywords

1 Introduction

Confusion layer of symmetric cryptography algorithms mostly consists of substitution boxes (S-boxes) and in order to provide better security against known attacks, S-boxes are selected depending on their cryptographic properties. Low non-linear and differential uniformity [24] provide resistance against linear [21] and differential cryptanalysis [6], respectively and most of the time these are the only properties designers focus on. However, it is shown that resistance against algebraic [11] and cube [12] attacks can be obtained by high algebraic degree and branch number. Moreover, lack of undisturbed bits [28] provides resistance against truncated [17], impossible [2], and improbable [27] differential cryptanalysis. It was shown in [20] that undisturbed bits are actually linear structures in coordinate functions. Thus, it is better to avoid linear structures to get better security against these kind of attacks. Resistance against side-channel attacks like differential power analysis [18] can be obtained depending on the number of shares [7] in threshold implementations. Implementation invariant resistance against these attacks can be obtained by S-boxes with a low transparency order [25] but low transparency order is not sufficient alone to directly achieve a satisfying level of security [10].

Recently it was shown in [29] that S-boxes may have parameters called differential factors which does not change the output difference of an S-box when they are XORed with the input pair. Thus, some counters of the guessed keys in a differential variant attack become the same, which prevents the attacker from fully capturing the attacked round keys. This may benefit the attacker because reduction in the attacked key space reduces the time complexity of many attacks. For instance, the 10, 11, and 12-round differential-linear attacks of [13] on Serpent [1] tries to capture 40, 48, and 160 bits of the key, respectively. However, it was shown in [29] that these attacks can only obtain advantages of 38, 46, and 157 bits on the key due to differential factors and these attacks can actually be performed with time complexities reduced by a factor of 4, 4, and 8, respectively.

Most of the statistical attacks on blocks ciphers consists of two steps: Capturing partial information about the key via distinguishers and obtaining the remaining key bits via exhaustive search. We note that although differential factors reduce the time complexity of the former, they increase the time complexity of the latter. In this work we use this observation to correct the differential attack of [31] on Present [9] which due to six differential factors requires a time complexity of \(2^{70}\) memory accesses instead of \(2^{64}\) memory accesses as it is claimed in [31].

Moreover, we show that differential factors also reduces the data complexity of differential attacks since the reduction in the key space allows us to use less number of pairs to distinguish the correct key. This observation also reduces the memory required to store the key counters and time complexity since the attack procedure is repeated for every data. We use our findings to obtain best differential-linear attacks on Serpent by reducing the data and time complexity of the previous attacks.

2 Differential Factors

Definition 1

([29]). Let S be a function from \(\mathbb {F}_2^n\) to \(\mathbb {F}_2^m\). For all \(x,y\in \mathbb {F}_2^n\) that satisfy \(S(x)\oplus S(y)=\mu \), if we also have \(S(x\oplus \lambda )\oplus S(y\oplus \lambda )=\mu \), then we say that the S-box has a differential factor \(\lambda \) for the output difference \(\mu \). (i.e. \(\mu \) remains invariant for \(\lambda \)).

Present’s S-box is given as an example in Table 1 which has \(\lambda =1\) as a differential factor for \(\mu =5\).

Table 1. Present’s S-box ordered in pairs where the output difference is \(\mu =5\). Note that XOR of any pair with \(\lambda =1\) gives another pair that has output difference \(\mu =5\).
Full size table

The following theorem shows that the number of differential factors of an S-box is the same with the number of differential factors of its inverse. Moreover, it also provides the differential factors of the inverse S-box when we know the differential factors of the S-box. Hence, there is no need to check the differential factors of the inverse of S-boxes. This theorem is useful in practice since inverse of an S-box is used for decryption in substitution permutation networks.

Theorem 1

([29]). If a bijective S-box S has a differential factor \(\lambda \) for an output difference \(\mu \), then \(S^{-1}\) has a differential factor \(\mu \) for the output difference \(\lambda \).

Moreover, differential factors for the same \(\mu \) form a vector space.

Theorem 2

([29]). If \(\lambda _1\) and \(\lambda _2\) are differential factors for an output difference \(\mu \), then \(\lambda _1\oplus \lambda _2\) is also a differential factor for the output difference \(\mu \). i.e. All differential factors \(\lambda _i\) for \(\mu \) form a vector space.

Differential factors are observed mostly in small S-boxes. For instance, \(73.3\,\%\) of all \(3\times 3\) bijective S-boxes contain differential factors. Moreover, a list of ciphers and hash functions whose \(4\times 4\) S-boxes contain differential factors are provided in [29].

2.1 Differential Factors and Time Complexity

We start by recalling the definition of advantage.

Definition 2

([26]). If an attack on an m-bit key gets the correct value ranked among the top r out of \(2^m\) possible candidates, we say the attack obtained an \((m-log(r))\)-bit advantage over exhaustive search.

Differential attacks on block ciphers use a differential as a distinguisher and the attack is performed by adding a few more rounds on the top or bottom of this differential. Pairs that may satisfy this differential are partially encrypted or decrypted under the possible subkeys and counters of these keys are incremented when the differential is satisfied. In a one round attack, one can obtain these counters just by looking at a precomputed table. However, more complicated attacks may require to repeat partial encryptions under every possible subkey. In these cases, differential factors reduce the time complexity of this step as follows.

Theorem 3

([29]). In a block cipher let an S-box S contain a differential factor \(\lambda \) for an output difference \(\mu \) and the partial round key k is XORed with the input of S. If an input pair provides the output difference \(\mu \) under a partial subkey \(k'\), then the same output difference is observed under the partial subkey \(k'\oplus \lambda \). Therefore, during a differential attack involving the guess of a partial subkey corresponding to the output difference \(\mu \), the advantage of the cryptanalyst is reduced by 1 bit and the time complexity of this key guess step is halved.

Proof

In a differential attack for any key \(k'\), \(k'\) and \(k'\oplus \lambda \) would get the same number of hits since \(\lambda \) is a differential factor. Hence the attacker cannot distinguish half of the guessed keys with the other half. Therefore during the key guessing step, the attacker does not need to guess half of the keys. Thus, the time complexity of this step is halved.    \(\square \)

From Theorems 2 and 3 we obtain the following Corollary.

Corollary 1

([29]). During a differential attack involving the guess of a partial subkey corresponding to the output difference \(\mu \) of an S-box that has a vector space of differential factors of dimension r for \(\mu \), the advantage of the cryptanalyst is reduced by r bits and the time complexity of the key guess step is reduced by a factor of \(2^r\).

Most of the statistical attacks on blocks ciphers first tries to capture partial information about the secret key and then the full key is obtained by exhaustive search. Thus, if possible, the attacker tries to balance these two steps to obtain the optimal time complexity for the attack. Although differential factors reduce the time complexity of the former, they increase the time complexity of the latter. We provide our first observation in Corollary 2.

Corollary 2

Differential factors reduce the time complexity of capturing partial information about the key which uses differentials but they increase the time complexity of the exhaustive search for obtaining the remaining key bits.

Thus, the attacker should take into account differential factors when trying to balance the time complexities of these two parts. We show the importance of Corollary 2 in Sect. 4 by proving that Wang’s differential attack on Present is actually wrong and the corrected attack requires \(2^{70}\) memory accesses instead of \(2^{64}\) as it is claimed in [31].

2.2 Differential Factors and Data Complexity

Statistical attacks use a distinguisher which is observed with different probabilities \(p_0\) and p for the correct key and the wrong keys, respectively. For instance, the attacker uses N plaintext pairs in differential attack and counts the times each subkey satisfies this distinguisher. The correct key is expected to be above some threshold T since we have \(p_0>p\). Thus, the number of hits a wrong (right) subkey gets can be seen as a random variable of a binomial distribution with parameters N and p (\(p_0\)). We denote the non-detection error probability, which is the probability of the counter for the right subkey to be less than T, by \(p_{nd}\); and the false alarm error probability, which is the probability of the counter for a wrong subkey to be higher than or equal to T, by \(p_{fa}\).

Theorem 4

Differential factors reduce the key space for the key guess process and therefore reduce the data complexity of the attack. Thus, memory required to keep the counters for the guessed keys also reduces. Reduction in the data complexity may also reduce the time complexity depending on the attack.

Proof

The amount of required plaintext pairs N to perform the attack with the desired success probability depends also on the number of wrong keys. Because they determine the number of binomial distributions from which we try to distinguish the correct key. Since the existence of the differential factors reduces the wrong subkey space, the number of pairs required to perform the attack also reduces. Thus, memory required to keep the counters for the guessed keys also reduces. Moreover, the attack procedure is repeated for every pair in most of the attacks. Therefore, this reduction in the data complexity further reduces the time complexity.    \(\square \)

When differential factors were introduced in [29], their effect on the data and memory complexity were overlooked. By using differential factors that appear in the differential-linear attacks on Serpent, we reduce the data complexity of these attacks in Sect. 5. Since the data and time complexities of these attacks are directly proportional, we further reduce the time complexities of these attacks. Moreover, we reduce the data and memory complexity of the differential attack on Present in Sect. 4 using Theorem 4.

Success probability of differential attacks are generally calculated easily using Selçuk’s formula [26] and it is used in the original Present attack. However, in this work we use Blondeau-Gérard-Tillich algorithm [8] since it is valid for both differential and differential-linear attacks. This algorithm takes p, \(p_0\), \(p_{nd}\), and \(p_{fa}\) as input and provides N and T as output.

3 PRESENT and SERPENT

Present [9] is a 31-round SPN (Substitution Permutation Network) type block cipher with block size of 64 bits that supports 80 and 128-bit secret key. It has been internationally standardized by ISO/IEC 29192-2:2012 [16] as a lightweight block cipher. Round function of Present, which is depicted in Fig. 1, is same for both versions of Present and consists of standard operations such as subkey XOR, substitution and permutation: At the beginning of each round, 64-bit input of the round function is XORed with the subkey. Just after the subkey XOR, 16 identical \(4 \times 4\)-bit S-boxes are used in parallel as a non-linear substitution layer and finally a permutation is performed so as to provide diffusion.

Fig. 1.
figure 1figure 1

Round function of Present

Full size image

Serpent [1] was designed by Anderson, Biham and Knudsen in 1998. It was submitted to the AES contest and became one of the five finalists. It has a block size of 128 bits and accepts any key size of length 0 to 256 bits. It is a 32-round SPN, where each round consists of key mixing, a layer of S-boxes and a linear transformation.

The 128-bit input value before round i is denoted by \(\hat{B}_i\), \(i \in \{0,\ldots ,31\}\). Each \(\hat{B}_i\) is composed of four 32-bit words \(X_0,X_1,X_2,X_3\) where \(X_0\) is the leftmost word.

Three round operations are specified as follows:

  1. 1.

    Key Mixing: At each round \(R_i\), a 128-bit subkey \(K_i\) is XORed with the current intermediate data \(\hat{B}_i\).

  2. 2.

    S-boxes: At each round, \(R_i\) uses a single S-box \(S_j\), where \(i\equiv j\pmod 8\) and \(i \in \{0,\ldots ,31\}\), 32 times in parallel. In this paper, we use the bitsliced version of Serpent. For example, in the first round the first copy of \(S_0\) takes the least significant bits from \(X_0,X_1,X_2,X_3\) and returns the output to the same bits. Thus, we obtain 32 4-bit slices referred as \(b_i\)’s, where \(i \in \{0,\ldots ,31\}\) and \(b_0\) is the right most slice.

  3. 3.

    Linear Transformation: The four 32-bit words \(X_0,X_1,X_2,X_3\) are linearly mixed by the following linear operations:

    figure afigure a

    where \(\lll \) denotes the left rotation operation and \(\ll \) denotes the left shift operation.

32-round Serpent cipher may be described by the following equations:

$$\begin{aligned} \hat{B}_0 := P&\qquad \hat{B}_{i+1} := R_i(\hat{B}_i), \; i \in \{0,\ldots , 31\}&\quad C := \hat{B}_{32} \end{aligned}$$

where

$$\begin{aligned}&\ \ R_i(X) = LT(\hat{S}_i (X \oplus K_i ) ), \; i \in \{0,\ldots ,30\} \\&R_{31}(X) = \hat{S}_{31}(X \oplus K_{31}) \oplus K_{32} \end{aligned}$$

and \(\hat{S}_i\) is the application of the S-box \(S_{(i\ (mod\ 8))}\) 32 times in parallel, and LT is the linear transformation.

In this paper, we use P, S, I to the denote output of the permutation layer, output of the substitution layer, and input of a round, respectively.

Differential factors of Present and Serpent’s S-boxes are provided in Table 2.

Table 2. Differential factors of Present and Serpent’s S-boxes
Full size table

4 Differential Attacks on PRESENT

The best known differential attack on Present is obtained in [31] by adding two rounds to the bottom of the 24 different 14-round differentials which has different input and same output difference. These differentials hold with probability \(p=2^{-62}\) and \(\varDelta _1\) is an example for these differentials

$$\begin{aligned} \varDelta _1: 0700000000000700 \rightarrow _{14r} 0000000900000009 \end{aligned}$$

This differential attack captures 32 bits of the key with a time complexity of \(2^{33.18}\) 2-round Present encryptions, a data complexity of \(2^{64}\) chosen plaintexts, and a memory complexity of \(2^{32}\) 6-bit counters. This part of the attack works with a success probability of \(99.9999939\,\%\) and then the remaining 48 bits are obtained via exhaustive search which requires \(2^{48}\) 16-round Present encryptions or equivalently \(2^{64}\) memory accesses.

It is claimed that these 14-round characteristics activates two S-boxes at the round 15 and due to the undisturbed bits of the S-box, it activates at most six S-boxes instead of eight in round 16. If activated, the input difference of these S-boxes must be 1. Present’s S-box has a differential factor \(\lambda =1\) for \(\mu =5\). Thus, the inverse of the S-box has a differential factor \(\lambda =5\) for \(\mu =1\) by Theorem 1. Since \(\mu =1\) coincides with the input difference of these six S-boxes, the advantage of this attack is actually 26 bits instead of 32 bits. This theoretical result can easily be observed experimentally by performing this attack by removing the first few rounds of the 14-round differential so that it remains within our computational power. This attack is summarized in Table 3.

Table 3. 16-round differential-linear attack of [31]. Output differences \(\mu \) that contain differential factors, which is \(\lambda =1\) for the inverse S-box, are shown in bold.
Full size table
Table 4. Comparison of Wang’s original differential attack on Present and our corrected one. MA - Memory Accesses, b - bits, CP - Chosen Plaintexts.
Full size table

This observation reduces the time complexity of the first part of the attack to \(2^{27.18}\) 2-round Present encryptions and the memory complexity to \(2^{26}\) 6-bit counters. However, the time complexity of exhaustive search for the remaining bits of the key is \(2^{54}\) 16-round Present encryptions or equivalently \(2^{70}\) memory accesses. Therefore, the correct time complexity of Wang’s differential attack on Present [31] is \(2^{70}\) memory accesses, instead of \(2^{64}\).

Another correction we make for this attack is due to Theorem 4. The original attack uses the whole codebook and achieves a success probability of 0.999999939. However, the original attack tries to capture 32 bits of the key. Thus, we need \(p_{fa}\le 2^{-33}\) to have only the correct key counter above the threshold T. Since the six differential factors used in the attack reduces the key space for the key guess process, we can choose \(p_{fa}=2^{-27}\) to prevent any wrong key to get a counter higher than T. Using the Blondeau-Gérard-Tillich algorithm with parameters \(p=2^{-64}\), \(p_0=24\cdot 2^{-62}\), \(p_{nd}=1-0.999999939\), and \(p_{fa}=2^{-27}\) shows that this attack can be performed with \(2^{63.58}\) data complexity to achieve the success probability of the original attack. This change reduces the memory required for the guessed key counters to \(6\cdot 2^{26}\) bits from \(6\cdot 2^{32}\) bits. These corrections are summarized in Table 4.

Table 5. 12-round differential-linear attack of [13]. Output differences \(\mu \) that contain differential factors, which are \(\mu =4\) and \(\mu =E\) for \(S_1\) and \(\mu =4\) for \(S_0\), are shown in bold. Undisturbed bits are shown in italic.
Full size table
Table 6. Summary of attacks on Serpent. Our observations on differential factors in Theorem 4 convert the attacks of [29] to the best attacks for this cipher. En - Encryptions, MA - Memory Accesses, B - bytes, AC - Adaptive Chosen Plaintexts, CP - Chosen Plaintexts, KP - Known Plaintexts.
Full size table

5 Differential-Linear Attacks on SERPENT

The most successful differential-linear attacks on Serpent were provided by Dunkelman et al. in [13] for 10, 11, and 12 rounds for the key sizes 128, 192, and 256, respectively. These attacks combine the 3-round differential

$$\begin{aligned} \varDelta : 0000 0000 0000 0000 0000 0000 4005 0000\rightarrow 0??0 0?00 0?00 0000 000? 00?0 ??0? ?0?0 \end{aligned}$$

that has an experimental probability of \(2^{-7}\) with the 6-round linear approximation

$$\begin{aligned} \varLambda : 2006 0040 0000 0100 1000 0000 0000 0000\rightarrow 0000 1000 0000 0000 5000 0100 0010 0001 \end{aligned}$$

of [3] that has bias \(q=2^{-27}\). By performing experiments on the first four rounds of this 9-round differential-linear distinguisher, it was shown in [13] that for the full distinguisher, the probability of pairs to have the same parity in the masked outputs is \(1/2+2^{-57.75}\). The 11-round attack adds one round to the top of this distinguisher and one round to the bottom. The 12-round attack adds an extra round to the top, which is provided in Table 5. Since the time complexity of the 11-round attack exceeds the exhaustive search of 128 bits, the 10-round attack removes the last round of the distinguisher so that it becomes applicable to Serpent with 128-bit keys. These attacks partially encrypt the top rounds under every possible subkey to obtain the input difference of \(\varDelta \). Then the last round is decrypted to check the parity of the correct pairs which is actually performed by using precomputed lookup tables.

It was claimed that these attacks can capture 40, 48, and 160 bits of the subkey. Later it was shown in [29] that these attacks overlooked the differential factors of Serpent’s S-boxes \(S_0\) and \(S_1\) and the actual advantages are 38, 46, and 157 bits, respectively. Since the attack procedure is repeated for every guess of the subkey bits, existence of differential factors also reduced the time complexities of these attacks by a factor of 4, 4, and 8, respectively.

However, we can further improve these attacks using Theorem 4. We also not that a differential factor was overlooked in the 12-round attack of [29] and therefore the advantage of the attack is actually 156 bits, not 157. Since the differential factors used in the attacks reduce the key space to 38, 46, and 156 bits, we choose the false alarm probability for these attacks in Blondeau-Gérard-Tillich algorithm as \(p_{fa}=2^{-39}\), \(p_{fa}=2^{-47}\), and \(p_{fa}=2^{-157}\), respectively. This analysis shows that these attacks can actually be performed with data complexities \(2^{100.55}\), \(2^{120.8}\), and \(2^{122.45}\) instead of \(2^{101.2}\), \(2^{121.8}\), and \(2^{123.5}\) respectively. Since the data and time complexities of these attacks are directly proportional, we further reduce the time complexities of these attacks to \(2^{112.55}\), \(2^{132.7}\), and \(2^{244.35}\) from \(2^{113.2}\), \(2^{133.7}\), and \(2^{246.4}\), respectively. The attacks on Serpent are summarized in Table 6.

6 Conclusion

Many attacks on ciphers require data, time, and memory complexities that are beyond our computational powers. Thus, experiments on the reduced versions of these theoretical attacks are vital to check the validity in practice. For instance, it was believed that the key bits corresponding to active S-boxes in a differential attack could be fully captured in a differential attack. However, differential factors which are introduced in Lightsec 2014 show that this is not always the case. Differential factors were used to correct the differential-linear attacks on Serpent and the resulting attacks have reduced time complexities. Key recovery attacks generally consists of two parts and in this work we show that differential factors reduce the time complexity of the key guess using a distinguisher step but increase the time complexity of exhaustive search on the remaining key bits step. As an example, we show that the best differential attack on Present in the literature overlooked the differential factors and the attack actually requires \(2^{70}\) memory accesses instead of \(2^{64}\). Hence, differential factors affect the attacker adversely if the exhaustive search step of the attack requires time complexity more than the key guess step.

Moreover, we further investigate the effects of differential factors and observe that existence of differential factors in an attack reduces the memory complexity required for the key counters and the data complexity. This is because differential factors reduce the size of the key space for the key guess part of the attack which allows the attacker to distinguish the correct key from the wrong ones with a reduced number of data. The reduction in the data complexity may result in a similar reduction in the time complexity since data and time complexities are directly proportional in most of the attacks. Using these observations, we further reduce the data and time complexities of the best differential-linear attacks on Serpent to obtain the best attacks for this cipher. Moreover, we show that the differential attack on Present actually requires less data and memory complexity.