Louiza Khati

Damien Vergnaud

Analysis and Improvement of an Authentication Scheme in Incremental Cryptography

Introduced in cryptography by Bellare, Goldreich and Goldwasser in 1994, incrementality is an attractive feature that enables to update efficiently a cryptographic output like a ciphertext, a signature or an authentication tag after modifying the corresponding input. This property is very valuable in large scale systems where gigabytes of data are continuously processed (e.g. in cloud storage). Adding cryptographic operations on such systems can decrease dramatically their performance and incrementality is an interesting solution to have security at a reduced cost. We focus on the so-called XOR-scheme, the first incremental authentication construction proposed by Bellare, Goldreich and Goldwasser, and the only strongly incremental scheme (i.e. incremental regarding insert and delete update operations at any position in a document). Surprisingly, we found a simple attack on this construction that breaks the basic security claimed by the authors in 1994 with only one authentication query (not necessarily chosen). Our analysis gives different ways to fix the scheme; some of these patches are discussed in this paper and we provide a security proof for one of them.

Introduction

Bellare, Goldreich and Goldwasser initiate the study on incremental cryptography in [START_REF] Bellare | Incremental cryptography: The case of hashing and signing[END_REF] and then refined it in [START_REF] Bellare | Incremental cryptography and application to virus protection[END_REF]. Cryptographic incremental constructions are meant to provide efficient updates compared to classical algorithms. Usually, the result of a cryptographic algorithm (such as encryption or authentication) over a document has to be re-computed entirely if any change is applied to the document (and this regardless of the modification size). Incremental cryptography enables to update a signature, a message authentication code (MAC) or a ciphertext in time proportional to the number of modifications applied to the corresponding document. This attractive feature leads to build many incremental cryptographic primitives such as encryption schemes [START_REF] Bellare | Incremental cryptography and application to virus protection[END_REF][START_REF] Atighehchi | Towards fully incremental cryptographic schemes[END_REF][START_REF] Atighehchi | Space-efficient, byte-wise incremental and perfectly private encryption schemes[END_REF], signature [START_REF] Bellare | Incremental cryptography: The case of hashing and signing[END_REF][START_REF] Fischlin | Lower bounds for the signature size of incremental schemes[END_REF][START_REF] Mironov | Incremental deterministic publickey encryption[END_REF], MACs [START_REF] Bellare | Incremental cryptography and application to virus protection[END_REF][START_REF] Fischlin | Lower bounds for the signature size of incremental schemes[END_REF][START_REF] Micciancio | Oblivious data structures: Applications to cryptography[END_REF], hash functions [START_REF] Goi | Incremental hash function based on pair chaining & modular arithmetic combining[END_REF][START_REF] Bellare | A new paradigm for collision-free hashing: Incrementality at reduced cost[END_REF] and authenticated encryption constructions [START_REF] Buonanno | Incremental unforgeable encryption[END_REF][START_REF] Atighehchi | Towards fully incremental cryptographic schemes[END_REF][START_REF] Sasaki | A new mode of operation for incremental authenticated encryption with associated data[END_REF]].

An algorithm is incremental regarding specific update operations such as inserting, deleting or replacing a data block inside a document. A desirable incremental algorithm should support all these operations for any positions: it should be possible to insert, delete or replace a data block of the document for all positions without breaking the security of the cryptographic algorithm. Most known algorithms only support replacement of data blocks and the algorithms that support insertion, deletion and replacement1 are deemed strongly incremental.

Virus protection is the first application of incremental cryptography quoted in the seminal paper [START_REF] Bellare | Incremental cryptography: The case of hashing and signing[END_REF]. They consider the usage scenario where processor accesses files on a remote host and a virus can alter these files. A simple idea is to compute authentication tags for all files with a key stored securely by the processor and any modification by a virus will be detected by verifying the corresponding tag. Knowing that these files will be updated often enough, using an incremental authentication algorithm preserves the processor by performing a lighter computation.

Bellare et al. also introduced in [START_REF] Bellare | Incremental cryptography: The case of hashing and signing[END_REF] the corresponding security notions. In the basic security model, the adversary can obtain a valid authentication tag for any message it wanted (as in classical MAC security) and it can also update (with the supported update operations) valid pairs message/tag. This is a first security level but it is reasonable to consider a stronger adversary that can alter files and tags before applying update operations; it corresponds to the tamper-proof security notion introduced in [START_REF] Bellare | Incremental cryptography: The case of hashing and signing[END_REF].

Nowadays this use case can be extended to the "digital world". Large amount of data [START_REF] Gantz | The digital universe in 2010 : Big data, bigger digital shadows, and biggest growth in the far east[END_REF][START_REF] Mihajloska | Reviving the idea of incremental cryptography for the zettabyte era use case: Incremental hash functions based on SHA-3[END_REF] are processed every day by different services like cloud services, distributed networks and distributed storage. It is clear that all these data require integrity and/or privacy at a low computational cost otherwise going through gigabytes of data for minor changes without incremental primitives is really demanding in term of time and energy. A concrete example is the Cloud Bigtable by Google [START_REF]7th Symposium on Operating Systems Design and Implementation (OSDI '06)[END_REF] that stores petabytes of data across thousands of commodity servers. This Bigtable has a particular data structure that links a unique index number to each block. In this case an incremental hashing that supports replacement and insertion operations is suitable as mentioned in [START_REF] Mihajloska | Reviving the idea of incremental cryptography for the zettabyte era use case: Incremental hash functions based on SHA-3[END_REF]. A more critical usage is storage services in mobile cloud computing where a mobile client device is in addition limited in term of energy consumption. To solve this issue, Itani, Kayssi and Chehab provide an energy-efficient protocol in [START_REF] Itani | Energy-efficient incremental integrity for securing storage in mobile cloud computing[END_REF] that guarantee data integrity based on incremental MACs. Another use case is sensor networks and more specifically environmental sensors [START_REF] Hart | Environmental sensor networks: A revolution in the earth system science?[END_REF][START_REF] Mihajloska | Reviving the idea of incremental cryptography for the zettabyte era use case: Incremental hash functions based on SHA-3[END_REF]: several sensors are deployed at different physical positions and they record continuously data. At some point, all the data ends up in a big public database that has to be publicly checkable. The database is updated (insertion operation mainly) at a high frequency and if the hash value over all the database is entirely re-computed for each insertion it will be very consuming. All these use cases are examples among many others. Incremental cryptography is clearly an area to explore to solve practical issues.

For now incrementality is mainly investigated for hashing and signing even if it was also considered for encryption in [START_REF] Bellare | Incremental cryptography: The case of hashing and signing[END_REF][START_REF] Atighehchi | Towards fully incremental cryptographic schemes[END_REF]. It is not surprising regarding all the practical use cases that need incremental authenticated constructions. Recently, the CAESAR2 competition stimulates research on authenticated encryption algorithm. Sasaki and Yasuda analysed several candidates and found that none of them performs incrementality. That is why they designed their own authenticated encryption mode with associated data [START_REF] Sasaki | A new mode of operation for incremental authenticated encryption with associated data[END_REF] based on existing constructions. This new mode is incremental for the replace, insert and delete operations, but the insert and delete operations of this mode concern only the last block of the authenticated data or the last block of the message (and it remains open to design a strongly incremental authenticated encryption algorithm).

Actually, as far as we know, the only authentication scheme that is strongly incremental is the XOR-scheme designed by Bellare, Goldreich and Goldwasser in [START_REF] Bellare | Incremental cryptography and application to virus protection[END_REF] (cf. Figure 2). This strong property comes with a cost: only basic security is claimed in [START_REF] Bellare | Incremental cryptography: The case of hashing and signing[END_REF] and this algorithm needs to generate and store a lot of randomness. The MAC operation generates a random value for each data block and these random values are necessary for the verification and the update operations. The XOR-scheme is based on a pseudo-random function (PRF) and a pseudo-random permutation (PRP) and the incremental algorithms for (single block) insert and delete operations require only two applications of the underlying PRF and two applications of the underlying PRP. The XOR-scheme relies on the concept of pair block chaining (which was later used in [START_REF] Goi | Incremental hash function based on pair chaining & modular arithmetic combining[END_REF] which involves taking each pair of two consecutive blocks of a message and feeding them into a pseudo-random function before chaining all the outputs of the PRF into the final hash. This scheme extends another scheme, called the randomized XOR-scheme, from [START_REF] Bellare | XOR MACs: New methods for message authentication using finite pseudorandom functions[END_REF] which is incremental only for replacement. Even if they share a similar name, these two algorithms are different: the randomized XOR-scheme is not based on a pair block chaining structure and requires actually much less randomness. To distinguish the two schemes, in this paper, we will call this second scheme the unchained XOR-scheme.

An analysis on some incremental hash functions was provided by Phan and Wagner [START_REF] Phan | Security considerations for incremental hash functions based on pair block chaining[END_REF]. They give, inter alia, patterns that could give collisions on a hash function based on pair block chaining. Two cases are of interest for the XORscheme: non-distinct blocks and cycling chaining. The first one considers repeated blocks messages like A||B||C||B||A and B||C||B||A||B that would have the same sum value if no randomness was used (cf. Figure 2) but as underlined by the authors the random values appended to each message block prevents these repetitions. The second one considers a variant of the XOR-scheme [START_REF] Goi | Incremental hash function based on pair chaining & modular arithmetic combining[END_REF] where the first and the last block are chained then some repeated patters like A||B||A and B||A||B would have the same sum value but it not the case in the original version from [START_REF] Bellare | Incremental cryptography and application to virus protection[END_REF]. Therefore, in the present state-of-the-art, no attacks are known against the original strongly incremental XOR-scheme proposed in [START_REF] Bellare | Incremental cryptography and application to virus protection[END_REF].

Contributions of the Paper

In this paper, we analyse the security of the original XOR-scheme construction proposed by Bellare, Goldreich and Goldwasser in [START_REF] Bellare | Incremental cryptography and application to virus protection[END_REF] and based on a chained structure as defined in [START_REF] Bellare | Incremental cryptography: The case of hashing and signing[END_REF]. At tac k s . We provide an attack that breaks the XOR-scheme basic security claimed by the authors3 . It succeeds with probability 1 using only one MAC query. It takes advantage of the chaining structure of this scheme and some xor function properties. This attack is very simple and it is surprising that it remained unnoticed until now (especially since the paper [START_REF] Bellare | Incremental cryptography and application to virus protection[END_REF] appeared in a major computer science conference and was extensively quoted since 1994).

A n a ly s i s a n d Pat c h e d c o n s t ru c t i o n s . We analyse our attack and the original XOR-scheme to find where its security breaks down. We show that the main flaw is that the XOR-scheme does not explicitly take into account the document length and we noticed that adding the number of data block to the construction prevents this kind of attacks. We analyse different ways to patch the scheme by introducing the document block length in the construction and found that the scheme can still be weak for some options.

We propose a modified version of the XOR-scheme and prove its basic security. Our security proof for the patched XOR-scheme uses tool from the unchained XOR-scheme security proof [START_REF] Bellare | XOR MACs: New methods for message authentication using finite pseudorandom functions[END_REF].

O rg a n i z at i o n o f t h e Pa p e r . We introduce some mathematical backgrounds, recall the security models for incremental MAC constructions and we give a detailed description of the XOR-scheme construction in Section 2. Then we present a general forgery attack and its analysis in Section 3. In Section 4, we discuss different solutions to patch efficiently the scheme without making it more complicated neither breaking the structure of the algorithm. We choose one construction and give its detailed description. Its security proof is given in Section 5 before the conclusion in Section 6.

Preliminaries

Notations

For any integer n, {0, 1} n denotes the set of bit strings of length n and we let {0, 1} * denote the set of all finite-length bit strings. For two bit strings X and Y , X||Y denotes their concatenation. For a finite set S, we use x Given a non-empty subset K, a function family F k : K × {0, 1} → {0, 1} L , where k ∈ K, is a (t, )-pseudo-random function (PRF) if for any algorithm A running in a time at most t, the following holds:

|P r[k $ ← -K : A F k (.) = 1] -P r[F $ ← -F ,L : A F (.) = 1]| ≤ .
Given a non-empty subset K, a permutation family

P k : K × {0, 1} L → {0, 1} L ,
where k ∈ K, is a (t, )-pseudo-random permutation (PRP) if for any algorithm A running in a time at most t, the following holds:

|P r[k $ ← -K : A P k (.) = 1] -P r[F $ ← -F L,L : A F (.) = 1]| ≤ .

Definitions

S y n tac t i c D e f i n i t i o n .

We begin by describing the syntactic definition of strongly incremental MAC algorithms. In the following, we consider authentication of messages whose length is a multiple of an integer b (which is usually smaller than the block length of the underlying PRF or PRP) but is obviously possible to handle messages of arbitrary finite length using padding.

A document D ∈ D with D = ∞ i=1 {0, 1} ib is a sequence of n b-bit blocks, for some integer n ≥ 1 denoted D = (D 1 , D 2 , . . . , D n ) where D i is the i-th b-bit block of D. Definition 1. A strongly incremental MAC scheme is a 5-tuple Π = (K, MAC, V, I, D)
in which: K is the key space. A key k is randomly chosen in the key space K. The key k is a parameter for the MAC, V, I and D algorithms. MAC, the MAC algorithm, is a probabilistic algorithm that takes as input k and a document D and returns an authentication tag T . V, the verification algorithm, is a deterministic algorithm that takes as input a document D and a tag T and returns 1 if the tag is valid and 0 otherwise. I, the incremental insert algorithm, is a probabilistic algorithm that takes as input the insertion position j, the inserted block D i , the document D and a tag T to update. D, the incremental delete algorithm, is a probabilistic algorithm that takes as input the suppression block position j, the document D the message block to add D j and a tag T to update.

with the three following correctness properties:

-(∀k ∈ K)(∀n ∈ N)(∀D ∈ {0, 1} nb )(∀T ∈ {MAC(k, D)})({V(k, D , T )} = {1}) -(∀k ∈ K)(∀n ∈ N)(∀D = (D 1 , D 2 , . . . , D n ) ∈ {0, 1} nb )(∀T ∈ {MAC(k, D)}) (∀j ∈ {1, . . . , n + 1})(∀D * ∈ {0, 1} b )(∀T ∈ {I(j, D * , D, T )}) ({V(k, (D 1 , . . . , D j-1 , D * , D j , . . . D n ), T )} = {1}) -(∀k ∈ K)(∀n ∈ N)(∀D = (D 1 , D 2 , . . . , D n ) ∈ {0, 1} nb )(∀T ∈ {MAC(k, D)}) (∀j ∈ {1, . . . , n})(∀T ∈ {D(j, D, T )}) ({V(k, (D 1 , . . . , D j-1 , D j+1 , . . . D n ), T )} = {1})
R e m a r k . In practice, the incremental algorithms I and D have to be more efficient than re-computing an entire authentication tag T and cryptographers are looking for scheme where these algorithms are constant-time (i.e. independent of the number of b-bit blocks of the document D).

S e c u r i t y M o d e l .

The adversary A is an algorithm (i.e. an oracle probabilistic Turing machine) playing in a computational security game denoted G BS MAC,V,I,D (cf. Figure 1). A key k is picked uniformly at random in the key space of the strongly incremental MAC and the adversary has access to all the following oracles -a MAC oracle: the adversary can ask to compute a MAC (for k) on any document of its choice; -a verifying oracle: the adversary can ask to verify (for k) the validity of any pair document/authentication tag; -an update oracle: the adversary can use the incremental operations (for k) on chosen document/authentication tag pairs (in a way depending on the security models as defined below).

At the end of each oracle query (except verification queries), the corresponding authenticated document/authentication tag (D, r) is added to a list L and the adversary wins the game if it outputs eventually a pair (D , r ) / ∈ L that is accepted by the verification algorithm.

B a s i c S e c u r i t y . As defined in [START_REF] Bellare | Incremental cryptography: The case of hashing and signing[END_REF], in basic security settings the adversary A is not allowed to do incremental operations on a couple (D, T ) where the verification algorithm V(D, T ) will fail. It can only apply incremental operations on couples (D, T ) that belong to the list L. As mentioned above, to win the security game, A must provide a forgery that is to say a document D * and a tag T * such that V(D * , T * ) returns 1 and the couple (D * , T * ) is not in the list L.

Remark 1. The verification V(D, T ) is not applied before incremental operation to check authenticity otherwise the low computational cost is lost. It is simply assumed that A does not query incremental operations on altered couples. In this paper, we focus on this basic security notion only. Definition 2. Let Π = (K, MAC, V, I, D) be a strongly incremental MAC scheme and let A be an adversary. Let Adv BS A,Π :=

Pr[k $ ← -K; L ← {}; (D * , T * ) ← A MAC L k ,V L k ,I L k ,D L k : 1 ← V L k (D * , T * ) ∧ (D * , T * ) / ∈ L].
Π is (λ, q m , q v , q inc ; )-BS-secure in the basic sense if, for any adversary A which runs in time λ, making q m queries to the MAC oracle, q v to the V oracle and q inc valid queries to the incremental oracles (I, D) we have Adv BS A,Π < . Ta m p e r -P ro o f S e c u r i t y . As defined in [START_REF] Bellare | Incremental cryptography and application to virus protection[END_REF]tamper-proof security is a stronger security notion since the adversary A is allowed to query incremental operation on any couple (D, T ) even new couples (couples that do not belong to L). Then A wins the security game if it provides a new couple (D * , T * ) such that V(D * , T * ) returns 1. It was already mentioned in [START_REF] Bellare | Incremental cryptography and application to virus protection[END_REF], that the XOR-scheme does not achieve tamper-proof security and this is also the case of our modified XOR-scheme.

Game G BS MAC,V,I,D k $ ← -K L ← {} If A MAC L k ,V L k ,I L k ,D L k makes a query (D * , T * ) such that -V L k (D * , T * ) returns 1 and -(D * , T * ) / ∈ L Then Return 1 Else return 0.

Description of the XOR-scheme

The XOR-scheme (X S) as defined in [START_REF] Bellare | Incremental cryptography: The case of hashing and signing[END_REF] is an incremental authenticated algorithm based on pair-wise chaining as shown in Figure 2. Let and L be two positive integers and let b < be some positive integer. The X S scheme is based on a pseudo-random function F : K F × {0, 1} 2 -→ {0, 1} L and a pseudo-random permutation P : K P × {0, 1} L -→ {0, 1} L . The incremental algorithms for (single block) insert and delete operations require only two applications of the underlying PRF and two applications of the underlying PRP. The X S scheme generates an authentication tag for a document D by repeatedly applying the PRF to pairs of blocks -each made of a b-bit data block from the document D and an -b random block (pick uniformly at random and independently for each block). In the following, for simplicity, we consider only documents whose binary length is a multiple of b and we denote D = ({0, 1} b ) * .

• The key space X S.K is K F × K P the Cartesian product of the key space of the underlying PRF F and PRP P . • The MAC algorithm X S.MAC takes as input a document D ∈ D and outputs a tag T := (r, τ ). For each document block D i , an ( -b)-bits block r i is randomly generated. The concatenation of these values is denoted It takes as inputs the position j where the block value has to be inserted, the previous block value D j-1 4 , the block value D j5 , the new block value D j and the tag T . It outputs the new tag.

F k 1 F k 1 F k 1 F k 1 F k 1 P k 2
R i := D i ||r i . Each couple (R i-1 , R i ) is
• The Delete operation X S.D enables to delete a block from the document.

It takes as inputs the position j where the block as to be deleted, the block value to delete D j , the previous and next block values D j-1 and D j+1 and the tag T .

The update algorithms are intuitive and given in Fig. 8 (in Appendix) for update operations at a position different from the first block position. They can be adapted to be applied to the first block. In the original version, it is specified that a prefix and postfix are added to the document. For a document D = D 1 . . . D n , the authentication tag is computed on D 0 ||D 1 . . . D n ||D n+1 where D 0 and D n+1 are specific prefix and postfix values. In this paper, this specification is not taken into account: it does not prevent our attack and the repaired scheme is proven secure without it. XO R -s c h e m e l i m i t s . Supporting insert, delete and consequently replace operations should make the XOR-scheme very efficient in term of update time running. The fresh random values r i generated by this scheme for each new document block are necessary for security. But generating so much randomness is time consuming: for an n-block document D, a n( -b)-random bits value r is generated. Random generation also slows down the insertion operation. Another drawback is the tag expansion: the random value r is part of the tag and needs to be stored. For a n block document, random storage costs n( -b) bits. Even if today storage is not an issue, having short tags is desirable.

3 Forgery Attacks against the XOR-scheme According to the basic security game described in Fig. 1, the adversary A wins the game if it finds a new pair (D * , T * ) such that the verification operation returns 1. If an adversary has access to any tag T (such that T = (r, τ )) returned by the MAC algorithm on a document D (for example D 0 ||D 1 ||D 2 ), it can forge a different document D * having the same value τ . The value τ is computed as follows:

τ = P k2 [F k1 (D 0 ||r 0 , D 1 ||r 1 ) ⊕ F k1 (D 1 ||r 1 , D 2 ||r 2 )] (1)
Σ = F k1 (R 0 , R 1 ) ⊕ F k1 (R 1 , R 2 ) = h 1 ⊕ h 2 (2)
A can build a document D * = D and a value r * such that the corresponding Σ * value collides with Σ even if there is no weakness on F . A way to do so is inserting a specific block chain in document D in order to cancel all the new values h i introduced by these repetitions as shown in Figure 3. It seems that the chaining structure of the XOR-scheme should prevent this behavior because changing or inserting a block value will affect two values h i then the tag τ will be different. These modifications have to be compensated: the values h i introduced has to be canceled by xoring the same value and all the original values h i that are deleted has to be re-introduced. We use this trick to break the claimed basic security.

(R0, R1) (., .) (., .) (R1, R2) ↓ ↓ ↓ ↓ h1 ⊕ . . . ⊕ . . . ⊕ h2 = Σ = 0
(D 1 ||r 1 , D 2 ||r 2 ) (R 0 , R 1 ) (R 1 , R 2 ) (R 2 , R 1 ) (R 1 , R 2 ) (R 2 , R 1 ) (R 1 , R 2 ) ↓ ↓ ↓ ↓ ↓ ↓ h 1 ⊕ h 2 ⊕ h 2 ⊕ & & h 2 ⊕ h 2 ⊕ & & h 2 = Σ
Fig. 5. Attack on the XOR-scheme

The document D * is different from D but it has the same value τ . The document D * given in Figure 5 is an example of a forgery and many other examples can be given. To be more general, for any x ∈ {0, 1} b , any x ∈ {0, 1} ( -b) and for any valid pair (D, T ) such that D = D 0 . . . D i ||D i+1 . . . D n , many forgeries (D * , (r * , τ )) can be built by inserting the specific block chain D i ||x||D i ||x in D (and the corresponding random value chain r i ||x ||r i ||x in r for any x ) such that:

D * = D 0 . . . D i-1 || D i ||x||D i ||x||D i ||D i+1 . . . D n r * = r 0 . . . r i-1 || r i ||x ||r i ||x ||r i || r i+1 . . . r n .
A variant of this forgery is to insert only a repeated document block D i (and r i ) is the following:

D * = D 0 . . . D i-1 || D i ||D i ||D i ||D i+1 . . . D n . r * = r 0 . . . r i-1 || r i ||r i ||r i || r i+1 . . . r n .
A more powerful forgery can be built from (D, T ) by inserting any values x and y in D (and any values x and y in r ) such that:

D * = D 0 . . . D i-1 || D i ||x||y||x||y||x||D i ||x||D i ||D i+1 . . . D n . r * = r 0 . . . r i-1 || r i ||x ||y ||x ||y ||x r i ||x ||r i || r i+1 . . . r n .
For all these attacks, the underbraced chains can be repeated many times. These three attacks are some of the possible attacks, following this canceling strategy, some exotic chains can be inserted in order to ends with a value τ that corresponds to a legitimate tag. A first observation is that all these attacks are performed by inserting blocks and providing a forgery D * that has the same length that the original one looks impossible or at least harder.

Modification of the XOR-scheme

The previous section described an attack that breaks the basic security of the XOR-scheme by producing a document D * using a MAC query (D, T ) where τ = τ * and |D| b = |D * | b . All the forgeries D * produced are longer that the original document D. One can notice that if the adversary A is only allowed to MAC and verify documents that have the same length n then the attack presented in Section 3 will fail. A first naive idea is to force all documents to have the same length (documents that are too small can be padded in the MAC algorithm) but this solution is not realistic and the incremental property will be lost. A natural way to fix this flaw is to use the document length n for the computation of the value τ in order to make it size dependent. The size can be expressed according to any units: number of bits, bytes, blocks. Choosing the number of blocks n is sufficient. A postfix block containing the number of blocks n can be added at the end of the document then the computation of the value Σ will become: The last block works as a mask for each value τ : incremental operation will refresh the last random value r n in order to have a different mask value for any modification. As a consequence, the pseudo-random permutation P is not necessary anymore (τ = Σ), it is removed in the modified scheme (Figure 6). This version of the XOR-scheme is proven in Section 5.

Σ = F k1 (D 0 ||r 0 , D 1 ||r 1 ) ⊕ F k1 (D 1 ||r 1 , D 2 ||r 2 ) ⊕ • • • ⊕ F k1 (D n-1 ||r n-1 , r n ||n) F k 1 F k 1 F k 1 F k 1 F k 2 τ n D0 D1 D2 D3
The last random block value r n (concatenated with the document length n) is necessary otherwise the corresponding h n value can be canceled. The following attack is an example: The couple (D * , r * ) is a forge: it is not in the list L of tagged document and it has a valid tag. To avoid such attacks, for incremental operations the last random block (concatenated with the document length) need to be always refreshed. To be sure that none of the previous attack will not be practical, an independent key is used to process the last couple (R n-1 , R n ). That way, it would be hard for an adversary to make a forgery from a linear combination of tagged documents.

C o m p l e x i t y . The modified XOR-scheme is slightly slower than the original one. For the MAC and the incremental algorithms the P call is removed but a call to the function F k2 is added as shown in Figure 7. The delete D and insert I operations are slightly slower because of the last block update: the last value R i depending on the document length has to be removed and the a new value R i with the new document length n is added.

Functions scheme ( -b)-bits Generation F P xor MAC XS n n -1 1 n -1 M-XS n + 1 (n -1) + 1 0 n V XS 0 n -1 1 n -1 M-XS 0 (n -1) + 1 0 n D XS 0 3 2 3 M-XS 1 5 0 5 I XS 1 3 2 3 M-XS 2 5 0 5
Fig. 7. Complexity: XOR-scheme (XS) and Modified XOR-scheme (M-XS)

O t h e r S o l u t i o n s . In the original XOR-scheme (Fig. 2), the document length can be added differently in the algorithm (but still with a random value r n ):

1 Before the last operation P k2 (Σ), an intermediate operation F k3 (r n ||n, Σ) can be added such that

τ = P k2 [F k3 (r n ||n, Σ)]. 2
The block length can be processed individually as a last block such that

τ = P k2 [F k3 (r n ||n) ⊕ Σ].

Security Proof

The security proof follows the proof strategy used in [START_REF] Bellare | XOR MACs: New methods for message authentication using finite pseudorandom functions[END_REF] for proving the unchained XOR-scheme.

I n f o r m at i o n t h e o r e t i c c a s e .

As in [START_REF] Bellare | XOR MACs: New methods for message authentication using finite pseudorandom functions[END_REF], we first consider the case where the two underlying PRFs F k1 and F k2 are replaced by two truly random functions F 1 and F 2 from {0, 1} 2 to {0, 1} L . We consider an unbounded adversary and the following theorem claims the security of this modified scheme in the information theoretic case. More precisely, it provides an absolute bound on the success of the adversary in terms of the number of oracle queries it makes.

Theorem 1. Let F 2 ,L be the family of random functions with input length 2 and output length L. Let A be any (computationally unbounded) adversary, in the basic security settings, making a (q m , q v , q inc )-attack against the modified XOR-scheme with two functions picked uniformly at random from F 2 ,L . The probability that A is successful is at most

q 2 • 2 b-+ q v • (t 2 • 2 b-+ •2 -L ).
where q = q m + q inc and t denotes the maximal block-length of the documents authenticated in the security game.

R e m a r k . The modified XOR-Scheme is not tamper-proof secure.

Proof (Theorem 1 (Sketch.)). The proof follows closely the proof from [START_REF] Bellare | XOR MACs: New methods for message authentication using finite pseudorandom functions[END_REF]. The main difference is that we use two different random functions in the modified scheme and that we need the following simple lemma to prove that some specific matrix (close to the one used in [START_REF] Bellare | XOR MACs: New methods for message authentication using finite pseudorandom functions[END_REF]) is full-rank. For the reader familiar with [START_REF] Bellare | XOR MACs: New methods for message authentication using finite pseudorandom functions[END_REF], we use similar notations in the following.

Lemma 1. Let X be some finite set and let n ∈ N.

Let (R 0 , R 1 , . . . , R n ) ∈ X n+1 with R i = R j for all i = j then if there exists (R * 0 , R * 1 , . . . , R * n ) ∈ X n+1 such that {(R 0 , R 1 ), (R 1 , R 2 ), . . . (R n-1 , R n )} = {(R * 0 , R * 1 ), (R * 1 , R * 2 ), . . . (R * n-1 , R * n )} then for all i ∈ {0, . . . , n}, R i = R * i .
Proof (Lemma 1). This lemma can be easily proved by induction over n. Let us denote S n the first set

{(R 0 , R 1 ), (R 1 , R 2 ), . . . (R n-1 , R n )}
where all R i are distinct. In particular, the set S n contains exactly n different couples. One can notice that the first member of each couple is the second member of the previous couple except the first and the last couples. In others words a value R i appears in two couples: once as a first member and once as a second member except the first one R 0 and the last one R n .

The case n = 1 is trivial. We consider the case n = 2 that provides greater clarity. Let assume that it exists (R *

0 , R * 1 , R * 2 ) ∈ X 3 such that {(R 0 , R 1 ), (R 1 , R 2 )} = {(R * 0 , R * 1 ), (R * 1 , R * 2 )} and #{R 0 , R 1 , R 2 } = 3.
As there are exactly two couples in each set, we have the following two cases:

-case 1: (R 0 , R 1 ) = (R * 0 , R * 1 ) and (R 1 , R 2 ) = (R * 1 , R * 2 ) then in this case, we get R 0 = R * 0 , R 1 = R * 1 , R 2 = R * 2 ; -case 2: (R 0 , R 1 ) = (R * 1 , R * 2 ) and (R 1 , R 2 ) = (R * 0 , R * 1 )
. The first equality implies R * 1 = R 0 and the second equality implies R * 1 = R 2 and thus R 0 = R 2 which contradicts the statement R 0 = R 2 .

Suppose now that Lemma 1 holds for all integers k ≤ n -1 for some n ∈ N * . We will show that it holds for n.

Let us suppose that there exists (R *

0 , R * 1 , . . . , R * n ) ∈ X n+1 such that S n = S * n where S * n is the set {(R * 0 , R * 1 ), (R * 1 , R * 2 ), . . . (R * n-1 , R * n )}.
Again, as all the values R i are different in S n then the n couples are different. The equality of these two sets S n and S * n implies that they contain exactly the same n couples and that in each set a couple appears only once. We have the following two cases:

-case 1: (R n-1 , R n ) = (R * n-1 , R * n ) and S n-1 = S * n-1 . From the induction hypothesis, for all i ∈ {0, . . . , n -1}, R i = R * i . -case 2: (R n-1 , R n ) = (R * n-1 , R * n ) Then there exists i ∈ {0, . . . , n -1} such that (R n-1 , R n ) = (R * i-1 , R * i ). It implies R * i =
R n and according to the structure of these sets, there is a couple in S * n that has a first member equal to R * i = R n ) and it has to be the case in S n . But as mentioned above, R n is a value that appears only in one couple of S n and we get a contradiction.

We will use this lemma with X = {0, 1} at the end of the proof to show that different messages of the same block-length involve different input pairs for the underlying PRF F 1 .

Since the adversary A is computationally unbounded we may assume without loss of generality that it is deterministic. The probabilistic choices in A's attack on the scheme are thus the initial choice of F 1 and F 2 of the random functions in F 2 ,L and the choices of random coins made by the authentication oracles in the security game. We assume (again without loss of generality) that A makes exactly q = q s + q inc authentication queries (either as a direct MAC query or as an update query using the insert or the delete oracle). As in [START_REF] Bellare | XOR MACs: New methods for message authentication using finite pseudorandom functions[END_REF], there is no loss of generality to assume that A makes all its authentication queries and then makes exactly one verify query (for its purported forgery). We prove that in this case the probability of the event (denoted Succ) A's forgery is valid is upper-bounded by

q 2 • 2 b-+ t 2 • 2 b-+ 2 -L .
and using a classical argument (see e.g. [START_REF] Bellare | XOR MACs: New methods for message authentication using finite pseudorandom functions[END_REF]) we get the claimed bound for general adversaries.

We consider the simple case where all the random coins used in the last block of each authenticated document are different. Note that in all authentication queries (from a fresh MAC query or an update query), this random block is picked uniformly at random and independently of the previous blocks. To analyze the probability of this event (denoted Distinct), we can therefore use the following simple lemma: Lemma 2 ([5, Fact A.1]). Let P (m, t) denote the probability of at least one collision in the experiment of throwing t balls, independently at random, into m buckets. Then P (m, t) ≤ t 2 /m.

We thus have Pr

[Succ] = Pr[Succ|Distinct] • Pr[Distinct] + Pr[Succ|Distinct] • Pr[Distinct] ≤ Pr[Succ|Distinct] + Pr[Distinct] ≤ Pr[Succ|Distinct] + P (2 b-, q) ≤ Pr[Succ|Distinct] + q 2 • 2 b-.
and it remains to upper-bound Pr [Succ|Distinct].

Let us fix a particular sequence of q documents D 1 , . . . , D q (each made of at most t blocks of b bits) corresponding to all documents authenticated in the security game by some authentication queries (either as a direct MAC query or as an update query using the insert or the delete oracle). We also fix r 1 , . . . , r q some bit-strings possibly used as random values in the modified XOR-scheme for these documents (i.e. r i consists in 1 ≤ t i ≤ t blocks of -b bits if D i is made of t i blocks of b bits) and we assume that the last blocks of all of them are all different. Finally we fix τ 1 , . . . , τ q some possible corresponding tags in {0, 1} L for these documents. We consider only bit-strings (D 1 , . . . , D q ), (r 1 , . . . , r q ) and (τ 1 , . . . , τ q ) for which the probability that there exists two functions F 1 and F 2 such that T i = (r i , τ i ) is a valid MAC for D i (for all i ∈ {1, . . . , q}) for F 1 and F 2 is non-zero.

We will compute the probability of the event that A's forgery is valid conditioned on the event that the authentication queries made by A are on the documents D 1 , . . . , D q , use the random coins (r 1 , . . . , r q ) and result in the tags (τ 1 , . . . , τ q ). More precisely, we will show that this probability is upper-bounded by t 2 •2 b-+2 -L (and since the bit-strings (D 1 , . . . , D q ), (r 1 , . . . , r q ) and (τ 1 , . . . , τ q ) are arbitrary, we will get the result by standard conditioning arguments).

We consider a possible forgery output by A and we denote D q+1 the corresponding document, r q+1 the used randomness and τ q+1 the tag. It is worth noting that the pair (D q+1 , r q+1 ) is different from all pairs (D i , r i ) for all i ∈ {1, . . . , q} (since otherwise, this is not an actual forgery) but we cannot assume that the last block of r q+1 is different from the last blocks of all previous random values r i for all i ∈ {1, . . . , q} (since A may choose it arbitrarily and it can reuse a value obtained in a previous authentication query).

For i ∈ {1, . . . , q + 1}, we denote D i j for all j ∈ {1, . . . , t i }, the j-th block of the document D i and similarly r i j for all j ∈ {1, . . . , t i + 1}, the j-th block of the randomness r i . As in [START_REF] Bellare | XOR MACs: New methods for message authentication using finite pseudorandom functions[END_REF], we consider the matrix B with q + 1 rows and 2 2 +1 columns over F 2 = {0, 1} where the entry in row i ∈ {1, . . . , q + 1} and column j ∈ {1, . . . , 2 2 +1 } is defined as follows:

for j ∈ {1, . . . , 2 2 }, the entry is equal to 1 if j is the index of the 2 -bit string (D i ti ||r i ti ||t i ||r i ti+1 ) in lexicographic order (and 0 otherwise).

for j ∈ {2 2 + 1, . . . , 2 2 +1 }, the entry is equal to 1 if j -2 2 is the index of the 2 -bit string (D i k ||r i k ||D i k+1 ||r i k+1 ) in lexicographic order for some k ∈ {1, . . . , t i -1} (and 0 otherwise).

In other words, the matrix B contains a 1 on the row i for i ∈ {1, . . . , q + 1} only at positions corresponding to bit-strings of length 2 used as inputs to the random functions F 1 and F 2 in the modified XOR-scheme (where the left part consisting of the first 2 2 columns of the matrix corresponds to the unique input of F 2 and the right part corresponds to all inputs to F 1 ).

We have the following lemma:

Lemma 3. The matrix B has full rank with probability at least 1 -t 2 • 2 b-.

Proof (Lemma 3). The proof is similar to the proof of [START_REF] Bellare | XOR MACs: New methods for message authentication using finite pseudorandom functions[END_REF]Lemma A.3]. If the pair (t q+1 , r q+1 tq+1+1 ) is different from all (t i , r i ti+1 ) for i ∈ {1, . . . , q}, then the matrix B is in echelon form (in its left part) and is thus trivially of full rank.

Otherwise, we assume that r q+1 tq+1+1 is equal to some r i ti+1 and if t q+1 = t i (the last block of randomness of A's forgery is equal to the last block of randomness of the i-th authenticated message and the block-length of these two messages are equal). It is worth noting that there exists only one index i ∈ {1, . . . , q} such that this is the case (since we assume that these last blocks of randomness are all different). For this i-th document, the random blocks r i j for j ∈ {1, . . . , t i } are all different with probability at least 1 -

t 2 i • 2 b-≥ 1 -t 2 • 2 b-by Lemma 2.
Since the pair (D q+1 , r q+1 ) is different from (D i , r i ) and since the pairs (D i k , r i k ) are all different for k ∈ {1, . . . , t i } (with probability at least 1 -t 2 • 2 b-), we can apply Lemma 1 to the sets (of the same length t i = t q+1 ): Therefore in this case the left part of the last row (consisting of the first 2 2 columns) is identical to the left part of the i-th row but these rows differ in at least one position in the right part of the matrix B. By elementary operations on the rows, one can easily transform the matrix B in echelon form and it is therefore of full rank (with probability at least 1 -t 2 • 2 -b ).

D i 1 ||r i 1 ||D i 2 ||r i 2 , D i 2 ||r i 2 ||D i 3 ||r i 3 , . . . , D i ti-1 ||r i ti-1 ||D i ti ||r i
To conclude the proof, one can identify the functions F 1 and F 2 to their vector of values in ({0, 1} 2 ) L by denoting F i (x) = (ϕ

(x)
i,1 , . . . , ϕ

i,L ) for x ∈ {0, 1} 2 and i ∈ {1, 2}, where ϕ i,j ∈ {0, 1} 2 for i ∈ {1, 2} and j ∈ {1, . . . , L}. In this case by construction, τ i is the authentication tag of the document D i with randomness r i for all i ∈ {1, . . . , q + 1} if and only if for all j ∈ {1, . . . , L}, the j-th bit τ (j) i of τ i is equal to the dot product of the i-th row of the matrix B and the vector ϕ 2,i ||ϕ 1,i . Using the same argument as in [START_REF] Bellare | XOR MACs: New methods for message authentication using finite pseudorandom functions[END_REF], since B is of full rank, the number of vectors satisfying this q + 1 equations is 2 L times smaller than the number of vectors satisfying only the first q equations (corresponding to the first q rows of B), and therefore we obtained that the forgery τ q+1 output by the adversary is valid with probability 2 -L if the matrix B is full rank.

We have thus proved that, in the simplified case, the probability that A's forgery is valid is upper-bounded by

q 2 • 2 b-+ t 2 • 2 b-+ 2 -L .
and thus the claimed bound for general adversaries.

C o m p u tat i o n a l c a s e . If we replace the (truly) random functions by pseudo-random functions in the previous result, we obtain readily the following computational security result: Theorem 2. Let F be the family of pseudo-random functions with input length 2 • and output length L. Let A be any adversary making a (q m , q v , q inc )-attack against the modified XOR-scheme with two functions picked uniformly at random from F and running in time λ. There exist an adversary B against the pseudo-randomness property of F that makes q = q • t queries to F , runs in time λ = λ + O(q ( + L)) such that

Adv P RF B,F ≥ Adv BS A,X S -[q 2 • 2 b-+ q v • (t 2 • 2 b-+ •2 -L )].
where q = q m + q inc and t denotes the maximal block-length of the documents authenticated in the security game.

Proof (Theorem 2). The proof is identical to the proof of [START_REF] Bellare | XOR MACs: New methods for message authentication using finite pseudorandom functions[END_REF]Theorem 4.2] and is left to the reader.

Conclusion

We showed that the XOR-scheme as described in [START_REF] Bellare | Incremental cryptography: The case of hashing and signing[END_REF] does not provide the claimed basic security: a forgery can be easily built from any tag by inserting specific document block chains to a legitimate document and the corresponding random value chains to the legitimate random value. We proposed a modified XOR-scheme that is not vulnerable to these attacks and we proved its security in the basic sense. Our modified XOR-scheme is the only secure strongly incremental algorithm but unfortunately it still has some drawbacks: the randomness generation slows down the algorithm and the tag length makes it unpractical because the random values have to be stored. But it is definitely worth analyzing its structure in order to improve it or to build another strongly incremental authenticated scheme (or prove a lower bound on the length of strongly incremental MAC algorithms). Another interesting open problem is to design a strongly incremental authenticated scheme that achieves tamper-proof security.

$←-

  S to denote sampling x uniformly at random from S. For X ∈ {0, 1} * , we use |X| to denote the bit length of X and |X| denotes the number of -bit block in the bit-string X (and in particular |X| 1 = |X|). R a n d o m f u n c t i o n s / R a n d o m p e r m u tat i o n s . The set of all functions {0, 1} → {0, 1} L is denoted F ,L . A random function F is a randomly chosen function in F ,L . The set of all permutations {0, 1} → {0, 1} is denoted P . A random permutation P is a randomly chosen permutation in P . P s e u d o -R a n d o m f u n c t i o n s / P s e u d o -R a n d o m p e r m u tat i o n s .

Fig. 1 .

 1 Fig.1. Game defining Basic Security (BS) for an incremental authentication scheme.

Fig. 2 .

 2 Fig. 2. Description of the XOR-scheme

  processed by the function F k1 and outputs a value denoted h i then the bitwise XOR (eXclusive OR) of all the values (denoted Σ) is processed by the permutation P k2 to give the value τ .• The Verification algorithm X S.V takes as inputs the document D and a tag T := (r, τ ). It re-computes the value τ from the inputs r and D. It returns 1 if this value is equal to the input τ and 0 otherwise. • The Insert operation X S.I enables to insert a block value in a document.

Fig. 3 .

 3 Fig. 3. Xor cancellation strategy in the XOR-scheme

Fig. 4 .

 4 Fig. 4. Σ computation for 3 block document

Fig. 6 .

 6 Fig. 6. Description of the fixed XOR-scheme

1 .

 1 A asks the MAC of a document D = D 0 ||D 1 and receives the tag T 1 = (r 0 ||r 1 , τ 1 ). 2. A asks to delete the first block of D by with the delete query D(0, ., D 0 , D 1 , τ 1 ) and receives T 2 = (r 1 , τ 2 ).

3 .

 3 A asks to insert the block D 0 at the first position of the resulting document with the query I(0, D 1 , ., D 0 , τ 2 ) and receives T 3 = (r 0 ||r 1 , τ 3 ). 4. A asks to insert the block D 2 at the position 2 of the original document D with the query I(2, ., D 1 , D 2 , τ 1 ) and receives T 4 = (r 0 ||r 1 ||r 2 , τ 4 ). 5. A builds the document D * = D 0 ||D 1 ||D 2 and the tag T * = (r 0 ||r 1 ||r 2 , τ 1 ⊕ τ 3 ⊕ τ 4 ).

3 ,.

 3 . . . , D q+1 ti-1 ||r q+1 ti-1 ||D q+1 ti ||r q+1 tiWe thus obtain that there exist an index k ∈ {1, . . . , t i -

Actually supporting insertion and deletion is sufficient as replacement can be obtain by combining these two update operations.

Competition for Authenticated Encryption: Security, Applicability, and Robustness.

In[START_REF] Bellare | Incremental cryptography and application to virus protection[END_REF] Theorem 3.1], Bellare, Goldreich and Goldwasser stated a security result for their scheme but no proofs are provided in their paper.

For the first position, there is no previous block.

For the last position, there is no next block.

Acknowledgments. The authors are supported in part by the French ANR ALAMBIC Project (ANR-16-CE39-0006). The authors thank Mihir Bellare for helpful discussions and for pointing out references.

Original XOR-scheme Algorithms