Christina Boura
email: christina.boura@uvsq.fr

Anne Canteaut
email: anne.canteaut@inria.fr

Jérémy Jean
email: jeremy.jean@ssi.gouv.fr

Valentin Suder
email: valentin.suder@uvsq.fr

Two Notions of Differential Equivalence on Sboxes

Keywords: Boolean function, Sbox, APN, difference distribution table, equivalence

come   L'archive ouverte pluridisciplinaire

Introduction

Block ciphers are central primitives in symmetric encryption schemes. Modern block ciphers are designed based on a methodology which guarantees that the cipher is resistant against all classical attacks. Differential cryptanalysis, presented by Biham and Shamir in 1990 [BS91], is one of the most prominent attacks against block ciphers, and a precise evaluation of its complexity has led to some design criteria on the building blocks in the cipher. The main criterion, which has been introduced by Nyberg and Knudsen [NK93,Nyb94], is the so-called differential uniformity of the Sbox, i.e., of the nonlinear mapping used in the cipher. This parameter should be as small as possible in order to maximize the complexity of differential attacks, and the mappings with the lowest differential uniformity, named APN mappings, have been investigated in many works during the last twenty-five years. These mappings are indeed highly relevant for cryptographic applications and they are also optimal combinatorial objects of independent interest. Therefore, this design criterion is at the origin of a whole line of research, including the search for infinite families of permutations with a low differential uniformity, the study of their properties or some classification work (e.g. [Nyb94, CV95, CCZ98, Dob99, BDMW10, HM11, EKP06]).

However, besides the differential uniformity of the Sbox, the whole differential spectrum and even the form of the difference distribution table (DDT) are important when the resistance against several variants of differential cryptanalysis is quantified. The number of occurrences of the differential uniformity in the DDT of the Sbox corresponds to the number of one-round differentials with the highest probability and should then be minimized. Also, the whole differential spectrum of the Sbox is involved in all known upper-bounds on the maximal expected differential probability over two rounds of an SPN cipher [PSLL03,CR15]. Not only the number, but also the location within the DDT of these maximal values may influence the resistance of the cipher against multiple differential cryptanalysis [BG11] or truncated differential attacks [Knu95] (see e.g. [BCC10, Section 3.2] for a discussion). When designing a block cipher, it would then be of major interest to be able to start from a desired DDT which guarantees a high resistance against all variants of differential cryptanalysis, and to construct Sboxes having this specific DDT. Instead, the main technique currently available to the designers consists in randomly generating Sboxes until one with a suitable DDT is found. However, constructing Sboxes from a prescribed DDT is a difficult problem, related to many open issues in the area. The characterization of the valid DDT, i.e., for which there exists at least one function with these particular DDT, is also open. In the case of APN functions, this general problem corresponds to the problem of determining the differential equivalence class of a given function, introduced by Gorodilova [Gor16]. It has also been raised by Carlet in the case of APN functions [Car15,Pb. 3.11]. It is obviously related to the so-called Big APN problem, i.e., the existence of APN permutations operating on an even number of variables. Indeed, it has been long conjectured that bijective APN functions do only exist in odd dimension, until the first ever counter-example over F 6 2 was presented by Dillon et al. [BDMW10]. However, the conjecture still stands for any even dimension n ≥ 8.

Our Contributions. In this work, we are interested in two different equivalence notions for vectorial Boolean functions, that we call DDT and γ-equivalence. The first one applies to functions sharing the same difference distribution table while the second, applies more generally to functions whose DDT have the same support. In [Gor16], Gorodilova studies the γ-equivalence classes for quadratic APN functions and in particular for the Gold family of functions. She most notably proves that the size of the γ-classes for any function is invariant under extended affine (AE) equivalence. Gorodilova wonders then whether something similar can be proved for CCZ-equivalence. In this work, we give an answer to this question by proving that the number of elements in the differential class of a function is invariant under CCZ-equivalence.

In parallel, we also provide an algorithm for computing the differential equivalence class corresponding to a prescribed DDT. We applied this algorithm to find several equivalence classes. Most notably, one of the main problems we focus on is to determine whether the differential equivalence class of a permutation over F n 2 can contain more than 2 2n elements. In other words, we wonder whether two permutations F and G with the same DDT necessarily satisfy

G(x) = F (x ⊕ c) ⊕ d for some c, d ∈ F n 2 .
As a result, we found permutations F whose differential equivalence classes contain other elements than the functions x → F (x ⊕ c) ⊕ d. However, we conjecture that this is only the case when some rows of the corresponding DDT are equal. We also discuss some properties of the DDT of an APN permutation, adding some constraints on the valid DDT for such permutations.

Two Notions of Differential Equivalence

Even if the following properties hold in the general case, our work mainly focuses on vectorial Boolean functions with the same number of inputs and outputs, i.e., on functions from F n 2 into itself. Several cryptographic Sboxes are examples of such functions, which usually verify additional properties for cryptographic applications, most notably nonlinearity. Although we focus on Sboxes in the remainder of this paper, most of the results can be adapted to general vectorial Boolean functions.

DDT-equivalence and γ-equivalence

The differential properties of a vectorial Boolean function are related to its derivatives.

Definition 1 (Derivative of a function). Let F be a function from

F n 2 into F m 2 . The derivative of F with respect to a ∈ F n 2 is the function ∆ a F : x ∈ F n 2 → F (x ⊕ a) ⊕ F (x).
The constant derivatives of a function often play a major role and correspond to its linear structures.

Definition 2 (Linear space and linear structures of a function). Let F be a function from

F n 2 into F m 2 . An element a ∈ F n 2 is called a linear structure of F if ∆ a F is constant.
The set of all linear structures is a vector space named the linear space of F .

The multi-sets corresponding to the images of the derivatives of F are usually represented as a two-dimensional array called the difference distribution table.

Definition 3 (DDT and its characteristics). Let F be a function from

F n 2 into F n 2 . The difference distribution table (DDT) of F is the two-dimensional table defined by δ F (a, b) = #{x ∈ F n 2 : ∆ a F (x) = b}, ∀a, b ∈ F n 2 .
Two important characteristics of the DDT, introduced in [Nyb94, CCZ98] respectively, are as follows:

the differential uniformity of F is the highest value in the DDT, i.e.

max a,b∈F n 2 ,a =0 δ F (a, b).
The lowest possible value for the differential uniformity of a function from F n 2 into itself is two and the functions with differential uniformity two are called almost perfect nonlinear (APN).

the indicator of the DDT is the Boolean function of 2n variables defined by

γ F (a, b) = 0 if and only if δ F (a, b) = 0 or a = 0.
The previous properties then lead to two different notions of equivalence between Sboxes. We say that F and G are DDT-equivalent if they have the same DDT, and that they are γ-equivalent if their DDTs have the same support, or equivalently if

γ F = γ G .
The notion of γ-equivalence has been investigated under the name differential equivalence by Gorodilova [Gor16]. It must not be confused with the differential equivalence introduced in [Sud15, Sud17], which refers to another property.

Obviously, DDT-equivalence implies γ-equivalence. However, the converse also holds in some particular cases.

Proposition 1. Let F and G be two functions from F n 2 into itself which are γequivalent. Assume that, for each derivative of F and G, there exists some integer λ such that the derivative is a λ-to-1 function. Then, F and G are DDT-equivalent. Most notably, this situation holds when both F and G are quadratic functions. It also implies that any function which is γ-equivalent to an APN function F is also DDT-equivalent to F .

Proof. The result comes from the fact that, in this case, the DDT of the function is entirely determined by its support. Assume that, for any a ∈ F n 2 , a = 0, ∆ a F is a λ-to-1 function (where λ may depend on a). Then, the entries of the row in the DDT corresponding to ∆ a F belong to {0, λ}. Since the sum of all entries within a row equals 2 n , we deduce that λ is a power of two, and its value can be deduced from the number of elements b such that γ F (a, b) = 1 which equals 2 n λ -1 . Then, the row corresponding to ∆ a F is entirely deduced from γ F . When F is a quadratic function, its derivatives have degree at most one. Then, ∆ a F is a 2 d -to-1 function where d is the dimension of the kernel of ∆ a F .

It is worth noticing that the previous proposition does not mean that the γequivalence class of a quadratic function equals its DDT-equivalence class. A quadratic function F such that C γ (F ) = C DDT (F ) is exhibited at the end of Section 2.2. However, the two notions coincide for APN functions, for instance for the quadratic APN functions studied in [Gor16] and in [YWL14], implying that the γ-equivalent APN functions exhibited in [Gor16] are also DDT-equivalent. In general, the two notions of differential equivalence do not coincide. The following example exhibits two γ-equivalent functions with different DDTs.

Example 1. Let F and G : F 4 2 → F 4 2 be represented by their value tables: ,2,3,4,5,6,7,8,9,10,11,12,13,15,14], ,3,2,5,4,7,6,8,9,10,11,12,13,14,15].

F = [0,1
G = [0,1
Both DDTs are diagonal with 2 × 2 blocks, the first block being 16 0 0 16 for both tables. Then, for F , all the diagonal blocks are 12 4 4 12 , whereas for G, half of the blocks only are of this shape, the other ones are 4 12 12 4 . It is then clear that F and G, who are both of algebraic degree three, are γ-equivalent, but are not DDT-inequivalent.

Properties of differential-equivalence classes

In this work, we mainly focus on the sizes of the DDT-equivalence classes and γequivalence classes. A lower bound on these sizes is given in the following proposition.

Proposition 2. Let F be a function from F n 2 into itself and let denote the dimension of its linear space, i.e., of the space formed by all linear structures of F . Then, the DDT-equivalence class of F contains the 2 2n-distinct functions of the form

x → F (x ⊕ c) ⊕ d, c, d ∈ F n 2 .
(1)

Proof. The fact that all functions F c,d : x → F (x ⊕ c) ⊕ d are DDT-equivalent is well-known (e.g., [Gor16,Prop. 1]). Now, two pairs (c 1 , d 1 ) and (c 2 , d 2 ) lead to the same function if and only if, for all x ∈ F n 2 ,

F (x ⊕ c 1 ) ⊕ F (x ⊕ c 2 ) = d 1 ⊕ d 2 , which means that ∆ c 1 ⊕c 2 F = d 1 ⊕ d 2 , i.e. (c 1 ⊕ c 2 ) is a linear structure and d 2 = d 1 ⊕ ∆ c 1 ⊕c 2 F .
Then, the number of distinct functions F c,d equals 2 2n-.

In the sequel, we consider that two functions are trivially DDT-equivalent if they satisfy Equation (1) from the above Proposition 2. Moreover, we say that a DDTequivalent class is trivial if its size matches the lower-bound given in Proposition 2.

In [Gor16], Gorodilova conjectures that if F is an APN quadratic function, then for all functions F that are DDT-equivalent to F we have that deg(F ⊕ F ) ≤ 1. This relation is obvious if F is trivially equivalent to F as in this case F ⊕ F is just a derivative function of F . However, the above relation does not hold if F is not APN. The following proposition exhibits such a counter-example.

Proposition 3. For any even n ≥ 4, there exists a quadratic function

Q from F n 2 into F n 2 whose DDT-equivalence class contains a function of any degree d, 2 ≤ d ≤ n/2.
Proof. Let f be a bent function of n variables and F be the function from

F n 2 into itself defined by F (x) = (f (x), c 1 , . . . , c n-1 ), ∀x ∈ F n 2 , where (c 1 , . . . , c n-1 ) is a constant in F n-1 2
. Then, ∆ a F (x) = (∆ a f (x), 0, . . . , 0). Since f is bent, ∆ a f is balanced for all nonzero a. Then, ∆ a F takes the value (0, 0, . . . , 0) for 2 n-1 inputs, and the value (1, 0, . . . , 0) for the other ones. In other words, the DDT of any such Sbox F is defined by: for any nonzero a ∈ F The result then follows from the fact that, for any even n ≥ 4, there exist bent functions of n variables with degree d for all 2

≤ d ≤ n/2 [Rot76, Page 303].
For instance, the following quadratic Sbox F from F 4 2 → F 4 2 follows the previous construction

F = [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1].
The DDT class of F is not trivial and contains 7168 functions. This number actually corresponds to the number of bent functions of 4 variables, 28 × 2 5 , multiplied by the number of possible constants (c 1 , c 2 , c 3 ) ∈ F 3 2 that can be used for defining the last three coordinates. As an example,

F = [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1].
is non-trivially DDT-equivalent to F and has also algebraic degree two. However, deg(F ⊕ F ) = 2.

As we have just shown, the DDT-equivalence does not preserve the algebraic degree. Another natural question is what happens with the differential uniformity. Obviously, the DDT-equivalence preserves the differential uniformity. However, this is not the case for γ-equivalence. We give below a four functions F 1 , . . . , F 4 from F 4 2 to itself that are γ-equivalent but have a different differential uniformity. 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] with δ F 1 = 14,F 2 = [1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1] with δ F 2 = 12,

F 1 = [
F 3 = [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1] with δ F 3 = 10, F 4 = [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1] with δ F 4 = 8.
The last function, F 4 , has degree two. Since F 1 , F 2 , F 3 are γ-equivalent to F 4 but not DDT-equivalent, F 4 is an example of a quadratic function whose γ-equivalence class does not coincide with the DDT-equivalence class.

Invariance of the Sizes of Differential-Equivalence Classes Under CCZ-Equivalence

Another important property of the size of these equivalence classes is the following result proved in [Gor16] for γ-equivalence, which can easily be generalized to DDTequivalence. The proof, that closely follows the proof idea of [Gor16] is provided here for completeness.

Proposition 4 (adapted from [Gor16]). Let F and G be two functions which are EA-equivalent, i.e., there exist three affine functions A 0 , A 1 , A 2 where A 1 and

A 2 are bijective such that G = A 2 • F • A 1 ⊕ A 0 .
Then, the DDT-equivalence classes (resp. γ-equivalence classes) of F and of G have the same size. Moreover, the class of G is composed of all A 2 • F • A 1 ⊕ A 0 where F varies in the class of F .

Proof. Let L 0 , L 1 and L 2 denote the linear parts of the affine functions A 0 , A 1 and A 2 . It is well-known that the DDT of F and G are related by

δ G (a, b) = δ F (L 1 (a), L -1 2 (b ⊕ L 0 (a)))
, for all (a, b) .

(2)

This comes from the fact that

∆ a G(x) = A 2 [F (A 1 (x ⊕ a))] ⊕ A 2 [F (A 1 (x))] ⊕ A 0 (x ⊕ a) ⊕ A 0 (x), = L 2 [F (A 1 (x) ⊕ L 1 (a)) ⊕ F (A 1 (x))] ⊕ L 0 (a), = L 2 ∆ L 1 (a) F (A 1 (x)) ⊕ L 0 (a).
Let F ∈ C DDT (F ) be an element in the DDT-equivalence class of F and let us consider

G = A 2 • F • A 1 ⊕ A 0 . Then, the DDT of F and G satisfy: for all (a, b) δ G (a, b) = δ F (L 1 (a), L -1 2 (b ⊕ L 0 (a))) = δ F (L 1 (a), L -1 2 (b ⊕ L 0 (a))),
where the last equality comes from the fact that F and F have the same DDT. Then, we deduce from (2

) that δ G (a, b) = δ G (a, b) for all (a, b). It follows that (A 2 • F • A 1 ⊕ A 0 ), F ∈ C DDT (F ) ⊆ C DDT (G).
By exchanging the roles of F and G, we deduce that both sets coincide.

Whether an analogue of the previous result holds for CCZ-equivalence is a natural question raised by Gorodilova [Gor16]. An obvious case for which it can be proved that two CCZ-equivalent functions F and G have DDT-classes of the same size is when F is a permutation and G = F -1 . Indeed, if F is a permutation, any function Φ in C DDT (F ) is a permutation too and the DDT of

Φ -1 satisfies δ Φ -1 (a, b) = δ Φ (b, a) = δ F (b, a) = δ F -1 (a, b). Thus, C DDT (F -1 ) = {Φ -1 , Φ ∈ C DDT (F )}.
But the general case of two CCZ-equivalent functions F and G seems more difficult. Indeed, CCZ-equivalence means that

{(x, G(x)), x ∈ F n 2 } is the image of {(x, F (x)), x ∈ F n 2 } by a linear permutation L of F n 2 × F n 2 .
However, this implies that, if L is seen as a pair of functions,

L : (x, y) → (L 1 (x, y), L 2 (x, y)), then x → L 1 (x, F (x)
) is a permutation. This last condition is then required for transforming a given function F into a CCZ-equivalent function. Thus, if we want to prove, as it holds when F and G are EA-equivalent, that the DDT-equivalence class of F can be transformed into the DDT-equivalence of G by applying the same L, we need to prove that x → L 1 (x, Φ(x)) is a permutation for all Φ ∈ C DDT (F ). This is the keypoint in the following theorem.

Theorem 1. Let F and G be two CCZ-equivalent functions from F n 2 into itself and let L be a linear permutation of F n 2 × F n 2 seen as a pair of two linear functions:

L(x, y) = (L 1 (x, y), L 2 (x, y)) such that F 1 : x → L 1 (x, F (x)) is a permutation and L(x, F (x)) = (F 1 (x), G • F 1 (x)) for all x ∈ F n 2 .
Then, the DDT-equivalence classes (resp. γ-equivalence classes) of F and of G have the same size. More precisely,

C DDT (G) = L 2 (Φ -1 1 (x), Φ • Φ -1 1 (x)), Φ ∈ C DDT (F ) , C γ (G) = L 2 (Φ -1 1 (x), Φ • Φ -1 1 (x)), Φ ∈ C γ (F ) ,
where

Φ 1 : x → L 1 (x, Φ(x)).
Proof. The proof results from the fact that the DDT of two CCZ-equivalent functions F and G, which are related by

L(x, F (x)) = (F 1 (x), G • F 1 (x)) for all x ∈ F n 2 , satisfy: δ G (a, b) = δ F (L -1 (a, b)) for all (a, b).
Indeed, the number of (x, x ) in F n 2 such that

x ⊕ x = a and G(x) ⊕ G(x ) = b equals the number of y = F -1 1 (x) and y = F -1 1 (x ) such that F 1 (y) ⊕ F 1 (y ) = a and G • F 1 (y) ⊕ G • F 1 (y ) = b or equivalently L(y, F (y)) ⊕ L(y , F (y )) = L y ⊕ y , F (y) ⊕ F (y ) = (a, b).
It follows that, for any

Φ ∈ C DDT (F ) such that Φ 1 : x → L 1 (x, Φ(x)) is a permutation, the function Γ : x → L 2 (Φ -1 1 (x), Φ • Φ -1 1 (x)) satisfies δ Γ (a, b) = δ Φ (L -1 (a, b)) = δ F (L -1 (a, b)),
where the first equality is deduced from the fact that

L(x, Φ(x)) = (Φ 1 (x), Γ • Φ 1 (x)) , ∀x ∈ F n 2 . Thus, δ Γ (a, b) = δ G (a, b), i.e. Γ ∈ C DDT (G). Similarly, for any Φ ∈ C γ (F ) such that Φ 1 : x → L 1 (x, Φ(x)
) is a permutation, the indicators of the DDTs satisfy

γ Γ (a, b) = γ Φ (L -1 (a, b)) = γ F (L -1 (a, b)), implying that Γ ∈ C γ (G). Now, we need to prove that any Φ ∈ C γ (F ) is such that Φ 1 : x → L 1 (x, Φ(x)
) is a permutation. Suppose that Φ 1 is not a permutation. Then, there exist two distinct elements x and

x in F n 2 such that L 1 (x, Φ(x)) = L 1 (x , Φ(x )), implying L 1 (x ⊕ x , Φ(x) ⊕ Φ(x )) = 0. Let a := x ⊕ x and b := Φ(x) ⊕ Φ(x ). Then, L 1 (a, b) = 0
and both a and b differ from 0 since Φ is a permutation. By definition, δ Φ (a, b) > 0 since x and x are solutions of

Φ(X ⊕ a) ⊕ Φ(X) = b. Since Φ ∈ C γ (F ), δ Φ (a, b) > 0 if and only if δ F (a, b) > 0. We deduce that δ G (L(a, b)) = δ F (a, b) > 0. But, L(a, b) = (L 1 (a, b), L 2 (a, b)) = (0, c) for some nonzero c ∈ F n
2 since L is a permutation and (a, b) = (0, 0). We then get that there exists some nonzero c such that δ G (0, c) > 0, which is impossible. Therefore, for any

Φ ∈ C γ (F ), x → L 1 (x, Φ(x)) is a permutation. We deduce that L 2 (Φ -1 1 (x), Φ • Φ -1 1 (x)), Φ ∈ C DDT (F ) ⊆ C DDT (G)
and

|C DDT (G)| ≥ |C DDT (F )|.
Similar relations hold for the γ-equivalence classes.

Equality is then derived by exchanging the roles of F and G.

It follows that the sizes of these differential-equivalence classes can be computed for one representative in each CCZ-equivalence class only.

Other Characterizations of DDT-Equivalence

The DDT-equivalence can also be expressed in terms of the Walsh transform. Indeed, it is well-known [CV95, BN13] that the squared Walsh coefficients of an Sbox are obtained by computing the Fourier transform of its difference table.

Definition 4 (Walsh transform). Let F be a function from F n 2 into itself. The Walsh transform of F is the function

W F : (u, v) → W F (u, v) = x∈F m 2 (-1) u•x+v•F (x) ,
where x • y denotes the scalar product between two elements x and y in F n 2 .

Proposition 5 (DDT-equivalence and Walsh transform). Let F and G be two functions from F n 2 into itself. Then, F and G are DDT-equivalent if and only if

W 2 F (u, v) = W 2 G (u, v), ∀u, v ∈ F n 2 .
Proof. The squared Walsh coefficients of any function are given by applying the Walsh transform to the difference table as follows (see e.g.

[BN13]): for any u, v ∈ F n 2 , W 2 F (u, v) = a,b∈F n 2 (-1) a•u+b•v δ F (a, b). (3)
Therefore, if F and G have the same DDT, we deduce that

W 2 F (u, v) = W 2 G (u, v), ∀u, v ∈ F n 2 .
The converse is derived in the same way, since applying the inverse Fourier transform to (3) leads to

δ F (a, b) = 2 -2n u,v∈F n 2 (-1) a•u+b•v W 2 F (u, v).
The size of the DDT-equivalence class of a function then corresponds to the number of sequences of signs which provide a valid Walsh transform from a given squared Walsh transform.

The DDT-equivalence can also be characterized by the Hamming weights of the derivatives of the components of the Sbox, as stated in the following proposition. Proposition 6. Let F and G be two functions from F n 2 into itself. Then, F and G are DDT-equivalent if and only if, for all v ∈ F n 2 , the Boolean functions

F v : x → v • F (x) and G v : x → v • G(x) are such that ∆ a F v and ∆ a G v have the same Hamming weight for all a ∈ F n 2 .
Proof. Let v be a nonzero element in F n 2 . Then,

2 n -wt(∆ a F v ) = # {x ∈ F n 2 : ∆ a F v (x) = 0} = # {x ∈ F n 2 : v • ∆ a F (x) = 0} = # x ∈ F n 2 : ∆ a F ∈ v ⊥ = b∈ v ⊥ δ F (a, b).
It follows that, if F and G have the same DDT, then

wt(∆ a F v ) = wt(∆ a G v ), ∀a ∈ F n 2 .
Obviously, the equality also holds when v = 0 since F 0 and G 0 both correspond to the all-zero function in this case.

Conversely, let us now assume that wt(∆ a F v ) = wt(∆ a G v ) for all a and v. It is known (e.g., [Car93]) that

W 2 F (u, v) = a∈F n 2 (-1) a•u   x∈F n 2 (-1) ∆aFv(x)   .
Using that

x∈F n 2 (-1) ∆aFv(x) = 2 n -2wt(∆ a F v ), we deduce that, for all u, v ∈ F n 2 , W 2 F (u, v) = W 2 G (u, v),
which is equivalent to F and G being DDT-equivalent.

Applying the previous characterization to quadratic functions leads to the following corollary.

Corollary 1. Let F and G be two quadratic functions from F n 2 into itself. Then, F and G are DDT-equivalent if and only if, for any v ∈ F n 2 , F v and G v have the same linear space LS v and, for any

a ∈ LS v , ∆ a F v = ∆ a G v .
Proof. The proof is directly derived from the previous proposition, using the fact that, for a quadratic Boolean function f , any a which is not a linear structure of f is such that ∆ a f has degree one implying that wt(∆ a f ) = 2 n-1 . Therefore, the fact that ∆ a F v and ∆ a G v have the same Hamming weight needs to be checked when a is a linear structure of F v and G v only.

Computation of the γ-Equivalence and DDT-Equivalence Classes

We present in this section an algorithm that takes as input a 2 n × 2 n table D filled with nonnegative integers and returns all functions F from F n 2 into itself, if any, whose difference distribution table has the same indicator (see Definition 3) as the one of D, which we denote γ D . In other words, our algorithm retrieves the γ-equivalence class of functions of a given table D. Note that one can also derive the DDT-equivalent functions from this class, by post-filtering the functions returned by the algorithm against a desired DDT.

Throughout the following sections, we denote binary vectors of F n 2 by integers and make an extensive use of this notation. The algorithm determines all possible values for F (i), i = 0, . . . , 2 n -1, by taking into account the constraints imposed by the table D and the values F (j), j < i, that have already been computed. It essentially implements a tree-traversal algorithm, where each Level i contains the nodes corresponding to the possible values that F (i) can take. The tree therefore has depth 2 n . There is a natural incentive to implement such algorithms using recursion, which we adopt in the sequel.

From now on, we denote by R i = {y : D[i][y] = 0} the set of column indices of non-zero elements on D's ith row. The algorithm starts running and tries to determine all possible values for F (0), F (1), . . . , F (2 n -1). By assuming that all values F (0), F (1), . . . , F (i -1) have already been set, the value F (i) can be computed according to the following relations:

-F (i) ⊕ F (0) = ∆ i F (0) must lie in R i , -F (i) ⊕ F (1) = ∆ i⊕1 F (1) must lie in R i⊕1 , -F (i) ⊕ F (2) = ∆ i⊕2 F (2) must lie in R i⊕2 , -. . . -F (i) ⊕ F (i -1) = ∆ i⊕(i-1) F (i -1) must lie in R i⊕(i-1) .
Thus, F (i) should lie in the intersection of the sets

{x ⊕ F (0) : x ∈ R i } ∩ {x ⊕ F (1) : x ∈ R i⊕1 } ∩ • • • ∩ {x ⊕ F (i -1) : x ∈ R i⊕(i-1) }.
If this intersection is empty, then the algorithm backtracks and picks another value for F (i -1), from the set of possible values. Otherwise, F (i) is set to the smallest element in the intersection and the algorithm continues by searching for possible values for F (i + 1). At this point, it has to be noticed that F (0) can take any given value. However, we explain now a pruning observation that prevents the algorithm from trying all possible 2 n values for F (0) and all possible values for F (1).

Pruning. We can reduce the search space of the algorithm by pruning some branches. The procedure starts, without restriction, by the determination of the images of 0 and 1. We explain now why it is possible to fix those two values and still recover all the other functions for different values of these images.

First, recall that a function F (x) and F (x) ⊕ d, for any d ∈ F n 2 , have the same DDT. This implies that there are at least 2 n functions having a certain DDT for any image of 0. We can therefore fix the image of 0 to any particular value, and query the algorithm for functions having this first defined point. All the other functions will then be recovered by translation.

Second, for a defined image of 0, it is not necessary to ask the algorithm to look for every possible image of 1. Indeed, the functions F (x) and F (x ⊕ c) ⊕ F (0) ⊕ F (c), for any c ∈ F n 2 , have the same DDT. This means that, once F (0) has been fixed, there are as many solutions for any value of F (1) as long as F (0) ⊕ F (1) ∈ R 1 . Moreover, remark that there is an even number of functions having the same DDT and the same images in 0 and 1: the functions F (x) and F (x ⊕ 1) ⊕ F (0) ⊕ F (1) are equal in 0 and 1.

One Example. Before giving the pseudo-code of the algorithm, we show a small example of its execution for the 2 3 × 2 3 table shown in Figure 1, which corresponds to the DDT of the PRINTcipher Sbox [KLPR10].

Here are the main steps performed by the algorithm (also see Figure 2):

1. Set F (0) = 0 2. Set F (1) = 1, as 1 is the minimal value of the set R 1 = {1, 3, 5, 7}

As

F (2) ⊕ F (0) ∈ R 2 = {2, 3, 6, 7} and F (2) ⊕ F (1) ∈ R 3 = {1, 2, 5, 6}, F (2) ∈ {2, 3, 6, 7} ∩ {0, 3, 4, 7} = {3, 7}. Set F (2) = 3. 4. As F (3) ⊕ F (0) ∈ R 3 = {1, 2, 5, 6}, F (3) ⊕ F (1) ∈ R 2 = {2, 3, 6, 7} and F (3) ⊕ F (2) ∈ R 1 = {1, 3, 5, 7}, F (3) ∈ {1, 2, 5, 6} ∩ {2, 3, 6, 7} ∩ {0, 2, 4, 6} = {2, 6}. Set F (3) = 2. 5. As F (4) ⊕ F (0) ∈ R 4 = {4, 5, 6, 7}, F (4) ⊕ F (1) ∈ R 5 = {1, 3, 4, 6}, F (4) ⊕ F (2) ∈ R 6 = {2, 3, 4, 5} and F (4) ⊕ F (3) ∈ R 7 = {1, 2, 4, 7}, F (4) ∈ {4, 5, 6, 7} ∩ {0, 2, 5, 7} ∩ {0, 1, 6, 7} ∩ {0, 3, 5, 6} = ∅.

Go back to

Step 4 and set F (3) = 6. Compute now any possible values for F (4) by repeating Step 5, with F (3) = 6. 7. . . . 8. Once F (7) has been fixed, we verify that γ F is equal to the indicator of D and add it to a list of solutions. We then backtrack to find the other solutions.

The two solutions found with the restrictions F (0) = 0 and F (1) = 1 are F = (0, 1, 3, 6, 7, 4, 5, 2) and F = (0, 1, 7, 2, 5, 6, 3, 4) as it can be seen in Figure 2. All the γ-equivalent functions can be found by computing F (x ⊕ c) ⊕ d and F (x ⊕ c) ⊕ d for all c, d ∈ F 3 2 . At the end, we obtain 2 6 γ-equivalent functions.

Algorithm. In the algorithm, we take the pruning observation into account and only look for functions such that the image of 0 is 0 and the image of 1 is the first possible value. From now on, we denote by S a table of dimension 2 n used to store the intermediate possible images. Then, we denote by F a solution returned by the algorithm, obtained when all the cells of S have been set. Hence, at the beginning, S[0] is set to 0 and S[1] is set to min{R 1 }. The recursive Algorithm 2 is then called for i = 2, where i means that the algorithm is searching for candidate values for S[i]. It starts by computing the possible values for S[i] on Line 2 and store them in a set L. If this set is not empty, the algorithm tries to compute the next value, S[i + 1], for every possible value of S[i]. The procedure is repeated until either S[2 n -1] has been set or L is empty. In the latter case, the algorithm backtracks to the next possible value in L at a certain Level i as there was no solution in this branch. In the former case, all the values for S have been set. At this point, we verify (Line 4) whether the function found has the same γ indicator as the table D (resp. it has D as a DDT). Indeed, it is possible that the support of γ S is strictly included in the one of the indicator of D.

Algorithm 1 Main

Input: A table D of size 2 n × 2 n Output: A list F of all functions F : F n 2 → F n 2 γ-equivalent to the indicator of D 1: F ← {∅}
Globaly defined 2: S ← [0, min{R1}, 0, . . . , 0] len(S) = 2 n 3: RecursifSearch(S, 2) 4: return F

Experimental Results

One of the questions we are interested in is the existence of two DDT-equivalent permutations F and G, which are not related by G(x) = F (x ⊕ c) ⊕ d for some c, d. It is worth noticing that, in the case of non-bijective mappings, such pairs of functions exist. For instance, in [Gor16], 2 2n+n/2 quadratic functions have been exhibited, which are γ-equivalent (and thus DDT-equivalent) to the Gold function x 2 n/2+1 +1 over F 2 n when n is a multiple of 4.

Results for some Known Functions

Using the algorithm described in the previous section, we have been able to compute the γ-equivalence classes and the DDT-equivalence classes of some cryptographically relevant functions. It is clear from Theorem 1, that it is sufficient to run the algorithm for a single representative in each CCZ-equivalence class.

Known APN Permutations for n ≤ 9. After computation, we can affirm that the size of the DDT-equivalence classes of all known APN permutations over F n 2 , with n ≤ 9, is 2 2n . This equivalently means that each DDT-equivalence class is trivial.

Algorithm 2 RecursifSearch

Input: A table S of size 2 n , an integer i 1: if i < 2 n then 2: L ← 0≤k<i {x ⊕ S[k] : x ∈ R k } 3: else 4: if γS = γD then
Or DDT(S) = D if we test the DDT-equivalence 5:

Append S to F 6:

return 7: if L = ∅ then 8:
for all x ∈ L do 9:

S[i] ← x 10:
RecursifSearch(S, i + 1) 11: else 12: return More precisely, for n ≤ 9, the known classes of APN permutations can be defined, up to CCZ equivalence, by the following representatives:

for n = 3: the Gold permutation, for n = 5: the three CCZ-classes described by Brinkmann and Leander in [BL08, Table 3], for n = 6: the so-called Dillon permutation [BDMW10], for n ∈ {7, 9}: the power permutations given in [BDKM09, Table 1].

For n ≤ 8, all known quadratic APN functions have been studied by Gorodilova (see Table 4 in [Gor16]). Here, we also checked that the DDT-equivalence classes of all known APN permutations of degree strictly higher than two are trivial. It is worth noticing that all known APN permutations in dimension 6 are CCZ-equivalent to a quadratic function [BDMW10]. The fact that the corresponding DDT-equivalent class is trivial is then directly deduced from Theorem 1 and [Gor16].

APN Functions for n ≤ 8. We also carried out some experiments for nonbijective APN functions. For instance, we can easily compute the sizes of the DDTequivalence classes of all APN functions of 6 variables of degree at most 3. Indeed, there exist 21 CCZ-equivalence classes of APN functions of 6 variables of degree at most 3 [Lan09] but all these classes contain a quadratic function, except the class discovered independently by [EP09] and by [BL08]. Since Gorodilova has computed the sizes of the DDT-equivalence classes for all quadratic APN functions in six variables, we only need to consider the single remaining class, named Class 13 in [BL08, Table 5]. We have computed the DDT-equivalence class of this function and seen that it is trivial.

Furthermore, we have computed the sizes of the DDT-equivalence classes for all APN functions of 7 and 8 variables given in [BDKM09]. We found that all of the given functions in dimension 7 have trivial classes, while in dimension 8 only the function x 9 has a not trivial class containing 2 20 functions as proved in [Gor16,Theorem 1].

Optimal Sboxes for n = 4. We have also examined all permutations of dimension n = 4 with optimal differential uniformity (equal to 4) and optimal nonlinearity from the 16 different affine-equivalence classes given in [LP07]. The γ-equivalence class for each of them contains exactly 2 8 elements. Since none of these functions has a linear structure, we deduce from Proposition 2 that these 2 8 elements also form their DDT-equivalence class.

As we have seen, none of the permutations with the lowest possible differential uniformity in dimension n < 6 has a DDT-equivalence class with size bigger than 2 2n . However, it is possible to construct such permutations when we increase the differential uniformity.

An Example of Non-Trivially DDT-Equivalent Permutations

In this paragraph, we exhibit a permutation F over F 5 2 , such that some elements in its DDT-equivalence class are not of the form F (x ⊕ c) ⊕ d for any c, d ∈ F 5 2 . We consider the table D, composed by 2×2 blocks of the form 16 16 16 16 everywhere on the diagonal except for the first block which is 32 0 0 32 . By running our algorithm on this table, we recovered 56×2 8 permutations having this DDT. Even by considering the fact that the permutations corresponding to this DDT will necessarily have a linear structure, this number is still higher than the number of distinct functions of the form F (x ⊕ c) ⊕ d, which equals 2 2×5-1 as shown in Proposition 2.

In Table 1 are presented two functions F and F whose DDT is D but for which there is no pair (c, d) such that F (x) = F (x ⊕ c) ⊕ d for all x.

x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 F (x) 0 1 2 3 4 5 6 7 8 9 10 11 13 12 15 14 F (x) 0 1 2 3 4 5 6 7 8 9 10 11 13 12 15 14 The common point between all these examples is that they have non-distinct rows in their DDTs. Besides this property, they seem to have very different characteristics: some of them are permutations with a linear structure, while the other ones are non-bijective and APN. Moreover, as previously noticed, the APN permutations seem to not have larger DDT-equivalence classes (at least for small dimensions). These remarks, combined with the computations we have performed using our algorithm, lead us to the statement of the following conjecture.

x
Conjecture 1. The DDT-equivalence class of a permutation F , such that the rows in its DDT are pairwise distinct, only contains permutations of the form F (x ⊕ c) ⊕ d, with c, d ∈ F n 2 (i.e. is trivial).

It is worth noticing that Example 1 shows that the same conjecture does not hold for γ-equivalence.

Hoping to make a step towards the proof of this conjecture, we show in the next section that APN permutations cannot have two equal rows in their DDTs.

A Note on the DDTs of APN Permutations

Since the DDTs having at least two equal rows seem to play an important role, a natural question is the following: Is it possible that this situation occurs for some remarkable families of Sboxes? As a partial answer, we prove in this section that all the rows in the DDT of any APN permutation are distinct.

Let F be an APN permutation of F n 2 . We start by stating two simple remarks. The first remark is due to the fact that F is a permutation while the second one is a result of F being APN.

Remark 1. F (x) ⊕ F (y) = F (x) ⊕ F (z), for x, y, z ∈ F n 2 pairwise distinct.
Indeed, if we suppose that for some pairwise distinct x, y, z ∈ F n 2 , we have that F (x) ⊕ F (y) = F (x) ⊕ F (z), this would imply that F (y) = F (z), which is a contradiction by the fact that F is a permutation.

Remark 2. ∆ a F (x) = ∆ a F (y), for x, y, a ∈ F n 2 with y = {x, x ⊕ a} and a = 0.

Assuming an equality between the left and the right hand-sides of the equation, would imply an equality between two images of ∆ a F not trivially equal, which cannot occur as F is APN.

Theorem 2. Let F be an APN permutation of F n 2 . Then, the rows of the DDT of F are pairwise distinct.

Proof. We prove this result by contradiction. Indeed, suppose that the row of the DDT corresponding to the image set of ∆ a F equals the row corresponding to the image set of ∆ b F , for some a, b ∈ F n 2 \ {0} with a = b. The proof then tries to match the values ∆ a F (x), for x ∈ F n 2 with the values ∆ b F (x), for x ∈ F n 2 and to show that this is impossible to do. For this, we show that it is impossible to create a chain of values x 0 , x 1 , . . . , x 2 n -1 such that

∆ a F (x 0 ) = ∆ b F (x 1 ) ∆ a F (x 1 ) = ∆ b F (x 2 ) . . . ∆ a F (x 2 n -2 ) = ∆ b F (x 2 n -1 ).
We start by proving the following statement by induction.

Let x 0 , . . . , x k-1 ∈ F n 2 such that ∆ a F (x i ) = ∆ b F (x i+1 ) for all 0 ≤ i < k-1. Then, there are at most 2 n -4k possibilities for choosing x k such that ∆ a F (x k-1 ) = ∆ b F (x k ).
More precisely, x k does not take any of the 4k values x i , x i ⊕ a, x i ⊕ b, x i ⊕ a ⊕ b, for i = 0, . . . , k -1.

Basis. Let k = 1. Suppose that ∆ a F (x 0 ) = ∆ b F (x 1 ). Then, the variable x 1 cannot take any of the four values x 0 , x 0 ⊕ a, x 0 ⊕ b and x 0 ⊕ a ⊕ b. Indeed, if we suppose for example that ∆ a F (x 0 ) = ∆ b F (x 0 ), this translates to F (x 0 ) ⊕ F (x 0 ⊕ a) = F (x 0 ) ⊕ F (x 0 ⊕ b) which is impossible by Remark 1. We use Remark 1 to prove in the same way the impossibility of the remaining three values. Therefore, there are at most 2 n -4 possible values for x 1 .

Inductive step. Suppose that for all i < k there are at most 2 n -4i possibilities for choosing x i and that x i cannot take any of the values in the set {x j , x j ⊕ a, x j ⊕ b, x j ⊕ a ⊕ b|0 ≤ j < i}. We show in the following that there are at most 2 n -4k possibilities for choosing x k .

We have that ∆ a (x k-1 ) = ∆ b (x k ). By Remark 1, we get that x k = {x k-1 , x k-1 ⊕ a, x k-1 ⊕ b, x k-1 ⊕ a ⊕ b}. We show now that x k / ∈ {x i , x i ⊕ a, x i ⊕ b, x i ⊕ a ⊕ b | 0 ≤ i ≤ k -2}. Indeed, suppose for example that x k = x i for some 0 ≤ i ≤ k -2. We have that

∆ a F (x i-1 ) = ∆ b F (x i ), ∆ a F (x k-1 ) = ∆ b F (x i ).
By adding these equations, we get that ∆ a F (x i-1 ) = ∆ a F (x k-1 ). By the induction hypothesis, x k-1 = x i-1 and since F is APN we get a contradiction by Remark 2. The other contradictions are obtained in a similar way by the induction hypothesis and Remark 2.

We show now that it is impossible to construct such a sequence x 0 , . . . , x 2 n -1 . Indeed, we can see, that for choosing for example a value for x k for k = 2 n-2 , there are 2 n -4 • 2 n-2 = 0 choices left. Therefore, we conclude that if F is an APN permutation of F n 2 all rows of the DDT must be pairwise distinct.

Note however that the above result does not hold if one of the two conditions is not met, i.e. if F is not APN or if it is not bijective. Indeed, the two functions of Table 1 are both bijective but have equal rows in their DDT. On the other hand, Function 12 in Table 5 in [BL08] is an APN function of 6 variables whose DDT has some identical rows. Actually, this property holds for any APN quadratic function of an even number of variables.

Conclusion

In this paper, we investigated two different notions of differential equivalence, the DDT-equivalence and the γ-equivalence, and provided an algorithm to compute both equivalence classes for a given vectorial Boolean function. We plan to incorporate this algorithm into the recent C++ library dedicated to the study of equivalence of Boolean functions [FJ18]. During our experiments, we encountered permutations over F n 2 whose differential equivalence class contains more than 2 2n elements. We conjectured in this paper that functions having a non-trivial DDT-equivalence class may relate to the number of distinct rows in their DDT. Furthermore, some other questions about the size of the DDT-equivalence and the γ-equivalence classes naturally arose during this work. For example, we were not able to find an example of an APN function in an odd number of variables having a non-trivial γ-equivalence class. The question is then if such APN functions exist. Another question is whether there exist differentially 4-uniform permutations whose DDT-equivalence class is different from its γ-equivalence class. We have found examples of differentially 4-uniform non-bijective functions for which the two associated classes are different, but in the bijective case, for all the tested functions, the two notions coincide. Finally, an interesting future direction would be to study the differential equivalence classes, and in particular the sizes, of functions either in higher dimensions and/or without any particular structure.

  00 . . . 0) = δ(a, 10 . . . 0) = 2 n-1 and δ(a, b) = 0, ∀b ∈ {0 . . . 0, 10 . . . 0} δ(0 . . . 0, 0 . . . 0) = 2 n and δ(0 . . . 0, b) = 0 for all nonzero b .

Figure 2 :

 2 Figure 2: Example of the algorithm's execution on the table of Figure 1.

  Difference distribution table of dimension 2 3 × 2 3 corresponding to the PRINTcipher Sbox.

	∆out
	0 1 2 3 4 5 6 7
	0 8 . . . . . . .
	1 . 2 . 2 . 2 . 2
	2 . . 2 2 . . 2 2
	∆in 3 . 2 2 . . 2 2 .
	4 . . . . 2 2 2 2
	5 . 2 . 2 2 . 2 .
	6 . . 2 2 2 2 . .
	7 . 2 2 . 2 . . 2
	Figure 1:

Table 1 :

 1 Two non-trivially DDT-equivalent permutations.4.3 A Conjecture on the Size of DDT-Equivalence ClassesSeveral examples of functions having a non-trivial DDT-equivalence class are now known. They include some non-bijective APN functions in even dimension, namely the Gold functions for n ≡ 0 mod 4[Gor16] and a quadratic APN function in six variables(Number 12 in Table 5 in [BL08]), and the examples exhibited in this paper.

	16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
	F (x) 16 17 19 18 20 21 23 22 25 24 26 27 28 29 31 30
	F (x) 16 17 19 18 21 20 22 23 24 25 27 26 28 29 31 30


Pierre-Olivier Brissaud

Jérôme Franc

Isabelle Chrisment

Thibault Cholez

Olivier Bettan

Passive Monitoring of HTTPS Service Use

HTTPS is used today to secure the majority of web communications and so enhance user privacy. Therefore, traffic monitoring techniques must evolve to remain useful, especially to support security considerations, as for example detecting and filtering the forbidden uses of a web service. However, privacy should remain as intact as possible. This paper describes a new passive and transparent method to infer the use of a HTTPS service by extracting and interpreting only meaningful metadata derived from the encrypted traffic without deeply profile individual users. We propose a model using the sizes of objects loaded in the HTTPS service as a signature, by leveraging kernel density estimation, supporting then a classification function. We assess this approach extensively on the Google Images Service although our approach remains valid for some other services. We succeed to achieve an accuracy of 99.18% when detecting particular keywords to be searched over a large dataset of 115,500 distinct keywords.

I. INTRODUCTION

According to the report of the Electronic Frontier Foundation [7], half of the Internet traffic was protected by HTTPS in February 2017. Although defending and improving user privacy are highly important, monitoring, detecting and mitigating bad behaviors are also legitimate, such as tracking illegal activities undergone through the Internet or inappropriate activities in an enterprise network. However, both of these goals are quite antagonist. Usual monitoring techniques based on simple filtering rules such as port-based or deep packet inspection have become obsolete given the generalization of encrypted web applications.

To keep an accurate view of a traffic within an enterprise network, decryption proxies are usually deployed but they totally break user privacy by being able to decrypt any single HTTPS web page. Actually, the initial objective of monitoring bad behaviors is not to track every request of any user but rather to raise an alert or block users' traffic when they do not respect pre-established rules. We thus provide a solution to allow detecting an inappropriate use of a service (based on static pre-established rules) without revealing the full activity of the users, and without entirely denying access to this service, to assure a good trade-off between security and privacy.

The solution presented in this paper is (1) passive as it only collects encrypted HTTP (HTTPS) traffic, and (2) totally transparent as no specific software is supposed to be installed at the user side. The only pre-requisite is a learning phase to derive signatures based on a specific rule set. More specifically, the particular use of a service leads to the loading of different objects in an HTTPS (HTTP/1.1+TLS) page which exhibit different observable characteristics that can be used to build a signature. In that sense, our approach is complementary to website fingerprinting and service or traffic classification methods. In this paper, we demonstrate the feasibility of such a monitoring scheme on different services and conduct an evaluation on Google Images. While traffic classification techniques can identify automatically web and HTTPS traffic, website fingerprinting will reveal that the Google Images service is in use. With our in-depth technique we are able to detect a forbidden use of this service, e.g. inappropriate searched contents.

The paper is organized as follows. Section II presents related work. Our problem and model are defined in Section III. Section IV gives an overview of the design of the solution and Section V and VI explain the data collection process and the evaluation respectively. Finally, Section VII discusses the results and Section VIII concludes the paper.

II. RELATED WORK

Previous studies have shown that privacy is not guaranteed by encryption especially with HTTPS. In 1996, Wagner et al. [START_REF] Wagner | Analysis of the ssl 3.0 protocol[END_REF] highlighted the vulnerabilities of the SSL protocol against traffic analysis. Then, Cheng et al. [START_REF] Cheng | Traffic analysis of ssl encrypted web browsing[END_REF] followed by Sun et al. [START_REF] Sun | Statistical identification of encrypted web browsing traffic[END_REF] and Hintz [START_REF] Hintz | Fingerprinting websites using traffic analysis[END_REF] have experimented the feasibility of a website recognition attack using resources' size with closed world assumptions1 . The publications based on Herrmann et al. [START_REF] Herrmann | Website fingerprinting: attacking popular privacy enhancing technologies with the multinomial naïve-bayes classifier[END_REF], like Panchenko et al. [START_REF] Panchenko | Website fingerprinting in onion routing based anonymization networks[END_REF], Cai et al. [START_REF] Cai | Touching from a distance: Website fingerprinting attacks and defenses[END_REF], Wang et al. [START_REF] Wang | Improved website fingerprinting on tor[END_REF] [23] and Hayes and Danezis [START_REF] Hayes | k-fingerprinting: A robust scalable website fingerprinting technique[END_REF] have extended website fingerprinting over anonymization browsers such as TOR [START_REF]Tor project[END_REF] or JAP [2]. They have applied different clustering methods and features, mostly based on packet size distributions, for their fingerprints. Website fingerprinting techniques tend to identify various pages from different websites whereas our goal is to profile users' activities on a single website, i.e. knowing what keywords have been typed, and so, what specific information has been searched.

Analysis of encrypted traffic can be related to different levels as traffic flow classification, service identification or specific application/protocol behavior detection. The first level aims to detect the type of the different flows in the encrypted traffic as surveyed by Velan et al. [START_REF] Velan | A survey of methods for encrypted traffic classification and analysis[END_REF]. At a higher level we quote Shbair et al. [START_REF] Shbair | A multi-level framework to identify https services[END_REF] with his framework for service detection over HTTPS. The last level targets specific applications or protocols and detects known behaviors, for example identifying video stream on Netflix by Reed and Kranch [START_REF] Reed | Identifying https-protected netflix videos in realtime[END_REF] or VoIP on Skype for language or expression detection by Wright et al. [25] [26]. Those works are built on a precise understanding of the encoding techniques for the video or the audio stream and their aftereffects in the encrypted domain. In [START_REF] Coull | Traffic analysis of encrypted messaging services: Apple imessage and beyond[END_REF], Coull and Dyer were able to determine the language used in discussions on the IMessage instant text messaging application. They have sorted the type of messages and, based on the text message length, have defined a signature for each language. Song, Wagner and Tian [START_REF] Song | Timing analysis of keystrokes and timing attacks on ssh[END_REF] have used timing attacks for detecting ssh input and manage to find login password. Finally, IOACTIVE LABS [START_REF]Traffic analysis on google maps with gmaps-trafficker[END_REF] have detected the location displayed to the client on Google Maps based on a meticulous learning of the size of satellite images and their contiguity. To identify images on Google Images, we propose a similar technique, based on images' sizes and their sequence. However, our method is more general, is robust to small size variations, achieves a direct classification for each loaded page and does not suppose any relationship between consecutive loaded pages.

III. MODELING IMAGES SEARCHES

A. Problem definition

Many web services as image search engines, online market or social network offer research fields which return pages with many HTTP objects and specifically images. As the images are highly related to the searched keyword, they can be considered as a signature for the keyword, contrary to other web objects (css, etc.) that are used across pages. Thereafter, the encryption should prevent to recognize the keywords and the images if we observe the network traffic. However we demonstrate in this paper that metadata retrieved from an HTTPS connection can lead to detect information on such services.

Considering the previously cited services, they can be used to look after illegal or inappropriate content in a company network. We want to give the network administrator a tool to detect the access to some content without blocking the full service nor being able to discover any other activity that is not explicitly monitored, to respect privacy.

We assume the administrator can thus intercept network traffic and has set a precise keywords2 list he wants to monitor for each service (the monitored keywords).

When a user requests specific keywords from an image search engine, traffic is generated between the web browser (client) and the server. At this stage, objects and associated metadata are sent to the user. The objective is to know if the traffic generated by the user's request matches some traces produced by a monitored keyword, and possibly to determine this specific keyword.

Assuming L a traffic flow dataset for the learning purpose and M the monitored keyword set, every single element l ∈ L is a traffic flow corresponding to a single keyword w ∈ M and defined as a sequence of packets p i : ∀l ∈ L, ∃w ∈ M : l = w, {p 1 , . . . , p i , . . . , p n }

(1)

The aggregation criterion and technique are defined in Section IV. Based on that knowledge, our model is built as a function f which takes a new sequence of packets p related to a keyword w as input and deduces whether it has been generated or not by a monitored keyword w. If w ∈ M , the function f should recognize p as being in L and return a specific keyword w ∈ M . If not, the function returns u (i.e. unknown keyword):

∀p = {p 1 , . . . , p i , . . . , p n }, f (p) = w ∈ M u (2)
The problem thus resides in defining f from the learning datasets, i.e. all l ∈ L and the associated keyword w ∈ M .

B. Rationale

In most popular image search engines, several thumbnails are returned for a single keyword. The number of thumbnails is not constant from a keyword research to another, but there are several dozens for each request. Each thumbnail is generated from a single image. Due to image compression techniques with formats like jpeg, the size (in bytes) of images is highly variable and independent of the rendered size (in pixels). As a result, the encrypted size of the thumbnails can vary from one image to another. A keyword is thus associated with numerous encrypted image sizes whose range values span over thousands of bytes. Having two keywords sharing the same set of thumbnails sizes is highly improbable as it is a high combinatorial problem.

C. Refined model

Although in this paper, we study an image search service, the method can be easily transposed to web service which loads numerous and various objects, which can be representative of a particular behavior (e.g. searches).

Like the image search service, the content of any web-based application page reflects the service use with various objects loaded depending on the user actions and requests. Therefore, the signatures of a service use can be expressed through some observable characteristics of the objects with some of them being observable even with encryption, especially the size. Indeed, the encrypted size of an object highly depends on its original size. Thus, we refined our model based on Equation (2), with s i the size of each object from a trace3 , as follows:

∀l ∈ L, ∃w ∈ M : l = w, {s 1 , . . . , s i , . . . , s n } ∀s ={s 1 , . . . , s i , . . . , s n }, f (s) = w ∈ M u (3)
Actually images are present in many web pages. For example we can mention online shopping website where products are usually represented by image thumbnails as well or social networks where images are also widely used to illustrate text content and thus images are related with the original request. This is why we select images as significant objects to use for signature construction. Using all objects without distinction would have been possible but introducing some noises due to very generic objects being loaded.

IV. METHODOLOGY

A. Overview

As highlighted in Figure 1, a learning phase is required for the administrator to be able to monitor the user traffic. A database of signatures related to the keywords of the monitored list M is built by the learning module. The list M is provided by the administrator (1), the crawler then requests each keyword, a given determined number of times, on the image search engine (2) while the traffic is captured (2'). A profile from all the traces related to a keyword (details in Section IV-B) is then derived by the signature generator.

When real users access the search engine (a), the traffic (a') is captured and the part related to the image search engine is extracted. The data are then sent to the classifier (b) which is in charge of determining if a match exists with a signature from the database built during the learning stage (details in Section IV-C). Then, the results of the classification engine can be used to raise alerts to the administrator or blacklist a user with bad behaviors (inappropriate searches).

B. Signature generation

As discussed in Section III-B the thumbnail sizes are discriminative of a searched keyword. However, the HTTPS answer containing the thumbnails also includes the HTTP response header. This introduces some noise as the size of the encrypted answer varies (in a scale of few bytes), for the same keyword request. Hence, relying on exact sizes is irrelevant. Thus, the designed method has to catch the variable sizes of the thumbnails and learn automatically this variation when multiple samples are collected.

In this paper, we leverage the Kernel Density Estimation (KDE) technique [START_REF] Parzen | On estimation of a probability density function and mode[END_REF] to support our method. Assuming a distribution for the thumbnail sizes of a keyword, KDE estimates the density function. Unlike Gaussian mixture models, KDE is non-parametric in the sense that it does not assume any specific type of underlying probability functions. Hence, the derived density function represents a signature of a keyword and any set of thumbnail sizes can be tested against to verify whether it matches. Let X = (x 1 , ..., x n ) be a random distribution, K a kernel function and h the bandwidth parameter of the kernel, the density function is estimated as follows:

R → [0, 1] y → 1 nh n i=1 K( y-xi h ) (4)
The bandwidth parameter sets the span of the smoothing of the density function around the provided sample points. The In our context, a distribution is composed of all the n thumbnails sizes s i for a searched keyword k. As we have no prior assumption on data, we use an uniform kernel function defined in Equation ( 5):

K(y) = 1 2 if | y |≤ 1 else 0 (5)
Assuming Equations ( 4) and ( 5), the signature function noted σ w is thus defined regarding the distribution of encrypted object sizes (i.e. the encrypted thumbnails sizes: s i ):

σ w (y) = 1 nh n i=1 ( 1 2 if | y -s i |≤ h else 0) (6)
Our database of signatures D is thus composed of all estimated density functions: D = {σ w , w ∈ M }

C. Classification engine

According to Equation (3), the classifier processes a list of object sizes and should return a searched keyword w from the list M or u (for "unknown") in case the keyword was not in the monitored keyword list. The whole process is split into three parts: the thumbnails size extraction, the signature scoring and the result filtering.

Considering HTTPS full packet capture pcap traces of a single requested keyword (the dataset collection is explained in Section V), extracting an HTTP object size requires first to delimit the latter in the encrypted payload. As no pipelining is available by default on modern web browser with HTTP/1.1 version [1], we know that between two client requests, using the same connection, there are only packets corresponding to the HTTP response (header + payload) of the server [14], hence only containing a single HTTP object.

Therefore, by analyzing the TCP and TLS headers, a list of sizes for all the encrypted HTTP requests and the corresponding encrypted HTTP response sizes can be built. Because we observe peaks on the requests sizes distribution corresponding to the thumbnail request, we filter the objects sizes to keep only the objects related with thumbnails, that are the most relevant as they are representative of the searched keyword.

Thus, we can generate the list of all thumbnails sizes 4 for the trace subsequent to a keyword query. This list is denoted as s = {s 1 , . . . , s i , . . . , s n }. Actually, such analysis has to be done for each monitored service.

The scoring consists in computing a single score for each signature (density function) of the database D. For each σ w ∈ D, the score is calculated by evaluating the fitness of each size s i to the function σ w and summing over all results :

sc w (s) = n i=1 σ w (s i ) (7)
A naive classifier would select the keyword associated with the maximum score. However, the classifier may decide that a keyword is unknown as highlighted by u in the classification function in Equation ( 3). The main issue is that there is naturally no signature for u and so a maximum score could not be calculated for an unknown keyword. Actually, the classification engine avoids as much as possible missclassification and prefers to raise an unknown value if our confidence of the maximal score is too low. To assess the latter, an outlier detection approach is used to check whether this score is much higher than other ones. Assuming the full list of calculated scores L s , for a given capture, s, of image sizes, the highest score is considered as relevant only if it reaches a threshold calculated from the mean, mean(L s ), and the standard deviation, std(L s ):

f (s) = arg max w∈M scw(s), scw(s) > mean(Ls) + α × std(Ls) u otherwise (8)
The filtering parameter α multiplied by the standard deviation defines the minimum deviation from the mean. The impact of this parameter is evaluated in Section VI.

V. DATASET COLLECTION

A. Capturing traces from the Google Images Search Engine

To evaluate our method, we applied it to Google Images. For validation purposes, all traces are collected by our own crawler providing both traces for training and testing in the following conditions:

• Client web-browser: Firefox 54.0.1 (64-bit) on debian 8, • Firefox settings: full screen display with a resolution of 1920×1080 without cache support and HTTP/2 disabled to force HTTP/1.1 (TLS version 1.2), • English version of Google Images (google.com 5 ). Our crawler opens a page at a specific URL and collects the traffic. The packets captured during the page loading of each searched keyword are stored in a pcap file, from which the request and response sizes are extracted for all the loaded objects. 4 for the rest of the paper we note the thumbnail or image size refer to the encrypted HTTP response size related to the thumbnail 5 we used https://www.google.com/ncr for disabling regional redirection

B. Dataset constitution based on keywords lists

Our evaluation assumes an open-world situation, i.e. the objective is to determine whether a new trace is significantly representative of a monitored keyword (in M ) or not. Some of these new testing traces thus correspond to the monitored keywords (∈ M ) while others represent unknown user searches ( ∈ M ). A first set of experiments is exclusively based on a restricted dataset data 1 of 10,500 keywords from the English Oxford dictionary and allows us to assess our technique and its parameters in various conditions. A second dataset, made from a larger scale experiment, extends the first one with 105,000 other words/expressions from Wikipedia pages titles [START_REF]Wikipedia's article list[END_REF] composing data 2 .

Five traces of each keyword are automatically captured for data 1 , four are reserved for training, i.e. to build meaningful signatures, and one for validation purposes since testing is based on individual traces. data 2 traces are only used to verify whether our signatures are robust against new unknown keywords. That is why there is only one trace per each keyword in dataset data 2 as training does not use it. All the traffic has been captured during June and July 2017. More detailed information is summarized in Table I. To support reproducible research, a sample of the dataset and a description are available at http://betternet.lhs.inria.fr/ datasets/googleimg/, the full dataset is available on demand.

VI. EVALUATION

A. Classification metrics

Based on Equation (2), a trace p i with its real label l i ∈ {L ∪ {u}} is related to a predicted label f (p i ). Thus we consider f (p i ) as a:

TP (True Positive) if l i = u and l i = f (p i ), this is the case where the trace p i corresponds to a monitored keyword from list M and is properly classified accordingly, FP (False Positive) if l i = u and u = f (p i ), which means that the trace does not correspond to a monitored keyword but is wrongly classified by our system, WC (Wrong Classification) if l i = u and l i = f (p i ), the trace p i which is associated with a keyword in M has been properly detected as part of M but the predicted keyword by our system is wrong. Hence, the goal is to evaluate if our method is able to check whether a trace is related to any keyword from M. We make the distinction between TP and WC because our technique can be tested with two different granularities: with the ability to detect a monitored keyword in the search without distinction among keywords (T P + W C) and its ability to exactly identify which keyword has been used (only T P ). In In this section, we measure the impact of the different parameters: the bandwidth (h), filtering threshold (α) and the number of monitored keywords (|M |) based on extensive experiments. Hence, we use only the small-scale dataset of data 1 . The objective is to help in configuring our technique and also define the proper parameters for the large-scale experiment presented in the next section. In order to determine the effects of the KDE bandwidth parameter, the classifier was trained with 1/10 (1,050) of the keywords and then tested with one trace of all keywords [START_REF] Coull | Traffic analysis of encrypted messaging services: Apple imessage and beyond[END_REF]500). This experiment was reproduced three times, each time with a different non-overlapping training keywords set. Average value for the true and false positive rates are shown in Figure 2 where the filtering threshold α varies to draw a single ROC (Receiver Operating Characteristic curve) curve. When the chosen bandwidth (h) increases, the classifier performance is better, with 16 appearing as the best choice (less than 0.2% of false positives with more than 96.8% of true positives) but close to h = 4. One exception is for h = 9. In that case, a minor performance degradation is shown.

In details, the detection capacity increases from 1 to 4 then between 5 and 16 it first decreases then increases again to reach the most efficient value 16. For the bandwidth values greater than 16 the TPR decreases as the bandwidth increases. These variations are related to the variable encrypted size of each thumbnail, i.e. for a same thumbnail, the size can vary of few bytes, which indeed motivates the use of KDE. We experimentally deduce that the variation for the encrypted size is mostly contained in a range of +/-4 bytes around a central value and few are in a range of +/-16 bytes. Secondly, we focus on the filtering threshold (α). Two ROC curves of Figure 2 are selected: with the two different values for the bandwidth h = 16 and h = 70. They are shown apart in Figure 3 with details regarding the value of the filtering threshold which varies. The higher the filtering threshold is, the lower the TPR and FPR. Logically, the filter dismisses more traces when the threshold increases. It is worth mentioning that the threshold values for the best efficiency depend on the bandwidth because it has a direct impact on the mean score computed for the filtering operation (the density function is smoother when the bandwidth increases).

The last scenario assesses the impact of the number of elements in the list M of monitored keywords. We trained our classifier with 100, 500, 1,000 or 2,000 monitored keywords and use 8,000 unknown keywords for the tests. The bandwidth parameter was set to 16 based on the previous experiment and each experiment was done 3 times with different selected sets of training keywords. Figure 4 highlights that the efficiency of our classifier is inversely proportional to the length of M . Actually, more collisions among keywords can appear when the number of latter increases, and so slightly decreases the efficiency of our technique.

Table II summarizes the impact of the bandwidth and filtering threshold parameters on all classification metrics. The WCR almost always equals to 0 except for small filtering thresholds. Hence, when a trace is actually classified, as being part of the monitored keywords list, our technique has a Fig. 4: Detailed values of α (reported on curves) for selected bandwidth parameters (h) (small dataset)

C. Large-scale experiment

Figure 5 reports the experiment of the previous section where 10% of the keyword of data 1 are selected to be monitored. Then, we add either unknown keyword for testing or new keywords for learning. By adding traces from non monitored keyword (data 2 ) to be tested (105,000 in total) but still keeping 1050 keywords to be monitored, this proportion is then decreased. As a result (curve 1050/105000), no major difference can be observed, so the signatures remain valid. An update of the signature database is actually necessary when the blacklist M is updated (new keywords added) or for trending keywords which results may change in time.

However, when the amount of monitored keywords increases, in our case with 10,500 keywords (curve 10500/105000), a degradation of the classification performance is shown due to more collisions between signatures. Because the similarities between signatures from different keywords is very low, the degradation is highly limited. Figure 5 shows that the number of TPs is decreased by around 2%. Meantime, the number of FPs is lightly increased by 0.5%. Actually, as reported in Table III, the maximum accuracy is 0.9918 with T P R = 0.966 and F P R = 0.0056. It is obtained with the same parameter configuration as the experiment with the small dataset in the previous section.

VII. DISCUSSION

The stability and the robustness of the signatures are out of the scope of this paper but we share here some observations. The thumbnails returned by Google Images can evolve over the time and mostly for keywords related with trending topics. It is possible to continuously generate and capture traffic to update signatures. While many web services rely on user profiles Fig. 5: Roc curve: test on monitored and unknown list length (small/large dataset) (using cookies for example) to personalize services, we did not observe any evidence that returned thumbnails may be related to the user history, but only to some request options.

The solution is based on the possibility to extract HTTP object sizes and correlate them with their request size. HTTP/ 2 is therefore challenging because of multiplexing. Indeed, reassembling the packets related to the same response appears no more possible. As a result, the use of the HTTP/2 protocol would prevent the proposed method of this paper. Actually (05/30/2018) 26% of websites have been reported to have migrated to HTTP/2 based on a w3techs report [START_REF]W3techs report[END_REF] and HTTP/ 1.1 is still today the most widely used HTTP protocol. Furthermore, our technique aims to support the network management, especially monitoring, in an enterprise environment where the administrator may impose the use of a particular version of the protocol in the web browser configuration.

VIII. CONCLUSION

This paper presented a method to monitor the use of HTTPS services of interest in the context of an enterprise network where security policies must be enforced. Our method relies on the size of traffic generated by individual objects loaded on the web page to build highly discriminative signatures based on KDE. The solution is passive, transparent, as no decryption proxy or middlebox acting as a Man-in-the-Middle is required. It can monitor the use of a predefined list of keywords but not more. Those properties make it better for people privacy than current solutions. The paper presents a deep evaluation when applied to the Google Image service. Extensive evaluation was performed based on more than 115,000 real traces. The results show an accuracy higher than 99% with less than 1% of false positives.

In future work, we will focus on testing other methods to evaluate the robustness of HTTP/2 against this kind of fingerprinting.

Fig. 1 :

 1 Fig. 1: Global architecture to track HTTPS application use

  the testing dataset the number of traces related to a monitored or unknown keyword is denoted as |m| and |uk| respectively. Assuming all traces p i , |T P | is the count of TP traces, |F P | the count of FP and |W C| the count of WC. The following relative metrics are thus computed: TPR (True Positive Rate): |T P | |m| FPR (False Positive Rate): |F P | |uk| WCR (Wrong Classification Rate) The probability that a trace related to a monitored keyword is classified as another monitored keyword: |W C| |T P | Acc (Accuracy) The ratio of traces which have been well classified independently of their nature (from a monitored or unknown keyword): |T P |+|uk|-|F P | |m|+|uk| B. Parameters evaluation

Fig. 2 :

 2 Fig. 2: ROC curve: test bandwidth (small dataset)

Fig. 3 :

 3 Fig.3: Impact of h on TPR and FPR assuming a variable threshold α (small dataset)

TABLE I :

 I Dataset origins

	ID	Origin	Number of keywords	Captures per keyword	Average packets number by trace	Average duration by trace
	data1	Dictionary (en)	10,500	5
	data2	Wikipedia (en) titles pages	105,000	1	1,155 pkt/trace	2.94 s/trace

TABLE II

 II

						: Result overview(small dataset: data1): 1,050 monitored keyword / 10,500 unknown
	h α	1	4	TPR	16	50	1	4	FPR	16	50	1	4 Accuracy 16	50	1	4 WCR	16	50
	3.5	0.832	0.983	0.989	0.948	0.0909	0.0788		0.068	0.0602	0.9011	0.9276	0.9379	0.9406	0.015	0.003	0	0
	3.9	0.824	0.977	0.983	0.830	0.0182	0.0123	0.0098	0.0083	0.9654	0.9866	0.9895	0.975		0
	4.1	0.819	0.970	0.968	0.607	0.0026	0.0018		0.001	0.001	0.979	0.9953	0.9959	0.9584		0
	4.25	0.797	0.941	0.868	0.185	0.0002	0			0	0	0.9789	0.9939	0.9863	0.9155		0
	4.35	0.464	0.223	0.007	0	0	0			0	0	0.9445	0.9194	0.897	0.8963		0

TABLE III :

 III Result overview (large dataset: data1 & data2): 10,500 monitored keyword / 105,000 unknown

	h α		1	4	TPR	16	50	1	4	FPR	16	50	1	4 Accuracy 16	50	1	4	WCR	16	50
	3.5	0.820	0.979	0.986	0.927	0.1042	0.0908	0.0811	0.0739	0.8889	0.9207	0.9250	0.9262	0.017	0.001	0.001	0.001
	3.9	0.814	0.973	0.980	0.790	0.0219	0.0201	0.0162	0.013	0.9631	0.9788	0.9834	0.9691	0.004	0	0	0
	4.1	0.805	0.965	0.966	0.557	0.0052	0.0069	0.0056	0.0026	0.9775	0.9884	0.9918	0.9574	0.001	0	0	0
	4.25	0.780	0.932	0.871	0.170	0.0009	0.0038	0.0026	0.0003	0.9792	0.9857	0.9858	0.9242		0
	4.35	0.448	0.253	0.009	0	0	0.0004		0	0	0.9498	0.8762	0.9099	0.9091		0
	high probability to identify the precise keyword which was
	originally queried. In the best case, the accuracy can reach
	more than 99% with T P R = 0.968 and F P R = 0.001 as
	highlighted in bold in Table II.
			1.00					bandwidth : 16
			0.99
			0.98
		True Positive Rate	0.000 0.92 0.93 0.94 0.95 0.96 0.97	0.005		0.010 False Positive Rate 0.015 0.020 Monitored list length 0.025 0.030 100 500 1000 2000

Closed world is opposed to open world as it only considers a finite sample for both the training and testing. The open world assumption involves a finite dataset to monitor and unlimited possibilities for the testing phase.

In the rest of the paper, keyword refers to the user search which is actually a single or a set of keywords

In the rest of the paper, a trace refer to the packet capture, stored in a pcap file, when requesting a keyword till the full page with all objects is loaded