Lucas Barthelemy
email: lbarthelemy@quarkslab.com

Ninon Eyrolles
email: neyrolles@quarkslab.com

Raphaël Roblin
email: raph.roblin@gmail.com

Binary Permutation Polynomial Inversion and Application to Obfuscation Techniques

Keywords:

 presented ways to mix such a tool with permutation polynomials modulo 2 n in order to make the obfuscation technique more resilient to SMT solvers. However, because of limitations regarding the inversion of such permutations, the set of permutation polynomials presented suffers some restrictions. Those restrictions allow several methods of arithmetic simplification, decreasing the effectiveness of the technique at hiding information. In this work, we present general methods for permutation polynomials inversion. These methods allow us to remove some of the restrictions presented in the literature, making simplification attacks less effective. We discuss complexity and limits of these methods, and conclude that not only current simplification attacks may not be as effective as we thought, but they are still many uses of polynomial permutations in obfuscation that are yet to be explored.

INTRODUCTION

Obfuscation techniques often use invertible functions to hide meaningful components of the program, especially in data-flow obfuscation. A common example is the encoding of variables or constants with affine functions [START_REF] Collberg | A Taxonomy of Obfuscating Transformations[END_REF], also used in cryptographic white-box setups [START_REF] Chow | White-Box Cryptography and an AES Implementation[END_REF]. A natural generalization of an affine function is a polynomial and if it is bijective, it is called permutation polynomial.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. SPRO'16, October 28 2016, Vienna, Austria Permutation polynomials are the subject of many research efforts in mathematics [START_REF] Mullen | Permutation polynomials over finite fields[END_REF][START_REF] Mullen | The structure of a group of permutation polynomials[END_REF][START_REF] Wang | On permutation polynomials[END_REF]. The well-studied Dickson polynomials [START_REF] Hong | Necessary conditions for reversed dickson polynomials of the second kind to be permutational[END_REF][START_REF] Qu | Dickson polynomials of the second kind that permute zm[END_REF] provide examples of permutation polynomials. Most of the results on these polynomials assume that their coefficients are in a finite field.

In the cryptographic context, applications of permutation polynomials appeared as a generalization of the RSA cryptosystem or for designing symmetric protocols [START_REF] Lidl | Permutation Polynomials in RSA-Cryptosystems[END_REF][START_REF] Müller | Some remarks on public-key cryptosystems[END_REF][START_REF] Lidl | Permutation polynomials in RSA-cryptosystems[END_REF][START_REF] Gupta | Cryptological applications of permutation polynomials[END_REF]. Only little work focuses on permutation polynomial with coefficients in the ring of integer modulo 2 n [START_REF] Gomez-Calderon | Galois rings and algebraic cryptography[END_REF][START_REF] Ronald | Permutation Polynomials Modulo 2w[END_REF], which represents the main application of such polynomials in the context of software obfuscation. In the context of error correcting code applied to mobile communications, permutation polynomials modulo 2 n appear as a central object to design interleavers [START_REF] Lahtonen | On the degree of the inverse of quadratic permutation polynomial interleavers[END_REF][START_REF] Takeshita | Permutation polynomial interleavers: an algebraic-geometric perspective[END_REF][START_REF] Sun | Interleavers for turbo codes using permutation polynomials over integer rings[END_REF].

To the best of our knowledge, papers related to applications of permutation polynomials modulo 2 n present results on the characterization of such polynomials or study subfamilies for which the inverse polynomial is given thanks to a closed-form formula. This is particularly the case for the paper by Rivest [START_REF] Ronald | Permutation Polynomials Modulo 2w[END_REF] which provides a characterization of all the permutation polynomials modulo 2 n and the one by Zhou et al. [START_REF] Zhou | Information Hiding in Software with Mixed Boolean-Arithmetic Transforms[END_REF] which uses a (strict) subfamily for which a closed-form formula is known for the inverse. Using a subfamily is a problem in the context of obfuscation since such polynomials will have an intrinsic form which can be recognized more easily and thus help the reverser. The attack proposed in [START_REF] Biondi | Effectiveness of Synthesis in Concolic Deobfuscation[END_REF] relies on this property.

Our main objective in this paper is to provide algorithms and implementations for the computation of the inverse of any permutation polynomial modulo 2 n . Thus, obfuscation designer can stop relying on permutation polynomials with specific form (and so easily breakable).

Before presenting our contributions, we recall some theoretical results which will be used in the sequel.

Binary Permutation Polynomials

In the sequel, we will be mainly interested in bijective functions of Z2n = Z/2 n Z the integer ring modulo 2 n . More precisely, we will consider objects as defined in the following: Definition 1. Let A be a finite ring. A map f : A → A is said to be a polynomial function if there exists a polyno-mial P in A[x] such that ∀a ∈ A : f (a) = P (a). If, moreover f is bijective, this function and the polynomial P are said to be a permutation polynomial of A. When A = Z2n we will call them binary permutation polynomial.

In [START_REF] Ronald | Permutation Polynomials Modulo 2w[END_REF] Rivest provides the following result which characterizes binary permutation polynomials.

Theorem 1 ([16]). Let A = Z2n with n ≥ 2 and let P (x) = a0 + a1x + • • • + a d x d be a polynomial with integral coefficients. The polynomial P represents a function f of A which is a binary permutation polynomial if and only if a1 is odd, (a2 + a4 + a6 + . . . ) is even, and (a3 + a5 + a7 + . . . ) is even.

It is worth to note that the function f in the preceding theorem can be represented by many different polynomials. More precisely, we have the following results.

Proposition 1. Let A be a finite ring. The ring F(A) of polynomial functions on A is isomorphic to the quotient ring A[X]/I where I is the polynomial ideal defined by I = {P ∈ A[x] : ∀a ∈ A, P (a) = 0}. In particular, the group P(A) (for the composition) of permutation polynomials of A is a subset of this quotient ring.

In the case where A is a finite field, the structure of F(A) can be identified (since every function is polynomial) [START_REF] Mullen | The structure of a group of permutation polynomials[END_REF], but in the case of a finite ring it is far from easy. When A is a finite ring, there are many papers providing theoretical results on F(A) or P(A) (e.g. structure, isomorphism, cardinality) but only few reports on algorithmic aspects. In the rest of this paper, we will address the problem of efficiently computing a polynomial representing the inverse of a given binary permutation polynomial and consider some applications to obfuscation.

MBA Obfuscation using Binary Permutation Polynomials

In [START_REF] Zhou | Information Hiding in Software with Mixed Boolean-Arithmetic Transforms[END_REF], Zhou et al. present a constant obfuscation based on two components: Mixed Boolean-Arithmetic (MBA) expressions and binary permutation polynomials. They present their own subset of binary permutation polynomials for which they provide a closed-form formula for inversion. For a given degree m > 0, they define the following subset of P(Z2n ):

Pm(Z2n ) = m i=0 aix i | a1 is odd and a 2 i = 0 for i > 1
and prove the following theorem.

Theorem 2 ([22]

). The set Pm(Z2n ) is a permutation group under the functional composition operator •. The inverse of an element f (x) = m i=0 aix i ∈ Pm(Z2n ) is given by g(x) = m j=0 bjx j where each coefficient can be computed by: bm = -a -m-1

1 am, b1 = a -1 -a -1 1 m j=2 ja j-1 0 Aj, b0 = -m j=1 a j 0 bj and b k = -a -k-1 1 -a -1 1 m j=k+1 n r a j-k 0 Aj, m -1 ≥ k ≥ 2
where Am = -a -m 1 am, and A k are recursively defined by

A k = -a -k 1 a k - m j=k+1 j k a j-k 0 Aj, for 2 ≤ k < m.
From this set, Zhou et al. propose an obfuscation technique based on the composition of two binary permutation polynomials P (x) and Q(x) = P -1 (x), and an m-variable MBA identity E = 0 with multiple non-zero terms. For a certain constant K ∈ Z2n , one has K = Q(P (K)) = Q(E + P (K)). Expanding the expression yields an obfuscated expression containing m variables and yet having always K as an output value.

While this work provides an interesting way of using binary permutation polynomials in obfuscation, it presents two drawbacks: firstly, only a small subset of P(Z2n ) is used and secondly, public work describing attacks of this technique [START_REF] Biondi | Effectiveness of Synthesis in Concolic Deobfuscation[END_REF] was recently published.

Attack of MBA Obfuscation

In [START_REF] Biondi | Effectiveness of Synthesis in Concolic Deobfuscation[END_REF], Biondi et al. describe three approaches to attack the MBA-based constant obfuscation: albegraic simplification, SMT solver-based deobfuscation, and synthesis-based deobfuscation. The algebraic simplification method is of first interest for us, since it is strongly based on the form (see Theorem 2) of the set of polynomials defined by Zhou et al. As stated by the authors of the attack, the recovering of both polynomials P and Q is based on the fact that the coefficients of Q(x) = m j=0 bjx j are all even except for b1. It is indeed stressed in [START_REF] Biondi | Effectiveness of Synthesis in Concolic Deobfuscation[END_REF] that, should polynomials from another family that the one of Theorem 2 be used to obfuscate, the reduction attack presented would fail.

In Section 2.3, we present how to compute the inverse of any binary permutation polynomial as characterized by Rivest, thus enlarging the family of potential obfuscating polynomials to be used in the MBA-based obfuscation. More precisely, we present the following contributions.

Contributions

In this paper, we assess the feasability of binary permutation polynomials inversion with two known methods: Lagrange interpolation and Newton's inversion algorithm. We show in Section 2.1 that using a ring extension, it is possible to use Lagrange interpolation in order to compute the inverse of a restrained set of permutation polynomials, namely the one defined by Expression (4) (this set includes the one defined in [START_REF] Zhou | Information Hiding in Software with Mixed Boolean-Arithmetic Transforms[END_REF]). As Lagrange interpolation does not provide a method to inverse all binary permutation polynomials, and has a high complexity due to the fact that it operates on a ring extension, we detail in Section 2.3 how Newton's inversion method can be used in the context of binary permutation polynomials.

Through the use of the zero ideal as mentioned in Proposition 1 and in Section 2.2.1, we define a ring of reduced permutation polynomials, and we adapt Newton's method for compositional inversion on this particular ring. As opposed to the method used in [START_REF] Zhou | Information Hiding in Software with Mixed Boolean-Arithmetic Transforms[END_REF] and Lagrange interpolation, this new method successfully inverts all the binary permutation polynomials. Moreover, the complexity of Newton's method proved to be far better than Lagrange interpolation since computations are made on integer modulo 2 n , and thus the cost of multiplication is far less than the one in the ring extension used during Lagrange interpolation.

Both the zero ideal and the algorithm for permutation polynomial inversion provide new possibilities for obfuscation, as well as for working with polynomials in Z2n . In particular, it offers resilience of the technique presented by Zhou et al. from the algebraic attack in [START_REF] Biondi | Effectiveness of Synthesis in Concolic Deobfuscation[END_REF].

ON INVERTING BINARY PERMUTATION POLYNOMIALS

In this section, we introduce two methods to invert permutation polynomials in Z2n [x]. In contrary to the formula given in [START_REF] Zhou | Information Hiding in Software with Mixed Boolean-Arithmetic Transforms[END_REF] that allows to invert a thin part of all the permutation polynomials, we present two general algorithms that efficiently inverse more permutation polynomials, one of them even inverting all polynomials as characterized by Rivest in [START_REF] Ronald | Permutation Polynomials Modulo 2w[END_REF].

We first introduce an interpolation method and show its limitations, then present a more efficient inversion method based on a modular functional Newton approach. Even if the first method is far more costly in term of performances than the second one, its exposition greatly helps to understand what is the best strategy for inverting permutation polynomials.

Inversion Through Interpolation

In order to identify a polynomial given as a black box, it is usual to proceed by interpolation [START_REF] Zippel | Interpolating polynomials from their values[END_REF][START_REF] Dumas | On newton-raphson iteration for multiplicative inverses modulo prime powers[END_REF]. The main problem here is to find enough sample points. In this section, we present a method allowing this computation in Z2n [x].

Thorough this article, we consider applications Z2n → Z2n which are defined by evaluation of a polynomial f (x). We will use the same notation for the polynomial and the corresponding function. In particular, X will denote the identity application: x X -→ x ∀x ∈ Z2n .

Lagrange Interpolation in a Modular Ring

Let us consider a function ϕ taking as entry an integer in Z2n and supplying the polynomial evaluation of f at this point:

x ϕ -→ f (x)
For each point evaluated, we can predict the result of ϕ -1 without its knowledge:

x ϕ -→ y ⇔ y ϕ -1 ---→ x
Let us assume that ϕ -1 can be defined as the evaluation of an (unknown) polynomial f -1 . If, moreover, the polynomial f is taking values in a finite field and f -1 is of degree dinv, then from dinv + 1 tuples (yi = f (xi), xi) one can find f -1 by computing a Lagrange interpolation:

f -1 (x) = d inv j=0 xj i =j (x -yi) (yj -yi) (1)
In the case of binary permutation polynomials, the Expression (1) is not always computable, as half of the elements in Z2n are zero-divisors. Thus, by considering the determinant of the Vandermonde's matrix

V f of f det(V f ) = 0≤i<j≤d inv (yj -yi) (2)
which is equal to the denominator of Expression (1), the computation of the Lagrange interpolation is possible if and only if det(V f ) is inversible. However, it can be shown that if the yi are in the ring Z2n , then as soon as dinv ≥ 2, the product 0≤i<j≤d inv (yj -yi) is not invertible. Therefore, Lagrange interpolation is not applicable as usual on this particular ring.

Ring Extension

The impossibility to use Lagrange interpolation comes from the fact that there is no invertible combination of three or more elements in Z2n such that the product in Expression ( 2) is invertible. To bypass this problem, the base ring needs to be extended. The approach is similar to field extension, i.e. to extend the base ring Z2n with a new symbolic element ω, which defines the bigger ring Z2n [ω] as the quotient of Z2n [x] by an irreducible polynomial P of degree m to which ω is a root. The resulting ring is Z2n [ω] = Z2n [x]/P and will be noted as Z m 2 n . We will show how such a sufficiently big extension allows Lagrange interpolation in our context. These extensions generally are called Galois rings.

To know if the application of a Lagrange interpolation is possible in such an extension, the progression of the number of invertible elements is of first interest. The following fundamental result from [START_REF] Wan | Lectures on Finite fields and Galois rings[END_REF] gives a formal definition of Galois rings which will help us recognize invertible elements.

Theorem 3. In the Galois ring Z2n [ω], there exists a nonzero element α of multiplicative order 2 m -1 which is a root of a monic basic primitive polynomial h(x) in Z2n [x] of degree m and dividing x 2 m -1 -1. The element α verifies that

Z2n [α] = {a0 + a1α + • • • + am-1α m-1 : a0, a1, . . . , am-1 ∈ Z2n } is isomorphic to Z2n [ω].
This theorem states that any Galois ring extension can be defined by an element α which is primitive. This means that any element of the extension can be written with powers of α as explained in the following Theorem.

e = a0 + a1 × 2 + • • • + an-1 × 2 n-1
where a0, a1, . . . , an-1 ∈ T . Moreover, e is invertible if and only if a0 = 0. This representation is called 2-adic representation. If we take a look at this representation modulo 2, we have:

e = a0 mod 2
Therefore, in order to have a0 = 0, we need e = 0 mod 2. When e is represented as a polynomial in ω, to achieve such a condition, e needs to have at least one odd coefficient (since all even coefficients become null modulo 2). Thus we can characterize the invertible elements of Z m 2 n as elements with at least one odd coefficient, while elements with only even coefficients are zero-divisors.

In order to compute Lagrange interpolation, we need dinv + 1 elements yi such that the product

0≤i<j≤d inv (yj -yi) (3)
is invertible.

In order to obtain a set of elements such that the product of their difference is invertible (as in Expression (3)), for any couple of elements within that set, there must be at least one degree on which their coefficients have different parity (so that the difference between those two coefficients is odd). Note that the value of said coefficients is not important, only their parity. Thus, let us consider the elements of Z m 2 n with coefficients in {0, 1}. The number of elements for which the product of differences are invertible is the number of distinct elements with m coefficients in {0, 1}, i.e. a set of elements for which the result of Expression (3) is of size at most 2 m .

To compute Lagrange interpolation, we need a set of size at least dinv elements. Thus, when choosing the extension degree m, we need:

m > log 2 (dinv)
Note that n does not appears in this inequality. However, the following section will demonstrate that dinv needs to be estimated, and that estimation depends on n.

The problem is that we are using extended Lagrange interpolation to invert a polynomial f (x), therefore we do not generate the set {y0, . . . , y d inv } but {x0, . . . , x d inv } on which f will be evaluated on. Predicting the invertibility of

0≤i<j≤d inv (f (xj) -f (xi))
is a non-trivial problem. But by knowing the number of invertible elements in Z m 2 n , the probability that the matrix V f is invertible when randomly drawing a set E of dinv elements can be computed. Let P r(V -1

f,E ) be the probability that the Vandermonde matrix determinant of the polynomial f evaluated on the random set of elements E is invertible. In other words:

E = {x0, . . . , x d inv } P r(V -1 f,E ) = P r 0≤i<j≤d inv (f (xj) -f (xi)) is invertible
Assuming that the permutation polynomial f is injective within the extended ring, the following property holds:

Proposition 2. The probability to obtain an invertible Vandermonde matrix when randomly drawing dinv elements in Z m 2 n is:

P r(V -1 f,E ) = 1 -P r(V -1 f,E ) = 1 - 2 (n-1)m 2 nm = 1 - 1 2 m
Therefore that probability increases proportionally to m.

Regarding complexity, Lagrange interpolation has a complexity quadratic in the number of points we interpolate on. But those points are now elements of Z m 2 n , meaning computing on those points is equivalent to computing on polynomials of degree m. Thus we achieve a complexity of:

O((dinvM(m)) 2 ) ≈ O((dinvm 2 ) 2 )
We need to find a balance between the cost of computing det(V f ) with evaluation points E and that of performing Lagrange interpolation.

This allows us to perform a Lagrange interpolation successfully. Moreover, Z m 2 n being extended from Z2n , if f -1 exists in Z2n , then the interpolation should produce a result in Z2n (i.e. all coefficients in α are null). We will see in Sections 2.1.3 and 2.2.3 that this is not always the case, due to non-uniqueness of compositional identity.

Reachable Polynomials and Complexity

While the complexity of the extended Lagrange interpolation is far worse than the closed-form expression provided in [START_REF] Zhou | Information Hiding in Software with Mixed Boolean-Arithmetic Transforms[END_REF], it successfully inverts all polynomials of the set provided in this paper.

Let us consider an intermediary set between the one defined in [START_REF] Zhou | Information Hiding in Software with Mixed Boolean-Arithmetic Transforms[END_REF] and the full set of permutation polynomials as characterized in [START_REF] Ronald | Permutation Polynomials Modulo 2w[END_REF]:

f (x) = d i=0 aix i a1 is odd ai is even ∀i ≥ 2 (4)
The extended Lagrange interpolation also offers the possibility of inverting such polynomials, but the alleged inverse degree has to be greatly increased. With our own implementation of extended Lagrange, we determined empirically that dinv needs to be approximately equal to d × n. As recalled above the Lagrange interpolation is quadratic in the number of elements interpolated on, that are themselves elements of Z m 2 n . Thus, we obtain a complexity of O((dn) 2 m 4 ) for such a computation when dinv = d × n.

Using this Lagrangian strategy our goal of inverting the full set of permutation polynomials is not achieved but provide more inversions than the close formula given in [START_REF] Zhou | Information Hiding in Software with Mixed Boolean-Arithmetic Transforms[END_REF]. Unfortunately, the result of the extended Lagrange interpolation remains in Z m 2 n regardless of the number of points interpolated on.

A main drawback of ring extension, apart from the increase in complexity, is that it requires to work on the ring Z2n [X] as opposed to P(A) as described in Section 2.1.2. The next section will develop why this prevents the inverse computation of all permutation polynomials as characterized by Rivest.

On Polynomial Ideals

Addressing the problem of dinv alleged huge value requires to focus on the problem of polynomial simplification, meaning that for a given polynomial f , one asks for a polynomial g (if it exists) verifying:

g(x) = f (x) mod 2 n ∀x ∈ Z2n with deg(g) < deg(f )
In [START_REF] Smile | Polynomial functions on the units of z2n[END_REF], a method for polynomial simplification using polynomial ideal is presented: in this section, we adapt their method to our case. An ideal of Z2n [x] generated by the finite sequence of polynomials {F0, F1, . . . , Fs} is the set of all its Z2n [x]-linear combinations:

F0, . . . , Fs = { s i=0 GiFi : Gi ∈ Z2n [x]} 2.2.1 Zero Ideal on Z * 2 n

and Z2n

The method presented in [START_REF] Smile | Polynomial functions on the units of z2n[END_REF] is defined in the ring of polynomials with coefficients in Z * 2 n , the ring of inversible elements in Z2n . The authors define an ideal I * generated by a finite set {P * 1 , . . . , P * d *

n+1

} of polynomials which evaluate globally to 0 as a function taking values in Z * 2 n . Thus the ideal I * verifies:

P ∈ I * ⇐⇒ P (x) = 0 mod 2 n ∀x ∈ Z * 2 n
The authors define this set of polynomials in the following way (we choose here to use positive roots):

P * i (x) = 2 n-i-t i i j=0 (x -2j -1)
where ti is the largest integer such that 2 divides i!. The integer d * n is defined as the largest integer i such that n-i-ti is positive. In particular, P * 0 = 2 n and P *

d * n+1 = (x -1)(x - 3) • • • (x -2d * n + 1
). Let us recall that, in a field, for a variable a to be root of a polynomial, (x -a) must divide that polynomial. However, in a general ring, zero-divisors provide an alternative way of producing 0.

When x is an odd integer, the value i j=1 (x -2j -1) is a product of i consecutive even numbers. Therefore, as explained in [START_REF] Smile | Polynomial functions on the units of z2n[END_REF], it is divisible by 2 i i! and so it is divisible by 2 i+ti . Multiplying this polynomial by 2 n-i-t i results in 2 n which is equal to zero in Z2n .

From The P * i generating the ideal I * on Z * 2 n , we deduce the set of polynomials Pi generating the ideal I in Z2n [x] of all the polynomials evaluating to 0 for any value of x in Z2n , i.e. I is the zero ideal of Z2n [x] (see Proposition 1). The definition of Pi is derived from P * i , by considering even roots, so that if x is even, it still induces a product of i consecutive even numbers:

Pi = 2 n-i-t i 2i-1 j=0 (x -j)
Note that P0 is equal to 2 n and the degree of Pi is increasing with i. The index of the polynomial Pi with highest degree is defined as follows. Let imax be the greatest integer such that n -( -1) -t -1 > 0. Two cases are possible, i.e n -imax -ti max equals 0 or is negative, but the polynomial Pi max is always defined as

Pi max = 2imax-1 j=0 (x -j)

Polynomial Simplification

The generating set {Po, . . . , Pi max } of the zero ideal I provides an algorithmic method to compute in Z2n [x] modulo I. In particular, for a given f , this let us compute a polynomial g of smallest degree in the class {f + h : h ∈ I} of f modulo I. Such a computation is called polynomial simplification. As stated in Proposition 1, any polynomial g in the class of f will define the same function on Z2n , thus the simplification procedure let us define a binary permutation polynomial with the smallest polynomial as possible.

We now describe this simplification method. First, note that for all i, the polynomial Pi is the product of a monic polynomial (with a leading coefficient equals to 1) and a constant equal to a power of 2 (which we will refer as expi in the sequel). Moreover, the more i increases (therefore the degree of Pi), the smaller expi gets. From these remarks, one can simplify a given permutation polynomial f by using the following procedure. If expi divides the leading coefficient a d of f (x) = d i=0 aix i and deg(Pi) < d, let us define g the permutation interpreted as the polynomial:

g(x) = f (x) -( a d expi )(x d-deg(P i ) )Pi
Then g is in the same class as f modulo I and deg(g) < d (i.e g is a reduction of f modulo I).

The process continues with the new polynomial g while the conditions on the leading coefficient and the degree are true. At the end, one obtains the reduction of f modulo I with the smallest degree.

To resume the previous discussion, the permutation polynomial set P(Z2n ) is now seen as a quotient sub-group of Z2n [X]/I as described in the introduction. For each class in P(Z2n ), one can choose, as a representative, a polynomial of degree smaller than the ones of the Pi. Hence, these representatives have a degree smaller than dn = 2 × imax the degree of Pi max and thus, the set P(Z2n ) is finite.

We then deduce the following central result.

Theorem 5. The ideal I = P0, . . . , Pi max verifies

for f, g ∈ Z2n [X] and h ∈ I f = g -h ⇐⇒ f (x) = g(x) mod 2 n ∀x ∈ Z2n
Moreover any binary permutation polynomial can be equally represented by a polynomial of degree at most dn = Deg(Pi max ).

We do not provide a complete proof of this result, it will be detailed in an extended version of this paper.

Identity Polynomials in Z2n

Simplification is not the only result induced by the zero ideal. Let us define the set I2n :

I2n = {x + h(x)} ∀h ∈ I
This set defines a class of polynomials which are, as functions, equivalent to X. Therefore, for a given polynomial f , if there exists g such as g

• f ∈ I2n , g is equivalent to f -1 .
This is an important result as it hints the reason why Lagrange interpolation struggles to invert some polynomials. Lagrange interpolation searches for a polynomial verifying g(f (x)) = x mod 2 n , but as we shown, there are other choices producing a compositional inverse. That is to say, x (the polynomial) is not the only permutation polynomial defining X (the function). This means that:

g(f (x)) = x mod 2 n ∀x ∈ Z2n ⇐⇒ g • f = X
Let g be a polynomial such as g(f (x)) = x+h(x) with h ∈ I, we witnessed, through experimentation, that replacing x in the Lagrange formula by x + h(x) produced a valid g. The problem with such an approach is that, unlike P(Z2n ), I2n is not finite. Therefore predicting h before interpolation did not seem reliable in practice.

However, other inversion methods do not present such restrictions. Newton's method for compositional inversion is one of them.

Inversion Through Newton's Method

In this section we present an adaption for the binary permutation polynomials of the Newton's method for the computation of the compositional inverse as presented in [START_REF] Bostan | Algorithmes rapides pour les polynômes, séries formelles et matrices[END_REF].

Iterative Inversion in Fields

Newton's method (also known as Newton-Raphson method) aims to find successively better approximations of the roots of a function f on some set E. It is based on the assumption that, near a point x0 in the vicinity of a root, a function's behavior is almost that of its tangent line:

f (x) ≈ f (x0) + f (x0)(x -x0) ∀x ∈ E
Therefore, one can approximate a better root by finding x such that:

f (x0) + f (x0)(x -x0) = 0 x = x0 - f (x0) f (x0)
As long as f is derivable and that its derivative evaluation in some xi is invertible, one can define the following iteration:

xi+1 = xi - f (xi) f (xi)
Where xi+1 is a better root approximation than xi. Therefore, if a root exists, the algorithm should converge to it (they are some exceptions in which the algorithm is "trapped" in a cycle, but we never encountered this problem while testing this algorithm in Z2n ). This method can be adapted for other purposes, for example:

xi+1 = xi - f (xi) -7 f (xi)
should converge to x such as f (x) = 7.

The formula linked to our problematic is that of compositional inverse:

gi+1 = gi - f • (gi -X) f • gi
The main problem with this formula is the arithmetic inversion of f (gi). But it is possible to use the following simplification:

f • g = X (f • g) = (f • g) × g = 1 g = 1 f • g gi+1 = gi -g i × (f • (gi -X))
This method was defined on a field, and in the following section we address the subject of its use in Z2n .

The Z2n Case

In order to assess the correctness of the method in Z2n , we use the two properties for Newton's method to correctly compute a compositional inverse [START_REF] Bostan | Algorithmes rapides pour les polynômes, séries formelles et matrices[END_REF]:

f (0) = 0 f (0) is invertible
The second condition is respected as f (0) = a1 which is always invertible, regardless of the polynomial we study.

In order to check for the first property, let us consider the polynomial:

r(x) = d i=1 aix i
we have f = r + a0, meaning f produces the same permutation as r with an additional shift. Therefore, if we invert r, we have the following equality:

r -1 • f = f • r -1 = a0 + r • r -1 = a0 + X (r -1 • f ) -a0 = X
The polynomial r(x) having no constant coefficient, this means r -1 -a0 is inverse of f . However, r(0) = 0, thus r is invertible through Newton's method (in practice, Newton's method in Z2n converges while f (0) = 0 most of the time).

Therefore, if there exists g such as g • f = X, Newton's method should converge to g. We tried to use this method on the set of polynomials which were invertible through Lagrange interpolation and the method succeeded every time.

However, the full set of permutation polynomials as characterized in [START_REF] Ronald | Permutation Polynomials Modulo 2w[END_REF] still remains out of reach for Newton's method as it is. But, as mentioned in Section 2.2.3, this results from the fact that:

g(f (x)) = x mod 2 n ∀x ∈ Z2n ⇐⇒ g • f = x
Let us take a second look at the formula presented in the previous section:

gi+1 = gi - f • (gi -X) f • gi
The problem is that x is not the only polynomial equivalent to the identity function X modulo the zero ideal I. Thus if g(f (x)) = x + h(x) with h ∈ I not equal to 0, this formula would become:

gi+1 = gi - f • (gi -x -h(x))) f • gi
However, we will see in the next section an alternative way of computing on reduced polynomials, which does not assume the knowledge of h.

The Full Set is Reachable

Unlike Lagrange interpolation, Newton's method does not require the use of an extended ring. Thus, one can compute Newton's method in the ring of reduced polynomials F(Z2n ) where:

g(f (x)) = x mod 2 n ∀x ∈ Z2n ⇐⇒ g(f ) = x
Using Newton's method in the ring of reduced polynomials consists in reducing modulo I the result of each iteration (see Section 2.2.2). Then, during the computation, if a polynomial g equivalent to x appears it would be reduced to x. Thus, the problem emphasized above is now solved.

We tried to inverse all the permutation polynomials as characterized in [START_REF] Ronald | Permutation Polynomials Modulo 2w[END_REF]. Not only does it succeed in inverting all the polynomials, but the fact that the degrees of the reduced polynomials are bounded prevents unnecessary increase of the size of the objects during composition and multiplication.

As far as computation goes, each iteration requires a composition and a multiplication (along with some additions and subtractions). In theory, Newton's method converge to a solution with quadratic speed (see [START_REF] Bostan | Algorithmes rapides pour les polynômes, séries formelles et matrices[END_REF]). Meaning to inverse a polynomial, the number of iterations required would be squared in the degree of its inverse. This degree being bounded by n, we get at most √ n iterations. Considering a quadratic cost for polynomial multiplication and composition, an overall complexity of O(d 2 n × √ n) is achieved, where dn is a bound on the degree of a reduced polynomial (see Section 2.2.2). This complexity is far better than the one of the Lagrange interpolation as described above.

Note that the cost of polynomial reduction does not change this complexity estimation. Actually. if we consider consider the product of two polynomials of degree dmax, the resulting polynomial before reduction is then of degree 2 × dmax. Reducing that polynomial to a polynomial of degree dmax requires dmax polynomial subtractions, and therefore presents a complexity of O(d 2 max ). On the same principle, further reduction from this polynomial of degree dmax to a polynomial of smaller degree will at most be quadratic in the degree, which is the same complexity as the other computations performed (multiplications and compositions) during each iterations of Newton's inversion.

On the degree of the inverse

An interesting result which could follow this study is the relation between the degree of a permutation polynomial and the degree of its minimal inverse (let us recall that in contrary to the set defined in [START_REF] Zhou | Information Hiding in Software with Mixed Boolean-Arithmetic Transforms[END_REF], the degree of a permutation polynomial is not necessary the same as its inverse).

Because the polynomial set defined in [START_REF] Zhou | Information Hiding in Software with Mixed Boolean-Arithmetic Transforms[END_REF] does not present such a problem, our hypothesis is that this difference in degree is tight to the difference between this set and the full characterization given in [START_REF] Ronald | Permutation Polynomials Modulo 2w[END_REF].

Permutation polynomials presented in [START_REF] Zhou | Information Hiding in Software with Mixed Boolean-Arithmetic Transforms[END_REF] are polynomials i aix i such that:

2 n 2 |ai ∀i ≥ 2
Therefore each coefficient ai with i ≥ 2 has a very high 2-adic valuation.

The set of all the permutation polynomials as characterized by Rivest does not present such a restriction: it includes polynomials with coefficients of small 2-adic valuation. In the opposite, those polynomials results in high degree differences between a polynomial and its inverse. We leave these observations as an open problem that will be studied in a future work.

RESULTS AND APPLICATIONS

Experimental Results

We have implemented all these methods in Python and C language. In this section we report on their performances and applications. Experimental results presented in Figures 1 and 2 were realized on a Lenovo T 430 with an Intel Core i7 -3520M CP U @ 2.90GHz × 4.

Performances

For the results presented in Figures 1, we uniformely drawn permutation polynomials of various degrees and mesured inversion time.

As stated in Section 2.3.3, Newton's iterative method for computing a compositional inverse on Z2n converges in √ n iterations, regardless of the degrees of f and f -1 (while the cost of performing one iteration does depend on the degree). However, our experimental results tend to show a convergence in log 2 (n) iterations. Newton's method is known to show such convergence rates in some very peculiar cases (see [START_REF] Bostan | Algorithmes rapides pour les polynômes, séries formelles et matrices[END_REF]). We have yet to formalize the fact that our problem belongs to one of those, this will be part of our following work on this topic.

Moreover, as one can see on Figure 1 the complexity of the Newton's method seems to depend linearly in the bound on the degree of the given polynomial than quadratically. This behavior may be explained by the simplification method using the zero ideal presented in Section 2.2.2. This reduction allows us to bound the degree of the intermediate polynomials, reducing costs even further. This bound being reached extremely rapidly by the degree of our intermediate polynomial (composition and multiplication induce a rapid growth of its degree), the cost of increasing the degree of the initial polynomial only affects the operations of composition and multiplication linearly. We also plan to study more precisely, in an extended version of this paper, the tight complexity of the Newton's method in this context.

Applications in Obfuscation

In this section, we assess the use of our contributions in the field of program obfuscation, whereas by using permutation polynomial inversion, or identity polynomials as presented in Section 2.2.3.

The cost of obfuscation can be determined either during obfuscation time or during execution. We focus more on the latter, since obfuscation usually has limitations regarding the performance overhead it produces, but more rarely on the time needed to actually obfuscate the input program.

Using Permutation Polynomial Inversion

The obfuscation technique presented in [START_REF] Zhou | Information Hiding in Software with Mixed Boolean-Arithmetic Transforms[END_REF] aims at hiding a constant K with a permutation polynomial f , its inverse f -1 and an MBA expression E equivalent to zero, with the following process:

K = f -1 (E + f (K))
Thus what will appear in the obfuscated code is a polynomial in the variables of E. Obviously, this method could be used with any non-trivial expression E equivalent to zero, not only MBA expressions.

Our results regarding binary permutation polynomial inversion allow any designer to use any of these permutations for this type of obfuscation. This offer both more diversity in the obfuscation technique, and resilience to algebraic attacks such as presented in [START_REF] Biondi | Effectiveness of Synthesis in Concolic Deobfuscation[END_REF].

For example, the binary permutation polynomial:

f = 195907858x 3 + 727318528x 2 + 3506639707x + 6132886
could be used to obfuscate a constant K. However 195907858 is only divisible by 2 while 727318528 is divisible by 2 16 .

Therefore, when trying to simplify f with the technique presented in [START_REF] Biondi | Effectiveness of Synthesis in Concolic Deobfuscation[END_REF], the factor 2 16 is supposed to divide both coefficients a3 and a2, and in fact, it only divides a3. This polynomial thus provides a counter example to the attack proposed in [START_REF] Biondi | Effectiveness of Synthesis in Concolic Deobfuscation[END_REF]. More generally, f and f -1 can be used to encode variables or constants. For constants, this means computing the value f (K) during obfuscation, storing this value in the program instead of K, and using f -1 (f (K)) during execution. In the same manner, one can replace every writing occurrences of a variable x with f (x) and all reading instructions of f (x) with f -1 (f (x)). This process is quite common in obfuscation as it prevents the value of x from appearing in memory, but is more costly since it requires two evaluations of a permutation polynomial (f and f -1 ) compared to the encoding of a constant (f (K) is computed during obfuscation). This also means that during the obfuscation process, encoding a variable requires to check for the degrees of both f and f -1 for performances issues, while constant encoding only requires a small degree for f -1 .

Regarding encoding of variables or constants, the use of permutation polynomials does not provide much more security compared to affine functions, as much as it provides diversity. Indeed, we showed in Section 2.3 that inverting permutation polynomials is not a difficult problem, as Newton's method efficiently invert all binary permutation polynomials. Nevertheless, encoding with such polynomials contributes to the diversity of the obfuscation technique, thus increasing the difficulty to detect it by reverse engineering.

Using Polynomials of the Zero Ideal I

From the zero ideal I we defined in Section 2.2.1, we can use polynomials in I to design two obfuscation techniques. Let us consider a polynomial h ∈ I, then h(x) = 0 mod 2 n ∀x ∈ Z2n . Therefore h can be used to produce an opaque zero, i.e. a non-trivial null expression. This could be used for example as an opaque predicate (see [START_REF] Collberg | A Taxonomy of Obfuscating Transformations[END_REF]), or in replacement of the MBA expression in Zhou et al. [START_REF] Zhou | Information Hiding in Software with Mixed Boolean-Arithmetic Transforms[END_REF] obfuscation:

K = f -1 (h(x) + f (K))
Another use for the polynomial of this ideal is to obfuscate arithmetic expressions, namely polynomials in Z2n [x]. Let us consider a polynomial g(x) to obfuscate, one could write it (h(x) + 1) × g(x) and expand the product to hide the details of g. It is also possible to add dependencies to other variables of the obfuscated program by using h(z) for some other variable z of the context: adding dependencies increases the resilience of the obfuscation technique by making the analysis of the program more complex.

On the other hand, once one example of the obfuscation scheme has been reversed, its weakness is that the analyst only needs to identify the variable z not influencing the output of the computation, and remove any term in z. Keeping the same input for h and g (e.g. (h(x) + 1) × g(x)) removes this weakness, but quotienting by the ideal will remove h(x).

In term of performance, we conducted some experiments to benchmark our approach. In Figure 2, one can see the ratio between execution time of an obfuscated polynomial modulo 2 64 and execution time of an unobfuscated one in function of the degree of h. We conducted our test on numerous polynomials h ∈ I drawn uniformly. We chose polynomials g in Z2n [X], drawn uniformly as well. As one can see, this ratio is quite small, it never exceeds 10 even for polynomial h of degree up to 64. All in all, we think this approach can make analysis more difficult with a negligible impact on the efficiency of the program.

CONCLUSION

In this paper, we have investigated two methods for inverting binary permutation polynomials. These methods allow us to expand the set of permutation polynomials usable for obfuscation purposes. Increasing the variety of those polynomials makes the elaboration of a simplification method harder. Moreover, we introduced some notions (zero ideal) that can be used to improve obfuscation methods using permutation polynomials.

Future works will regard the application of our result to polynomial permutation modulo p n with p > 2 as well as multivariate permutation polynomials. In particular, this would require to adapt the zero ideal formula to different rings.

  c 2016 Copyright held by the owner/author(s). Publication rights licensed to ACM. ISBN 978-1-4503-4576-7/16/10. . . $15.00 DOI: http://dx.doi.org/10.1145/2995306.2995310

Theorem 4 .

 4 With the same notations as in Theorem 3. Let the set T = {0, 1, α, . . . , α 2 m -2 }, then any element e ∈ Z2n [α] can be written uniquely as

Figure 1 :

 1 Figure 1: Invertion time using Newton's method on 64 bits.

Figure 2 :

 2 Figure 2: Obfuscation overhead ratio depending on the degree of h.