Gaëtan Leurent

Differential and Linear Cryptanalysis of ARX with Partitioning Application to FEAL and Chaskey

Keywords: Differential cryptanalysis, linear cryptanalysis, ARX, addition, partitioning, Chaskey, FEAL FEAL

In this work, we refine a partitioning technique recently proposed by Biham and Carmeli to improve the linear cryptanalysis of addition operations, and we propose an analogue improvement of differential cryptanalysis of addition operations. These two technique can reduce the data complexity of linear and differential attacks, at the cost of more processing time. Our technique can be seen of the analogue for ARX ciphers of partial key guess and partial decryption for SPN ciphers. We show a first application of the generalized linear partitioning technique on FEAL-8X, revisiting the attack of Biham and Carmeli. We manage to reduce the data complexity from 2 14 to 2 12 known plaintexts, while the time complexity increases from 2 45 to 2 47 . Then, we use these technique to analyze Chaskey, a recent MAC proposal by Mouha et al., that is being studied for standardisation by ISO and ITU-T. Chaskey uses an ARX structure very similar to SipHash. We use a differential-linear attack with improvements from the partitioning technique, combined with a convolution-based method to reduce the time complexity. This leads to an attack on 6 rounds with 2 25 data and 2 28.6 time (verified experimentally), and an attack on 7 rounds with 2 48 data and 2 67 time. These results show that the full version of Chaskey with 8 rounds has a rather small security margin.

Introduction

Linear cryptanalysis and differential cryptanalysis are the two major cryptanalysis techniques in symmetric cryptography. Differential cryptanalysis was introduced by Biham and Shamir in 1990 [START_REF] Biham | Differential Cryptanalysis of DES-like Cryptosystems[END_REF], by studying the propagation of differences in a cipher. Linear cryptanalysis was discovered in 1992 by Matsui [START_REF] Matsui | A New Method for Known Plaintext Attack of FEAL Cipher[END_REF][START_REF] Matsui | Linear Cryptanalysis Method for DES Cipher[END_REF], using a linear approximation of the non-linear round function.

In order to apply differential cryptanalysis (respectively, linear cryptanalysis), the cryptanalyst has to build differentials (resp. linear approximations) for each round of a cipher, such the output difference of a round matches the input difference of the next round (resp. linear masks). The probability of the full differential or the imbalance of the full linear approximation is computed by 1 multiplying the probabilities (respectively imbalances) of each round. This yields a statistical distinguisher for several rounds:

-A differential distinguisher is given by a plaintext difference δ P and a ciphertext difference δ C , so that the corresponding probability p is non-negligible:

p = Pr E(P ⊕ δ P ) = E(P ) ⊕ δ C 2 -n .
The attacker collects D = O(1/p) pairs of plaintexts (P i , P i ) with P = P ⊕δ P , and checks whether a pair of corresponding ciphertexts satisfies

C i ⊕ C i = δ C .
This happens with high probability for the cipher, but with low probability for a random permutation. -A linear distinguisher is given by a plaintext mask χ P and a ciphertext mask χ C , so that the corresponding imbalance1 ε is non-negligible:

ε = 2 • Pr P [χ P ] = C[χ C ] -1 2 -n/2 .
The attacker collects D = O(1/ε 2 ) known plaintexts P i and the corresponding ciphertexts C i , and computes the observed imbalance:

ε = |2 • # {i : P [χ P ] = C[χ C ]} /D -1| .
The observed imbalance is close to ε for the attacked cipher, and smaller than 1/ √ D (with high probability) for a random function.

Last round attacks. The distinguishers are usually extended to a key-recovery attack on a few more rounds using partial decryption. The main idea is to guess the subkeys of the last rounds, and to compute an intermediate state value from the ciphertext and the subkeys. This allows to apply the distinguisher on the intermediate value: if the subkey guess was correct the distinguisher should succeed, but it is expected to fail for wrong key guesses. In a Feistel cipher, the subkey for one round is usually much shorter than the master key, so that this attack recovers a partial key without considering the remaining bits. This allows a divide and conquer strategy were the remaining key bits are recovered by exhaustive search. For an SPN cipher, this technique can be applied if the difference δ C or the linear mask χ C only affect a small number of SBoxes, because guessing the key bits affecting those SBoxes is sufficient to invert the last round.

ARX ciphers. In this paper we study the application of differential and linear cryptanalysis to ARX ciphers. ARX ciphers are a popular category of ciphers built using only additions (x y), bit rotations (x ≪ n), and bitwise xors (x ⊕ y). These simple operations are very efficient in software and in hardware, but they interact in complex ways that make analysis difficult and is expected to provide security. ARX constructions have been used for block ciphers (e.g. TEA, XTEA, Our results. In this paper we study in detail how key bit guesses can be used to analyze ARX ciphers. Our main technique follows a recent paper by Biham and Carmeli [START_REF] Biham | An Improvement of Linear Cryptanalysis with Addition Operations with Applications to FEAL-8X[END_REF] by partitioning the available data according to some plaintext and ciphertext bits. In each subset, some data bits have a fixed value and we can combine this information with key bit guesses to deduce bits after the key addition. These known bits result in improved probabilities for differential and linear cryptanalysis. While Biham and Carmeli considered partitioning with a single control bit (i.e. two partitions), and only for linear cryptanalysis, we extend this analysis to multiple control bits, and also apply it to differential cryptanalysis.

We then demonstrate our techniques with applications to FEAL-8X and Chaskey. We show that this results in a significant reduction of the data complexity, in exchange for some more processing time (for a fixed number of rounds). Alternatively, we can extend the attack to a larger number of rounds with a small increase of the data complexity. Those results are very similar to the effect of partial key guess and partial decryption in a last-round attack: we turn a [29] 2 24 2 24 [2,39] 2 14 2 45

[3] 2 10 2 62

[3] 2 12 2 47 Section 4

distinguisher into a key recovery attack, and we can add some rounds to the distinguisher.

Reducing the data complexity at the expense of time complexity is interesting because the data complexity of an attack is often the limiting factor: in practice, it is quite easy to perform 2 50 computations, but collecting (and storing) 2 50 known or chosen plaintext is virtually impossible. Moreover, the reduction in data complexity can actually lead to a reduction in time complexity. Our techniques increases the processing time per plaintext, but since the number of required plaintext is reduced, the total complexity can in fact be reduced. In particular, this is the case of our attacks against Chaskey.

For FEAL-8X, we manage to reduce the data complexity of the best known plaintext attack with practical time complexity from 2 14 to 2 12 . For Chaskey, we show how to build efficient differential-linear distinguishers, to reduce the data complexity with the partitioning technique, and to reduce the time complexity using a convolution method. For 7 rounds of Chaskey, the resulting differentiallinear distinguisher requires 2 78 data and 2 78 time, but this can be reduced to 2 48 data and 2 67 time, using partitioning. In addition, this result is quite interesting because standard bodies (ISO/IEC JTC1 SC27 and ISO/IEC JTC1 SC27) are currently conducting a preliminary study on the standardization of Chaskey [START_REF] Mouha | Chaskey[END_REF], but little external cryptanalysis has been published so far. The full version of Chaskey has 8 rounds, and is claimed to be secure against attacks with 2 48 data and 2 80 time. Our attacks are summarized in Table 1 and2. The paper is organized as follows: we first explain the partitioning technique for linear cryptanalysis in Section 2 and for differential cryptanalysis in Section 3. Then we demonstrate the application of our techniques, to FEAL in Section 4 and to Chaskey in Section 5.

Linear Analysis of Addition

We discuss linear cryptanalysis applied to addition operations, and our improvement using partitioning. We describe the linear approximations using linear masks; for instance an approximation for E is written as Pr E(x)[χ ] = x[χ] = 1/2 ± ε/2 where χ and χ are the input and output linear masks (x[χ] denotes

x[χ 1 ] ⊕ x[χ 2 ] ⊕ • • • x[χ ],
and x[χ i ] is bit χ i of x), and ε > 0 is the imbalance. We also denote the imbalance of a random variable x as ε(x) = |2 • Pr[x = 0] -1|, and I(x) = |ε(x)|. We will sometimes identify a mask with the integer with the same binary representation, and use an hexadecimal notation.

We first study linear properties of the addition operation, and use an ARX cipher E as example. We denote the word size as w. We assume that the cipher starts with an xor key addition, and a modular addition of two state variables. 3We denote the remaining operations as E , and we assume that we know a linear approximation (α, β, γ) E -→ (α , β , γ ) with imbalance ε for E . We further assume that the masks are sparse, and don't have adjacent active bits. Following previous works, the easier way to extend the linear approximation is to use the following masks for the addition:

(α ⊕ α 1, α) -→ α. (1)
As shown in Figure 1, this gives the following linear approximation for E:

(α ⊕ α 1, β ⊕ α, γ) E -→ (α , β , γ ). (2)
In order to explain our technique, we initially assume that α has a single active bit, i.e. α = 2 i . We explain how to deal with several active bits in Section 2.3. If i = 0, the approximation of the linear addition has imbalance 1, but for other values of i, it is only 1/2 [START_REF] Wallén | Linear Approximations of Addition Modulo 2 n[END_REF]. In the following we study the case i > 0, where the linear approximation (2) for E has imbalance ε/2.

Improved analysis with partitioning

We now explain the improved analysis of Biham and Carmeli [START_REF] Biham | An Improvement of Linear Cryptanalysis with Addition Operations with Applications to FEAL-8X[END_REF]. A simple way to understand their idea is to look at the carry bits in the addition. More precisely, we study an addition operation s = a b, and we are interested in the value s[α]. We assume that α = 2 i , i > 0, and that we have some amount of input/output pairs. We denote individual bits of a as a 0 , a 1 , . . . a n-1 , where a 0 is the LSB (respectively, b i for b and s i for s). In addition, we consider the carry bits c i , defined as c 0 = 0,

c i+1 = MAJ(a i , b i , c i ) (where MAJ(a, b, c) = (a ∧ b) ∨ (b ∧ c) ∨ (c ∧ a)). Therefore, we have s i = a i ⊕ b i ⊕ c i . E x 3 [α ] y 3 [β ] z 3 [γ ] x 2 [α] y 2 [β] z 2 [γ] x 0 [α ⊕ α 1] y 0 [β ⊕ α] z 0 [γ] k x k y k z x 1 [α ⊕ α 1] y 1 [β ⊕ α] z 1 [γ]
Fig. 1. Linear attack against the first addition Note that the classical approximation s i = a i ⊕ a i-1 ⊕ b i holds with probability 3/4 because c i = a i-1 with probability 3/4. In order to improve this approximation, Biham and Carmeli partition the data according to the value of bits a i-1 and b i-1 . This gives four subsets: 00 If (a i-1 , b i-1 ) = (0, 0), then c i = 0 and s i = a i ⊕ b i . 01 If (a i-1 , b i-1 ) = (0, 1), then ε(c i ) = 0 and I(s i ⊕ a i ⊕ a i-1 ) = 0. 10 If (a i-1 , b i-1 ) = (1, 0), then ε(c i ) = 0 and I(s i ⊕ a i ⊕ a i-1 ) = 0. 11 If (a i-1 , b i-1 ) = (1, 1), then c i = 1 and

s i = a i ⊕ b i ⊕ 1.
If bits of a and b are known, filtering the data in subsets 00 and 11 gives a trail for the addition with imbalance 1 over one half of the data, rather than imbalance 1/2 over the full data-set. This can be further simplified to the following:

s i = a i ⊕ b i ⊕ a i-1 if a i-1 = b i-1 (3)
In order to apply this analysis to the setting of Figure 1, we guess the key bits k x i-1 and k y i-1 , so that we can compute the values of x 1 i-1 and y 1 i-1 from x 0 and y 0 . More precisely, an attack on E can be performed with a single (logical) key bit guess, using Eq. (3):

x 2 i = x 1 i ⊕ y 1 i ⊕ x 1 i-1 if x 1 i-1 = y 1 i-1 x 2 i = x 0 i ⊕ y 0 i ⊕ x 0 i-1 ⊕ k x i ⊕ k y i ⊕ k x i-1 if x 0 i-1 ⊕ y 0 i-1 = k x i-1 ⊕ k y i-1
If we guess the key bit k x i-1 ⊕ k y i-1 , we can filter the data satisfying

x 0 i-1 ⊕ y 0 i-1 = k x i-1 ⊕ k y i-1
, and we have I(

x 2 i ⊕ x 0 i ⊕ y 0 i ⊕ x 0 i-1 ) = 1.
Therefore the linear approximation (2) has imbalance ε. We need 1/ε 2 data after the filtering for the attack to succeed, i.e. 2/ε 2 in total. The time complexity is also 2/ε 2 because we run the analysis with 1/ε 2 data for each key guess. This is an improvement over a simple linear attack using (2) with imbalance ε/2, with 4/ε 2 data.

In general we can compute the reduction of the data complexity reached by this kind of technique over a regular linear analysis as

G lin = µ × ε2 /ε 2
where µ is the fraction of data used in the attack, ε is the initial imbalance, and ε is the improved imbalance for the selected subset. For Biham and Carmeli's attack, we have µ = 1/2 and ε = 2ε, hence G lin = 2.

Generalized partitioning

? xi 0 ? ? + ? yi 0 ? ? ? ai ? ? ? 0 ? xi1 ? ? + ? yi 1 ? ? ? ai ? ? ? 1 ? xi 0 0 ? + ? yi 1 0 ? ? ai ? ? ? 0 0 ? xi 0 1 ? + ? yi 1 1 ? ? ai ? ? ? 1 1 ? xi1 0 ? + ? yi 0 1 ? ? ai ? ? ? ? ?

Fig. 2. Some cases of partitioning for linear cryptanalysis of an addition

We now refine the technique of Biham and Carmeli using several control bits. In particular, we analyze cases 01 and 10 with extra control bits a i-2 and b i-2 (some of cases of shown in Figure 2):

01.00 If (a i-1 , b i-1 , a i-2 , b i-2 ) = (0, 1, 0, 0), then c i-1 = 0, c i = 0 and s i = a i ⊕ b i . 01.01 If (a i-1 , b i-1 , a i-2 , b i-2 ) = (0, 1, 0, 1), then ε(c i-1 ) = 0, ε(c i ) = 0, and I(s i ⊕ a i ⊕ a i-1 ) = 0. 01.10 If (a i-1 , b i-1 , a i-2 , b i-2 ) = (0, 1, 0, 1), then ε(c i-1 ) = 0, ε(c i ) = 0, and I(s i ⊕ a i ⊕ a i-1 ) = 0. 01.11 If (a i-1 , b i-1 , a i-2 , b i-2 ) = (0, 1, 1, 1), then c i-1 = 1, c i = 1 and s i = a i ⊕ b i ⊕ 1. 10.00 If (a i-1 , b i-1 , a i-2 , b i-2 ) = (1, 0, 0, 0), then c i-1 = 0, c i = 0 and s i = a i ⊕ b i . 10.01 If (a i-1 , b i-1 , a i-2 , b i-2 ) = (1, 0, 0, 1), then ε(c i-1 ) = 0, ε(c i ) = 0, and I(s i ⊕ a i ⊕ a i-1 ) = 0. 10.10 If (a i-1 , b i-1 , a i-2 , b i-2 ) = (1, 0, 0, 1), then ε(c i-1 ) = 0, ε(c i ) = 0, and I(s i ⊕ a i ⊕ a i-1 ) = 0. 10.11 If (a i-1 , b i-1 , a i-2 , b i-2 ) = (1, 0, 1, 1), then c i-1 = 1, c i = 1 and s i = a i ⊕ b i ⊕ 1.
This yields an improved partitioning because we now have a trail for the addition with imbalance 1 in 12 out of 16 subsets: 00.00, 00.01, 00.10, 00.11, 01.00, 01.11, 10.00, 10.11, 11.00, 11.01, 11.10, 11.11. We can also simplify this case analysis:

s i = a i ⊕ b i ⊕ a i-1 a i ⊕ b i ⊕ a i-2 if a i-1 = b i-1 if a i-1 = b i-1 and a i-2 = b i-2 (4)
This gives an improved analysis of E by guessing more key bits. More precisely we need

k x i-1 ⊕ k y i-1 , and k x i-2 ⊕ k y i-2
, as shown below:

x 2 i = x 1 i ⊕ y 1 i ⊕ x 1 i-1 x 1 i ⊕ y 1 i ⊕ x 1 i-2 if x 1 i-1 = y 1 i-1 if x 1 i-1 = y 1 i-1 and x 1 i-2 = y 1 i-2 x 2 i =    x 0 i ⊕ y 0 i ⊕ x 0 i-1 ⊕ k x i ⊕ k y i ⊕ k x i-1 x 0 i ⊕ y 0 i ⊕ x 0 i-2 ⊕ k x i ⊕ k y i ⊕ k x i-2 if x 0 i-1 ⊕ y 0 i-1 = k x i-1 ⊕ k y i-1 if x 0 i-1 ⊕ y 0 i-1 = k x i-1 ⊕ k y i-1 and x 0 i-2 ⊕ y 0 i-2 = k x i-2 ⊕ k y i-2 I(x 2 i ⊕ x 0 i ⊕ y 0 i ⊕ x 0 i-1 ) = 1 if x 0 i-1 ⊕ y 0 i-1 = k x i-1 ⊕ k y i-1 I(x 2 i ⊕ x 0 i ⊕ y 0 i ⊕ x 0 i-2 ) = 1 if x 0 i-1 ⊕ y 0 i-1 = k x i-1 ⊕ k y i-1 and x 0 i-2 ⊕ y 0 i-2 = k x i-2 ⊕ k y i-2
Since this analysis yields different input masks for different subsets of the data, we use an analysis following multiple linear cryptanalysis [START_REF] Biryukov | On Multiple Linear Approximations[END_REF]. We first divide the data into four subsets, depending on the value of

x 0 i-1 ⊕ y 0 i-1 and x 0 i-2 ⊕ y 0 i-2
, and we compute the measured (signed) imbalance εs of each subset. Then, for each guess of the key bits k x i-1 ⊕ k y i-1 , and k x i-2 ⊕ k y i-2 , we deduce the expected imbalance ε k s of each subset, and we compute the distance to the observed imbalance as

s (ε s -ε k s ) 2 .
According to the analysis of Biryukov, De Cannière and Quisquater, the correct key is ranked first (with minimal distance) with high probability when using O(1/c 2 ) samples, where c 2 = i ε 2 i is the capacity of the system of linear approximations. Since we use three approximations with imbalance ε, the capacity of the full system is 3ε 2 , and we need 1/3 • 1/ε 2 data in each subset after partitioning, i.e. 4/3 • 1/ε 2 in total.

Again, the gain of this analysis can be computed as G lin = µ × ε2 /ε 2 . With µ = 3/4 and ε = 2ε, we find G lin = 3.

The same technique can be used to refine the partitioning further, and give a gain of G lin = (2 t -1)/2 t × 4 when guessing t bits.

Combining partitions

Finally, we can combine several partitions to analyze an addition with several active bits. If we use k 1 partitions for the first bit, and k 2 for the second bit, this yields a combined partition with k 1 • k 2 cases. If the bits are not close to each other, the gains of each bit are multiplied. This can lead to significant improvements even though G lin is small for a single active bit.

For more complex scenarios, we select the filtering bits assuming that the active bits don't interact, and we evaluate experimentally the probability in each subset. We can further study the matrix of probabilities to detect (logical) bits with no or little effect on the total capacity in order to improve the complexity of the attack. This will be used for our applications in Sections 4 and 5.

3 Differential Analysis of Addition We now study differential properties of the addition. We perform our analysis in the same way as the analysis of Section 2, following Figure 3. We consider the first addition operation separately, and we assume that we know a differential (α, β, γ) → (α , β , γ ) with probability p for the remaining of the cipher. Following previous works, the simple way to extend the differential is to use the following differences for the addition:

δx 3 = α δy 3 = β δz 3 = γ δx 2 = α δy 2 = β δz 2 = γ δx 0 = α ⊕ β δy 0 = β δz 0 = γ k x k y k z δx 1 = α ⊕ β δy 1 = β δz 1 = γ
α ⊕ β, β -→ α.
Similarly to our analysis of linear cryptanalysis, we consider a single addition s = a b, and we first assume that a single bit is active through the addition. However, we have to consider several cases, depending on how many input/output bits are active. The cases are mostly symmetric, but there are important differences in the partitioning.

Analysis of (

α = 0, β = 2 i ) With i < w -1, the probability for the addition is Pr[(2 i , 2 i ) -→ 0] = 1/2.
Improved analysis with structures. We first discuss a technique using multiple differentials and structures. More precisely, we use the following differentials for the addition:4

D 1 : (2 i , 2 i ) -→ 0 Pr (2 i , 2 i ) -→ 0 = 1/2 D 2 : (2 i ⊕ 2 i+1 , 2 i ) -→ 0 Pr (2 i ⊕ 2 i+1 , 2 i ) -→ 0 = 1/4
We can improve the probability of D 2 using a partitioning according to (a i , a i+1 ):

00 If (a i , a i+1 ) = (0, 0), then a = a 2 i 2 i+1 and s = s . 01 If (a i , a i+1 ) = (0, 1), then a = a 2 i and Pr[s = s ] = 1/2. 10 If (a i , a i+1 ) = (1, 0), then a = a 2 i and Pr[s = s ] = 1/2. 11 If (a i , a i+1 ) = (1, 1), then a = a 2 i 2 i+1 and s = s .
This can be written as:

Pr (2 i , 2 i ) -→ 0 = 1/2 Pr (2 i ⊕ 2 i+1 , 2 i ) -→ 0 = 1/2 if a i = a i+1
The use of structures allows to build pairs of data for both differentials from the same data set. More precisely, we consider the following inputs:

p = (x 0 , y 0 , z 0 ) q = (x 0 ⊕ 2 i , y 0 ⊕ 2 i , z 0 ) r = (x 0 ⊕ 2 i+1 , y 0 , z 0 ) s = (x 0 ⊕ 2 i+1 ⊕ 2 i , y 0 ⊕ 2 i , z 0 )
We see that (p, q) and (r, s) follow the input difference of D 1 , while (p, s) and (r, q) follow the input difference of D 2 . Moreover, we have from the partitioning:

Pr[E(p) ⊕ E(q) = (α , β , γ )] = 1/2 • p Pr[E(r) ⊕ E(s) = (α , β , γ )] = 1/2 • p Pr[E(p) ⊕ E(s) = (α , β , γ )] = 1/2 • p if x 0 i ⊕ x 0 i+1 = k x i ⊕ k x i+1 Pr[E(r) ⊕ E(q) = (α , β , γ )] = 1/2 • p if x 0 i ⊕ x 0 i+1 = k x i ⊕ k x i+1
For each key guess, we select three candidate pair out of a structure of four plaintexts, and every pair follows a differential for E with probability p/2. Therefore we need 2/p pairs, with a data complexity of 8/3 • 1/p rather than 4 • 1/p. In general we can compute the gain of this technique as

G diff = µT /2 × p/p
where µ is the fraction of data used in the attack, T is the number of plaintexts in a structure (we consider T 2 /4 pairs rather than T /2 without structures) p is the initial probability, and p is the improved probability for the selected subset.

Here we have µ = 3/4, T = 4, and p = p, hence G diff = 3/2.

Generalized partitioning. We can refine the analysis of the addition by partitioning according to (b i ). This gives the following:

Pr (2 i , 2 i ) → 0 = 1 if a i = b i Pr (2 i ⊕ 2 i+1 , 2 i ) → 0 = 1 if a i = b i and a i = a i+1
This gives an attack with T = 4, µ = 3/8 and p = 2p, which yield the same gain G diff = 3/2. However, this analysis allows to recover an extra key bit, which can be useful for further steps of an attack.

Moreover, if the differential trail is used in a boomerang attack, or in a differential-linear attack, the gain should be evaluated as:

G diff-2 = µT /2 × (p/p) 2 .
In this context, the partitioning with a single control bit still has a gain of G diff-2 = 3/2, but the partitioning with two control bits has a gain of G diff-2 = 3.

Alternatively, we can use a larger structure to reduce the complexity: with a structure of size 2 t , we have an attack with a gain G diff = (2 t -1)/2 t × 2, by guessing t -1 (or t) key bits.

Analysis of (

α = 2 i , β = 0) With i < w -1, the probability for the addition is Pr[(2 i , 0) -→ 2 i ] = 1/2.
Improved analysis with structures. As in the previous section, we consider multiple differentials, and use partitioning to improve the probability:

D 1 : Pr (2 i , 0) -→ 2 i = 1/2 D 2 : Pr (2 i ⊕ 2 i+1 , 0) -→ 2 i = 1/2 if a i = a i+1
We also use structures in order to build pairs of data for both differentials from the same data set. More precisely, we consider the following inputs:

p = (x 0 , y 0 , z 0 ) q = (x 0 ⊕ 2 i , y 0 , z 0 ) r = (x 0 ⊕ 2 i+1 , y 0 , z 0 ) s = (x 0 ⊕ 2 i+1 ⊕ 2 i , y 0 , z 0 )
We see that (p, q) and (r, s) follow the input difference of D 1 , while (p, s) and (r, q) follow the input difference of D 2 . Moreover, we have from the partitioning:

Pr[E(p) ⊕ E(q) = (α , β , γ )] = 1/2 • p Pr[E(r) ⊕ E(s) = (α , β , γ )] = 1/2 • p Pr[E(p) ⊕ E(s) = (α , β , γ )] = 1/2 • p if x 0 i ⊕ x 0 i+1 = k x i ⊕ k x i+1 Pr[E(r) ⊕ E(q) = (α , β , γ )] = 1/2 • p if x 0 i ⊕ x 0 i+1 = k x i ⊕ k x i+1
In this case, we have G diff = 3/2, with µ = 3/4, T = 4, and p = p.

Generalized partitioning. Again, we can refine the analysis of the addition by partitioning according to (s i ). This gives the following:

Pr (2 i , 0) → 2 i = 1 if a i = s i Pr (2 i ⊕ 2 i+1 , 0) → 2 i = 1 if a i = s i and a i = a i+1
Since we can not readily filter according to bits of s, we use the results of Section 2:

a i ⊕ b i ⊕ a i-1 = s i if a i-1 = b i-1
This gives:

Pr (2 i , 0) → 2 i = 1 if b i = a i-1 and a i-1 = b i-1 Pr (2 i ⊕ 2 i+1 , 0) → 2 i = 1 if b i = a i-1 and a i-1 = b i-1 and a i = a i+1
Unfortunately, we can only use a small fraction of the pairs µ = 3/16. With T = 4 and p = 2p, this yields G diff = 3/4, which is worse than in the previous section.

Analysis of (

α = 2 i , β = 2 i ) With i < w -1, the probability for the addition is Pr[(0, 2 i ) -→ 2 i ] = 1/2.
The results in this section will be the same as in the previous section, but we have to use a different structure. Indeed when this analysis is applied to E, we can freely modify the difference in x 0 but not in y 0 , because it would affect the differential in E .

More precisely, we use the following differentials:

D 1 : Pr (0, 2 i ) -→ 2 i = 1/2 D 2 : Pr (2 i+1 , 2 i ) -→ 2 i = 1/2 if a i+1 = b i
and the following structure:

p = (x 0 , y 0 , z 0 ) q = (x 0 , y 0 ⊕ 2 i , z 0 ) r = (x 0 ⊕ 2 i+1 , y 0 , z 0 ) s = (x 0 ⊕ 2 i+1 , y 0 ⊕ 2 i , z 0 )
This yields:

Pr[E(p) ⊕ E(q) = (α , β , γ )] = 1/2 • p Pr[E(r) ⊕ E(s) = (α , β , γ )] = 1/2 • p Pr[E(p) ⊕ E(s) = (α , β , γ )] = 1/2 • p if x 1 i ⊕ x 0 i+1 = k y i ⊕ k x i+1 Pr[E(r) ⊕ E(q) = (α , β , γ )] = 1/2 • p if x 1 i ⊕ x 0 i+1 = k y i ⊕ k x i+1
4 Application to FEAL-8X

We now present application of our techniques to reduce the data complexity of differential and linear attacks.

FEAL is an early block cipher proposed by Shimizu and Miyaguchi in 1987 [START_REF] Shimizu | Fast Data Encipherment Algorithm FEAL[END_REF]. FEAL uses only addition, rotation and xor operations, which makes it much more efficient than DES in software. FEAL has inspired the development of many cryptanalytic techniques, in particular linear cryptanalysis.

At the rump session of CRYPTO 2012, Matsui announced a challenge for low data complexity attacks on FEAL-8X using only known plaintexts. At the time, the best practical attack required 2 24 known plaintexts [START_REF] Biham | On Matsui's Linear Cryptanalysis[END_REF] (Matsui and Yamagishi had non-practical attacks with as little as 2 14 known plaintext [START_REF] Matsui | A New Method for Known Plaintext Attack of FEAL Cipher[END_REF]), but Biham and Carmeli won the challenge with a new linear attack using 2 15 known plaintexts, and introduced the partitioning technique to reduce the data complexity to 2 14 [START_REF] Biham | An Improvement of Linear Cryptanalysis with Addition Operations with Applications to FEAL-8X[END_REF].

We now explain how to apply the generalized partitioning to attack FEAL-8X. Our attack follows the attack of Biham and Carmeli [START_REF] Biham | An Improvement of Linear Cryptanalysis with Addition Operations with Applications to FEAL-8X[END_REF], and uses the generalized partitioning technique to reduce the data complexity further. The attack by Biham and Carmeli requires 2 14 data and about 2 45 time, while our attack needs only 2 12 data, and 2 47 time.

The attacks are based on a 6-round linear approximation with imbalance 2 -5 , using partial encryption for the first round (with a 15 bit key guess), and partial decryption for the last round (with a 22 bit key guess). This allows to compute enough bits of the state after the first round and before the last round, respectively, to compute the linear approximation. For more details of the attack, we refer the reader to the description of Biham and Carmeli [START_REF] Biham | An Improvement of Linear Cryptanalysis with Addition Operations with Applications to FEAL-8X[END_REF].

In order to improve the attack, we focus on the round function of the second-to-last round. The corresponding linear approximation is x[10115554] → y[04031004] with imbalance of approximately 2 -3 .

We partition the data according to the following 4 bits 5 (note that all those bits can be computed in the input of round 6 with the 22-bit key guess of DK7):

b 0 = f 0,3 ⊕ f 1,3 ⊕ f 2,2 ⊕ f 3,2 b 1 = f 0,3 ⊕ f 1,3 ⊕ f 2,3 ⊕ f 3,3 b 2 = f 0,3 ⊕ f 1,3 ⊕ f 2,5 ⊕ f 3,5 b 3 = f 0,2 ⊕ f 1,2 ⊕ f 0,3 ⊕ f 1,3
The probability of the linear approximation in each subset is as follows (indexed by the value of b This gives a total capacity c 2 = i (2 • p i -1) 2 = 2.49, using subsets of 1/16 of the data. For reference, a linear attack without partitioning has a capacity (2 -3 ) 2 , therefore the gain can be computed as:

G lin = 1/16 × 2.49/2 -6 ≈ 10
This can be compared to Biham and Carmeli's partitioning, where they use a single linear approximation with capacity 0.1 for 1/2 of the data, this give a gain of only:

G lin = 1/2 × 0.1/2 -6 ≈ 3.2
On the other hand the time complexity is increased because we have to guess 4 more key bits, and repeat the analysis 16 times. Since the data is reduced by a factor 4, the total time complexity increases by a factor 4 compared to the attack on Biham and Carmeli. This result in an attack with 2 12 data and 2 47 time.

Application to Chaskey

Chaskey is a recent MAC proposal designed jointly by researchers from COSIC and Hitachi [START_REF] Mouha | Chaskey: An Efficient MAC Algorithm for 32-bit Microcontrollers[END_REF]. The mode of operation of Chaskey is based on CBC-MAC with an Even-Mansour cipher; but it can also be described as a permutation-based design as seen in Figure 4. Chaskey is designed to be extremely fast on 32-bit micro-controllers, and the internal permutation follows an ARX construction with 4 32-bit words based on SipHash; it is depicted in Figure 5. Since the security of Chaskey is based on an Even-Mansour cipher, the security bound has a birthday term O(T D • 2 -128 ). More precisely, the designers claim that it should be secure up to 2 48 queries, and 2 80 computations. So far, the only external cryptanalysis results on Chaskey are generic attacks in the multi-user setting [START_REF] Mavromati | Key-recovery attacks against the mac algorithm chaskey[END_REF]. The only analysis of the permutation is in the submission document; the best result is a 4 round bias, that can probably be extended into a 5 round attack following the method of attacks against the Salsa family [START_REF] Aumasson | New Features of Latin Dances: Analysis of Salsa, ChaCha, and Rumba[END_REF]. It is important to try more advanced techniques in order to understand the security of Chaskey, in particular because it is being considered for standardisation. 2 -289.9

Differential-linear cryptanalysis

The best differential characteristics found by the designers of Chaskey quickly become unusable when the number of rounds increase (See Table 3). The designers also report that those characteristics have an "hourglass structure": there is a position in the middle where a single bit is active, and this small difference is expanded by the avalanche effect when propagating in both direction. This is typical of ARX designs: short characteristics have a high probability, but after a few rounds the difference cannot be controlled and the probability decrease very fast. The same observation typically holds also for linear trails.

Because of these properties, attacks that can divide the cipher E in two parts E = E ⊥ • E and build characteristics or trail for both half independentlysuch as the boomerang attack or differential-linear cryptanalysis -are particularly interesting. In particular, many attacks on ARX designs are based on the boomerang attack [START_REF] Yu | The Boomerang Attacks on the Round-Reduced Skein-512[END_REF][START_REF] Mendel | Boomerang Distinguisher for the SIMD-512 Compression Function[END_REF][START_REF] Biryukov | Boomerang Attacks on BLAKE-32[END_REF][START_REF] Leurent | Boomerang Attacks on Hash Function Using Auxiliary Differentials[END_REF][START_REF] Lamberger | Higher-Order Differential Attack on Reduced SHA-256[END_REF][START_REF] Sasaki | Boomerang Distinguishers on MD4-Family: First Practical Results on Full 5-Pass HAVAL[END_REF] or differential-linear cryptanalysis [START_REF] Huang | Differential-linear cryptanalysis of icepole[END_REF]. Since Chaskey never uses the inverse permutation, we cannot apply a boomerang attack, and we focus on differential-linear cryptanalysis. Differential-linear cryptanalysis uses a differential δ i E -→ δ o with probability p for E , and a linear approximation χ i E ⊥ -→ χ o with imbalance ε for E ⊥ (see Figure 6). The attacker uses pairs of plaintexts (P i , P i ) with P i = P i ⊕ δ i , and computes the observed imbalance

|2 • # {i : C[χ o ] = C [χ o ]} /D -1|.
Following the heuristic analysis of [START_REF] Biham | Enhancing Differential-Linear Cryptanalysis[END_REF], the expected imbalance is about pε 2 , which gives an attack complexity of O(2/p 2 ε 4 ):

-A pair of plaintext satisfies E (P ) ⊕ E (P ) = δ o with probability p. In this case, we have

E (P )[χ i ] ⊕ E (P )[χ i ] = δ o [χ i ].
Without loss of generality, we assume that δ o [χ i ] = 0. -Otherwise, we expect that E (P )[χ i ] ⊕ E (P )[χ i ] is not biased. This gives the following:

Pr E (P )[χ i ] ⊕ E (P )[χ i ] = 0 = (1 -p) • 1/2 + p = 1/2 + p/2 (5)
I(E (P )[χ i ] ⊕ E (P )[χ i ]) = p (6)
-We also have

I(E (P )[χ i ] ⊕ C[χ o ]) = I(E (P )[χ i ] ⊕ C [χ o ]) = ε from the linear approximations. Combining with (8), we get I(C[χ o ] ⊕ C [χ o ]) = pε 2 .
A more rigorous analysis has been recently provided by Blondeau, Leander and Nyberg [START_REF] Blondeau | Differential-linear cryptanalysis revisited[END_REF], but since we use experimental values for the complexity, the heuristic explanation will be sufficient.

Using partitioning

A differential-linear distinguisher can easily be improved using the results of Section 2 and 3. We can improve the differential and linear part separately, and combine the improvements on the differential-linear attack. More precisely, we have to consider structures of plaintexts, and to guess some key bits in the differential and linear parts. We partition all the potential pairs in the structures according to the input difference, and to the filtering bits in the differential and linear part; then we evaluate the observed imbalance ε[s] in every subset s.

Finally, for each key guess k, we compute the expected imbalance ε k [s] for each subset s, and then we evaluate the distance between the observed and expected imbalances as

L(k) = s (ε[s] -ε k [s]) 2
(following the analysis of multiple linear cryptanalysis [START_REF] Biryukov | On Multiple Linear Approximations[END_REF]). While we follow the analysis of multiple linear cryptanalysis to evaluate the complexity of our attack, we use each linear approximation on a different subset of the data, partitioned according to the filtering bits. In particular, we don't have to worry about the independence of the linear approximations.

If we use structures of size T , and select a fraction µ diff of the input pairs with an improved differential probability p, and a fraction µ lin of the output pairs with an improved linear imbalance ε, the data complexity of the attack is O(µ lin µ 2 diff T /2 × 2/p 2 ε4 ). This corresponds to a gain of G diff-2 G 2 lin .

More precisely, using differential filtering bits p diff and linear filtering bits c lin , the subsets are defined by the input difference ∆, the plaintext bits P [p diff ] and the cipher text bits C[c lin ] and C [c lin ], with C = E(P ) and C = E(P ⊕ ∆). In practice, for every P, P in a structure, we update the value of ε

[P ⊕ P , P [p lin ], C[c diff ], C [c diff ]].
We also take advantage of the Even-Mansour construction of Chaskey, without keys inside the permutation. Indeed, the filtering bits used to define the subsets s correspond to the key bits used in the attack. Therefore, we only need to compute the expected imbalance for the zero key, and we can deduce the expected imbalance for an arbitrary key as

ε k diff ,k lin [∆, p, c, c ] = ε 0 [∆, p ⊕ k lin , c ⊕ k diff , c ⊕ k diff ].
Time complexity. This description lead to an attack with low time complexity using an FFT algorithm, as described previously for linear cryptanalysis [START_REF] Collard | Improving the Time Complexity of Matsui's Linear Cryptanalysis[END_REF] and multiple linear cryptanalysis [START_REF] Hermelin | Dependent Linear Approximations: The Algorithm of Biryukov and Others Revisited[END_REF]. Indeed, the distance between the observed and expected imbalance can be written as:

L(k) = s (ε[s] -ε k [s]) 2 = s (ε[s] -ε 0 [s ⊕ φ(k)]) 2 , where φ(k diff , k lin ) = (0, k lin , k diff , k diff ) = s ε[s] 2 + s ε 0 [s ⊕ φ(k)] 2 -2 s ε[s]ε 0 [s ⊕ φ(k)],
where only the last term depend on the key. Moreover, this term can be seem as the φ(k)-th component of the convolution ε 0 * ε. Using the convolution theorem, we can compute the convolution efficiently with an FFT algorithm.

This gives the following fast analysis:

1. Compute the expected imbalance ε 0 [s] of the differential-linear distinguisher for the zero key, for every subset s. 2. Collect D plaintext-ciphertext pairs, and compute the observed imbalance ε[s] of each subset. 3. Compute the convolution ε * ε, and find k that maximizes coefficient φ(k).

Differential-linear Cryptanalysis of Chaskey

In order to find good differential-linear distinguishers for Chaskey, we use a heuristic approach. We know that most good differential characteristics and good linear trails have an "hourglass structure", with a single active bit in the middle. If a good differential-linear characteristics is given with this "hourglass structure", we can divide E in three parts E = E ⊥ • E ⊥ • E , so that the single active bit in the differential characteristic falls between E and E ⊥ , and the single active bit in the linear trail falls between E ⊥ and E ⊥ . We use this decomposition to look for good differential-linear characteristics: we first divide E in three parts, and we look for a differential characteristic -We consider a pair of plaintext (P, P ) with P = P ⊕ δ i , and we denote

δ i E -→ δ o in E (with probability p), a differential-linear characteristic δ o E ⊥ -→ χ i in E ⊥ (
X = E (P ), Y = E ⊥ (X), C = E ⊥ (Y ). -We have X ⊕ X = δ o with probability p. In this case, I(Y [χ i ] ⊕ Y [χ i ]) = b -Otherwise, we expect that Y [χ i ]⊕Y [χ i ] is not biased. This gives the following: Pr Y [χ i ] ⊕ Y [χ i ] = 0 = (1 -p) • 1/2 + p • (1/2 + b/2) = 1/2 + bp/2 (7) I(Y [χ i ] ⊕ Y [χ i ]) = bp (8)
-We also have

I(Y [χ i ] ⊕ C[χ o ]) = I(Y [χ i ] ⊕ C [χ o ]) = ε from the linear approximations.
Combining with (8), we get

I(C[χ o ] ⊕ C [χ o ]) = bpε 2 .
In the E ⊥ section, we can see the characteristic as a small differential-linear characteristic with a single active input bit and a single active output bit, or as a truncated differential where the input difference has a single active bit and the output value is truncated to a single bit. In other words, we use pairs of values with a single bit difference, and we look for a biased output bit difference.

We ran an exhaustive search over all possible decompositions E = E ⊥ •E ⊥ •E (varying the number of rounds), and all possible positions for the active bits i at the input of E ⊥ and the biased bit6 j at the output of E ⊥ . For each candidate, we evaluate experimentally the imbalance

I(E ⊥ (x)[2 j ] ⊕ E ⊥ (x ⊕ 2 i )[2 j ]
), and we study the best differential and linear trails to build the full differential-linear distinguisher. This method is similar to the analysis of the Salsa family by Aumasson et al. [START_REF] Aumasson | New Features of Latin Dances: Analysis of Salsa, ChaCha, and Rumba[END_REF]: they decompose the cipher in two parts E = E ⊥ • E ⊥ , in order to combine a biased bit in E ⊥ with an approximation of E ⊥ .

This approach allows to identify good differential-linear distinguisher more easily than by building full differential and linear trails. In particular, we avoid most of the heuristic problems in the analysis of differential-linear distinguishers (such as the presence of multiple good trails in the middle) by evaluating experimentally I(E ⊥ (x) [2 j ] ⊕ E ⊥ (x ⊕ 2 i )[2 j ]) without looking for explicit trails in the middle. In particular, the transition between E and E ⊥ is a transition between two differential characteristics, while the transition between E ⊥ and E ⊥ is a transition between two linear characteristics.

Attack against 6-round Chaskey

The best distinguisher we identified for an attack against 6-round Chaskey uses 1 round in E , 4 rounds in E ⊥ , and 1 round in E ⊥ . The optimal differences and masks are: -Differential for E with probability p ≈ 2 -5 : [START_REF] Biham | Differential Cryptanalysis of DES-like Cryptosystems[END_REF][START_REF] Langford | Differential-Linear Cryptanalysis[END_REF][START_REF] Mavromati | Key-recovery attacks against the mac algorithm chaskey[END_REF], v 3 [START_REF] Langford | Differential-Linear Cryptanalysis[END_REF][START_REF] Mavromati | Key-recovery attacks against the mac algorithm chaskey[END_REF] E -→ v 2 [START_REF] Lamberger | Higher-Order Differential Attack on Reduced SHA-256[END_REF] -Biased bit for E ⊥ with imbalance ε ⊥ = 2 -6.05 : [START_REF] Collard | Improving the Time Complexity of Matsui's Linear Cryptanalysis[END_REF] -Linear approximations for E ⊥ with imbalance ε ⊥ = 2 -2.6 : [START_REF] Langford | Differential-Linear Cryptanalysis[END_REF][START_REF] Mendel | Boomerang Distinguisher for the SIMD-512 Compression Function[END_REF], v 2 [0, 8, 15], v 3 [START_REF] Biham | Enhancing Differential-Linear Cryptanalysis[END_REF] The differential and linear trails are shown in Figure 7. The expected imbalance is p 16.25 . This gives a differential-linear distinguisher with expected complexity in the order of D = 2/p 2 ε 2 ⊥ ε 4 ⊥ ≈ 2 33.5 . We can estimate the data complexity more accurately using [12, Eq. ( 11)]: we need about 2 34.1 pairs of samples in order to reach a false positive rate of 2 -4 . Experimentally, with 2 34 pairs of samples (i.e. 2 35 data), the measured imbalance is larger than 2 -16.25 with probability 0.5; with random data, it is larger than 2 -16.25 with probability 0.1. This matches the predictions of [START_REF] Blondeau | Accurate estimates of the data complexity and success probability for various cryptanalyses[END_REF], and confirms the validity of our differential-linear analysis.

v 0 [26], v 1 [26], v 2
v 2 [22] E ⊥ -→ v 2
v 2 [16] E ⊥ -→ v 0 [5], v 1
• ε ⊥ • ε 2 ⊥ = 2 -
This simple differential-linear attack is more efficient than generic attacks against the Even-Mansour construction of Chaskey. It follows the usage limit of Chaskey, and reaches more rounds than the analysis of the designers. Moreover, but we can improve it using the results of Sections 2 and 3.

Analysis of linear approximations with partitioning. To make the description easier, we first invert the linear operations at the end, so that the linear trail becomes: [START_REF] Collard | Improving the Time Complexity of Matsui's Linear Cryptanalysis[END_REF][START_REF] Leurent | Analysis of Differential Attacks in ARX Constructions[END_REF], v 2 [START_REF] Collard | Improving the Time Complexity of Matsui's Linear Cryptanalysis[END_REF][START_REF] Langford | Differential-Linear Cryptanalysis[END_REF][START_REF] Leurent | Analysis of Differential Attacks in ARX Constructions[END_REF], v 3 [START_REF] Leurent | Analysis of Differential Attacks in ARX Constructions[END_REF] We select control bits to improve the probability of the addition between v 1 and v 2 on active bits 16 and 24. Following the analysis of Section 2.2, we need v 1 [START_REF] Bogdanov | PRESENT: An Ultra-Lightweight Block Cipher[END_REF] ⊕ v 2 [START_REF] Bogdanov | PRESENT: An Ultra-Lightweight Block Cipher[END_REF] and v 1 [START_REF] Cho | Crossword Puzzle Attack on NLS[END_REF] ⊕ v 2 [START_REF] Cho | Crossword Puzzle Attack on NLS[END_REF] as control bits for active bit 16. To identify more complex control bits, we consider v 1 [START_REF] Bogdanov | PRESENT: An Ultra-Lightweight Block Cipher[END_REF][START_REF] Cho | Crossword Puzzle Attack on NLS[END_REF][START_REF] Lamberger | Higher-Order Differential Attack on Reduced SHA-256[END_REF][START_REF] Langford | Differential-Linear Cryptanalysis[END_REF], v 2 [START_REF] Bogdanov | PRESENT: An Ultra-Lightweight Block Cipher[END_REF][START_REF] Cho | Crossword Puzzle Attack on NLS[END_REF][START_REF] Lamberger | Higher-Order Differential Attack on Reduced SHA-256[END_REF][START_REF] Langford | Differential-Linear Cryptanalysis[END_REF] as potential control bits, as well as v 3 [START_REF] Langford | Differential-Linear Cryptanalysis[END_REF] because it can affect the addition on the previous half-round. Then, we evaluate the bias experimentally (using the round function as a black box) in order to remove redundant bits. This leads to the following 8 control bits:

v 2 [16] E ⊥ -→ v 1
v 1 [14] ⊕ v 2 [14] v 1 [14] ⊕ v 1 [15] v 1 [22] v 1 [23] v 1 [15] ⊕ v 2 [15] v 1 [15] ⊕ v 3 [23] v 2 [22] v 2 [23]
This defines 2 8 partitions of the ciphertexts, after guessing 8 key bits. We evaluated the bias in each partition, and we found that the combined capacity is c 2 = 2 6.84 . This means that we gain the following factor

G lin = 2 -8 × 2 6.84 /2 -2•2.6 ≈ 2 4 (9)
Analysis of differential with partitioning. There are four active bits in the first additions:

-Bit 23 in v 2 v 3 : (2 23 , 2 23 ) -→ 0 -Bit 30 in v 2 v 3 : (2 30 , 2 30 ) -→ 2 31 -Bit 6 in v 2 v 3 : (2 6 , 0) -→ 2 6 -Bit 26 in v 0 v 1 : (2 26 , 2 26 ) -→ 0
Following the analysis of Section 3, we can use additional input differences for each of them. However, we reach a better trade-off by selected only three of them. More precisely, we consider 2 3 input differences, defined by δ i and the following extra active bits:

v 2 [24] v 2 [31] v 0 [27]
As explained in Section 2, we build structures of 2 4 plaintexts, where each structure provides 2 3 pairs for every input difference, i.e. 2 6 pairs in total.

Following the analysis of Section 3, we use the following control bits to improve the probability of the differential:

v 2 [23] ⊕ v 2 [24] v 2 [30] ⊕ v 3 [30] v 0 [26] ⊕ v 0 [27] v 2 [24] ⊕ v 3 [23] v 0 [27] ⊕ v 1 [26]
This divides each set of pairs into 2 5 subsets, after guessing 5 key bits. In total we have 2 8 subsets to analyze, according to the control bits and the multiple differentials. We found that, for 18 of those subsets, there is a probability 2 -2 to reach δ o (the probability is 0 for the remaining subsets). This leads to a gain:

G diff = 18/2 8 × 2 4 /2 × 2 -2 /2 -5 = 9/2 G diff-2 = 18/2 8 × 2 4 /2 × (2 -2 /2 -5 ) 2 = 36
This corresponds to the analysis of Section 3: we have a gain of 3/2 for bits v 2 [START_REF] Langford | Differential-Linear Cryptanalysis[END_REF] and v 0 [START_REF] Lipmaa | Efficient Algorithms for Computing Differential Properties of Addition[END_REF], and a gain of 2 for v 2 [START_REF] Mendel | Boomerang Distinguisher for the SIMD-512 Compression Function[END_REF] in the simple linear case. In the differential-linear case, we have respectively gains of 3 and 2.

Finally, the improved attack requires a data complexity in the order of:

D/G 2 lin G diff-2 ≈ 2 20.3 .
We can estimate the data complexity more accurately using the analysis of Biryukov, De Cannière and Quisquater [START_REF] Biryukov | On Multiple Linear Approximations[END_REF]. First, we give an alternate description of the attack similar the multiple linear attack framework. Starting from D chosen plaintexts, we build 2 2 D pairs using structures, and we keep N = 18•2 -8 •2 -14 •2 2 D samples per approximation after partitioning the differential and linear parts. The imbalance of the distinguisher is 2 -2 • 2 -6.05 • 2 6.84 = 2 -1. 21 . Following [9, Corrolary 1], the gain of the attack with D = 2 24 is estimated as 6.6 bits, i.e. the average key rank should be about 42 (for the 13-bit subkey).

Using the FFT method of Section 5.2, we perform the attack with 2 24 counters ε[s]. Each structure of 2 4 plaintexts provides 2 6 pairs, so that we need 2 2 D operations to update the counters. Finally, the FFT computation require 24 × 2 24 ≈ 2 28.6 operations.

We have implemented this analysis, and it runs in about 10s on a single core of a desktop PC. 7 Experimentally, we have a gain of about 6 bits (average key rank of 64 with 128 experiments); this validates our theoretical analysis. We also notice some key bits don't affect the distinguisher and cannot be recovered. On the other hand, the gain of the attack can be improved using more data, and further trade-offs are possible using larger or smaller partitions.

Attack against 7-round Chaskey

The best distinguisher we identified for an attack against 7-round Chaskey uses 1.5 round in E , 4 rounds in E ⊥ , and 1.5 round in E ⊥ . The optimal differences and masks are:

-Differential for E with probability p = 2

-→ v 0 [31] -Biased bit for E ⊥ with imbalance ε ⊥ = 2 -6.1 : v 0 [31] E ⊥ -→ v 2 [20]
7 Haswell microarchitecture running at 3.4 GHz -Linear approximations for E ⊥ with imbalance ε ⊥ = 2 -7.6 : [START_REF] Cho | Crossword Puzzle Attack on NLS[END_REF][START_REF] Collard | Improving the Time Complexity of Matsui's Linear Cryptanalysis[END_REF][START_REF] Leurent | Construction of Differential Characteristics in ARX Designs Application to Skein[END_REF][START_REF] Matsui | A New Method for Known Plaintext Attack of FEAL Cipher[END_REF], v 1 [START_REF] Biham | Differential Cryptanalysis of DES-like Cryptosystems[END_REF][START_REF] Biryukov | Boomerang Attacks on BLAKE-32[END_REF][START_REF] Hermelin | Dependent Linear Approximations: The Algorithm of Biryukov and Others Revisited[END_REF][START_REF] Leurent | Boomerang Attacks on Hash Function Using Auxiliary Differentials[END_REF], v 2 [START_REF] Biham | On Matsui's Linear Cryptanalysis[END_REF][START_REF] Biryukov | On Multiple Linear Approximations[END_REF][START_REF] Hermelin | Dependent Linear Approximations: The Algorithm of Biryukov and Others Revisited[END_REF][START_REF] Huang | Differential-linear cryptanalysis of icepole[END_REF][START_REF] Langford | Differential-Linear Cryptanalysis[END_REF][START_REF] Matsui | Linear Cryptanalysis Method for DES Cipher[END_REF], v 3 [0, [START_REF] Leurent | Construction of Differential Characteristics in ARX Designs Application to Skein[END_REF][START_REF] Matsui | A New Method for Known Plaintext Attack of FEAL Cipher[END_REF] This gives a differential-linear distinguisher with expected complexity in the order of D = 2/p 2 ε 2 ⊥ ε 4 ⊥ ≈ 2 77.6 . This attack is more expensive than generic attacks against on the Even-Mansour cipher, but we now improve it using the results of Sections 2 and 3.

v 2 [20] E ⊥ -→ v 0 [0,
Analysis of linear approximations with partitioning. We use an automatic search to identify good control bits, starting from the bits suggested by the result of Section 2. We identified following control bits: [START_REF] Gilbert | A Statistical Attack of the FEAL-8 Cryptosystem[END_REF] Note that the control bits identified in Section 2 appear as linear combinations of those control bits. This defines 2 19 partitions of the ciphertexts, after guessing 19 key bits. We evaluated the bias in each partition, and we found that the combined capacity is c 2 = 2 14.38 . This means that we gain the following factor: G lin = 2 -19 × 2 14.38 /2 -2•7.6 ≈ 2 10.5 [START_REF] Biryukov | On Multiple Linear Approximations[END_REF] This example clearly shows the power of the partitioning technique: using a few key guesses, we avoid the cost of the last layer of additions.

v 1 [3] ⊕ v 1 [11] ⊕ v 3 [10] v 1 [3] ⊕ v 1 [11] ⊕ v 3 [11] v 0 [15] ⊕ v 3 [14] v 0 [15] ⊕ v 3 [15] v 1 [11] ⊕ v 1 [18] ⊕ v 3 [17] v 1 [11] ⊕ v 1 [18] ⊕ v 3 [18] v 1 [3] ⊕ v 2 [2] v 1 [3] ⊕ v 2 [3] v 1 [11] ⊕ v 2 [9] v 1 [11] ⊕ v 2 [10] v 1 [11] ⊕ v 2 [11] v 1 [18] ⊕ v 2 [17] v 1 [18] ⊕ v 2 [18] v 1 [2] ⊕ v 1 [3] v 1 [9] ⊕ v 1 [11] v 1 [10] ⊕ v 1 [11] v 1 [17] ⊕ v 1 [18] v 0 [14] ⊕ v 0 [15] v 0 [15] ⊕ v 1 [3] ⊕ v 1 [11] ⊕ v 1
Analysis of differential with partitioning. We consider 2 9 input differences, defined by δ i and the following extra active bits:

v 0 [9]
v 0 [START_REF] Lamberger | Higher-Order Differential Attack on Reduced SHA-256[END_REF] v 0 [START_REF] Mendel | Boomerang Distinguisher for the SIMD-512 Compression Function[END_REF] v 0 [START_REF] Hermelin | Dependent Linear Approximations: The Algorithm of Biryukov and Others Revisited[END_REF] v 0 [START_REF] Bogdanov | PRESENT: An Ultra-Lightweight Block Cipher[END_REF] v 0 [START_REF] Lipmaa | Efficient Algorithms for Computing Differential Properties of Addition[END_REF] v 2 [START_REF] Lamberger | Higher-Order Differential Attack on Reduced SHA-256[END_REF] v 2 [START_REF] Lipmaa | Efficient Algorithms for Computing Differential Properties of Addition[END_REF] v 2 [START_REF] Biham | Cryptanalysis of SHA-0 and Reduced SHA-1[END_REF] As explained in Section 2, we build structures of 2 10 plaintexts, where each structure provides 2 9 pairs for every input difference, i.e. 2 18 pairs in total. Again, we use an automatic search to identify good control bits, starting from the bits suggested in Section 3. We use the following control bits to improve the probability of the differential: This divides each set of pairs into 2 14 subsets, after guessing 14 key bits. In total we have 2 23 subsets to analyze, according to the control bits and the multiple differentials. We found that, for 17496 of those subsets, there is a probability 2 -11 to reach δ o (the probability is 0 for the remaining subsets). This leads to a gain: Finally, the improved attack requires a data complexity of: 44.5 .

G diff-2 =
D/G 2 lin G diff-2 ≈ 2
Again, we can estimate the data complexity more accurately using [START_REF] Biryukov | On Multiple Linear Approximations[END_REF]. In this attack, starting from N 0 chosen plaintexts, we build 2 8 N 0 pairs using structures, and we keep N = 17496 • 2 -23 • 2 -38 • 2 8 N 0 samples per approximation after partitioning the differential and linear parts. The imbalance of the distinguisher is 2 -11 • 2 -6.1 • 2 14.38 = 2 -2.72 . Following [9, Corrolary 1], the gain of the attack with N 0 = 2 48 is estimated as 6.3 bits, i.e. the average rank of the 33-bit subkey should be about 2 25.7 . Following the experimental results of Section 5.4, we expect this to estimation to be close to the real gain (the gain can also be increased if more than 2 48 data is available).

Using the FFT method of Section 5.2, we perform the attack with 2 61 counters ε[s]. Each structure of 2 10 plaintexts provides 2 18 pairs, so that we need 2 8 D operations to update the counters. Finally, the FFT computation require 61 × 2 61 ≈ 2 67 operations.

This attack recovers only a few bits of a 33-bit subkey, but an attacker can run the attack again with a different differential-linear distinguisher to recover other key bits. For instance, a rotated version of the distinguisher will have a complexity close to the optimal one, and the already known key bits can help reduce the complexity.

Conclusion

In this paper, we have described a partitioning technique inspired by Biham and Carmeli's work. While Biham and Carmeli consider only two partitions and a linear approximation for a single subset, we use a large number of partitions, and linear approximations for every subset to take advantage of all the data. We also introduce a technique combining multiple differentials, structures, and partitioning for differential cryptanalysis. This allows a significant reduction of the data complexity of attacks against ARX ciphers, as demonstrated by our applications.

Our main application is a differential-linear attack against Chaskey, that reaches 7 rounds out of 8. In this application, the partitioning technique allows to go through the first and last additions almost for free. This is very similar to the use of partial key guess and partial decryption for SPN ciphers.

Fig. 3 .

 3 Fig. 3. Differential attack against the first addition

3 , b 2 , b 1 ,

 321

Fig. 4 .

 4 Fig. 4. Chaskey mode of operation (full block message)

Fig. 5 .

 5 Fig. 5. One round of the Chaskey permutation. The full permutation has 8 rounds.

Fig. 6 .

 6 Fig. 6. Differential-linear cryptanalysis

  with imbalance b), and a linear characteristic χ i E ⊥ -→ χ o in E ⊥ (with imbalance ε), where δ o and χ i have a single active bit. This gives a differential-linear distinguisher with imbalance close to bpε 2 :

Fig. 7 .

 7 Fig. 7. 6-round attack: differential characteristic, and linear trail.

  17496/2 23 × 2 10 /2 × (2 -11 /2 -17 ) 2 = 4374 ≈ 2 12.1

Table 1 .

 1 Key-recovery attacks on Chaskey

	Rounds	Data	Time
	6	2 35	2 35	Differential-Linear
	6	2 25	2 28.6	Differential-Linear with partitioning
	7	2 78	2 78	Differential-Linear
	7	2 48	2 67	Differential-Linear with partitioning

Table 2 .

 2 Known-plaintext attacks on FEAL-8X

	Data	Time	Ref.
	2 14	2 64

Table 3 .

 3 Probabilities of the best differential characteristics of Chaskey reported by the designers[START_REF] Mouha | Chaskey: An Efficient MAC Algorithm for 32-bit Microcontrollers[END_REF]

	Rounds:	1	2	3	4	5	6	7	8
	Probability:	1	2 -4	2 -16	2 -37	2 -73.1	2 -132.8	2 -205.6

also called correlation

A notable counterexample is FEAL, which uses only 8-bit additions.

This setting is quite general, because any operation before a key addition can be removed, as well as any linear operation after the key addition. Ciphers where the key addition is made with a modular addition do not fit this model, but they can still take advantage of partitioning techniques.

Note that in the application to E, we can modify the difference in x 1 but not in y 1 .

We use Biham and Carmeli's notation fi,j for bit j of input word i

We also consider pairs of adjacent bits, following the analysis of[START_REF] Cho | Crossword Puzzle Attack on NLS[END_REF].

v 0 [4] ⊕ v 2 [3] v 2 [22] ⊕ v 3 [21] v 2 [27] ⊕ v 3 [26] v 2 [27] ⊕ v 3 [27] v 2 [3] ⊕ v 2 [4] v 2 [21] ⊕ v 2 [22] v 2 [26] ⊕ v 2 [27] v 0 [9] ⊕ v 1 [8] v 0 [14] ⊕ v 1 [13] v 0 [27] ⊕ v 1 [26] v 0 [30] ⊕ v 1 [30] v 0 [8] ⊕ v 0 [9] v 0 [18] ⊕ v 0 [19] v 0 [21] ⊕ v 0[START_REF] Lamberger | Higher-Order Differential Attack on Reduced SHA-256[END_REF]


Hui Li

Sébastien Le Beux
email: sebastien.le-beux@ec-lyon.fr

Gabriela Nicolescu

Jelena Trajkovic

Ian O'connor

Optical Crossbars on Chip: a comparative study based on worst-case losses

Keywords: Optical Network on Chip, crossbar, optical losses

The many cores design research community have shown high interest in optical crossbars on chip for more than a decade. Key properties of optical crossbars, namely a) contention free data routing b) low latency communication and c) potential for high bandwidth through the use of WDM, motivate several implementations of this type of interconnect. These implementations demonstrate very different scalability and power efficiency ability depending on three key design factors: a) the network topology, b) the considered layout and the c) the injection losses induced by the fabrication process. In this paper, the worst-case optical losses of crossbar implementations are compared according to the factors mentioned above. The comparison results has the potential to help many cores system designer to select the most appropriate crossbar implementation according, for instance, to the number of IP cores and the chip die size.

I.

INTRODUCTION Technology scaling down to the ultra deep submicron domain provides for billions of transistors on chip, enabling the integration of hundreds of cores. Many core designs integrating interconnect that can support low latency and high data bandwidth are being increasingly required in modern embedded systems to address the increasing power and performance constraints of embedded applications. Designing such systems using traditional electrical interconnect represents a significant challenge: due to capacitive and inductive coupling [START_REF] Ho | The Future of Wires[END_REF], interconnect noise and propagation delay of global interconnect increase. The increase in propagation delay requires global interconnect to be clocked at a very low rate, which limits the achievable bandwidth and overall system performance.

In this context, Optical Network-on-Chip (ONoC) is an emerging technology considered as one of the key solutions for the future generation of on-chip interconnects. It relies on optical waveguides to carry optical signals, so as to replace electrical interconnect and provide the low latency and high bandwidth properties of the optical interconnect. Moreover, 3D integration technologies allow for both optical and electrical layers to be stacked. Proposals for ONoC can, thus, realistically envision the integration of sufficient photonic devices for fast chip-length communications [START_REF] Psota | ATAC: Improving Performance and Programmability With on-Chip Optical Networks[END_REF][2] [START_REF] Ye | A Torus-based Hierarchical Optical-Electronic Networkon-Chip for Multiprocessor System-on-Chip[END_REF].

Among the proposed ONoCs, the crossbar-based solutions gain considerable interest among the major players in the field. The efficient crossbar solutions rely on passive Microring Resonators (MRs), and they do not require any arbitration [START_REF] O'connor | Reduction Methods for Adapting Optical Network on Chip Topologies to Specific Routing Applications[END_REF] [START_REF] Beux | Layout Guidelines for 3D Architectures including Optical Ring Network-on-Chip (ORNoC)[END_REF] due to the dedicated point-to-point connections between IP cores. In these networks, the signals propagation relies on Wavelength Division Multiplexing (WDM). Comparing the proposed crossbars is a tedious task, since it requires considering both network characteristics and technological data, assuming layout constraints.

In this paper, we compare proposed crossbars according to their worst-case losses, which is a key metric to evaluate the ONoC scalability and power efficiency. The worst-case losses can be estimated by considering the losses in the network (e.g. from waveguide crossing and waveguide length) and the optical losses value (e.g. propagation loss).

The paper is structured as follows. Section II presents the considered architecture model, topologies and implementations. Section III presents the loss model and a design methodology for a given crossbar ORNoC is given in Section IV. Section V gives the comparison results and Section VI concludes the paper.

II. ARCHITECTURE MODEL, TOPOLOGIES AND

IMPLEMENTATIONS In this section, we describe the considered ONoC architecture model, the associated topologies and implementations.

A. Architecture Model Overview

Figure 1 illustrates the considered 3D architecture model. It is composed of an electrical layer implementing NxN IP cores and an optical layer implementing ONoC. In our study, we assume N is an even number but the work could be easily extended for odd values and for NxM IP cores architectures. The optical network in the optical layer is composed of on-chip laser sources [START_REF] Van Campenhout | A compact SOI-integrated multiwavelength laser source based on cascaded InP microdisks[END_REF], MRs, and photodetectors. The ONoC is connected to the IP cores through Through Silicon Vias (TSV) [START_REF] Loi | Supporting Vertical Links for 3D Networks-on-Chip: Toward an Automated Design and Analysis Flow[END_REF]. Numerous ONoCs relying on WDM were proposed. Among these networks, wavelength routing scheme can be used to propagate data from a source IP core to a destination IP core, thus leading to a contention-free network (without need for arbitration), with high throughput, and low latency. In this work, we compare ONoC architecture implementing crossbar functionality by considering the use of on-chip lasers. Indeed, efficient on-chip lasers usually require the inclusion of III-V semiconductors: gallium arsenide (GaAs) or indium phosphide (InP) are currently considered to be the best options. Microlasers, based on microdisk structures coupling light evanescently from the cavity resonant mode to the guided mode in an adjacent silicon waveguide, are sufficiently compact as to be implemented in a large number and at any position. For a given wavelength, the size of an on-chip laser is of the same order of magnitude as the size of an MR used to modulate continuous waves emitted by off chip lasers, which leads to a similar on-chip size for both approaches. While onchip laser sources require the use of less mature technologies compared to their off-chip counterpart, they have the potential to provide the following three key advantages:

• Easier and more efficient integration by relaxing layout constraints: in case of on-chip lasers, it is not necessary to distribute the light from an external source to the modulators (e.g. through the so called power waveguide in Corona [START_REF] Vantrease | Corona: System Implications of Emerging Nanophotonic Technology[END_REF]).

Relaxing such constraints contributes to reducing the number of waveguide crossings or even to avoiding them altogether in the ring topology. • Higher scalability by keeping the architecture fully distributed, which is not achievable by considering centralized off-chip lasers. • Lower power by reducing the worst-case communication distance. This corresponds to the distance from the source IP to the destination IP for on-chip laser based architectures, while for off-chip laser based architecture, this distance includes also the distance from the off-chip laser to the source IP. Shorter distance consequently reduces the optical losses and hence the minimum required laser output power. Moreover, the power consumption can be further improved by locally turning off the laser when no communication is required.

B. Passive ONoC Architecture Implementations

The crossbar network topologies considered in this study are 1) Matrix [START_REF] Bianco | Optical Interconnection Networks based on Microring Resonators[END_REF], 2) λ-router [START_REF] O'connor | Reduction Methods for Adapting Optical Network on Chip Topologies to Specific Routing Applications[END_REF], 3) Snake [START_REF] Ramini | Contrasting wavelength-routed optical NoC topologies for powerefficient 3D-stacked multicore processors using physical-layer analysis[END_REF], 4) ORNoC [START_REF] Beux | Layout Guidelines for 3D Architectures including Optical Ring Network-on-Chip (ORNoC)[END_REF], as shown in Figure 4. In the figure, each column is dedicated to a topology and the lines give their i) graphical representation, ii) implementation characteristics, iii) layout and iv) loss model. This section briefly introduces these implementations and illustrates the way they can be used to interconnect 2x2 IP cores. We also illustrate the layout for 4x4 IP cores architecture, and evaluate the number of required optical devices, assuming N is an even number.

1) Matrix

The first crossbar topology relies on a traditional Matrixlike structure. Figure 2 (a) illustrates a simple example where 4 IP cores are interconnected using the Matrix. Full connectivity is considered, which leads to a total of 16 MRs in this example. By considering only inter-IP communications, one MR per line of the Matrix can be removed. For NxN IP cores, (N 2 -1)xN 2 passive MRs are, thus, used to implement the crossbar itself. The transmitters are composed of on-chip laser sources, and the receivers are composed of photodetectors and passive MRs that drop the signal onto the photodetector (not illustrated in the figure for sake of clarity). Because we focus on crossbar networks, we assume dedicated communication between all the IP cores through spatial WDM. As a consequence (N²-1)xN² laser sources, photodetectors and passive MR are required in the network interface. It is worthwhile noting that all topologies considered in this paper require the same. Matrix topology uses N²-1 wavelengths to implement all the communications.

Figure 2 also presents two possible layouts layout A and layout B , which are designed to A) avoid any waveguide crossing between the network interfaces and the crossbar itself and B) reduce the worst-case distance between IP cores. The crossbar is located in the middle of the optical layer for layout optimization purposes (it is represented as a box for the sake of clarity). It interconnects 16 inputs (in red lines) with 16 outputs (in black lines) through 240 MRs. The same layouts will be assumed to interface with λ-router and Snake networks.

2) λ-router λ-router is a multistage network topology relying on WDM to propagate optical signals from input to output ports. Compared to the Matrix, the multistage structure allows reducing the number of waveguide crossing in the worst-case scenario (6 and 3, for Matrix and λ-router, respectively, in the case of 4 IP cores). This is achieved by assuming symmetric 2x2 switches structure relying on 2 identical MRs. The initial structure of λ-router would assume 240 MRs, for the architecture with 4x4 IP cores, but a reduction method [START_REF] O'connor | Reduction Methods for Adapting Optical Network on Chip Topologies to Specific Routing Applications[END_REF] reduces the network complexity by managing only the required optical connections and by removing the unused MRs. As a result, 224 MRs are required to implement the network.

3) Snake Snake is, also, a multistage network topology. It has the same properties as the λ-router. The only difference is the distribution of the MRs in the network, which leads to the more compact layout compared to λ-router, with the side effect of different waveguide length between different input and output pairs. Similarly to λ-router, a reduction method adapted from [START_REF] O'connor | Reduction Methods for Adapting Optical Network on Chip Topologies to Specific Routing Applications[END_REF] can be applied to remove unused MRs.

4) ORNoC (Optical Ring Network-on-Chip) In ORNoC, each IP core communicates with another IP through waveguides forming a ring. The following operations are performed:

• Injection: the IP core injects an optical signal into a waveguide through its output port data. The wavelength of the signal specifies the destination of the IP core;

• Pass through: the incoming signal propagates along the waveguide (i.e. no MR with the same resonant wavelength is located along the waveguide); • Ejection: the incoming optical signal is ejected from the waveguide and is redirected to the destination IP core. This is achieved by an MR located along the waveguide and with the same resonant wavelength as the signal.

In ORNoC, the same wavelength can be used to realize multiple communications on the same waveguide, at the same time. Furthermore, and multiple waveguides can be used to interface IP cores. Both clockwise (C) and counter-clockwise (CC) rotation can be considered for signal propagation, where each direction is realized on a separate waveguide. For this comparative study, we consider two versions of ORNoC: ORNoC C and ORNoC C-CC that rely on: only the C rotation, and both C and CC rotations, respectively. Both are illustrated in Figure 2: blue and red lines represent C and CC directions separately. Compared to the other networks, no MR is used in the network itself, (i.e. MRs are used only in the network interfaces. This leads to a reduction of the total number of optical devices. However, the ring structure implies crossing intermediate interfaces. This leads to an increase of the minimum number of wavelengths to be used (6 and 3 wavelengths are required to interconnect 4 IP cores with ORNoC C and ORNoC C-CC , respectively). If the maximum number of wavelengths in the network is reached, then waveguides can be added in order to realize all the communication, without any impact on the layout complexity and the waveguide crossing, by considering a serpentine layout.

1) Matrix

2) λ-router

3) Snake 4a) ORNoC C 4b) ORNoC C-CC Structural view IP1 IP3 IP4 IP2 λ1 λ2 λ1 λ3 λ3 λ4 IP1 IP3 IP4 IP2
No. of resources

MR net 4 N 2 2 ) 1 ( N N × - 2 2 ) 1 ( N N × - 0 0 MR less 2 2 ) 1 ( N N × - 2 2 ) 2 ( N N × - 2 2 ) 2 ( N N × - 0 0 MR det 2 2 ) 1 ( N N × - NB Laser 2 2 ) 1 ( N N × - NB wl 1 2 - N 2 N 2 N 2 / ) 1 ( 2 2 N N × - 4 / ) 1 ( 2 2 N N × - Layout Loss model D max Layout A : d 3 N: 2   d N d N × × + × - × 2 2 / ) 1 ( 4 N: even and N>2 d N d N × - + × - ) 1 ( ) 2 ( 2   d N d N × - + × - ) 1 ( ) 1 2 / ( 2 Layout B : d N × - × ) 1 ( 2 N crossing (network and layout) 3 2 2 - × N 1 2 - N 5 2 2 - × N 0 0 Layout A : 0 Layout B : 1 2 / 4 / 3 2 - + × N N N drop 2 2 2 1 1

III. OPTICAL LOSS MODEL

This section presents the proposed optical loss models for crossbar comparison.

The worst-case losses in the optical path L wc for each network is defined by assuming NxN IP cores and by assuming N to be an even number greater than 2. We assume on-chip laser sources for all topologies, which contribute to reduced number of waveguide crossing compared to the offchip laser counterpart. The loss model is given by the expression [START_REF] O'connor | Reduction Methods for Adapting Optical Network on Chip Topologies to Specific Routing Applications[END_REF]. L wc depends on: the total propagation loss in the waveguide L waveguide , total loss due to waveguide crossing L crossing , and drop loss L drop when a signal encounters a MR with the same wavelength, all given in dBs. We assume a negligible bending loss: with P crossing and P drop the injection loss occurring in waveguide crossing and drop operation, respectively, and N crossing and N drop their respective number of occurrences in the worst case scenario.

Considering both technological and structural values related to the fabrication process and the network topology enables a fair comparison between networks.

Figure 2 gives the values D max , N crossing and N drop for the considered networks. For Matrix, λ-router and Snake networks, both layouts are considered, which leads to bigger longest distance in case A and more additional waveguide crossing in case B. We do not consider the distance between inputs and outputs of the network itself. Two drop operations occur, one in the network itself and one more in the receiver interface to drop the signal into the photodetector.

Both ORNoC C and ORNoC C-CC do not suffer from any waveguide crossing and the signal is dropped only once in the receiver part (N crossing =0 and N drop =1). However, the considered serpentine layout implies that d max increases more rapidly when compared to the other networks. It is worth noticing that d max is significantly reduced for the C-CC case compared to the C case. This will result in a lower worst-case loss, which directly contributes to the energy-efficiency of ORNoC C-CC . The following section gives the design methodology assumed for ORNoC in order to reduce both the number of required wavelengths and the worst case distance between a source IP and a destination IP.

IV. ORNOC WAVELENGTH ASSIGNMENT METHODOLOGY

IN ORNOC The efficient design of ORNoC requires careful wavelength assignment between IP cores to reduce the number of wavelengths. This section details the methodology for ORNoC C and ORNoC C-CC .

In ORNoC C , a single direction is used to propagate the signals. Therefore, in the the connectivity matrix, we allocate the same wavelength i) between IP i and IP j and ii) between IP j and IP i . Following this method, one wavelength is used in the whole ring to implement 2 connections, thus leading to an efficient assignment of the wavelength (i.e. there is no ring segment unoccupied by the wavelength). By considering the use of a single waveguide, the total number of required wavelengths is equal to half of the total number of connections in the network, i.e. N wl =(N²-1)xN²/2. By considering the use of multiple waveguides, the total number of used wavelengths can be reduced by reusing a same set of wavelengths in different waveguides. Figure 3 a) illustrates an example of wavelength assignment between a source (S) and a destination (D) for the design of a crossbar connecting 4 IP cores. In this example, 6 wavelengths are required (λ 0 ...λ 5 ), which is twice the number of required wavelengths in Snake, λ-router and Matrix. The large number of wavelengths is mainly due to the fact that each wavelength can be used only twice per waveguide. In ORNoC C-CC , the long distance communication can be avoided by implementing the connection through a shortest path assignment schemes, relying on the selection of the appropriate direction on a different ring. Communications from IP i to IP j and from IP j to IP i are realized through 2 separated waveguides propagating signals in opposite direction. For sake of regularity and symmetry in the connectivity matrix, the same wavelength is used for bidirectional communications. The wavelengths are assigned as follow: starting from source core IP X , first a wavelength is assigned to the longest distance communication in direction C, to a destination core IP Y ; second, the same wavelength is assigned to communication from IP Y to the longest distance communication (still in direction C), to a destination core IP Z . We apply the same assignment to the following longest distance communication until source core IP X is reached, meaning that the wavelength is used on the whole ring (i.e. the wavelength is efficiently used on the ring). The same process is applied starting from each IP core with a different wavelength. The same algorithm iterates with other wavelengths until a wavelength is assigned to each connection. Figure 3 b) illustrates the connectivity matrix for the 4 IP cores architecture example. Blue and red colors indicate the use of C and CC direction for signal propagation, respectively. Three wavelengths are required when considering the use of a single waveguide for each direction (e.g. by considering 3 waveguides, a single wavelength would be required). In this example, each wavelength is used only up to twice on a single waveguide, which is due to the small number of IP cores; wavelengths can be further reused as the number of IP cores increases, which contributes to the improvement of the communication density.

D S IP1 IP2 IP3 IP4 D S IP1 IP2 IP3 IP4 IP1 - λ 0 λ 1 λ 2 IP1 - λ 2 λ 0 λ 1 IP2 λ 0 - λ 3 λ 4 IP2 λ 2 - λ 2 λ 1 IP3 λ 1 λ 3 - λ 5 IP3 λ 0 λ 2 - λ 0 a IP4 λ 2 λ 4 λ 5 - b IP4 λ 1 λ 1 λ 0 -
V. COMPARATIVE STUDY We compare the presented implementations according to the worst-case losses. In a first comparison, all the networks are considered by assuming a given set of technological value extracted from Table 1. In a second comparison, we further compare the networks assuming various design parameters. [START_REF] Pan | FlexiShare: Channel Sharing for an Energy-Efficient Nanophotonic Crossbar[END_REF] [START_REF] Pan | FlexiShare: Channel Sharing for an Energy-Efficient Nanophotonic Crossbar[END_REF] 0.05 1 1.5 Kirman (2010) [START_REF] Kirman | A power-efficient all-optical on-chip interconnect using wavelength-based oblivious routing[END_REF] 0.12 1 1 Biberman (2011) [START_REF] Biberman | Photonic Network-on-Chip Architectures Using Multilayer Deposited Silicon Materials for High-Performance Chip Multiprocessors[END_REF] 0.05 0.5 0.5 Koka (2012) [START_REF] Koka | A micro-architectural analysis of switched photonic multi-chip interconnects[END_REF] 0.2 0.1 1.5

A. Worst-case losses evaluation

We first assume a fixed 4cm 2 die size and evaluate the losses for different architecture size: N=2, 4, and 8; where the distance between IP cores decreases as the number of IP cores increases, d=10mm, 5mm, 3.33mm and 2.5mm, respectively. ), the same conclusion can be made for architectures containing up to 6x6 IP cores. However, for 8x8 IP cores, worst case loss is lower for layout A , due to the lower propagation loss in the waveguide, thus highlighting the better scalability of this layout. It is worth noticing that other layouts could provide good tradeoff. ORNoC C-CC is the most scalable network despite the long distance introduced by the serpentine layout. By considering values from Biberman, ORNoC C-CC is the most scalable network, with 5.25dB in the worst case path for 8x8 IP cores, followed by λ-router using layout B (so called λ-router-b in the figure) with 8.45dB, thus achieving 37.9% improvement. By assuming parameters from Koka (not illustrated), the worst-case loss in ORNoC C-CC and λ-router-b become 2.45dB and 26.15dB, thus leading to a 90.6% improvement for ORNoC C-CC . Because of the rather large distance implied by the die size we consider, ORNoC C does not exhibit a good scalability. For a 8x8 architecture with a single waveguide per direction, ORNoC C-CC requires 1008 wavelengths compared to 63 wavelengths for Matrix and 64 for Snake and λ-router. 1008 is not a realistic value for the number of wavelengths; however, it is important to notice that additional waveguides can be used in ORNoC to satisfy the constraints on the maximum number of wavelengths, which can be achieved without any waveguide crossing because of the 3D architecture and the use of on-chip laser sources. Following the methodology from [START_REF] Beux | Layout Guidelines for 3D Architectures including Optical Ring Network-on-Chip (ORNoC)[END_REF], ORNoC would require 16 waveguides if we consider an optimistic maximum number of 64 wavelengths per waveguides, and 63 waveguides if we consider more realistic scenario with 16 wavelengths per waveguide. If such constraints on the number of wavelengths must be respected for Matrix, Snake or λrouter, this can be achieved by considering the use of multiple networks, which implies additional waveguide crossing [START_REF] Beux | Multi-Optical Network on Chip for Large Scale MPSoC[END_REF]. With ORNoC C-CC , no waveguide crossing is required, the layout is regular and d max is reduced compared to ORNoC C , which make the network implicitly scalable without any custom place-and-route tool [START_REF] Ramini | Contrasting wavelength-routed optical NoC topologies for powerefficient 3D-stacked multicore processors using physical-layer analysis[END_REF] [START_REF] Ramini | Engineering a Bandwidth-Scalable Optical Layer for a 3D Multi-Core Processor with Awareness of Layout Constraints[END_REF].

Figure 5 represents the worst case loss assuming parameters given by Biberman, size of 8x8 IP cores, and various distance between IP cores (d=0.125, 0.25, 0.5, 1 and 2mm). The impact of the distance increase is the greatest for ORNoC C and ORNoC C-CC , due to the serpentine layout. Still, even for a 2mm distance, which implies a realistic 2.56cm² die size, ORNoC C-CC remains the most power efficient network.

B. Implementation Comparison

In order to further explore the design space, for the example of 8x8 IP cores, and various distances, we consider a range of 0-2dB for propagation losses and a range of 0-0.2dB for waveguide crossing loss.

Figure 6 illustrates comparison results for the implementation of λ-router according to layout A (i.e. without waveguide crossing) and layout B (reduced waveguide length), assuming P drop =1dB. We also plot the values from Table 1. The area below each line represents the design space for which the worst case is lower for layout A ; the area above the line gives the design space where the worst case loss is lower for layout B , and the line itself represents the designs with the same worst case losses for both layouts. This further helps determine the most appropriate layout, for a given set of injection loss values, and a given distance between IP cores. These comparisons highlight the importance of technological parameters, layout and network characteristics to evaluate the worst-case optical loss. For a given set of technological value (e.g. crossing loss), certain topology and layout may be more advantageous, which may significantly impact the overall power efficiency of the crossbar. VI. CONCLUSION Optical crossbars on chip represent an efficient interconnect solution for many cores architectures. Various crossbar implementations are possible and their worst-case losses rely on topological, physical and technological aspects. In this paper, we compare possible crossbar implementations relying on matrix, multistage and ring-based networks. For a given number of IP cores to interconnect and a given die size, our approach allows to identify the implementation characterized by the lower worst-case optical losses, i.e. the most power efficient solution. For the explored design space, ring-based topology implementations exhibit higher power efficiency compared to matrix based and multistage-based network implementations. The approach was applied to passive and fully interconnected networks but it can be extended to active networks requiring resources allocation mechanism. We will focus on this aspect in our future work.

Figure 1 :

 1 Figure 1: The crossbar ONoC is implemented on the optical layer and it interconnects IP cores located on the electrical layer

Figure 2 :

 2 Figure 2: Summary of considered ONoC: 1) Matrix, 2) λ λ λ λ-router, 3) Snake, 4a) ORNoC C and 4b) ORNoC C-CC

  P propagation (in dB/cm) the intrinsic propagation loss of the optical signal in the waveguide and d max (in cm) the longest distance between the source and destination. It depends on the layout represented in Figure2. A key metric to define d max is the distance d between two neighboring interfaces to the IP cores;

Figure 3 :

 3 Connectivity matrix for a) ORNoC and b) ORNoC C-CC

Figure 4 a

 4 ) and b) illustrate the evaluation results for injection losses with the parameter values given by Pan and Biberman, respectively. If we compare different layouts for Matrix, λrouter and Snake topologies, using the values from Pan, (Figure 4 a), layout B uniformly outperforms layout A , for all network By considering the set of values from Pan (Figure 4 a), layout B outperforms layout A for Matrix, λ-router and Snake networks. By considering values from Biberman (Figure 4 b

Figure 4 :

 4 Figure 4: Worst-case losses evaluation for various number of IP cores assuming injection loss parameters from a) Pan [12] and b)Biberman[START_REF] Biberman | Photonic Network-on-Chip Architectures Using Multilayer Deposited Silicon Materials for High-Performance Chip Multiprocessors[END_REF]

Figure 5 :

 5 Figure 5: Evaluation of the impact of the distance between IP cores on the worst case losses

Figure 6 :Figure 7

 67 Figure 6: Comparison of layout A and layout B for the implementation of λ λ λ λ-router (8x8 IP cores, P drop =1dB) Figure 7 further compares Snake and ORNoC C-CC : the area below a line represents the design space for which ORNoC C-CC provides lower worst-case losses, thus highlighting the advantage of ORNoC C-CC compared to Snake.These comparisons highlight the importance of technological parameters, layout and network characteristics to evaluate the worst-case optical loss. For a given set of technological value (e.g. crossing loss), certain topology and layout may be more advantageous, which may significantly impact the overall power efficiency of the crossbar.

Figure 7 :

 7 Figure 7: Comparison between Snake vs ORNoCc -CC (8x8 IP cores, P drop =1dB)

Table 1 : Injection Loss parameters

 1

	Optical loss	P crossing	P propagation	P drop

ACKNOWLEDGMENT

Sébastien Le Beux is supported by a Région Rhône-Alpes grant.