Charles Bouillaguet
email: charles.bouillaguet@ens.fr

Jean-Charles Faugère
email: jean-charles.faugere@inria.fr

Pierre-Alain Fouque
email: pierre-alain.fouque@ens.fr

Ludovic Perret
email: ludovic.perret@lip6.fr

Practical Cryptanalysis of the Identification Scheme Based on the Isomorphism of Polynomial with One Secret Problem

This paper presents a practical cryptanalysis of the Identification Scheme proposed by Patarin at Crypto 1996. This scheme relies on the hardness of the Isomorphism of Polynomial with One Secret (IP1S), and enjoys shorter key than many other schemes based on the hardness of a combinatorial problem (as opposed to numbertheoretic problems). Patarin proposed concrete parameters that have not been broken faster than exhaustive search so far. On the theoretical side, IP1S has been shown to be harder than Graph Isomorphism, which makes it an interesting target. We present two new deterministic algorithms to attack the IP1S problem, and we rigorously analyze their complexity and success probability. We show that they can solve a (big) constant fraction of all the instances of degree two in polynomial time. We verified that our algorithms are very efficient in practice. All the parameters with degree two proposed by Patarin are now broken in a few seconds. The parameters with degree three can be broken in less than a CPU-month. The identification scheme is thus quite badly broken.

Introduction

Multivariate cryptography is concerned with the use of multivariate polynomials over finite fields to design cryptographic schemes. The use of polynomial systems in cryptography dates back to the mid eighties with the design of C * [START_REF] Matsumoto | Public quadratic polynomial-tuples for efficient signature-verification and message-encryption[END_REF], and many others proposals appeared afterwards [START_REF] Patarin | The Oil and Vinegar signature scheme[END_REF][START_REF] Patarin | Flash, a fast multivariate signature algorithm[END_REF][START_REF] Patarin | QUARTZ, 128-Bit Long Digital Signatures[END_REF][START_REF] Koblitz | Algebraic Aspects of Cryptography[END_REF][START_REF] Wolf | Taxonomy of Public Key Schemes Based on the Problem of Multivariate Quadratic Equations[END_REF]. The security of multivariate schemes is in general related to the difficulty of solving random or structured systems of multivariate polynomial equations. This problem has been proved to be NP-complete [START_REF] Garey | Computers and Intractability, A Guide to the Theory of NP-Completeness[END_REF], and it is conjectured [START_REF] Bardet | Asymptotic Behaviour of the Degree of Regularity of Semi-Regular Polynomial Systems[END_REF] that systems of random polynomials are hard to solve in practice. As usual when a trapdoor must be embedded in a hard problem, easy instances are transformed into random-looking instances using secret transformations. In multivariate cryptography, it is common to map an easily-invertible collection of polynomials a into an apparently random one b. It is then assumed that, being supposedly indistinguishable from random, b should be hard to solve. The structure-hiding transformation is very often the composition with linear (or affine) invertible mappings S and T , namely b = T • a • S. The matrices S and T are generally part of the secret-key.

The Isomorphism of Polynomials (IP) is the problem of recovering the secret transformations S and T given a and b. It is a fundamental problem of multivariate cryptography, since its hardness implies the difficulty of the key-recovery for various multivariate cryptosystems. Notorious examples include C * [START_REF] Matsumoto | Public quadratic polynomial-tuples for efficient signature-verification and message-encryption[END_REF], the traitor tracing scheme proposed by Billet and Gilbert [START_REF] Billet | A traceable block cipher[END_REF], the SFLASH signature scheme [START_REF] Patarin | Flash, a fast multivariate signature algorithm[END_REF], the ℓ-IC signature scheme [START_REF] Ding | ℓ-invertible cycles for multivariate quadratic public key cryptography[END_REF], the square-vinegar signature scheme [START_REF] Baena | Square-vinegar signature scheme[END_REF] and the Square encryption scheme [START_REF] Clough | Square, a new multivariate encryption scheme[END_REF] 3 . All these schemes have been broken, because the structure of the central map was not hidden enough. The corresponding IP problem was then not random, but structured. However, when no apparent structure exists in both a and b, then the IP problem is fairly difficult. This motivated Patarin to introduce it as an intractable assumption by itself in [START_REF] Patarin | Hidden fields equations (hfe) and isomorphisms of polynomials (ip): Two new families of asymmetric algorithms[END_REF]. So far only exponential algorithms [START_REF] Patarin | Improved Algorithms for Isomorphisms of Polynomials[END_REF][START_REF] Faugère | Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects[END_REF] are known to attack the general IP problem.

An important special case of IP is the IP problem with one secret (IP1S for short), where T is the identity matrix. Patarin suggested in 1996 [START_REF] Patarin | Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms[END_REF] to construct a zero-knowledge identification scheme relying on the hardness of IP1S, inspired by the Zero-Knowledge proof system for Graph Isomorphism of [START_REF] Goldreich | Proofs that yield nothing but their validity and a methodology of cryptographic protocol design[END_REF]. The proposed parameters lead to relatively small key sizes (for instance to secret and public keys of 256 bits each and no additional information), as the complexity of the problem was believed to be exponential. The proposed parameters have not been broken so far, and no technique better than exhaustive search is known to attack the scheme. The IP1S problem is also interesting from a complexity-theoretic point of view. It has been proved in [START_REF] Patarin | Improved Algorithms for Isomorphisms of Polynomials[END_REF] that IP1S is Graph Isomorphism-hard (GI-hard for short). This leads Patarin et al. to claim that IP1S is unlikely to be solvable in polynomial time, because no polynomial algorithm is known for GI in spite of more than forty years of research. On the other hand, GI is not known to be NP-complete. Generating hard instances GI is pretty non-trivial, and there are powerful heuristics as well as expected linear time algorithms for random graphs [START_REF] Fortin | The graph isomorphism problem[END_REF]. This compromises the use of GI as an identification mechanism, and was part of the motivation for introducing IP1S as an alternative. Moreover, when used in this context, instances of the IP problem are random, which presumably avoids all the attacks on the cryptographic schemes mentioned above.

Previous and Related Work. The identification scheme based on IP1S is not based on number-theoretic assumptions, unlike for instance the well-known Fiat-Shamir protocol [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF]. Many other identification schemes are not based on number theoretic assumptions [START_REF] Shamir | An efficient identification scheme based on permuted kernels (extended abstract)[END_REF][START_REF] Stern | A new identification scheme based on syndrome decoding[END_REF][START_REF] Stern | Designing identification schemes with keys of short size[END_REF][START_REF] Pointcheval | A new identification scheme based on the perceptrons problem[END_REF][START_REF] Lyubashevsky | Lattice-based identification schemes secure under active attacks[END_REF]. However, the IP1S-based identification scheme enjoys shorter keys than most others.

To our knowledge, the first algorithm dedicated to IP1S can be found in Geiselmann et al. [START_REF] Geiselmann | An Attack on the Isomorphisms of Polynomials Problem with One Secret[END_REF]. The authors of [START_REF] Geiselmann | An Attack on the Isomorphisms of Polynomials Problem with One Secret[END_REF] remarked that each row of a matrix solution of IP1S verifies an algebraic system of equations. They then used an exhaustive search to find the solutions of such system. Soon after, this technique has been improved by Levy-dit-Vehel and Perret [START_REF] Vehel | Polynomial Equivalence Problems and Applications to Multivariate Cryptosystems[END_REF] who replaced this exhaustive search by a Gröbner basis computation. This still yields exponential algorithms, and the improvement induced by this replacement is is as significant as the gain obtained when comparing Gröbner basis and exhaustive search for solving random algebraic systems. It is negligible over small field (i.e., typically, F 2 ), but significant for instances of IP1S over large fields. However, the complexity of those algorithms remains exponential by nature.

Finally, Perret [START_REF] Perret | A Fast Cryptanalysis of the Isomorphism of Polynomials with One Secret Problem[END_REF] shows that the affine and linear variants of IP1S are equivalent, i.e., one can without loss of generality restrict our attention to the case where S is linear (as opposed to affine). In addition, a new approach for solving IP1S using the Jacobian matrix was proposed. The algorithm is polynomial when the number u of polynomials in a and b is equal to the number of variables n. However, when u < n, the complexity of this approach is not well understood. Moreover, when the number of polynomials is very small, for instance u = 2, this algorithm is totally inefficient.

The main application of IP1S is the identification scheme proposed in [START_REF] Patarin | Improved Algorithms for Isomorphisms of Polynomials[END_REF]. The public key being composed of two sets of u polynomials, it is interesting to keep the number of polynomials as small as possible (1 or 2). For such parameters, the authentication mechanism based on IP1S looks appealing in terms of key size.

All in all, the existing literature on the IP and IP1S problem can be split in two categories: heuristic algorithms with (more or less vaguely) "known" complexity and unknown success probability [START_REF] Patarin | Improved Algorithms for Isomorphisms of Polynomials[END_REF], and rigorous algorithms that always succeeds but with unknown complexity [START_REF] Faugère | Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects[END_REF][START_REF] Perret | A Fast Cryptanalysis of the Isomorphism of Polynomials with One Secret Problem[END_REF][START_REF] Vehel | Polynomial Equivalence Problems and Applications to Multivariate Cryptosystems[END_REF][START_REF] Geiselmann | An Attack on the Isomorphisms of Polynomials Problem with One Secret[END_REF]. This situation makes it very difficult, if not plainly impossible to compare these algorithms based on their theoretical features. The class of instances that can be solved by a given algorithm of the first type is in general not known. Conversely, the class of instances over which an algorithm of the second type terminates quickly are often not known as well. This lead the authors of IP/IP1S algorithms to measure the efficiency of their techniques in practice, or even not to measure it at all. Several sets of concrete parameters for IP and IP1S were proposed by Patarin in [START_REF] Patarin | Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms[END_REF], and can be used to measure the progress accomplished since their introduction. The techniques presented in this paper allow to break all these challenges in practice.

Techniques. The algorithms presented here are deterministic, and rely on the two weapons that have dealt a severe blow to multivariate cryptography: linear algebra and Gröbner bases. Our ideas borrow to the recent differential cryptanalysis of multivariate schemes. While the algorithms are not very complicated, analyzing their running time is fairly non-trivial, and requires the invocation of not-so-well-known results about linear algebra (such as the dimension of the commutant of a matrix, or the properties of the product of two skew-symmetric matrices), as well as known results about random matrices, most notably the distribution of the rank and the probability of being cyclic. The two most delicate steps of the analysis involve lower-bounding the dimension of the kernel of a homogeneous system of matrix equations, and upper-bounding the degree of polynomials manipulated by a Gröbner-basis algorithm.

Our Results. We present two new "rigorous" and deterministic algorithms. On the practical side, these algorithms are efficient: random quadratic IP1S instances and random cubic inhomogeneous IP1S instances can be broken in time O n 6 for any size of the parameters. In particular, all the quadratic IP1S challenges proposed by Patarin are now broken in a few seconds. The biggest cubic IP1S challenge can be broken in less than 1 CPU-month. The IP1S identification scheme is thus broken beyond repair in the quadratic case. In the case of cubic IP1S, our attack runs in time O n 6 × q n , and the security parameter have to be seriously reconsidered, which makes the scheme much less attractive, since the key size is cubic in n.

A rigorous analysis of our algorithms is both necessary and tricky. When generating linear equations, special care has to be taken to count how many of them are independent. The recent history of algebraic cryptanalysis taught us that failure to do so may have drastic consequences. Additionally, the complexity of Gröbner bases computation, even though a bit more well-understood now in the generic case, is still often a delicate matter for structured systems.

A unique and distinctive feature of our algorithms compared to the previous state of affairs, and one of our main theoretical contribution, is that we characterize the class of instances that can be solved by our techniques in polynomial time. We show, for instance, that a (big) constant fraction of all quadratic IP1S instances can be solved in polynomial time.

Organisation of the paper. In section 2, we recall some useful facts about the IP1S problem. Then, in section 3, we introduce the identification scheme based on the hardness of IP1S and compare it to other non-number theoretic based ID schemes. We then introduce our algorithms to break IP1S in the quadratic case in section 4, and in the cubic case in section 5.

The IP1S Problem

We recall the definition of the IP1S problem. Given two families of polynomials a and b in F q [x 1 , . . . , x n ] u the task is to find an invertible matrix S ∈ GL n (F q ) and a vector c ∈ (F q )

n such that:

b(x) = a(S • x + c). (1)
We will denote by f (k) the homogeneous component of degree k of f , and by extension a (k) denotes the vector of polynomials obtained by taking the homogeneous components of degree k of all the coordinates of a. We define the derivative of a in c to be the function ∂a ∂c : x → a(x + c) + a(x). The following lemma is very useful, and is at the heart of the techniques proposed in [START_REF] Faugère | Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects[END_REF]. Lemma 1. i) For all k ≥ 1, we have:

b (k) = a + ∂a ∂c (k) • S.
ii) If d is the degree of a and b, then b (d) = a (d) • S. iii) S transforms the set of common zeroes of a into the set of common zeroes of b.

Proof. Let us write T (x) = T ℓ • x + T c and S(x) = S ℓ • x + S c where T ℓ and S ℓ are n × n matrices, whereas S c and T c are vectors of (F q )

n . We have:

b(x) = T c + T ℓ • a(S ℓ • x + S c ) = T c + T ℓ • Da(S ℓ • x, S c ) + a(S ℓ • x) + a(S c ) -a(0) = T c + T ℓ • a (S c ) -a(0) + T ℓ • ∂a ∂S c • S ℓ (x) + (T ℓ • a • S ℓ ) (x)
The first statement follows from the application of [17, lemma 4] to the last equality. The second and third statements are direct consequences of the first one.

⊓ ⊔

A useful consequence of lemma 1 is that without loss of generality we may assume c to be the null vector 4 . A consequence of point ii) is that from any instance of the problem we can deduce a linear homogeneous instance by considering only the homogeneous component of highest degree. If this instance can be solved, and S can be retrieved, then recovering c is not difficult, using a slight generalization of the idea shown in [START_REF] Geiselmann | Attacking the Affine Parts of SFLASH[END_REF]. If S is known, then ∂a ∂c can be explicitly computed, and c can usually be deduced therefrom. For instance, focusing on the homogeneous component of degree one yields a system of u • n linear equations in n variables that admits c as a solution. In most cases, it will in fact admit only c as a solution, which enables recovering c. It was pointed out in [START_REF] Patarin | Improved Algorithms for Isomorphisms of Polynomials[END_REF] that if there is only one quadratic polynomial, then the problem is easily solved in polynomial time. This follows from the fact that quadratic forms admit a canonical representation (see for instance [START_REF] Lidl | Finite fields[END_REF]). The change of coordinate can be then easily computed. We will therefore focus on the case of u ≥ 2 when the polynomials are quadratic.

For various reasons, the IP1S problem becomes easier when u is close to n, and harder when u is small. For instance, the algorithm given in [START_REF] Perret | A Fast Cryptanalysis of the Isomorphism of Polynomials with One Secret Problem[END_REF] deals with the case u = n in polynomial time, but cannot tackle the case where u = 2 and n is big, which prevented it from breaking the parameters proposed by Patarin. Additionally, small values of u leads to smaller public keys. Therefore, we will restrict our attention to the case where u = 2 when the polynomials are quadratic, and where u = 1 when they are cubic. These are the most cryptographically relevant cases, and the most challenging. We will also consider the case where F q is a field of characteristic two. It can be shown that this makes the problem a bit harder, but again this is the most cryptographically relevant case. The quadratic and cubic IP1S problems are very different and lead to specific approaches, therefore we will discuss them separately.

Patarin's IP1S-Based identification Scheme

Zero-Knowledge proofs were introduced in 1985 by Goldwasser, Micali and Rackoff in [START_REF] Goldwasser | The knowledge complexity of interactive proof-systems (extended abstract)[END_REF]. Soon afterwards, Fiat and Shamir [START_REF] Fiat | How to prove yourself: Practical solutions to identification and signature problems[END_REF] used the hardness of quadratic residuosity to build an efficient identification scheme. Many other identification schemes appeard afterwards, all relying on the hardness of number-theoretic assumptions. Some cryptographers took a different line of research, and tried to design identification scheme from different computational assumptions, not relying on number theory, but instead on the NP-hardness of some specific combinatorial problems.

One of the very-first combinatorial identification scheme was proposed by Shamir [START_REF] Shamir | An efficient identification scheme based on permuted kernels (extended abstract)[END_REF], and relied on the hardness of the Permuted Kernel Problem (PKP). Later on, Stern proposed in [START_REF] Stern | A new identification scheme based on syndrome decoding[END_REF] a scheme based on the intractability of Syndrome Decoding (SD), and in [START_REF] Stern | Designing identification schemes with keys of short size[END_REF] a scheme based on the intractability of Constrained Linear Equations (CLE). Finally, Pointcheval [START_REF] Pointcheval | A new identification scheme based on the perceptrons problem[END_REF] proposed a scheme related to the hardness of the Perceptron Problem, originating from the area of learning theory. All these problems are NP-complete (as opposed to IP1S). The designers proposed practical parameters, aiming for a security level of 2 64 or more, which are summarized in table 1. In all these schemes, it is required that all users share a public common set of information, a "common setting", usually describing the instance of the hard problem. For instance, in number-theoretic problems, the description of the curve, or of the group over which a discrete logarithm problem is considered is a common public information. While this information is not a "key" stricto sensu, it must nevertheless be stored by the prover and by the verifier, leading to higher memory requirements. However, in some case it can be chosen randomly, or generated online from a small seed using a PRNG. [START_REF] Shamir | An efficient identification scheme based on permuted kernels (extended abstract)[END_REF][START_REF] Stern | A new identification scheme based on syndrome decoding[END_REF][START_REF] Stern | Designing identification schemes with keys of short size[END_REF][START_REF] Pointcheval | A new identification scheme based on the perceptrons problem[END_REF][START_REF] Patarin | Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms[END_REF] in order to obtain a security level of roughly 2 64 . 4 this was already observed in [START_REF] Perret | A Fast Cryptanalysis of the Isomorphism of Polynomials with One Secret Problem[END_REF].

Challenge [START_REF] Patarin | Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms[END_REF]. We introduce challenge E.

On the contrary, the IP1S-based identification scheme proposed by Patarin in [START_REF] Patarin | Hidden fields equations (hfe) and isomorphisms of polynomials (ip): Two new families of asymmetric algorithms[END_REF][START_REF] Patarin | Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms[END_REF] does not need the prover and the verifier to share additional information (except maybe the description of the finite field, which is very small). It works very similarly to the original identification scheme based on a zero-knowledge proof system for Graph-Isomorphism (GI) by Goldreich, Micali and Wigderson [START_REF] Goldreich | Proofs that yield nothing but their validity and a methodology of cryptographic protocol design[END_REF]. One of the reasons for replacing GI by IP1S is the existence of efficient heuristic algorithms for GI, capable of solving efficiently random instances. The generation of hard instances of GI is a delicate matter [START_REF] Fortin | The graph isomorphism problem[END_REF]. Replacing the GI problem by IP1S yields shorted key, and random instances of IP1S were a priori secure. Patarin proposed concrete parameters, which are shown in table. 2. The PKP and SD schemes lead to bigger keys than IP1S, while the Perceptron scheme leads to comparable key-sizes, and CLE yields smaller keys than IP1S, if we neglect the additional memory requirement imposed by the common setting.

These IP1S challenges cannot be attacked using the existing techniques [START_REF] Faugère | Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects[END_REF][START_REF] Geiselmann | An Attack on the Isomorphisms of Polynomials Problem with One Secret[END_REF][START_REF] Perret | A Fast Cryptanalysis of the Isomorphism of Polynomials with One Secret Problem[END_REF]. So the best attack remains exhaustively searching for the secret key. As a final note, let us mention that Lyubashevsky recently proposed in [START_REF] Lyubashevsky | Lattice-based identification schemes secure under active attacks[END_REF] to build an identification scheme using the hardness of lattice problems, but did not propose concrete parameters.

Cryptanalysis of Quadratic IP1S

The main observation underlying our quadratic IP1S algorithm is that by differentiating equation ( 1), it is possible to collect linear equations between the coefficients of S and those of S -1 .

We denote by Df : (F q ) n × (F q ) n → F q u the differential of a function f : F n q → F u q . Df is defined by:

Df (x, y) = f (x + y) -f (x) -f (y) + f (0)
It is easy to see that Df (x, y) = Df (y, x). If f is a polynomial of total degree d, then Df is a polynomial of total degree d, but of degree d -1 in x and y. Thus, when f is quadratic, then Df is a symmetric bilinear mapping. Going back to the quadratic IP1S problem, for all vectors x, y ∈ (F q ) n , we have:

∀x, y ∈ (F q ) n , Db(x, y) = Da (S • x, S • y) .
Using the change of variable y ′ = S • y, this equation becomes:

∀x, y ′ ∈ (F q ) n , Db(x, S -1 • y ′ ) = Da(S • x, y ′ ). (2)
Since a and b are of total degree 2, then Da and Db are bilinear (symmetric) mappings. In this case, since equation ( 2) is valid for all x and y, then in particular it is valid on a basis of (F q ) n × (F q ) n , and substituting fixed basis vectors for x and y yields linear equations between the coefficients of S and those of S -1 . This idea for obtaining linear equations can also be described relatively simply using the usual theory of quadratic forms (with the tweaks required by the fact that we are working in characteristic two). If F q is a field of even characteristic, then the set of homogeneous quadratic polynomials in n variables over F q is in one-to-one correspondance with the set of symmetric matrices with zero diagonal. Let P (a k ) denote the matrix of the symmetric bilinear form associated with a k (it is related to the polar form of a k in odd characteristic). Recall that the coefficient of index (i, j) of P (a k ) is Da k (e i , e j ), where (e i ) 1≤i≤n is a basis of (F q )

n . We then have:

S :      S -1 • P (b 1 ) = P (a 1 ) • t S . . . S -1 • P (b u ) = P (a u ) • t S (3)
Each one of these u matrix equations yields n 2 linear homogeneous equations between the 2n 2 coefficients of S and those of S -1 . These last u • n 2 homogeneous linear equations cannot be linearly independent as they admit a nontrivial solution S -1 , S . The kernel of S is thus non-trivial, and our hope would be that it describes only one solution. When u is strictly greater than two, we then have much more linear equations than unknowns, and we empirically find only one solution (when the polynomials are randomly chosen). When u = 2, which is again the most relevant case, the situation is unfortunately not as nice; Theorem 1 below shows that the kernel of S is of dimension higher that n -in fact, we will show below that it is of dimension at least 2n. This means that solving the linear equations cannot by itself reveal the solution of the IP1S problem, because S admits at least q 2n solutions, out of which only very few are actual solutions of the IP1S instance 5 . However, the linear equations collected this way can be used to simplify the resolution of the IP1S problem.

When looking at one coordinate of (1), we have an equality between two multivariate polynomials that holds for any value of the variables. Therefore the coefficients of the two polynomials can be identified (this is essentially the algorithm presented in [START_REF] Faugère | Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects[END_REF]). This yields a system S quad of u • n 2 /2 quadratic equations in n 2 unknown over F q . With u = 2, this precisely gives n 2 equations in n 2 unknown, which cannot be solved by any existing techniques faster than exhaustive search.

However, we now know that S lives in the kernel of S, and therefore S can be written as the sum of k = dim ker S matrices that can be easily computed using standard linear algebra. Identifying coefficients in (1) then yields a system S quad of u • n 2 /2 quadratic equations in k unknown. Our hope is that k is small enough for the system to be very overdefined, so that computing a Gröbner basis of S quad is polynomial in theory, and feasible in practice.

The analysis of the attack then proceeds in two steps:

1. Estimate the rank of S (i.e., the value of k).

2. Estimate the complexity of the Gröbner basis computation.

For the sake of simplicity, we will analyze the attack algorithm under some assumptions on the input system. For instance, we will assume that that n is even, and that one of the two quadratic forms we are dealing with is nondegenerate. We will then argue that a random instance satisfies this assumption with high probability, but we are well aware that some structured instance may not. This is in fact quite logical, because a worst-case polynomial algorithm for IP1S would imply a worst-case polynomial for Graph-Isomorphism (a fact that would be quite surprising). The situation of the IP1S problem is in this respect quite similar to that of GI: heuristics are capable of dealing efficiently with the random case, while some very special instances make them fail (interestingly, hard instances for GI are transformed into hard instances for IP1S through the reduction). Lastly, we mention that our algorithm does not necessarily fail on an instance that does not meet our assumptions. However, we no longer have a guarantee on its running time. Random instances fail to meet the assumption with a small probability, but we empirically observed that the algorithm solves them in reasonable time as well.

Counting Linearly Independent Equations

Obtaining guarantees on the number of linearly independent equations in S is the most important and the most delicate part of the attack. Since dim ker S is a function of the instance, it makes sense to consider the random variable giving dim ker S assuming the instance was randomly chosen. Fig. 1 above shows its (experimentally observed) distribution for various sizes of the base field. We immediately see that in odd characteristic, dim ker S is often n, while in characteristic two it is often 2n. In the sequel we provide mathematical arguments to back this observation up. We will focus on the (harder) case of fields of characteristic two, since this is the more cryptographically relevant case.

Our results are expressed in terms of the similarity invariants P 1 , . . . , P s of a matrix M . Their product is the characteristic polynomial of M , P s is the minimal polynomial of M , and P i divides P i+1 . The main technical result needed to understand the rank of S is the following theorem. Theorem 1. Let A 1 , A 2 , B 1 , B 2 be four given matrices of size n × n with coefficients in F q . Let us consider the set of all pairs (X, Y ) of n × n matrices satisfying the following linear equations:

S : B 1 = X • A 1 • Y B 2 = X • A 2 • Y
Let us assume that S admits at least one solution (X 0 , Y 0 ) with both X 0 and Y 0 invertible, and that A 1 is also invertible. 5 We note that this contradicts the hope expressed in section 9 of [ Fig. 1: Experimental distribution of dim ker S.

i) There is a vector-space isomorphism between the kernel of S and the commutant of

C = A 2 • A -1 1 . ii) n ≤ dim ker S.
iii) Let P 1 , . . . , P s be the similarity invariants of C. Then:

dim ker S = s j=1 (2s -2j + 1) • deg P j Proof.
Because a solution of S exists, then B 1 is invertible. Thanks to this, we can write:

S : Y = A -1 1 • X -1 • B 1 B 2 • B -1 1 • X = X • A 2 • A -1 1
Using the particular solution X 0 then gives:

S : Y = A -1 1 • X -1 • B 1 C • X -1 0 • X = X -1 0 • X • C
From there, it is not difficult to see that the kernel of S is in one-to-one correspondance with the commutant of C, the isomorphism being (X, Y ) → X -1 0 • X. The second point of the theorem follows from the well-known fact that n lower-bounds the dimension of the commutant of any endomorphism on a vector space of dimension n (see for instance [7, Fact 2.18.9]). The third point follows from a general result on the dimension of the commutant [20, chapter 6, exercise 32].

⊓ ⊔ Theorem 1 directly applies to our study of the rank of S with A i = P (a i ) and B i = P (b i ). However, it holds only if P (a 1 ) or P (a 2 ) is invertible (we may swap them if we wish, or even take a linear combination). Note that since P (a 1 ) is a random skew-symmetric matrix, it cannot be invertible if n is odd, and the analysis is more complicated in that case. This is why we focus on the case where n is even, and where one of the two quadratic forms is nondegenerate. The following lemma gives us the probability that P (a i ) (or P (b i )) is invertible.

Lemma 2 ([31], theorem 3).

Let N 0 (n, r) denote the number of symmetric matrices of size n × n over F q with zeros on the diagonal and of rank r.

N 0 (n, 2s) = s i=1 q 2i-2 q 2i -1 • 2s-1 i=1 q n-i -1 N 0 (n, 2s + 1) = 0
If n is even, the probability that P (a 1 ) is invertible if q = 2 is about 0.419 (this probability increases exponentially with q). The probability that either P (a 1 ) or P (a 2 ) is invertible is then about 0.662 when q = 2.

Theorem 1 is then applicable in more than half of the cases when q = 2 (and we expect this proportion to grow very quickly with q). When it is applicable, what guarantee does it exactly offer? We would need to know something about the similarity invariants of C. An easy case would be when the minimal and characteristic polynomials are the same (then there is only one invariant factor, and it is precisely the characteristic polynomial). Then Theorem 1 tells us that the dimension of ker S is n. For random matrices, the probability of this event is given by the following lemma.

Lemma 3 ([21]

, theorem 1). Let c(n, q) be the proportion of cyclic n × n matrices (i.e., matrices for which the minimal polynomial is of degree n). We have:

1 q 2 (q + 1) < 1 -c(n, q) < 1 (q 2 -1)(q -1)
And asymptotically, we have:

lim n→∞ c(n, q) = q 5 -1 q 2 (q -1)(q 2 -1) • ∞ i=1 1 - 1 q i
For random matrices over F 2 , and for n big enough, the proportion of cyclic matrices approaches 0.746. Unfortunately, C is hardly a random matrix. In odd characteristic it is the product of two symmetric matrices, while in characteristic two it is the product of two symmetric matrices with null diagonal. The product of two such matrices is very far from being random, and it is in fact never cyclic, as the following result shows.

Theorem 2 ([6]). Let M be a non-singular matrix of even dimension. Then the two following conditions are equivalent:

i) M can be written as the product of two symmetric matrices with null-diagonal.

ii) M has an even number of similarity invariants P 1 , . . . P 2ℓ , and P 2i+1 = P 2i+2 .

Corollary 1. If n is even and C is invertible, then ker S has dimension at least 2n.

Proof. By theorem 2, C has at least two invariants, both equal to the minimal polynomial of C (which thus happens to be of degree n/2). Then theorem 1, point iii) shows that ker S has dimension 2n. If C has more invariants, ker S can only be of higher dimension.

⊓ ⊔

Corollary 1 shows that with a constant probability (when the two quadratic forms are non-degenerate) dim ker S is greater than 2n, which sounds like bad news. When C is not invertible, theorem 2 no longer holds (there are counterexamples), but what does apparently still hold is the fact that the minimal polynomial of C has degree at most n/2, and this would be sufficient to show that in all cases dim ker S ≥ 2n, in accordance with Fig. 1.

What we would in fact need to know is the probability that ker S is exactly of dimension 2n. Theorem 1 still connects this dimension to the similarity invariants of C, even though C is not a uniformly random matrix. It seems plausible that C is unlikely to have a very high number of similarity invariants, and that the most common situation is that it has only two invariants (twice the minimal polynomial). We could not compute explicitly this probability, and we could not find ways to obtain it in the available literature. We measured it experimentally and found 0.746 (after 10 5 trials) when q = 2. This is strikingly close to the result brought by lemma 3 in the random case. Under the conjecture that C has two invariant factors with this probability, then theorem 1 tells us that in about 75% of the cases, dim ker S = 2n. The empirical probability seems to be even higher, as shown by Fig 1.

Solving Very Overdefined Quadratic Systems

The solution of the IP1S instance ( 1) is systematically the solution of a system S quad of n 2 quadratic equations. In the previous section, we argued that we can reduce this system to n 2 equations in 2n unknowns with high probability, and (much) more unknowns with negligible probability. The system is so overdefined that it can almost be resolved by linearization. Indeed, it has N 2 /4 equations in N unknowns. In practice, computing a Gröbner basis of the ideal generated by S quad terminates very quickly, and allows to recover the actual solutions of the problem. This last fact can be theoretically justified. It is well-known that Gröbner basis algorithms [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases (F4)[END_REF][START_REF] Faugère | A New Efficient Algorithm for Computing Gröbner Bases Without Reduction to Zero (F5)[END_REF] are more efficient on overdefined systems. The complexity of most algorithms strongly depend on a parameter of the ideal called the degree of regularity. Indeed, the cost of computing a Gröbner basis is polynomial in the degree of regularity D reg of the system when the ideal has dimension zero, i.e., when the number of solutions is finite. The computation of a Gröbner basis essentially amounts to solve a system of M sparse linear equations in M variables, where M is the number of monomials of degree D reg in N variables. The complexity of this process is roughly O N 3•Dreg , with 2 < ω ≤ 3 the linear algebra constant, and N the number of variables of ideal considered (in our case, N = 2n).

The behavior of the degree of regularity is well understood for "random" systems of equations [START_REF] Bardet | Étude des systèmes algébriques surdéterminés. Applications aux codes correcteurs et à la cryptographie[END_REF][START_REF] Bardet | On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations[END_REF][START_REF] Bardet | Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems[END_REF] (i.e., regular or semi-regular systems). It is conjectured that the proportion of semi-regular systems on N variables goes to 1 when N goes to +∞. Therefore, we can assume that for large N a random system is almost surely semi-regular. This is to some extent a worst-case assumption, as it usually means that our system is not easier to solve than the others. The coefficients of the Hilbert series associated with the ideal generated by a semi-regular sequence of m equations in N variables coincide with those of the series expansion of the function f (z) = 1 -z 2 m /(1 -z) N , up to the degree of regularity. The degree of regularity is the smallest degree d such that the coefficient of degree d in the series expansion of f (z) is not strictly positive. This property enables an explicit computation of the degree of regularity for given values of m and N .

Furthermore, the available literature readily provide asymptotic estimates of the degree of regularity for semigeneric ideals of N + k or α • N equations in N variables, but unfortunately not for the case of α • N 2 in N variables, which is the situation we are facing here. We thus tabulated in table. 3 the degree of regularity for semi-regular systems of equations having the same number of equations and unknowns as those occurring in our attack. From this table, we conclude that for any reasonable value of the parameters, the degree of regularity will be 3, and thus computing a Gröbner basis of S quad should have complexity at most O n 9 . In practice, the maximal degree reached by the F 4 algorithm on our equations is two, which is even better. Table 3. Degree of regularity of random with the same parameters as those occuring in our attack.

Implementation

We demonstrated that the algorithm described in this section terminates in time O n 6 on a constant fraction of the instances. This reasoning is backed up by empirical evidence: we implemented the algorithm using the computer algebra system MAGMA [START_REF] Bosma | The Magma Algebra System I: The User Language[END_REF]. Solving the equations of S quad is achieved by first computing a Gröbner basis of these equations for the Graded-Reverse Lexicographic order using the F 4 algorithm [START_REF] Faugère | A new efficient algorithm for computing Gröbner bases (F4)[END_REF], and then converting it to the Lexicographic order using the FGLM algorithm [START_REF] Faugère | Efficient Computation of Zero-Dimensional Gröbner Bases by Change of Ordering[END_REF]. This implementation breaks the random instances of IP1S in very practical time. For instance, Challenges A and C are solved in a few seconds. Challenge E takes a few minutes, but the dominating part in the execution of the algorithm is in fact the symbolic manipulation of polynomials required to write down the equations of S quad . Actually solving the resulting quadratic equations turns out to be easier than generating them. We never generated a random instance that we could not solve with our technique, for any choice of the parameters.

There are only public parameter sets, and no public challenges to break, so we unfortunately cannot provide the solution of an open challenge to prove that our algorithm works. However, the source code of our implementation is available on the webpage of the first author.

In this section, we focus on the case where a and b are composed of a single cubic polynomial. We assume that a and b are given explicitly, i.e.:

a = n i=1 n j=i n k=j A i,j,k • x i x j x k , b = n i=1 n j=i n k=j B i,j,k • x i x j x k .
As already explained, we can restrict our attention to the homogenous case. The techniques developed previously for the quadratic case cannot directly applied in this setting. Indeed, the differential is no longer a bilinear mapping, and then there is no obvious linear equations between the coefficients of a solution and those of its inverse. However, we can combine the use of the differential together with the Gröbner basis approach proposed in [START_REF] Faugère | Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects[END_REF]. We denote by S 0 = {s 0 i,j } 1≤i,j≤n a particular solution of IP1S between a and b, i.e., it holds that b = a • S 0 . For all vectors x, y ∈ (F q )

n , we have:

Da(S 0 • x, y) = Db(x, S -1 0 • y).
a and b being of total degree 3, the coefficients of S 0 and S -1 0 appear with degree two in the expression of Da and Db above. Let R be the ring K[s 1,1 , . . . , s n,n , u 1,1 , . . . , u n,n ]. We consider the algebra A s of all n × n matrices over R. Let S = {s i,j } and U = {u i,j } in A s be symbolic matrices. We denote by I a,b the ideal generated by all the coefficients in R of the equations:

Da(S • x, y) -Db(x, U • y) = 0, U • S -1 n = 0 n , S • U -1 n = 0 n .
It is easy to see that U = S -1 0 and S = S 0 is particular solution of this system, and also a solution of IP1S between b and a. Our goal is to provide an upper bound on the maximum degree reached during a Gröbner basis computation of I a,b .

We prove here that D reg = 2 for I a,b under the hypothesis that we know one row of a particular solution S 0 , i.e.,

we assume then that we know the following ideal J = s 1,j -s Proof. We use the fact that the degree of regularity of an ideal is generically left invariant by any linear change of the variables or generators [START_REF] Lazard | Gröbner-bases, gaussian elimination and resolution of systems of algebraic equations[END_REF]. In particular, we consider the ideal I ′ a,b generated by all the coefficients in K[x 1 , . . . , x n , y 1 , . . . , y n ] of the equations:

Da(S 0 (S + I n )x, y) -Db(x, (U + I n )S -1 0 y) = 0, U • S = 0 n , S • U = 0 n .
It is clear that I ′ a,b is obtained from I a,b by replacing S (resp. U ) by S 0 (I n + S) (resp. (U + I n )S -1 0 ). Thus, the degree of regularity of I ′ a,b and I a,b are equal. Using the same transformation, the ideal J becomes

J ′ = s 1,j | j = 1, . . . , n .
We now estimate the degree of regularity of the ideal I ′ a,b + J ′ . For a reason which will become clear in the sequel, it is more convenient to work with I ′ a,b + J ′ . In what follows, F will denote the generators of I ′ a,b + J ′ . We will show that many new linear equations appear when considering equations of degree 2. To formalize this, we introduce some definitions related to the F 4 algorithm [START_REF] Faugère | A New Efficient Algorithm for Computing Gröbner Bases Without Reduction to Zero (F5)[END_REF]. In particular, we will denote by I d,k the linear space generated during the k-th step of F 4 when considering polynomials of degree d.

Definition 1.

We have the following recursive definition of I d,k :

I d,0 (F ) = Vect K (F ) I d,1 (F ) = Vect K (s i,j f | 1 i, j n and f ∈ I d,0 (F )) +Vect K (u i,j f | 1 i, j n and f ∈ I d,0 (F )) I d,k (F ) = Vect K (s i,j f | 1 i, j n and f ∈ I d,k-1 (F ) and deg(f ) ≤ d -1) +Vect K (u i,j f | 1 i, j n and f ∈ I d,k-1 (F ) and deg(f ) ≤ d -1) .
Roughly speaking, the index k is the number of steps in the F 4 /F 5 [START_REF] Faugère | A New Efficient Algorithm for Computing Gröbner Bases Without Reduction to Zero (F5)[END_REF] algorithm to compute an element f ∈ I d,k (F ). We show that I 2,1 (F ) contains exactly n 2 +2n linear equations. This means that we have already many linear equations generated during the first step of a Gröbner basis computation of F . Lemma 4. I 2,1 (F ) contains the following linear equations:

{u 1,j | j = 1, . . . , n}. (4)
Proof. From the first row of the following zero matrix S • U we obtain the following equations:

               s 1,1 u 1,1 + s 1,2 u 2,1 + s 1,3 u 3,1 + • • • + s 1,n u n,1 = 0, s 1,1 u 1,2 + s 1,2 u 2,2 + s 1,3 u 3,2 + • • • + s 1,n u n,2 = 0, s 1,1 u 1,3 + s 1,2 u 2,3 + s 1,3 u 3,3 + • • • + s 1,n u n,3 = 0, • • • s 1,1 u 1,n + s 1,2 u 2,n + s 1,3 u 3,n + • • • + s 1,n u n,n = 0
Using the equations s 1,j = 0 from the ideal J ′ , we obtain then u 1,1 = 0, u 1,2 = 0, . . . , u 1,n = 0.

⊓ ⊔

We can also predict the existence of other linear equations in I 2,1 (F ).

Lemma 5. For all (i, j) ∈ {1, . . . , n} 2 the coefficient of y 1 y i x j in Da(S 0 (S + I n )x, y) -Db(x, (U + I n )S -1 0 y) is a non zero6 linear equation modulo the equations of the ideal J ′ and (4). Among these equations, there are n which depend only of the variables {s k,ℓ | 1 ≤ k, ℓ ≤ n}.

Proof. We consider the coefficient of the monomial m = y 1 y i x j in the expression

∆ = ∆ a -∆ b = Da(S 0 (S + I n )x, y) -Db(x, (U + I n )S -1 0 y).
Since the monomial m is linear in x j it is clear that the corresponding coefficient in ∆ a = Da(S 0 (S + I n )x, y) is also linear in the variables s i,j ; moreover this coefficient is non zero. We have now to consider the coefficient of m in ∆ b . Since Db(x, y) is the differential of an homogenous polynomial of degree 3 we can always write:

Db(x, y) = n i=1 n j=i ℓ i,j (y 1 , . . . , y n ) x i x j + n i=1 q i (y 1 , . . . , y n )x i (5)
where ℓ i,j (resp. q i ) is a polynomial of degree 1 (resp. 2). Consequently, the coefficient of m Db is also the coefficient of y 1 y i in q j ((U + I n )S -1 0 y). That is to say, in q j (y) we have now to replace y = (y 1 , . . . , y n ) by ((U + I n )S -1 0 y). Thus, modulo the equations of the ideal J ′ and (4), we can write the product ((U + I n )S -1 0 y) as

=       y 1 . . . . . . y n            1 0 0 0 u 2,1 • • • • • • u 2,n . . . • • • • • • . . . u n,1 • • • • • • u n,n          * * * * * * * * * * * * * * * *     =       y 1 . . . . . . y n            * * * * ( * u 2,1 + • • • + * u 2,n ) • • • • • • ( * u 2,1 + • • • + * u 2,n ) . . . • • • • • • . . . ( * u n,1 + • • • + * u n,n ) • • • • • • ( * u 2,1 + • • • + * u n,n )      =      * y 1 + ( * u 2,1 + • • • + * u 2,n )y 2 + • • • + ( * u n,1 + • • • + * u n,n )y n * y 1 + ( * u 2,1 + • • • + * u 2,n )y 2 + • • • + ( * u n,1 + • • • + * u n,n )y n . . . * y 1 + ( * u 2,1 + • • • + * u 2,n )y 2 + • • • + ( * u n,1 + • • • + * u n,n )y n     
Hence the coefficient of y 1 y i in q j ((U + I n )S -1 0 y) is linear in the variables u k,l when i = 1 and the coefficient of y 2 1 is a constant.

⊓ ⊔

To summarize: Lemma 6. I 2,1 (F ) contains exactly n 2 + 2n linear equations.

Proof. In I 2,1 (F ), we have n linear equations from lemma 5, n linear equations from the very definition of J ′ , and n 2 linear equations from lemma 5 ⊓ ⊔

As explained before, we obtain n 2 + 2n linear equations for I 2,1 (F ). However, we have 2n 2 variables. So, we have to consider I 2,2 (F ), i.e., the equations generated at degree 2 during the second step. Thanks to lemma 6, we can reduce the original system to a quadratic system in 2n 2 -(2n + n 2 ) = (n -1) 2 variables. W.l.o.g we can assume that we keep only the variable u i,j where 2 ≤ i, j ≤ n. Let F ′ be the system obtained from F after substituting the 2n + n 2 linear equations of lemma 6. All the monomials in K[x 1 , . . . , x n , y 1 , . . . , y n ] of Da(S 0 (S+I n )x, y)-Db(x, (U +I n )S -1 0 y) have the following shape:

x i y j y k or y i x j x k with 1 ≤ i, j, k ≤ n.

Hence the number of such monomials is 2n n(n+1)

2

= n 2 (n + 1) ≈ n 3 , which implies that the number of equations in F ′ is also n 3 .

Thanks to this remark, we will now prove that we can linearize F ′ . Let T (F ′ ) be the set of all monomials occurring in F ′ . We can assume that T (

G ′ ) = [t 1 < t 2 < • • • < t N ]. It is important to remark that t 1 = u 2,2 up to t (n-1) 2 = u n,n
are in fact variables. Now, let M be the matrix representation of G ′ w.r.t. T (G ′ ). Since we know precisely the shape of the equations from the proof of lemma 5, it is possible to establish that:

1. most of the equations are very sparse, namely each equation contains about n 2 non-zero terms. 2. all the variables t 1 , . . . , t (n-1) 2 occur in all the equations After a Gaussian elimination of the matrix M , we obtain the following shape:

M =       1 (n-1) 2 0 0 0 0 × • • • • • • 0 × . . . . . . 0 × • • • . . .      
Hence, we obtain after a second step of computation in degree 2 the equations u 2,2 = • • • = u n,n = 0. This means that after 2 steps of computation at degree 2, we obtain (n -1) 2 + 2n + n 2 = 2n 2 linear equations in 2n 2 unknowns. This explains why the maximum degree reached during the Gröbner basis computation of I ′ a,b + J ′ is bounded by 2, and concludes the proof of theorem 3. ⊓ ⊔

Application to the Linear Inhomogeneous Case

If c = 0 in equation ( 1), and if a has a non-trivial homogeneous component of degree 1, then looking at the homogeneous component of degree one yields the image of S on one point. We are then in a situation where theorem 3 is applicable, and S can be determined though a Gröbner basis computation which terminates in time O n 6 .

Implementation and Application to the Other Cases

All the other cases reduce to the linear homogeneous case, as mentioned in section 2. In this setting, the problem is that we do not have enough knowledge on S to make the Gröbner basis computation efficient. A simple idea would be to guess a column of S then compute the Gröbner basis. This approach has complexity O n 6 • q n as explained before. It is possible to reduce this complexity by a factor of q, by discarding guesses for the column of S that yields different values of a and b on the corresponding points. The biggest proposed cubic IP1S challenge (Challenge C in fig. 2) has u = 1, n = 16 and q = 2. Given one relation on S, the computation of the Gröbner basis takes 90 seconds on a 2.8Ghz Xeon computer using the publicly available implementation of F 4 in MAGMA. Since this has to be repeated 2 15 times, the whole process takes about one CPU-month (and can be parallelized at will). For challenge D, the Gröbner basis is computed in 0.1 second, and the whole process takes about 2 hours.

An Interesting Failure

We conclude this section with a simple idea that could have lead to an improvement, by efficiently giving a relation on S, but which fails in an interesting manner. Let us denote by Z a (resp. Z b ) the set of zeroes of a (resp. b). Because of lemma 1, and since S is linear, we have:

S x∈Za x = y∈Z b y
This yields a relation on S, which is enough to use theorem 3. a and b may be assumed to have about q n-1 zeroes. Finding them requires time O (q n ). The complexity of the attack could thus be improved to O n 6 + q n . Surprisingly, this trick fails systematically, and this happen to be consequence of the Chevalley-Warning theorem [START_REF] Chevalley | Démonstration d'une hypothèse de M. Artin[END_REF][START_REF] Warning | Bemerkung zur vorstehenden Arbeit von Herrn Chevalley[END_REF].

Lemma 7. The sum of the zeroes of a cubic form on 5 variables or more over F q is always zero.

Proof. Let us consider the elements of Z a having α as their first coordinate, and let us denote by n α their number. These are in fact the common zeroes of (a, x 1 -α). By the Chevalley-Warning theorem [START_REF] Chevalley | Démonstration d'une hypothèse de M. Artin[END_REF][START_REF] Warning | Bemerkung zur vorstehenden Arbeit von Herrn Chevalley[END_REF], if a has at least 5 variables, then the characteristic of the field divides n α . Therefore, their sum has zero on the first coordinate. Applying this result for all values of α shows that the sum of zeroes of a has a null first coordinate. We then just consider all coordinates successively. ⊓ ⊔

Conclusion

In this paper, we present algorithms for the IP problem with one secret for two random quadratic equations and one cubic equation. As already explained, there are the most cryptographically relevant instances. Moreover, we explain the complexity, success probability and give sufficient conditions so that the algorithms work. We combine the use of the differential and the computation of Gröbner bases of very overdefined systems. All the proposed IP1S challenges can be broken in practice by the technique we describe, as the following table shows.

Challenge Time to break on one core A 3 seconds B 1 month C 0 seconds D 1 hours E 3 minutes

In view of these results, we conclude that Patarin's IP1S-Based identification scheme is no longer competitive with respect to others combinatorial-based identification schemes [START_REF] Shamir | An efficient identification scheme based on permuted kernels (extended abstract)[END_REF][START_REF] Stern | A new identification scheme based on syndrome decoding[END_REF][START_REF] Stern | Designing identification schemes with keys of short size[END_REF][START_REF] Pointcheval | A new identification scheme based on the perceptrons problem[END_REF].

Theorem 3 .

 3 | j = 1, . . . , n . The degree of regularity of I a,b + J is 2. Therefore, computing a Gröbner basis of this ideal takes time O n 6 .

Table 1 .

 1 Practical parameters proposed in

	Scheme Common Setting Public Key Secret Key
	PKP	2048 7992	256 512	374 808
	SD	131 072 524 288	256 512	512 1024
	CLE	3600 3600	80 96	80 96
	Perceptron	10807	144	117
	IP1S	0	256	272

Table 2 .

 2 n q Degree Polynomial(s) Public Key Private Key Concrete parameters for IP1S. Patarin proposed challenges A,B,C and D in

	A	16 2	2	2	272 bits	256 bits
	B	16 2	3	1	816 bits	256 bits
	C	6 16	2	2	168 bits	144 bits
	D	6 16	3	1	224 bits	144 bits
	E	32 2	2	2	1056 bits 1024 bits

In the description of some of these schemes, the easily-invertible central map contains parameters that are part of the secret-key. However, in this case there exists an equivalent secret key where these parameters have a fixed value. This is notoriously the case of C * .

more precisely, generically non zero.


Charles Bouillaguet
email: charles.bouillaguet@ens.fr

Orr Dunkelman
email: orr.dunkelman@weizmann.ac.il

Gaëtan Leurent
email: gaetan.leurent@ens.fr

Pierre-Alain Fouque
email: pierre-alain.fouque@ens.fr

Another Look at Complementation Properties

In this paper we present a collection of attacks based on generalisations of the complementation property of DES. We find symmetry relations in the key schedule and in the actual rounds, and we use these symmetries to build distinguishers for any number of rounds when the relation is deterministic. This can be seen as a generalisation of the complementation property of DES or of slide/related-key attacks, using different kinds of relations. We further explore these properties, and show that if the relations have easily found fixed points, a new kind of attacks can be applied. Our main result is a self-similarity property on the SHA-3 candidate Lesamnta, which gives a very surprising result on its compression function. Despite the use of round constants which were designed to thwart any such attack, we show a distinguisher on the full compression function which needs only one query, and works for any number of rounds. We also show how to use this self-similarity property to find collisions on the full compression function of Lesamnta much faster than generic attacks. The main reason for this is the structure found in these round constants, which introduce an interesting and unexpected symmetry relation. This casts some doubt on the use of highly structured constants, as it is the case in many designs, including the AES and several SHA-3 candidates. Our second main contribution is a new related-key differential attack on round-reduced versions of the XTEA block-cipher. We exploit the weakness of the key-schedule to suggest an iterative related-key differential. It can be used to recover the secret key faster than exhaustive search using two related keys on 37 rounds. We then isolate a big class of weak keys for which we can attack 51 rounds out of the cipher's 64 rounds. We also apply our techniques to ESSENCE and PURE.

Introduction

In this paper with study the existence of simple relations that can go trough the rounds of a cipher with a very high probability. For example, in DES if all the key bits are flipped, then all the subkeys are flipped as well. Moreover, if we also negate the plaintext, then all the F functions receive the original input, and the ciphertext is also negated: DES K (P ) = (DES K (P )). This is known as the complementation property of DES.

A similar property is present in one round of AES [START_REF] Le | Complementation-Like and Cyclic Properties of AES Round Functions[END_REF]. If one rotates the columns of an AES state, this rotates the column of the state after SubBytes, ShiftRows, and MixColumns. A study of similarity relations of the AES round operations is done in [START_REF] Le | Complementation-Like and Cyclic Properties of AES Round Functions[END_REF]. The authors show that the rotations by 1, 2 or 3 columns are the only byte-permutation to commute with the AES round. The AES key-schedule is responsible for breaking those symmetry relations and one should be very careful when using the AES round in a new construction. Another well-known example is based on related-key attacks [START_REF] Biham | New Types of Cryptoanalytic Attacks Using related Keys (Extended Abstract)[END_REF][START_REF] Biham | New Types of Cryptanalytic Attacks Using Related Keys[END_REF][START_REF] Knudsen | Cryptanalysis of LOKI91[END_REF] and slide attacks [START_REF] Biryukov | Slide Attacks[END_REF]. In the latter, two plaintexts such that one is the encryption of the other by one round are used. If this is the case, then the ciphertexts are also separated by one round of encryption. Hence, a slid pair (or a related-key plaintext pair) suggests two equations for the round function, which in many cases is sufficient to retrieve the secret key. We note that slide attacks were also adapted for hash functions, where the slide property is used for several attack scenarios [START_REF] Gorski | Slide Attacks on a Class of Hash Functions[END_REF].

In this paper we show new kinds of self-similarity properties in block ciphers and hash functions. The new ideas generalize the previous attacks, by treating a wider set of relations. Moreover, some of the similarity relations we use have fixed points, which is not the case for the complementation property. The keys which are mapped to themselves by the similarity relation can be treated as weak-keys, and they even allow to mount various attacks when the cipher is used to build a hash function.

Deterministic self-similarity properties can usually be detected with a very small number of queries (one or two), over any number of rounds of a cipher, making them very interesting properties to study. However, it should be noted that most attacks involving self-similarity properties are expected to be in the related-key setting and/or will only affect classes of weak keys. This restriction is less problematic in the context of a hash function: there is no secret involved, and the adversary has a greater control over the inputs to the primitive (depending on how exactly the hash function is built, and the attack model).

We also stress that our distinguishers are very simple and efficient, so that they can be practical if the block cipher is used in an unusual setting. For example, a well-known self-similarity property of TEA is that each key has four equivalent keys [START_REF] Kelsey | Key-Schedule Cryptoanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES[END_REF]. 3 This does not seem to be a practical threat for the block cipher (up to a loss of two bits of security in exhaustive search). However, Microsoft used TEA as a hash function in Davies-Meyer mode to enforce limitations on the Xbox, and this weakness of TEA has been used in practice to bypass the security limitations [START_REF] Steil | 17 Mistakes Microsoft Made in the Xbox Security System[END_REF].

We show an example of self-similarity properties in Lesamnta, and discuss a probabilistic self-similarity for ESSENCE . Using this approach we have identified an iterative related-key differential for XTEA. We also find a class of weak keys in the block-cipher PURE.

One of the interesting outcomes of this research, is a new way to tackle round constants. While differing round constants seem to thwart slide attacks, they are not necessarily sufficient to protect against our more generalized approach, as we present in the attack on the compression function of Lesamnta.

Road-map

First we formally define the notion of self-similarity in Section 2, and we show some ways to exploit this property. In particular we discuss new attacks based on keys which are fixed under the similarity relation. Then we show concrete example of self-similarity relation: we study Lesamnta in Section 3, ESSENCE in Section 4, PURE in Section 5, and round-reduced XTEA in Section 6. We conclude the paper in Section 7.

Self-Similarity

Following [START_REF] Barkan | In How Many Ways Can You Write Rijndael[END_REF], we define self-similarity as follows:

Definition 1 (Self-similarity relation in a block cipher). A block cipher E encrypts the plaintext P under the key K to E K (P ). A self-similarity relation is given by invertible and easy to compute transformations4 φ, ψ and θ such that:

∀K, P : θ(E K (P )) = E ψ(K) (φ(P ))
If such relations exists then the cipher is self-dual according to the terminology of [START_REF] Barkan | In How Many Ways Can You Write Rijndael[END_REF]. Similarly, we can define self-similarity for compression functions and for stream ciphers: Definition 2 (Self-similarity relation in a compression function). A compression function H maps a chaining value X and a message M to a new chaining value H(X, M ). A self-similarity relation is given by invertible and easy to compute transformations φ, ψ and θ such that:

∀X, M : θ(H(X, M )) = H(φ(X), ψ(M ))
Definition 3 (Self-similarity relation in a stream cipher). A stream cipher G generates the key-stream G K (I) with the key K and the IV I. A self-similarity relation is given by invertible and easy to compute transformations φ, ψ and θ such that:

∀K, I : θ(G K (I)) = G ψ(K) (φ(I))
We say that a set of transformation is a weak self-similarity if this relation only holds with a probability which is less than 1 (but higher than for a random permutation). These definitions are wide enough to include several types of known attacks such as the complementation property of DES, for which φ = ψ = θ, and φ(x) = x.

The notion of self-similarity is quite broad. For example, the following known results can be seen as self-similarity properties:

-The complementation property of DES and LOKI [START_REF] Kwan | A General Purpose Technique for Locating Key Scheduling Weakness in DES-like Cryptosystems (Extended Abstract)[END_REF]:

ψ(K) = K ⊕ ∆ φ(P ) = P ⊕ ∆ θ(C) = C ⊕ ∆
-The equivalent keys of TEA [START_REF] Kelsey | Key-Schedule Cryptoanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES[END_REF]

ψ(K) = K ⊕ ∆ φ(P ) = P θ(C) = C
-The recently found weakness in the compression function of the SHA-3 candidate CHI [START_REF] Aumasson | Observation on the PRE-MIXING step of CHI-256 and CHI-224[END_REF]:

ψ(K) = K φ(P ) = P θ(C) = C
It is possible to consider high probability differentials as (weak) self-similarity properties. For example, in Section 6 we present some iterative related-key differential for XTEA that was found using the self-similarity approach.

In this paper, we will consider iterated self-similarity properties. Let E be a cipher defined by the iteration of a round function F , with the subkeys RK i derived for the master key K by a function G: RK i = G(K, i), i.e., the cipher can be described as:

RK i = G(K, i) X 0 = P X i+1 = F (X i , RK i ) E K (P ) △ = X r .
We look for a self-similarity property of the round function F , i.e., two transformations Θ, Ψ such that Θ(F (X, RK )) = F (Θ(X), Ψ (RK )). Then assuming we can find (or construct) K, K ′ such that G(K ′ , i) = Ψ (G(K, i)), we have E k ′ (θ(P )) = θ(E k (P )). Note that the relation we are using on the subkeys is defined as RK ′ i = Ψ (RK i ): each subkey of the second cipher is related to the corresponding subkey of the original cipher. This is in contrast with related-key attacks where the relation is RK ′ i+1 = RK i .

Attacks Based on Self-Similarity

Self-similarity properties obviously offer an efficient distinguisher in the relatedkey setting. If one is given access to an oracle E K * and an oracle E ψ(K * ) for an unknown K * , he can distinguish the block cipher E from an ideal cipher by querying E K (P ) and E ψ(K) (φ(P )) for a random P . Moreover, a self-similarity property can be used to speed up the exhaustive search of the key by a small factor, as explained in [START_REF] Biham | New Types of Cryptoanalytic Attacks Using related Keys (Extended Abstract)[END_REF]. Let n be the size of the longest cycle of the permutation ψ. In most cases, n will be quite small (if n is big then the attack will actually be more efficient). Then, query C i = E K * (φ (i) (P )) for i ∈ 0, 1, . . . , n -1, and compute C i = θ (-i) (C i ). Now, compute E K (P ) for a set of keys K and look for a match with one of the C i . If there is a match, then ψ (i) (K) is likely to be the key:

E K (P ) = C i ⇐⇒ E K (P ) = θ (-i) (C i ) ⇐⇒ E ψ (i) (K) (φ (i) (P )) = C i = E K * (φ (i) (P )).
The idea of the attack is that the set of tested keys has to include only one key per each cycle of ψ. Each time a new E K (P ) is computed, this allows to test all the key candidates in the cycle of K, by applying θ iteratively to the obtained ciphertext, and comparing the resulting ciphertext with the respective pre-computed ciphertext. Hence, if the evaluation of θ is faster than E ψ(K) , one can reduce the time of exhaustive search.

Attacks Based on Fixed points of Self-Similarity relations

Some of the φ and ψ relations that we show have a large number of fixed points. These points can be used in several different attack scenarios. The fixed points of ψ will be weak key, so we consider the fixed points of φ as weak plaintexts.

First, let us show that the set of the fixed points of ψ is a weak-key class. If a weak plaintext is encrypted under a weak key, the ciphertext will also be a fixed point of the similarly relation, i.e., θ(C) = θ(E K (P )) = E ψ(K) (φ(P )) = E K (P ) = C. This allows to distinguish the weak keys with a single query using a weak plaintext.

In the context of hash functions, fixed points in the similarity relations allow to find collisions in the compression function more efficiently than exhaustive search. One just has to evaluate the compression function on weak inputs, and the output would lie in the set of fixed point of θ. Note that the attack becomes more efficient when the number of fixed-points in θ becomes smaller.

In Section 3.1 we show how to use the self-similarity property of Lesamnta to reduce its security in several usage scenarios. These attacks are based on the idea that one can randomly reach a fixed point of φ, and from there it is easy to reach any fixed point of θ. In this case, the attacks become more efficient when the number of fixed points of φ grows.

Xi+4 Xi+3 Xi+2 Xi+1 Ki+4 Ki+3 Ki+2 Ki+1 Xi+3 Xi+3 Xi+1 Xi Ki+3 Ki+2 Ki+1 Ki F ⊕ ⊕ G ⊕ ⊕ Ri+3
Fig. 1. The Round Function of Lesamnta. This Round Function is Iterated 32 Times.

A Short Description of Lesamnta. Lesamnta is a hash function proposal by Hirose, Kuwakado, and Yoshida as a candidate in the SHA-3 competition [START_REF] Hirose | SHA-3 Proposal: Lesamnta[END_REF]. It is based on a 32-round unbalanced Feistel scheme with four registers used in MMO mode. The key schedule is also based on a similar Feistel scheme. The round function is described by Figure 1 and can be written as:

X i+4 = X i ⊕ F (X i+1 ⊕ K i+3 ) K i+4 = K i ⊕ G (K i+1 ⊕ R i+3 )
where R 0 , . . . , R 31 are round constants, the state register X is initialized with the message in X -3 , X -2 , X -1 , X 0 , and the key register is initialized with the chaining value in

K -3 , K -2 , K -1 , K 0 . The output of the compression function is X -3 ⊕ X 29 , X -2 ⊕ X 30 , X -1 ⊕ X 31 , X 0 ⊕ X 32 .
Lesamnta has two main variants: Lesamnta-256 with 64-bit registers (hence, a message block and chaining value of 256 bits), and Lesamnta-512 with 128-bit registers (hence, a message block and chaining value of 512 bits).

The round functions F and G are inspired by the AES round function. F uses four round of transformations similar to SubBytes, ShiftRows and MixColumns, while G uses only one round of similar transforms. The transformations used in F and G are different, even though they are both heavily inspired by the AES. In Lesamnta-256 a 64-bit register is represented by a 2-by-4 byte matrix in F , and by a 4-by-2 matrix in G. In Lesamnta-512, a 128-bit register is seen as a 4-by-4 matrix. The round constants are defined by a simple counter: R i = 2i+(2i+1)•2 32 for Lesamnta-256 and R i = 2i + (2i + 1) • 2 64 for Lesamnta-512. For more details, we refer the reader to the full specification [START_REF] Hirose | SHA-3 Proposal: Lesamnta[END_REF].

The Self-Similarity Relation of Lesamnta. The round functions F and G are very similar to the AES round function, and they have the same self-similarity property: if the two halves of the input are swapped, then the output is also swapped. Indeed, it is easy to see that SubBytes, ShiftRows and MixColumns do have this property. However, the key-schedule of Lesamnta includes round constants R i to avoid symmetry-based attacks.

Luckily, these constants are word-symmetric up to the least significant bit. More precisely, if

R i = (R ⊤ i R ⊥ i )
, where the top and bottom parts of R i are 32-bit (64-bit in Lesamnta-512), then the only difference between R ⊤ i and R ⊥ i is in the least significant bit.

Let us introduce a few notations. We say that two words x and y are "halfswapped" if the top half of x (denoted by x ⊤ ) is the bottom half of y (denoted by y ⊥ ), and vice-versa. We denote the half-swapped value of x = (x ⊤ x ⊥ ), i.e., (x ⊥ x ⊤ ), by ← → x . We also formalize the structural property of the round constants: we define x to be (x ⊥ ⊕ 1 x ⊤ ⊕ 1). Then, the following property of rounds constants holds: R i = R i . We extend these two relations to vectors of words in the natural way, namely, (x, y) = (x ′ , y ′ ) if x = x ′ and y = y ′ .

Our idea is to combine the swapping of halves of the state with flipping the least significant bit of each half to compensate the difference in the constants. The swapping commutes with the round functions F and G, and the masking is canceled by the Feistel structure. For this purpose, let us mention the following useful properties:

i) x ⊕ y = ←-→ x ⊕ y ii) x ⊕ ← → y = x ⊕ y
Hence, consider a master keys K of 4 words, and let K ′ = K, i.e., by definition,

K ′ -3 = K -3 , . . . , K ′ 0 = K 0 . The first property implies in particular that K ′ -2 ⊕ R 0 = ← -----→ K -2 ⊕ R 0 .
Therefore, when computing K 1 and K ′ 1 , the two values that enter G are half-swapped. This property goes through all the successive operations in G (SubWords, KeyLinear, and ByteTranspose5 ). The output of G is therefore half-swapped as well. Then, thanks to the second property, and thanks to the fact that K ′ -3 = K -3 , we find that K ′ 1 = K 1 . This argument can be iterated, and shows that if the master keys are related, then all the other subkeys are related (we have K ′ i = K i for all i). Now, it is easy to see that as the subkeys in the two concurrent hash processes are related and at the same time so are the "plaintexts", then the same relation will be maintained through the rounds. Specifically, let the plaintexts be P and P ′ = P . By definition again, we have X ′ -3 = X -3 , . . . , X ′ 0 = X 0 . The argument above repeats: we have X ′ -2 = X -2 , K ′ 0 = K 0 , and thanks to the first property, the input of F is half-swapped. This property goes trough F , and since X ′ -3 = X -3 , the second property grants us X ′ 1 = X 1 . This argument can be iterated again, and shows that X ′ i = X i , for all i. Lastly, there is a feed-forward operation: the output of the compression function is Y 0 = X -3 ⊕ X 29 , . . . , Y 3 = X 0 ⊕ X 32 . Thanks to the first property again, we find that Y ′ = ← → Y . This yields:

CF ( K, M ) = ← ------→ CF (K, M )
Self-Similarity of Lesamnta. Finally, we note that if we pick a chaining value h which is weak (i.e., h = h), and a message block m which is also weak (i.e., m = m), then CF (h, m) is weak as well, but in a different manner (we have

CF (h, m) = ← -----→ CF (h, m))
, and this can be easily identified (the top and bottom halves of each output word are the same). Hence, it is possible to distinguish the compression function of Lesamnta using one single query. For example, in Lesamnta-256

h = m =
(00000000, 00000001), (00000000, 00000001), (00000000, 00000001), (00000000, 00000001)

leads to CF (h, m) = (52afa888, 52afa888), (61c0aebc, 61c0aebc), (1c9d4d3a, 1c9d4d3a), (95f45a98, 95f45a98)
and in Lesamnta-512

h = m =    
(0000000000000000, 0000000000000001), (0000000000000000, 0000000000000001), (0000000000000000, 0000000000000001), (0000000000000000, 0000000000000001)

    leads to CF (h, m) =    
(b0421baf4899c67e, b0421baf4899c67e), (e6b528589fadd0ce, e6b528589fadd0ce), (3547c4021eb4c7ee, 3547c4021eb4c7ee), (a8188b26052d044d, a8188b26052d044d)

   
Following our findings, the designers of Lesamnta decided to tweak the algorithm by changing the round constants. For the tweaked version we refer the reader to [START_REF] Hirose | Security Analysis of the Compression Function of Lesamnta and its Impact[END_REF].

Using These Properties on the Full Lesamnta

Faster Collisions in the Compression Function. It is possible to use the above property to find collisions in the compression function faster than exhaustive search. We pointed out that if we pick weak inputs, h = h and m = m, then each of the four output words has the same top and bottom halves. In other words, the output of the compression function is restricted to a subspace of size 2 n/2 for Lesamnta-n.

Hence, by taking 2 n/4 pairs of (chaining values, message blocks) which are weak, we expect to find a collision in the output of the compression function.

Second Preimage Attack on Weak Messages. The self-similarity property of the compression function induces a set of weak messages. In such messages, one of the chaining values h i (which is the output of the compression function) encountered during the hash process is such that h i = ← → h i , i.e., it is of the form h i = (S||S), (U ||U ), (W ||W ), (Y ||Y ). A random (r + 1)-block long message is in the weak set with probability r • 2 -n/2 . We now discuss how to find a second preimage of a weak message in time 2 n/2 and negligible memory. Finding a new message of (i -1) blocks yielding the chaining value h i immediately yields a second preimage on the full hash function. To do so, an adversary may follow these steps:

1. Choose an arbitrary prefix of (i -2) message blocks. 2. Find a message block which yields a weak chaining value h i-1 . Since there are 2 n/2 such chaining values, it is expected that 2 n/2 random trials are sufficient. 3. Find a weak message block m such that CF (h i-1 , m) = h i . On average, for each starting chaining value, there is one such message block, amongst 2 n/2 possible choices. Thus, about 2 n/2 random trials are expected to be necessary. 4. Concatenating all parts with the suffix of the original message starting from the i-th block yields a second preimage.

The total complexity of the process is 2 n/2 .

Herding Attack on Lesamnta. The self-similarity property of the compression can be used to propose a better herding attack on Lesamnta than the one of [START_REF] Kelsey | Herding Hash Functions and the Nostradamus Attack[END_REF].

In the herding attack, the adversary commits to a hash value H * , and is given a challenge message M afterwards. His goal is to find a suffix S such that H(M S) = H * . The generic herding attack on hash functions of n bits presented in [START_REF] Kelsey | Herding Hash Functions and the Nostradamus Attack[END_REF] requires an offline time complexity of 2 (n+ℓ)/2+2 online time complexity of 2 n-ℓ and memory of 2 ℓ+1 . We now present a customized herding attack using self-similarity for Lesamnta with complexity 2 n/2 and negligible precomputation and memory.

1. Choose a weak chaining value h * , and choose an upper-bound L on the number of message blocks of the prefix M . Then, compute the finalization function on h * , assuming a message of L + 2 full blocks. This yields the committed value H * (of a message of length L + 2 blocks). 2. Receive the challenge M , and append random suffixes S of L + 1 -|M | blocks, until hitting a weak chaining value h. It is expected that 2 n/2 random trials are sufficient. 3. Try random weak message blocks S ′ . We know that H(M S S ′ ) is weak, with H(M S S ′ ) = ← -------→ H(M S S ′ ). Therefore, we expect to reach h * after only 2 n/2 trials. 4. Output M S S ′ as the answer to the challenge.

Distinguishing-H Attack on HMAC. The self-similarity property can also be used to distinguish HMAC-Lesamnta from HMAC instantiated with another PRF. The distinguisher follows the ideas of Wang et. al in [START_REF] Wang | Cryptanalysis on HMAC/NMAC-MD5 and MD5-MAC[END_REF], and the complexity would be 2 3n/4 . We note that this line of research may not be harmful, as distinguishing HMAC from PRF (for any hash function) has a complexity of 2 n/2 . We also note that the claimed security level of HMAC-Lesamnta is only 2 n/2 .

Application to ESSENCE

R i R i+1 R i+2 R i+3 R i+4 R i+5 R i+6 R i+7 F L ⊕ ⊕ ⊕ K i K i+1 K i+2 K i+3 K i+4 K i+5 K i+6 K i+7 F L ⊕ ⊕
Fig. 2. ESSENCE Round Function (iterated 32 times).

Description of ESSENCE . ESSENCE is a hash function proposal by Martin

as a candidate in the SHA-3 competition [START_REF] Martin | ESSENCE: A Candidate Hashing Algorithm for the NIST Competition[END_REF]. The design is based on two shift registers with 8 words each. One shift register is used to expand the message by generating subkeys, while the other processes the chaining value with the subkeys.

R i+8 = R i ⊕ F (R i+1 , R i+2 , . . . , R i+7 ) ⊕ L(R i+7 ) ⊕ K i K i+8 = K i ⊕ F (K i+1 , K i+2 , . . . , K i+7 ) ⊕ L(K i+7 )
The feedback function is designed with two functions: a non-linear bit-wise function F , and a linear function L that mixes the bits inside the words. The linear function is based on clocking an LFSR a fixed number of times. The chaining value is loaded into R -7 , R -6 , . . . , R 0 , while the message block is loaded into K -7 , K -6 , . . . , K 0 . After 32 rounds, the output is computed as

R -7 ⊕ R 25 , R -6 ⊕ R 26 ,. . . , R 0 ⊕ R 32 .
ESSENCE has two main variants: ESSENCE -256 with 32-bit words (hence a message block and a chaining value of 256 bits each), and ESSENCE -512 with 64-bit words (hence a message block and chaining value of 512 bits). The best known attack on ESSENCE is a collision attack with complexity 2 68 [START_REF] Naya-Plasencia | Cryptanalysis of ESSENCE[END_REF]. The design of ESSENCE uses no constants. Therefore, it is possible to build a distinguisher against ESSENCE using a slide attack [START_REF] Mouha | Observations of non-randomness in the ESSENCE compression function[END_REF].

The Self-Similarity Relation. Most of the components used in ESSENCE are bitwise, and the L is the only part responsible of mixing the bits of the words. Moreover, it is based on an LFSR, and LFSRs have a good behavior with regards to rotations. More precisely we have Pr(L(x ≪1 ) = L(x) ≪1 ) = 1/4 as shown in Figure 3. Therefore, we can build a new self-similarity attack based on rotating the message and the chaining value. This gives subkeys such that K ′ i = K ≪1 i as opposed to K ′ i = K i+1 in the slide attack. More precisely, we consider the following relation: Constructing a Good Pair. Let us rotate the master key:

K ′ i = K ≪1 i R ′ i = R ≪1 i x0, x1 xn-1 x1 xn-1, xn xt xt+n-1 t -1 step x1 xn-1, x0 xt, xt+1 xt+n-1 t -1 step xt+1 xt+n-1, xt+n = x x ′ = if x0 = xn = F (x) F (x ′ ) = if xt = xt+n
K ′ -7 = K ≪1 -7 , K ′ -6 = K ≪1 -6 , . . . , K ′ 0 = K ≪1 0 .
For each round, there is a probability 1/4 that the new subkey K ′ i is equal to K ≪1 i , because we only need the LSFR-based function to commute with a rotation of 1 bit. The full compression function uses the subkeys K -7 to K 24 , so a random message K and its related message K ′ will give related subkeys with probability 2 -48 .

To find a suitable chaining value we will use something similar to message modification techniques to get 8 rounds for free. We start from round 31 (one before the last round) and make a random choice of R 24 , R 25 , . . . , R 31 such that each of these value satisfy

L(R ≪1 i ) = L(R i ) ≪1 . We use the related state R ′ 24 = R ≪1 24 , R ′ 25 = R ≪1 25 ,. . . , R ′ 31 = R ≪1 31 .
We first compute round 32 forward, and R 32 follows the relation with probability 1 because the non bitwise part is L(R 31 ) and R 31 was chosen so that L(R ≪1 31 ) = L(R 31 ) ≪1 . Then we compute the remaining round backwards and check that the new values still satisfy

R ′ i = R ≪1 i : R i = R i+8 ⊕ F (R i+1 , R i+2 , . . . , R i+7 ) ⊕ L(R i+7 ) ⊕ K i .
In rounds 23, 22, . . . , 17, the non-bitwise part is respectively L(R 30 ), L(R 29 ), . . . , L(R 24 ) so they go through with probability 1. Then, we compute rounds 16 to -7, and each of cost a probability 1/4. In total we have a probability 2 -48 that a random choice of R 25 , R 26 , . . . , R 32 gives a correct chaining value. Hence, with complexity 2 48 , we can construct a pair of messages and chaining values such that:

K ′ = K ≪1 R ′ = R ≪1 G(K ′ , R ′ ) = G(K, R) ≪1
It might be possible to use advanced message modifications to further improve this complexity.

Application to PU RE

PURE is a block cipher introduced by Jakobsen and Knudsen to demonstrate the interpolation attack [START_REF] Jakobsen | The Interpolation Attack on Block Ciphers[END_REF]. It is designed as a block cipher with a very strong algebraic structure, and good resistance to differential and linear cryptanalysis. However, it is weak against algebraic attacks, which was the point of the article. Later, Buchmann et al. defined Flurry, which can be seen as a generalized version of PURE with a key schedule [START_REF] Buchmann | Block Ciphers Sensitive to Gröbner Basis Attacks[END_REF]. Again, the point of Flurry was to show that a block cipher can be secure against differential and linear cryptanalysis, but weak against algebraic attack (Gröbner basis techniques in the case of Flurry). PURE and Flurry are not to be used as real ciphers, but serve as demonstration that algebraic attacks can be useful against ciphers with a very strong algebraic structure.

By applying a self-similarity attack to PURE, we intend to show that the algebraic structure of a block cipher can be used to mount a simple self-similarity attack that does not need complex polynomial computation (as opposed to the interpolation attack or Gröbner basis techniques). Moreover, we build a distinguisher with only one query as well as a class of weak keys, both for any number of round, whereas the previous algebraic attacks could only break a limited number of rounds.

Description of PU RE. PURE is a simple Feistel cipher with a monomial S-Box. All the operations are carried in the finite field F 2 m ;6 the plaintext is composed of two field elements, and the key is given as r field elements, where r is the number of rounds:

L 0 = P L R 0 = P R L i+1 = R i R i+1 = L i ⊕ (R i ⊕ K i ) 3 .
There is no key schedule in PU RE, the key is given as r field elements K 0 , K 1 , . . . , K r-1 which are used as round subkeys.

The Self-Similarity Relation. Because of the strong algebraic structure of PURE, it is natural to look for algebraic relations. In particular we can use the Frobenius mapping (x → x 2 ) in the field F 2 m : it commutes with any monomial S-Box, and it is linear. It is straightforward to check that the following is a self-similarity relation for PU RE:

θ(z) = ψ(z) = φ(z) = z 2
More precisely, if K ′ i = K 2 i for all rounds and

P ′ L = P 2 L , P ′ R = P 2 R , then we will have L ′ i = L 2 i and R ′ i = R 2
i for all rounds. This gives a very efficient distinguisher for PU RE in the related-key setting. However, we note that since PURE has no key-schedule, it is trivial to make a related-key attack. Nevertheless, a slight generalization of this initial observation leads to the discovery of a class of weak keys for PU RE.

A Class of Weak Keys. Given some α ∈ F 2 m , and 0 < k < m, we now consider the following self-similarity relation:

θ(z) = ψ(z) = φ(z) = z 2 k ⊕ α ⊕ α 2 k
Again, it is easy to check that this is actually a self-similarity. If

K ′ i = ψ(K i ), L ′ i = φ(L i ) and R ′ i = φ(R i
), then we have:

R ′ i+1 = L ′ i ⊕ (R ′ i ⊕ K ′ i ) 3 = L 2 k i ⊕ α ⊕ α 2 k ⊕ (R i ⊕ K i ) 2 k 3 = L i ⊕ (R i ⊕ K i ) 3 2 k ⊕ α ⊕ α 2 k = φ(R i+1 )
It must be noted that φ cannot be the identity, thus it can actually be used to distinguish PU RE used with a weak key from a random function. The weak keys are the fixed points of ψ. Now, if k divides m, then x → x 2 k admits all the subfield F 2 k as fixed points, which means that when K i = α + x i , with x i ∈ F 2 k , then the key is weak. It is possible to check this with only one query: just encrypt (α, α), and test the ciphertext for self-similarity. Testing all the possible α's requires 2 m queries. With k = m/2, this yields 2 m+rm/2 weak keys out of 2 mr .

Bad Key-Schedules. A consequence of the previous observation is that there many bad key-schedules for PURE. For example, let us consider the following key schedule based on a Feistel scheme with the same monomial S-Box:

K 0 = K L , K 1 = K R K i+2 = K i ⊕ (K i+1 ⊕ C i ) 3 (if i < r -1)
The C i 's are round constants. Their purpose is to break the regularity and avoid slide attacks. However, we now know that if the round constants can be written

C i = α + x i , with
x i in a subfield, then weak keys exist for the full scheme. For example, C i = α and C r-1 = α + 1 avoids slide properties, but is still a very bad choice since it exhibit weak keys.

Application to XTEA

XTEA is a block cipher designed by Needham and Wheeler. It is a Feistel network that encrypts 64-bit plaintexts with a a 128-bit key. The round function is pretty simple, and the security relies more on the high number of times it is iterated: 64 rounds are the recommended setting.

Description of XTEA. The Feistel structure of XTEA can be described as:

L i R i L i+1 R i+1 RK i ≪ 4 ≫ 5 ⊕ ⊞ ⊕ ⊞ L 0 = P L R 0 = P R L i+1 = R i R i+1 = L i ⊞ (F (R i ) ⊕ RK i ) F (x) = ((x ≪ 4) ⊕ (x ≫ 5)) ⊞ x
The key schedule is rather simple: the master key K is made of four 32-bit words, and the 32-bit round key RK i is generated from the master key:

RK 2i = (i • δ) ⊞ K ((i•δ)≫11) mod 4 RK 2i+1 = ((i + 1) • δ) ⊞ K ((i+1)•δ) mod 4
where δ = 0x9E3779B9 is a constant derived from the golden ratio.

Currently, the best known attack on XTEA is the one from [START_REF] Lu | Related-key rectangle attack on 36 rounds of the XTEA block cipher[END_REF], which can break up to 36 rounds of XTEA in the related-key model (with four keys) using 2 65 chosen plaintexts and 2 126.44 time (or 2 64 chosen plaintexts and 2 104 time for a weak-key class of 2 111 weak keys).

The Self-Similarity Relation. The idea of our attack on XTEA is inspired by the complementation property of the DES. In a complementation property, the difference in the plaintext and the difference in the key cancel each other before entering the F function. Such attacks are possible if the key schedule allows a fixed difference in all the subkeys. The key schedule of XTEA is weak enough to do so, but the key is added after the F function, to prevent the complementation property. However, if there is a good differential characteristic α → β in the F function, we can put a difference α in the plaintext, and a difference β in the key to cancel it after the F function. This gives an iterative related-key differential characteristic.

L i ⊕ M R i ⊕ M L i+1 ⊕ M R i+1 ⊕ M K i ⊕ M ⊕ F ⊕ Complementation property L i ⊕ α R i ⊕ α L i+1 ⊕ α R i+1 ⊕ α K i ⊕ β ⊞ F ⊕ RK iterative differential on XTEA
More precisely, in the case of XTEA, we use the following weak self-similarity:

ψ(K i ) = K i ⊞ 2 31 ⊞ 2 26 φ(L i , R i ) = θ(L i , R i ) = L i ⊞ 2 31 , R i ⊞ 2 31
Because of the key-schedule, we have that if K ′ = ψ(K), then RK ′ i = ψ(RK i ). We also use the fact that:

F (x ⊞ 2 31 ) = F (x) ⊞ 2 31 ⊞ 2 26 or F (x) ⊞ 2 31 ⊟ 2 26
Therefore, the differences will cancel out (and the self-similarity will hold for the round function) as long as the carries in F (x) ⊞ 2 31 ± 2 26 are the same as the carries in K i ⊞ 2 31 ⊞ 2 26 . For a given key K, we can compute the carries in each round, and deduce the probability of the differential characteristic (which will be the probability that the self-similarity relation holds). For example if there is no carry in the key, then there is a probability 1/2 that there will also be no carry in the F function. If there is a one-bit carry in the key, there is a probability 1/4 that there will be exactly a one-bit carry in the F function.

The probability of the differential path is therefore quite dependent on the key. However, we know exactly the subsets of the key space that correspond to a given set of carries. Therefore, we can count the number of keys giving a specific probability for the self-similarity relation (Figure 4 shows the number of keys yielding a specific number of carries). We discuss two possible attack scenarios: attacking all the keys, and attacking a class of weak keys. Note that due to the irregular key schedule, we may obtain better attacks by selecting a subset of the rounds that do not start at round 0.

Attacking All the Keys. If we consider rounds 19 to 50, the self-similarity relation holds with probability greater than 2 -60 for about half of the keys. If we consider 2 62 message pairs, there is a good probability to have a right pair. If so, we can use it to recover the key, with 5 extra rounds by guessing K 2 and K 3 (which are the two keys words affecting the subkeys of these rounds). Now assume that the self-similarity holds with probability greater than 2 -60 for a given key, then we expect at least 4 right pairs. A wrong subkey guess is expected to lead to about 2 -2 = 1/4 pairs which allegedly satisfy the selfsimilarity property. Hence, if we consider only key proposals for K 2 and K 3 which suggest two or more pairs, we expect to deal with 2 64 • 2 -5.23 < 2 59 remaining wrong subkeys (while the probability of discarding the wrong value is only 9.2%). Hence, exhaustive search over the remaining possibilities would take less time than required for the partial decryption. Moreover, it is possible to discard wrong guesses for K 2 and K 3 , as all the pairs must offer the same number of carries in round 19 and round 50. If this is not the case, then the subkey guess is necessarily wrong.

Finally, we note that if the above attack fails, the adversary learns with very good probability that the key is in the subset with more than 60 carries, which reduces the search space by 1/2. This gives an attack on 37 rounds (19 to 55), with data complexity 2 63 , and time complexity 2 125 on average.

Attacking a Class of Weak Keys. If we consider rounds 9 to 55, we have a weak key class with only 60 carries, which contains 2 107.5 keys out of 2 128 . We can attack a key in this weak key class using 2 62 message pairs. Once a good pair exist, we can use it to recover the key, with 4 extra rounds by guessing K 2 and K 3 . This gives an attack on 51 rounds (9 to 59), with data complexity of 2 63 chosen plaintexts, and time complexity 2 123 on average, for a weak key class of size 2 107. 5 .

A similar attack can be applied to XXTEA by changing ψ(K i ) = K i ⊞ 2 32 ⊞ 2 26 ⊞ 2 28 . However, it can only be applied against very reduced version since each two carry chains have to be equal for each round.

Conclusion

This work shows one more time that symmetry in the building blocks of a cryptographic primitive can be dangerous. We have shown new ways to build symmetry relations based on rotations or algebraic expressions. We have also described new attacks based on these relations when there exists key and/or plaintexts which are fixed under the similarity relations. The common way to avoid such symmetries is to include round constants (either in the key schedule or in the actual rounds). However, our results on the hash function Lesamnta show that if the constants suggest some self-similarity property, it may interact with other components to suggest a self-similarity property of the entire primitive. Hence, we conclude that some round constants can be weaker than others, and that highly structured round constants should be avoided.

Fig. 3 .

 3 Fig. 3. Symmetry relation on an LFSR-based function. L is a linear function defined by clocking an LFSR a fixed number of times. If the initial state of the LFSR is rotated by 1 place, there is a probability 2 -2 that the output state is rotated as well.

Fig. 4 .

 4 Fig.4. Distribution of the number of carries in rounds 19-50 of XTEA. log 2 of the number of keys with a given number of carries. 48% of the keys have less than 60 carries, and 52% have less than 61 carries.

We note that this property is commonly described as a related-key differential with probability 1, or a complementation property.

In this context, and for the reminder of the paper, we require that at least one of the three transformations φ, ψ, and θ is not the identity.

Application to LesamntaOur most interesting result is a self-similarity property of Lesamnta. This selfsimilarity property is based on swapping the two halves of the state and XOR-ing them with a constant. The most surprising part about this property is that it can actually deal with the round constants, which are supposed to break all symmetry relations.

We note that in the submission document[START_REF] Hirose | SHA-3 Proposal: Lesamnta[END_REF] the term "ByteTranspos" is used.

In the original description of PURE, m was in fact 32, which yields a 64-bit cipher.

Acknowledgements

We would like to thank the Lesamnta team, and especially to Hirotaka Yoshida for the fruitful discussions.