Marek Broll
email: marek.broll@rub.de

Federico Canale
email: federico.canale@rub.de

Nicolas David
email: nicolas.david@inria.fr

Antonio Flórez-Gutiérrez
email: antonio.florez-gutierrez@inria.fr

Gregor Leander
email: gregor.leander@rub.de

María Naya-Plasencia
email: maria.nayaplasencia@inria.fr

Yosuke Todo
email: yosuke.todo.xt@hco.ntt.co.jp

New Attacks from Old Distinguishers Improved Attacks on Serpent

Keywords: Differential-linear cryptanalysis, key-recovery, Serpent, conditional differential, conditional linear., If x2

Serpent was originally proposed in 1998 and is one of the most studied block ciphers. In this paper we improve knowledge of its security by providing the current best attack on this cipher, which is a 12-round differential-linear attack with lower data, time and memory complexities than the best previous attacks. Our improvements are based on an improved conditional key guessing technique that exploits the properties of the Sboxes.

Introduction

Symmetric primitives play a vital role in today's secure communication. In a nutshell, their success is certainly based on their outstanding performance on the one hand and the trust in their security on the other hand. The block cipher Serpent [START_REF] Biham | Serpent: A new block cipher proposal[END_REF] is an excellent example of the successful interplay between security and performance considerations. Serpent was a finalist in the Advanced Encryption Standard competition organized by NIST, and -unofficially -ranked second. Its design greatly contributed to our understanding of performance block ciphers by being consequently designed with a bit-sliced implementation in mind. It has also been the target of an impressively large amount of cryptanalysis like [START_REF] Kelsey | Amplified boomerang attacks against reducedround MARS and Serpent[END_REF][START_REF] Biham | The rectangle attack -rectangling the Serpent[END_REF][START_REF] Biham | Linear cryptanalysis of reduced round Serpent[END_REF][START_REF] Biham | New results on boomerang and rectangle attacks[END_REF][START_REF] Biham | Differential-linear cryptanalysis of Serpent[END_REF][START_REF] Collard | Improved and multiple linear cryptanalysis of reduced round Serpent[END_REF][START_REF] Collard | Improving the time complexity of matsui's linear cryptanalysis[END_REF][START_REF] Cho | A new technique for multidimensional linear cryptanalysis with applications on reduced round Serpent[END_REF][START_REF] Dunkelman | A differential-linear attack on 12-round Serpent[END_REF][START_REF] Nguyen | Improving the algorithm 2 in multidimensional linear cryptanalysis[END_REF][START_REF] Mclaughlin | Filtered nonlinear cryptanalysis of reduced-round Serpent, and the wrong-key randomization hypothesis[END_REF][START_REF] Liu | Differential-linear cryptanalysis from an algebraic perspective[END_REF] over the years.

All of those attacks are based on variants or generalizations of differential ( [START_REF] Biham | Differential cryptanalysis of DES-like cryptosystems[END_REF]) and linear ( [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF]) cryptanalysis, which are two of the fundamental families of attacks on symmetric primitives. Differential cryptanalysis is based on differences between pairs of plaintexts which propagate through the cipher with high probability, while linear cryptanalysis is based on linear approximations which exhibit high correlation. In both cases the aim is to distinguish the cipher from a random permutation by collecting enough plaintext-ciphertext pairs. In [START_REF] Langford | Differential-linear cryptanalysis[END_REF] a combination of both types of distinguishers was introduced. It is shown that a probability 1 differential and a linear approximation can be combined to obtain a distinguisher that covers more rounds. The technique was extended in [START_REF] Biham | Enhancing differential-linear cryptanalysis[END_REF] to allow for probabilities different from 1 in the differential part.

In this paper we make use of two main observations to construct the best attack on Serpent. We start by extending some ideas presented in [START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF] for differentiallinear attacks on ARX constructions to SPN networks.

In addition, and this is the technically most important part, we use some ideas for improving the key recovery part of these attacks. The idea is to minimize the parts of the key that need to be guessed by closely investigating the involved Sboxes. As we will see, in the case of the coordinate functions of the Serpent Sboxes (and its derivatives) it is possible to deduce information on its output given only partial information on its input. Here, and this allows a significantly more fine-grained approach, we consider not only reductions that are possible for the entire input space, but rather split the input space (repeatedly) into halves by considering linear conditions on the input.

By using these techniques we are able to propose the best known attacks on Serpent, as summarized in Table 1. While the first and third attack yield the best time and data/memory complexity, respectively, the second attack shows that we can get a much better time complexity than the best previously known attacks and better data and memory complexity.

Related Work

Serpent has been the target of multiple reduced-round cryptanalysis efforts ever since it was first introduced. These include linear ( [START_REF] Biham | Linear cryptanalysis of reduced round Serpent[END_REF][START_REF] Collard | Improving the time complexity of matsui's linear cryptanalysis[END_REF]), multiple and multidimensional linear ( [START_REF] Collard | Improved and multiple linear cryptanalysis of reduced round Serpent[END_REF][START_REF] Cho | A new technique for multidimensional linear cryptanalysis with applications on reduced round Serpent[END_REF][START_REF] Nguyen | Improving the algorithm 2 in multidimensional linear cryptanalysis[END_REF]), nonlinear ( [START_REF] Mclaughlin | Filtered nonlinear cryptanalysis of reduced-round Serpent, and the wrong-key randomization hypothesis[END_REF]), boomerang ( [START_REF] Kelsey | Amplified boomerang attacks against reducedround MARS and Serpent[END_REF][START_REF] Biham | New results on boomerang and rectangle attacks[END_REF]), rectangle ( [START_REF] Biham | Linear cryptanalysis of reduced round Serpent[END_REF][START_REF] Biham | Enhancing differential-linear cryptanalysis[END_REF]), and differential-linear ( [START_REF] Biham | Differential-linear cryptanalysis of Serpent[END_REF][START_REF] Dunkelman | A differential-linear attack on 12-round Serpent[END_REF][START_REF] Liu | Differential-linear cryptanalysis from an algebraic perspective[END_REF]) attacks. We will next discuss the best known attacks. All those claim to attack 12 rounds and consider the Serpent version using a 256-bit key.

Flawed Complexity Estimates Before doing so, we would like to point out that unfortunately, quite some previous attacks turned out to be flawed. In some cases flaws were not describe previously. In all those cases, the overly optimistic complexity estimates were confirmed by the authors of the corresponding papers.

First published 12-round attack. Some differential-linear attacks on 11 and 12round Serpent were proposed in [START_REF] Dunkelman | A differential-linear attack on 12-round Serpent[END_REF]. However, we have found that the 12-round attack is incorrect (also pointed out in [START_REF] Liu | Differential-linear cryptanalysis from an algebraic perspective[END_REF] and acknowledged by the authors). Indeed, the attack consists of a 112 keybit guess in the first round, which should allow the attacker to perform the 11-round variant of the attack on the rest of the rounds. This assumption is incorrect, as although the difference in the state after the first round is determined, the input values of the active Sboxes in the second round are unknown, which are required by the 11-round attack as they are part of the plaintext. Any evident workaround would either increase the data complexity beyond the whole codebook or the time complexity over the exhaustive search. The attacks which are presented in this paper are amended versions of this 12-round attack, as they are based on the same distinguisher.

Multidimensional-linear 12-round attacks. A family of multidimensional linear attacks on up to 12 rounds are presented in [START_REF] Nguyen | Improving the algorithm 2 in multidimensional linear cryptanalysis[END_REF]. The complexity estimates for these attacks were found to be overly optimistic in [START_REF] Mclaughlin | Filtered nonlinear cryptanalysis of reduced-round Serpent, and the wrong-key randomization hypothesis[END_REF], where new estimates were provided. The original estimates in [START_REF] Nguyen | Improving the algorithm 2 in multidimensional linear cryptanalysis[END_REF] rely on an overestimated capacity, mistaken time complexity conversion to full encryptions, and very small advantage and success probability. Of the two proposed variants of the 12-round attack, the complexities of the first were corrected to 2 125.8 data complexity, a time complexity of 2 242 memory accesses, and 2 108 memory complexity, while the second variant was found to be invalid and no valid corrected version was presented given for it. We have found, however, that the memory complexity for the first attack is also incorrect. The attack consists of 2 128 repetitions of the 11-round attack, once for each guess of the last round subkey. We can choose between a memory complexity of 2 125.813 to store the data but with a larger time complexity of 2 253.813 , or a large memory complexity of 2 236 with the same time complexity 4 . The values given in Table 1 correspond to the corrected complexities.

Differential-Linear. In a recent work which is independent from ours [START_REF] Liu | Differential-linear cryptanalysis from an algebraic perspective[END_REF], a new 12-round differential-linear attack on Serpent is proposed that tries to improve the distinguisher bias and the key recovery complexity simultaneously with an algebraic approach. The complexities of their attack can be seen in Table 1, where we have corrected the memory complexity for the sake of comparison: while in the original paper the authors claimed a memory of 2 99 , they have confirmed to us that they did not take into account the cost of storing the data (as each plaintext-ciphertext pair has to be accessed multiple times), and agree with this comparison. In their paper the authors also indicate the problems with the attack from [START_REF] Dunkelman | A differential-linear attack on 12-round Serpent[END_REF], and state that they were not able to fix these problems without increasing the complexity beyond that of exhaustive search. This shows how powerful our new key-recovery techniques are, as they allow to bring the time complexity of this attack below 2 256 . Even more, we are able to provide the best known 12-round attack on Serpent, as can be seen in Table 1. The time complexity of [START_REF] Liu | Differential-linear cryptanalysis from an algebraic perspective[END_REF], as can be seen in Table 1 is quite higher than ours even in the version where we have also better data and memory. As a side note our attack is also the only known differential-linear attack on 12 rounds that starts from the first round of Serpent.

Finally, our attack shares some basics with [START_REF] Broll | Generic framework for key-guessing improvements[END_REF]. Indeed, as the authors from [START_REF] Broll | Generic framework for key-guessing improvements[END_REF] point out, our original ideas used specifically for Serpent have inspired that paper's generalized framework used for other ciphers and other attacks than differential-linear ones.

Outline

The paper is structured as follows: Section 2 provides the specifications of Serpent as well as a short introduction to differential-linear attacks. Section 3 provides a first "fixed" version of the 12-round attack which was introduced in [START_REF] Dunkelman | A differential-linear attack on 12-round Serpent[END_REF] whose corrected time complexity is very close to exhaustive search. Section 4 focuses on some useful properties of the Serpent Sboxes, as well as discussing how similar properties should be exploitable in all small Sboxes. Finally, in Section 5 we use these properties in an improved version of the attack which reduces the time complexity by a factor of around 2 22 .

Preliminaries

Description of the Serpent cipher

Serpent is a block cipher which was introduced in [START_REF] Biham | Serpent: A new block cipher proposal[END_REF] by Anderson, Biham and Knudsen. Its design consists of a substitution-permutation network (SPN) with an internal state of 128 bits. It admits 128, 192 or 256 bit keys. The encryption map consists of a round function which is iterated 32 times. The round function consists of three steps: first the state is XORed with key material, then a layer of of 4-bit Sboxes is applied, and the round ends with a linear transformation. The cipher makes use of the following 8 Sboxes, which were constructed in a pseudo random way to fulfil several cryptographic criteria:

x x x 0 1 2 3 4 5 6 7 8 9 A B C D E F S 0 (x) S 0 (x) S 0 (x) 3 8 F 1 A 6 5 B E D 4 2 7 0 9 C S 1 (x) S 1 (x) S 1 (x) F C 2 7 9 0 5 A 1 B E 8 6 D 3 4 S 2 (x) S 2 (x) S 2 (x) 8 6 7 9 3 C A F D 1 E 4 0 B 5 2 S 3 (x) S 3 (x) S 3 (x) 0 F B 8 C 9 6 3 D 1 2 4 A 7 5 E S 4 (x) S 4 (x) S 4 (x) 1 F 8 3 C 0 B 6 2 5 4 A 9 E 7 D S 5 (x) S 5 (x) S 5 (x) F 5 2 B 4 A 9 C 0 3 E 8 D 6 7 1 S 6 (x) S 6 (x) S 6 (x) 7 2 C 5 8 4 6 B E 9 1 F D 3 A 0 S 7 (x) S 7 (x) S 7 (x) 1 D F 0 E 8 2 B 7 4 C A 9 3 5 6
We now provide a precise description of the round function, which will be given using the bitsliced notation of [START_REF] Biham | Serpent: A new block cipher proposal[END_REF]. The 128-bit internal state X is represented by four 32-bit words which are denoted X 0 , X 1 , X 2 and X 3 , with X j [i] being the i-th leftmost bit of word j. The 32 rounds are numbered 0 to 31. Each round consists of the following four steps:

-Key mixing. A 128 bit subkey is XORed to the internal state. The subkey at round i will be denoted by K i . -Sbox Layer. Different Sboxes are used depending on the round, in particular S (i mod 8) is used at round i. The Sbox Layer operation consists of the application of 32 copies of the Sbox to the internal state. For each i ∈ {0, . . . , 31} we perform the appropriate Sbox transformation to the 4bit string (X 0

[i], X 1 [i], X 2 [i], X 3 [i]
). The parallel application of the Sbox in round i will be denoted S i . -Linear transformation. The linear operation is denoted by LT and consists of the following steps:

X 0 ← X 0 ≪ 13; X 2 ← X 2 ≪ 3 X 1 ← X 1 ⊕ X 0 ⊕ X 2 ; X 3 ← X 3 ⊕ X 2 ⊕ (X 0 3) X 1 ← X 1 ≪ 1; X 3 ← X 3 ≪ 7 X 0 ← X 0 ⊕ X 1 ⊕ X 3 ; X 2 ← X 2 ⊕ X 3 ⊕ (X 1 7) X 0 ← X 0 ≪ 5; X 2 ← X 2 ≪ 22
Here j denotes a j-bit left shift and ≪ j denotes a j-bit left rotation. In round 31 this linear transformation is ommited and an additional subkey K 32 is XORed to the state instead.

If we denote by B i the 128-bit value at round i, the cipher operates as follows:

B 0 ← IP (P ) B i+1 ← R i ( B i ) C ← IP -1 ( B 32 )
where

IP is an initial permutation R i (X) = LT ( S i (X ⊕ K i )) for i = 0, . . . , 30 R i (X) = S i (X ⊕ K i ) ⊕ K 32 for i = 31
Key schedule. The key schedule described in [START_REF] Biham | Serpent: A new block cipher proposal[END_REF] turns the 256-bit user key K into 33 128-bit round subkeys, that is, 132 32-bits words of key material. The user key is first written as 8 32-bit words K = w -8 w -7 • • • w -1 . This prekey sequence is extended using the recurrence relation

w i = (w i-8 ⊕ w i-5 ⊕ w i-1 ⊕ φ ⊕ i) ≪ 11,
where φ = 0x9e3779b9. We then build the sequence k i from w i using the Sboxes: We then distribute the 32-bit words k j to build the 128-bit subkeys K i :

{k 0 , k 33 , k 66 , k 99 } = S 3 (w 0 ,
K i = {k 4i , k 4i+1 , k 4i+2 , k 4i+3 }
The round key K i is the result of the application of the fixed initial permutation IP to K i , hence K i = IP (K i ).

Differential-linear Cryptanalysis

We consider a cipher E K decomposed in two parts F K and G K , thus E K = G K • F K . The ideas developed in [START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Biham | Enhancing differential-linear cryptanalysis[END_REF] allow to combine differential properties of F K and linear properties of G K to build a more global property on E K . Let δ -→ ∆ be a differential with probability p for F K . In other words,

Prob x,K (F K (x + δ) = F K (x) + ∆) = p.
Let α, y ⊕ β, z be a linear approximation of G K with correlation q:

Prob x,K ( α, y ⊕ β, G K (y) = 0) -Prob x,K ( α, y ⊕ β, G K (y) = 1) = q.
In [START_REF] Langford | Differential-linear cryptanalysis[END_REF][START_REF] Biham | Enhancing differential-linear cryptanalysis[END_REF] it is shown that

Corr x,K ( β, E K (x) ⊕ β, E K (x ⊕ δ) ) = pq 2
under certain independence assumptions. This means that E K can be distinguished from a random permutation with O p 2 q 4 chosen plaintext-ciphertext pairs. It suffices to generate plaintext pairs (x, x ⊕ δ) and compute the correlation of β, E K (x) ⊕ β, E K (x ⊕ δ) . Note that the presence of truncated differentials and linear hulls will influence the correlation of a differential-linear distinguisher. Furthermore, the independence assumption is not always satisfied, so the transition between the differential and the linear part may have an unexpected correlation. To overcome this issue, several approaches, such as the differential-linear connectivity table (DLCT) [START_REF] Bar-On | DLCT: A new tool for differential-linear cryptanalysis[END_REF] have been introduced. One of the most commonly-used techniques is to remove a small number of transition rounds from the differential and the linear paths and estimate their correlation r experimentally, and consider the correlation of the full distinguisher is prq 2 . This approach is of course limited to sufficiently large correlations r.

Another improvement we use is the idea introduced in [START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF] of generating many pairs which verify the differential part of the distinguisher from a single pair. In the paper, it is noted that flipping certain bits in the input will not change the fact that a pair fulfils the differential part of the differential-linear distingusher. In the best case, this reduced the data complexity by a factor of 1/p.

A differential-linear distinguisher can be used to mount a key-recovery attack by extending it at the top and/or at the bottom with key guesses. We can guess some key material which determines the input difference of the distinguisher from the plaintext and some key material which determines the output parity bit from the ciphertext. By computing the correlation of the differential-linear distinguisher for each guess of the key, we can separate the correct key guess from all the wrong ones. In order to determine the advantage and success probability of our attacks, we will use the models introduced for linear cryptanalysis in [START_REF] Blondeau | Improved parameter estimates for correlation and capacity deviates in linear cryptanalysis[END_REF].

First version of the attack

In this section we present a corrected version of the flawed 12-round attack from [START_REF] Dunkelman | A differential-linear attack on 12-round Serpent[END_REF] by considering the correct diffusion on the key recovery rounds along with the idea introduced in [START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF] of generating multiple good differential pairs.

Differential-linear distinguisher

Our attack is based on the same differential-linear distinguisher that was used in the flawed 12-round attack in [START_REF] Dunkelman | A differential-linear attack on 12-round Serpent[END_REF]. We start from a "central" distinguisher which starts with a fixed difference at the beginning of round 2, progresses through a three-round truncated differential with probability p = 2 -6 , and then ends with a five-round linear approximation with correlation q = 2 -21 (we remove the last round of the original distinguisher). The expected correlation for the differential-linear distinguisher is thus pq 2 = 2 -48 . However, experiments with the correlation of the transition rounds between the differential and the linear trail suggest that the actual correlation should be at least 2 -46.75 . Our aim for

---X ----X----X----X-X--X ------X- #23 S3 ---B ----B----B----B-2--E ------1- #22 LT R11 ----1-----------5----1----1----1 #21 S2 ----A-----------1----B----B----B #20 LT R10, q10 = 2 -5 --1----1 ----1----1-------------- #19 S1 --1----B ----B----A-------------- #18 LT R9, q9 = 2 -6 --------------------1----1----1- #17 S0 --------------------1----B----A- #16 LT R8, q8 = 2 -5 ------1----1 -------------------- #15 S7 ------A----1 -------------------- #14 LT R7, q7 = 2 -4 ------------------------1------- #13 S6 ------------------------8------- #12 LT R6, q6 = 2 -2 --4----------------------------8 #11 S5 --2----------------------------2 #10 LT R5, q5 = 2 -4
-??--?---?---------? --?-??-? ?-?-

#9 S4
-??--?---?---------? --?-??-? ?-?-

#8 LT R4 --*----------------------------- #7 S3 --4----------------------------- #6 LT R3, p3 = 2 -1 ------------------------A--4 ---- #5 S2 ------------------------4--5 ---- #4 LT R2, p2 = 2 -5 2------------1A--E--4----------- #3 S1 5------------C1--8--9----------- #2 LT R1, p1 = 2 -12
118A -25---8--88-C-12 4-24 8618 --1-

#1 S0 XXXX -XX---X--XX-X-XX X-XX XXXX --X- #0 R0
Lin. KR Linear trail Differential Diff. KR Fig. 1: The basic differential-linear attack on 12-round Serpent obtained by simple extension of the distinguisher, which requires more data than the whole codebook. The hyphenrepresents a zero difference/mask in the nibble to improve readability. The nibble difference * is undetermined but is zero in the rightmost bit.

the twelve-round attack is to effectively extend this distinguisher by two rounds at the top and two rounds at the bottom.

If we consider (one of) the best differential transition(s) for each active round 1 Sbox and the best linear approximation for each active Sbox in round 10 (in other words, if we extend the distinguisher to these rounds without any key recovery), the data needed for a reasonable probability of success would be more than 2 2•(48.75+12+2•5) = 2 141.5 , which surpasses the size of the codebook. This version of the attack is illustrated in figure 1.

Improving the first rounds

Our first improvement is inspired by the ideas proposed in [START_REF] Beierle | Improved differential-linear attacks with applications to ARX ciphers[END_REF] in the context of ARX, which we adapt to SPN constructions. The idea is to make sure that some of the differential transitions in round 1 hold for all the data by guessing all the keybits required to know the input values to these Sboxes, instead of only the input differences. For each plaintext, we can deduce a part of the associated plaintexts which will guarantee that the pair always verifies these transitions. This requires guessing more keybits than needed for computing the difference at the beginning of round 1, but allows a reduction in data complexity.

There are five active Sboxes (11,14,17,18 and 31) in round 1, which lead to 20 active Sboxes in round 0. In other words, we have to guess 80 bits of K 0 in order to obtain the desired difference at the beginning of round 1. The aim now is to choose some Sboxes in round 1 for which we will also determine the input values, and to do so in a way which optimizes the number of additional keybit guesses. We therefore look at each of the active Sboxes in round 1 and see which additional Sboxes in round 0 would be activated if we decide to guess the input values as well as the differences. We see that in the case of Sboxes 17, 18 and 31, not all Sboxes are active in round 0. From this table we infer that our efforts should be directed towards Sboxes 11, 17,18 and 31. Sboxes 31 and 17 are particularly interesting as their transition probability is smaller. If we simply fixed the input value of the four Sboxes to one which satisfies the transition with the input difference indicated in the figure, the amount of available data for each key guess would be reduced by a factor of 2 10 . Instead we consider that the input differences to these Sboxes are variable, as we just need the correct output difference to be satisfied. This also means that the target output difference for round 0 is variable.

Giving this treatment to the four Sboxes would make all Sboxes except for 23 active in round 1. In order to reduce the number of keybit guesses, we will only choose 3 out of these 4 Sboxes, and we will impose some conditions in the input differences in order to obtain the best data complexity: the best choice are Sboxes 31, 18 and 17. Let us point out that at the end of section 5.3 another variant is proposed by considering the four Sboxes that provides the best data complexity. We have chosen two conditions that provide the best trade-off between the reduction of available data and the reduction of keybits to guess.We first impose a 1-bit condition to the difference in state #2 by requiring the difference in bit x 3 in column 17 to be 0. This rejects half of the plaintext pairs, but reduces the number of active bits in the previous round. This condition is compatible with the original difference, which was 1. Additionally, in column 31 we only consider differences in which the difference in x 0 is zero. This condition is not compatible with the original difference of 5 and rejects 3/4 of the plaintexts, but makes column 29 in the previous round inactive. In the end we keep 2 -3 of the plaintext pairs, which means we can generate up to 2 124 differential pairs for each key guess from the whole codebook. This new path is represented in Figure 2.

In addition to the 76 keybits 5 corresponding to the difference, computing the input values to these three Sboxes requires guessing all the other keybits except for Sboxes 23 and 29, which are inactive. This implies a 120 bit key guess in round 0 plus 12 bits in the round 1 for the three active Sboxes in #2 whose input values are required. In the end the amount of pairs required by the attack is reduced by a factor of 2 2•(3+3+2)-3 = 2 13 with respect to the previous version.

We can summarise the differential pair generation as follows:

-Pick a random plaintext x.

-Guess 120 bits of K 0 and 12 bits of K 1 . With these we can compute the outputs of S 1 in columns 17, 18 and 31, y [START_REF] Dunkelman | A differential-linear attack on 12-round Serpent[END_REF], y [START_REF] Flórez-Gutiérrez | Improving key-recovery in linear attacks: Application to 28-round PRESENT[END_REF] and y[31], respectively. -With these we can compute

∆[17] = S -1 1 (y[17]) + S -1 1 (y[17] + A), ∆[18] = S -1 1 (y[18]) + S -1 1 (y[18] + 1) and ∆[31] = S -1 1 (y[31]) + S -1 1 (y[31] + 2)
, which are the input differences to these Sboxes. If ∆ [START_REF] Dunkelman | A differential-linear attack on 12-round Serpent[END_REF] 0 (S 0 (x + K 0 ) + LT -1 (∆)) + K 0 , and (x, x ) is a candidate differential pair.

Last Rounds

As before, we want to reduce the data complexity by making some changes to round 10. For each of the five active Sboxes (0,5,10,15,27), we determine which bits are required to compute the full output values as opposed to a single parity bit. In other words, for each of these Sboxes we compute which Sboxes would remain inactive in round 11 if we determine the full output value: We will use a linear output mask spread between the inputs and the outputs of the S 2 layer in round 10. If we determine the full output (instead of just the 5 There are 4 less bits to guess as column 29 is now inactive.

---X --X-XX---X----X-X--X X-X-X-XX

#23 S3 ---X --X-XX---X----X-X--X X-X-X-XX #22 LT R11 ----1-----------5----1----1----X #21 S2 ----A-----------1----B----B----B #20 LT R10, q10 = 2 -4 --1----1 ----1----1-------------- #19 S1 --1----B ----B----A-------------- #18 LT R9, q9 = 2 -6 --------------------1----1----1- #17 S0 --------------------1----B----A- #16 LT R8, q8 = 2 -5 ------1----1 -------------------- #15 S7 ------A----1 -------------------- #14 LT R7, q7 = 2 -4 ------------------------1------- #13 S6 ------------------------8------- #12 LT R6, q6 = 2 -2 --4----------------------------8 #11 S5 --2----------------------------2 #10 LT R5, q5 = 2 -4
-??--?---?---------? --?-??-? ?-?-

#9 S4
-??--?---?---------? --?-??-? ?-?-

#8 LT R4 --*----------------------------- #7 S3 --4----------------------------- #6 LT R3, p3 = 2 -1 ------------------------A--4 ---- #5 S2 ------------------------4--5 ---- #4 LT R2, p2 = 2 -5 2------------1A--E--4----------- #3 S1 @------------$#--8--9----------- #2 LT R1, p1 = 2 -4 XX-X XXXX -XXX XXXX XXXX XXXX XXXX XXXX #1 S0 XX-X XXXX -XXX XXXX XXXX XXXX XXXX XXXX #0 R0
Lin. KR Linear trail

Differential

Diff. KR Fig. 2: The slightly improved differential-linear attack on 12-round Serpent with staggered key-recovery. The nibble difference $ is undetermined but is one in the leftmost bit x 3 because of the differential properties of S 1 . The nibble difference * is undetermined but is zero in the rightmost bit x 0 . The nibble difference @ is undetermined but is zero in the rightmost bit x 0 . The nibble difference # is undetermined but is zero in the leftmost bit x 3 .

desired parity bit) of Sbox 0, there are 13 active Sboxes in the last round. The other four active Sboxes in round 10 are part of the differential-linear distinguisher. We thus need to guess 4 • 13 = 52 keybits of K 12 , and 4 bits of K 11 .

The key recovery in the linear part can be performed efficiently by using the FFT algorithm for multiple rounds which was introduced in [START_REF] Flórez-Gutiérrez | Improving key-recovery in linear attacks: Application to 28-round PRESENT[END_REF], with a cost of 2 • 52 • 2 2•52 additions / substractions and 2 2•52 products for each guess of the key in the top and each of the 2 4 key guesses in round 10.

Complexity analysis

In order to properly evaluate the time complexity, we need to compare the cost of the basic operations of the attack against 12-round Serpent encryptions. We first focus on the distillation phase of the FFT algorithm For each generated plaintext: we perform a two round encryption at the beginning and a one round decryption at the end. However, the partial encryption can be performed for one plaintext x and the result can be reused for all input values of the two inactive Sboxes in round 0. The filtering requires us to process 2 3 plaintexts to find one which satisfies the desired conditions. The cost of processing each plaintext is thus (2 -8 • 2 3 • 2/12 + 1/12) = 2 -3.50 encryptions.

For the comparison of a 12-round encryption with one of the arithmetic operations, we note that we can consider 128 • 3 • 12 = 4608 as a lower bound for the number of bit operations in a 12-round Serpent encryption. On the other hand, a 128 bit addition can be performed with 256 bit operations and a 128 bit product with 128 • log 2 (128) 961 bit operations. We thus get a worst-case 2 -4.17 conversion factor for the additions and 2 -2.26 for the products.

Given the distinguisher's correlation of 2 -48.75-4-2•4 = 2 -60.75 , and using the model from [START_REF] Blondeau | Improved parameter estimates for correlation and capacity deviates in linear cryptanalysis[END_REF], we obtain that with 2 123.96 pairs, (2 127.96 data before sieving), an advantage of 15 bits is obtained with probability 0.1.

The time complexity of the attack is as follows:

2 120 • 2 12
Top key guess

• 2 123.96 •2 -3.5 +2 4 • 104 • 2 -4.17 + 2 -2.26 • 2 104
Bottom key guess +2 256-15 2 252.46 encryptions. We need 2 127.96 registers for the data, as well as 2 104 for the distillation tables of the FFT. The overall memory complexity is thus around 2 127.96 .

Sbox conditions

The purpose of the present Section is to illustrate some conditional properties of the Serpent Sboxes which can improve the differential part of the attack, as well as studying the presence of similar properties in small (4-bit) Sboxes.

Conditions on the Serpent Sboxes

We consider the first Serpent Sbox, S 0 , which is used in round 0. If we denote its input by x = (x 3 , x 2 , x 1 , x 0 ) and the output by y = (y 3 , y 2 , y 1 , y 0 ) then the following set of conditional relations always holds:

x2 ⊕ x1 ⊕ x0 = 1 ⇒ y0 = x3 ⊕ x2 ⊕ x0 ⊕ 1 x3 ⊕ x2 ⊕ x1 = 0 ⇒ y1 = x3 ⊕ x2 ⊕ x0 ⊕ 1 x2 = 1 ⇒ y2 = x3 ⊕ x1 ⊕ x0 x3 = 0 ⇒ y3 = x2 ⊕ x1 ⊕ x0 x3 = 1 ⇒ y3 = x3 ⊕ x2 ⊕ x1
Thanks to these relations, we can compute output bit y 3 without querying the full input. We first query x 3 . Depending on this bit, we query either x 2 ⊕ x 1 ⊕ x 0 or x 3 ⊕ x 2 ⊕ x 1 to obtain y 3 . This decreases the amount of key material that needs to be guessed in an attack, as in the end we only have to consider four different guesses of the key as opposed to the usual sixteen. More specifically, if

x i = m i ⊕ k i where (m 0 , m 1 , m 2 , m 3
) is the known state before adding the key guess (k 0 , k 1 , k 2 , k 3 ), then in order to compute the output bit y 3 of S 0 , we first guess k 3 and determine the input bit x 3 = m 3 ⊕ k 3 . If x 3 = 0, we guess the bit k 2 ⊕ k 1 ⊕ k 0 and, thanks to the above conditions, we have that

y 3 = x 2 ⊕ x 1 ⊕ x 0 = (m 2 ⊕ m 1 ⊕ m 0 ) ⊕ (k 2 ⊕ k 1 ⊕ k 0 ).
Otherwise, when x 3 = 1 we guess k 3 ⊕ k 2 ⊕ k 1 and determine

y 3 = x 3 ⊕ x 2 ⊕ x 1 = (m 3 ⊕ m 2 ⊕ m 1 ) ⊕ (k 3 ⊕ k 2 ⊕ k 1 ).
We can find some similar relations which determine y 0 , y 1 and y 2 in the cases which were not covered by the previous set of relations:

x2 ⊕ x1 ⊕ x0 = 0 and x2 = 0 ⇒ y0 = x3 ⊕ 1 x2 ⊕ x1 ⊕ x0 = 0 and x2 = 1 ⇒ y0 = x0 ⊕ 1 x3 ⊕ x2 ⊕ x1 = 1 and x2 = 0 ⇒ y1 = x0 ⊕ 1 x3 ⊕ x2 ⊕ x1 = 1 and x2 = 1 ⇒ y1 = x3 ⊕ 1 x2 = 0 and x1 = 0 ⇒ y2 = x3 x2 = 0 and x1 = 1 ⇒ y2 = x0 ⊕ 1
With these relations we can determine any one bit of the output of the Sbox with either four (output bit y 3 ) or six different guesses of key-bits on average. We can construct analogous conditional relations which determine more than one output bit at the same time. A more convenient representation of these conditions can be given with binary trees, as it is explained in the appendix.

The same technique can be applied to reduce the guesses necessary to determine whether a pair (x, x ) = (m ⊕ k, m ⊕ k) satisfies a certain output difference ∆, i.e., if S 0 (x) ⊕ S 0 (x ) = ∆. We consider the function

F ∆ (x) = S -1 0 (S 0 (x) ⊕ ∆) ⊕ x,
and we search for conditional relationships which allow us to find a good pair (x, x ) by guessing k only partially. The reason is that, if (x, x ) is a good pair,

F ∆ (x) = x ⊕ x = m ⊕ m,
and knowing F ∆ (x) and m is therefore enough to recover m . We give a partial example for ∆ = 4. From the relations of F 4 represented as a tree in Figure 6a, we derive the following (partial) conditions for the case x 0 = 0:

x0 = 0 and x1 = 0 ⇒ F4(x) = C x0 = 0 and x1 = 1 ⇒ F4(x) = 5 ⊕ x32
Therefore, in order to guess F 4 (x), we have first to guess bit k 0 . If x 0 = m 0 ⊕k 0 = 0, then we guess k 1 and find that

F 4 (x) = m ⊕ m = C if x 1 = k 1 ⊕ m 1 = 1, i.e. m = m ⊕ C. Otherwise, if x 1 = k 1 ⊕ m 1 = 0, we guess k 3 and find out that m = m ⊕ 5 if x 3 = k 3 ⊕ m 3 = 0 m ⊕ 7 if x 3 = k 3 ⊕ m 3 = 1 .
The case for which x 0 = 0 can be treated in a similar way. Thanks to this gradual way of guessing k, we obtain the desired information by doing only an average of six guesses instead of sixteen.

Conditions on general 4-bit Sboxes

We will now show that the presence of linear conditions like the ones we have shown for S 0 is unavoidable if the number of bits of the Sbox is small compared to the number of (linear) restrictions in the input.

Lemma 1. Let f : F n 2 → F n 2 be a permutation (Sbox). If 2 k -k ≤ n, then there exist a subspace U of dimension k of F n 2 and a vector u ∈ F n 2 such that f | U +u has maximum linearity, that is, there exist nonzero linear masks α ∈ U + u, β ∈ F n 2 for which α • x + β • f (x) is constant in U + u.
Proof. Pick any subspace V ⊆ F n 2 of dimension n -k and set U = V ⊥ . Let L V be an n -k × n matrix whose row subspace is V and let M U be a 2 k × n matrix whose rows are all the elements of U . Note that x ∈ U if and only if L V x = 0. We denote by f (M U ) the matrix which is generated by applying f to every row of M U . We can also define M U + u in the same way for an arbitrary vector u ∈ F n 2 . For an arbitrary vector u, [α, β] ∈ F 2n 2 is a correlation 1 mask in U + u if

L V 0 M U + u f (M U + u) W α β =      L V α c . . . c      (1)
for some c ∈ {0, 1}. We are only interested in solutions where α ∈ U + u. We set u = 0 for convenience, in which case L V α must be equal to zero.

The matrix W has 2n columns and n -k + 2 k rows, so if n -k + 2 k < 2n, the system is necessarily under-determined, the kernel of W is nonempty, and all its elements are masks with correlation 1. If n -k + 2 k = 2n and the kernel contains only the trivial mask (that is, if W is a full rank square matrix), then W -1 [0, 1, . . . , 1] t is a non-trivial mask with correlation 1.

With this lemma we can justify the existence of linear relations in several cases for small Sboxes:

n 1 2 3 4 k 0 1 0 1 2 0 1 2 3 0 1 2 3 4 n -2 k + k 0 0 1 1 0 2 2 1 -2 3 3 2 -1 -8
Relation? ?

It is quite clear that in the cases n = k = 3 and n = k = 4 it is impossible to find such a relation unless the map f is linear, however, in the case n = 4, k = 3 we can still prove the existence of these relations: Lemma 2. For every permutation f : F 4 2 → F 4 2 there exist a subspace U of dimension 3 and a vector u ∈ F 4 2 such that f | U +u has linearity 8.

Proof. Without loss of generality we assume that f (0) = 0, via affine equivalence. We remove the corresponding row from W and we consider c = 0, as for c = 1 would get a contradiction. We again set u = 0. We pick V at random as above but in such a way that U contains certain vectors a, b, c, d. W is then a square matrix which either has rank(W ) < 8, in which case the kernel of W contains at least one non-trivial solution and we are done, or has rank 8. In the latter case the only solution to the equation is the trivial one. We will now show that it is impossible for the matrix W to have rank 8 if we choose a, b, c, d appropriately.

Since n = 4, f cannot be an APN permutation, and it must have a vanishing 2-flat (Theorem 5 in [START_REF] Carlet | Codes, bent functions and permutations suitable for DES-like cryptosystems[END_REF]). There exist distinct a, b, c, d for which

a + b + c + d = 0 = f (a) + f (b) + f (c) + f (d).
(

) 2
This provides a nontrivial relationship between the rows of W which can be used to obtain an equivalent matrix of rank 7 or lower.

A conditional linear property of S 2

Another improvement we will apply is based on the framework for conditional linear cryptanalysis which was presented in [START_REF] Biham | Conditional linear cryptanalysis -cryptanalysis of DES with less than 2 42 complexity[END_REF]. We consider the Sbox S 2 (which is used in round 10 in the attack) and the linear approximation B, x ⊕ 1, S 2 (x) :

(y 2 , y 0 ) = (1, 1)

y 2 = y 0 = 1 x x x 0 1 3 4 5 6 9 A B C D F 2 7 8 E S 2 (x) S 2 (x) S 2 (x) 8 6 9 3 C A 1 E 4 0 B 2 7 F D 5 B, x ⊕ 1, S 2 (x) B, x ⊕ 1, S 2 (x) B, x ⊕ 1, S 2 (x) 0 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1
If we consider the whole domain, the correlation is 4-12 16 = -1 2 . However, under the condition (y 2 , y 0 ) = (1, 1) the correlation increases to 2-10 12 = -2 3 . We will use this condition to improve the correlation of the linear part of the distinguisher.

Improved 12-round attack using Sbox properties

In this section, we apply some of the Sbox properties we have discussed in Section 4 to the 12-round attack of Section 3, whose complexity was only barely lower than that of an exhaustive key search. The reduction in time complexity is achieved by a careful analysis of the key recovery in the first two rounds, as well as a small improvement to the linear approximation of round 10 by using conditional linear cryptanalysis ( [START_REF] Biham | Conditional linear cryptanalysis -cryptanalysis of DES with less than 2 42 complexity[END_REF]).

Improving the differential key recovery

We start by looking at the configuration of required differences and values at the output of S 0 in the first round, which is represented in detail in Figure 3. The figure contains both the differences (top half) and the values (bottom half) which are required at the output of the S 0 layer (state #1). On the top half, if a number is written in a cell, then the bit difference on this cell will influence the difference in the column indicated by the number written inside at the input of S 1 in state #2 (more differences might affect it but it is not important and for a better readability of the drawing we just write one here). The color of the background of such a cell indicates whether the difference is fixed (grey) or variable (white). On the bottom half, if an indexed number a b is written inside a cell, then the bit associated to this cell will influence the value of bit b of the input of Sbox a in the S 1 layer. For space reasons, symbols are used when more than one bit is influenced. We only need the values associated to columns 31, 18 and 17 as the other two Sboxes are part of the differential and thus only knowledge of the input difference is required. The colors of the columns (also indexed with lower case letters from a to f ) indicate where we can reduce the amount of keybits we guess below four.

The main idea is to exploit the fact that we might not need to guess all the keybits at the input of an Sbox: in some cases the knowledge of a few input bits might be enough to determine all the required information about the output if we guess the key in an orderly manner, as we showed earlier. Furthermore, as the conditional relations introduced in Section 4 describe the desired output bit as a linear combination of the inputs it'll sometimes be possible to XOR the associated keybit guess into a keybit guess for the next round. A more comprehensive explanation and more details in the conditions are provided in A from appendix.

As an example, if we need to determine the input bit of State #2

z = y ⊕ k 1
for some keybit k 1 of round 1 and we know that y = x ⊕ k 0 for some key-bit k 0 of round 0 and plaintext bit x (thanks to conditions), then we can combine the two key guesses into one, as z = x ⊕ k 1 ⊕ k 0 . This can only be done once for each input bit of S 1 (it is impossible to merge one bit of K 1 with several bits of K 0 at the same time).

We have considered all the active Sboxes of the state immediately after the application of S 0 , as shown in Figure 3. We consider six categories of columns "of interest" depending on the outputs which are required for the attack. For each of this, we are going to compute the multiplicative time factor that we gain with respect to guessing naively, as was done in the previous attack.

Columns of type a (yellow).

There are 2 Sboxes (23,29) which are inactive and need no key guessing at all (the same as in the previous attack). These provide gain factor of 2 -8 with respect to a full subkey guess.

Columns of type b (orange). In columns 10, 14 and 26 we require no output differences, but we need to determine a single output bit from each. Instead of guessing sixteen keybits, we can make use of the properties of S 0 :

-Column 26: we only need y 0 , which we can determine as follows:

• If x2 ⊕ x1 ⊕ x0 = 0 then: * If x1 ⊕ x0 = 0 then y0 = x3 ⊕ 1. * If x1 ⊕ x0 = 1 then y0 = x0 ⊕ 1. • If x2 ⊕ x1 ⊕ x0 = 1 then y0 = x3 ⊕ x2 ⊕ x0 ⊕ 1.
For a given plaintext, we consider six possible guesses of the key instead of sixteen on each column, thus resulting in a 6/16 gain factor for each.

-Column 14: we only need y 2 , which can be determined as follows with a gain factor of 6/16:

-Column 10: we only need y 3 which can be determined as follows with a gain of 4/16:

• If x3 = 0 then y3 = x2 ⊕ x1 ⊕ x0. • If x3 = 1 then y3 = x3 ⊕ x2 ⊕ x1.
We obtain a gain factor of 6 16 • 6 16 • 4 16 2 -4.83 . In addition, we can absorb the last bit guess for some of the columns into the next round. As bit x 3 of column 17 in S 1 is associated to both Sboxes 10 and 26 in S 0 , we can only do this a total of two times (round 1 input bits x 3 in column 17 and x 1 in column 18). The overall gain factor with respect to a full subkey guess is 2 -4.83 •2 -2 = 2 -6.83 . The trees associated to these conditions can be seen in Figure 4 from the appendix.

Columns of type c (red). In columns 2, 3 and 19, we require no output difference but two output bits are needed. We proceed as in the previous case, but considering both bits at the same time.

-Column 19: We need y 1 and y 3 . Using the trees from Figure 5c in the appendix we can see that determining both bits y 3 and y 1 requires three bits in total. We are also able to absorb one keybit into the next round (x 2 from column 17), but the other bit has to be guessed. The gain for this column is thus

2×2 3 2 6 = 2 -2 .
-Column 3: We need y 0 and y 2 . We can obtain an average guessing cost of 10 as seen in the corresponding tree from Figure 5b, which gives a gain factor of 2 -0.68 . -Column 2: This column (Figure 5a) has the same complexity as 19, as both their trees have the same number of leaves, and also contains two new keybits that might be absorbed: we need 3 input bits to determine the two desired output bits. We can absorb also one keybit in the last linear relation, that can be the keybit from x 0 of column 17 or from x 2 of column 31. We thus also obtain a gain factor of 2 -2 .

Combining the gains from these Sboxes we obtain a total factor of 2 -4.68 .

Columns of type d (pink). Columns 15 and 28 only require no output difference, but this difference is not fixed. There are four possible differences in column 28: 0, 4, A or E (as both ∆x 1 and ∆x 3 come from difference ∆x 2 in column 18 from the next round), which appear with probability 1/4 (this can be deduced from the DDT of S 1 and the output differences for columns 18 and 31). We first guess the parts of the first round subkey which determine the values at the inputs of columns 18 and 31, so that we know which difference we want at the output of column 28. This is only possible because we only need the output differences from these two columns, and no actual bit values.

We will use the trees built with function F ∆ mentioned in Section 4.1 that are detailed in Figure 6 in the appendix. As an example, if we compute the cost when the desired output difference in column 28 is 4 on average there are 6 possible guesses. The costs for the other non-zero differences are obtained in a similar way and are 2 3 for both. The overall cost becomes:

1 4 6 + 1 4 2 3 + 1 4 2 3 + 1 4 • 1 2 2.52
instead of 2 4 , and implies a gain factor of 2 -1.48 . For column 15 we have two possible output differences: 4 and C (as input ∆x 3 in column 18 is always 1). For difference 4 the average cost is 6, and for C the average cost is 10, which gives a total gain factor of 6/2+10/2 16 = 2 -1 . Both gain factors multiply to 2 -2.48 .

Columns of type e (turquoise). In columns 1,7, 8 and 11 we have a fixed difference and we also need to determine some output values. We will also use the conditions given by functions F ∆ mentioned in Section 4.1, but now we have also to look at the values of the inputs and outputs to satisfy the conditions. Let us illustrate the example for column 1.

In column 1 we have a fixed output difference of ∆ = 1 and we want to determine bit y 1 . If we consider function F 1 , we can see that there are 8 possible input differences δ: 3, 6, 9, C, B, A, E or F. In order to determine whether a pair (x, x⊕δ) leads indeed to the desired output difference 1, we always need to guess three key bits: this is because for any fixed δ the set {x : S 0 (x) ⊕ S 0 (x ⊕ δ) = 1} is an affine space (of dimension 1) and therefore can be described by three linear conditions, i.e. three key bits are needed in order to verify them. In each of these cases, the three bits needed to guess whether a pair is a good pair are enough to determine y 1 . Column 1 has therefore a gain factor of 2 -1 .

We can do the same thing with columns 7, 8 and 11. In the case of columns 7, some of the possible input differences define an affine space {x : S 0 (x) ⊕ S 0 (x ⊕ δ) = 8} of dimension 2, that means only 2 keybits are needed for guessing a good pair with this particular input difference. Taking into account that a further guess is sometimes needed for then determining the desired output values, the number of needed known key bits can be reduced from the full guess and we obtain a gain factor of 2 -1. 13 . For column 8 we have the output difference that affects one of the needed values, so we will need to guess the four input bits, but we can always absorb the bit x 3 of column 31, so the gain factor is still 2 -1 . For column 11 all four input bits need to be guessed for each considered input difference, but for two input differences that represent half of the cases (B and 2) two of the guesses independently determine the values of the two needed values. That means that bit y 3 , that corresponds to bit x 3 , of column 18 can always be absorbed, as it wasn't done before; and that bit y 1 , corresponding to bit x 0 of column 17 that was absorbed half of the times in column 2, can now be absorbed the other half of the time. For the other half of the cases only y 3 can be absorbed. The overall gain factor for column 11 is 2 -1. 19 .

In total these columns generate a gain factor of 2 -4.32 .

Columns of type f (purple). We have three columns of this type: variable difference and some values needed. Depending on the value of the difference, we will find some of the cases previously studied.

For half of the cases of column 22, when the difference is zero, we can just use the same tree from Figure 5b, which gives a factor of 10/16, while in the other half of the cases, when the difference is 4, the case is similar as for the e column 8, and we obtain a gain factor of 1/2 absorbing the bit 31 0 , which gives 1/2 • 10 16 + 1/2 • 2 -1 = 2 -0.83 . For column 20, the desired bits are y 0 , y 1 and y 3 . When the difference is 0, an optimal tree for simultaneously determining these bits is given in Figure 7. From this we obtain a gain factor for this columns of 1/2 • 2 -0.42 + 1/2 = 2 -0.19 .

Column 0 is exactly the case of column 26 when the difference is zero. We can even absorb bit x 0 of column 18 as it hasn't been absorbed before. When the difference is 1, we recover a similar case as for columns of type e, having in this case a gain factor of 1/2. The gain factor of this column is therefore 1/2 • 6 16 • 1/2 + 1/4 = 2 -1.54 . This gives a total gain factor for these columns of:

2 -0.83 • 2 -0.19 • 2 -1.54 = 2 -2.56 .

Conditional linear cryptanalysis

In the case of the linear key-recovery for the last rounds, even though similar properties exist for S 3 to the ones we have used for S 0 , exploiting them is much more complicated than in the differential part, as we are performing the last round key recovery with the FFT. Nevertheless, we can apply conditional properties in the Sbox S 2 of the previous round, round 10, using the framework which was established in [START_REF] Biham | Conditional linear cryptanalysis -cryptanalysis of DES with less than 2 42 complexity[END_REF].

If we look at the linear approximation of Sbox 10, if we impose the condition that its outputs y 0 and y 2 are not both 1 at the same time, then the correlation goes from -1/2 to -2/3. This would improve the overall correlation by a factor (2/3×(1/2) -1 ) 4 = 2 1.66 . As we have to discard the ciphertext pairs which do not verify the condition, we only keep a proportion of (3/4) 2 = 2 -0.83 . With this we can reduce the data complexity to 2 0.83-1.66 , resulting in 2 123.13 × 2 4 = 2 127. 13 . However, since the bottleneck of the previous attack was the exhaustive search, we instead keep a similar data complexity of 2 123.92 × 2 4 = 2 127.92 , so that the advantage increases to 23.

We still have to see how this affects the the key recovery in the final round: with respect to the previous attack, we require output bit y 2 of Sbox 10 in round 10. This additional bit only activates column 6 in the next round. The number of active keybits in the last round is thus 56.

Complexity and trade-offs

We now compute the time complexity of this improved version of the attack. The data and memory complexities are 2 127.92 . If we consider all the gain factors we have accumulated, the cost of the key recovery part is 2 140-8-6.83-4.68-2.48-4.32-2.56 • 2 123.92-3.5 + 2 4 • 112 • 2 112 • 2 -4.17 Trade-offs between data and time. We can reduce the data and memory complexities by relaxing one of the conditions in the first rounds, though this increases the time complexity. We remove the condition on the difference in bit x 0 in column 31 of state #2. This reduces the data complexity by a factor 2 2 . This changes the differences in columns 29, 26 and 13 from Figure 3: column 29 becomes a column of type e, column 26 becomes a column of type f , and column 13 won't impact the complexity as it was not exploited in the attack.

Column 29. Its previous gain factor was 2 -4 . For the 3/4 of the cases where the previous bit condition in column 31 no longer holds, we want an ouput difference of 8 (Figure 6e). The new cost for this column is

1/4 × 1 + 3/4 × 10 = 2 2.954 ,
which results in a more modest gain factor of 2 Attack with the best data complexity. As we have discussed in Section 3.2, in order to improve the correlation of the distinguisher, we chose to determine three of the five Sboxes active in round 1. We now show how to also determine the fourth one that was considered interesting, allowing to make the data complexity smaller.

In this case there will then be no conditions imposed in the differences of state #2. We can proceed as in the previous attack, and we will obtain one column of type a (23), three columns of type c (2,3 and 19), three columns of type e (0, 7 and 8), and four columns of type f (12, 22, 26 and 29). We compute the gain factor the same way as before, and we obtain for column 29: 2 -1.607 , column 26: 2 -1.192 , column 23: 2 -4 , column 22: 2 -1.35 , column 19: 2 1.41 , column 12: 2 -1 , column 8: 2 -1.678 , column 7: 2 1.41 , column 3: 2 -0.415 , column 2: 2 -0.415 and column 0: 2 -1.54 . This gives a total gain factor of 2 -16.023 . We will not consider the conditional linear property in the output as otherwise the term related to the FFT would be the bottleneck, and this implies that for a data and memory complexity of 2 118.40 , which gives an advantage of 16 bits, we have a time complexity of: 2 128+16-16.023 • 2 118.40-3.5 + 2 4 • 104 • 2 104 • 2 -4.17 + 2 256-16 = 2 242.93 12-round encryptions.

Conclusion

In this paper we improved upon the best known attacks on Serpent. Our improved differential-linear attack has simultaneously lower time, data, and memory complexities than the best previous attacks. We would like to stress that our improvements do not modify the underlying distinguisher at all, and only focus on the data selection and, most importantly, the key-guessing procedure. We find it remarkable that by focusing solely on this part, we are able to significantly improve (and thereby actually fix) previous results.

While our approach in this paper is highly specific to Serpent and the differentiallinear distinguishers we used, its ideas can be applied more generally, both to other attacks as well as to other ciphers. Indeed, as mentioned above, our work here is the predecessor of the general framework of [START_REF] Broll | Generic framework for key-guessing improvements[END_REF]. Our work also serves as an application of these ideas to differential-linear cryptanalysis, an example of which was not present in [START_REF] Broll | Generic framework for key-guessing improvements[END_REF].

A Connection to the Tree-Based Key-Recovery of [START_REF] Broll | Generic framework for key-guessing improvements[END_REF] and Conditions used in Section 5

The conditions used in the attack of Section 5 and Section 4.1 can be expressed in terms of a special type of binary decision trees (called affine decision trees in [START_REF] Broll | Generic framework for key-guessing improvements[END_REF] and parity decision trees elsewhere when the bit-length of the output is one). The authors of [START_REF] Broll | Generic framework for key-guessing improvements[END_REF] examine those trees formally. An affine decision tree is a regular binary tree for which the inner nodes represent the decision rule for evaluation and the leaves represent the function values of all inputs arriving there.

Given a tree for a (non-constant) function f and undetermined (resp. partially determined, key-dependent) input x which has to be evaluated in the key guessing phase, one needs to guess the bit b = α, x indicated by the root and then follow the appropriate edge to the sub-tree representing the function f | α,x =b (here: the left sub-tree represents f | α,x =0 and the right f | α,x =1 ). Each leaf represents an affine subspace on which the function is constant and whose codimension is the depth of the corresponding leaf.

Let the tree for f have k leaves with corresponding affine spaces A 1 , . . . , A k (which we identify with the leaves) and depths d 1 , . . . , d k . When we arrive in a leaf A i , we have made at most d i additional guesses during the key guessing phase. The size of each space is |A i | = 2 n-di . That means that the total cost incurred is k i=1 2 di 2 -di = k since 2 di is the cost of guessing d i bits and we will end up in A i for a proportion of 2 -di inputs. Put differently, the multiplicative gain over guessing all n bits of input is k 2 n . As noted in [START_REF] Broll | Generic framework for key-guessing improvements[END_REF], the goal in most attack scenarios is therefore to minimize the number of leaves (the size of the tree).

In the following, we write selection patterns α as hexadecimal numbers, whose binary representation is regarded as an element of F 4 2 . The bold numbers refer to leaves, and depending on the number of output bits m, is a hexadecimal number between 0 and 2 m -1.

In the following, we give the trees used in the attack of Section 5.

Columns of type b. Let us first look at the set of relations for Sbox S 0 given in Section 4.1. Those relations make up size-minimal trees for coordinate functions of S 0 : y i (x) = 2 i , S(x) . Columns of type c. For column 19 (type c) one can derive from the conditions given in Section 4.1 that only three bits are necessary to determine both y 1 and y 3 using the tree from Figure 5c. The resulting gain (8/16) is optimal. One additional bit can be absorbed by adding the corresponding keybit from the next round to the final linear relation. The same happens for column 2, giving each of these two columns a gain factor of 2 -2 . Column 3 has a smaller gain of 2 -0.68 .

The trees for columns of type c can be found in Figure 5.

Columns of type d (and e). For columns of type d we have to determine good pairs (x, x ) whose output difference ∆ = S 0 (x) + S 0 (x ) belongs to a fixed subset, like for example ∆ = 4: Given x, we look at the function F ∆ mentioned in Section 4.1. Its corresponding tree is given in Figure 6a. It has size 6 and therefore a gain factor of 6/16. When the expected output difference is 0, so must be the input difference. Therefore instead of guessing 4 bits, we need not guess any. Hence we gain a factor of 1/16 in this case. The corresponding tree has one leaf only.

The size-minimal trees for the other three possible differences C (for column 15) and A and E (for column 28) can be found in Figure 6, as well as the tree for the difference 8 of column 29 used for the better memory trade-off. A tree for column 20 of type f . For column 20, when the output difference is zero the right input pairs are trivial, while the three output bits must be determined.

The tree shown in Figure 7 shows how to do an optimal guess in order to do that. Fig. 7: Tree for column 20, to determine output bits y 0 , y 1 and y 3

  3 = 1 or ∆[31] 0 = 1, we reject the plaintext for this key guess. -Together with the fixed ∆[11] = 9, ∆[14] = 8, we have obtained the appropriate input difference for round 1, ∆. -The associated plaintext is x = S -1

  31

Fig. 3 :

 3 Fig. 3: Reducing the required keybit guesses in the first round.

2

 2 231.91 equivalent encryptions, while the exhaustive search has cost 2 256-23 . The total time complexity is thus around 2 233.55 12-round encryptions.

Fig. 4 :

 4 Fig. 4: Trees for 2 i , S 0 (x)

19 Fig. 5 :

 195 Fig. 5: Trees for columns of type c

∆ = 8 Fig. 6 :

 86 Fig. 6: Trees for F ∆ = S -1 0 (S 0 (x) + ∆) + x, columns of type d

Table 1 :

 1 Summary of working 12-round attacks on Serpent. The adjustment of some of the complexities and attacks with flaws is discussed in the text.

	Complexity

  w 33 , w 66 , w 99 ) {k 1 , k 34 , k 67 , k 100 } = S 2 (w 1 , w 34 , w 67 , w 100 ) • • • {k 31 , k 64 , k 97 , k 130 } = S 4 (w 31 , w 64 , w 97 , w 130 ) {k 32 , k 65 , k 98 , k 131 } = S 3 (w 32 , w 65 , w 98 , w 131 )

  State after S 0 , values: * : 17 1 , 31 0 * * : 17 2 , 18 2 • : 17 0 , 18 0 • • : 17 0 , 18 3 † : 17 2 , 31 0 † † : 17 2 , 18 2 Value from y 0 /y 1 /y 2 /y 3 in Sbox 17/18/31

	State after S 0 , differences:
	17 11					11							31													18 17			14 18	∆y0
	31 31		18 17		18 17						18 17 17			18 17			31			11							∆y1
				31			18 17		18 17						18				14			11		31							∆y2
				18 17		18 31			18 17		18 14 18 17				18		31		14			11					∆y3
	31	30	29	28	27	26	25	24	23	22	21	20	19	18	17	16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
	• 17 0			18 3 17 3				18 0 17 0 31 2			31 1				31 0 31 0				31 3 18 2 17 2 18 2 * * *		18 0	y0
		31 1					31 0					18 2 17 2 18 1 17 1				18 0 17 0										31 2		y1
	31 2 31 2			31 1 18 2 17 2 31 0 31 3			18 2 † † †		18 1 17 1				18 0 •• 17 3 31 2			18 0 17 0			y2
								31 3			18 2 17 2 31 0								18 3 17 3				18 0 17 0		31 2			y3
	31	30	29	28	27	26	25	24	23	22	21	20	19	18	17	16	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
			a d		b			a f		f c				d b			e b		e e				c c e f
																															GAIN
		17 Variable difference from Sbox 17/18/31 Fixed difference 11 17 0 a Free columns b No difference, 1 output value c No difference, 2 output values				2 -8.00 2 -6.83 2 -4.68
																		d No values, variable output difference		2 -2.48
																		e Fixed difference, 1 or 2 output values		2 -4.32
																		f Variable difference, 1 to 3 values			2 -2.56

  2.954-4 = 2 -1.04 . Time complexity for a data complexity of 2125.74 . By considering the new gain factors and choosing a different amount of data and advantage, we obtain: 2 140-4-1.04-5.40-0.6-4.68-2.48-4.32-2.56 • 2 123.74-3.5 + 24 • 112 • 2 112 • 2 -4.17 equivalent encryptions for the key recovery and 2 256-21 encryptions for the exhaustive search, which result in an overall time complexity of 2 236.31 . This time the data and memory complexities are 2 123.74 × 2 2 = 2 125.74 .

	Column 26. Its previous gain factor was 6/16 = 2 -1.415 . However, this will now
	only apply to 1/4 of the data, which is when the bit condition in column 31
	holds. For the other 3/4, the guessing cost is 12/16, results in the cost
	1/4 × 6 + 3/4 × 12 = 2 3.39 ,
	and a new gain factor of 2 -0.6 .

We contacted the authors with respect to this, but they were unable to provide any further information. We also contacted the authors of[START_REF] Liu | Differential-linear cryptanalysis from an algebraic perspective[END_REF] and they agreed in a personal communication, which is why these results are not cited in[START_REF] Liu | Differential-linear cryptanalysis from an algebraic perspective[END_REF].

Acknowledgment

This work was partially funded by the DFG, (German Research Foundation) under Germany s Excellence Strategy -EXC 2092 CASA -390781972. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement no. 714294 -acronym QUASYModo).


Thi Thu

Nga Vu
email: vu@laplace.univ-tlse.fr

Gilbert Teyssedre
email: gilbert.teyssedre@laplace.univ-tlse.fr

Bertrand Vissouvanadin
email: bertrand.vissouvanadin@laplace.univ-tlse.fr

John Yuddy
email: john.yuddy.sr@gmail.com

Christian Laurent
email: christian.laurent@laplace.univ-tlse.fr.

Transient space charge phenomena in HVDC model cables

Keywords: Space charge, HVDC cable, electric field distribution, current transients

In the development of polymer-insulated HVDC cable systems, space charge and conduction current are among the most important features to analyze. Space charge accumulation in the insulation drives the field distribution and directly impact on the performance of the cable. To have further information on the evolution of space charge, conduction current measurements under various electrical and thermal conditions are of great importance. Reversely, knowledge on space charge features brings understanding in conductivity behavior. The aim of this paper is to investigate the accumulation of space charge and charging current transients under various conditions of temperature and applied voltage in 1.5 mm-thick cross-linked polyethylene (XLPE) insulation of mini-cables by means of simulation and measurements.

INTRODUCTION

The number of HVDC link projects is experiencing an unprecedented growth due to the superiority of DC over the traditional HVAC energy transport [START_REF] Mazzanti | Extruded Cables for High-Voltage Direct-Current Transmission[END_REF]. Further, the development of insulating materials for HVDC cable manufacturing, especially polymers provides advantages in terms of cost, operating temperature, the risk of pollution or maintenance in comparison to impregnated paper-based insulation [START_REF] Hanley | A General Review of polymeric insulation for use in HVDC Cables[END_REF]. However, the use of synthetic insulation under electrical stress is generally confronted to space charge accumulation issues which may lead to the reduction of the cable performance and/or lifetime.

Among the various possible mechanisms of charges accumulation, the effect of conductivity gradient in the insulation, resulting from the distribution of temperature and/or electric field, has been the subject of many studies [3, 4, and 5]. It has been pointed out in the literature that the conductivity of polymeric insulator may vary strongly with temperature and magnitude of electric field. It has been also widely shown that space charge amount depends directly on conductivity gradient and thermal activation energy of conductivity. Therefore, conduction current measurements under various electrical and thermal conditions are of great importance to have more information on the evolution of space charge.

The objective of this paper is to report on transient space charge phenomena amongst which front of charges and charging current transients obtained under various conditions of temperature and applied voltage in the insulation of mini-cables. Several hypotheses are raised for explaining the front of charges and possible correlation to current transient in cylindrical geometry. The study requires assessing the evolution of conductivity vs. thermal and electrical stresses in the mini-cable. A two-dimensional function of the cable conductivity can be obtained from the fit of conduction current data acquired under various conditions of temperature (T) and voltage (V) using an analytical function of conductivity following the procedure explained in [START_REF] Vu | Correlating Conductivity and Space Charge Measurements in Multi-dielectrics under Various Electrical and Thermal Stresses[END_REF]. The obtained semi-empirical function of conductivity has been subsequently used in simulation to evaluate charging current transients in mini-cable.

EXPERIMENTAL Samples

Samples used for conductivity and space charge measurements are mini-cables provided by Nexans. The test samples are sections of cables of approximately 3 m in length. The cable characteristic dimensions are reported in Fig. 1 where:

• The radius of the inner conductor is of 0.7 mm;

• The thicknesses of the internal and external semiconductor (SC) are respectively 0.7 mm and 0.15 mm;

• The inner and outer radius of insulation, ri and re are respectively 1.4 mm and 2.9 mm; The insulator thickness is 1.5 mm.

Space charge measurements on mini-cable samples

Space charge measurements have been carried out using the pulse-electro-acoustic (PEA) method through the configuration of Fig. 2. The PEA cable device was provided by TechImp S.p.A., Italy. The cable was fixed to the PEA cell using a mechanical holder insuring a good acoustic contact between the outer SC and aluminum electrode of the measuring device.

A pulse generator, providing 30ns duration voltage of up to 5 kV amplitude and 10 kHz repetition rate, was used for the PEA set-up. At maximum amplitude, the pulse frequency must be reduced to 5 kHz to avoid overheating of the output terminal resistor used for impedance matching. The pulses were injected to the measurement area via the outer SC of cable. The outer SC was removed over a length of 5 cm (cf. Fig. 2) between the measuring location and the region where pulses are applied creating a decoupling capacitor between pulse and HVDC supply. For electrical stress, a negative DC voltage was applied to the cable conductor using a Rogovsky electrode. Such an electrode was used for the purpose of reducing the electric field and perturbation-induced discharges occurring at the connecting areas between the cable and the high voltage source. Two voltage levels were investigated in this work: -30 kV and -55 kV, providing Laplacian fields EI of ~ -30 kV/mm and -55 kV/mm at the interface with the inner SC, respectively; and -14 kV/mm and -26 kV/mm at the outer SC.

Space charge measurements on mini-cables were performed under two different temperature conditions: at room temperature (~22 0 C) and under a temperature gradient through the cable radius. To achieve a temperature gradient across the cable insulation, a current was injected into the cable core by means of a current transformer, as shown in Fig. 2, while the external surface of the semiconductor was kept in ambient. For the latter condition, the targeted temperature at the inner semiconducting screen was 70°C. Thermal modelling of the cable was achieved to set the current to be injected targeting a temperature of 70°C at the inner SC. The result was a current of 32 A, providing a surface temperature of the cable of 60°C.

The surface of the cable is expected to reach a steady state temperature after a period of about 1h of heating and stabilizes around a value of 60°C.

The amplitude of pulses in the PEA measurement was set to 400 V and repetition frequency to 5 kHz. PEA measurements consisted in a cycle of 4h/4h of polarization/depolarization. One new cable sample was used for every stress level. Space charge profiles were recorded every 200 seconds throughout the measurement protocol. The calibration procedure used for space charge recovery is presented in [START_REF] Vissouvanadin | Deconvolution techniques for space charge recovery using pulsed electroacoustic method in coaxial geometry[END_REF].

Conductivity measurements on mini cable samples

The setup used for current measurements in mini-cable samples is shown in Fig. 3. The outer SC is removed in some section of the cable for preventing surface conduction. Guard electrodes of 1cm length were created at both ends of the active area of measurement. The measuring electrode of 20 cm length, 1 cm apart from the guard electrodes, was connected to a Keithley 617 electrometer through a protecting circuit. A 35kV DC high voltage generator from FuG Elektronik GmbH was directly connected to the cable core. The electrometer and DC supply are interfaced via a GPIB bus for data acquisition.

The cable sample is placed in an oven in air at atmospheric pressure for varying the temperature accurately.

Measurements were performed under different temperatures varying from 30°C to +90°C by step of 10°C. For each of the temperature levels, charging/discharging current measurements were realized for 10 values of applied field ranging between 2 and 25 kV/mm under isothermal conditions. Polarization/depolarization steps last for 1h/1h. A new sample has been used for each value of temperature to avoid possible memory effects. Current values were recorded every 2 seconds all along the measurements.

RESULTS

Space charge measurement results: evidence of front of negative charges

Fig. 4 shows the color-scaled spatio-temporal cartography of space charge density for applied voltages of -30 kV and -55 kV at room temperature. In this representation, time is along axis X while the cable insulation radius is on Y axis (anode is to the top, cathode to the bottom). Blue and red colors correspond to negative and positive charges respectively. During volt-on, a negative charge region builds-up over more than half of the insulation with a density sensibly increasing with stressing time. The negative charge density in the bulk of insulation is substantially higher under -55kV compared to that obtained under -30 kV.

A front of negative charges generated from the cathode markedly appears at the beginning of the polarization step for both applied voltages. The front of charges crosses the cable insulation from the inner SC to the outer SC. The occurrence of the negative charges front phenomenon is even more pronounced under -55 kV (the density of transported charges being higher) than that under -30 kV. The transit time of the front from the inner electrode to the outer electrode is estimated to about 38 min and 1 hour at -30 kV and -55 kV, respectively. We also observe a concomitant build-up of negative charges in the bulk of the insulator during the front of charges progression towards the anode. Under a temperature gradient of 10°C (Fig. 5), a negative space charge region settles rapidly from the inner SC and extends up to the outer SC forming heterocharges (after 100s under -55 kV). At the end of the 4 h polarization step, the maximum density of negative charges is in the order of 0.5 and 1 C/m 3 for -30 kV and -55 kV, respectively.

The cartography also reveals a front of negative charges with a transit time to reach the anode estimated to 18 min under -55 kV, slower than under -30 kV (12 min).

The amount of accumulated charges substantially increases with the electrical stress. Thus, when the applied voltage changes from -30 to -55 kV, the charge density increases in the insulator and the redistribution of electric field is significant both in presence and absence of temperature gradient.

A higher temperature (65°C in average through the cable insulation) associated to a temperature gradient of 10°C leads to a significant accumulation of negative charges in the bulk of insulation. Furthermore, the sign and the shape of accumulated charge profiles obtained in the presence of thermal gradient suggest an effect due to conductivity associated to the temperature gradient over the cable radius. Indeed a negative space charge spread over the all insulation is expected under negative voltage in such a thermal condition [START_REF] Fabiani | HVDC Cable Design and Space Charge Accumulation. Part 3: Effect of Temperature Gradient[END_REF]. For measurements at room temperature, a substantial field dependence of the conductivity is necessary to explain the formation of a negative space charge in cylindrical geometry [START_REF] Mcallister | Charge Accumulation in DC Cables: A Macroscopic Approach[END_REF]. We present some conductivity measurements on these cables in the next section, though these are limited to applied voltage of 30 kV and cannot be easily extrapolated to higher field. Most of space charge cartographies exhibit the phenomenon of front of negative charges originating from the cathode and reaching the anode after a certain time. It is worth to note that the velocity of the front of negative charges depends on the condition of temperature and applied voltage. The transit time of the front and the corresponding apparent mobility at various electrical and thermal stresses are summarized in Table 1.

Mobilities were estimated from the following equation, considering the mean field, Eavg, in the cable insulation:

𝜇 ≅ 𝑟 𝑒 -𝑟 𝑖 𝐸 𝑎𝑣𝑔 . 𝑡 𝑡 (1)
where re and ri are the outer and inner radius of the insulation and tt is the transit time, Eavg is the average of the Laplacian fields at the inner and outer radius of cable insulation.

Table 1: transit time of negative charges front and its apparent mobility at various electrical and thermal stresses

Surprisingly, it is found that the transit time of the negative charges front increases, and therefore the mobility decreases, with the applied voltage. To get a better understanding of the dependency of the charge fronts kinetic with temperature and voltage stresses, conduction current measurements have been carried out on mini-cable samples subjected to various electrical and thermal conditions.

Conduction current measurement results: evidence of current peak during transient

Results of charging current transients of mini-cable sample at 40°C under different fields are represented in Fig. 6.

Fig.6: Charging current transient of mini-cable at 40 0 C for different applied voltages

For almost all temperature values, the charging current increases at short time and reaches a maximum value, then it decreases with time for approaching steady state value. Moreover, the involved mechanism is clearly thermally activated since the time to peak decreases with increasing temperature with following approximately an

Arrhenius law (see next sections).

There are, at least three possible mechanisms to be considered to explain such an increase of the transient current during short time:

1) Charges injection and transport through the insulationin that case, the time to peak would be directly related to the transit time of carriers through the insulation;

2) A process linked only to the front of negative charges previously observed on space charge patterns. The time to current peak could be related to the transit of charge front.

3) An association of field dependent conductivity and divergent field (due to cylindrical geometry) where the current transient could correspond to the balancing of the field distribution. In this case then one needs to compute voltage and temperature variation of conductivity.

In the following, the latter hypothesis is investigated first. Computing current transients, using e.g. a numerical solver, requires an analytical expression of conductivity as a function of field and temperature. Current data obtained on cable sections can be used for this purpose; however, with this geometry, present results cannot be used directly to obtain the field dependence of conductivity. Indeed, the steady state field distribution varies along the cable radius and is a priori unknown because it depends itself upon conductivity. A functional form has to be hypothesized for the field dependence of conductivity.

Current-voltage model for current transient calculation in cable geometry

An expression of conductivity generally adopted for polymeric materials is as follows:

σ(E, T) = A. exp ( -E a k B T ) . sinh(C(T). E(r)) E(r) ( 2
)
where A is a constant. Ea is the activation energy of conductivity and C is a temperature-dependent coefficient.

Noting:

B = A. exp ( -E a k B T ) (3)
From the conductivity expression (2), the current flowing in the external circuit during steady state is given by:

I(T) = B. sinh(C(T)E(r)). 2. π. r. ℓ (4)
Where r is the radius, r i ≤ r ≤ r e and ℓ is the measuring section length of the cable (ℓ = 20cm).

From there, the field at the radius r can be deduced from the expression of the conduction current:

E(r) = 1 C . sinh -1 ( I B. 2. π. r. ℓ ) (5)
Integrating the above expression of the electric field from the internal to the external radius gives the following relationship between the applied voltage (Vapp) and the total current (I):

-V app = K(I) C ( sinh -1 (K I ) K I - sinh -1 (K E ) K E + 1 2 log {[K E 2 + 1] 0.5 -1} {[K I 2 + 1] 0.5 + 1} {[K E 2 + 1] 0.5 + 1} {[K I 2 + 1] 0.5 -1} ) (6)
where

K(I) = I B.2.π.ℓ K I (I) = I B.2.π.ℓ.r i K E (I) = I B.2.π.ℓ.r e
The above expression was used to fit experimental quasistationary charging currents versus voltage for estimating the B and C coefficients at various temperatures. The coefficients obtained for conductivity Eq. 2 of XLPE minicable are shown in Table 2.

A (SI) 0.15 Ea (eV) 0.43 C (m/V) 2.4.10 -9 T -6.8.10 -7 for 313 T  363 K Table 2: Coefficients obtained from the fit of conduction current data (T from 40°C to 90°C, V from 4 to 30 kV) using Eq.6 on mini-cable.

Experimental data fits of XLPE mini-cables for different voltages and temperatures have been achieved and model-measurement comparison is presented in Fig. 7. It can be argued that there is a fairly good fit of data particularly for temperatures above 60°C, possibly because at these temperatures steady state is likely to be reached more quickly so that the difference between 1h charging currents and steady current values is negligible, which is no longer the case at lower temperatures.

DISCUSSION

The above model can be used to check possible links between transient processes obtained in space charge and conduction measurements. The semi-empirical model of conductivity was implemented into Comsol® software to compute the current transients in the mini-cables subjected to stresses applied in the experimental measurements. Fig. 8 shows the modeled current as a function of time at 40°C under various voltage stresses from 4 to 30 kV on minicable. There is no appreciable variation in time of the current, meaning no prominent transient. The time constant (/) is relatively large, of the order of 4h at 40°C and 10kV/mm, and comparable to the measurement and modelling time scale. The small amplitude of the transient is a consequence of the mild field dependency of conductivity of the material (a relatively low C coefficient is obtained). Therefore, it is clear that the only effect of electric field dependence of conductivity in hypothesis 3) is not able to explain the current peaks observed in charging current transient (see Fig. 6). In respect to hypothesis 1), we consider the time to peak of charging current. Fig. 9 represents the time in which current value reaches a maximum as a function of temperature for different applied voltages. This time depends strongly on the temperature and field. On the assumption that the measured time corresponds to a time transit of the carriers, and considering the average field applied to the insulation, in the same way as for estimation of propagation speed of charge front, a dependency as 1/V of the transit time tti is expected: To give an order of magnitude of mobility, tti obtained at 30°C under 6 kV is of the order of 1000 s so that the deduced mobility is of the order of μ ≈ 4.10 -13 m²/V/s. For an applied voltage of 30 kV (see Fig. 9), the time to current peak decreases with temperature according to the Arrhenius law with activation energy of about 1.6 eV. Following this trend, at room temperature (22°C) the current peak would occur after 2100 s (35 min) of polarization. This time is comparable to the estimated transit time (38 min) of negative charges front obtained from PEA measurements for the same condition. This result would indicate that the peak occurs when the front of charges reaches the counter-electrode so that the current peak and the front of negative charges would be the signatures of the same phenomenon.

𝑡 𝑡𝑖 ≅ 𝑟 𝑒 -𝑟 𝑖 𝜇. 𝐸 𝑚𝑜𝑦 ≅ (𝑟 𝑒 -𝑟 𝑖 ) 2 𝜇 . 1 𝑉 𝑎𝑝𝑝 (7)
However, the transit time from current measurements clearly decreases with increasing voltage while in the case of space charge measurements it increases when the applied voltage changes from 30 to 55 kV. The latter is a rather unexpected behavior as it implicitly means that the charge mobility would be decreasing with increasing field. However, negative differential mobility has been reported as example by Chen et al. [START_REF] Chen | Observation of negative differential mobility and charge packet in polyethylene[END_REF] for positive carriers. It is also one of the processes explaining the propagation of charge packets maintaining their shape [START_REF] Baudoin | Charge packets modeling in polyethylene[END_REF]. Current measurements under voltages greater than 30 kV were not possible here mainly because for safety reasons for the equipment. The lack of current data at higher voltages could not confirm the increase of the front of charges transit time with the applied voltage. Further, the transit time from current peak is extrapolated at 60°C and 30 kV/mm (from Fig. 9) to few seconds while from PEA (see Fig. 5a) it is 12 min at 30 kV in the presence of a thermal gradient of 60/70°C. It is noteworthy that temperature behaviors appear markedly different for the two phenomena although temperature conditions were not exactly similar (isothermal for current/temperature gradient for space charge). Hence to be in the same conditions, it would be interesting in the future to perform space charge measurements on minicables under isothermal conditions.

Finally, it is worth stressing on the potential harmfulness of such space charge transient processes for cables endurance [START_REF] Fabiani | Measuring a possible HVDC insulation killer: fast charge pulses[END_REF]. Kinetic energy and field strengthening are among the harmful processes whereby early ageing and breakdown of insulations may occur. Many questions are still to investigate such as the impact of polarity on the process, along with the repetitive character when applying consecutive charging/discharging steps.

CONCLUSIONS

Space charge measurements carried out on HVDC minicables reveal systematic occurrence of negative charges front crossing the cable insulation from the inner to the outer electrode. A prominent feature of the charges front concern its transit time which increase and decrease respectively with applied voltage and temperature. Isothermal current measurements on mini-cables in the range between 30°C and 90°C under various voltages were carried out to identify the mechanism behind the charges front phenomenon. A transient process in charging current was observed, exhibiting features of a charge injection process.

We have clearly shown that the transient charging current process cannot be explained by field redistribution due to the non-linear conductivity coupled to the cylindrical geometry. The pending question is on the identical nature or not of the transient processes in space charge and in charging currents. It has been shown that, at a temperature of 30°C, the same mechanism is possibly behind the current peak and the front of negative charges phenomena. However additional work is necessary regarding for example the features of negative differential mobility observed in space charge space transient processes and its counterpart in current transients. Raising these scientific issues is of real importance for the reliability of HVDC cable systems, regard for example of type tests that impose severe transient stresses.

Fig. 1 :

 1 Fig. 1: Section of mini-cable sample

Fig. 2 :

 2 Fig. 2: Schematic representation of the PEA Cable system

Fig. 3 :

 3 Fig. 3: Sketch of current measurement set-up for minicable

Fig. 4 :

 4 Fig. 4: Cartography of space charge density for applied voltages of -30 kV (a) and -55 kV (b) at room temperature

Fig. 5 :

 5 Fig. 5: Cartography of space charge density for applied voltages of -30 kV (a) and -55 kV (b) under a thermal gradient of 10 0 C

  10 -14 1.3 × 10 -14 1.0 × 10 -13 3.8 × 10 -14

Fig. 7 :

 7 Fig. 7: Fit (solid lines) of conduction current data (circles) to the model for various temperatures.

Fig. 8 :

 8 Fig. 8: Computed transient currents at 40 0 C under voltages from 4 to 30 kV on mini-cable.

Fig. 9 :

 9 Fig. 9: Evolution of time for the current peak vs. temperature for different applied voltage

Cite as: T.T.N.Vu, G. Teyssedre, B. Vissouvanadin, J.Y. Steven, C. Laurent, "Transient space charge phenomena in HVDC model cables", 9th Int. Conf. on Insulated Power Cables (Jicable), Versailles, 21-25 June 2015. Proc. JiCable'15, pp. 1-6, 2015

Acknowledgments

We acknowledge L. Boyer from Nexans for provision of minicable samples, and one of us (J.Y. S.) thanks PLN for the financial support.