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

Mridul Nandi
email: mridul.nandi@gmail.com

Ferdinand Sibleyras
email: ferdinand.sibleyras@inria.fr

Generic Attacks against Beyond-Birthday-Bound MACs

Keywords: Modes of operation, Cryptanalysis, Message Authentication Codes, Beyond-Birthday-Bound security

In this work, we study the security of several recent MAC constructions with provable security beyond the birthday bound. We consider block-cipher based constructions with a double-block internal state, such as SUM-ECBC, PMAC+, 3kf9, GCM-SIV2, and some variants (LightMAC+, 1kPMAC+). All these MACs have a security proof up to 2 2n/3 queries, but there are no known attacks with less than 2 n queries. We describe a new cryptanalysis technique for double-block MACs based on finding quadruples of messages with four pairwise collisions in halves of the state. We show how to detect such quadruples in SUM-ECBC, PMAC+, 3kf9, GCM-SIV2 and their variants with O(2 3n/4 ) queries, and how to build a forgery attack with the same query complexity. The time complexity of these attacks is above 2 n , but it shows that the schemes do not reach full security in the information theoretic model. Surprisingly, our attack on LightMAC+ also invalidates a recent security proof by Naito. Moreover, we give a variant of the attack against SUM-ECBC and GCM-SIV2 with time and data complexity Õ(2 6n/7 ). As far as we know, this is the first attack with complexity below 2 n against a deterministic beyondbirthday-bound secure MAC. As a side result, we also give a birthday attack against 1kf9, a single-key variant of 3kf9 that was withdrawn due to issues with the proof.

Introduction

Message authentication codes (or MACs) ensure the authenticity of messages in the secret-key setting. They are a core element of real-world security protocols such as TLS, SSH, or IPSEC. A MAC takes a message (and optionally a nonce) and a secret key to generate a tag that is sent with the message. Traditionally, they are classified into three types: deterministic, nonce-based, and probabilistic.

Deterministic MAC designs are the most popular, with widely used constructions based on block-cipher (CBC-MAC [START_REF]Computer data authentication[END_REF][START_REF] Bellare | The security of the cipher block chaining message authentication code[END_REF], OMAC [START_REF] Iwata | OMAC: One-key CBC MAC[END_REF], PMAC [START_REF] Black | A block-cipher mode of operation for parallelizable message authentication[END_REF], LightMAC [START_REF] Luykx | A MAC mode for lightweight block ciphers[END_REF], . . . ) and hash functions (HMAC [START_REF] Bellare | Keying hash functions for message authentication[END_REF], NMAC [START_REF] Bellare | Keying hash functions for message authentication[END_REF], NI-MAC [START_REF] An | Constructing VIL-MACs from FIL-MACs: Message authentication under weakened assumptions[END_REF], . . . ). However, there is a generic forgery attack against all deterministic iterated MACs, using collisions in the internal state, due to Preneel and van Oorschot [START_REF] Preneel | MDx-MAC and building fast MACs from hash functions[END_REF]. Therefore, these MACs only achieve security up to the birthday bound, i.e. when the number of queries by the adversary is bounded by 2 n/2 , with n the state size. This is equivalently called n/2-bit security.

One way to increase the security is to use a nonce, a unique value provided by the user (in practice, the nonce is usually a counter). This approach has been pioneered by Wegman and Carter [41] based on an earlier work by Gilbert et al. [START_REF] Gilbert | Codes which detect deception[END_REF]. Later a few follow ups like EDM and EWCDM [START_REF] Cogliati | EWCDM: An efficient, beyond-birthday secure, noncemisuse resistant MAC[END_REF], and Dual EDM [START_REF] Mennink | Encrypted davies-meyer and its dual: Towards optimal security using mirror theory[END_REF] have been proposed to achieve beyond birthday security.

Alternatively, a probabilistic MAC uses a random coin for the extra value, which is usually called a salt, and must be transmitted with the MAC. Probabilistic MACs have the advantage that they can stay secure when called with the same input twice, and don't require a state to keep the nonce unique. Some popular probabilistic MAC constructions are XMACR [START_REF] Bellare | XOR MACs: New methods for message authentication using finite pseudorandom functions[END_REF], RMAC [START_REF] Jaulmes | On the security of randomized CBC-MAC beyond the birthday paradox limit: A new construction[END_REF] and EHtM [START_REF] Minematsu | How to thwart birthday attacks against MACs via small randomness[END_REF]. In particular, RMAC and EHtM have security beyond the birthday bound.

However, deterministic MACs are easier to use in practice, and there has been an important research effort to build deterministic MAC with security beyond the birthday bound, using an internal state larger than the primitive size. In particular, several constructions use a 2n-bit internal state so that collisions in the state are only expected after 2 n queries. Yasuda first proposed SUM-ECBC [START_REF] Yasuda | The sum of CBC MACs is a secure PRF[END_REF], a beyond birthday bound (BBB) secure deterministic MAC that achieves 2n/3bit security. However, this construction has rate 1/2 and later Yasuda himself proposed one of the most popular BBB secure MAC PMAC+ [START_REF] Yasuda | A new variant of PMAC: Beyond the birthday bound[END_REF] achieving rate 1. Later several other constructions like 3kf9 [START_REF] Zhang | 3kf9: Enhancing 3GPP-MAC beyond the birthday bound[END_REF], LightMAC+ [START_REF] Naito | Blockcipher-based MACs: Beyond the birthday bound without message length[END_REF], GCM-SIV2 [START_REF] Iwata | Stronger security variants of GCM-SIV[END_REF], and single key PMAC+ [START_REF] Datta | Single key variant of PMAC_Plus[END_REF] have been proposed. Interestingly, all the above designs share a common structure: a double-block universal hash function outputs a 2nbit hash value (seen as two n-bit halves), and a finalization function generates the tag by XORing encrypted values of the two n-bit hash values. This structure has been called double-block-hash-then-sum, and it will be the focus of our paper.

More recently, variants of PMAC+ based on tweakable block-cipher have also been proposed, such as PMAC_TBC [START_REF] Naito | Full PRF-secure message authentication code based on tweakable block cipher[END_REF], PMACx [START_REF] List | Revisiting full-PRF-secure PMAC and using it for beyondbirthday authenticated encryption[END_REF], ZMAC [START_REF] Iwata | ZMAC: A fast tweakable block cipher mode for highly secure message authentication[END_REF], and ZMAC+ [START_REF] List | ZMAC + -an efficient variable-output-length variant of ZMAC[END_REF].

Our results. We focus on the security of deterministic block-cipher based MACs with security beyond the birthday bound and double-block hash construction. Several previous works have been focused on security proofs, showing that they are secure up to 2 2n/3 queries [START_REF] Yasuda | A new variant of PMAC: Beyond the birthday bound[END_REF][START_REF] Zhang | 3kf9: Enhancing 3GPP-MAC beyond the birthday bound[END_REF][START_REF] Iwata | Stronger security variants of GCM-SIV[END_REF][START_REF] Datta | Single key variant of PMAC_Plus[END_REF][START_REF] Yasuda | The sum of CBC MACs is a secure PRF[END_REF][START_REF] Naito | Blockcipher-based MACs: Beyond the birthday bound without message length[END_REF]. For most of these constructions, the advantage of an adversary making q short queries is bounded by O(q 3 /2 2n ). Recently, Naito [START_REF] Naito | Improved security bound of LightMAC_Plus and its single-key variant[END_REF] gave an improved security proof for LighMAC+, with advantage at most O(q 2 t q v /2 2n ), with q t MAC queries and q v verification queries. In particular, this would prove security up to 2 n when the adversary can only do a single verification query.

In this work, we take the opposite approach and look for generic attacks against these modes. We use a cryptanalysis technique that can be seen as a generalisation of the collision attack of Preneel and van Oorschot [START_REF] Preneel | MDx-MAC and building fast MACs from hash functions[END_REF]. Instead of looking for a pair of messages so that the full state collides, we look for a quadruple of messages, which can be seen either as two pairs colliding on the first Table 1. Summary of the security for studied modes and our main results. q is the number of queries, is maximum size of a query, σ is total number of processed blocks. The expected lower bound and attack complexity is in number of constant length queries ( = O(1)). We use "U" for universal forgeries, and "E" for existential forgeries.

Mode

Provable security bounds Attacks (this work)

Advantage

Queries Queries Time Type

SUM-ECBC [42] O( q 3 3 2 2n ) Ω(2 2n/3 ) O(2 3n/4 ) Õ(2 3n/2 ) U O(2 6n/7 ) Õ(2 6n/7 ) U GCM-SIV2 [20] O( q 3 2 2 2n ) Ω(2 2n/3 ) O(2 3n/4 ) Õ(2 3n/2 ) U O(2 6n/7 ) Õ(2 6n/7 ) U PMAC+ [43] O( q 3 3 2 2n ) Ω(2 2n/3 ) O(2 3n/4 ) Õ(2 3n/2 ) E LightMAC+ [33] O( q 3 2 2n ) Ω(2 2n/3 ) O(2 3n/4 ) Õ(2 3n/2 ) E 1kPMAC+ [9] O( σ 2 n + qσ 2 2 2n ) Ω(2 2n/3 ) O(2 3n/4 ) Õ(2 3n/2 ) E 3kf9 [44] O( q 3 3 2 2n + q 2 n ) Ω(2 2n/3 ) O( 4 √ n • 2 3n/4 ) Õ(2 5n/4 ) U 1kf9 [8] O( q 2 2 n + q 3 4 2 2n + q 4 4 2 3n + q 4 6 2 4n ) Ω(2 2n/3 ) O(2 n/2 ) Õ(2 n/2 ) U
half of the state, or two pairs colliding on the second half. Since the finalization function combines the halves with a sum, we can detect such a quadruple because the corresponding MACs sum to zero, and can usually amplify this filtering. Moreover, when the message are well constructed, the relations defining the four collisions create a linear system of rank only three, so that we expect one good quadruple out of 2 3n . Therefore, we only need four lists of 2 3n/4 queries, and we expect one good quadruple out of the 2 3n choices in the four lists.

Table 1 shows a summary of our main results and how they compare with their respective provable security claims. In particular, we have forgeries attacks with O(2 3n/4 ) MAC queries against SUM-ECBC, GCM-SIV2, PMAC+, LightMAC+, 1kPMAC+, and 3kf9. As far as we know, these are the first attacks with less than 2 n queries against these constructions. Our attack against LighMAC+ contradicts the recent security bound for LighMAC+ [START_REF] Naito | Improved security bound of LightMAC_Plus and its single-key variant[END_REF], because we have an attack with O(2 3n/4 ) MAC queries, and a single verification query. The other attacks do not contradict the security proofs, but they make an important step towards understanding the actually security of these modes: we now have a lower bound of 2 2n/3 queries from the proofs, and an upper bound of 2 3n/4 from our attacks.

The attacks have a complexity of 2 3n/4 in the information theoretic model (the model used for most MAC security proofs), but we note that an attacker needs more than 2 n operations to create a forgery. However, we have found a variant of our attack against SUM-ECBC and GCM-SIV2 with total complexity below 2 n , using O(2 6n/7 ) queries and Õ(2 6n/7 ) operations.

We have also found an attack with only O(2 n/2 ) queries and Õ(2 n/2 ) operations against 1kf9 [START_REF] Datta | Building single-key beyond birthday bound message authentication code[END_REF], a single key variant of 3kf9 with claimed security up to 2 2n/3 queries. 1kf9 has been withdrawn due to issues with its security proof, but no attack was known previously.

Related works.

There has been extensive work on security proofs for modes of operations, with a recent focus on security beyond the birthday bound. An interesting example is the encryption mode CENC by Iwata [START_REF] Iwata | New blockcipher modes of operation with beyond the birthday bound security[END_REF]: the initial proof was only up to 2 2n/3 queries, but a later proof showed that it actually remains secure close to 2 n queries [START_REF] Iwata | CENC is optimally secure[END_REF]. Our results show that in the case of double-blockhash-then-sum MACs, the security is lower than n-bit security.

Similarly, the initial proof of the randomized MAC EHtM only gave security up to 2 2n/3 , but a later proof showed security up to 2 3n/4 [START_REF] Dutta | Tight security analysis of EHtM MAC[END_REF]. This result also includes a matching attack, using a technique similar to ours based on looking for quadruples. However in the case of EHtM the attacker can observe part of the state, which allows him to find a right quadruple in O(2 3n/4 ) time and memory. In our case we can't observe the internal state at all, thus we need to use different tricks tailored to each construction in order to amplify the filtering and avoid the many false-positives. In particular, this significantly increases the time and memory complexity.

There has also been intensive work on generic attacks to complement the security proof results. After the generic collision attack of Preneel and van Oorschot [START_REF] Preneel | MDx-MAC and building fast MACs from hash functions[END_REF], more advanced attacks against MACs have been described, with stronger outcomes than existential forgeries, starting with a key-recovery attack against the envelop MAC by the same authors [START_REF] Preneel | On the security of two MAC algorithms[END_REF]. In particular, a series of attacks against hash-based MACs [START_REF] Leurent | New generic attacks against hash-based MACs[END_REF][START_REF] Peyrin | Generic universal forgery attack on iterative hash-based MACs[END_REF][START_REF] Guo | Updates on generic attacks against HMAC and NMAC[END_REF][START_REF] Dinur | Improved generic attacks against hash-based MACs and HAIFA[END_REF] led to universal forgery attacks against long challenges, and key-recovery attacks when the hash function has an internal checksum (like the GOST family). Against PMAC, Lee et al. showed a universal forgery attack in 2006 [START_REF] Lee | Forgery and key recovery attacks on PMAC and mitchell's TMAC variant[END_REF]. Later, Fuhr, Leurent and Suder gave a key-recovery attack against the PMAC variant used in AEZv3 [START_REF] Fuhr | Collision attacks against CAESAR candidatesforgery and key-recovery against AEZ and Marble[END_REF]. Issues with GCM authentication with truncated tags were also pointed out by Ferguson [START_REF] Ferguson | Authentication weaknesses in GCM[END_REF]. These attacks don't contradict the security proofs of the schemes, but they are important results to understand the security degradation after the birthday bound.

Organization of the paper. We first explain our attack technique using quadruples of messages in Section 2, and give three concrete attacks using this technique: an attack against SUM-ECBC and GCM-SIV2 in Section 3, an attack against PMAC+ and related constructions in Section 4, and an attack against 3kf9 in Section 5. Finally, we show a variant of the technique using special properties of the single-key constructions of [START_REF] Datta | Building single-key beyond birthday bound message authentication code[END_REF][START_REF] Datta | Single key variant of PMAC_Plus[END_REF] in Section 6.

Notations. We denote the concatenation of messages blocks x and y as x y. When x and y fit together in one block, we use x|y to denote their concatenation. We use L[i] to denote element i of list L, x [i] to denote bit i of x, and x [i:j] to denote bits i to j -1. Finally, we use a curly brace for systems of equations.

Generic Attack against double-block-hash MACs

We first explain our attacks in a generic way, and leave the specific details to later sections focused on concrete MAC constructions.

We consider MACs where the 2n-bit internal state is divided in two n-bit parts, that we denote Σ and Θ, and the final MAC is computed as:

MAC(M ) = E Σ(M ) ⊕ E Θ(M ) ,
where E and E denote the block cipher with potentially different keys. The functions Σ and Θ can be seen as two n-bit universal hash functions computed on the message, hence the name double-block-hash-then-sum MAC.

Our attacks exploit the fact that the two halves are combined with a sum, where one side depends only on Σ, and the other side depends only on Θ. They do not seem applicable to constructions with more intricate finalization functions, such as LightMAC+2 [START_REF] Naito | Blockcipher-based MACs: Beyond the birthday bound without message length[END_REF], or the tweakable block-cipher based constructions PMAC_TBC [START_REF] Naito | Full PRF-secure message authentication code based on tweakable block cipher[END_REF], PMACx [START_REF] List | Revisiting full-PRF-secure PMAC and using it for beyondbirthday authenticated encryption[END_REF], ZMAC [START_REF] Iwata | ZMAC: A fast tweakable block cipher mode for highly secure message authentication[END_REF], or ZMAC+ [START_REF] List | ZMAC + -an efficient variable-output-length variant of ZMAC[END_REF].

Using Quadruples

Our strategy consists in looking for a quadruple of messages (X, Y, Z, T ) such that pairs of values collide for one half of the state. More precisely, we look for quadruples satisfying a relation R(X, Y, Z, T ) defined as:

R(X, Y, Z, T ) :=          Σ(X) = Σ(Y ) Θ(Y ) = Θ(Z) Σ(Z) = Σ(T ) Θ(T ) = Θ(X)
In particular, since the MAC is computed as MAC(M ) = E Σ(M ) ⊕E Θ(M ) , it follows that: R(X, Y, Z, T ) =⇒ MAC(X) ⊕ MAC(Y ) ⊕ MAC(Z) ⊕ MAC(T ) = 0.

(1)

In addition, if the messages X, Y, Z, T are well constructed, the relation R reduces to a linear system of rank only three, i.e.

Σ(X) = Σ(Y ) and Θ(Y ) = Θ(Z) and Σ(Z) = Σ(T ) =⇒ Θ(T ) = Θ(X).
Therefore, we expect to find one quadruple satisfying the relation out of 2 3n , and we can construct 2 3n quadruples with just 4 × 2 3n/4 queries. This gives an attack with data complexity O(2 3n/4 ).

In practice, we consider lists of 2 3n/4 messages, generated with two message injection functions φ and ψ. These functions are different in every attack, but they mostly correspond to adding two distinct prefixes, as in the following example:

φ(i) = 0 i ψ(i) = 1 i X = φ(x) = 0 x Y = ψ(y) = 1 y Z = φ(z) = 0 z T = ψ(t) = 1 t,
In particular, the pairs (X, Y ), (Y, Z), (Z, T ) and (T, X) that we consider always contain a message built with φ and message built with ψ. Therefore, we will have the required collisions in Σ or Θ if the difference introduced in the half-state by the second block cancels the difference found after processing the first block. This type of attack has some similarities with a higher order differential attack. Indeed, in the easiest case (e. g. our attack against SUM-ECBC), the relation R can be written as R(x, y, z, t) ⇐⇒ x⊕y = z⊕t = ∆ 1 and x⊕t = y⊕z = ∆ 3 for some secret values ∆ 1 and ∆ 3 . This idea of looking for quadruples is also very similar to the attack on EHtM [START_REF] Dutta | Tight security analysis of EHtM MAC[END_REF], but the full attack will turn out quite different. Indeed, in the case of EHtM, the attacker can observe the salt R which represent half of the 2n-bit internal state. Here this would be the equivalent of observing Σ(m) for all processed messages m. This is clearly not possible for the studied constructions and we need something more to discriminate and find a good quadruple that satisfies R.

Detecting Quadruples: Generalized Birthday Algorithms

To finish the attack we usually need to locate one good quadruple. The relation MAC(X) ⊕ MAC(Y ) ⊕ MAC(Z) ⊕ MAC(T ) = 0 in itself is too weak because we expect one quadruple out of 2 n to satisfy it randomly, but we can usually amplify the filtering using related quadruples that satisfy R simultaneously (the exact details depend on the MAC construction).

In most of our attacks, we can express the search for a quadruple as an instance of the 4-sum problem, and solve it using variants of Wagner's generalized birthday algorithm [START_REF] Wagner | A generalized birthday problem[END_REF]. This reduces the time complexity of the attacks (compared to a naive search), and provides trade-offs between the query, memory and time complexities.

More precisely, our problem can be stated as follow:

Definition 1 (4-sum problem). Given four lists L 1 , L 2 , L 3 , L 4 of 2 s elements, with on average 2 p quadruples (x, y, z, t) ∈ L 1 × L 2 × L 3 × L 4 such that x ⊕ y ⊕ z ⊕ t = 0, find one of them.
Note that if the lists contain random n-bit words, we expect to have 2 p = 2 4s-n solutions, but in some of our instances there are more solutions because of the structure of the lists. We denote the join operator as ; it computes the pairwise sum of two lists, and keeps the initial values attached to the sum. In addition, the join operator with filtering α t only keeps values such that the t least significant bits of the sum agree with the value α:

A B = {(a ⊕ b, a, b) : (a, b) ∈ A × B} A α t B = (a ⊕ b, a, b) : (a, b) ∈ A × B, a [0:t] ⊕ b [0:t] = α
In particular, we have = 0 0 . We also denote as ∞ the joint operator with filtering over the full input values. The filtered joint operator is the basis of Wagner's algorithm, and it can be computed in almost linear time by sorting the two input lists, and stepping through them simultaneously. Direct algorithm. While a naive algorithm for our 4-sum instances would take time 2 4s to examine all quadruples, there is a simple improvement with time and memory Õ(2 2s ). First, the attacker builds

L1 L2 L3 L4 α s L α 12 α s L α 34 ∞ for α ∈ {0, 1} s do L α 12 ← L1 α s L2 L α 34 ← L3 α s L4 L ← L α 12 ∞ L α 34 if L = ∅ then (0, (x, y), (z, t)) ← L[0] return (x, y, z, t) end if end for return ⊥
L 12 = L 1 L 2 and L 34 = L 3 L 4 .
Then, he looks for a collision between the first component of L 12 and L 34 . A collision directly yields a solution. This always finds a solution if it exists in Õ(2 2s ) operations but it also takes O(2 2s ) memory.

Memory efficient algorithm.

We can reduce the memory complexity of the algorithm if we avoid constructing the full lists L 12 and L 34 . An algorithm with low memory complexity was first described by Chose et al. [START_REF] Chose | Fast correlation attacks: An algorithmic point of view[END_REF], but we use the description given by Wagner in the full version of [START_REF] Wagner | A generalized birthday problem[END_REF].

Instead of building the full lists L 12 and L 34 , we filter values such that s least significant bits differ by some fixed value α. This reduces the expected size of the lists to only 2

s : E[|L α 34 |] = E[|L α 12 |] = |L 1 | • |L 2 |/2 s = 2 s .
If this algorithm is repeated for every s-bit value α, it will eventually find all solutions.

Actually, one run of the algorithm detects the solutions whose least significant bits of x ⊕ y are equal to α. If there are 2 p solutions in total, there is one such solution with probability 2 p-s , and this algorithm will find the first solution after trying 2 s-p values of α on average. Therefore, the expected time complexity of the algorithm given by Figure 1 is only Õ(2 2s-p ).

Related work.

In a 2016 work, Nikolic and Sasaki [START_REF] Nikolic | Refinements of the k-tree algorithm for the generalized birthday problem[END_REF] investigate the 4-sum where we need to find 4 different inputs x, y, z, t to a function f such that f (x)⊕f (y)⊕f (z)⊕f (t) = 0. They also mention that their algorithm is adaptable to pairwise identical functions, i. e.

f (x) ⊕ g(y) ⊕ f (z) ⊕ g(t) = 0.
Most of our attacks can be written in this way; concretely, they are equivalent to instances of random functions with 3n-bit outputs. In this setting our algorithm takes time Õ(2 3n/2 ) and memory O(2 3n/4 ), while Nikolic and Sasaki's work can reach Õ(2 9n/8 ) time and O(2 3n/4 ) memory. Unfortunately, their algorithm requires Õ(2 9n/8 ) queries to the functions; this would translate to Õ(2 9n/8 ) queries to the MAC, which is not interesting in our context.

Attacking SUM-ECBC-like constructions

We start with attacks against SUM-ECBC [START_REF] Yasuda | The sum of CBC MACs is a secure PRF[END_REF] and GCM-SIV2 [START_REF] Iwata | Stronger security variants of GCM-SIV[END_REF]; while the constructions are quite different, they have a similar structure and the same attacks can be used in both cases. We give a universal forgery attack with O(2 3n/4 ) queries and Õ(2 3n/2 ) operations (using memory O(2 3n/4 )), and a variant with total complexity below 2 n , with O(2 6n/7 ) queries and Õ(2 6n/7 ) operations.

Attacking SUM-ECBC

SUM-ECBC was designed by Yasuda in 2010 [START_REF] Yasuda | The sum of CBC MACs is a secure PRF[END_REF], inspired by MAC constructions summing two CBC-MACs in the ISO 9797-1 standard. The scheme uses a block cipher keyed with four independent keys, denoted as E 1 , E 2 , E 3 , E 4 . The message M is first padded with 10 * padding, and divided into n-bit blocks. In the following we ignore the padding and consider the padded message as the input: this makes our description easier, and any padded message whose last block is non-zero can be "un-padded" to generate a valid input message. The construction is defined as follows (see also Figure 2):

Σ(M ) = σ σ 0 = 0 σ i = E 1 (σ i-1 ⊕ m i ) Θ(M ) = θ θ 0 = 0 θ i = E 3 (θ i-1 ⊕ m i ) MAC(M ) = E 2 (Σ(M )) ⊕ E 4 (Θ(M ))
Attack. Following the framework of Section 2, we consider quadruple of messages, built with two message injection functions:

φ(i) = 0 i ψ(i) = 1 i
In particular, we have

MAC(φ(i)) = E 2 E 1 i ⊕ E 1 (0) Σ0(i) ⊕ E 4 E 3 i ⊕ E 3 (0) Θ0(i) MAC(ψ(i)) = E 2 E 1 i ⊕ E 1 (1)
Σ1(i) ⊕ E 4 E 3 i ⊕ E 3 (1)
Θ1(i)
Next, we build quadruples of messages X, Y, Z, T with

X = φ(x) Y = ψ(y) Z = φ(z) T = ψ(t),
and we look for a quadruple with partial state collisions for the underlying pairs, i. e. a quadruple following the relation:

R(x, y, z, t) :=          Σ 0 (x) = Σ 1 (y) Σ 0 (z) = Σ 1 (t) Θ 0 (z) = Θ 1 (y) Θ 0 (x) = Θ 1 (t).
We have

R(x, y, z, t) ⇔          x ⊕ E 1 (0) = y ⊕ E 1 (1) z ⊕ E 3 (0) = y ⊕ E 3 (1) z ⊕ E 1 (0) = t ⊕ E 1 (1) x ⊕ E 3 (0) = t ⊕ E 3 (1) ⇔      x ⊕ y ⊕ z ⊕ t = 0 x ⊕ y = E 1 (0) ⊕ E 1 (1) x ⊕ t = E 3 (0) ⊕ E 3 (1)
As promised in Section 2, R defines a 3n-bit relation. We can easily observe when x ⊕ y ⊕ z ⊕ t = 0, and we can also detect the relation on the sum of the MACs following Equation (1):

R(x, y, z, t) ⇒ MAC(φ(x)) ⊕ MAC(ψ(y)) ⊕ MAC(φ(z)) ⊕ MAC(ψ(t)) = 0 Moreover, we observe that R(x, y, z, t) is satisfied if and only if R(x ⊕ c, y ⊕ c, z ⊕ c, t ⊕ c
) is satisfied for any constant c. We use this relation to build several quadruples that satisfy R simultaneously:

R(x, y, z, t) ⇐⇒ ∀c, R(x ⊕ c, y ⊕ c, z ⊕ c, t ⊕ c) (2)
This leads to an attack with O(2 3n/4 ) queries: we consider four sets X , Y, Z, T of 2 3n/4 values, and we look for a quadruple (x, y, z, t) ∈ X × Y × Z × T with:

     x ⊕ y ⊕ z ⊕ t = 0 MAC(φ(x)) ⊕ MAC(ψ(y)) ⊕ MAC(φ(z)) ⊕ MAC(ψ(t)) = 0 MAC(φ(x ⊕ 1)) ⊕ MAC(ψ(y ⊕ 1)) ⊕ MAC(φ(z ⊕ 1)) ⊕ MAC(ψ(t ⊕ 1)) = 0. (3)
Because we need a fair distribution of values x ⊕ y and x ⊕ t to find the good quadruple we build the sets as:

X = x ∈ {0, 1} n : x [0:n/4] = 0 Y = x ∈ {0, 1} n : x [n/4:n/2] = 0 Z = x ∈ {0, 1} n : x [n/2:3n/4] = 0 T = x ∈ {0, 1} n : x [3n/4:n] = 0
With this construction, there is exactly one quadruple (x, y, z, t) ∈ X ×Y ×Z ×T that respects R, given by:

x = v 1 |w 2 |u 3 |0 y = w 1 |v 2 |0|u 4 z = u 1 |0|v 3 |w 4 t = 0|u 2 |w 3 |v 4 ,
where:

E 1 (0) ⊕ E 1 (1) =: u 1 |u 2 |u 3 |u 4 E 3 (0) ⊕ E 3 (1) =: v 1 |v 2 |v 3 |v 4 E 1 (0) ⊕ E 1 (1) ⊕ E 3 (0) ⊕ E 3 (1) =: w 1 |w 2 |w 3 |w 4 .
We expect on average one random quadruple satisfying (3) (with 2 3n potential quadruples, and a 3n-bit filtering), in addition to the quadruple satisfying R.

The correct quadruple can easily be checked with a few extra queries.

In practice, we use the generalized birthday algorithms of Section 2.2 in order to optimize the complexity of the attack. We consider four lists:

L 1 = {x MAC(φ(x)) MAC(φ(x ⊕ 1)) : x ∈ X } L 2 = {y MAC(ψ(y)) MAC(ψ(y ⊕ 1)) : y ∈ Y} L 3 = {z MAC(φ(z)) MAC(φ(z ⊕ 1)) : z ∈ Z} L 4 = { t MAC(ψ( t )) MAC(ψ( t ⊕ 1)) : t ∈ T }
Notice that we can build those lists with 5 • 2 3n/4 queries as, by construction, for any element i of Y, Z, T the element (i ⊕ 1) also belongs to Y, Z, T , respectively. We use the algorithm of Section 2.2 to find (x, y, z, t)

∈ X × Y × Z × T such that L 1 [x] ⊕ L 2 [y] ⊕ L 3 [z] ⊕ L 4 [t] = 0 with Õ(2 3n/2
) operations, using a memory of size O(2 3n/4 ). After finding a collision, we verify that it is not a false positive by testing the relation for another value c. As there are on average O(1) random quadruples the attack is indeed using a total of 5

• 2 3n/4 + O(1) = O(2 3n/4 ) queries.
Universal Forgeries. This attack can be extended to a universal forgery. Indeed, the fixed prefix 0 and 1 can be replaced by v and v ⊕ 1 for any block v, and when we identify a right quadruple (x, y, z, t) we deduce the value

∆ 1 = E 1 (v) ⊕ E 1 (v ⊕ 1) and ∆ 3 = E 3 (v) ⊕ E 3 (v ⊕ 1). There is also a length extension property: if (x, y, z, t) is a right quadruple, then MAC(v x s) ⊕ MAC(v ⊕ 1 y s) ⊕ MAC(v z s) ⊕ MAC(v ⊕ 1 t s) = 0 for any suffix s.
Therefore if we want to forge a MAC for any message m of size ≥ 2 blocks we parse it as m = v w s (where s has zero, one, or several blocks) and perform the attack to recover ∆ 1 and ∆ 3 . Then we can forge using the previous relation, and Equation (2):

MAC(v w s) = MAC(v ⊕ 1 w ⊕ ∆ 1 s) ⊕ MAC(v w ⊕ ∆ 3 s) ⊕ MAC(v ⊕ 1 w ⊕ ∆ 1 ⊕ ∆ 3 s)
Optimizing the time complexity. Equation ( 2) can also be used to reduce the time complexity below 2 n , at the cost of more oracle queries. Indeed, if we consider a subset C of {0, 1} n , we have:

R(x, y, z, t) ⇔ ∀c ∈ C, R(x ⊕ c, y ⊕ c, z ⊕ c, t ⊕ c) ⇒ ∀c ∈ C, MAC(φ(x ⊕ c)) ⊕ MAC(ψ(y ⊕ c)) ⊕ MAC(φ(z ⊕ c)) ⊕ MAC(ψ(t ⊕ c)) = 0 ⇒ c∈C MAC(φ(x ⊕ c)) ⊕ c∈C MAC(ψ(y ⊕ c)) ⊕ c∈C MAC(φ(z ⊕ c)) ⊕ c∈C MAC(ψ(t ⊕ c)) = 0 (4)
If we select C as a linear subspace, then the last expression does not depend on the full (x, y, z, t), but only on their projection on the orthogonal of C. Concretely, we use C = x : x [3n/7:n] = 0 = x : x < 2 3n/7 , so that the value c∈C MAC(φ(x ⊕ c)) is independent of bits 0 to 3n/7 -1 of x. Therefore, we consider the rewritten MAC function

MAC (v w) = c∈C MAC(v w ⊕ c),
the following message injections, with a 4n/7-bit input

φ (i) = 0 i|0 ψ (i) = 1 i|0,
and a reduced relation over 4n/7-bit values:

R (x, y, z, t) :=          x ⊕ y = (E 1 (0) ⊕ E 1 (1)) [3n/7:n] y ⊕ z = (E 3 (0) ⊕ E 3 (1)) [3n/7:n] z ⊕ t = (E 1 (0) ⊕ E 1 (1)) [3n/7:n] t ⊕ x = (E 3 (0) ⊕ E 3 (1)) [3n/7:n] ⇔      x ⊕ y ⊕ z ⊕ t = 0 x ⊕ y = (E 1 (0) ⊕ E 1 (1)) [3n/7:n] x ⊕ t = (E 3 (0) ⊕ E 3 (1)) [3n/7:n]
Thanks to Equation 4, we still have:

R (x, y, z, t) ⇒ MAC (φ (x)) ⊕ MAC (ψ (y)) ⊕ MAC (φ (z)) ⊕ MAC (ψ (t)) = 0
Since the relation R is now only a 12n/7-bit condition, we can use shorter lists than before, with just 2 3n/7 elements. We can also increase the filtering using the same trick as previously, considering the following lists:

L 1 = x MAC (φ (x)) MAC (φ (x ⊕ 1)) : x ∈ {0, 1} 4n/7 , x [0:n/7] = 0 L 2 = y MAC (ψ (y)) MAC (ψ (y ⊕ 1)) : y ∈ {0, 1} 4n/7
, y [n/7:2n/7] = 0

L 3 = z MAC (φ (z)) MAC (φ (z ⊕ 1)) : z ∈ {0, 1} 4n/7 , z [2n/7:3n/7] = 0 L 4 = t MAC (ψ ( t )) MAC (ψ ( t ⊕ 1)) : t ∈ {0, 1} 4n/7 , t [3n/7:4n/7] = 0
Finally, using the algorithm of Section 2.2 with s = 3n/7 and p = 0, we can locate a right quadruple using Õ(2 6n/7 ) queries, Õ(2 6n/7 ) operations, and O(2 3n/7 ) memory. This recovers only 4n/7 bits of E 1 (0) ⊕ E 1 (1) and E 3 (0) ⊕ E 3 (1), but we can easily recover the remaining bits, either by brute force, or by repeating the attack with a different set C.

Attacking GCM-SIV2

GCM-SIV2 is an authenticated encryption mode designed by Iwata and Minematsu [START_REF] Iwata | Stronger security variants of GCM-SIV[END_REF] as a double-block-hash version of GCM-SIV (in the following, we consider GCM-SIV2 with GHASH as the underlying universal hash function). For simplicity, we focus on the authentication part of GCM-SIV2, using inputs with a non-empty associated data, and an empty message. In this case, GCM-SIV2 becomes a nonce-based MAC. The message M (considered as associated data for the mode) is zero-padded, divided into n-bit blocks, and the length is appended in an extra block. Then the construction is defined as follows, with a finite field multiplication (see also Figure 3):

Σ(N, M ) = N ⊕ H 1 ⊕ i=1 m i H +2-i 1 Θ(N, M ) = N ⊕ H 2 ⊕ i=1 m i H +2-i 2 MAC(N, M ) = E 1 (Σ(M )) ⊕ E 2 (Θ(M )) E 3 (Σ(M )) ⊕ E 4 (Θ(M ))
Attack. The structure of the authentication part of GCM-SIV2 is essentially the same as the structure of SUM-ECBC, where the block cipher calls E 1 and E 3 are replaced by multiplication by H 1 and H 2 . The finalization function has a 2n-bit output MAC 1 , MAC 2 , but quadruples following R will collide on both outputs. Thus, we can essentially repeat the SUM-ECBC attack, but there is an important difference: GCM-SIV2 is a nonce-based MAC, rather than a deterministic one. Therefore, all queries must include a nonce N , and we should not query two different messages with the same nonce. We adapt the previous attack using message injection functions that output both a nonce and a message, so that we use two fixed messages, 0 and 1, with variable nonces:

φ(i) = (i, 0) ψ(i) = (i, 1)

MAC(φ(

i)) = E 1 i ⊕ H 1 Σ0(i) ⊕ E 2 i ⊕ H 2 Θ0(i) E 3 Σ 0 (i) ⊕ E 4 Θ 0 (i) MAC(ψ(i)) = E 1 i ⊕ H 1 ⊕ H 2 1 Σ1(i) ⊕ E 2 i ⊕ H 2 ⊕ H 2 2 Θ1(i) E 3 Σ 1 (i) ⊕ E 4 Θ 1 (i) .
We consider quadruples of nonce/messages X, Y, Z, T with

X = φ(x) Y = ψ(y) Z = φ(z) T = ψ(t),
and we have the same kind of relations as in the previous attack:

R(x, y, z, t) :=          Σ 0 (x) = Σ 1 (y) Σ 0 (z) = Σ 1 (t) Θ 0 (z) = Θ 1 (y) Θ 0 (x) = Θ 1 (t). ⇔      x ⊕ y ⊕ z ⊕ t = 0 x ⊕ y = H 2 1 x ⊕ t = H 2 2 ⇒ MAC(φ(x)) ⊕ MAC(ψ(y)) ⊕ MAC(φ(z)) ⊕ MAC(ψ(t)) = 0
Since the MAC output is 2n-bit long, we can directly build an attack with O(2 3n/4 ) queries: we consider four distinct sets X , Y, Z, T of 2 3n/4 values, and we look for a quadruple (x, y, z, t) ∈ X × Y × Z × T , such that

x ⊕ y ⊕ z ⊕ t = 0 MAC(φ(x)) ⊕ MAC(ψ(y)) ⊕ MAC(φ(z)) ⊕ MAC(ψ(t)) = 0 (5)
we expect to find one good quadruple that respects R along with O(1) quadruples that randomly satisfy the observable filter [START_REF] Black | A block-cipher mode of operation for parallelizable message authentication[END_REF]. This leads to an attack with O(2 3n/4 ) queries and time Õ(2 3n/2 ). Since we recover H 1 and H 2 (from H 2 1 = x ⊕ y and H 2 2 = x ⊕ t), we can do universal forgeries. In addition, we can also easily adapt the attack with O(2 6n/7 ) queries and time Õ(2 6n/7 ).

Attacking PMAC-like constructions

We now describe attacks against PMAC+ [START_REF] Yasuda | A new variant of PMAC: Beyond the birthday bound[END_REF] and related constructions: 1kMAC+ [9], and LightMAC+ [START_REF] Naito | Blockcipher-based MACs: Beyond the birthday bound without message length[END_REF]. We have an existential forgery attack with O(2 3n/4 ) queries and Õ(2 3n/2 ) operations (using memory O(2 3n/4 )), with a range of time-memory trade-offs with O(2 t ) queries, with 3n/4 < t < n, and Õ(2 3n-2t ) operations (using memory O(2 t )).

Attacking PMAC+

PMAC+ was designed by Yasuda in 2011 [START_REF] Yasuda | A new variant of PMAC: Beyond the birthday bound[END_REF], as a variant of PMAC [START_REF] Black | A block-cipher mode of operation for parallelizable message authentication[END_REF] with a larger internal state. The scheme internally uses a tweakable block cipher construction inspired by the XE construction [START_REF] Rogaway | Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC[END_REF], that we denote as Ẽi . The message M is first padded with 10 * padding, and divided into n-bit blocks, but for simplicity we ignore the padding in our description. The construction is shown in Figure 4 3 :

Σ(M ) = i=1 Ẽi (m i ) Ẽi (x) = E 1 (x ⊕ 2 i ∆ 0 ⊕ 2 2i ∆ 1 ) Θ(M ) = i=1 2 -i Ẽi (m i ) ∆ 0 = E 1 (0) ∆ 1 = E 1 (1) MAC(M ) = E 2 (Σ(M )) ⊕ E 3 (Θ(M ))
Attack. As in the previous attack, we use message injection functions with two different prefixes, but we include an extra block u to define related quadruples:

φ u (i) = u 0 i ψ u (i) = u 1 i MAC(φ u (i)) = E 2 Ẽ1 (u) ⊕ Ẽ2 (0) ⊕ Ẽ3 (i) Σu,0(i) ⊕ E 3 4 Ẽ1 (u) ⊕ 2 Ẽ2 (0) ⊕ Ẽ3 (i) Θu,0(i) MAC(ψ u (i)) = E 2 Ẽ1 (u) ⊕ Ẽ2 (1) ⊕ Ẽ3 (i) Σu,1(i) ⊕ E 3 4 Ẽ1 (u) ⊕ 2 Ẽ2 (1) ⊕ Ẽ3 (i) Θu,1(i)
.

Next, we build quadruples of messages X, Y, Z, T with

X = φ u (x) Y = ψ u (y) Z = φ u (z) T = ψ u (t),
and we look for a quadruple with partial state collisions for the underlying pairs, i. e. a quadruple following the relation: We have

R(x, y, z, t) :=          Σ u,0 (x) = Σ u,1 (y) Σ u,0 (z) = Σ u,1 (t) Θ u,0 (z) = Θ u,1 (y) Θ u,0 (x) = Θ u,1 (t). m1 2 • ∆0 2 2 • ∆1 E1 Ẽ1 0 0 2 -1 m2 2 2 • ∆0 2 4 • ∆1 E1 Ẽ2 2 -2 ... ... ... m 2 • ∆0 2 2 • ∆1 E1 Ẽ 2 0 E2 E3 Σ Θ MAC(m)
R(x, y, z, t) ⇔          Ẽ3 (x) ⊕ Ẽ2 (0) = Ẽ3 (y) ⊕ Ẽ2 (1) Ẽ3 (z) ⊕ Ẽ2 (0) = Ẽ3 (t) ⊕ Ẽ2 (1) Ẽ3 (y) ⊕ 2 Ẽ2 (1) = Ẽ3 (z) ⊕ 2 Ẽ2 (0) Ẽ3 (t) ⊕ 2 Ẽ2 (1) = Ẽ3 (x) ⊕ 2 Ẽ2 (0) ⇔      Ẽ3 (x) ⊕ Ẽ3 (y) ⊕ Ẽ3 (z) ⊕ Ẽ3 (t) = 0 Ẽ3 (x) ⊕ Ẽ3 (y) = Ẽ2 (0) ⊕ Ẽ2 (1) Ẽ3 (t) ⊕ Ẽ3 (x) = 2 Ẽ2 (0) ⊕ 2 Ẽ2 (1)
Again, R defines a 3n-bit relation, and we can detect it through the sum of the MACs following Equation (1):

R(x, y, z, t) ⇒ MAC(φ u (x)) ⊕ MAC(ψ u (y)) ⊕ MAC(φ u (z)) ⊕ MAC(ψ u (t)) = 0
In addition, the relation R is independent of the value u, so that we can easily build several quadruples that satisfy R simultaneously. This leads to an attack with O(2 3n/4 ) queries: we consider four sets X , Y, Z, T of 2 3n/4 random values, and we look for a quadruple (x, y, z, t) ∈ X × Y × Z × T , such that

∀u ∈ {0, 1, 2}, MAC(φ u (x)) ⊕ MAC(ψ u (y)) ⊕ MAC(φ u (z)) ⊕ MAC(ψ u (t)) = 0
We expect on average one random quadruple (with 2 3n potential quadruples, and a 3n-bit filtering), and one quadruple satisfying R (also a 3n-bit condition). The correct quadruple can easily be checked with a few extra queries.

In practice, we use the generalized birthday algorithms of Section 2.2 in order to optimize the complexity of the attack. We consider four lists:

L 1 = {MAC(φ 0 (x)) MAC(φ 1 (x)) MAC(φ 2 (x)) : x ∈ X } L 2 = {MAC(ψ 0 (y)) MAC(ψ 1 (y)) MAC(ψ 2 (y)) : y ∈ Y} L 3 = {MAC(φ 0 (z)) MAC(φ 1 (z)) MAC(φ 2 (z)) : z ∈ Z} L 4 = {MAC(ψ 0 ( t )) MAC(ψ 1 ( t )) MAC(ψ 2 ( t )) : t ∈ T } and we look for a quadruple (x, y, z, t) ∈ X × Y × Z × T such that L 1 [x] ⊕ L 2 [y] ⊕ L 3 [z] ⊕ L 4 [t] = 0.
This can be done with Õ(2 3n/2 ) operations, using a memory of size O(2 3n/4 ). Finally, once a quadruple (x, y, z, t) satisfying R(x, y, z, t) has been detected, it can be used to generate forgeries. Indeed, we can predict the MAC of a new message by making three new queries using Equation ( 1):

∀u, MAC(φ u (x)) = MAC(ψ u (y)) ⊕ MAC(ψ u (z)) ⊕ MAC(φ u (t))
Time-Query Trade-offs. As opposed to the SUM-ECBC attack, we don't have an analogue to Equation ( 2) that can be used to reduce the time complexity. However, the time complexity of the algorithm can be slightly reduced when using more than O(2 3n/4 ) queries. If we consider sets X , Y, Z, T of size 2 t with 3n/4 < t < n, the resulting 4-sum is slightly easier, because there are 2 4t-3n expected solutions. Using the algorithm of section 2.2, this can be solved in time Õ(2 3n-2t ), using a memory of size O(2 t ).

Attacking LightMAC+

LightMAC+ was designed by Naito [START_REF] Naito | Blockcipher-based MACs: Beyond the birthday bound without message length[END_REF] using ideas from PMAC+ [START_REF] Yasuda | A new variant of PMAC: Beyond the birthday bound[END_REF] and LightMAC [START_REF] Luykx | A MAC mode for lightweight block ciphers[END_REF]. If we consider it as based on a tweakable block cipher Ẽ, it follows the same structure as PMAC+ (see Figure 5), but Ẽ takes a message block smaller than n bits:

Σ(M ) = i=1 Ẽi (m i ) Ẽi (x) = E 1 (i|x) Θ(M ) = i=1 2 -i Ẽi (m i ) MAC(M ) = E 2 (Σ(M )) ⊕ E 3 (Θ(M ))
Since the structure of LightMAC+ is the same as the structure of PMAC+, we can use the same attack. The only difference from our point of view is that the message blocks are shorter than the block-size. As long as one message block is big enough to fit 2 3n/4 different values, our attack will succeed.

This attack violates the improved security proof recently published at CT-RSA [START_REF] Naito | Improved security bound of LightMAC_Plus and its single-key variant[END_REF], with a security bound of O(q 2 t q v /2 2n ) (with q t MAC queries and q v verification queries). Indeed, our attack reaches a constant success probability with q t = O(2 3n/4 ) and q v = 1. We have shared our attack with Naito and he agreed that his proof is flawed.

Attacking 1kPMAC+

1kPMAC+ is a single-key variant of PMAC+ [START_REF] Yasuda | A new variant of PMAC: Beyond the birthday bound[END_REF] designed by Datta, Dutta, Nandi, Paul and Zhang [START_REF] Datta | Single key variant of PMAC_Plus[END_REF], shown in Figure 8.

Since the structure of 1kPMAC+ is the same as the structure of PMAC+, we can use the same attack. Alternatively, we can take advantage of the fix functions to mount a more straightforward attack, as shown in Section 6.

Attacking f9-like constructions

Our third attack is applicable to 3kf9 [START_REF] Zhang | 3kf9: Enhancing 3GPP-MAC beyond the birthday bound[END_REF] and similar constructions. We have a universal forgery attack with O(2 3n/4 ) queries and Õ(2 5n/4 ) operations using memory O(2 n ), with a possible time-memory trade-offs.

Attacking 3kf9

3kf9 [START_REF] Zhang | 3kf9: Enhancing 3GPP-MAC beyond the birthday bound[END_REF], designed by Xhang, Wu, Sui and Wang, is a three-key variant of the f9 mode used in 3G telephony. While the original f9 does not have security beyond the birthday bound [START_REF] Knudsen | Analysis of 3gpp-mac and two-key 3gpp-mac[END_REF], 3kf9 is secure up to 2 2n/3 queries. We describe 3kf9 in Figure 6:

Σ(M ) = σ σ 0 = 0 σ i = E 1 (σ i-1 ⊕ m i ) Θ(M ) = i=1 σ i MAC(M ) = E 2 (Σ(M )) ⊕ E 3 (Θ(M ))
Attack. Our attack follows the same structure as the previous attacks. We start with messages of the form:

φ(i) = 0 i ψ(i) = 1 i,
and the corresponding MACs:

MAC(φ(i)) = E 2 E 1 x ⊕ E 1 (0) Σ0(x) ⊕ E 3 E 1 x ⊕ E 1 (0) ⊕ E 1 0 Θ0(x) MAC(ψ(i)) = E 2 E 1 x ⊕ E 1 (1) Σ1(x) ⊕ E 3 E 1 x ⊕ E 1 (1) ⊕ E 1 1 Θ1(x)
.

We use quadruples of messages X, Y, Z, T with

X = φ(x) Y = ψ(y) Z = φ(z) T = ψ(t),
and we look for a quadruple with partial state collisions for the underlying pairs, i. e. a quadruple following the relation:

R(x, y, z, t) :=          Σ 0 (x) = Σ 1 (y) Σ 0 (z) = Σ 1 (t) Θ 0 (z) = Θ 1 (y) Θ 0 (x) = Θ 1 (t). ⇔          x ⊕ E 1 (0) = y ⊕ E 1 (1) z ⊕ E 1 (0) = t ⊕ E (1) E 1 (z ⊕ E 1 (0)) ⊕ E 1 (0) = E 1 (y ⊕ E 1 (1)) ⊕ E 1 (1) E 1 (x ⊕ E 1 (0)) ⊕ E 1 (0) = E 1 (t ⊕ E 1 (1)) ⊕ E 1 (1) ⇔      x ⊕ y ⊕ z ⊕ t = 0 x ⊕ y = E 1 (0) ⊕ E 1 (1) E 1 (x ⊕ E 1 (0)) ⊕ E 1 (t ⊕ E 1 (1)) = E 1 (0) ⊕ E 1 (1) ⇒ MAC(φ(x)) ⊕ MAC(ψ(y)) ⊕ MAC(φ(z)) ⊕ MAC(ψ(t)) = 0.
As in the previous attacks, R defines a 3n-bit relation. Moreover, we can easily observe when x ⊕ y ⊕ z ⊕ t = 0, and the relation x ⊕ y = E 1 (0) ⊕ E 1 (1) can be verified across several quadruples. We don't have related quadruples satisfying R simultaneously as in the previous attacks, but we can use those properties to detect right quadruples. This leads to an attack with Õ(2 3n/4 ) queries: we consider four sets X , Y, Z, T of 4 √ n × 2 3n/4 random values, and we look for quadruples (x, y, z, t) ∈ X × Y × Z × T , such that: Since this a 2n-bit condition, we expect on average n • 2 n quadruples (x, y, z, t) satisfying [START_REF] Chose | Fast correlation attacks: An algorithmic point of view[END_REF]. In order to filter out the right ones, we look at the value x ⊕ y for all these quadruples. While the wrong quadruples should have a random x ⊕ y, the right ones have x ⊕ y = E 1 (0) ⊕ E 1 (1). Therefore, with high probability, the most frequent value for x⊕y is equal to E 1 (0)⊕E 1 [START_REF] An | Constructing VIL-MACs from FIL-MACs: Message authentication under weakened assumptions[END_REF], and quadruples satisfying this extra relation are right quadruples with probability 1 /2. More precisely, we expect on average n wrong quadruples for each value of x ⊕ y, and n right quadruples with x ⊕ y = E 1 (0) ⊕ E 1 [START_REF] An | Constructing VIL-MACs from FIL-MACs: Message authentication under weakened assumptions[END_REF].

x ⊕ y ⊕ z ⊕ t = 0 MAC(φ(x)) ⊕ MAC(ψ(y)) ⊕ MAC(φ(z)) ⊕ MAC(ψ(t)) = 0. ( 6
Optimizing the time complexity. While the algorithm of Section 2.2 would take time Õ(2 3n/2 ) with Õ(2 3n/4 ) queries, we can reduce the time complexity using sets X , Y, Z, T with some structure. More precisely, we use:

X = Z = x ∈ {0, 1} n : x [0:n/4] = 0 Y = T = x ∈ {0, 1} n : x [n/4:n/2] = 0
so that quadruples can be written as

x =: x 3 |x 2 |x 1 |0 ∈ X y =: y 3 |y 2 |0|y 0 ∈ Y z =: z 3 |z 2 |z 1 |0 ∈ Z t =: t 3 |t 2 |0|t 0 ∈ T .
In particular, right quadruples satisfy x⊕y⊕z ⊕t = 0, therefore x 1 = z 1 , y 0 = t 0 , and

x 3 |x 2 ⊕ z 3 |z 2 = y 3 |y 2 ⊕ t 3 |t 2 .
We use these properties to adapt the algorithm of Section 2.2 and locate the quadruples efficiently. First we guess the n/2-bit

value α 3 |α 2 := x 3 |x 2 ⊕ z 3 |z 2 = y 3 |y 2 ⊕ t 3 |t 3 . Then, for each x = x 3 |x 2 |x 1 |0, there is a single candidate z = (x 3 ⊕ α 3 )|(x 2 ⊕ α 2 )|x 1 |0
that could be part of a right quadruple. Similarly, every y = y 3 |y 2 |0|y 0 can be paired with a single t = (y 3 ⊕ α 3 )|(y 2 ⊕ α 2 )|0|y 0 . Therefore, we consider the two following lists:

L 1 = {MAC(φ(x 3 |x 2 |x 1 |0)) ⊕ MAC((x 3 ⊕ α 3 )|(x 2 ⊕ α 2 )|x 1 |0) : x 3 |x 2 |x 1 |0 ∈ X } L 2 = {MAC(φ(y 3 |y 2 |0|y 0 )) ⊕ MAC((y 3 ⊕ α 3 )|(y 2 ⊕ α 2 )|0|y 0 ) : y 3 |y 2 |0|y 0 ∈ Y}
After sorting the lists, we look for matches, and the corresponding quadruples x, y, z, t are exactly the quadruples satisfying

     x ⊕ y ⊕ z ⊕ t = 0 (x ⊕ z) [n/2:n] = α 3 |α 2 MAC(φ(x)) ⊕ MAC(ψ(y)) ⊕ MAC(φ(z)) ⊕ MAC(ψ(t)) = 0. (7)
More precisely, a match We need Õ(2 3n/4 ) operations to generate those quadruples. We repeat this 2 n/2 times to exhaust all n/2-bit values α 3 |α 2 and generate all quadruples satisfying [START_REF] Chose | Fast correlation attacks: An algorithmic point of view[END_REF]. Finally, we use an array to count the number of occurrences of each possible value of x ⊕ y. Each counter receives an average two values, but the counter corresponding to E 1 (0) ⊕ E 1 (1) will receive three values on average. After repeating all the operations O(n) times, with some arbitrary constants in place of the zero bits, the highest counter corresponds to E 1 (0) ⊕ E 1 (1) with high probability, as proved in Section 5.2. This gives an attack with Õ(2 3n/4 ) queries, Õ(2 5n/4 ) operations, and O(2 n ) memory 4 . Time-Memory Trade-offs. We can reduce the memory usage if we store only a subset of the counters, and repeat the whole algorithm until the whole set has been covered. Concretely, we store only the counters with a fixed value for bits [0 : n/8] and [n/4 : 3n/8] of x ⊕ y. Because of the way the lists L 1 and L 2 are constructed, we have actually fixed n/8 bits of y 0 and x 1 , and we can reduce the lists to size 2 5n/8 . Therefore we evaluate 2 3n/4 counters in time Õ(2 n/2 • 2 5n/8 ), using only O(2 3n/4 ) memory. We repeat iteratively over the full counter set, so we need time Õ(2 n/4 • 2 n/2 • 2 5n/8 ) = Õ(2 11n/8 ). More generally, we have a timememory trade-off with time Õ(2 5n/4+t/2 ) and memory O(2 n-t ) for 0 < t < n/4.

L 1 [x] = L 2 [y] suggests z = x ⊕ α 3 |α 2 |0|0
Forgeries. Once we found a quadruple (x, y, z, t) that respects R(x, y, z, t) we know that after processing message φ(x) = 0 x and ψ(t) = 1 t, there is no difference in the Θ part of the state (Θ 0 (x) = Θ 1 (t)). Moreover we have [START_REF] An | Constructing VIL-MACs from FIL-MACs: Message authentication under weakened assumptions[END_REF]; this implies that there is a difference E 1 (0) ⊕ E 1 (1) = x ⊕ y in the Σ part of the state. Therefore, we can build a full state collision with message 0 x 0 and 1 t x ⊕ y. In particular, the following relation can be used to create forgeries with an arbitrary message m (of any length):

Θ 0 (x) = Σ 0 (x) ⊕ E 1 (0) and Θ 1 (t) = Σ 1 (x) ⊕ E 1
MAC(0 x 0 m) = MAC(1 t x ⊕ y m).
Universal Forgeries. We can even forge the tag of an arbitrary message of length at least (2n + 2) blocks with complexity only n + 1 times the complexity of the simple forgery attack. The technique is more advanced and inspired by the multi-collision attack described by Joux [START_REF] Joux | Multicollisions in iterated hash functions. Application to cascaded constructions[END_REF]. For ease of notation we'll show how to forge the signature for a message starting with 2n + 2 blocks of zero, but this can be trivially adapted for any message.

First, we find a quadruple (x 1 , y 1 , z 1 , t 1 ) as before. Then we consider messages 0 0 and 1 x 1 ⊕y 1 . Since x 1 ⊕y 1 = E 1 (0)⊕E 1 (1), we have Σ(0 0) = Σ(1 x 1 ⊕y 1 ), i. e. the Σ part of the state collides. Moreover, we know the difference in the Θ part:

Θ(0 0) ⊕ Θ(1 x 1 ⊕ y 1 ) = x 1 ⊕ y 1 .
More generally, at step i we use message injection functions

φ i (x) = 0 0 . . . 0 ×2(i-1) 0 x ψ i (x) = 0 0 . . . 0 ×2(i-1) 1 x,
to look for a quadruple of messages

X i = φ i (x i ) Y i = ψ i (y i ) Z i = φ i (z i ) T i = ψ i (t i ).
When a right quadruple (x i , y i , z i , t i ) has been identified, we can deduce that the MACs for 0 0 . . . 0 0 0 and 0 0 . . . 0 1 x i ⊕ y i will match on the Σ branch and differ by x i ⊕ y i in their Θ branch.

After several iterations, we have actually built a multi-collision: all the messages h 1 h 2 . . . h n h n+1 with h i ∈ {(1 x i ⊕ y i ), (0 0)} collide on the Σ branch. In addition, we also know the difference in the Θ branch for those messages: it is equal to {i : hi =0 0} (x i ⊕ y i ).

After at most n + 1 steps, we can find a non empty subset I ⊆ [1 : n + 1] such that i∈I (x i ⊕ y i ) = 0 by simple linear algebra 5 . This gives a collision on the full state, using messages m 0 = 0 0 . . . 0 (with 2(n + 1) blocks) and h = h 1 h 2 . . . h n h n+1 with h i = 1 x i ⊕ y i if i ∈ I, h i = 0 0 otherwise. Since the full state collides, we have for any message m (of any length): MAC(h m) = MAC(m 0 m).

Detailed Complexity Analysis

We want to prove the claim that one will need to find O(n • 2 n ) quadruples in order to finish the attack on 3kf9 described in Section 5.1. We say the attack finishes when we recover the target value T = E(0) ⊕ E [START_REF] An | Constructing VIL-MACs from FIL-MACs: Message authentication under weakened assumptions[END_REF].

Assuming that each quadruple we find respects R with probability 1/2 n , we fill a list of counters for every suspected values of T ; a random quadruple gives two random values and a right one gives one value equal to T and one random value. Therefore we sum up the distribution of an observable value x as:

x $ ←-{0, 1} n with probability 1 -1/2 n+1 ←-T with probability 1/2 n+1
Let N be the number of observed values, and X c i represents the indicator that the i th value equals c (following a Bernoulli distribution), so that the counter corresponding to c is X c = N i=1 X c i . Now we have to discriminate between the distributions of X c with c = T , and the distribution of X T :

Pr(X T i = 1) = Pr(x = T ) = (1 -1/2 n+1 )/2 n + 1/2 n+1 = (3/2 -1/2 n+1 )/2 n =⇒ E[X T ] = N (3/2 -1/2 n+1 )/2 n Pr(X c i = 1) = Pr(x = c) = (1 -1/2 n+1 )/2 n =⇒ E[X c ] = N (1 -1/2 n+1 )/2 n =⇒ E[X T ] ≥ 3/2 • E[X c ]
We use the Chernoff bound to get a lower bound on the probability that a given counter is higher than the average value of X T :

Pr(X c ≥ E[X T ]) ≤ P r(X c ≥ 3/2 • E[X c ]) ≤ e -N (1-1/2 n+1 )/2 n+1
and assuming the counters are independent:

P r(X c < E[X T ]) ≥ 1 -e -N (1-1/2 n+1 )/2 n+1 P r(∀c = T : X c < E[X T ]) ≥ (1 -e -N (1-1/2 n+1 )/2 n+1 ) 2 n
This expression will asymptotically converge to a strictly positive constant when e -N (1-1/2 n+1 )/2 n+1 2 -n . Therefore, we use

N n ln(2) • 2 n+1 (1 -1/2 n+1 ) = O(n • 2 n ).
Since we observe 2 values per quadruples, this makes O(n • 2 n ) quadruples. Moreover, the event 'X T ≥ E[X T ]' has a probability close to 0.5, therefore after O(n • 2 n ) quadruples, we indeed have a Ω(1) probability that X T is greater than all of the other counters, which allows to recover the value T . Performing the attack until the end with probability Ω(1) also requires O(n • 2 n ) quadruples.

To get to this result some assumptions have been made, like the independence of the counters, but they all tend to be either conservative or asymptotically true.

Attacking 1kf9

1kf9 is a single-key variant of 3kf9 suggested in [START_REF] Datta | Building single-key beyond birthday bound message authentication code[END_REF], and later withdrawn. Since the structure of 1kf9 is the same as the structure of 3kf9, we can use the same attack. However, in the next section, we give an attack with birthday complexity using properties of the fix functions. Zhang [START_REF] Datta | Building single-key beyond birthday bound message authentication code[END_REF][START_REF] Datta | Single key variant of PMAC_Plus[END_REF]. The fix functions just fix the least significant bit an n-bit value to zero or one, and are used for domain separation:

Attacks using collision in fix functions

fix0 : x → x [1:n] |0 fix1 : x → x [1:n] |1
Datta et al. used those function to build a single-key variant of PMAC+ called 1kPMAC+ [START_REF] Datta | Single key variant of PMAC_Plus[END_REF], and a single-key variant of 3kf9 called 1kf9 [START_REF] Datta | Building single-key beyond birthday bound message authentication code[END_REF], both with security up to 2 2n/3 queries. However, 1kf9 has been withdrawn because of issues in its security proof. In this section, we exploit trivial collisions in the fix functions to build colliding pairs or quadruples more easily:

fix0(x) = fix0(x ⊕ 1) fix1(x) = fix1(x ⊕ 1)
This allows a more straightforward attack against 1kPMAC+ with the same complexity as the attacks in Section 4, and an attack against 1kf9 [START_REF] Datta | Building single-key beyond birthday bound message authentication code[END_REF] with birthday complexity, violating its security claims.

Attacking 1kf9

The 1kf9 mode uses the fix function for domain separation to build a single-key variant of 3kf9, as shown in Figure 7:

σ 0 = 0 σ i = E(σ i-1 ⊕ m i ) Σ (M ) = σ Σ(M ) = 2 fix0(Σ (M )) Θ (M ) = i=1 σ i Θ(M ) = 2 fix1(Θ (M )) MAC(M ) = E(Σ(M )) ⊕ E(Θ(M ))
Attack. Because of a mistake in the proof of 1kf9, we can use pairs of messages instead of quadruples. More precisely, instead of looking for a quadruple with pairwise collisions in Σ and Θ, we look for a pair of message X, Y colliding on Σ , and with a difference in Θ that will be absorbed by the fix1 function. Therefore, we define the relation R as:

R(X, Y ) := Σ (X) = Σ (Y ) 2Θ (X) = 2Θ (Y ) ⊕ 1 ⇒ MAC(X) = MAC(Y ).
We build the messages with different postfixes, parametrized by u:

X = φ u (x) = x u Y = ψ u (y) = y u ⊕ d,
where d is the inverse of 2 in the finite field. With this construction, we have

Σ (φ u (x)) = E u ⊕ E(x ⊕ E(0)) Θ (φ u (x)) = E u ⊕ E(x ⊕ E(0)) ⊕ E x ⊕ E(0) ⊕ E 0 Σ (ψ u (y)) = E u ⊕ d ⊕ E(y ⊕ E(0)) Θ (ψ u (y)) = E u ⊕ d ⊕ E(y ⊕ E(0)) ⊕ E y ⊕ E(0) ⊕ E 0
In particular, we observe

From this observation, we construct a birthday attack against 1kf9. We build two lists:

L 0 = MAC(φ 0 (x)) : x < 2 n/2 L 1 = MAC(ψ 0 (y)) : y < 2 n/2 , and we look for a match between the lists. We expect on average one pair to match randomly, and one pair to match because of [START_REF] Datta | Building single-key beyond birthday bound message authentication code[END_REF]. Moreover, when we have a collision candidate L 0 [x], L 1 [y], we can verify whether it is a right pair by comparing MAC(x 1) and MAC(y d ⊕ 1). Therefore, we find a pair satisfying R(X, Y ) with complexity 2 n/2 , and this leads to simple forgeries using [START_REF] Datta | Building single-key beyond birthday bound message authentication code[END_REF]. This contradicts the security proof of 1kf9 given in [START_REF] Datta | Building single-key beyond birthday bound message authentication code[END_REF]. Note that this attack is still valid if we use different multiplications for the two branches in the finalization function.

Attacking 1kPMAC+

The 1kPMAC+ mode uses the fix function for domain separation to build a singlekey variant of PMAC+, as shown in Figure 8. Attack. Since the fix functions used in the finalization have collisions, we can build a variant of the attacks from Section 4 using differences in Σ and/or Θ that are absorbed by the fix functions. More precisely, we use the following relation R on quadruple of messages: R(X, Y, Z, T ) :=

         Σ (X) = Σ(Y ) ⊕ 1 Θ (Y ) = Θ(Z) ⊕ 1 Σ (Z) = Σ(T ) ⊕ 1 Θ (T ) = Θ(X) ⊕ 1 ⇒ MAC(X) ⊕ MAC(Y ) ⊕ MAC(Z) ⊕ MAC(T ) = 0.
We can find quadruple of messages satisfying R using a single message injection function:

φ u (i) = u i X = φ u (x) = u x Y = ψ u (y) = u y Z = φ u (z) = u z T = ψ u (t) = u t Indeed we have MAC(φ u (i)) = E fix0 Ẽ1 (u) ⊕ Ẽ2 (x) Σ u (i) ⊕ E fix1 4 Ẽ1 (u) ⊕ 2 Ẽ2 (x) Θ u (i)
We observe that: R(x, y, z, t) ⇔

         Ẽ2 (x) = Ẽ2 (y) ⊕ 1 Ẽ2 (z) = Ẽ2 (t) ⊕ 1 2 Ẽ2 (x) = 2 Ẽ2 (z) ⊕ 1 2 Ẽ2 (y) = 2 Ẽ2 (t) ⊕ 1 ⇔      Ẽ2 (x) ⊕ Ẽ2 (y) ⊕ Ẽ2 (z) ⊕ Ẽ2 (t) = 0 Ẽ2 (x) = Ẽ2 (y) ⊕ 1 Ẽ2 (x) = Ẽ2 (z) ⊕ d
Therefore, R defines a 3n-bit relation that is independent of the value u. This can be used for attacks in the same way as in the previous sections, using a single list L = MAC(φ 0 (x)) MAC(φ 1 (x)) MAC(φ 2 (x)) : x < 2 3n/4

We can find a quadruple of four distinct values (x, y, z, t) such that L[x] ⊕ L[y] ⊕ L[z] ⊕ L[t] = 0 with Õ(2 3n/2 ) operations, using a memory of size O(2 3n/4 ), and this easily leads to forgeries.

Conclusion

In this paper we have introduced a cryptanalysis technique to attack doubleblock-hash MACs using quadruples of messages. We show three variants of the technique, with with O(2 3n/4 ) queries against SUM-ECBC, GCM-SIV2, PMAC+, LightMAC+, 1kPMAC+ and 3kf9. All these modes have a security proof up to 2 2n/3 queries, but no attacks with fewer than 2 n queries were known before our work.

Our main attacks are in the information theoretic model, and an attacker would need more than 2 n operations to perform a forgery. On the other hand, we also have a variant of the attack against SUM-ECBC and GCM-SIV2 with time complexity Õ(2 6n/7 ). This opens the path for attack with total complexity below 2 n for other double-block-hash MACs.

We believe that studying generic attacks is important in order to understand the security of these MACs, and is needed in addition to security proofs. In particular our results show that they do not reach full security, and we invalidate a recent proof for LightMAC+. However, there is still a gap between the 2 2n/3 bound of the proofs, and our attacks with O(2 3n/4 ) queries. Further work is needed to determine whether the attacks can be improved, or whether better proofs are possible.

Fig. 1 .

 1 Fig. 1. Generalized Birthday algorithm to find good quadruples.

Fig. 2 .

 2 Fig. 2. Diagram for SUM-ECBC with a -block message.

Fig. 3 .

 3 Fig.3. Diagram for authentication in GCM-SIV2 using GHASH with a -block message, a nonce N , hash keys H1 and H2.

Fig. 4 .

 4 Fig. 4. Diagram for PMAC+ with a -block message where ∆0 = E1(0) and ∆1 = E1(1).

Fig. 5 .

 5 Fig. 5. Diagram for LightMAC+ with (n -z)-bit blocks of a -block message where (v)z is the value v written over z bits.

Fig. 6 .

 6 Fig. 6. Diagram for 3kf9 with a -block message.

Finally, we showFig. 7 .

 7 Fig. 7. Diagram for 1kf9 with a -block message.

E

  (x ⊕ E(0)) ⊕ E(y ⊕ E(0)) = d ⇔ Σ (φ u (x)) = Σ (ψ u (y)) ⇒ Θ (φ u (x)) ⊕ Θ (ψ u (y)) = d ⇒ MAC(φ u (x)) = MAC(ψ u (y)).

ΣFig. 8 .

 8 Fig. 8. Diagram for 1kPMAC+ with a -block message where ∆1 = E(1) and ∆2 = E(2).

  and t = y ⊕ α 3 |α 2 |0|0, but there are four corresponding quadruples: (x, y, z, t), (z, y, x, t), (x, t, z, y), (z, t, x, y), and two candidate values for E 1 (0) ⊕ E 1 (1): x ⊕ y and x ⊕ y ⊕ α 3 |α 2 |0|0.

The algorithm and the figure given in[START_REF] Yasuda | A new variant of PMAC: Beyond the birthday bound[END_REF] differ in the coefficients used to compute Θ. We use the algorithmic description because it matches later PMAC+ variants, but the attack can easily be adapted to the other case.

We can actually reduce the polynomial factors by fixing only (nlog 2 (n))/4 bits to zero, in order to have sets of size[START_REF] Bellare | The security of the cipher block chaining message authentication code[END_REF] √ n • 2 3n/4 .

We construct the kernel of the linear function λi → i λi(xi ⊕ yi)

Acknowledgement

Mridul Nandi is supported by R.C.Bose Centre for Cryptology and Security. Part of this work was supported by the French DGA.

A SageMath Implementation

In order to verify that the algorithm is correct, we have implemented the attack against SUM-ECBC with complexity Õ(2 6n/7 ) given in Section 3.1 with SageMath: xor␣␣=␣lambda␣x,␣y:␣x.__xor__(y) txor␣=␣lambda␣a,b:␣tuple(xor(u,v)␣for␣u,v␣in␣zip(a,b)␣) def␣random_perm(n): ␣␣pp␣=␣Permutations(n).random_element() ␣␣return␣lambda␣x:␣pp(x+1)-1 def␣CBC(E,M): ␣␣x␣=␣0 ␣␣for␣m␣in␣M: ␣␣␣␣x␣=␣E(x.__xor__(m)) ␣␣return␣x def␣SUMECBC(E1,E2,E3,E4,M): ␣␣a␣=␣E2(CBC(E1,M)) ␣␣b␣=␣E4(CBC(E3,M)) ␣␣return␣a.__xor__(b) E1,␣E2,␣E3,␣E4␣=␣(random_perm(2^21)␣for␣_␣in␣range(4)) MAC␣=␣lambda␣x:␣SUMECBC(E1,E2,E3,E4,x) print␣"Values␣to␣recover␣␣␣␣␣␣␣|␣{0:06x}␣{1:06x}".format( ␣␣xor(E1(0),E1(1)),␣xor(E3(0),E3(1))) print␣"Generating␣data..." L1,L2,L3,L4␣=␣[],␣[],␣[],␣[] for␣i␣in␣range(2^12): ␣␣if␣(i&0b000000000111␣==␣0):␣L1.append(i) ␣␣if␣(i&0b000000111000␣==␣0):␣L2.append(i) ␣␣if␣(i&0b000111000000␣==␣0):␣L3.append(i) ␣␣if␣(i&0b111000000000␣==␣0):␣L4.append(i) def␣macs(u,i): ␣␣x␣=␣(0,0) ␣␣for␣j␣in␣range(i,2^21,2^12): ␣␣␣␣x␣=␣txor (x,(MAC([u,j]),␣MAC([u,␣xor(1,j

]),␣xor(L13[i][1],L24[j][2])) ␣␣␣␣if␣L13[i]␣<␣L24[j]: ␣␣␣␣␣␣i+=1 ␣␣␣␣else: ␣␣␣␣␣␣j+=1 ␣␣elif␣L13[i][0]␣<␣L24[j][0]: ␣␣␣␣i+=1 ␣␣else: ␣␣␣␣j+=1


Lucas Nussbaum

Experiment data management

Motivations

Lucas Nussbaum Experiment data management

Status

Data Management Plan:

Testbed X does not produce data itself (not a telescope). User experiments do, they should be the ones with a DMP.


Director -Frédéric Desprez

Fd

Christian Ln

Adrien Perez

Laurent Lebre

David Lefevre

Margery

Lucas Nussbaum

Organization and governance

Landscape -cloud & experimentation

1 Public cloud infrastructures (AWS, Azure, Google Cloud Platform, etc.) No information/guarantees on placement, multi-tenancy, real performance Private clouds: Shared observable infrastructures Monitoring & measurement No control over infrastructure settings Ability to understand experiment results Bare-metal as a service, fully reconfigurable infrastructure (Grid'5000) Control/alter all layers (virtualization technology, OS, networking) In vitro Cloud 1 Inspired from a slide by Kate Keahey

  organization of simulation and data analysis phases Simulate on a cluster; move data; post-mortem analysis Unsuitable for Exascale (data volume, time) Solution: analyze on nodes, during simulation Between or during simulation phases? dedicated core? node? Grid'5000 used for development and test, because control: Of the software environment (MPI stacks) Of CPU performance settings (Hyperthreading) Of networking settings (Infiniband QoS) Then evaluation at a larger scale on the Froggy supercomputer (CIMENT center, Grenoble) a distributed IaaS cloud, based on OpenStack Move services as close as possible to users Legal reasons, network latency Leverage regional data centers Increase resillience (no SPOF) P2P and self-* approaches Grid'5000 as a testbed already provides: http://beyondtheclouds.github.io/

Matthieu Dreher and Bruno Raffin. "A Flexible Framework for Asynchronous in Situ and in Transit Analytics for Scientific Simulations". In: CCGrid. 2014. Lucas Nussbaum Grid'5000

Lucas Nussbaum Grid'5000

Houssem Chihoub and Christine Collet. "A scalability comparison study of smart meter data management approaches". In: Grid'5000 Winter School. 2016. Lucas Nussbaum Grid'5000

tests, 1055 configurations Still, does not cover everything please report problems! Lucas Nussbaum Grid'5000

Public cloud infrastructures (AWS, Azure, Google Cloud Platform, etc.) No information/guarantees on placement, multi-tenancy, real performance

Other random stuff

Additional switch on the grisou cluster 48 nodes with 4x 10G interfaces and 1x 1G interface 1G interfaces are connected to an ONIE-supported switch VPN to connect to Grid'5000 sudo-g5k

OAR job extensions (oarwalltime command)

Persistent virtual machines

News on the website (also: Twitter @grid5000, RSS)