Lydie Le Forestier

Mikael Motelica-Heino

Philippe Le Coustumer

Michel Mench

Ecodynamique

Ecodynamique d'éléments traces en contexte de phytostabilisation aidée par des laitiers dans un sol sableux contaminé en cuivre

teaching and research institutions in France or abroad, or from public or private research centers.

Haricot = indicateur de biodisponibilité du Cu

(2)

(1)

(3) • Les amendements (laitiers) permettent d'abattre la fraction disponible de Cu (pool labile et dissous vrai).

• Le sol de prairie présente des valeurs en total dissous plus faibles, mais supérieures au sol de contrôle.

Cu (mg kg -1 ) < 5 < 5

As (mg kg -1 ) < 5 < 5 Cr (mg kg -1 ) 511 900 Zn (mg kg -1 ) 24 < 5

Sol PLDS Sol CARMEUSE pH 8,3 ± 0,1 8,0 ± 0,1 EC (mS cm -1 )

184 ± 11,9 201,3 ± 5,5

Premières feuilles de haricot séchées à l'étuve à 70°C puis pesées La minéralomasse en Cu est la plus faible pour le sol de contrôle CTRL, puis pour le sol de prairie M. Elle est 2 fois plus élevée pour le sol amendé au laitier PLDS que pour CARMEUSE.

La minéralomasse en Cu pour le sol UNT est intermédiaire avec une forte variabilité.

• Dans les sols non amendés UNT et M, le Cu est surtout associé à la fraction oxydable donc aux oxyhydroxydes de Fe et Mn, puis à la fraction résiduelle, et enfin associé à la fraction réductible donc à la matière organique.

• Dans les sols amendés aux laitiers, le Cu se trouve surtout dans la fraction résiduelle. L'ajout de laitiers permet d'augmenter significativement la fraction non remobilisable.

• Sol UNT Sol M Sol CTRL pH 6,4 5,4 ± 0,4 7,01 EC (mS cm -1 ) 61,2 ± 19,8 86,3 169 ± 22 C total (g kg -1 ) 32,6 ± 3,5 83,9 ± 26,2 COT (g kg -1 )

4,9 ± 0,4 10,4 40,4 SiO 2 (g kg -1 ) 661,4 ± 55,9 673,1 ± 149,2 Al 2 O 3 (g kg -1 ) 165,1 ± 29,3 132.1 ± 66,8 Fe 2 O 3 (g kg -1 ) 40,8 ± 7,9 41,8 ± 20,7 CaO (g kg -1 )

15,8 ± 21,8 3,2 ± 0,4 MgO (g kg -1 )

3,9 ± 0,6 4,3 ± 1,9 Na 2 O (g kg -1 )

1,3 ± 0,9 1,9 ± 1,1 TiO 2 (g kg -1 ) 2,7 ± 0,2 10,5 ± 14,2 P 2 O 5 (g kg -1 )

2,4 ± 0,3 2,2 ± 0,9

Sol UNT Sol M Sol CTRL Réf. sol sableux (Baize, 1997) Cu (mg kg -1 ) 3003 ± 719 888 21,5 3,2 -8,4

As (mg kg -1 ) 18 ± 2 9 ± 2 3,6 1 Cr (mg kg -1 ) 38 ± 6 27 ± 2 17,9 14,1 -40,2 Zn (mg kg -1 ) 118 ± 13 77 ± 14 50,9 17 -48

  Ce site constitue la plateforme BIOGECO: les sols sont gérés par des solutions de phytoremédiation, dont la phytoextraction (tournesol, tabac) et la phytostabilisation (saule, peuplier, graminées) aidée ou non par des amendements organiques (compost) et minéraux (dolomie, fer zérovalent et laitiers).Contamination :-Sulfate de cuivre(utilisé entre 1913 et 1980) -Arséniate de Cuivre Chromé (CCA)(utilisé de 1980 à 2006) Vue des lysimètres sur le site• 450 g de sol équivalent sec par pot• Sol maintenu à 50% de WHC (Water Holding Capacity), i.e. de la capacité de rétention maximale en eau du sol, par ajout d'eau déionisée • 4 graines de haricot nain (préalablement germés dans du coton humide) plantés dans chaque pot • Eclairage avec lampe: 21°C, cycle journalier 16h éclairage / 8h nuit • Durée de la croissance = 21 jours • 3 réplicats pour chaque type de sol EC = conductivité électrique Carbone total dosé par analyseur élémentaire LECO COT = carbone organique total dosé par Rock Eval Eléments majeurs dosés par ICP-ES  Mésocosmes  Caractéristiques des amendements Deux laitiers d'aciérie ont été utilisés comme amendement: • PLDS (P-spiked Linz-Donawitz Slag): laitier enrichi en phosphore (Negim et al., 2012) • CARMEUSE : laitier de la société Carmeuse L'amendement a consisté à ajouter 1 g de laitier dans 100 g de sol UNT = sol contaminé et non traité PLDS = sol contaminé, végétalisé avec Agrostis gigantea et un peuplier (Populus trichocarpa x deltoides cv Beaupré) (= végétaux de type excluders, stockant Cu dans leurs racines) et amendé avec des laitiers d'aciérie enrichis en phosphore (P-spiked LD slag) CARMEUSE= sol contaminé, végétalisé avec la rotation tournesol/tabac et amendé avec des laitiers d'aciérie de l'entreprise Carmeuse M = sol prélevé dans la prairie à proximité du site CTRL = sol de jardin non contaminé, prélevé à quelques kms sur la même terrasse alluviale à Gradignan, qui servira de sol de contrôle Cas du cuivre: • investigation recommandée si [Cu] sol > 35 mg/kg • phytotoxicité potentielle si [Cu] feuille > 25-30 mg/kg MS , Cr, Zn dosés par ICP-MS  Spéciation du Cu dans les sols Objectif: Effet de la phytostabilisation aidée par des amendements (laitiers) sur des sols sableux contaminés au Cu. Le but est d'acquérir des connaissances sur les mécanismes réactionnels dans le sol, les concentrations et spéciations des contaminants dans des sources d'exposition  Sols sélectionnés:  Historique: Contamination diffuse aux métaux Phytodisponibilité du Cu Horizon 0 -0,25 mExtractions séquentielles:(Tessier et al., 1979)



  Techniques de prélèvement  Résultats de la spéciation du Cu en solution pCu 2+ = 3,20 + 1,47pH -1,84log 10 ([Cu] sol ) (Sauvé, 2003) • DGT (Diffusive Gradient in Thin film) et dosage ICP-Risk assessment and sustainable land management using plants in trace element-contaminated soils. Ed. M. Mench, B. Mocquot, 69-70, Centre INRA Bordeaux-Aquitaine L'écodynamique d'éléments traces est étudiée dans des sols fortement contaminés au Cu issus d'un ancien site industriel de traitement du bois situé à Saint Médard d'Eyrans (Gironde, France) (Mench and Bès, 2009). Il s'agit de sols sableux de la terrasse alluviale de la Garonne. Valeur max Valeur min Cette étude se focalise sur l'écodynamique du Cu dans ces sols gérés par phytostabilisation aidée par ajout de laitiers d'aciérie, qui peuvent contribuer à l'immobilisation d'éléments du fait de leurs propriétés alcalines. Les horizons de sol en surface UNT et PLDS ont été échantillonnés en triplicats dans les lysimètres du site Schéma d'un lysimètre en coupe Tessier A., Campbell P., Bosson M. (1979) Analyt. Chemist. 51, 844-851 • Dans les sols non traités et amendés, Cu se trouve surtout sous forme colloïdale (colloïdes inorganiques et colloïdes complexés à la matière organique).

  La croissance végétale est très faible sur le sol contaminé non traité UNT. Elle est plus élevée sur les sols amendés aux laitiers, avec un meilleur rendement pour PLDS. Les sols M et CTRL présentent une croissance intermédiaire.Les concentrations en Cu dans les feuilles de haricot ayant poussé sur le sol contaminé non traité sont très élevées et variables. Ces concentrations sont très inférieures dans les sols amendés aux laitiers. Elles sont plus faibles pour le sol de prairie M, mais supérieures aux valeurs obtenues dans le sol sableux de contrôle.

  L'amendement de laitiers permet de réduire la fraction disponible du Cu en solution, le pool labile du Cu dans le sol, la fraction remobilisable du Cu dans le sol, et la phytodisponibilité du Cu. • L'amendement de laitiers augmente le pH du sol, ce qui favoriserait l'adsorption du Cu libre sur les surfaces des laitiers. • La phytodisponibilité du Cu est réduite par l'ajout de laitiers, de façon similaire pour les 2 laitiers (PLDS et CARMEUSE). • L'amendement de laitiers PLDS est plus favorable pour la croissance des plantes que le laitier CARMEUSE. Les laitiers peuvent donc être utilisés de façon positive en phytostabilisation aidée La minéralomasse est un indicateur de phytodisponibilité, et est obtenue en multipliant la masse de feuilles sèches par la concentration en Cu dosée dans les feuilles.


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

Pierre Karpman
email: pierre.karpman@gmail.com

Security Amplification against Meet-in-the-Middle Attacks Using Whitening ⋆

Keywords: Block cipher, meet-in-the-middle attack, provable security, exposure resilient function

In this paper we introduce a model for studying meet-in-the-middle attacks on block ciphers, and a simple block cipher construction provably resistant to such attacks in this model. A sideresult of this is a proper formalization for an unproven alternative to DESX proposed by Kilian and Rogaway; this construction can now be shown to be sound in our model. Meet-in-the-middle attacks exploit weaknesses in key schedule algorithms, and building constructions resistant to such attacks is an important issue for improving the security of block ciphers. Our construction is generic so that it can be used on top of any block cipher, and it does not require to increase the key-length. We use an exposure resilient function (or ERF) as a building block and we propose a concrete and efficient instantiation strategy based on compression functions.

Introduction

In the area of block cipher design, much work up to now has been devoted to proving resistance to classical statistical attacks like standard linear and differential cryptanalysis (see e.g. [START_REF] Nyberg | Provable Security Against Differential Cryptanalysis[END_REF][START_REF] Vaudenay | Provable Security for Block Ciphers by Decorrelation[END_REF][START_REF] Daemen | The Wide Trail Design Strategy[END_REF]). However, resistance to attacks that exploit weaknesses of the key schedule has remained mainly unaddressed. These attacks consist principally in meet-in-the-middle (MiTM) [START_REF] Diffie | Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard[END_REF] and relatedkey attacks [START_REF] Biham | New Types of Cryptanalytic Attacks Using Related Keys[END_REF].

A typical good design criterion for key schedules is to have a high minimal distance between expanded keys; performance is also often another issue, and key schedules are expected to be fast, so as not to impact too much the encryption of small messages. An additional criterion could be for the key schedule to be non-linear, although many (good) key schedules are in fact linear. These design principles, however, do not really amount to a theory comparable to the one devoted to resistance to statistical attacks. Nonetheless, a few works study the security of key schedules with respect to related-key attacks from a more theoretical perspective [START_REF] Nikolic | Tweaking AES[END_REF][START_REF] May | Strengthening the Key Schedule of the AES[END_REF][START_REF] Choy | AES Variants Secure against Related-Key Differential and Boomerang Attacks[END_REF].

Meet-in-the-middle attacks are an important technique available to the cryptanalysts studying symmetric primitives. It is important to avoid such attacks since unlike statistical attacks they usually have low data requirements. Beyond the classical result on double-encryption (see e.g. [START_REF] Diffie | Special Feature Exhaustive Cryptanalysis of the NBS Data Encryption Standard[END_REF]), MiTM attacks are effective at exploiting weaknesses in the key schedule algorithms of block ciphers or the message expansion of hash functions. In the context of block ciphers, MiTM attacks are the most efficient attacks on many ciphers: round-reduced version of IDEA [START_REF] Biham | New Data-Efficient Attacks on Reduced-Round IDEA[END_REF], round-reduced version of AES [START_REF] Demirci | A Meet-in-the-Middle Attack on 8-Round AES[END_REF][START_REF] Dunkelman | Improved Single-Key Attacks on 8-Round AES-192 and AES[END_REF][START_REF] Bouillaguet | Automatic Search of Attacks on Round-Reduced AES and Applications[END_REF], or the full GOST [START_REF] Isobe | A Single-Key Attack on the Full GOST Block Cipher[END_REF]. Furthermore, a MiTM phase is usually used to extend the number of rounds reached by a statistical attack, as seen for instance in the attacks of Biham and Shamir [START_REF] Biham | Differential Cryptanalysis of the Full 16-Round DES[END_REF] and of Matsui [START_REF] Matsui | The First Experimental Cryptanalysis of the Data Encryption Standard[END_REF] on the DES. Finally, the recent biclique attack is a MiTM-related technique useful to speed up exhaustive search. Bicliques were found to be successful against AES and IDEA [START_REF] Bogdanov | Biclique Cryptanalysis of the Full AES[END_REF][START_REF] Khovratovich | Narrow-Bicliques: Cryptanalysis of Full IDEA[END_REF]. In the context of hash functions, MiTM techniques may be used to find preimages; this was for instance the case for attacks on MD4 [START_REF] Leurent | MD4 is Not One-Way[END_REF][START_REF] Aoki | Preimage Attacks on One-Block MD4, 63-Step MD5 and More[END_REF], MD5 [START_REF] Sasaki | Finding Preimages in Full MD5 Faster Than Exhaustive Search[END_REF][START_REF] Aoki | Preimage Attacks on One-Block MD4, 63-Step MD5 and More[END_REF], or AES in a hash function setting [START_REF] Sasaki | Meet-in-the-Middle Preimage Attacks on AES Hashing Modes and an Application to Whirlpool[END_REF].

Our Contributions. In this paper, we develop a simple model for meet-in-the-middle attacks and propose a generic block cipher construction that is provably resistant to such attacks in this model. The idea behind our model is simple and based on the fact that many MiTM attacks on block ciphers can be seen as decomposing the cipher into two sub-ciphers, and then applying the classical MiTM attack on double-encryption (in more recent variations, the cryptanalyst may also guess part of the key or part of the intermediate state [START_REF] Isobe | A Single-Key Attack on the Full GOST Block Cipher[END_REF][START_REF] Dinur | Efficient Dissection of Composite Problems, with Applications to Cryptanalysis, Knapsacks, and Combinatorial Search Problems[END_REF]). Hence we argue that studying a construction in the sole context of double-encryption is actually meaningful for studying many types of MiTM attacks on a single cipher vulnerable to such attacks. However our goal is not to study constructions actually based on double-encryption (such as for instance the double XORcascade [START_REF] Gaži | Efficient and Optimally Secure Key-Length Extension for Block Ciphers via Randomized Cascading[END_REF], cf. below). This is because such constructions already lend themselves to meet-inthe-middle attacks even when the underlying cipher(s) does not; our objective is different and consists in obtaining a construction resistant to MiTM when the underlying cipher is not. Studying the construction with a composition of two ciphers as an underlying primitive is therefore only a mean of simulating the construction applied to a single cipher that is vulnerable to meet-in-themiddle attacks.

Our construction relies on a core (or internal) cipher and on a form of whitening. Let E k be the core cipher of key k, and f a function with good enough properties, then define a new cipher

EF k (p) E k (p ⊕ f (k)) ⊕ f (k).
The main idea behind this construction is to force an attacker to commit to a value for the whole key before being able to exploit any data he may have access to, thereby making it impossible to work separately on parts of the key 1 . A similar idea can be found for instance in the operation mode of the SHA-3 candidate SIMD [START_REF] Leurent | Design and Analysis of Hash Functions[END_REF]: the goal in this context was to make message modification techniques à la Wang impossible by forcing the attacker to commit to a specific value of the message, before the message expansion phase. We prove that meet-in-the-middle attacks are not effective against the EF cipher; this is achieved by upper-bounding the maximum advantage of an attacker of the above construction in a double-encryption setting (when E is a cascade of two ciphers), and showing that it is less than the advantage of a meet-in-the-middle adversary.

We do this with a method adapted from Kilian and Rogaway's proof on DESX, and justify formally how this is relevant when the construction is applied to a single cipher on which MiTM attacks may be performed. We also discuss how the construction can be instantiated efficiently in practice.

Related Work.

We can distinguish two kinds of works on provable security for block ciphers: proving a property for some high-level and generic construction, or proving the resistance of an actual cipher to more specific attacks. Our work clearly belongs to the first category, whereas from the second we can cite e.g. the provable resistance of block ciphers to classical linear and differential cryptanalysis. Our approach is generic so that it can be used on top of any cipher; it is for instance similar to some proposals for building tweakable block ciphers [START_REF] Liskov | Tweakable Block Ciphers[END_REF].

Similar-looking constructions have already been proposed in the literature, but with a distinct motivation of extending the equivalent key length of the core primitive. One such construction is the DESX (or its more generic name 'FX') construction, proposed by Rivest and formally proved by Kilian and Rogaway [START_REF] Kilian | How to Protect DES Against Exhaustive Key Search[END_REF]. It can be described as taking a cipher E k under the key k, and defining a new cipher

EX k,k 1 ,k 2 (p) E k (p ⊕ k 1 ) ⊕ k 2 .
A more recent development is the aforementioned double XOR-cascade of Gaži and Tessaro [START_REF] Gaži | Efficient and Optimally Secure Key-Length Extension for Block Ciphers via Randomized Cascading[END_REF]. This construction is based on a cipher E and defines a new cipher 2XOR as:

2XOR k,k 1 (p) E k (E k (p ⊕ k 1 ) ⊕ k 1 )
, 1 Or alternatively to force the attacker to guess the value of the whitening independently of the key.

where k is a key related to k (the authors suggest flipping one bit of k). However, this requires two calls to the cipher E , and therefore cannot readily be used in our context. The main difference between the above constructions and ours is that we do not aim for a bigger equivalent key length, and derive all the whitening keys from the original key to E . We also study our construction specifically in the context of resistance to meet-in-the-middle attacks. Interestingly, Kilian and Rogaway briefly mention a construction that can be seen as an instantiation of ours. Their purpose was to define an alternative to the FX construction that gives more flexibility in the choice of the key length to the user. Instead of using independent keys k, k 1 , k 2 , they suggest deriving them from an arbitrarily-long key k, as the (truncated) output of f ( k), f 1 ( k), and f 2 ( k) respectively, where f , f 1 , f 2 are defined as SHA-1 prefixed with three different constants. Once again the motivation is different from ours, and no proof nor formalization is given for this construction. Note that as a consequence of our results, it is possible to prove that this construction is sound.

Outline of the Paper. We present our model for studying meet-in-the-middle attacks in §2 and our construction in §3. We prove the resistance of the construction to the attacks captured by our model in §4. We discuss our result and its implications on advanced meet-in-the-middle techniques in §5, and instantiation issues in §6.

A Model for Meet-in-the-Middle Attacks

Generic Constructions

The aim of our work is to define constructions resistant to MiTM attacks. We define here what we mean by construction and what kinds of constructions we specifically consider. We first recall the definition of a block cipher.

Definition 1 A block cipher is a mapping

E : {0, 1} κ × {0, 1} n → {0, 1} n such that ∀k ∈ {0, 1} κ , E (k, •) (also noted E k (•)
) is a permutation. The first and second arguments of E are called the key and message (block) respectively. The variables κ and n denote the key size (or length) and block size (idem) of E .

Definition 2 A single-cipher construction is a block cipher E : {0, 1} κ × {0, 1} n → {0, 1} n that can be described as the composition Post • E • Pre of functions Pre, E , and Post, where E : {0, 1} κ ′ ×{0, 1} n → {0, 1} n is a block cipher. The functions Pre and Post may take both of E 's inputs as arguments, that is the key and the message. A ν-cipher construction is a block cipher that can be described as the composition (1) • Pre (1) where the ciphers E (i ) use independent keys, and where the Pre (i ) and Post (i ) functions may take any of these keys as inputs. A ν-cipher construction of the specific form

Post (ν) • E (ν) • Pre (ν) • Post (ν-1) • • • • • E
Post • E (ν) • E (ν-1) • • • • • E (1)
• Pre is called a ν * -cipher construction. Any single-cipher construction can be extended to a ν * -cipher construction in a straightforward way.

In this paper, we consider the EF construction, defined in §3, which is a single-cipher construction. It is thus generic, and can be used both with already-existing algorithms, and as a basis to design a cipher ex nihilo.

The Model

Our goal in this section is to give a formal model for MiTM attacks that allows to prove security properties. We later use this model to prove the resistance of the EF construction to such attacks. This model does not capture the concept of any MiTM attack, but it does nonetheless take into account a significant class.

The idea behind our model is that a MiTM attack on, say, cipher E often performs a conceptual decomposition of E into two sub-ciphers, with separate key bits. We can thus model such attacks as being performed on a double-encryption construction with two independent ciphers, seen as black-boxes. This allows us to consider MiTM attacks against generic ciphers. We detail this argument in the remainder of this section.

The Classical Meet-in-the-Middle Attack on Double Encryption. Let us consider the cipher E , defined as the composition of the two independent ciphers F and G , operating on independent keys k 1 and k 2 respectively. We denote by E k (p) the action of encrypting the plaintext p with E and key k and producing the ciphertext c. By definition of E , we have E k (p) G k 2 (F k 1 (p)), with k 1 and k 2 uniquely defined by k.

The MiTM attack on double-encryption exploits the fact that k 1 and k 2 are used independently in their respective ciphers; in its simplest form, it can be described as follows:

Get a known plaintext p and its corresponding ciphertext c. for every possible candidate k i 1 for key k 1 do Compute y i F k i 1 (p) and store the result in memory.

end for for every possible candidate

k j 2 for key k 2 do Compute y ′ j G -1 k j 2
(c) and store the result in memory.

end for for every y

i = y ′ j do Output (k i 1 , k j 2 ) as a candidate for (k 1 , k 2 )
. end for This procedure may be repeated until only one candidate for k 1 and k 2 remains, using many plaintext/ciphertext pairs. If we call κ the size of the keys k 1 and k 2 in bits, the cost of the attack is then of the order 2 κ in time and memory, which is much lower than the 2 2κ time that bruteforce search on k would cost. If k 1 and k 2 are of different size κ 1 and κ 2 , one needs only to store the candidates for the smaller size, e.g. in a hash table, and the candidates for the bigger key size can be computed on the fly. The general cost of this attack is thus of the order of max(2 κ 1 , 2 κ 2 ) in time, and min(2 κ 1 , 2 κ 2 ) in memory.

This attack can still be applied when k 1 and k 2 are not independent but have only some of their bits in common. In that case, one just needs to guess the common bits and repeat the above procedure for every guess.

A Model for Meet-in-the-Middle Attacks on a Single Cipher. MiTM attacks are in no way limited to double-encryption; in fact they are well-suited to iterated ciphers with weak key schedules. However, the ideas involved in a MiTM attack on a single cipher are essentially the same as for attacking double-encryption.

Let us consider an iterated cipher E with round function ρ i for round i : we define

E k (p) as the composition ρ r k r • • • • • ρ 1 k 1 (p)
, where r is the number of iterations of the round function, and the k i 's are round keys generated from k by a key schedule. The idea behind a MiTM attack on E is to find two sets k α and k β of consecutive round keys such that they involve strictly different bits of k. In other words we have

k α {k i , • • • , k i + j }, k β {k i + j +1 , • • • , k i + j +1+k }, with k α ∩ k β =
(when the intersection is taken over the bits of k found in k α and k β ). Once these sets are found, it is possible to guess independently the bits of k present in k α and the ones present in k β , in a way exactly similar as for double-encryption. That is, finding the sets is equivalent to conceptually decompose (a part of) E in two sub-ciphers with independent keys, on which double-encryption is performed: we have

E k = (ρ i + j +1+k • • • • • ρ i + j +1 ) k β • (ρ i + j • • • • • ρ i ) k α (
although this equality is true only if i = 1 and i + j + 1 + k = r . This constraint can easily be waved, however, if we restrict ourselves to finding sub-ciphers for a round-reduced version of E ).

We are now ready to formalize our model. We start by stating the security of double-encryption with ideal ciphers, thanks to a theorem of Aiello et al. [START_REF] Aiello | Security Amplification by Composition: The Case of Doubly-Iterated, Ideal Ciphers[END_REF] 2 .

Theorem 1 ([1]

) Let F : {0, 1} κ × {0, 1} n → {0, 1} n be an ideal block cipher. For any κ, n, t , q ≥ 1, where t and q denote the number of oracle access to F and F -1 , and F • F respectively, then the maximum advantage of any adversary A t ,q trying to distinguish F • F from a random permutation with resources t and q is upper-bounded by t 2 /2 2κ . This bound is tight up to a constant factor as long as q is not too small. We allow ourselves to use a more general expression of this result when considering doubleencryption of not necessarily equal ciphers F and G , of not necessarily equal key lengths κ 1 and κ 2 , where t 1 and t 2 denote the number of oracle access to F and G -1 respectively. In this case, we use the upper-bound t 1 •t 2 /2 κ 1 +κ 2 3 . We now define the notion of constructions resistant to MiTM attacks.

Definition 3 Let F : {0, 1} κ 1 × {0, 1} n → {0, 1} n and G : {0, 1} κ 2 × {0, 1} n → {0, 1} n be two block ci- phers. A two-cipher construction E(F , G
) is said to be resistant to the meet-in-the-middle attack if the maximum advantage of any adversary A trying to distinguish E(F , G ) from a random permutation is:

max A Adv E(F ,G ) (A t 1 +t 2 ,q ) < t 1 • t 2 /2 κ 1 +κ 2 , up to constant factors.
This definition is made meaningful by the tightness of the bound of theorem 1. Essentially, it says that a two-cipher construction is resistant to meet-in-the-middle attacks if no adversary can distinguish it with an advantage that is at least as good as the best one it could get if only composition of the two ciphers were used instead.

Definition 4 Let E : {0, 1} κ × {0, 1} n → {0, 1} n be a block cipher. A single-cipher construction E(E ) is said to be resistant to the meet-in-the-middle attack if for any two block ciphers F : {0, 1} κ 1 × {0, 1} n → {0, 1} n and G : {0, 1} κ 2 × {0, 1} n → {0, 1} n such that E = G • F and κ = κ 1 + κ 2 , the maximum advantage of any adversary A trying to distinguish E(E ) from a random permutation is:

max A Adv E(E ) (A t 1 +t 2 ,q ) < t 1 • t 2 /2 κ 1 +κ 2 ,
up to constant factors.

In other words, this means that the best attack on the construction E(E ) is strictly worse than the best meet-in-the-middle attack on E . Our model is justified by the next proposition:

Proposition 1 Let E be a two * -ciphers construction resistant to the meet-in-the-middle attack.

Then the restriction of E to a single cipher is a single-cipher construction resistant to the meet-inthe-middle attack.

Proof. This is a direct consequence of definitions 3 and 4.

⊓ ⊔

Hence, the resistance of a single-cipher construction to MiTM attacks can be studied by analyzing its two * -ciphers variant. In practice, we perform this analysis in the ideal block cipher model [START_REF] Bellare | Luby-Rackoff Backwards: Increasing Security by Making Block Ciphers Noninvertible[END_REF][START_REF] Kilian | How to Protect DES Against Exhaustive Key Search[END_REF].

A Construction Resistant to Meet-in-the-Middle Attacks

We now formally define our construction. We start by introducing the notion of Exposure-Resilient Functions (or ERF), as defined by Canetti et al. [START_REF] Canetti | Exposure-Resilient Functions and All-or-Nothing Transforms[END_REF]. ERFs are similar to all or nothing transforms, which were introduced by Rivest [START_REF] Rivest | All-or-Nothing Encryption and the Package Transform[END_REF].

Definition 5 An ℓ-ERF is a mapping f : {0, 1} α → {0, 1} β such that for random values r , R in {0, 1} α , {0, 1} β ; for any L ∈ α ℓ , the distributions 〈[r ] L , f (r )〉 and 〈[r ] L , R〉 are indistinguishable one from another; where α ℓ denotes the set of subsets of {1 . . . α} of size ℓ, and for x ∈ {0, 1} α , [x] L denotes x restricted to its bits not in L.

Here, we will consider particularly weak ERFs, in the sense that when less than ℓ bits of r are unknown to the adversary, he is then supposed to be able to predict the value of f (r ′ ) for any r ′ that fixes the unknown bits of r to some value. However, we will mostly consider degenerate cases where ℓ is zero. That is, the output of the ERF is indistinguishable from random until all of its input is revealed. Constructions of ERFs are known to exist in the standard model [START_REF] Canetti | Exposure-Resilient Functions and All-or-Nothing Transforms[END_REF], and it is trivial to see that a random oracle meets the definition of a zero-ERF. Hence, from a practical point of view, a zero-ERF can be instantiated by a hash function, in the random oracle model.

We now define our construction, which we will note EF for short. Definition 6 Let E : {0, 1} κ × {0, 1} n → {0, 1} n be a block cipher. We write E k (p) c the action of encrypting the plaintext p with E under the key k, to produce the ciphertext c. Let f : {0, 1} κ → {0, 1} n be an ℓ-ERF. Then we define the EF construction with core cipher E as

EF k (p) E k (p ⊕ f (k)) ⊕ f (k)
, where '⊕' denotes bitwise exclusive or.

Our goal is to prove the resistance of this construction to MiTM attacks. According to our model, we will study this construction as a two-ciphers construction. That is, we instantiate

E k by G k 2 • F k 1 .
In this case, the EF construction applied to E can be written as:

EF (k 1 ,k 2 ) (p) G k 2 (F k 1 (p ⊕ f (k 1 , k 2 ))) ⊕ f (k 1 , k 2 ).

Resistance of the EF Construction to Meet-in-the-Middle Attacks

In this section, we prove an upper-bound on the advantage of an adversary trying to distinguish the EF two-ciphers construction from a random permutation, in function of the number of queries made to different oracles. The bound we obtain shows that our construction significantly improves the resistance of double-encryption to generic attacks such as the classical MiTM, and hence is resistant to the MiTM attack, in the terminology of definitions 3 and 4.

Security Model

We consider the EF two-ciphers construction applied to G • F , where F : {0, 1} κ 1 ×{0, 1} n → {0, 1} n and G : {0, 1} κ 2 × {0, 1} n → {0, 1} n are ideal block ciphers [START_REF] Bellare | Luby-Rackoff Backwards: Increasing Security by Making Block Ciphers Noninvertible[END_REF][START_REF] Kilian | How to Protect DES Against Exhaustive Key Search[END_REF]: for each key k 1 (resp. k 2 ), the map F k 1 (resp. G k 2 ) is a permutation randomly chosen from the set Π n of all (2 n )! permutations operating on words of size n. For ease of presentation, and without loss of generality, we assume that κ 1 = κ 2 κ. The 'f ' function used in EF is an ℓ-ERF with ℓ small. We consider an adversary who is given access to four oracles:

-Two of them are F and G ; when provided with a key k ′ 1 (resp. k ′ 2 ) of size κ and an input x (resp. y) of size n, they return the result y (resp. z) of encrypting x (resp. y) with F (resp. G ) with key k ′ 1 (resp. k ′ 2 ). Queries to the inverse oracles F -1 and G -1 are permitted, and are not distinguished from regular queries. That is, if F (x) y has been queried, we consider that F -1 (y) x has also been queried, and conversely.

-One oracle gives an access to f , and when provided with an input of size 2κ bits, returns the result of size n of the evaluation of f on this input.

-The last oracle, which we call U , takes as input a plaintext p and returns either EF(p), with EF instantiated with F , G , and f with fixed, randomly chosen keys k 1 and k 2 ; or the image of p from a fixed permutation π randomly selected from the set Π n . Again, queries to U -1 are permitted.

Each access to an oracle will be counted and expressed by the following variables:

-The number of accesses to U is denoted by D. They represent the amount of data available to the adversary.

-The number of accesses to F and F -1 (resp. G and G -1 ) is denoted by q 1 (resp. q 2 ).

-The number of accesses to f is denoted by q f . The goal of the adversary is to distinguish between U being π or the EF construction. We define the advantage of an adversary as its probability of successfully distinguishing the two instantiations of U . More formally: Definition 7 Let Π n be the set of permutations on words of size n; let us note x R ← S the action of randomly choosing an object x from the set S ; let us denote by A EF and A π the answer, 0 or 1, of an adversary A with access to the aforementioned oracles, when U is the EF construction and a randomly chosen permutation respectively. Then the advantage Adv A of the adversary A is defined as:

Adv A Pr ∀k ′ 1 ∈ {0, 1} κ , F k ′ 1 R ← Π n ; ∀k ′ 2 ∈ {0, 1} κ , G k ′ 2 R ← Π n ; π R ← Π n : A π = 1 - Pr ∀k ′ 1 ∈ {0, 1} κ , F k ′ 1 R ← Π n ; ∀k ′ 2 ∈ {0, 1} κ , G k ′ 2 R ← Π n ; k 1 R ← {0, 1} κ ; k 2 R ← {0, 1} κ : A EF = 1 .
Our objective is to bound this advantage for any adversary A in function of the number of queries he has made to the oracles. We note Adv(ℓ, D, q 1 , q 2 , q f ) the advantage of any adversary having made less than D, q 1 , q 2 , and q f queries to the oracles, when f is an ℓ-ERF.

Notations.

-A key candidate for F (resp. G ) is denoted by k ′ 1 (resp. k ′ 2 ). Those are keys for which the adversary makes queries to the oracles awaiting a key as part of their inputs. Moreover, we may count the accesses to those oracles when queried with a specific key. The number of accesses to

F (resp. G , f ) with key k ′ 1 (resp. k ′ 2 , (k ′ 1 , k ′ 2 )) is written q 1 (k ′ 1 ) (resp. q 2 (k ′ 2 ), q f (k ′ 1 , k ′ 2 )
). Furthermore, the number of queries to the F (resp. G ) oracle with key k ′ 1 (resp. k ′ 2 ) and for a specific message p is noted q 1 (k ′ 1 , p) (resp. q 2 (k ′ 2 , p)). -If U has been instantiated with EF, the key used in the instantiation for F (resp. G ) is denoted by k 1 (resp. k 2 ). For ease of presentation, we will consider it valid to talk about those keys even when it is not clear if U is instantiated with EF.

-We denote by x, y, z, the intermediate values p⊕f

(k 1 , k 2 ), F k 1 (p⊕f (k 1 , k 2 ))), and G k 2 (F k 1 (p⊕ f (k 1 , k 2 )
)) respectively. -We make use of an indicator function, written 1. We have 1(x) = 0 if and only if x is zero, and it is one otherwise. This may be extended to sets, where 1(x) = 0 if and only if x is the empty set, and is one otherwise.

-The concatenation of words x and y is noted x||y, the Hamming weight of a word x is denoted by hw(x).

The Result

Our main result about the security of the EF construction is summarized by the following theorem.

Theorem 2

The advantage Adv(ℓ, D, q 1 , q 2 , q f ) of an adversary trying to distinguish EF from a random permutation is upper-bounded by:

2 -2κ max 2 ℓ n ℓ • q f , 2 -n • D k ′ 1 , k ′ 2 min(q 1 (k ′ 1 ), q 2 (k ′ 2 )) . (1)
One can see that to gain an advantage of one, an adversary with D available data needs at least 2 2κ 2 ℓ ( n ℓ )

or 2 κ+n D queries to the oracles, whichever is the smallest. For ℓ = 0, n = κ, and D = 1, these two terms are equal to 2 2κ ; in the case of double-encryption without the EF construction, one would only need of the order of 2 κ queries. This result immediately implies the following corollary:

Corollary 1 The two * -ciphers and single-cipher EF construction is resistant to meet-in-the-middle attacks, in the terminology of definitions 3 and 4, as long as D < 2 n (i.e. the adversary does not have access to the whole codebook).

Proof. For small values of ℓ, and when D < 2 n , Adv(ℓ, D, q 1 , q 2 , q f ) is strictly smaller than the bound of definitions 3 and 4.

⊓ ⊔

The restriction that D < 2 n is important, and comes from more general properties of FX-like constructions. In particular, such a construction cannot be used in all generality in order to increase the equivalent key length of a block cipher, as the key length cannot be shown to be more than the one of the core cipher when all the codebook is available to the adversary. This is the case for the original construction of DESX, and remains true in our modified setting when the core cipher is a 2-cascade (i.e. a composition of two ciphers). In the latter case, the double XOR-cascade of Gaži and Tessaro does increase the effective key length of the (modified) 2-cascade. However, as it has already been noted, we want our construction to be applicable to a single cipher as well, and therefore cannot use one similar to theirs. The above restriction notwithstanding, we believe that our construction is still interesting in practice. The first reason is that attacks where the adversary uses the whole codebook would not only be of limited interest to the attacker, they can also be made asymptotically as expensive as the designer of the cipher wishes to; so big an amount of data is also fairly unrealistic for many ciphers with big block sizes (e.g. 128 bits). The second reason is that raising the data complexity of a MiTM attack from the information-theoretically lower-bound to the whole codebook, for an adversary to get the same time complexity, is in itself a huge improvement of the resistance to MiTM attacks.

Proof Sketch

We outline here the strategy used for proving theorem 2, while the full proof is given in the appendix.

Given the similarities between the EF and FX constructions and their security models, our proof has a structure close to the one of Kilian and Rogaway [START_REF] Kilian | How to Protect DES Against Exhaustive Key Search[END_REF]. In particular, we use games for each oracle to define the situations where an adversary may distinguish the instantiation of the U oracle (we do not fully redefine the games in this paper, though, and refer to [START_REF] Kilian | How to Protect DES Against Exhaustive Key Search[END_REF] for a more detailed description). For each such situation, we then bound the probability of the distinction being possible in function of the past queries made by the adversary. We bound separately the advantage of an adversary trying to find distinguishing situations for the three oracles, F , G , and U , and then combine these bounds together with the bound of the advantage over f to produce a general result.

It should be noticed that we do not need to consider situations for the "inverse" oracles (such as e.g. F -1 ), as the constraints possibly put on the input/output pairs of queries to those oracles are simply swapped when compared to the ones for the "forward" oracles (an input of an inverse oracle being an output for the corresponding forward oracle). Therefore, the advantage when distinguishing inverse oracles is not different from when considering forward oracle.

The main difference between our proof and the one of [START_REF] Kilian | How to Protect DES Against Exhaustive Key Search[END_REF] is that, from the structure of the construction, an adversary has essentially the choice of guessing the output of the f function directly (thereby seeing f (k 1 , k 2 ) as a third independent key), or via its inputs and the properties of f . This shows in the bound of theorem 2 as the two arguments of the maximum function. Because our construction is more complex than FX, we also have more oracles to consider.

Discussion

In the previous section, we have shown that the EF construction increases the resistance of a cipher to "classical" MiTM attacks. We now argue that this improved resistance carries on to more advanced MiTM techniques, which further increases the relevance and interest of the construction. We also address the relevance of our ideal-cipher-based model.

About Ideal Ciphers

pointed above, our proof uses the ideal cipher model. This could be seen as limiting the relevance of the applications we claim -building constructions resistant to MiTM attacks-as we use a setting where the best attack on the sub-ciphers is basically brute-force.

We claim that this is not a limitation. Using ideal ciphers allows one to express bounds in terms of number of queries to the relevant oracles: the cost of each query is of little importance in so far as it is bounded by a constant. In other words, our results show that the EF construction increases the security of double-encryption by ensuring that an adversary needs to perform more queries to the oracles to gain an advantage comparable to the one he would get when the construction is not used. Whether the queries are expensive or not (i.e. whether the best attacks on the sub-ciphers is brute-force or not) does not change the asymptotic increase of security that one can expect by choosing a bigger key or block size. This is as much valid for the sub-ciphers decomposition of a MiTM attack on single cipher as for double-encryption.

Another concern might be that actual MiTM attacks do not typically perform a full decomposition of the attacked cipher in two sub-ciphers with independent keys. This is indeed an ideal case for the attacker which is seldom met in practice. However, real attacks that do not conform to this ideal case are typically less powerful, while still needing a decomposition in two subciphers at some point; hence our construction increases the security against these real attacks as well.

The Splice-and-Cut Exception

Before going on to the expected advantages of the EF construction, we should mention one situation where it does not seem to be useful, i.e. when protecting against splice-and-cut MiTM attacks.

A splice-and-cut MiTM attack uses a conceptual decomposition of a cipher with sub-ciphers that may be defined by considering the first and last round of the attacked cipher as consecutive. That is, we consider decompositions of say, , that can be written as, say G 2 • F • G 1 . In order to perform this variant of the MiTM attack, the attacker typically guesses one intermediate value at the boundary between the two sub-ciphers using different key subsets, and then queries the plaintext or ciphertext corresponding to the encryption or decryption of this value for a given sub-key candidate. With data obtained this way, it is then easy to perform a MiTM attack.

It is possible to adapt our model to the conceptual decomposition used in a splice-and-cut attack. However, because this attack typically requires the whole code-book to be performed, the bound that would be obtained by a generalization of theorem 2 would not show any improved resistance. It might be that improved resistance to the splice-and-cut MiTM could be shown by leaving the information-theoretic view of the ideal cipher model, but this does not seem to be an easy task.

In the end, because of their huge data requirements, splice-and-cut MiTM are more suited to attacking hash functions, and are seldom used against block ciphers. Consequently, we think that the impact of the EF construction not being efficient against them is somewhat limited in its targeted applications.

Taking Advanced Attack Techniques into Account

We now discuss the issue of including some more advanced MiTM techniques used by cryptanalysts in our proof that the EF construction increases the resistance of a single cipher to MiTM attacks. We discuss this for two important techniques: the initial structure of Sasaki and Aoki [START_REF] Sasaki | Finding Preimages in Full MD5 Faster Than Exhaustive Search[END_REF], and its later generalization to bicliques by Khovratovich et al. [START_REF] Khovratovich | Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 Family[END_REF].

Initial Structure. This is an advanced techniques that may be used in order to increase the number of rounds reached by an existing MiTM attack. It consists in finding an initial structure between two sub-ciphers of the MiTM attack that use, say, key subsets 1 and k 2 respectively. The structure consists itself in a sub-cipher that can be computed thanks to the key subsets k ′ 1 ⊆ k 1 and k ′ 2 ⊆ k 2 , but with the key bits from k ′ 2 being used before the bits of k ′ 1 in the structure (otherwise the relevant parts of the initial structure can be included in the two sub-ciphers of the MiTM). Finding initial structures gives more flexibility to the attacker in the matching phase, leading to more powerful attacks. For instance, they were key in finding the first preimage attack on the full MD5 [START_REF] Sasaki | Finding Preimages in Full MD5 Faster Than Exhaustive Search[END_REF].

In order to be applicable, the initial structure technique still needs the cipher under attack to be decomposed in two sub-ciphers. The added sophistication of the matching phase typically allows the attacker to define a decomposition that covers more rounds of the full cipher than what he would obtain without using the initial structure. Yet this does not change the fact that the attacker needs to test the key candidates for both sub-ciphers. What the bounds on the EF construction say is that it is impossible to use a MiTM technique to do this efficiently, because of the increased number of queries that have to be made to the sub-ciphers (and possibly to the f function) in order to test all possible keys and get an advantage of one; this is completely independent of the number of rounds covered by the sub-ciphers.

In essence, the initial structure technique allows an attacker to find better decompositions, but it does not improve the key-testing phase per se. Therefore we claim that the EF construction still improves the security of a cipher against adversaries using initial structures: however good the decomposition of the initial cipher they may get, the construction layer will prevent efficient use of it.

Bicliques. This is a generalization of the previous technique that allows for a more systematic way to construct initial structures, instead of searching them manually as was done originally. In its simplest form, the biclique technique can be seen as a way to extend an existing (spliceand-cut) MiTM attack by constructing bicliques between intermediate states in order to cover the rounds not included in the existing attack. Again, this leads to more powerful attacks, and this technique has successfully been used to analyze several hash functions and block ciphers such as Skein [START_REF] Khovratovich | Bicliques for Preimages: Attacks on Skein-512 and the SHA-2 Family[END_REF], AES [START_REF] Bogdanov | Biclique Cryptanalysis of the Full AES[END_REF], or IDEA [START_REF] Khovratovich | Narrow-Bicliques: Cryptanalysis of Full IDEA[END_REF].

Again, for this technique to be applicable, finding a decomposition in sub-ciphers is necessary. Hence, even if the biclique parts themselves are not something that is captured in our analysis, it is still the case for the decomposition: for a given decomposition of given parameters size, the bound on the number of queries to the sub-ciphers necessary to gain a given advantage is not changed by the presence of bicliques. The interest of the EF construction in this case is again to ensure that no decomposition can be efficiently used, either alone or as part of a wider attack. This analysis and its arguments is similar to the one that was performed on the recent PRINCE cipher in order to assess its resistance to bicliques [START_REF] Borghoff | PRINCE -A Low-Latency Block Cipher for Pervasive Computing Applications -Extended Abstract[END_REF].

Summary. We did not formalize the arguments presented in this section, and it does not seem to be easy to do so. In addition, although we think that an increased resistance to the MiTM phase is an important step towards some sort of provable security against these techniques, the interest of that in the case of actual designs might be somewhat more limited. The reason is that if these techniques allow to efficiently use a decomposition with small parameters size as part of a bigger attack, the increased resistance to the MiTM phase might not impact the overall complexity significantly. This might be a concern when resistance to e.g. bicliques is considered.

In the end, much work still needs to be done in order to better understand how to resist advanced MiTM techniques, and this is far beyond the scope of this paper. Yet we believe that an increased resistance to even just the basic MiTM attack should be an important part of this work, much as resisting standard statistical attacks is an important part of modern cipher design.

Alternatives for the Construction

We end this section by outlining three alternatives for the EF construction that differ with the main proposal in the way the output of the f function is combined with the input of the core cipher.

A first obvious variation is to use modular addition instead of XOR.

Definition 8 Let f : {0, 1} κ → {0, 1} n be an ℓ-ERF. Then we define the EF ⊞ construction with core cipher E as

EF ⊞ k (p) E k (p ⊞ f (k)) ⊞ f (k)
, where ⊞ denotes addition in Z/2 n Z.

This variant may be useful in practice, when the core cipher of the construction is no longer seen as a black box. Because a block cipher typically performs key whitening with sub-keys derived from k, if it is performed with an XOR operation, it may be better to combine the output of f with modular addition, in order to make it non-linear with respect to this whitening 4 . Conversely, the original construction is maybe to be preferred when the whitening is done with modular addition. Note that adding whitening keys with modular addition instead of XOR was already proposed by Dunkelman et al. as a generalization of the Even-Mansour construction [START_REF] Dunkelman | Minimalism in Cryptography: The Even-Mansour Scheme Revisited[END_REF].

A second variation exploiting a similar idea is to replace XOR with multiplication in a finite field.

Definition 9 Let f : {0, 1} κ → {0, 1} n be an ℓ-ERF. Then we define the EF ⊠ construction with core cipher E as EF

⊠ k (p) E k (p ⊠ f (k)) ⊠ f (k), where ⊠ denotes multiplication in F 2 n .
Although quite slower than XOR or modular addition, multiplication in a finite field mixes its inputs very thoroughly, which makes it attractive when performance is not critical.

A last variation we suggest is to use even stronger mixing with a decorrelation module [START_REF] Vaudenay | Provable Security for Block Ciphers by Decorrelation[END_REF].

Definition 10 Let f , g : {0, 1} κ → {0, 1} n be two ℓ-ERFs. Then we define the EFG DC construction with core cipher E as EFG DC

k (p) E k (p ⊠ f (k) ⊕ g(k)) ⊠ f (k) ⊕ g(k).
Finally, we can also propose an obvious variation orthogonal to the three above, consisting in using two (four in the case of EFG DC ) different functions to derive the two whitening keys.

It is worthwhile noting that all these variants directly benefit from the proofs for the EF construction, as these did not rely on any specific property of XOR not shared by the alternative operations used here (in particular they are all invertible). However, the different constructions are likely to give different levels of security when used in practice, especially when other attacks than MiTM are considered. For instance, decorrelation modules are expected to provide some additional protection against classical differential attacks, which XOR or modular addition do not by themselves.

Practical Instantiation

We conclude this work by discussing how to efficiently instantiate the EF construction in practice. We start by showing how it is possible to use a hash function h as the f function. This is justified by the fact that such a function is a zero-ERF in the random-oracle model. We note EH the resulting construction.

Corollary 2 With notations adapted from § §3 and 4, the advantage Adv(D, q 1 , q 2 , q h ) of an adversary trying to distinguish EH k (p) E k (p ⊕ h(k)) ⊕ h(k) from a random permutation, where h is a hash function, is upper-bounded in the random oracle model by:

2 -κ max q h , 2 -n • D k ′ 1 ,k ′ 2 min(q 1 (k ′ 1 ), q 2 (k ′ 2 )) (2)
for queries q 1 and q 2 to any two ciphers

F k 1 and G k 2 such that E k = G k 1 • F k 2 .
This is very similar to an alternative to the FX construction proposed by Kilian and Rogaway, and already mentioned in §1.

From an efficiency point of view, using a call to a (small) hash function as part of the encryption process could be expensive. Therefore, the EH construction might be of little interest when computational power is limited or when the key has to be regularly changed (for instance because the cipher is itself used in a hashing mode). However, we believe that there are meaningful applications for block ciphers where none of these restrictions apply, making this type of instantiation still of interest. It is also worth noting that the input to h/f is of fixed size, and thus only a "one-shot" compression function with a fixed IV ĥ : {0, 1} κ → {0, 1} n is actually needed, and not a full-fledged hash function h : {0, 1} * → {0, 1} n . Finally, it is likely that a smart instantiation would use synergy between the core of the cipher and the h / ĥ function; using two completely unrelated functions for both components would probably not be the simplest way to proceed. In particular, it seems an interesting option to build the hash function by using the block cipher E itself in a hashing mode 5 . If we can make it so that only one call to the compression function is needed (this is the case e.g. when the key and block sizes of E are equal), then it is even possible to build the compression function from E used as a fixed permutation E ′ , with all its round keys independently set to a constant. This can be achieved by e.g. using E in Matyas-Meyer-Oseas mode, with ĥ(x) then defined as E ′ (x) ⊕ x. Note that such a construction can be performed with many current block ciphers, including AES-128. Even though care should be taken before using any cipher in a hashing mode (this is the case for AES too [START_REF] Sasaki | Meet-in-the-Middle Preimage Attacks on AES Hashing Modes and an Application to Whirlpool[END_REF]), the fact that in this case it may be used with independent round keys may significantly improve its security in that setting (not least because it rules out meet-in-the-middle attacks such as [START_REF] Sasaki | Meet-in-the-Middle Preimage Attacks on AES Hashing Modes and an Application to Whirlpool[END_REF]). Therefore, we believe that this instantiation strategy is sound, and that it can be applied to many existing ciphers, as well as being usable for future designs.

The result is stated in the specific case where the two ciphers are equal.

Although in practice, we actually study our construction in the case of κ 1 = κ 2 , and therefore we will really be using exactly the same bound as in the main result of[START_REF] Aiello | Security Amplification by Composition: The Case of Doubly-Iterated, Ideal Ciphers[END_REF].

Alternatively, a concrete instantiation could use f (k) as the unique whitening key.

Obviously, one may also consider reduced-round variants of the same cipher in order to make this step faster. It is a designer's role to find a good tradeoff between efficiency and security, and this instantiation strategy makes no exceptions.

A Proof of Theorem 2

We use the notations of §4.1.

A.1 The F Game

In this sub-section, we give a bound for the advantage of an adversary when it is trying to distinguish U thanks to the answers of queries to the F oracle. We will say that such an adversary is playing the F game. We first identify these situations when the instantiation of U makes a difference for the answers to queries to F .

The distinguishing situation. On a query to F k ′ 1 (x) y, then: 1. if k ′ 1 = k 1 ; 2. and if U (x ⊕ f (k 1 , k 2 )) c has been previously queried (or 'def', for short); 3. and if G -1 k 2 (c ⊕ f (k 1 , k 2 )) y ′ has been previously queried; then we must have y = y ′ when U is instantiated by EF, which makes the distinction possible.

Probability of Distinction in Function of the Number of Queries. Our proof revolves around the combinatorial argument that when the number of oracle queries is known, it is not too hard to bound the probability of encountering the distinguishing situation for a random choice of k 1 and k 2 . In other words, given the amount of past queries, it is possible to bound the proportion of the key-space of F and G that will force at least one specific value for an input/output pair of

From the distinguishing situation, it is straightforward to express the probability of obtaining an input/output pair for F that can lead to distinction. That is, one that makes distinguishing possible if F is additionally queried with key k 1 . This is equal to:

where z is arbitrary. We can see that the first term in (3) defines the input of a call to F that may lead to distinction, and the second term defines the corresponding output of such a call. The full probability of distinguishing U on a query to F k ′ 1 (x) can then be written as:

We first bound the advantage of an adversary when assuming that f is a zero-ERF. That is, the output of a call to f is completely random until all of its input is known.

From (3), we can see that an input/output pair of F for a pair of key candidates (k ′ 1 , k ′ 2 ) may become defined via two ways: either the adversary made a query to f (k ′ 1 , k ′ 2 ) and corresponding queries to U and G ; either he has guessed sufficiently many values for the output of f (k ′ 1 , k ′ 2 ) without querying f , and made many queries to U and G to be able to check and find the right value. We will say that an adversary behaving according to the first (resp. second) way follows the first (resp. second) strategy.

The potential advantage (no pun intended) of the second strategy is that it allows to work separately on the guesses for k 1 and k 2 . This is reminiscent of the classical MiTM attack; however, we will see that with the EF construction, this advantage is still considerably reduced because of the presence of f . Strategy One. We study the case of an adversary following the first strategy exclusively. We start by defining a variable τ 2 , function of k ′ 1 and k ′ 2 . We use this variable to bound the probability for input/output pairs of terms from (3) to be defined for a pair of key candidates (k ′ 1 , k ′ 2 ). We have:

We then define a variable θ 2 , function of k ′ 1 , that we use to bound the number of cases defined for a fixed key candidate k ′ 1 . This will be useful to bound the advantage of the adversary when k ′ 1 is the right first key. This variable can be succinctly defined thanks to τ 2 , and we have:

It follows that for a right guess k 1 of k ′ 1 , the advantage of the adversary can be bounded by 2 -κ θ 2 (k 1 ). Consequently, we define a final variable Θ 1 as:

This allows us to bound the advantage of an adversary by 2 -2κ Θ 1 . If we fully develop Θ 1 again, this yields:

What is interesting here is that we need at least one call to f for every pair of candidates (k ′ 1 , k ′ 2 ) for those candidates to contribute to the value of Θ 1 . Therefore, we can bound

) without losing too much precision. This gives us the final bound we will use for the advantage of an adversary playing the F game and following strategy one:

This means that to gain an advantage of one, an adversary will need at least 2 2κ queries q f to the f oracle.

Strategy Two. We now turn our attention to an adversary exclusively following the second strategy. In this case, for the guess of a key candidate k ′ 1 , in order to check a key candidate k ′ 2 , there may be many guesses of the value of f (k ′ 1 , k ′ 2 ) to consider to gain a non-marginal advantage. In the case of strategy two, we redefine the variable τ 2 as:

We also redefine θ 2 as:

In this case we do not have indicator functions as in strategy one anymore, as what becomes important is the proportion of guesses for f (k 1 , k 2 ) that were made out of how many possible values it can take (whereas in the case of strategy one, we explicitly compute f for the couples (k 1 , k 2 ), and thus only care if the right one was once considered). We also witness the introduction of a min term that translates the fact that for a guess of the value of f (•) to be useful in an attack, it needs to be verifiable form both the plaintext and the ciphertext. If we put it in another way, the queries q 1 (k ′ 1 ) (resp.

) differences with the plaintexts (resp. the ciphertexts); if more differences are defined with, say, the plaintexts than with the ciphertexts (because e.g. of more calls to q 1 than to q 2 ), some of those differences will not possibly be checked for the whole construction, and thereby will not contribute to the attack. Now we can use θ 2 and define Θ 1 to bound the advantage of the adversary as previously; the only difference will be the full expression for Θ 1 . In this case it will be:

Hence we can bound the advantage of an adversary playing the F game and following strategy two by:

This means that to gain an advantage of one, an adversary will need at least 2 κ+n D queries q 1 and q 2 to the F and G oracles, those being possibly made independently for the two oracles.

Mixing the two strategies. In order to bound the advantage of an adversary playing the F game regardless of the strategy it is following, it suffices to combine the bounds ( 9) and ( 13) together. We can do this easily without losing too much precision by taking the maximum of the two. Indeed we can see that the term q f (k ′ 1 , k ′ 2 ) does not influence the value of ( 13), and that the number of to queries D, q 1 (k ′ 1 ), and q 2 (k ′ 2 ) does not influence the value of ( 9) in so far as it is greater than one. This gives the following result: Lemma 1 The advantage Adv(0, D, q 1 , q 2 , q f ) of an adversary trying to distinguish U by playing the F game is upper-bounded by:

) . ( 14)

A.2 The G Game

This game being exactly symmetrical with the previous one, we only give the result here.

Lemma 2

The advantage Adv(0, D, q 1 , q 2 , q f ) of an adversary trying to distinguish U by playing the G game is upper-bounded by:

A.3 The U Game now consider the game that identifies the situation where queries to U itself may lead to distinction.

The distinguishing situation. On a query to U (p) c, then:

) y has been previously queried; 2. and if G k 2 (y) z has been previously queried; then we must have c = z ⊕ f (k 1 , k 2 ) when U is instantiated with EF, which makes distinction possible.

Probability of Distinction in Function of the Number of

Queries. Again, we express the probability of obtaining an input/output pair possibly leading to distinction. This is equal to:

In this equation, the first (resp. second) term corresponds to an input (resp. output) of a distinguishing call to U . We can treat this equation in a similar fashion as previously, although we need to redefine the two strategies.

Strategy One. To compute our bound, we may define an intermediate variable τ U , function of k ′ 1 and k ′ 2 , that plays the same role as in the F game. We have:

For a right guess of k ′ 1 (resp. k ′ 2 ), it is easy to see that we can bound the advantage of an adversary by 2 -κ

). It ensues that the full advantage of an adversary playing the U game by following strategy one can be bounded by:

To gain an advantage of 1, an adversary will therefore need at least of the order of 2 2κ queries to the f oracle.

Strategy Two. In the case of strategy two, we need to redefine the variable τ U . For each query p to U , only joint queries to F and G -1 with similar differences from p and U (p) respectively may help to define the terms in 16; and then we have τ U defined as:

For a right guess of k ′ 1 (resp. k ′ 2 ) we can use this variable to bound the advantage of an adversary similarly as for strategy one. It ensues that the full advantage of an adversary playing the U game by following strategy two can be bounded by:

To gain an advantage of 1, an adversary will need a workload at least of the order of 2 κ+n D queries to the F and G oracles each, with those possibly being made independently one from another. This gives us our result for the U game:

Lemma 3 The advantage Adv(0, D, q 1 , q 2 , q f ) of an adversary trying to distinguish U by playing the U game is upper-bounded by:

A.4 The f Game

The EF construction is defined with being an ℓ-ERF, but so far we gave bounds for the advantage of an adversary specifically when ℓ is zero. We claim that taking ℓ greater than zero decreases the bounds by a factor at most n ℓ 2 ℓ , making the construction still relevant if ℓ is small (for instance, with n = 128, we can take ℓ = 3 and lose around 22 bits of security). We prove this claim for the F game, but the proof easily generalizes to the other games.

First we should notice that the only strategy we need to consider is strategy one. Indeed, whether f is an ℓ-ERF or a zero-ERF has no impact if the value of f (k ′ 1 , k ′ 2 ) is guessed independently of (k ′ 1 , k ′ 2 ), because we expect f to have a full range in any case. With this in mind we can redefine the variable τ 2 for strategy one. We have:

We can plug this directly into the value of Θ 1 to find :

As each query to f (k ′ 1 , k ′ 2 ) yields at most 2 ℓ n ℓ pairs (k ′′ 1 , k ′′ 2 ) such that

≤ ℓ is not we get the bound:

The advantage Adv(ℓ, D, q 1 , q 2 , q f ) of an adversary trying to distinguish U when following strategy one is upper-bounded by:

A.5 Joining Pieces Together

The proof of theorem 2 is just obtained by combining the results of lemmata 1, 3, 4, and by remarking that the second term in lemma 3 is upper-bounded by the second term in lemma 1.


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

Damien Vergnaud

Jean-Christophe Zapalowicz
email: jean-christophe.zapalowicz@inria.fr

Keywords: Micali-Schnorr generator, Time, Memory, Data tradeoff

In this paper, we study the security of the Micali-Schnorr pseudorandom number generator. The security of this cryptographic scheme is based on two computational problems which are variants of the RSA problem. The RSA problem essentially aims at recovering the plaintext from a random ciphertext. In the analysis of the Micali-Schnorr pseudorandom generator, we are interested in instances of this problem where the plaintext is small and where the ciphertext is not entirely known. We will describe time / memory tradeoff techniques to solve these hard problems which provides the first analysis of this pseudorandom generator 25 years after its publication.

Time/Memory/Data Tradeoffs for variants of the RSA Problem 1 Introduction

In this paper we study two cryptographic computational problems related to the RSA problem. Given a modulus N , product of two large prime numbers, and an odd exponent e, coprime to ϕ(N ) the order of the multiplicative group Z * N , the RSA problem consists in recovering the plaintext m ∈ Z * N from a random ciphertext c = m e mod N . The variants we look at consider particular instances of this problem where the plaintext is small or where the plaintext is small and only a part of the ciphertext is known. These two problems appear to be related to the security of a pseudorandom generator proposed by Micali and Schnorr [START_REF] Micali | Efficient, perfect polynomial random number generators[END_REF].

A pseudorandom generator is a deterministic polynomial time algorithm that expands short seeds (made of truly random bits) into longer bit sequences, whose distribution cannot be distinguished from uniformly random bits by a computationally bounded algorithm. Pseudorandom number generators are probably the most basic cryptographic primitive: they are widely used for block ciphers, public-key encryption, digital signatures, keystream generation and as passwords sources. It is well-known that pseudorandom generators exist if and only if oneway functions exist [START_REF] Håstad | A pseudorandom generator from any one-way function[END_REF] (though this generic construction is highly inefficient).

The first practical generator with proven security was proposed by Blum and Micali [START_REF] Blum | How to generate cryptographically strong sequences of pseudo-random bits[END_REF]. The Blum-Micali generator outputs only one bit per iteration -which costs one exponentiation modulo a large prime p -and its security is based on the intractability of the discrete logarithm problem in Z * p . It has been shown (e.g. [START_REF] Håstad | The security of all RSA and discrete log bits[END_REF]) that the generator remains secure if one outputs O(log log p) bits per iteration. Another line of pseudorandom generators is based on factoring-like assumptions (e.g. [START_REF] Blum | A simple unpredictable pseudo-random number generator[END_REF][START_REF] Micali | Efficient, perfect polynomial random number generators[END_REF][START_REF] Steinfeld | On the provable security of an efficient RSA-based pseudorandom generator[END_REF]). The BBS generator was introduced by Blum, Blum and Shub in [START_REF] Blum | A simple unpredictable pseudo-random number generator[END_REF] and proven secure under the assumption that deciding quadratic residuosity modulo a composite Blum 1 integer N is hard. The generator works by repeatedly squaring modulo N a random seed in Z * N and outputs (at each iteration) the least significant bit of the current value. Similarly, the RSA generator works by iterating the RSA encryption mapping v → v e mod N (for a public RSA modulus N and a public exponent e coprime to ϕ(N )) on a secret random initial seed value v 0 ∈ Z * N to compute the intermediate state values v i+1 = v e i mod N (for i ∈ N) and outputting the least significant bit of the state value at each iteration. In [START_REF] Alexi | RSA and Rabin functions: Certain parts are as hard as the whole[END_REF] Alexi et al. showed that one can output up to O(log log N ) bits per iteration of the BBS generator and the RSA generator. The actual number of bits that can be output depends on the concrete parameters adopted but the generators are considered too slow for most applications.

Another line of number-theoretic pseudorandom generators sacrifices provable security for efficiency. Gennaro [START_REF] Gennaro | An improved pseudo-random generator based on the discrete logarithm problem[END_REF] suggested a discrete-logarithm based generator that outputs O(log p) bits per modular exponentiation in Z * p but its security is based on a strong and not so well-studied "discrete logarithm with short exponents" assumption. Steinfeld, Pieprzyk and Wang [START_REF] Steinfeld | On the provable security of an efficient RSA-based pseudorandom generator[END_REF] showed, that assuming the hardness of a strong variant of the RSA inversion problem modulo the integer N , one can securely output as much as (1/2 -1/e) log N bits in the RSA generator. On the other hand, Herrmann and May [START_REF] Herrmann | Attacking power generators using unravelled linearization: When do we output too much?[END_REF] showed heuristically (using Coppersmith methods [START_REF] Coppersmith | Finding a small root of a bivariate integer equation; factoring with high bits known[END_REF][START_REF]Finding a small root of a univariate modular equation[END_REF]) that an output of (1 -1/e) log N most significant bits per iteration allows for efficient recovery of the whole sequence.

Micali and Schnorr [START_REF] Micali | Efficient, perfect polynomial random number generators[END_REF] proposed a variant of the RSA generator that on a secret random initial seed value x 0 ∈ Z * N computes the intermediate values v i = x e i mod N and outputs, for some k ∈ N, the k least significant bits of v i . But the successor x i+1 of x i is formed from a separate part of v i , the remaining most significant bits (contrary to the incestuous RSA generator where x i+1 = v i ). The security of Micali-Schnorr pseudorandom generator relies on the (strong) assumption that the distribution of x e mod N for random k-bit integers is indistinguishable from the uniform distribution on Z * N . The generator is insecure if (1 -1/e) log N least significant bits are output per iteration but no better attack was proposed since its proposal 25 years ago. It remains open to know what is the maximum quantity of information that can be output per iteration allowing the generator to be efficient but still secure against potential attackers.

Our Techniques As dynamic programming, time / memory tradeoffs is a wellknown technique to reduce the time complexity of a problem using memory. Shamir and Schroeppel in [START_REF] Schroeppel | A T = O(2 n/2 ), S = O(2 n/4 ) algorithm for certain NP-complete problems[END_REF] have described such algorithms for specific NPcomplete problems such as knapsack problems. In cryptography, this technique has been used many times to analyze the security of symmetric primitives such as block ciphers or stream ciphers and some computational problems such as the baby-step giant-step algorithm to compute discrete logarithms. Basically, some computations can be done independently of other resources. For instance, using the public key the adversary can precompute some values and store a small fraction of these values in the offline phase. Then, the adversary gets some ciphertexts and his goal can be to recover the secret key.

In [START_REF] Hellman | A cryptanalytic time-memory trade-off[END_REF] Hellman described a technique to invert random looking functions. This technique has been rigorously studied in [START_REF] Fiat | Rigorous time/space trade-offs for inverting functions[END_REF] by Fiat and Naor to work for any functions and rigorous lower bounds have been given in [START_REF] Barkan | Rigorous bounds on cryptanalytic time/memory tradeoffs[END_REF] by Barkan, Biham and Shamir. Oeschlin in [START_REF] Oechslin | Making a faster cryptanalytic time-memory trade-off[END_REF] described a variant of Hellman tradeoff, but this variant has been show equivalent to Hellman tradeoff by Barkan et al. since many heuristics can be applied to Hellman technique. Finally, Babbage [START_REF] Babbage | A space/time tradeoff in exhaustive search attacks on stream ciphers[END_REF] and Golic [START_REF] Golic | Cryptanalysis of alleged A5 stream cipher[END_REF], then Biryukov and Shamir [START_REF] Biryukov | Cryptanalytic time/memory/data tradeoffs for stream ciphers[END_REF] presented tradeoff for stream cipher by using more or less data. This resource is a crucial parameter in cryptanalysis and it is important to present attacks using as low data complexity as possible.

Our contributions. In this paper, we use time/memory/data tradeoff techniques to propose algorithms for two computational problems related to the security of the Micali-Schnorr pseudorandom generator. The algorithms are decomposed into two phases: the preprocessing one where the attacker constructs large hash tables using the structure of the focused cryptosystem, and the realtime phase where it uses the data produced by the cryptosystem and the hash tables to retrieve the secrets. The three tradeoffs algorithms we describe are similar to the tradeoffs for stream ciphers. However, in order to construct such algorithms, we need to specify the function f we used. For stream ciphers, the main idea is to execute from a hidden state the generator in order to have at least log S bits of output if the state is of size S. Here, we decide to truncate the output value. It is a bit weird to define f in such a way since the iteration of such functions is no more related to the iteration of the generator. However, the only things we need is to cover the space in such a way that the inversion will be possible. This choice of function f is suitable for Micali-Schnorr generator but does not work for the BBS or the RSA generator. Moreover, in order to prove that the many Hellman tables algorithm works (our third algorithm), we need to prove that each table uses an independent function. We provide such claim in the analysis of the third algorithm. Indeed, this independence assumption is in fact the tricky part of the analysis and Hellman paper relies on heuristic in order to provide lower bounds on the time complexity of his scheme. Using a computational argument we prove that the considered functions are independent.

Our algorithms do not contradict the strong assumption used for the Micali-Schnorr pseudorandom generator. They can be applied even though only a small part of the generator is output at each iteration. Moreover, we will show that once one value is recovered using the algorithms we describe for the first problem, then we are also able to retrieve the seed by using another time/memory tradeoff.

Finally, even if our algorithms beating the bound remain exponential, we achieve to decrease the constant and that can be very interesting in cryptography (for example, in the case of the factorization).

Organization of the paper. In Section 2, we present the first problem we look at and basics about the Micali-Schnorr pseudorandom generator. We explain why the problem is easy for some small parameters. In Section 3, we describe three time/memory algorithms for solving the first problem using different tradeoffs. In Section 4, we show other tradeoffs to recover the seed of the generator.

Micali-Schnorr Pseudorandom Generator

The Micali-Schnorr pseudorandom generator is defined by the recursive sequence (v i = x e i-1 mod N ) for i ≥ 1, with (e, N ) the RSA public key, x 0 ∈ [0, 2 r [ the secret seed of size 2 r and v i = 2 k x i +w i . At each iteration, this generator outputs the k least significant bits of v i , denoted by w i . In addition, denoting n the size of the modulus N , only x i of size r = n -k, unknown, is reused for the next iteration. Since the generator outputs O(k/ log e) bits per multiplication, one wants k to be as large as possible and e to be as small as possible. This pseudorandom generator is proven secure under the following assumption:

Assumption 1 The distribution of x e mod N for random r-bit integers is indistinguishable by all polynomial-time statistical tests from the uniform distribution of elements of Z * N .

Description of the problem. Let (e, N ) the RSA public key with N of size n.

Using the equality v i = 2 k x i + w i where v i ∈ Z N , w i ∈ [0, 2 k ) and x i ∈ [0, 2 r ), we consider the recurrence sequence

∀i ≥ 1, v i = x e i-1 mod N (1)
Given (e, N, r), {w 1 , • • • , w j } with j ∈ N, the problem consists in retrieving one value x c with c ∈ {0, • • • , j -1}. For an attacker, finding one of the values x i using some iterations of the Micali-Schnorr pseudorandom generator will lead to infer its next outputs. The difficulty of the above problem depends highly on the value of r. Figure 1 sums up this hardness, with a transition value equal to n/e. We first explain why it is easy to solve the problem when the size of r is less than n/e. Proof. If r ≤ n/e, the modular reduction is not performed in Equation 1, so v 1 = x e 0 over the integers and using v 1 = 2 k x 1 + w 1 , one has the following modular equation:

x e 0 = w 1 mod 2 k where all the values except x 0 are known. We now use the well-known Hensel's lifting lemma to retrieve this secret value.

Lemma 1 (Hensel's lifting lemma). Let p be a prime and c be a positive integer. One denotes f a polynomial having a root x modulo p c which satisfies:

f (x) = 0 mod p c and f ′ (x) = 0 mod p
Then, one can lift x to obtain an unique nontrivial root x * ∈ [0, p c+1 ) verifying:

f (x * ) = 0 mod p c+1 and x * = x mod p c
With Lemma 1, by using f (x) = x e -w 1 , one can reconstruct bit per bit x 0 looking at the powers of 2. The value x * can be efficiently computed by

x * = x + λ • 2 c where λ = -f (x) 2 c • (f ′ (x)) -1 mod 2. ⊓ ⊔
Note that if the value x 0 is even, one loses the uniqueness of the lift. However, computing x e -w 1 mod 2 k for each candidate x of size r can suffice to retrieve this value; else one tests another output w i of the generator. Another possibility to retrieve the seed consists in raising w 1 to the power e -1 mod 2 k-1 (notice that e is odd). However the complexity of Hensel lifting is linear in the size of the root, contrary to this exponentiation. To avoid this simple algorithm but to remain efficient, i.e to output a maximum of bits per iteration, the parameter k has to be smaller than ⌊n(1 -1 e )⌋. Finally, it seems hard to find a polynomial-time algorithm if r > n/e, for example by using Coppersmith techniques, which are techniques bases on lattice reduction to find small modular roots.

Solving the Problem using Time/Memory/Data Tradeoffs

For now, we consider the problem in the case where r is larger than n/e and we will present three similar algorithms that use different tradeoffs in order to solve the problem. These algorithms use the fact that only the hidden information, i.e the value x i of a relatively small size r, is recycled for the next iteration contrary to some other pseudorandom generators as the BBS or the RSA ones. We denote the five key parameters as follows:

-2 r represents the cardinality of the search space.

-P represents the time required by the preprocessing phase of the algorithm.

-M represents the quantity of access memory required for the algorithm.

-T represents the time required by the online phase of the algorithm.

-D represents the quantity of data required for the algorithm.

First algorithm

The first algorithm is quite simple to explain and to implement but not really efficient. The preprocessing phase consists in storing the couples (x, LSB k (x e mod N )) for some different values of x in a hash table. During the online phase, one tests for each value w i if it appears in the hash table. For example, it will work by taking M = 2 r/3 and D = T = 2 2r/3 or even M = T = D = 2 r/2 . The proof is given in the full version of this paper.

Second algorithm using one Hellman's table

The two next algorithms are based on [START_REF] Hellman | A cryptanalytic time-memory trade-off[END_REF][START_REF] Biryukov | Cryptanalytic time/memory/data tradeoffs for stream ciphers[END_REF]. Hellman then Biryukov and Shamir have proposed different attacks using tradeoffs for breaking block ciphers and stream ciphers. We define a special function in order to apply these attacks for solving our problem, and thus for the Micali-Schnorr pseudorandom generator. This second algorithm gives the same tradeoff as the first one, but need less data: for M = 2 r/3 and T = 2 2r/3 , it just requires a bit more than 2 r/3 data. Proof. Algorithm. Let f be the function defined by f (x) = LSB r (x e mod N ) where LSB r (x) represents the r least significant bits of x. The preprocessing phase consists in computing for m random different values

x 1 0 , • • • , x m 0 the values f t (x 1 0 ), • • • , f t (x m 0 )
with m, t ∈ N and where f t means that the function f is iterated t times. The construction of a hash table containing the f t (x i 0 ) as keys and the x i 0 as associated values, for i ∈ {1, • • • , m}, concludes this phase. The algorithm in online phase works as follows:

1. One selects a known value w j for j > 0. 2. One considers only the r least significant bits of w j , denoted by z j . 3. For i ∈ {0, • • • , t}, one tests if f i (z j ) is a key of the hash function. If the t + 1 tests fail, one selects the next known value and restarts the algorithm. 4. If a test succeeds, denoting the associated value x c 0 , one has:

f t-i (x c 0 ) = z j = f (f t-i-1 (x c 0 ) X )
X is a value of size r that corresponds with high probability to the hidden part of the generator at the previous iteration. A simple verification consists of the computation of the value X e mod N .

Value Hellman's Matrix for our algorithm

Key

x 1 0 f -→ f (x 1 0 ) f -→ • • • f -→ f t-1 (x 1 0 ) f -→ f t (x 1 0 ) . . . . . . x c 0 f -→ • • • f -→ X step 4 f -→ z j f -→ • • • f -→ step 3 f i (z j ) . . . . . . x m 0 f -→ f (x m 0 ) f -→ • • • f -→ f t-1 (x m 0 ) f -→ f t (x m 0 )
Table 1. Computation of our algorithm using a hash table

Table 1 gives an overview of the algorithm by manipulating the hash table and using the function f .

Complexity. The number of different values in this table can be estimated as follows (the end value of each chain is not counted):

E(#{f j (x i 0 ), 1 ≤ i ≤ m, 0 ≤ j < m}) = m i=1 t-1 j=0 P r[A i,j ]
where A i,j the event [f j (x i 0 ) / ∈ {f j ′ (x i ′ 0 ), i ′ < i or j ′ < j}]. Note that A i,j ⊆ A i,j-1 (since f j (x i 0 ) = f j-1 (x i 0 )). Moreover, we have the following property:

P r[A i,j |A i,j-1 ] ≥ 1 - it 2 r ⇒ P r[A i,j ] ≥ 1 - it 2 r j+1
Hence, the probability p that the value we search is in the Hellman's table is greater than 2 -r m i=1 t-1 j=0 (1 -it 2 r ) j+1 . By denoting D the number of known values of the recurrence, the time required by the preprocessing phase of the algorithm P is equal to O(mt), the memory M and the time of the algorithm T are defined by M = O(m) and T = O(Dt). For each known value of the recurrence, one has a probability p depending on the size of the table to success, and thus we need

Dp = O(1). If mt 2 ≪ 2 r then p ≈ 2 -r mt. Consequently we obtain the tradeoff Dt • m = O(2 r ), i.e T M = 2 r with T ≤ D 2 (due to mt 2 ≪ 2 r ).
As the table gets larger, some chains will eventually collide and merge due to the birthday paradox. So it may be preferable to use many small tables, that is the next attack. Finally note that, at step 4, each value f i (z j ) may have multiple predecessors, hence there is a small probability that f t-i (x c 0 ) will not be equal to z j . In this case, one tries an other output but it is clear that these "false alarms" will increase the complexity by only a small constant factor. ⊓ ⊔

Third algorithm using many Hellman tables

This last algorithm which uses more tables, proposes then another repartition between the memory, the time and the data. For example, for M = 2 5r/8 , T = 2 r/2 and D = 2 r/8 , this tradeoff is preferable compared to the first two algorithms. This set of tables covers a larger fraction of the possible output values and consequently, the online phase need less data. Each table requires a specific function and, in order to cover different independent output values, the functions need to be independent. In [START_REF] Hellman | A cryptanalytic time-memory trade-off[END_REF], Hellman rigorously calculated a lower bound on the expected coverage of images by a single table which is essentially the same analysis we did in the previous algorithm. However, the analysis for the full scheme (with many tables) is highly heuristic and is based on the unjustifiable assumption that many simple variants of f are independent of each other. Fiat and Naor in [START_REF] Fiat | Rigorous time/space trade-offs for inverting functions[END_REF] propose to use k-wise independent functions in order to propose an algorithm to invert any function, while Hellman assumes that the function is random. In order to replace the heuristic, one could think of using independent functions for each table by computing g i = h i • f , where {h i } i is a family of k-wise independent functions. The main drawback is that the number of such functions we need is exponential and it is not easy to construct such functions. Here, we want to avoid Hellman heuristic while similar heuristic could be made. For instance, we could define many functions by considering any r bits among the n -r output bits which will give us n-r r different functions. However, many functions will have the same subset of bits and we cannot assume independence between them. The analysis of the algorithm is based on the following hypothesis: Assumption 2 Denoting f (x) = LSB r (x e mod N ), the distribution of f (x) for random r ′′ -bit integers (r ′′ ≥ r) x is indistinguishable by all polynomial-time statistical tests from the uniform distribution of integers in [0, 2 r ). Proof. Algorithm. The third algorithm is similar to the second one but, instead of using a single table, one uses ℓ = t/D hash tables of size mt (assuming that t > D). First, one has to find which table covers the output value. Then one applies the second algorithm. Consequently, the search of the table requires to look for each value in all tables in parallel. Complexity. Using the same analysis as for the second algorithm, we know that we cover a fraction mt/2 r of the output values with one table. Now, using ℓ tables, we want to prove that the number of output values we cover is mtℓ. To prove such result, we have to solve the independence problem, namely that to describe independent functions for each table so that we are still able to invert f . First of all, the whole output of the n -r least significant bits of x e mod N can be used. But this only allows us to construct a constant number of functions. Our second idea is to use the fact that f is a random function or that its outputs are indistinguishable from the uniform distribution (Assumption 2). By using ℓ random and independent values z i ∈ [0, 2 r ′ ), we can define ℓ functions as g i (x) = f (x + z i • 2 r ) for i ∈ {1, • • • , ℓ}. We claim that this set of functions is independent, otherwise assumption 2 will be wrong for r ′′ = r + r ′ . Using the same notations as in the previous proof, the probability p that the value we search is in one of the ℓ Hellman's tables is greater than 1 -1 -

2 -r m i=1 t-1 j=0 (1 -it 2
r ) j+1 ℓ and p ≈ 2 -r mtℓ if mt 2 ≪ 2 r . We clearly have M = O(mℓ), T = O(Dtℓ) and P = O(mtℓ). For ℓ = t/D, we obtain the tradeoff

T M 2 D 2 = O(2 2r ) with D 2 ≤ T ≤ 2 r . ⊓ ⊔ Remark 1.
This tradeoff is less constraining than Hellman tradeoff: we only need that one value is in one table and not that a particular value.

4 Inverting RSA for Small Plaintext Problem

By using one of the previous algorithms, one knows the value of a hidden part of the generator denoted x i for i ≥ 0. We now present two different ways to invert the Micali-Schnorr generator, i.e to retrieve the secret seed x 0 .

Description of the problem. Let (e, N ) be an RSA public key with N of size n and an integer r ≤ n. Given (N, e, r) and y = x e mod N for x ∈ [0, 2 r ), the problem consists in recovering x.

Remark 2. This problem is well-known to be solvable in polynomial time when r ≤ n/e since as before the equality holds over the integers.

Multipoint evaluation of univariate polynomials

Let P (x) ∈ Z N [x] be a polynomial of degree less than n = 2 k . The multipoint evaluation problem is the task of evaluating P at n distinct points α 0 , . . . , α n-1 ∈ Z N . Using Horner's rule, it is easy to propose a solution that uses O(n 2 ) addition and multiplication in Z N but it is well-known that one can propose an algorithm with quasi-linear complexity Õ(n) operations in Z N using a divide-and-conquer approach [START_REF] Bostan | Linear recurrences with polynomial coefficients and application to integer factorization and Cartier-Manin operator[END_REF][START_REF] Fiduccia | Polynomial evaluation via the division algorithm: The Fast Fourier Transform revisited[END_REF].

Let P 0 = n/2-1 ℓ=0 (x -α ℓ ) and P 1 = n-1
ℓ=n/2 (x -α ℓ ) and let us define R 0 = P mod P 0 and R 1 = P mod P 1 . We have R 0 (α i ) = P (α i ) for all i ∈ {0, . . . , n/2-1} and R 1 (α i ) = P (α i ) for all i ∈ {n/2, . . . , n -1} and this gives immediately a recursive algorithm (i.e. compute P 0 , P 1 , R 0 , R 1 and reduce the problem to the multipoint evaluation of R 0 and R 1 of degree n/2 = 2 k-1 ).

Let A i (x) = (x-α i ) for i ∈ {0, . . . , n-1} and P i,j = A j2 i A j2 i +1 . . . A j2 i +2 i -1 for i ∈ {0, . . . , k} and 0 ≤ j < 2 k-i . We have P 0,j = A j and P i+1,j = P i,2j P i,2j+1 so for i ∈ {0, . . . , k} we can compute recursively all polynomials P i,j and 0 ≤ j < 2 k-i in 2 k-i-1 O(M (2 i )) = O(M (n)) operations in Z N where M (i) denotes the arithmetic complexity to compute the product of two polynomials of degree i in Z N [x]. Overall, the computation of all polynomials P i,j requires O(M (n) log n) operations in Z N using a tree.

The polynomials R 0 and R 1 can be computed using O(M (n)) operations in Z N (using a Newton inversion), hence the complexity T (n) of the recursive algorithm satisfies T

(n) = 2T (n/2) + O(M (n)) and therefore T (n) = O(M (n) log n).
The multipoint evaluation of univariate polynomials has found numerous application in cryptanalysis (e.g. [START_REF] Coron | Cryptanalysis of the RSA subgroup assumption from TCC[END_REF][START_REF] Chen | Faster algorithms for approximate common divisors: Breaking fully-homomorphic-encryption challenges over the integers[END_REF]). In our case, it is clear that using this technique will lead to retrieve the seed. For example, using the same notations as in preliminaries, suppose that we know the value of v i and want to retrieve the value of x i-1 of the generator. That can be done by multipoint evaluating the polynomial of degree e(2 r/2 + 1):

P (X) = (X e -v i )((X + 1) e -v i )((X + 2) e -v i )...((X + 2 r/2 ) e -v i ) mod N on the points k • 2 r/2 for k = 0, • • • , 2 r/2 in order to find k c such that P (k c • 2 r/2 ) = 0 mod N . Then, one searches the value of x i-1 on the form k c • 2 r/2 + ℓ for ℓ = 0, • • • , 2 r/2
. This technique requires Õ(e • 2 r/2 ) operations in Z N . Its complexity is linear in e but, as mentioned above, e is chosen as small as possible in practice. Moreover, one has to store the first tree, i.e 2 r/2 polynomials.

Remark 3. This algorithm can be applied to attack the RSA encryption system when used to encrypt a short secret key of a symmetric cipher. Our algorithm is slightly less efficient than the one in [START_REF] Boneh | Why textbook ElGamal and RSA encryption are insecure[END_REF] but it always succeeds (whereas recovering a 40-bit plaintext for instance is successful only with probability 0.39 in [START_REF] Boneh | Why textbook ElGamal and RSA encryption are insecure[END_REF]).

Coppersmith's method

Another technique is based on the well-known Coppersmith's method for the case of a modular univariate polynomial. In 1996, Coppersmith introduced latticebased techniques for finding small roots on univariate and bivariate polynomial equations in polynomial time [START_REF]Finding a small root of a univariate modular equation[END_REF][START_REF] Coppersmith | Finding a small root of a bivariate integer equation; factoring with high bits known[END_REF]. Some recalls are done in the full version. In our case, starting from the equation x e i-1 = v i mod N , we can define the following modular univariate polynomial f as f (x) = x e -v i mod N . The value x i-1 represents a small modular root of this polynomial. However, our root of size r is not enough small for this technique which requires the root to be less than N 1/e , i.e r < n/e (see [START_REF]Finding a small root of a univariate modular equation[END_REF]). To circumvent this problem, one can guess j bits of x in order to have r -j < n/e and then apply Coppersmith's method for each guess. Instead of f , one uses the polynomial g of degree e: g(x) = (λ + x) e -v i mod N with λ the guessed value of j bits. The truncated value of x i-1 denoted by x tr i-1 is a small modular root of g. Its degree being the same, the asymptotic condition on the size of the root remains the same. The followng theorem, proved in the full version, establishes the condition on the bound: Theorem 5. Using the set of polynomials {x j g i |j ≤ e -1 ∧ i ≤ p -1} ∪ {g p } with p ∈ N, Coppersmith's method will return x tr i-1 as long as x tr i-1 < N δ with:

Conclusion

In this paper, for the first time, we have shown that, for all recommended parameters, we are able to predict the Micali-Schnorr pseudorandom generator faster than by an exhaustive search by using time/memory tradeoff or time/memory/data tradeoff attacks. These attacks are feasible only because of the specificity of this generator that uses only a small number to iterate and it remains a open problem to design a time/memory tradeoff algorithm able to infer sequences produced by the BBS or the RSA generator (in the range of parameters not covered by Herrmann and May techniques [START_REF] Herrmann | Attacking power generators using unravelled linearization: When do we output too much?[END_REF]). We have also proposed three techniques (the last one is explained in the full version) to reverse the generator and retrieve the generator seed. An interesting open question is to decrease the memory requirement of our algorithms. The ρ or λ methods for factoring and discrete logarithms (which were invented by Pollard) use pseudorandom walks and require polynomial (or even constant) memory rather than exponential as in our time/memory tradeoffs. They can be applied to attack Gennaro's efficient pseudorandom generator based on the discrete logarithm [START_REF] Gennaro | An improved pseudo-random generator based on the discrete logarithm problem[END_REF] but it remains open to adapt this approach to predict the Micali-Schnorr pseudorandom generator.

Fig. 1 .Theorem 1 .

 11 Fig. 1. Difficulty of the problem depending of the value r

Theorem 2 .

 2 Given (e, N ) and D consecutive values w 1 , • • • , w D , there exists an algorithm which retrieves one of the values x 0 , • • • , x D-1 in time T , by using M random access memory such that T M = O(2 r ) with D = O(T ).

Theorem 3 .

 3 Given (e, N ) and D consecutive values w 1 , • • • , w D , there exists an algorithm which retrieves one of the values x 0 , • • • , x D-1 in time T , by using M random access memory such that T M = O(2 r ) with T ≤ D 2 .

Theorem 4 .

 4 Given (e, N ) and D consecutive values w 1 , • • • , w D , there exists an algorithm which retrieves one of the values x 0 , • • • , x D-1 in time T , by using M random access memory such that T M 2 D 2 = O(2 2r ) with D 2 ≤ T ≤ 2 r .

e 2 p + 2 1 e

 21 Starting from a basis (b 1 , • • • , b w ) of a lattice of Z m , this technique works in complexity O(w 4 m log B(w + log B)) with B = max 1≤i≤w b i , and we have to store the lattice of size w + m. By denoting x tr i-1 < N •(1-ǫ) with 0 < ǫ < 1, one can determine the minimal value for p in order to retrieve the root, i.e p = e-1-ǫ eǫ = O(1/ǫ). The number of polynomials w being equal to e(p -1) + 1 = O( e ǫ ), those of monomials m being equal to ep + 1 = O( e ǫ ) and log B = n, this technique will require O(2 r-n e •(1+ǫ) ( e 6 n ǫ 6 + e 5 n 2 ǫ 5 )) in time and O( e ǫ ) 2 in memory.

† ENS, CNRS & INRIA -UMR 8548

N is a Blum integer if N = pq with p and q primes and p, q ≡ 3 mod 4

Acknowledgements. This work was supported in part by the French ANR-12-JS02-0004 ROMAnTIC Project.