Thomas Fuhr
email: thomas.fuhr@ssi.gouv.fr

Henri Gilbert
email: henri.gilbert@ssi.gouv.fr

Jean-René Reinhard
email: jean-rene.reinhard@ssi.gouv.fr

Marion Videau
email: marion.videau@ssi.gouv.fr

Analysis of the Initial and Modified Versions of the Candidate 3GPP Integrity Algorithm 128-EIA3

Keywords: cryptanalysis, message authentication codes, existential forgery attacks, universal hashing

In this paper we investigate the security of the two most recent versions of the message authentication code 128-EIA3, which is considered for adoption as a third integrity algorithm in the emerging 3GPP standard LTE. We first present an efficient existential forgery attack against the June 2010 version of the algorithm. This attack allows, given any message and the associated MAC value under an unknown integrity key and an initial vector, to predict the MAC value of a related message under the same key and the same initial vector with a success probability 1/2. We then briefly analyse the tweaked version of the algorithm that was introduced in January 2011 to circumvent this attack. We give some evidence that while this new version offers a provable resistance against similar forgery attacks under the assumption that (key, IV) pairs are never reused by any legitimate sender or receiver, some of its design features limit its resilience against IV reuse.

Introduction

A set of two cryptographic algorithms is currently considered for inclusion in the emerging mobile communications standard LTE of the 3rd Generation Partnership Project 3GPP. It consists of an encryption algorithm named 128-EEA3 and an integrity algorithm named 128-EIA3 1 -that are both derived from a core stream cipher named ZUC. The algorithms ZUC, 128-EEA3, and 128-EIA3 were designed by the Data Assurance and Communication Security Research Center (DACAS) of the Chinese Academy of Sciences.

An initial version of the specifications of 128-EEA3/EIA3 and ZUC, that is referred to in the sequel as v1. [START_REF]Specification of the 3GPP Confidentiality and Integrity Algorithms UEA2 & UIA2. Document 1: UEA2 and UIA2 Specification[END_REF], was produced in June 2010 and published on the GSMA web site for an initial public evaluation [START_REF]ETSI/SAGE: Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3[END_REF][START_REF]SAGE: Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3[END_REF]. Following the discovery of some cryptographic weaknesses in the ZUC v1.4 initialisation [START_REF] Wu | Cryptanalysis of the Stream Cipher ZUC in the 3GPP Confidentiality & Integrity Algorithms 128-EEA3 & 128-EIA3[END_REF][START_REF] Sun | Preliminary Cryptanalysis Results of ZUC[END_REF] and of the forgery attack on 128-EIA3 v1.4 reported in this paper, tweaks to the specifications of ZUC and EIA3 were introduced by the designers and a modified version of the specifications referred to in the sequel as v1.5 was published in January 2011 for a second public evaluation period [START_REF]Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3[END_REF][START_REF]Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3[END_REF]. After its adoption by 3GPP, 128-EEA3/EIA3 will represent the third LTE encryption and integrity algorithm set, in addition to the already adopted sets 128-EEA1/EIA1 [START_REF]Specification of the 3GPP Confidentiality and Integrity Algorithms UEA2 & UIA2. Document 1: UEA2 and UIA2 Specification[END_REF] based on the stream cipher SNOW 3G and 128-EEA2/EIA2 [1, Annex B] based on AES.

The integrity algorithm 128-EIA3 is an IV-dependent MAC that takes as input (1) a 128-bit key, (2) various public parameters that together determine a 128-bit initial vector, (3) an input message of length between 1 and 20000 bits, and produces a 32-bit MAC value. It uses an universal hash function-based construction and has therefore many features in common with the algorithms of the well known Wegman-Carter family of message authentication codes [START_REF] Carter | Universal Classes of Hash Functions[END_REF][START_REF] Wegman | New Hash Functions and Their Use in Authentication and Set Equality[END_REF].

As already mentioned, we denote by 128-EIA3 v1.4 (resp. 128-EIA3 v1.5) the initial version specified in [START_REF]ETSI/SAGE: Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3[END_REF] (resp.the modified version specified in [START_REF]Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3[END_REF]). In this paper we analyse the security of both versions. We first show that 128-EIA3 v1.4 is vulnerable to a simple existential forgery attack. Given any known message M , any known or unknown initial vector, and the associated MAC under an unknown key, it is possible to predict the MAC value associated with a new message M ′ = M derived from M under the same initial vector and the same unknown key, with a success probability 1/2. This attack is generic, it does not rely on any specific feature of ZUC and works with any underlying stream cipher. It exploits a subtle deviation of 128-EIA3 v1.4 from the requirements of the Wegman-Carter paradigm. The latter requirements can be informally summarized by saying that mask values must behave as one-time masks, which is not the case for 128-EIA3 v1.4. As will be shown in the sequel, distinct 128-EIA3 v1.4 mask values are not necessarily independent. Indeed, in 128-EIA3 v1.4, the mechanism used to generate the masking values applied to the output of the universal hash function does not match the model used in the proof. Consequently, the arguments from [START_REF] Krawczyk | LFSR-based Hashing and Authentication[END_REF] and [START_REF] Shoup | On Fast and Provably Secure Message Authentication Based on Universal Hashing[END_REF] that are invoked in the design and evaluation report [START_REF]Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3[END_REF] to infer bounds on the success probability of forgery attacks on 128-EIA3 v1.4 are not applicable.

In [START_REF]Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3[END_REF], a tweak leading to 128-EIA3 v1.5 has been proposed to circumvent this attack. Through an improved generation procedure, masking values are either equal or independent. However, it can be observed that for distinct messages, no separation between the ZUC keystream bits involved in the universal hash function computation and those involved in the generation of the masking values is ensured.

While this represents a deviation from the requirements on masking values used in the Wegman-Carter paradigm, the security consequences are much less dramatic than for the initial MAC (v1.4) since an ad hoc proof given in [START_REF]Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3[END_REF] allows to show that the modified MAC offers a provable resistance against existential forgery attacks under the assumption that the same (key, IV) pair can never be re-used, neither by the MAC issuer nor by the MAC verifier. We show that this property however affects the resilience of 128-EIA3 v1.5 against forgery attacks if IV repetitions occur. We further observe that independently of this property, the universal hash function structure also results in some limitations of this resilience. This leads us to investigate the resistance of 128-EIA3 v1.5 and one natural variant of this MAC against forgery attacks involving three pairwise distinct messages and the same IV value. We make no claims regarding the practical applicability of the identified nonce repetition attacks to the LTE system.

In Section 3, we give a short description of the 128-EIA3 algorithms. We then describe the attack on v1.4 in Section 4 and discuss the reasons why the security proofs for related constructions by Krawczyk [START_REF] Krawczyk | LFSR-based Hashing and Authentication[END_REF] and Shoup [START_REF] Shoup | On Fast and Provably Secure Message Authentication Based on Universal Hashing[END_REF] do not guarantee the security of 128-EIA3 v1.4. In Section 5, we state a property which, although it may not be considered as an attack in standard security models, underscores the lack of robustness of 128-EIA3 v1.5 against nonce repetition. We also explain why a simple modification of 128-EIA3 fails to completely suppress such properties because of the universal hashing underlying structure.

Notation

Throughout the paper, we use the following notation.

-S is a stream cipher.

-For two finite bitstrings A = (a 0 , . . . , a ℓ-1 ) and B = (b 0 , . . . , b m-1 ), A B denotes the concatenation of A and B, i.e. the bitstring (a 0 , . . . , a ℓ-1 , b 0 , . . . , b m-1 ).

-For a bitstring A = (a 0 , . . .) of length ≥ j + 1, A| i j , 0 ≤ i ≤ j, denotes the (j-i+1)-bit string obtained from the consecutive bits of A between indices i and j, i.e. A| i j = (a i , . . . , a j ). -0 ℓ denotes the bitstring of length ℓ whose bits are all zero.

-W (i) denotes the i-th bit of a 32-bit word W .

-Let consider a 32-bit word W = (W (0) , . . . , W (31) ) and an integer a between 1 and 31. Then W ≪ a denotes the (32 -a)-bit word resulting from a left shift of W by a positions and a truncation of the a rightmost bits. More precisely, W ≪ a = (W (a) , . . . , W (31) ). The (32 -b)-bit word, W ≫ b, resulting from the right shift of W by b positions and a truncation of the b leftmost bits is defined in the same way. We have W ≫ b = (W (0) , . . . , W (31-b) ). 23 Description of the 128-EIA3 Integrity Algorithms

The integrity algorithms 128-EIA3 make a black box use of a stream cipher to generate a keystream from a key and an initial value. A stream cipher S is an algorithm that takes as input a k-bit key IK and an nbit initialisation value IV and outputs a binary sequence z 0 , . . . , z i , . . . named the keystream. The keystream is used to compute a 32-bit MAC value Tag according to the procedure described in Algorithm 1 which includes versions v1.4 and v1.5 for conciseness. Stated differently, the MAC value T associated with IK, IV , and an ℓ-bit message M = (m 0 , . . . , m ℓ-1 ) is derived by accumulating (for a set of positions i determined by the message bits and the message length) 32-bit words W i = (z i , . . . , z i+31 ) extracted from the keystream by applying it a 32-bit "sliding window":

T = ( ℓ-1 i=0 m i W i ) ⊕ W ℓ ⊕ W mask ,
where W mask = W L-32 with the value L being different between v1.4 and v1.5, i.e. W mask = W ℓ+32 for v1.4 and W mask = W ⌈ ℓ 32 ⌉×32+32 for v1.5. The parameter lengths used in 128-EIA3 are: k = n = 128 and 1 ≤ ℓ ≤ 20000.

In fact, the MAC of a message M is computed as

M AC(M ) = H (z 0 ,...,z ℓ+31 ) (M ) ⊕ W mask , Algorithm 1
The 128-EIA3 MAC algorithms

Input: IK ∈ {0, 1} k , IV ∈ {0, 1} n , 1 ≤ ℓ ≤ 20000 Input: M = (m0, . . . , m ℓ-1 ) ∈ {0, 1} ℓ if v1.4 then L = ℓ + 64 else if v1.5 then L = ℓ 32
× 32 + 64 {This is the only difference between v1.4 and v1.5}

end if (z0, . . . , zL-1) ← S(IK, IV )| 0 L-1 Tag = 0 for i = 0 to ℓ -1 do Wi ← (zi, . . . , zi+31) if mi = 1 then Tag ← Tag ⊕ Wi end if end for W ℓ ← (z ℓ , . . . , z ℓ+31 ) Tag ← Tag ⊕ W ℓ W mask ← (zL-32, . . . , zL-1) Tag ← Tag ⊕ W mask return Tag
where H (.) is a family of universal hash functions based on Toeplitz matrices with pseudorandom coefficients taken from a stream cipher output. We have:

H (z 0 ,...,z ℓ+31 ) (m 0 , . . . , m ℓ-1 ) = [m 0 , m 1 , . . . , m ℓ-1 , 1] •        z 0 z 1 . . . z 31 z 1 z 2 . . . z 32 z 2 z 3 . . . z 33 . . . . . . . . . . . . z ℓ z ℓ+1 . . . z ℓ+31        .
4 An Existential Forgery Attack against 128-EIA3 v1.4

In this section we describe an attack on the first version of 128-EIA3, that we call 128-EIA3 v1.4. This algorithm has some specific properties that we will now exploit to transform a valid MAC for a message M into a valid MAC for a message M ′ related to M .

Description of the substitution attack

We can notice that the words W i derived from the keystream and corresponding to message bits m i are not independent from each other. More precisely, we have:

W i+1 = ((W i ≪ 1), z i+32 ).
Moreover the "one-time masks" W mask associated with identical values of IV but different message lengths are related. We have:

W mask = (z ℓ(M )+32 , . . . , z ℓ(M )+63 ),
where ℓ(M ) denotes the length of the message M . Let us suppose that W mask is the one-time mask generated for the input (IK, IV, M ) and W ′ mask is the one-time mask generated for the input (IK, IV, M ′ ). If ℓ(M ′ ) -ℓ(M ) = ∆ℓ with 0 < ∆ℓ < 32, we have:

W ′ mask = (W mask ≪ ∆ℓ, β 0 , . . . , β ∆ℓ-1
), for some bit values β i . We can use these relations in a substitution attack.

Let us suppose that the adversary knows a valid MAC value T a given message M = (m 0 , . . . , m ℓ-1 ) of length ℓ bits under a given IV value IV and a key IK. This MAC can be transformed with probability 1/2 into a valid MAC, T ′ , for the (ℓ + 1)-bit message M ′ = (0, m 0 , . . . , m ℓ-1 ) under the same IV value IV and the same key IK.

Let us analyse what happens during the computation of the MAC for M ′ (under the same IV value IV and the same key IK). The generated keystream z 0 , . . . , z ℓ+64 is the same as the keystream that was used to compute T , with one extra bit: z ℓ+64 . As a consequence, the words W i , 0 ≤ i ≤ ℓ are identical. The one-time mask used is W ′ mask = (z ℓ+33 , . . . , z ℓ+64 ) = ((W mask ≪ 1), z ℓ+64 ). Then, the MAC value T ′ is given by the following formula:

T ′ = ℓ i=0 m ′ i W i ⊕ W ℓ+1 ⊕ W ′ mask = ℓ-1 i=0 m i W i+1 ⊕ W ℓ+1 ⊕ W ′ mask = ℓ-1 i=0 m i ((W i ≪ 1), z i+32 ) ⊕ (W ℓ ≪ 1, z ℓ+32 ) ⊕ ((W mask ≪ 1), z ℓ+64 ) = ℓ-1 i=0 m i W i ⊕ W ℓ ⊕ W mask ≪ 1, β = (T ≪ 1, β) , with β = ℓ-1 i=0 m i z i+32 ⊕ z ℓ+32 ⊕ z ℓ+64 .
The value (T ≪ 1, β) is thus a valid MAC for M ′ . Knowing T , the adversary only needs to guess the value of bit β, which happens with probability 1/2. This attack can naturally be generalized by recurrence to generate a valid MAC for (0 r ||M ), with probability 2 -r , when r < 32 : the corresponding tag is then T r = ((T ≪ r), β 0 , . . . , β r-1 ) for some value of the bits (β 0 , . . . , β r-1 ).

Equivalently, we have that T = (α 0 , . . . , α r-1 , T r ≫ r). This equation enables an adversary to transform a valid MAC IV, T r for (0 r ||M ) into a valid MAC for M with probability 2 -r .

The attack was checked for r = 1 and larger values of r on a few examples, using the implementation programs provided in the annexes of the specification documents [START_REF]ETSI/SAGE: Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3[END_REF][START_REF]SAGE: Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3[END_REF].

Partial Flaw in 128-EIA3 v1.4 Security Arguments

The Design and Evaluation Report [START_REF]Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3[END_REF] that accompanied version 1.4 erroneously invokes the security proofs of [START_REF] Shoup | On Fast and Provably Secure Message Authentication Based on Universal Hashing[END_REF] to infer that in the case of 128-EIA3 v1.4, no forgery of a new message can succeed with probability higher than 2 -32 . The argument comes from the fact that the algorithm makes use of an ε-almost XOR universal (ε-AXU) family of hash functions with ε = 2 -32 . Definition 1. [START_REF] Carter | Universal Classes of Hash Functions[END_REF][START_REF] Wegman | New Hash Functions and Their Use in Authentication and Set Equality[END_REF][START_REF] Stinson | Universal Hashing and Authentication Codes[END_REF][START_REF] Krawczyk | LFSR-based Hashing and Authentication[END_REF][START_REF] Rogaway | Bucket Hashing and its Application to Fast Message Authentication[END_REF] A family of hash functions {H K } K∈{0,1} k of range {0, 1} t is ε-AXU if for any two distinct messages M, M ′ in {0, 1} * and any c ∈ {0,

1} t P r K∈{0,1} k [H K (M ) ⊕ H K (M ′ ) = c] ≤ ε.
In [START_REF]Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3[END_REF], a proof is given that for any value of IV , the family of hash functions used in 128-EIA3, i.e. the intermediate value obtained in the MAC computation associated with key K just before before the exclusive or with W mask is ε-AXU with ε = 2 -32 .

As far as we know, the first construction of a secure MAC using ε-AXU hash functions has been issued by Krawczyk [START_REF] Krawczyk | LFSR-based Hashing and Authentication[END_REF], who proved that given H K (M ) ⊕ r for secret uniformly drawn values of K and r, an adversary cannot determine H K (M ′ ) ⊕ r with probability higher than ε. The onetime mask generation issue is briefly addressed by noticing that in most practical applications, the mask generation will rely on a stream cipher.

In [14, Appendix B], the security notions related to a Wegman-Carter MAC scheme using a pseudorandom function producing the one-time mask from a counter cnt is stated. In [15, Proposition 14], the probability of a forgery success is computed. The scheme is defined by: a finite PRF F : {0, 1} κ × {0, 1} n → {0, 1} t , a counter cnt ∈ {0, 1} n , and a family of universal hash functions {H K } K∈{0,1} k . The computation and the verification of MACs require to share an integrity key that consists of a random a ∈ {0, 1} κ and a random K ∈ {0, 1} k . At most 2 n messages may be MACed with the same key a, and

M AC(M ) = (cnt, F a (cnt) ⊕ H K (M )).
All the models used for the proofs assume that the hash function and the pseudorandom function are randomly chosen and in particular that they are independent from each other. In the case of 128-EIA3 v1.4, the construction does not fit the model as the two are related. Moreover, what makes our attack work is that the one-time masks used for messages M and M ′ of distinct lengths are different but related. In fact, we have:

M AC(M ) = (cnt, S(IK, cnt)| ℓ(M )+32 ℓ(M )+63 ⊕ H S(IK,cnt)| 0 ℓ(M )+31 (M )).
We see that the mask computation also involves the message length and leads to distinct, but related mask values, for identical IVs and different message lengths. Therefore no existing proof applies and we manage to derive an attack against v1.4.

Sensitivity of 128-EIA3 v1.to Nonce Reuse

In order to resist to our forgery attack, 128-EIA3 has been tweaked [START_REF]Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3[END_REF], leading to the specification of 128-EIA3 v1.5. This new version corresponds to the condition v1.5 in Algorithm 1. The tweak ensures that mask values generated by the algorithm for a given (key, IV) pair for different messages are either equal or independent through an improved selection of the location in the keystream from which the mask value is extracted:

W mask = (z L-32 , . . . , z L-1 ), with L = ℓ(M ) 32 × 32 + 64.
This comes at the cost of using a slightly longer part of the keystream. Although this ensures resistance against forgery attacks under the assumptions that (1) neither the MAC issuer nor the MAC verifier reuse any IV value under the same key and the (2) the keystream bits generated by ZUC are indistiguishable from random, as proven in [10, Section 11], we remark that this scheme remains fragile towards IV reuse.

In [START_REF] Rogaway | Bucket Hashing and its Application to Fast Message Authentication[END_REF][START_REF] Shoup | On Fast and Provably Secure Message Authentication Based on Universal Hashing[END_REF], the question of a stateful MAC (implying a counter) against a stateless MAC (with a randomly chosen IV) is briefly discussed. It is underlined in [START_REF] Shoup | On Fast and Provably Secure Message Authentication Based on Universal Hashing[END_REF] that reliably maintaining a state may be difficult. Practical experience shows that the correct handling of IVs is not a trivial task. Indeed, there is far from a theoretical security requirement to a practical implementation of a scheme and former IV critical modes like CBC have already been subjected to attacks against practical implementations (see e.g. [START_REF] Albrecht | Plaintext Recovery Attacks Against SSH[END_REF]). Therefore we think that it is also important to assess the level of robustness of a scheme in the case of an improper handling of the IV.

In this section we expose two specific properties of 128-EIA3 v1.5, which do not affect a generic Wegman-Carter authentication scheme. These properties involve the MACs of three distinct messages under the same key/IV pair. Therefore, they might threaten the security of 128-EIA3 v1.5 if an adversary can get the MAC of two distinct messages under the same (key, IV) pair. Such an event can happen if IVs are mistakenly repeated by the MAC generating party. It can also happen without deviating from the expected behaviour of the message authentication through substitution attacks: the attacker may use verification queries to gain knowledge on the system [START_REF] Bellare | The Power of Verification Queries in Message Authentication and Authenticated Encryption[END_REF][START_REF] Handschuh | Key Recovery Attacks on Universal Hash Function Based MAC Algorithms[END_REF]. More in detail, two valid 128-EIA3 tag values can be obtained by an adversary for the same (key, IV) pair and two distinct messages with a non-negligible probability due to the short MAC size (32 bits): one from the MAC generating party and (with probability 2 -32 ) an extra one from the verifying party. This may allow the adversary to predict with certainty the MAC value of a third message with the same (key, IV) pair. 3

On the Independance of Universal Hashing Keys and Masking Values

In the following we consider tags generated using the same key/IV pair. We remark that in the case of 128-EIA3 v1.5, even though masking values for two distinct messages are either equal or independent, the independence of the universal hash function keys (i.e. the keystream bits used in the computation of the hash value) and the masking values is not guaranteed. Parts of the keystream (z i ) used as masking values for a message can be used during the universal hash function computation for a longer message, and conversely. This represents a deviation of the mask value generation of 128-EIA3 v1.5 from the Wegman-Carter paradigm. We show that consequently, while the proof of [START_REF]Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3[END_REF] guarantees that the MACs associated with two distinct messages and the same IV value are independent and uniformly distributed, the knowledge of the tags of two related messages under the same (key, IV) pair may allow to compute the tag of a third message under the same key and IV. Consider any message M 1 of arbitrary length ℓ 1 , any message M 2 of length ℓ 2 ≥ 1 + 32(⌈ ℓ 1 32 ⌉ + 1), and the message M 3 = M 2 ⊕ δ of length ℓ 3 = ℓ 2 , where δ is the bitstring of length ℓ 2 whose prefix of length ℓ 1 is M 1 and whose other bits are zero except for the two bits at positions ℓ 1 and 32(⌈ ℓ 1 32 ⌉ + 1). Then we have

M AC(M 1 ) ⊕ M AC(M 2 ) ⊕ M AC(M 3 ) = 0. Indeed, M AC(M 1 ) = ℓ 1 -1 i=0 (m 1 i W i ) ⊕ W ℓ 1 ⊕ W 32(⌈ ℓ 1 32 ⌉+1) , M AC(M 2 ) = ℓ 2 -1 i=0 (m 2 i W i ) ⊕ W ℓ 2 ⊕ W 32(⌈ ℓ 2 32 ⌉+1) , M AC(M 3 ) = ℓ 1 -1 i=0 (m 1 i W i ) ⊕ ℓ 2 -1 i=0 (m 2 i W i ) ⊕ W ℓ 1 ⊕ W 32(⌈ ℓ 1 32 ⌉+1) ⊕ W ℓ 2 ⊕ W 32(⌈ ℓ 2 32 ⌉+1)
.

Consequently, for any such triplet of pairwise distinct messages the authentication codes of two messages gives a forgery for the third one. The above 3-message forgery can be avoided by making the masking values and the universal hashing keys independent, for example by following the slightly modified MAC described in Algorithm 2.

for i = 0 to ℓ -1 do Wi ← (zi+32, . . . , zi+63) if mi = 1 then Tag ← Tag ⊕ Wi end if end for W ℓ ← (z ℓ+32 , . . . , z ℓ+63 ) Tag ← Tag ⊕ W ℓ Tag ← Tag ⊕ W mask return Tag
This algorithm is quite similar to 128-EIA3 and requires the same number of keystream bits and the same amount of computation as 128-EIA3 v1.4 -the single difference being that the mask value consists of the first keystream bits and the universal hash function output value is derived from the subsequent keystream bits. This scheme ensures the equality or independence of keystream bits used as masking values or universal hashing key when tagging two different messages. It is also closer to the Wegman-Carter paradigm in that the masking value computation does not depend on the message being tagged -which is not the case in 128-EIA3 v1.4 and v1.5, where the length of the tagged message impacts the masking value. Unfortunately some non-generic properties remain, that are related to the Toeplitz matrix structure underlying the universal hash function construction rather than to the masking values generation method and hold for both 128-EIA3 v1.5 and Algorithm 2.

On the Sliding Property of the Universal Hash Function of 128-EIA3

In Section 4 we exploited a sliding property of the universal hash function used by 128-EIA3. Let z be the keystream sequence used in the computation of the universal hash function (i.e. without the final encrypting mask value). We denote by H z the universal hash function. Using the "slidingwindow" property of the construction based on Toeplitz matrices, we can derive the following property. For r < 32, we have

H z (0 r M ) ≫ r = H z (M ) ≪ r.
Let us now consider two messages M and M ′ = 0 M and assume that we got their tags T and T ′ under the same key/IV pair. Assume furthermore that these tag computations involve the same masking value W mask . This is always the case in Algorithm 2 and is true in 128-EIA3 v1.5 under some mild assumption on the length of M (namely that ℓ (mod 32) = 0). Thus we get

H z (M ′ ) ⊕ W mask = T ′ , H z (M ) ⊕ H z (M ′ ) = T ⊕ T ′ .
Let us now consider M ′′ = 0 2 M . We have

(H z (M ′ ) ⊕ H z (M ′′ )) ≫ 1 = (H z (0 M ) ⊕ H z (0 M ′ )) ≫ 1 = (H z (0 M ) ≫ 1) ⊕ (H z (0 M ′ ) ≫ 1) = (H z (M ) ≪ 1) ⊕ (H z (M ′ ) ≪ 1) = (H z (M ) ⊕ H z (M ′ ))) ≪ 1 = (T ⊕ T ′ ) ≪ 1.
By guessing a single bit, we thus get the value of H z (M ′ ) ⊕ H z (M ′′ ). Provided that the computation of the tag of M ′′ involves the same masking value W mask (i.e. ℓ (mod 32) = 31 in the case of 128-EIA3 v1.5), by adding H z (M ′ ) ⊕ H z (M ′′ ) to T ′ we get a tag value for M ′′ .

In other words, one can find a triplet (M, M ′ , M ′′ ) of pairwise distinct messages such that given the tags T and T ′ of the first two messages under the same IV, the tag T ′′ of the third one under the same IV can be guessed with a probability as large as 1/2. This results from the lack of 2-independence of the universal hash function H z used in 128-EIA3. While H z is uniformly distributed and 2 -32 -AXU -this implies the independence of the MACs of any two distinct messages under the same key and the same IV as shown in [START_REF]Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3[END_REF] -H z is far from being 2-universal, i.e. the hashes of two distinct messages can be strongly correlated and this results in the lack of independence of the MACs of three pairwise distinct messages illustrated here. 4

The IV construction in 128-EIA-3 and Prevention of Nonce Reuse

The input to the IV construction for 128-EIAx are [START_REF]3GPP Technical Specification Group Services and System Aspects: 3GPP System Architecture Evolution (SAE); Security architecture (Release 9)[END_REF]:

a 32-bit counter COUNT, -a 5-bit bearer identity BEARER, -a 1-bit direction of transmission DIRECTION.

This differs notably from the UMTS Integrity Algorithm (UIA) where the inputs for the IV construction are [START_REF]Specification of the 3GPP Confidentiality and Integrity Algorithms UEA2 & UIA2. Document 1: UEA2 and UIA2 Specification[END_REF]:

a 32-bit counter COUNT-I, -a 32-bit random value FRESH, -a 1-bit direction of transmission DIRECTION.

In the case of 128-EIA3, the IV is 128 bits and defined by 4 32-bit words, IV 0 IV 1 IV 2 IV 3 where:

IV 0 = COUNT IV 1 = BEARER 0 27 IV 2 = IV 0 ⊕ DIRECTION 0 31 IV 3 = IV 1 ⊕ 0 16 DIRECTION 0 15
We notice that while in UMTS two distinct values managed by the sending and receiving parties ensure the non-repetition of IVs, one single 32-bit counter is used for this purpose in LTE. Enforcing the use of fresh IVs by both the MAC issuer and the MAC verifier might therefore be more complex and we may express some concerns about the assurance that in LTE implementations the strong security requirement of (key, IV) pair never being reused at either side will always be verified.

The existential forgery attack presented in Section 4 was forwarded to the designers of 128-EIA3 v1.4, who produced the modified version 128-EIA3 v1.5 to address the issue. While our analysis of 128-EIA3 v1.5 did not reveal any security issue of similar significance and the new MAC offers a provable resistance (under some assumptions) against a large class of forgery attacks, we have highlighted some structural properties of the mask values computation and the universal family of hash functions underlying 128-EIA3 v1.5, and shown that these may lead to limitations of its resilience against nonce reuse. None of the security properties we have investigated here relates to the specific features of the underlying IV-dependent stream cipher ZUC.

Algorithm 2 A

 2 modified version of 128-EIA3 Input: IK ∈ {0, 1} k , IV ∈ {0, 1} n , ℓ ∈ N * Input: M = (m0, . . . , m ℓ-1 ) ∈ {0, 1} ℓ (z0, . . . , z ℓ+63 ) ← S(IK, IV )| 0 ℓ+63 Tag = 0 W mask ← (z0, . . . , z31)

We are thus using the same somewhat unusual convention as in[START_REF]SAGE: Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 & 128-EIA3[END_REF] for defining the symbols "≫" and "≪" as a "shift and truncate" rather than mere shifts. This is motivated by the fact that this convention is more convenient for presenting the attack of Section 4.

Whether this third message and the associated tag can be successfully submitted to the verifying entity depends on wheter the IV repetition detection of this entity is effective or not.

While another choice of Hz might have led to a much lower maximum success probability for a 3-message forgery, the existence of 4-message forgeries of success probability 1 seems difficult to avoid for any GF (2)-linear universal function family.

Acknowledgements

The authors would like to thank Steve Babbage for insightful comments on an early version of this paper.


Mohamed Ahmed Abdelraheem

Céline Blondeau

Maria Naya-Plasencia

Marion Videau

Erik Zenner

Maria Naya-Plasencia

María Naya-Plasencia

la diffusion de documents scientifiques

Keywords: ARMADILLO2, meet-in-the-middle, key recovery attack, preimage attack, parallel matching algorithm

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

ARMADILLO is a multi-purpose cryptographic primitive dedicated to hardware which was proposed by Badel et al. in [START_REF] Badel | ARMADILLO: A Multi-purpose Cryptographic Primitive Dedicated to Hardware[END_REF]. Two variants were presented: ARMADILLO and ARMADILLO2, the latter being the recommended version. In the following, the first variant will be denoted ARMADILLO1 to distinguish it from ARMADILLO2. Both variants comprise several versions, each one associated to a different set of parameters and to a different security level. For both primitives, several applications are proposed: fixed input-length MAC (FIL-MAC), pseudo-random number generator/pseudo-random function (PRNG/PRF), and hash function. In [START_REF] Sepehrdad | Fast Key Recovery Attack on ARMADILLO1 and Variants[END_REF], authors present a polynomial attack on ARMADILLO1. Even if the design of ARMADILLO2 is similar to the design of the first version, authors of [START_REF] Sepehrdad | Fast Key Recovery Attack on ARMADILLO1 and Variants[END_REF] claim that this attack can not be applied on ARMADILLO2.

The ARMADILLO family uses a parameterized internal permutation as a building block. This internal permutation is based on two bitwise permutations σ0 and σ1.

In [START_REF] Badel | ARMADILLO: A Multi-purpose Cryptographic Primitive Dedicated to Hardware[END_REF], these permutations are not specified, but some of the properties that they must satisfy are given.

In this paper we provide the first cryptanalysis of ARMADILLO2, the recommended variant. As the bitwise permutations σ0 and σ1 are not specified, we have performed our analysis under the reasonable assumption that they behave like random permutations. As a consequence, the results of this paper are independent of the choice for σ0 and σ1.

To perform our attack, we use a meet-in-the-middle approach and an evolved variant of the parallel matching algorithm introduced in [START_REF] Khovratovich | Cryptanalysis of Luffa v2 components[END_REF] and generalized in [START_REF] Naya-Plasencia | How to Improve Rebound Attacks[END_REF][START_REF] Naya-Plasencia | How to Improve Rebound Attacks[END_REF]. Our method enables us to invert the building block of ARMADILLO2 for a chosen value of the public part of the input, when a part of the output is known. We can use this step to build key recovery attacks faster than exhaustive search on all versions of ARMADILLO2 used in the FIL-MAC application mode. Besides, we propose several trade-offs for the time and memory needed for these attacks. We also adapt the attack to recover the key when ARMADILLO2 is used as a stream cipher in the PRNG application mode. We further show how to build (second) preimage attacks faster than exhaustive search when using the hashing mode, and propose again several time-memory trade-offs. We have implemented the attacks on a scaled version of ARMADILLO2, and the experimental results confirm the theoretical predictions.

Organization of the paper. We briefly describe ARMADILLO2 in Section 2. In Section 3 we detail our technique for inverting its building block and we explain how to extend the parallel matching algorithm to the case of ARMADILLO2. In Section 4, we explain how to apply this technique to build a key recovery attack on the FIL-MAC application mode. We briefly show how to adapt this attack to the stream cipher scenario in Section 4.2. The (second) preimage attack on the hashing mode is presented in Section 5. In Section 6 we present the experimental results of the verification that we have done on a scaled version of the algorithm. Finally, in Section 7, we propose a general form of the parallel matching algorithm derived from our attacks which can hopefully be used in more general contexts.

Description of ARMADILLO2

The core of ARMADILLO is based on the so-called data-dependent bit transpositions [START_REF] Moldovyan | A Cipher Based on Data-Dependent Permutations[END_REF]. We recall the description of ARMADILLO2 given in [START_REF] Badel | ARMADILLO: A Multi-purpose Cryptographic Primitive Dedicated to Hardware[END_REF] using the same notations.

Description

Let C be an initial vector of size c and U be a message block of size m. The size of the register (C U ) is k = c + m. The ARMADILLO2 function transforms the vector (C, U ) into (Vc, Vt) as described in Figure 1:

ARMADILLO2 : F c 2 × F m 2 → F c 2 × F m 2 (C, U ) → (Vc, Vt) = ARMADILLO2(C, U ).
The function ARMADILLO2 relies on an internal bitwise parameterized permutation denoted by Q which is defined by a parameter A of size a and is applied to a vector B of size k:

Q : F a 2 × F k 2 → F k 2 (A, B) → Q(A, B) = QA(B) C U QX (C U ) X QU (C U ) C U ✻ ✛ U ✻ ✻ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ Y ✻ ✛ ❡ ✻ Vc Vt Fig. 1. ARMADILLO2.
Let σ0 and σ1 be two fixed bitwise permutations of size k. In [START_REF] Badel | ARMADILLO: A Multi-purpose Cryptographic Primitive Dedicated to Hardware[END_REF], the permutations are not defined but some criteria they should fulfil are given. As the attacks presented in this paper are valid for any bitwise permutations, we do not describe these properties. We just stress that in the following, when computing the complexities we assume that these permutations behave like random ones. We denote by γ a constant of size k defined by alternating 0's and 1's: γ = 1010 • • • 10. Using these notations, we can define Q which is used twice in the ARMADILLO2 function. Let A be a parameter and B be the internal state, the parameterized permutation Q (that we denote by QA when indicating the parameter is necessary) consists in a = |A| simple steps. The i-th step of Q (reading A from its least significant bit to its most significant one) is defined by: -an elementary bitwise permutation: B ← σA i (B), that is:

• if the i-th bit of A equals 0 we apply σ0 to the current state,

• otherwise (if the i-th bit of A equals 1) we apply σ1 to the current state, -a constant addition (bitwise xor) of γ: B ← B ⊕ γ.

Using the definition of the permutation Q, we can describe the function ARMADILLO2. Let (C, U ) be the input, then ARMADILLO2(C, U ) is defined by:

-first compute X ← QU (C U ) -then compute Y ← QX (C U ) -finally compute (Vc Vt) ← Y ⊕ X, the output is (Vc, Vt).
Actually c and m can take different values depending on the required security level. A summary of the sets of parameters for the different versions (A, B, C, D or E) proposed in [START_REF] Badel | ARMADILLO: A Multi-purpose Cryptographic Primitive Dedicated to Hardware[END_REF] is given in

A Multi-Purpose Cryptographic Primitive

The general-purpose cryptographic function ARMADILLO2 can be used for three types of applications: FIL-MAC, hashing, and PRNG/PRF.

ARMADILLO2 in FIL-MAC mode. ARMADILLO2 in PRNG/PRF mode. The output sequence is obtained by taking the first t bits of (Vc, Vt) after at least r iterations. For ARMADILLO2 the proposed values are r = 1 and t = k (see [START_REF] Badel | ARMADILLO: A Multi-purpose Cryptographic Primitive Dedicated to Hardware[END_REF]Sec. 6]). When used as a stream cipher, the secret key is C. The keystream is composed of k-bit frames indexed by U which is a public value.

Inverting the ARMADILLO2 Function

In [START_REF] Badel | ARMADILLO: A Multi-purpose Cryptographic Primitive Dedicated to Hardware[END_REF] a sketch of a meet-in-the-middle (MITM) attack on ARMADILLO1, the first variant of the primitive, is given by the authors to prove lower bounds for the complexity and justify the choice of parameters. However, they do not develop further their analysis.

In this section we describe how to invert the ARMADILLO2 function when a part of the output (Vc, Vt) is known and U is chosen in the input (C U ). Inverting means that we recover C. The method we present can be performed for any arbitrary bitwise permutations σ0 and σ1. To conduct our analysis we suppose that they behave like random ones. Indeed, if the permutations σ0 and σ1 were not behaving like random ones, one could exploit their distributions to reduce the complexities of the attacks presented in this paper. Therefore, we are considering the worst case scenario for an attacker.

First, we describe the meet-in-the-middle technique we use. It provides two lists of partial states in the middle of the main permutation QX . To determine a list of possible values for C, we need to select a subset of the cartesian product of these two lists containing consistent couples of partial states. To build such a subset efficiently, we explain how to use an adaptation of the parallel matching algorithm presented in [START_REF] Khovratovich | Cryptanalysis of Luffa v2 components[END_REF][START_REF] Naya-Plasencia | How to Improve Rebound Attacks[END_REF]. Then we present and apply the adapted algorithm and compute its time and memory complexities. All cryptanalysis, we present, on the different applications of ARMADILLO2 relies on the technique for recovering C presented in this section.

The Meet-in-the-Middle Technique

Whatever mode ARMADILLO2 is embedded in, we use the following facts:

-We can choose the m-bit vector U , in the input vector (C U ).

-We know part of the output vector (Vc Vt): the m-bit vector Vt in the FIL-MAC, the (c + m)-bit vector (Vc Vt) in the PRNG/PRF and the c-bit vector Vc in the hash function.

We deal with two permutations: the pre-processing QU which is known as U is known and the main permutation QX which is unknown, and we exploit the three following equations:

-The permutation QU used in the pre-processing X = QU (C U ) is known. This implies that all the known bits in the input of the permutation can be traced to their corresponding positions in X. For instance, there are m coordinates of X whose values are determined by choosing U . -The output of the main permutation Y = (Vc Vt) ⊕ X implies we know some bits of Y . The amount of known bits of Y is denoted by y and is depending on the mode we are focusing on through (Vc Vt). -In the sequel, we divide X in two parts: X = (Xout Xin). Then, the main permutation Y = QX (C U ) can be divided in two parts: QX in and QX out separated by a division line we call the middle, hence we perform the meet-in-the-middle technique between QX in and Q -1 X out .

As (Xout Xin) = QU (C U ), we denote by min (resp. mout) the number of bits of U that are in Xin (resp. Xout). We have mout + min = m. We denote by ℓin (resp. ℓout) the number of bits coming from C in Xin (resp. Xout). We have ℓout + ℓin = c. The meet-in-the-middle attack is done by guessing the ℓin unknown bits of Xin and the ℓout unknown bits of Xout independently.

First, consider the forward direction. We can trace the ℓin unknown bits of Xin back to C with Q -1 U . Next, for each possible guess of Xin, we can trace the corresponding ℓin bits from C plus the m bits from U to their positions in the middle by computing QX in (C U ). Then consider the backward direction, we can trace the y known bits of Y back to the middle for each possible guess of Xout, that is computing Q -1 X out (Y ). This way we can obtain two lists Lin and Lout, of size 2 ℓ in and 2 ℓ out respectively, of elements that represent partially known states in the middle of QX .

To describe our meet-in-the-middle attack we represent the partial states in the middle of QX as ternary vectors with coordinate values from {0, 1, -}, where -denotes a coordinate (or cell) whose value is unknown. We say that a cell is active if it contains 0 or 1 and inactive otherwise. The weight of a vector V , denoted by wt(V ), is the number of its active cells. Two partial states are a match if their colliding active cells have the same values.

The list Lin contains elements

QX in (C U ) whose weight is x = ℓin + m. The list Lout contains elements Q -1
X out (Y ) whose weight is y. When taking one element from each list, the probability of finding a match will then depend on the number of collisions of active cells between these two elements.

Consider a vector A in {0, 1, -} k with weight a. We denote by P [k,a,b] (i) the probability over all the vectors B ∈ {0, 1, -} k with weight b of having i active cells at the same positions in A and B. This event corresponds to the situation where there are i active cells of B among the a active positions in A and the remaining (b -i) active

C U c = ℓ in + ℓout m = m in + mout QX (C U ) X QU (C U ) C U ✻ ✛ U ✻ ✻ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ ✛ Y ✻ ✛ ❡ ✻ Vc Vt c = ℓ in + ℓout m = m in + mout Merging point Q X in (C U ) Q -1 Xout (Y ) ✏ ❄ ✒ ✻ Xout X in           ℓout + mout ℓ in + m in
P [k,a,b] (i) = a i k-a b-i k b = b i k-b a-i k a
.

Taking into account the probability of having active cells at the same positions in a pair of elements from (Lin, Lout) and the probability that these active cells do have the same value, we can compute the expected probability of finding a match for a pair of elements, that we will denote 2 -N coll . We have:

2 -N coll = y i=0 2 -i P [k,x,y] (i).
This means that there will be a possible match with a probability of 2 -N coll . In total we will find 2 ℓ in +ℓ out -N coll pairs of elements that pass this test. Each pair of elements defines a whole C value. Next, we just have to check which of these values is the correct one.

The big question now is that of the cost of checking which elements of the two lists Lin and Lout pass the test. The ternary alphabet of the elements and the changing positions of the active cells make it impossible to apply the approach of traditional MITM attacks -having an ordered list Lin and checking for each element in the list Lout if a match exists with cost 1 per element. Even more, a priori, for each element in Lin we would have to try if it matches each of the elements from Lout independently, which would yield the complexity of exhaustive search.

For solving this problem we adapt the algorithm described in [5, Sec. 2.3] as parallel matching to the case of ARMADILLO2. A generalized version of the algorithm is exposed in Section 7 with detailed complexity calculations and the link to our application case.

ARMADILLO2 Matching Problem: Matching Non-Random Elements

Recently, new algorithms have been proposed in [START_REF] Naya-Plasencia | How to Improve Rebound Attacks[END_REF] to solve the problem of merging several lists of big sizes with respect to a given relation t that can be verified by tuples of elements. These new algorithms take advantage of the special structures that can be exhibited by t to reduce the complexity of solving this problem. As stated in [START_REF] Naya-Plasencia | How to Improve Rebound Attacks[END_REF], the problem of merging several lists can be reduced to the problem of merging two lists. Hereafter, we recall the reduced Problem 1 proposed in [START_REF] Naya-Plasencia | How to Improve Rebound Attacks[END_REF] that we are interested in.

Problem 1 ([5]). Let L1 and L2 be 2 lists of binary vectors of size 2 ℓ 1 and 2 ℓ 2 respectively. We denote by x a vector of L1 and by y a vector of L2. We assume that vectors x and y can be decomposed into z groups of s bits, i.e. x, y ∈ ({0, 1} s ) z and x = (x1, . . . , xz) (resp. y = (y1, . . . , yz)). The vectors in L1 and L2 are drawn uniformly and independently at random from {0, 1} sz .

Let t be a Boolean function, t : {0, 1} sz × {0, 1} sz → {0, 1} such that there exist some functions tj : {0, 1} s × {0, 1} s → {0, 1} which verify:

t(x, y) = 1 ⇐⇒ ∀j, 1 ≤ j ≤ z, tj(xj, yj) = 1.
Problem 1 consists in computing the set L sol of all 2-tuples (x, y) of (L1 ×L2) verifying t(x, y) = 1. This operation is called merging the lists L1 and L2 with respect to t.

One of the algorithms proposed in [START_REF] Naya-Plasencia | How to Improve Rebound Attacks[END_REF] to solve Problem 1 is the parallel matching algorithm, which is the one that provides the best time complexity when the number of possible associated elements to one element is bigger than the size of the other list, i.e., when we can associate by t more than |L2| elements to an element from L1 as well as more than |L1| elements to an element from L2.

In our case, the lists Lin and Lout correspond to the lists L1 and L2 to merge but the application of this algorithm differs in two aspects. The first one is the alphabet, which is not binary anymore but ternary. The second aspect is the distribution of vectors in the lists. In Problem 1, the elements are drawn uniformly and independently at random while in our case the distribution is ruled by the MITM technique we use. For instance, all the elements of Lin have the same weight x and all the elements of Lout have the same weight y, which is far from the uniform case.

The function t is the association rule we use to select suitable vectors from Lin and Lout. We say that two elements are associated if their colliding active cells have the same values. We can now specify a new Problem 1 adapted for ARMADILLO2: ARMADILLO2 Problem 1. Let Lin and Lout be 2 lists of ternary vectors of size 2 ℓ in and 2 ℓ out respectively. We denote by x a vector of Lin and by y a vector of Lout, with x, y ∈ {0, 1, -} k The lists Lin and Lout are obtained by the MITM technique described in Paragraph 3.1.

Let t : {0, 1, -} k × {0, 1, -} k → {0, 1} be the function defined by t = t1 • t2 • • • t k-1 • t k and: ∀j, 1 ≤ j ≤ k, tj : {0, 1, -} × {0, 1, -} → {0, 1}, xj 0 0 0 1 1 1 --- yj 0 1 -0 1 -0 1 - tj(xj, yj) 1 0 1 0 1 1 1 1 1
We say that x and y are associated if t(x, y) = 1. ARMADILLO2 Problem 1 consists in merging the lists Lin and Lout with respect to t.

We can now adapt the parallel matching algorithm to ARMADILLO2 Problem 1.

Applying the Parallel Matching Algorithm to ARMADILLO2

The principle of the parallel matching algorithm is to consider in parallel the possible matches for the α first cells and the next β cells in the lists Lin and Lout. The underlying idea is to improve, when possible, the complexity to find all the elements that are a match for the (α + β) first cells. To have a match between a vector in Lin and a vector in Lout, the vectors should satisfy:

the vector in Lin has u of its x active cells among the (α + β) first cells; -the vector in Lout has v of its y active cells among the (α + β) first cells; -looking at the (α + β) first cells, both vectors should have the same value at the same active position.

As x and y are the number of known bits from (C U ) and from Y resp. (see Fig. 2), the matching probability on the first (α + β) cells is:

2 -N α+β coll = x u=0 P [k,α+β,x] (u) • y v=0 P [k,α+β,y] (v) • v w=0 2 -w P [α+β,v,u] (w).
This means that we will find 2 c-N α+β coll partial solutions. For each pair passing the test we will have to check next if the remaining k -α -β cells are verified. : : : In a pre-processing phase, we first need to build three lists, namely LA, LB, L ′ B , which are represented in Fig. 3.

1...1 1...1 1...1 k+β α β α β α α β β β α L in L out L A L B L' B
List LA contains all the elements of the form (

x A 1 . . . x A α , y A 1 . . . y A α ) with (x A 1 . . . x A α ) ∈ {0, 1, -} α and (y A 1 . . . y A α ) being associated to (x A 1 . . . x A α ).
The size of LA is:

|LA| = α i=0 α i 2 i 3 α-i 2 i = 7 α .
List LB contains all the elements of the form (

x B 1 . . . x B β , y B 1 . . . y B β ) with (x B 1 . . .x B β ) ∈ {0, 1, -} β and (y B 1 , . . . , y B β ) being associated to (x B 1 , . . . , x B β ).
The size of LB is:

|LB| = β i=0 β i 2 i 3 β-i 2 i = 7 β . List L ′ B contains
|L ′ B | = β i=0 β i 2 i 3 β-i 2 i 2 ℓ in P [k,β,x] (i) 2 i β i = β i=0 3 β-i 2 i 2 ℓ in P [k,β,x] (i).
The cost of building L ′ B is upper bounded by (|L ′ B | + 3 β ), where 3 β captures the cases where no element in Lin corresponds to elements in LB and is normally negligible.

Next, we do the parallel matching. The probability for an element in Lout to have i active cells in its α first cells being

P [k,α,y] (i), for each element (x A 1 . . .x A α ,y A 1 . . .y A α ) in LA we consider the 2 ℓ out P [k,α,y] (i) 2 i ( α i )
elements y from Lout such that (y1, . . . , yα) = (y A 1 , . . . , y A α ). Then we check in L ′ B if elements indexed by (yα+1. . .y α+β , x A 1 . . .x A α ) exist. If this is the case, we check if each found pair of the form (x, y) verifies the remaining (k -α -β) cells. As we already noticed, we will find about 2 c-N α+β coll partial solutions for which we will have to check whether or not they meet the remaining conditions. The time complexity of this algorithm is:

O 2 c-N α+β coll + 7 α + 7 β + β i=0 3 β-i 2 i 2 ℓ in P [k,β,x] (i) + α i=0 3 α-i 2 i 2 ℓ out P [k,α,y] (i) .
The memory complexity is determined by 7 α + 7 β + |L ′ B |. We can notice that if

β i=0 3 β-i 2 i 2 ℓ in P [k,β,x] (i) > α i=0 3 α-i 2 i 2 ℓ out P [k,α,y] (i),
we can exchange the roles of Lin and Lout, so that the time complexity remains the same but the memory complexity will be reduced. The memory complexity is then:

O 7 α + 7 β + min β i=0 3 β-i 2 i 2 ℓ in P [k,β,x] (i), α i=0 3 α-i 2 i 2 ℓ out P [k,α,y] (i) .
4 Meet in the Middle Key Recovery attacks

Key Recovery Attack in the FIL-MAC Setting

In the FIL-MAC usage scenario, C is the secret key and U is the challenge. The response is the m-bit size vector Vt. In order to minimize the complexity of our attack, we want the number of known bits y from Y to be maximal. As Y = (Vc Vt) ⊕ X and X = QU (C U ) it means that we are interested in having the maximum number of bits from U among the m less significant bits of X.

As we have m bits of freedom in U for choosing the permutation QU , we need the probability of having i known bits (from U ) among the m first ones (of X), P [k,m,m] (i), to be bigger than 2 -m . Then to maximize the number of known bits in Y , we choose y as follows:

y = max 0≤i≤m i : P [k,m,m] (i) > 2 -m . (1)
For instance for ARMADILLO2-A, we have y = 38 with a probability of 2 -45.19 > 2 -48 . Then, from now on, we assume that we know y among the m bits of the lower part of X and y bits at the same positions of Y . Now, we can apply our meet-in-the-middle technique which allows us to recover the key. We have computed the optimal parameters for the different versions of ARMADILLO2, with different trade-offs -the generic attack has a complexity of 2 c . The results appear in Table 2.

For each version of ARMADILLO2 presented in Table 2, the first line corresponds to the (log 2 of the) size of the lists Lin and Lout with the smallest time complexity. The second line corresponds to the best parameters when limiting the memory complexity to 2 45 . In all cases, the complexity is determined by the parallel matching part of the attack. The data complexity of all the attacks is 1, that is, we only need one pair of plaintext/ciphertext to succeed.

Key Recovery Attack in the Stream Cipher Setting

As presented in [START_REF] Badel | ARMADILLO: A Multi-purpose Cryptographic Primitive Dedicated to Hardware[END_REF], ARMADILLO2 can be used as a PRNG by taking the t first bits of (Vc, Vt) after at least r iterations. For ARMADILLO2, the authors state in [START_REF] Badel | ARMADILLO: A Multi-purpose Cryptographic Primitive Dedicated to Hardware[END_REF]Sc. 6] that r = 1 and t = k is a suitable parameter choice. If we want to use it as a stream cipher, the secret key is C. The keystream is composed of k-bit frames indexed by U which is a public value.

In this setting, we can perform an attack which is similar to the one on the FIL-MAC, but with different parameters. As we know more bits of the output of QX , y = m + ℓout, complexities of the key recovery attack are lower.

In general, the best time complexity is obtained when ℓin = ℓout, as the number of known bits at each side is now x = m + ℓin in the input and y = m + ℓout in the output. In this context it also appears that the best time complexity occurs when α = β. There might be a small difference between α and β when the leading term of the time complexity is 2 c-N α+β coll . We present the best complexities we have computed for this attack in Table 3 -the generic attack has a complexity of 2 c . Other time-memory trade-offs would be possible. As in the previous section, we give as an example the best parameters when limiting the memory complexity to 2 45 .

(Second) Preimage Attack on the Hashing Applications

We recall that the hash function built with ARMADILLO2 as a compression function follows a strengthened Merkle-Damgård construction, where the padding includes the message length. In this case C represents the input chaining value, U the message block and Vc the generated new chaining value and the hash digest. In [START_REF] Badel | ARMADILLO: A Multi-purpose Cryptographic Primitive Dedicated to Hardware[END_REF] the authors state that (second) preimages are expected with a complexity of 2 c , the one of the generic attack. We show, in this section, how to build (second) preimage attacks with a smaller complexity.

Meet-in-the-Middle (Second) Preimage Attack

The principle of the attack is represented in Fig. 5.1. We first consider that the ARMADILLO2 function is invertible with a complexity of 2 q , given an output Vc and a message block. In the preimage attack, we choose and fix ℓ, the number of blocks of the preimage. In the second preimage attack, we can consider the length of the given message. Then, given a hash value h:

In the backward direction:

-We invert the insertion of the last block M pad (padding). This step costs 2 q in a preimage scenario and 1 in a second preimage one. We get

ARMADILLO2 -1 (h, M pad ) = S ′ .
-From state S ′ , we can invert the compression function for 2 b different message blocks M b with a cost 2 b+q , obtaining 2 b different intermediate states: ARMADILLO2 -1 (S ′ , M b ) = S ′′ . In the forward direction: From the initial chaining value, we insert 2 a messages of length (ℓ -2) blocks, M = M1 M2 . . . M ℓ-2 , obtaining 2 a intermediate states S. This can be done with a complexity of O((ℓ -2)2 a ). If we find a collision between one of the 2 a states S and one of the 2 b states S ′′ , we have obtained a (second) preimage that is M M b M pad .

A collision occurs if a + b ≥ c. The complexity of this attack is 2 a + 2 q + 2 b+q in time, where the middle term appears only in the case of a preimage attack and is negligible. The memory complexity is about 2 b (plus the memory needed for inverting the compression function). So if 2 q < 2 c , we can find a and b so that 2 a + 2 b+q < 2 c .

Inverting the Compression Function

In the previous section we showed that inverting the compression function for a chosen message block and for a given output can be done with a cost of 2 q < 2 c . In this section we show how this complexity depends on the chosen message block, as the inversion

❅ ❅ ❅ A R M A D IL L O 2 ❅ ❅ ❅ A R M A D IL L O 2 ❅ ❅ ❅ A R M A D IL L O 2 ❅ ❅ ❅ A R M A D IL L O 2 ❅ ❅ ❅ A R M A D IL L O 2 IV0 M1 M2 Mℓ-2 Mb Mpad S S ′′ S ′ c c m m c h Collision with probability 2 a 2 b 2 c ❅ ✒ ❅ ■ ❅ ■
1 second preimage 2 q preimage 2 b+q 2 a Fig. 4. Representation of the meet-in-the-middle (second) preimage attack. can be seen as a key recovery similar to the one done in Section 4. In this case we know U (the message block) and Vc, and we want to find C. When inverting the function with the blocks M b , we choose message blocks (U ) that define permutations QU which put most of the m bits from U among the c most significant bits of X. This will result in better attacks, as the bits in Y known from U do not cost anything and this gives us more freedom when choosing the parameters ℓin and ℓout.

As before, we have 2 m possibilities for QU . We denote by n the number of bits of U in the c most significant bits of X. The number of message blocks (U ) verifying this condition is:

N block (n) = 2 m P [k,c,m] (n).
In fact we are interested in the values of n which are the greatest possible (to lower the complexity) that still leaves enough message blocks to invert in order to obtain S ′′ . It means that these values belong to a set {ni} such that:

{n i } N block (ni) ≥ 2 b .
As the output is Vc, the ℓout bits guessed from X are also known bits from the output of QX . The number of known bits of the output of QX is then defined by: y = min(c, ℓout + n)

Compared to the key recovery attack, the number of known bits at the end of the permutation QX is significantly bigger, as we may know up to c bits, while in the previous case the maximal number for y was y = maxi i : P [k,m,m] (i) > 2 -m . To simplify the explanations, we concentrate on the case of ARMADILLO2-A, that can be directly adapted to any of the other versions. For n = 48 we have a probability P [128,80,48] = 2 -44.171 . This leaves 2 48-44.171 = 2 3.829 message blocks to invert which allow us to know y = min(80, ℓout + 48) bits from the output of QX . As we need to invert 2 b message blocks, if b is bigger than 3.829, we have to consider next the message blocks with n = 47, that allow us to know y = min(80, ℓout + 47) bits, and so on. For each n considered, the best time complexity (2 qn ) for inverting ARMADILLO2 might be different, but in practice, with at most two consecutive values of n we have enough message blocks for building the attack, and the complexity of inverting the compression function for these two different types of messages is very similar. For instance, in ARMADILLO2-A, we consider n = 48, 47, associated each to 2 3.829 and 2 9.96 possible message blocks respectively. The best time complexity for inverting the compression function in both cases is 2 q 48 = 2 q 47 = 2 65.9 , as we can see from Table 4. If we want to find the best parameters for a and b in the preimage attack, we can consider that a+b = c and 2 b = 2 b 48 +2 b 47 , and we want that 2 a = 2 b 48 2 65.9 +2 b 47 2 65.9 = 2 65.9 (2 b 48 + 2 b 47 ), as the complexity of the attack is O(2 a + 2 65.9 (2 b 48 + 2 b 47 )). So if we choose the parameters correctly, the best time complexity will be O(2 a+1 ). In this particular case the time complexity for n = 48 and for n = 47 is the same, so finding the best b and a can be simplified by b = c-q 2 and a = c -b. We obtain b = 7.275, a = 72.95. We see that we do not have enough elements with n = 48 for inverting 2 b blocks, but we have enough with n = 47 alone. As the complexities are the same in both cases, we can just consider b = b47. The best time complexity for the preimage attack that we can obtain is then 2 73.95 , with a memory complexity of 2 63.08 . Other trade-offs are possible by using other parameters for inverting the function, as shown in Table 5.

For the other versions of ARMADILLO2, the number of message blocks associated to y = m is big enough for performing the 2 b inversions, so we do not consider other n's for computing the (second) preimage complexity. Then, b = bm = c-q {n=m} 2 and a = c -bm.

Complexities for preimage attacks on the different versions of ARMADILLO2 are given in Table 5

Experimental Verifications

To verify the above theoretical results, we implemented the proposed key recovery attacks in the FIL-MAC and stream cipher settings against a scaled version of AR-MADILLO2 that uses a 30-bit key and processes 18-bit messages, i.e. c = 30 and m = 18. We performed the attack 10 times for both the FIL-MAC and the PRNG settings where at each time we chose random permutations for both σ0 and σ1 and random messages U (in the FIL-MAC case U was chosen so that we got y bits from U among the m least significant bits of X).

As for each application the key is a 30-bit key, the generic attack requires a time complexity of 2 30 . Using the parallel matching algorithm we decrease this complexity. Table 6 shows that the implementation results are very close to the theoretical estimates, confirming our analysis. We can also mention that we exchanged the role of Lin and Lout in our implementation of the attacks to minimize the memory needs.

Generalization of the Parallel Matching Algorithm

In Section 3, we managed to apply the parallel matching algorithm to invert the ARMADILLO2 function by modifying the merging Problem 1 of [START_REF] Naya-Plasencia | How to Improve Rebound Attacks[END_REF].

When the number of possible associated elements to one element is bigger than the other list as it is the case for ARMADILLO2, we cannot apply a basic algorithm like the instant matching algorithm proposed in [START_REF] Naya-Plasencia | How to Improve Rebound Attacks[END_REF]. Instead, we can use either the gradual matching or the parallel matching algorithms also proposed in [START_REF] Naya-Plasencia | How to Improve Rebound Attacks[END_REF]. We are going to concentrate on the parallel matching algorithm which allows a significant reduction of the time complexity of solving Problem 1, while allowing several time-memory tradeoffs. We can state the generalized problem that also covers our attack on ARMADILLO2 and give the corresponding parallel matching algorithm. We believe that this more general problem will be useful for recognizing situations where the parallel matching can be applied, and solving them in an automatized way.

The cost of building this list is upper-bounded by (|L ′ B |+(|A|) β ), where the second term captures the cases where no element in L1 corresponds to elements in LB and should be negligible. In the case where Next, we do the parallel matching. For each element (x A 1 , . . . , x A α , y A 1 , . . . , y A α ) in LA we consider the 2 ℓ 2 P (y A 1 ,...,y A α ), [1,α],L 2 elements y from L2 such that (y1. . .yα) = (y A 1 , . . . , y A α ) and we check in L ′ B if elements indexed by (yα+1. . .y α+β , x A 1 . . .x A α ) exist. If this is the case, we check if each found pair of the form (x, y) verifies the remaining (k -α -β) cells. We denote by Ω the number of partial solutions for which we will have to check whether or not they meet the remaining conditions:

Ω = 2 ℓ 1 +ℓ 2 b∈(A s ) α+β

Link with Formulas in the Case of ARMADILLO

Using the previous formulas for the time and memory complexities, we can rediscover formulas of the time and memory complexities we have computed for ARMADILLO2 (see. Section 3.3). As these formulas depend essentially on the size of the different lists, we simply expose how to find the size of the list |LA| using equation [START_REF] Khovratovich | Cryptanalysis of Luffa v2 components[END_REF].

For ARMADILLO2, the probabilities pj,a are independent of the position j and pj,a = 2/3 if and only if a is an active cell. Moreover, in this case, each cell is composed of one letter of the alphabet which means that s = 1. And we have: The same method can be applied to find the size of the list LB and L ′ B . Here we have Ω = 2 c-N α+β coll .

In this paper, we have presented the first cryptanalysis of ARMADILLO2, the recommended variant of the ARMADILLO family. We propose a key recovery attack on all its versions for the FIL-MAC and the stream cipher mode, which works for any bitwise permutations σ0 and σ1. We give several time-memory trade-offs for its complexity. We also show how to build (second) preimage attacks when using the hashing mode.

Besides the results on ARMADILLO2, we have generalized the parallel matching algorithm presented in [START_REF] Naya-Plasencia | How to Improve Rebound Attacks[END_REF] for solving a wider Problem 1 which includes the cases where the lists to merge do not have random elements. We believe that new types of meet-in-the-middle attacks might appear now given this algorithm that is cheaper than exhaustive search.

Fig. 2 .

 2 Fig. 2. Overview of the inversion of the ARMADILLO2 core function. cells of B lie in the (k -a) inactive positions in A. As the number of vectors of length k and weight b is k b , we have:

x 1 . 1 .-Fig. 3 .

 113 Fig. 3. Lists used in the parallel matching algorithm.

  a∈(A s ) α α j=1 |A| s pj,a j 2 ℓ 2 P a,[β+1,α+β],L 2 < b∈(A s ) β β j=1 |A| s p j,b j 2 ℓ 1 P b,[α+1,α+β],L 1we can swap L1 and L2, to reduce the memory complexity of the attack.

2 

 2 α+β j=1 p j,b j P b,[1,α+β],L 1The time complexity of this algorithm is:O   Ω + |LA| + |LB| + |L ′ B | + a∈(A s ) α α j=1 |A| s pj,a j 2 ℓ 2 P a,[β+1,α+β],LThe memory complexity is determined by the size of the lists LA, LB and L ′ B . Therefore the memory complexity is:a∈(A s ) α α j=1 |A| s pj,a j + b∈(A s ) β β j=1 |A| s p j,b j + b∈(A s ) β β j=1|A| s p j,b j 2 ℓ 1 P b,[α+1,α+β],L 1

Table

Table 1 .

 1 . Sets of parameters for the different versions of ARMADILLO2.

	Version	k	c	m
	A	128 80 48
	B	192 128 64
	C	240 160 80
	D	288 192 96
	E	384 256 128

  Lin to have i active cells in its next β cells is P [k,β,x] (i). The size of L ′ B is:

	for an element in
	for each element (x B 1 , . . . , x B β , y B 1 , . . . , y B β ) in LB all the elements x from Lin such that (xα+1 . . . , x α+β ) = (x B 1 , . . . , x B β ). Elements in L ′ B are of the form (y B 1 , . . . , y B β , x1, . . . , x k ) indexed 7 by (y B 1 . . . , y B β , x1, . . . , xα). The probability

Table 2 .

 2 Complexities of the meet-in-the-middle key recovery attack on the FIL-MAC application

	Version	c m ℓout ℓin α β log 2 (Time compl.) log 2 (Mem. compl.)
	ARMADILLO2-A 80 48	34 46 24 20 18 62 16 9	72.54 75.05	68.94 45
	ARMADILLO2-B 128 64	58 70 35 35 38 90 2	117.97 125.15	108.87 45
	ARMADILLO2-C 160 80	76 84 43 43 35 125 4 16	148.00 156.63	135.90 45
	ARMADILLO2-D 192 96	92 100 50 50 29 163 11 12	177.98 187.86	160.44 45
	ARMADILLO2-E 256 128	125 131 65 65 29 227 11 13	237.91 251.55	209.83 45

Table 3 .

 3 Version c m ℓout ℓin α β log 2 (Time compl.) log 2 (Mem. compl.) Complexities of the meet-in-the-middle key recovery attack for the stream cipher with various trade-offs.

	ARMADILLO2-A 80 48	40 40 19 19 27 53 11 16	65.23 71.62	62.91 45
	ARMADILLO2-B 128 64	64 64 31 32 29 99 9 16	104.71 119.69	101.75 45
	ARMADILLO2-C 160 80	80 80 39 40 26 134 14 14	130.53 151.29	127.49 45
	ARMADILLO2-D 192 96	96 96 47 48 30 162 8 16	156.35 184.37	153.23 45
	ARMADILLO2-E 256 128	128 128 64 64 30 226 8 16	207.96 248.66	205.93 45

Table 4 .

 4 Complexities for inverting the compression function.

	Version	c m ℓout ℓin n	log 2 ( N block (n))	α β	log 2 (Time compl.)	log 2 (Mem. compl.)
			35 45 47	9.95	22 16	65.90	63.08
			35 45 48	3.83	22 16	65.90	63.08
	ARMADILLO2-A 80 48	20 60 47	9.95	16 8	71.36	45
			27 53 48	3.83	11 16	71.62	45
	ARMADILLO2-B 128 64	62 66 64 33 95 64	15.89 15.89	33 30 104.67 6 16 120.41	102.35 45
	ARMADILLO2-C 160 80	78 82 80 26 134 80	19.82 19.82	41 38 130.48 11 16 152.24	128.08 45
	ARMADILLO2-D 192 96	94 98 96 30 162 96	23.74 23.74	49 46 156.31 8 16 184.37	153.82 45
	ARMADILLO2-E 256 128	126 130 128 34 222 128	31.58 31.58	65 62 207.96 5 16 249.47	205.30 45

Table 5 .

 5 , where we can see two different complexities with different trade-offs for each version. Complexities of the (second) preimages attacks.

				Best time	Time-memory trade-off
	Version	c	m	log 2 (Time compl.)	log 2 (Mem. compl.)	log 2 (Time compl.)	log 2 (Mem. compl.)
	ARMADILLO2-A 80 48	73.95	63.08	76.81	45
	ARMADILLO2-B 128 64	117.34	102.35	125.21	45
	ARMADILLO2-C 160 80	146.24	128.08	157.12	45
	ARMADILLO2-D 192 96	175.16	153.82	191.19	45
	ARMADILLO2-E 256 128	232.98	205.30	253.74	45

Table 6 .

 6 Key recovery attacks against a scaled version of ARMADILLO2 in the FIL-MAC and PRNG modes.

		c m ℓout ℓin α β y log 2 (|L ′ B |)	log 2 (c-N α+β coll )	log 2 (Time compl.)	log 2 (Mem. compl.)
	FIL-MAC	Impl. 30 18 12 18 8 6 14 23.477 Theory 30 18 12 18 8 6 14 23.475	27.537 27.538	27.874 27.874	24.066 24.064
	PRNG	Impl. 30 18 14 16 7 6 32 22.530 Theory 30 18 14 16 7 6 32 22.530	24.728 24.735	25.396 25.401	22.738 22.738

We can use standard hash tables for storage and look up in constant time.

We can use standard hash tables for storage and look up in constant time.

* This work was partially supported by the European Commission through the ICT programme under contract ICT-2007-216676 ECRYPT II † Supported by the National Competence Center in Research on Mobile Information and Communication Systems (NCCR-MICS), a center of the Swiss National Science Foundation under grant number 5005-67322 and by the French Agence Nationale de la Recherche through the SAPHIR2 project under Contract ANR-08-VERS-014 ‡ Partially supported by the French Agence Nationale de la Recherche under Contract ANR-06-SETI-013-RAPIDE § This work was produced while at the Technical University of Denmark

The Generalized Problem 1

As stated in [START_REF] Naya-Plasencia | How to Improve Rebound Attacks[END_REF], Problem 1 for N lists can be reduced to 2 lists, therefore we will only consider the problem of merging 2 lists in the sequel.

Generalized Problem 1. We are given 2 lists, L1 and L2 of size 2 ℓ 1 and 2 ℓ 2 respectively. We denote by x a vector of L1 and by y a vector of L2. Coordinates of x and y belong to a general alphabet A.

We assume that vectors x and y can be decomposed into z groups of s coordinates, i.e. x, y ∈ (A s ) z and x = (x1, . . . , xz) (resp. y = (y1, . . . , yz)).

We want to keep pairs of vectors verifying a given relation t: t(x, y) = 1. The relation t is group-wise,and is defined by t : (A s ) z × (A s ) z → {0, 1} such that there exist some functions tj : A s × A s → {0, 1}, verifying:

Generalized Problem 1 consists in merging these 2 lists to obtain the set L sol of all 2-tuples of (L1 × L2) verifying t(x, y) = 1. We say that x and y are associated in this case.

In order to analyze the time and memory complexities of the attack we need to compute the size of L sol . This quantity depends on the probability that t(x, y) = 1. More precisely the complexities of the generalized parallel matching algorithm depends on the conditional probabilities: Pry j [tj(xj, yj) = 1|xj = a], a ∈ A s . We will denote these probabilities by pj,a, a ∈ A s .

In [START_REF] Naya-Plasencia | How to Improve Rebound Attacks[END_REF] the elements of the lists L1 and L2 were binary (i.e. A = {0, 1}) and random, and the probability of each tj of being verified did not depend on the elements xj or yj. Let us consider as an example the case where s = 1 and tj tests the equality of xj and yj. We have: ∀j, 1 ≤ j ≤ z, pj,0 = pj,1 = 1 2 .

In the case of the ARMADILLO2 cryptanalysis that we present in this paper, the alphabet is ternary (i.e. A = {0, 1, -}) and the association rule (see. ARMADILLO2 Problem 1 ) gives:

and pj,-= 1

Generalized Parallel Matching Algorithm

First we need to build the three following lists:

List LA, of all the elements of the form (x A 1 , . . . , x A α , y A 1 , . . . , y A α ) with (x A 1 , . . . , x A α ) ∈ (A s ) α and (y A 1 , . . . , y A α ) being associated by t to (x A 1 , . . . , x A α ). The size of LA is:

where aj is the j-th coordinate of a ∈ (A s ) α . List LB, of all the elements of the form (x If we denote by P b,[α+1,α+β],L 1 the probability of having an element x from L1 such that (xα+1, . . . , x α+β ) = b, the size of L ′ B is:

|A| s p j,b j 2 ℓ 1 P b,[α+1,α+β],L 1 .