Marble Thomas Fuhr

Gaëtan Leurent

Valentin Suder

Collision Attacks against CAESAR Candidates Forgery and Key-Recovery against

Keywords: CAESAR competition, authenticated encryption, cryptanalysis, Marble, AEZ, PMAC, forgery, key-recovery

In this paper we study authenticated encryption algorithms inspired by the OCB mode (Offset Codebook). These algorithms use secret offsets (masks derived from a whitening key) to turn a block cipher into a tweakable block cipher, following the XE or XEX construction. OCB has a security proof up to 2 n/2 queries, and a matching forgery attack was described by Ferguson, where the main step of the attack recovers the whitening key. In this work we study recent authenticated encryption algorithms inspired by OCB, such as Marble, AEZ, and COPA. While Ferguson's attack is not applicable to those algorithms, we show that it is still possible to recover the secret mask with birthday complexity. Recovering the secret mask easily leads to a forgery attack, but it also leads to more devastating attacks, with a key-recovery attack against Marble and AEZ v2 and v3 with birthday complexity. For Marble, this clearly violates the security claims of full n-bit security. For AEZ, this matches the security proof, but we believe it is nonetheless a quite undesirable property that collision attacks allow to recover the master key, and more robust designs would be desirable. Our attack against AEZ is generic and independent of the internal permutation (in particular, it still works with the full AES), but the keyrecovery is specific to the key derivation used in AEZ v2 and v3. Against Marble, the forgery attack is generic, but the key-recovery exploits the structure of the E permutation (4 AES rounds). In particular, we introduce a novel cryptanalytic method to attack 3 AES rounds followed by 3 inverse AES rounds, which can be of independent interest.

Introduction

The purpose of an Authenticated Encryption scheme is to provide both privacy and integrity with a single cryptographic algorithm. In 2014, the CAESAR competition was launched with the goal to identify good Authenticated Encryption schemes as better alternatives to current options such as AES-GCM [START_REF]Advanced Encryption Standard (AES)[END_REF]. 57 candidates have been submitted to the CAESAR competition, and they must now be analyzed carefully.

In this paper, we provide a security analysis of the AES-based candidates Marble [START_REF] Guo | Marble Specification Version 1.0[END_REF] and AEZ v3 [START_REF] Hoang | AEZ v3: Authenticated-Encryption by Enciphering[END_REF]. Both designs are inspired by OCB [START_REF] Rogaway | OCB: a block-cipher mode of operation for efficient authenticated encryption[END_REF], designed in 2001 by Rogaway, Bellare, Black, and Krovetz. They are built as modes of operation of a block cipher 4 , using secret offsets at the input and/or output of the block cipher calls.

OCB. In OCB, a whitening key L is derived from the master key K, and the i-th message block M i is enciphered to

C i = E K (M i ⊕ γ i • L) ⊕ γ i • L
, where γ i is a (Gray) counter, • is a finite field multiplication, and γ i • L is the i-th offset. This design principle was later formalized as the XE and XEX construction [START_REF] Rogaway | Efficient instantiations of tweakable blockciphers and refinements to modes OCB and PMAC[END_REF], and proved to turn efficiently a secure block cipher into a secure tweakable block cipher [START_REF] Liskov | Tweakable block ciphers[END_REF]. OCB with a an n-bit block cipher is proven secure up to 2 n/2 queries, and Ferguson showed a collision attack matching the bound [START_REF] Ferguson | Collision attacks on OCB[END_REF]. The attack uses a long message M , so that there is a collision between two block cipher inputs:

M i ⊕ γ i • L = M j ⊕ γ j • L
The collision can be detected because M i ⊕ C i = M j ⊕ C j , and the value of L is recovered as (γ i ⊕ γ j ) -1 • (M i ⊕ M j ). When L is known, it is easy to forge messages.

Marble. Marble [START_REF] Guo | Marble Specification Version 1.0[END_REF] is a CAESAR candidate by Jian Guo inspired by COPA [START_REF] Andreeva | Parallelizable and authenticated online ciphers[END_REF]. COPA was designed in 2013, and combines OCB's offsets with an internal dependency chain in order to achieve some security in the case of nonce repetition. Marble uses two internal chains in order to prevent birthday attacks on the internal chain, and uses reduced-round AES as building blocks. Marble claims security against nonce-repetition, and against release of unverified plaintexts, but cannot hide common prefixes in case of nonce reuse (Marble is online). As opposed to most CAESAR candidates, Marble claims full 128-bit security (beyond the birthday bound). The structure of Marble can be seen in Figure 2.

Results presented so far on Marble include a cipher-text distinguisher with complexity 2 64 , similar to the distinguisher against the counter mode [START_REF] Sasaki | Universal Forgery on POET and Ciphertext Distinguisher on POET and Marble[END_REF].

AEZ. AEZ is a CAESAR candidate designed by Hoang, Krovetz, and Rogaway. The authors define the security notion of Robust AE, which is the optimal security achievable when nonces are repeated, and unverified plaintexts are released. AEZ is claimed to achieve this security notion. In this paper, we focus on the current version of AEZ, AEZ v3, as proposed on the crypto-competition mailing list, and presented at DIAC [START_REF] Hoang | AEZ v3: Authenticated-Encryption by Enciphering[END_REF]. AEZ v3 has also been accepted at Eurocrypt 2015, and presented as one of the honorable mentions for the best papers award [START_REF] Hoang | Robust authenticated-encryption AEZ and the problem that it solves[END_REF]. Our result can also be applied to AEZ v2, but not to AEZ v1, because of a different key expansion.

As far as we are aware, no cryptanalysis of AEZ as been published so far.

Our results

In this paper, we describe generic collision attacks against Marble and AEZ, allowing to recover the whitening key with about 2 n/2 chosen message queries. When the whitening key is known the security offered by Marble and AEZ crumbles and we show a forgery attack using a single extra encryption query. Moreover, we extend this result to key-recovery attacks using properties of the internal permutations and/or the key scheduling.

Our results are summarized in Table 1 and2. The data complexity is listed in number of message blocks (16 bytes). We now detail our results on each Authenticated-Encryption with Associated-Data (AEAD) scheme.

Marble. Our attack against Marble uses queries with repeated nonces, which should be secure according to the security claims of Marble. Since Marble claims security beyond the birthday bound (allowing up to 2 n block of data), the forgery attack using collisions clearly violates the security claims. In addition, we show that if unverified plaintexts are released, i.e. if we can obtain plaintexts from ciphertexts without a valid tag, then we can further recover the master key K. For this attack, we build special queries so that only 3 forward AES rounds and 3 backwards AES rounds are active, and we develop a novel method to attack such a reduced cipher with only known plaintext/ciphertexts. Our attack can be build upon two different distinguishers. the first one is based on the detection of collision events, and the second one on a statistical property. In both cases, our attack requires about 2 33 queries and its time complexity is 2 64 ; we believe this result is also of independent interest.

Following the disclosure of this attack, Guo proposed a minor modification of the specifications of Marble as version 1.2 [START_REF] Guo | Marble Specification version 1.2[END_REF]. However, our attack is still applicable to the modified version, as shown independently by ourselves and Lu [START_REF] Lu | On the Security of the COPA and Marble Authenticated Encryption Algorithms against (Almost) Universal Forgery Attack[END_REF]. Guo later decided to withdraw Marble from the CAESAR competition.

AEZ. Our analysis of AEZ v3 focuses on the processing of Associated Data. In particular, if AEZ is used with an empty message and no nonce, it turns into a variant of PMAC, and the security notion of Robust AE becomes the usual MAC security notion. We show how to recover the whitening key of this variant of PMAC with a collision attack (a collision attack is also possible against the standard PMAC, e.g. following [START_REF] Lee | Forgery and key recovery attacks on PMAC and mitchell's TMAC variant[END_REF]). More importantly, the key derivation of PMAC allows to recover the master key K from the whitening key.

This attack does not violate the security proof, but matches the security bound. However, collision attacks usually have a more limited impact (e.g. only affecting authenticity), and it seems quite unfortunate that a collision attack leads to a key-recovery. This property should probably be avoided when possible 5 .

COPA. After the release of an early version of this paper, Lu applied the same techniques to COPA, and described an attack to recover the whitening key [START_REF] Lu | On the Security of the COPA and Marble Authenticated Encryption Algorithms against (Almost) Universal Forgery Attack[END_REF].

The main attack in this paper actually targets the associated data processing, which uses PMAC, and can be applied to PMAC. However, the impact of this result is unclear because COPA and PMAC do not claim security beyond the birthday bound, and this attack cannot be turned into a key-recovery attack. Outline of the paper Since our collision attack on AEZ is much simpler than the attack against Marble, we first explain it in Section 2. Then we give a short description of the Marble authenticated encryption algorithm in Section 3. In section 4, we show how to recover the whitening key L and describe our forgery attack. Finally, we demonstrate in Section 5 how to recover the encryption key K from decryption-misuse queries.

Collision Attack against AEZ

We first explain the collision attack on AEZ and the resulting key-recovering attack.

Short Description of AEZ

For simplicity, we consider AEZ used with only associated data, without any nonce or message (the attack can easily be applied with a fixed nonce and message if required). In this case, AEZ turns into a variant of PMAC, and the

E k 1 E k 0 9J L τ E k 0 E k 0 E k 0 17J 18J 19J L L L A 2 1 A 2 2 A 2 3 E k 0 E k 0 25J 26J L L A 3 1 A 3 2
Fig. 1. AEZ used as a MAC (no message, no nonce, two AD strings).

security claim becomes the usual MAC security definition. A particularity of AEZ is that it allows a vector-valued input, i.e. it can authenticate a sequence of strings rather than a single string. More precisely, the MAC is computed as follow:

-The key derivation algorithm generates keys k 0 , k 1 and whitening keys J, L -Full data blocks A j i of the j-th string (indexed from 1) are processed as:

X j i = E k0 A j i ⊕ (i mod 8) • J ⊕ 2 (i-1)/8 • L ⊕ 8j • J
-If the last block is partial, it is enciphered as:

X j i = E k0 (A j i ⊕ 8j • J) -
The first block to be processed is the ciphertext extension τ (corresponding to the tag length). It is τ = 128 by default. -The tag is computed as E k1 ( i,j X j i ) where E is a full or reduced-round AES. This is illustrated by Figure 1.

Collision Attack on AEZ

In order to mount a collision attack against AEZ, we consider two sets of messages, with C a fixed block:

-A = {A x | x ∈ {0 . . . 2 64 -1}}, with A x = τ ; C; (C [x] 0 64 ) -B = {B y | y ∈ {0 . . . 2 64 -1}}, with B y = τ ; (C 0 64 [y]); C
All message are made of two separate strings; message in A have a string of one block and a string of two blocks, while messages in B have a string of two blocks and a string of one block. In particular, we have:

-MAC(A x ) = E k1 E k0 τ ⊕ L ⊕ 9J ⊕ E k0 C ⊕ L ⊕ 17J ⊕E k0 C ⊕ L ⊕ 25J ⊕ E k0 ([x] 0 64 ) ⊕ L ⊕ 26J -MAC(B y ) = E k1 E k0 τ ⊕ L ⊕ 9J ⊕ E k0 C ⊕ L ⊕ 17J ⊕E k0 (0 64 [y]) ⊕ L ⊕ 18J ⊕ E k0 C ⊕ L ⊕ 25J
This leads to a simple collision attack: MAC(A x ) = MAC(B y ) if and only if [x] [y] = 8 • J (where 8 = 18 ⊕ 26). With A and B of size 2 64 as defined above, there is exactly one collision, and the collision immediately reveals the value of

J = 8 -1 • ([x] [y]).
Key recovery. Surprisingly, the key derivation of AEZ allows to recover the master key K from the whitening key J. More precisely, if the master key K is of length 128 bits or smaller, J is an encryption of K under a known constant C: J = AES4 C (K). This can easily be inverted: K = AES4 -1 C (J). We note that this is not the case in PMAC, where the whitening key is an encryption of 0 under the secret key K: L = AES K (0). This attack matches the security proof of AEZ and does not violate the security claims. However, a complete break of AEZ after the birthday bound is not expected: most schemes with birthday-bound security are more resilient and collision attacks don't allow key-recovery.

It should be mentioned that the Eurocrypt version of AEZ does not explicitly specify a key derivation algorithm, and leaves it as an open problem: "The key K ∈ Byte * is mapped to three 16-byte subkeys (I, J, L) using the key-derivation function (KDF) named Extract that is called at line 401. The definition of Extract is omitted from the figures and regarded as orthogonal to the rest of AEZ. See the AEZ spec for the current Extract : Byte * → Byte 48 . In our view, it is an unresolved matter what the security properties (and even what signature) of a good KDF should be. Work has gone off in very different directions, and the area is currently the subject of a Password Hashing Competition (PHC) running concurrently with CAESAR."

Clearly, the key derivation of the AEZ v3 specification does not have the security properties of a good KDF.

Data limit. The AEZ specification requires users to change the key after encrypting 2 48 bytes, i.e. 2 44 blocks. This prevents the attack as described above. However, we can perform the attack with smaller sets A and B of size 2 41. 4 , with a success probability of 2 -45.2 . This is still much more efficient than generic attacks: with a time complexity of 2 44 , a brute-force key search only succeeds with a probability of 2 -84 .

Description of Marble

Marble is an authenticated encryption algorithm designed by Guo [START_REF] Guo | Marble Specification Version 1.0[END_REF] with keylength and tag-length of both 128 bits. A plaintext and its associated data are divided into blocks of 128 bits and are then proceeded consecutively. Its internal permutation is based on a modified version of the AES block cipher. Unlike other authenticated encryption algorithms, Marble does not require a nonce.

Marble has very strong security claims: it claims to offer full 128-bit security, i.e. an attack should take time T = 2 128 even after large amount of data have been encrypted with the same key (up to D = 2 128 ). This is in contrast to many CAESAR candidates and classical modes of operations for block ciphers (e.g. GCM), which only offer a birthday level of security, i.e. the ciphers are secure as long as T • D < 2 128 .

In addition, Marble does not use nonces, and the security claim even holds if unverified plaintexts are released, i.e. the adversary can request the decryption of a ciphertext C without knowing a valid tag corresponding to C (decryptionmisuse oracle). A few other CAESAR candidate allow the release of unverified plaintext (AEZ, POET, APE, Minalpher), but they only claim birthday security.

An overview of Marble is depicted in Figure 2. The Marble mode of operation makes use of two 128-bit chaining variables s 1 and s 2 , initialized with constants const 1 and const 2 . The associated data and the plaintext are padded independently, so both resulting fields A and P can be divided into 128 bit blocks. We do not describe the padding function here, as it does not affect our attacks. We will denote a message to encrypt by (AD M ), where AD is a vector containing l A 128-bit blocks of associated data and M is a vector containing l M 128-bit blocks of plaintexts.

The internal primitive used is a modified block cipher, as intermediate values of the block are combined with the incoming chaining variables. Formally, the primitive uses 3 internal keyed permutations E 1 , E 2 and E 3 and processes 128-bit blocks as follows. On input (P, s 1 , s 2 ), (C, s 1 , s 2 ) is defined as

X = E 1K (P ) (X , s 1 ) = (3X + s 1 , X + s 1 ) Y = E 2K (X ) (Y , s 2 ) = (3Y + s 2 , Y + s 2 ) C = E 3K (Y )
Note that additions and multiplications are performed in the binary Galois Field F 2 128 defined by the primitive polynomial x 128 +x 7 +x 2 +x+1. Furthermore, polynomials Σa i X i are denoted by the integers Σa i 2 i . Therefore, please note that additions and multiplications on such objects have to be interpreted as operations in the binary field (and not on the integer ring) and have to be handled carefully.

In the case of Marble, each one of the three permutations E 1 , E 2 and E 3 , is composed with 4 full-round of AES (i.e. SubByte, ShiftRow, MixColumn and Ad-dRoundKey). One can notice that no key addition is performed at the beginning of those permutations. 12 subkeys are therefore required. A 128-bit master key K is derived into 11 subkeys using the AES-128 key-schedule algorithm. The master key itself is used as the 12th subkey. For more information about the AES block cipher, we refer to [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF].

The Marble encryption then works as follows. First, a mask L is derived from the key K by encrypting a constant const 3 (which also sets key-dependent s 1 [0], s 2 [0]). For each associated data block A i (i ≥ 1), a pre-whitening key is defined as 2 i-1 3 2 L. For each plaintext block M i , a pre-whitening key and a post-whitening key are defined as 2 i L and 2 i-1 3L. These blocks are processed iteratively, starting with associated data, as follows:

1. Addition (i.e. xor) of the pre-whitening key; 2. Application of the internal primitive; 3. For plaintext blocks, application of the post whitening key, which results in ciphertext blocks.

Finally, the tag is computed by encrypting an extra block defined as the sum of all plaintext blocks and all encrypted additional data blocks, with prewhitening key 2 M 7L and post-whitening key 2 M -1 3L.

A universal forgery attack on Marble

In this section, we first describe a method to find the mask L using about 2 65 chosen plaintext queries. Then, we use this knowledge to compute forgeries. Our attack enables to modify the associated data field in a way that affects neither the ciphertext nor the authentication tag. It can therefore be used to compute universal forgeries in a chosen plaintext setting.

Recover the mask L

The main idea of the attack is to build a pair of message M = M so that the inputs to the E 1 functions are the same for both messages. This is possible if M and M have the same total length, but the associated data and message parts have different lengths. When the inputs to E 1 collide, all the intermediate computations collide, and we can detect this event on the resulting ciphertexts. Please note that as different multiples of L are used for post-whitening, this operation is more tricky than detecting a collision on ciphertexts. In the following we use 2 blocks of AD and 1 block of message for M , but 1 block of AD and 2 blocks of message for M .

More precisely, we encrypt messages M α and M β , for different values α, β ∈ F 2 128 , defined as follows (where A ∈ F 2 128 is a constant value):

-M α = (AD[1], AD[2] M [1]) = (A, 8α 6α); -M β = (AD[1] M [1], M [2]) = (A 8β, 6β). Const0 E1 Const1 E2 Const2 E3 L AD[1] 3 2 L E1 E2 E3 . . . . . . . . . AD[lA] 2 l A -1 • 3 2 L E1 E2 E3 τ M [1] 2L E1 E2 E3 3L C[1] M [2] 2 2 L E1 E2 E3 2 • 3L C[2] . . . . . . i M [i] 2 l M • 7L τ E1 E2 E3 2 lm-1 • 3 • 7L T Fig. 2.
General design of Marble. In the following, we consider sets of 2 64 values α and β so that α ⊕ β covers all values in F 2 128 . The inputs to the E 1 layer will be respectively (we note that 3 2 = 5 in F 2 128 ):

x 1 = A ⊕ 5L x 2 = 8α ⊕ 10L x 3 = 6α ⊕ 2L for M α x 1 = A ⊕ 5L x 2 = 8β ⊕ 2L x 3 = 6β ⊕ 4L for M β
In particular, we have:

x 1 ⊕ x 1 = 0 x 2 ⊕ x 2 = 8(α ⊕ β ⊕ L) x 3 ⊕ x 3 = 6(α ⊕ β ⊕ L)
Therefore, the inputs to E 1 collide when α ⊕ β = L.

We denote the output of the E 3 layer as y i (respectively y i ), and the corresponding ciphertexts as C α [START_REF] Andreeva | Parallelizable and authenticated online ciphers[END_REF] (respectively (C β [START_REF] Andreeva | Parallelizable and authenticated online ciphers[END_REF], C β [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF])). We have:

C α [1] = y 3 ⊕ 3L C β [1] = y 2 ⊕ 3L C β [2] = y 3 ⊕ 6L
In particular, if α ⊕ β = L, we have x i = x i for i ≤ 3, therefore y i = y i for i ≤ 3, and

C α [1] ⊕ C β [2] = 5L (since 3 ⊕ 6 = 5
). In order to detect this event efficiently we match the set of values {C α [1] ⊕ 5α} and {C β [2] ⊕ 5β}. When α ⊕ β = L, we have a match, and we can easily filter false positives using a new message pair with a different value of the constant A. The full algorithm is given by Algorithm 1, using 2 65 short encryption queries.

An attack against Marble 1.2

After the first release of our attack, Guo made a minor modification to the specification of Marble [START_REF] Guo | Marble Specification version 1.2[END_REF]. Namely, the input mask for the last block of associated data is changed from 2 i-1 3 2 L to 2 i-1 3 3 L. Our attacks can be adapted as follows.

The adversary needs to query an encryption oracle for messages M α and M β , defined as

-M α = (AD[1], AD[2] M [1]) = (10α, 28α 6α); -M β = (AD[1] M [1], M [2]) = (10β 28β, 6β).
Using the notations of Section 4.1, the inputs to the E 1 layer will be :

x 1 = 10α ⊕ 5L x 2 = 28α ⊕ 30L x 3 = 6α ⊕ 2L for M α x 1 = 10β ⊕ 15L x 2 = 28β ⊕ 2L x 3 = 6β ⊕ 4L for M β Algorithm 1 Recover L from an encryption oracle E. H ← ∅ H is a hash table for α ∈ {0, 1, . . . , 2 64 -1} do (C[1] T ) ← E(0, 8α 6α) H{C[1] ⊕ 5α} ← α end for for β ∈ {0, 2 64 , . . . , 2 128 -2 64 } do (C [1], C [2] T ) ← E(0 8β, 6β) if H{C [2] ⊕ 5β} exists then α ← H{C [2] ⊕ 5β} (D[1] T ) ← E(1, 8α 6α) (D [1], D [2] T ) ← E(1 8β, 6β) if D[1] ⊕ 5α = D [2] ⊕ 5β then return α ⊕ β end if end if end for
In particular, we have:

x 1 ⊕ x 1 = 10 • (α ⊕ β ⊕ L), x 2 ⊕ x 2 = 28 • (α ⊕ β ⊕ L), x 3 ⊕ x 3 = 6 • (α ⊕ β ⊕ L).
If for some (α, β), α ⊕ β = L, then x i = x i for i = 1, 2, 3. Then, the outputs of E 3 verify y 1 = y 1 , y 2 = y 2 and y 3 = y 3 and therefore, C α [START_REF] Andreeva | Parallelizable and authenticated online ciphers[END_REF]

⊕ 3L = C β [2] ⊕ 6L.
As 3 ⊕ 6 = 5, This can also be expressed as:

C α [1] ⊕ 5α = C β [2] ⊕ 5β.
Therefore, L has to be searched among the values (α ⊕ β) for which this relation holds. As for our attack on the previous version of Marble, about 2 64 different values of both α and β are required.

Computing forgeries on Marble without whitening keys

Once we have retrieved L, we can consider a simplified description of Marble where the masks are removed, as depicted in Figure 4. In its mask-less description, Marble possesses an interesting property as described in Figure 5: a series of identical input blocks X has a periodic effect on the internal state.

Indeed, if we let E 1 (X) = u, E 2 (3S 1 ⊕u) = v and E 2 (3S 1 ⊕2u) = w, it is easy to see that after encrypting 4 blocks X, the internal states S 1 and S 2 remain unchanged. Furthermore, if we use a series of 8 consecutive identical associated data blocks X, the effect on τ also cancels out. This leads to a universal forgery attack: for any associated data AD and plaintext M , the adversary computes the masked value B of a chunk of 8 identical blocks of associated data after AD

and queries the encryption oracle on ((A, B) M

). The answer (C T ) to that query is also a valid ciphertext for (AD M ), therefore the adversary can return (C T ) as a forgery. The attack is given as Algorithm 2.

Algorithm 2 Compute the ciphertext (C T ) from (AD M ) using known L.

B ← 2 l • 3 2 • L l A +7 l=l A (C T ) ← AEK ((AD, B) M )
Encryption oracle call return (C T )

Key-recovery attack

We now show how to recover the master key once the mask L has been determined. In order to simplify the description of the attack, we now focus on the mask-less variant of Marble; however the full attack can easily be adapted to the full version of Marble with a known mask.

The main idea is to collect pairs of messages with a fixed difference in some internal state variables. This will allow us to attack a reduced cipher composed by 4 AES rounds followed by 4 inverse AES rounds rather than a 12-round AES (see details below). Moreover, we apply this strategy to E 1 rather that to E 3 because the whitening key of E 1 is directly derived from L. Since L is known, the first AES round of E 1 is key-independent. Therefore we can peel it off, and attack only 3 forward rounds and 3 inverse rounds. However, this requires us to use decryption queries, but we can't forge valid tags for an arbitrary ciphertext yet, so we use a decryption-misuse oracle.

X E1 S1 E2 S2 E3 u 3S1 ⊕ u v X E1 E2 u 3S1 ⊕ 2u w E3 S1 ⊕ u S2 ⊕ v X E1 E2 u 3S1 ⊕ u v E3 S1 S2 ⊕ v ⊕ w X E1 S1 E2 u 3S1 ⊕ 2u w S2 E3 τ S1 ⊕ u S2 ⊕ w

Gathering pairs

The first step is to collect pairs of plaintext blocks that have the same difference in the S 1 lane (after the permutation E 1 ). In order to construct such plaintexts, we build pairs of ciphertexts with specific differences and values. More precisely, we consider pairs of messages as follows (with the same associated data AD): C x = (AD 0, 0 120 , 0, 0, 0, 0, 0, 0, 0, 0, x)

C x [i] = C x [i] ⊕ 2 i-1 • 3 • L C x = (AD 1, 0 120 , 1, 0, 0, 0, 0, 1, 1, 1, x) C x [i] = C x [i] ⊕ 2 i-1 • 3 • L
where 0 and 1 are constant one-block values and x takes a different value for each pair. We decrypt these pairs and we collect the final plaintext blocks.

We now study the differences in the S 2 lane (before the permutation E 3 ). Using the definition of the TRANS operation as given in Figure 3, S 2 is updated as follows during decryption:

S 2 [i + 1] = 2 • S 2 [i] ⊕ E -1 3 ( C[i])
With the messages C x and C x , we have

S 2 [129] = 2 129 S 2 [0] ⊕ (1 ⊕ 2 ⊕ • • • ⊕ 2 128 )A, S 2 [129] = 2 129 S 2 [0] ⊕ (1 ⊕ 2 ⊕ • • • ⊕ 2 128 )A ⊕ (2 0 ⊕ 2 1 ⊕ 2 2 ⊕ 2 7 ⊕ 2 128 )(A ⊕ B),
where

A = E -1 3 (0) and B = E -1 3 (1). Since 2 128 = 2 0 ⊕ 2 1 ⊕ 2 2 ⊕ 2 7 , we have S 2 [129] = S 2 [129]
. This is shown in Figure 5, where We now consider the final plaintext block given by the decryption oracle.

δ = A ⊕ B. E1 E2 2 127 δ ⊕ 2 6 δ ⊕ 2δ ⊕ δ E3 δ 0 ⊕ 1 . . . Px[130] ⊕ P x [130] E1 E2 E3 x ⊕ x
P x [130] = P x [130] ⊕ 2 130 • L = E -1 1 E -1 2 E -1 3 (x) ⊕ 3 • S 2 [129] ⊕ 3 • S 1 [129] P x [130] = P x [130] ⊕ 2 130 • L = E -1 1 E -1 2 E -1 3 (x) ⊕ 3 • S 2 [129] ⊕ 3 • S 1 [129] With U x = E -1 2 E -1 3 (x) ⊕ 3 • S 2 [129] , we have P x [130] = E -1 1 (U x ) ⊕ 3 • S 1 [129] P x [130] = E -1 1 (U x ) ⊕ 3 • S 1 [129]
Therefore, the pair P x [130], P x [130] can be seen as a plaintext/ciphertext pair for a cipher with 4 AES rounds, a middle key S 1 [129] ⊕ S 1 [129], and 4 inverse AES rounds:

P x [130] E 1 U x E -1 1 P x [130] S 1 [129] S 1 [129]
In addition, we can peel off the outer rounds since there is no whitening key in E 1 .

Extracting the key

We must now extract the key of a reduced cipher with 3 AES rounds, and 3 inverse AES rounds. First, we notice that the middle ShiftRow and MixColumn operations can be removed, if we transform the middle key. In a basic description, the operations in the middle are ShiftRow, MixColumn, AddKey, then XORing the constant S 1 [129] ⊕ S 1 [129], AddKey, InverseMixColumn, and Inverse-ShiftRow. Instead we move the (unknown) constant addition before ShiftRow, using the linearity of ShiftRow and MixColumn, so that ShiftRow, MixColumn and AddKey cancel out with AddKey, InverseMixColumn and InverseShiftRow. We denote the addition of the modified constant as AddDeltaS, and its value as

δ S = InverseShiftRow(InverseMixColumn(S 1 [129] ⊕ S 1 [129]
)). The middle rounds are then reduced to byte-wise operations: AddRoundKey, SubByte, AddDeltaS, InverseSubByte, AddRoundKey. This can be seen as a key-dependent Sbox layer. The first step of our attack is to guess a diagonal of the first round key, which allows to compute a column after the first round and before the last round. Next we focus on the middle rounds. The middle rounds have only one MixColumn op- eration, and one InverseMixColumn without byte shuffling in between. Therefore it can be seen as four parallel 32-bit functions, acting on each diagonal (similar to the Super-SBox technique [START_REF] Gilbert | Super-Sbox Cryptanalysis: Improved Attacks for AES-Like Permutations[END_REF]). Note that if the key guess is wrong, the resulting function can not be decomposed into 4 parallel functions. For each function, 1 input byte and 1 output byte are known. We describe below two different distinguishers for the middle rounds, that lead to key recovery attack with similar complexities. The first one is based on a rare event that can easily be detected, the second one relies on the detection of a statistical bias in the generic case.

Collision-based distinguisher For our first distinguisher, we focus on the constant δ S . We only know that δ S is non-zero on the full state. Considering that it is distributed uniformly on non-zero constants, it cancels one of the diagonals8 with probability (2 96 -1)/(2 128 -1) ≈ 2 -32 . Then, an average of 2 30 different choices of AD are necessary to reach a value of δ S that cancels on one of the diagonals. Let us consider that it occurs on the first diagonal (w.l.o.g.), which contains bytes 0, 7, 10, 13. Then, the value of these bytes collide before and after the AddDeltaS operation. Then, the values of the first column of the block (bytes 0, 1, 2, 3) are not affected by the middle rounds. If we continue the decryption process towards both ends of the modified version of the AES, the collision passes through the InverseMixColumn operation. After undoing the ShiftRow, SubByte and textsfAddKey operation, we notice that the values of bytes 0, 5, 10, 15 are equal at the beginning and at the end of the middle part of the cipher.

For each choice of AD, we then generate 3 (plaintext-ciphertext) pairs ( P x , P x ) for 3 values of x. Then, we proceed as follows.

In each of the 2 30 sets, we guess separately the 32 bits on each of the 4 antidiagonals9 of the first round key. This enables to compute one full column of the state before and after the middle rounds, for each value of x. For each byte b i in this column, we store a list L i of the key values such that the input byte and the output byte of the middle rounds are equal for each x.

Then we consider the first diagonal before and after the middle rounds. It contains bytes 0, 5, 10 and 15 of the block. Remember that the diagonals contain the inputs and outputs of 4 independent functions F i . From the 4 lists of partial keys L j , j = 0, 5, 10, 15, we can build all the keys such that the input of F i collides with the output for each value of x. Using the known plaintexts and ciphertexts for the full cipher, we can try all these keys as candidates. Then, we repeat the whole process with the other three diagonals.

We now explain why this attack works.

Filtering keys. Following the analysis above, the right key can be decomposed into 4 partial keys covering each diagonal of the block. If δ S cancels on one of the columns, then the partial values of the right key will appear on the four corresponding lists L i , and the full key will be among the combination of elements of the four lists. Therefore, the right key will be detected by our algorithm.

False positives. For each wrong partial 32-bit key, it is stored in the corresponding list L j if the input and output of F i collide on byte j, for each of the 3 values of x. This occurs with probability 2 -24 , if we consider the input and output byte computed for F i as independent. Therefore, we have on average one false positive of each of the 4 diagonals of the key. Considering that the number of false positives are independent for each diagonal of the key, there are on average (2 8 ) 4 = 2 32 keys to try, for each of the 4 diagonals and each of the 2 30 sets of values. The expected number of key candidates is marginally increased to (2 8 + 1) 4 ≈ 2 32 when the difference δ S cancels on the diagonal, as each set of partial keys at least contains the right key.

δ S = 0 on column i. As above, each wrong key guess is stored with probability 2 -24 , which leads to (2 8 ) 4 false positives on average, that are discarded by exhaustive search.

Summary of the attack. We focus on the key recovery attack on the mask-less version of Marble. In the decryption-misuse setting, it requires the decryption of 6 × 2 30 ciphertexts composed of 130 blocks of plaintext and 1 block of associated data, which correspond to 2 30 sets of 3 pairs. To build the lists of partial keys, one has to perform 6 × 1/4 of an AES round for each partial key guess, leading to a total of 3 × 2 31 AES rounds, for each set and each diagonal. The average complexity of this step for the full attack is then 3 × 2 63 AES rounds. The most time-consuming part of the attack is the exhaustive search among the remaining candidates, which requires 2 64 AES encryptions on average (2 32 per column and per set).

Linear cryptanalysis

The method described in Section 5.1 leads to the knowledge of plaintext-ciphertext pairs for a cipher that consists of 3 AES rounds, a key addition and 3 inverse AES rounds. The adversary therefore targets a cipher with a reduced number of rounds, in a known plaintext setting. Using linear cryptanalysis therefore seems a natural idea. As shown above, one can guess 4 key bytes, which leads to the knowledge of 4 input and 4 output bytes of the inner 4 rounds of this cipher.

In [START_REF] Keliher | Exact maximum expected differential and linear probability for two-round advanced encryption standard[END_REF], Keliher and Sui demonstrate that the maximum expected linear probability over 2 AES rounds is about LP ≈ 1.638 × 2 -28 . In our case, we can concatenate a linear trail with its inverse. When averaging over the possible values of the key and of the intermediate difference δ S , the maximum expected probability for a 4-round characteristic would be about LP 2 ≈ 1.342 × 2 -55 . This number also gives an estimation of the amount of data required for the attack to work. Even by taking into account the possible bias due to the linear hull effect, the complexity of the linear attack is expected to be far higher than the one suggested by the experiments below.

A refinement of the linear attack consists in noticing that between the two middle rounds, each byte of the block is affected only by a key byte and a byte of δ S , but not by other bytes of the block. Therefore, the two middle Sbox layers could be expressed as one layer of 8-bit key-dependent Sboxes, leading to trails with 6 active Sboxes instead of 10. Nevertheless, the best linear trail would then depend on the unknown value of δ S , which would make it hard to exploit. Instead, we use the following statistical distinguisher.

Statistical distinguisher

Intuitively, if we have many partial input/output pairs, we should detect some correlation between the inputs and output. Indeed, when the key guess is wrong, the function composing the distinguisher behaves as a 128-bit permutation instead of the parallel application of four 32-bit functions. Hence, the input and output bytes are less correlated. We focus on a property that does not require to know in advance which values are correlated, and works for any function based on (four 32-bit) parallel permutations.

For each known plaintext/ciphertext, we partially encrypt/decrypt one round on a specific diagonal and we denote one known input/output byte of the distinguisher by (α, β) respectively. It is possible to take into account the four known input/output pairs, but the distinguisher presented below works with only one position and is easier to explain. We use 2 16 counters c α,β to count how many times each pair (α, β) occurs with D available data. If the key guess is correct, there should be some correlation between α and β, which results in a higher value for some counters (and lower values for the other counters). In order to detect this effect, we compute the sample variance s 2 of the 2 16 counters: 2 , where c = 2 -16 α,β c α,β . We expect that s 2 is higher when the key guess is correct, because of the correlation between α and β. For a wrong key guess, the computation between α and β can not be decomposed into 4 parallel functions, and this correlation should vanish. The resulting attack is described by Algorithm 3.

s 2 = 2 -16 α,β (c α,β -c)
Algorithm 3 Recover the key of a reduced AES (3 direct rounds and 3 inverse rounds)

Input: Plaintext/ciphertext pairs (P, C) for 0 ≤ K < 2 32 do Partial key guess Initialize c α,β = 0 for all (P, C) do Compute α, β c α,β ← c α,β + 1 end for c ← 2 -16 α,β c α,β s 2 [K] ← 2 -16 α,β (c α,β -c) 2 end for return arg max K s 2 [K]
In order to analyze this algorithm, we model the counters using random variables C α,β , and the sample variance as S 2 for a wrong key guess, and S 2 * for the right key. Our goal is to show that when D is large enough, we have Pr[S 2 > S 2 * ] negligible, i.e. the correct key is ranked first.

Wrong key guess. We know that starting from α, if we revert the initial round with the wrong key, then compute three rounds forward with the correct keys, add δ S , compute three round backwards with the correct keys, and finally one round forward with the wrong key, we reach a state with β. Therefore, α and β are partial inputs/outputs of a 128-bit permutation.

If we model this function by a random 128-bit permutation, the number of data matching a pair (α, β), in images and pre-images of this 128-bit function, follows an hypergeometric distribution. Indeed, for each input which first byte has value α, the output is drawn uniformly without replacement among all the possible outputs of the function. The success is determined by whether the first byte of the output equals β. The number of draws is 2 120 , and there are 2 120 success cases among 2 128 possible values.

(α, β) occurs with D data, knowing that the probability of success is p = 2 120 /2 128 = 2 -8 . Let us call this variable X α,β . Hence we have

E[X α,β ] = (2 120 ) 2 /2 128 = 2 112 Var[X α,β ] = (2 120 ) 2 /2 128 × (1 -2 -8 ) 2 /(1 -2 -128 ) ≈ 2 112 -2 105 .
Next we study Y α,u the number of times each value α, u is reached with D samples, for each possible value u of the remaining 15 bytes of the input of F . The Y α,u follow a multinomial distribution, with:

E[Y α,u ] = 2 -128 D, Var[Y α,u ] = 2 -128 (1 -2 -128 )D, Var[Y α,u , Y α ,u ] = -2 -256 D.
Let us denote by S α,β the set of values u such that F (α, u) = (β, v) for some v. It contains exactly X α,β elements. The counters C α,β can then be expressed as

C α,β = u∈S α,β Y α,u .
The variables Y α,u all follow the same distribution. From the law of total variance, we have:

Var[C α,β ] = E X α,β   Var   u∈S α,β Y α,u |X α,β     +Var X α,β   E   u∈S α,β Y α,u |X α,β     σ = 2 -16 (1 -2 16
)D, we know that the distribution of the sample variance S 2 for a wrong key guess follows a χ 2 distribution [10, Proposition 2.11]:

S 2 ∼ σ 2 (n -1) χ 2 n-1 ∼ 2 -32 Dχ 2 2 16 -1
In particular, we have Pr[S 2 > 2 16 + 2 12 ] < 2 -90 , therefore we don't expect that the sample variance of a wrong key is above 2 16 + 2 12 . In practice, we use a single set of D plaintexts, and we evaluate the sample variance of the 2 16 counters; our experiments show that the distribution is close to a χ 2 distribution (the maximum value of s 2 with 2 16 samples was 2 16 + 1420).

For the right key, we don't have an analytic expression of the distribution of the sample variance, but we can perform experiments. Our experiments show that with very high probability S 2 * > 2 16 + 2 12 , as seen in Figure 8. Of our 2 16 experiments, the minimum value of s 2 * was 102795 ≈ 2 16 + 2 15 . Using D = 2 32 , we have a large margin and we expect the attack to work with significantly less data, but recovering L will be the bottleneck of the attack.

While this attack does not use any property of the parallel 32-bit function, we expect that it can be improved in the specific case of AES rounds. In particular, we notice a small peak around 3 × 2 16 in Figure 8, which is due to zero bytes in δ s , and it should be possible to take advantage of this.

Conclusion

Our results show that collision attacks can have a strong impact on the security of authenticated encryption schemes. It seems that extracting the whitening key using collisions is possible in many OCB-based designs, and this can sometimes be extended into a full key-recovery attack.

On AEZ, we show how to recover the whitening key, and we point out that the key derivation of AEZ v2 and v3 has the unfortunate property that the master key can easily be recovered from the whitening key. This allows a complete break after the birthday bound. Even with a limit on the amount of data processed with a single key, this still gives an attack with a higher success probability than generic attacks. While this does not violate the security proof of AEZ, we believe it would be better to avoid this property.

Our results on Marble show that it does not provide the security features claimed by the author, i.e. beyond birthday bound security and decryptionmisuse resistance. We note that Marble still offers a stronger security than many CAESAR candidates and classical modes of operations when using nonces (or unique AD). Once usage requirements are relaxed, our results also show that the security of Marble is similar to the security of other misuse resistant CAESAR candidates (e.g. APE-128, POET, AEZ, Minalpher) but it collapses badly after the birthday bound under a decryption-misuse setting, even leading to a full key recovery.

It seems that adding one extra operation on the state between the processing of the associated data and of the message would avoid our attacks, but a thorough analysis would be necessary to ensure that the resulting construction is secure. As our attack heavily relies on the fact that S 1 and S 2 keep the same values on two different plaintexts, one could xor a constant block (for example, 16 bytes encoding the byte positions in the block, (0, 1, . . . , 15)) on S 1 and S 2 after processing the associated data.

In addition, our key-recovery attack of Marble suggests that 4 AES rounds in the E functions are insufficient if the adversary can find a shortcut to target two E functions instead of three. In particular, this suggest that a deeper investigation of the security of AEZ with a modified key schedule would be interesting. Up to our knowledge, the statistical distinguisher presented to recover the encryption key of a reduced-round AES, has never been used before. Although it permits to attack few rounds, it seems that it is more efficient than a classical linear attack. We believe that it is sufficient enough for this kind of distinguisher to benefit from further research.

Fig. 3 .

 3 Fig. 3. The TRANS operation.

Fig. 4 .

 4 Fig. 4. Mask-less description of Marble. S1 and S2 are unknown key-dependent values.

Fig. 5 .

 5 Fig. 5. Collision on the internal state of the associated data.

Fig. 6 .

 6 Fig.6. Difference propagation in decryption. A red arrow means that there is a fixed unknown difference. A black arrow means that the difference is null.

Fig. 7 .

 7 Fig. 7. Reduced cipher composed of 3 AES rounds, the addition of δS and 3 inverse AES rounds. The distinguisher covers the middle part of this cipher.

Fig. 8 .

 8 Fig. 8. Experimental results: distribution of the sample variance S 2 and S 2 * with D = 2 32 (2 16 experiments with random keys).

Table 1 .

 1 Our results against Marble.

	Attack (Sec. claim) Data	Time
	Recover L		2 65 × 2 CP	2 64
	Forgery	(2 128 ) 2 65 × 2 CP	2 64
	Key-recovery (2 128 ):
	Collision-based 6	2 65 × 2 CP + 2 32.6 × 130 CC 2 64
	Collision-based	2 65 × 2 CP + 2 33 × 130 CC	2 64

Table 2 .

 2 Our results against AEZ.

	Attack	Data 7 Time Success probability
	Key-recovery 2 66.6	1	1
	Key-recovery 2 44	1	2 -45.2

For efficiency reasons, Marble and AEZ actually use 4-rounds of AES rather than a full block cipher.

In AEZ v4, for the second round of the competition, the designers took into account our result and modified the key derivation in order to prevent this property.

The chosen ciphertexts use the decryption-misuse model.

The AEZ specification requires to rotate the key after 2 44 blocks

defined as the images of columns by the ShiftRow operation

defined as the pre-images of columns by the ShiftRow operation

After expanding the sums and reordering the terms to make variances and covariances of the Y α,u appear, we get:

We have numeric expressions for each term of this expression, therefore we can compute the following approximation:

Correct key. Let us now assume that the key guess is correct, i.e. the pairs (α, β) are valid partial input/output but of a 32-bit function this time. We can then reapply the above analysis by adjusting the parameters to fit the 32-bit function. In this case, X α,β denotes the number of partial values of the data matching the pair (α, β) in the right column. In that case, we have an hypergeometric distribution with 2 24 draws without replacement from a set of 2 32 values, among which 2 24 define a success event.

Therefore, we have

Similarly, we can define variables Y α,u as the number of times a given input of the 32-bit function F is reached among D samples, drawn uniformly. As in the previous case, the Y α,u follow a multinomial distribution, with:

The same formula can be used to compute the variance of the counters C α,β . We get approximately:

Distinguisher. We obtain an efficient distinguisher with D = 2 32 : for a wrong key guess, the variance of the counter is about 2 16 , but it is about 2 17 for the right key. In order to evaluate the probability that the correct key is ranked first, we must evaluate how far the sample variance s 2 is from the true variance Var[C α,β ].

For a wrong key guess, if we use a single counter and repeat the experiment with 2 16 independent sets of D plaintexts, each counter C α,β can be approximated by a binomial distribution with parameters D and p = 2 -16 . If we approximate them as a normal distribution with parameters µ = 2 -16 D and


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

Differential Forgery Attack against LAC

Keywords: Differential cryptanalysis, differentials, characteristics, forgery attack, truncated differential, LBlock, LAC

LAC is one of the candidates to the CAESAR competition. In this paper we present a differential forgery attack on LAC. We study the collection of characteristics following a fixed truncated characteristic, in order to obtain a lower bound on the probability of a differential. We show that some differentials have a probability higher than 2 -64 , which allows a forgery attack on the full LAC. This work illustrates the difference between the probability of differentials and characteristics, and we describe tools to evaluate the probability of some characteristics.

Introduction

The CAESAR competition is an ongoing effort to identify new authenticated encryption primitives [START_REF]CAESAR: Competition for Authenticated Encryption: Security, Applicability, and Robustness[END_REF]. Authenticated encryption schemes provide both confidentiality and authenticity in a single primitive, instead of using an encryption scheme together with a MAC. The competition received 57 submissions in March 2014, and an important effort is now devoted to analyzing those candidates.

LAC is a CAESAR candidate designed by Zhang, Wu, Wang, Wu, and Zhang [START_REF] Zhang | LAC: A Lightweight Authenticated Encryption Cipher[END_REF]. LAC uses the same structure as ALE [START_REF] Bogdanov | ALE: AES-Based Lightweight Authenticated Encryption[END_REF]: it is based on a modified block cipher (the G function in LAC is based on LBlock [START_REF] Wu | LBlock: A Lightweight Block Cipher[END_REF]) that leaks part of its state. The main step of the algorithm is to encrypt the current state, and the leaked data is used as a keystream to produce the ciphertext. Meanwhile, a key schedule produces new keys for each encryption, and plaintext blocks are xored inside the state, so that the final state can be used to produce the tag T . This is depicted in Figure 1.

In LAC, the main state is 64-bit wide, the key register is 80-bit wide, and the plaintext is divided in blocks of 48 bits. The G function is a modified version of LBlock. It uses 16 rounds of Feistel network, where the round function F applies a key addition, 8 parallel S-Boxes on the nibbles of the state, (the 8 S-Boxes are identical), and a nibble permutation. In addition, the inactive branch of the Feistel network is rotated by 2 nibbles; this is shown in in Figure 2. The S-Box has a maximum differential probability of 2 -2 , which is optimal for a 4-bit S-Box; it is defined as S = {E, 9, F, 0, D, 4, A, B, 1, 2, 8, 3, 7, 6, C, 5}.

Description of the attack

Our attack is a differential forgery attack: given the authenticated encryption (C, T ) of a message M , we build a cipher-text (C , T ) = (C ⊕ ∆, T ) that is valid with a probability higher than 2 -64 .

More precisely, we use a two-block difference ∆ = (α, β) so that a difference α is first injected in the state, and we predict the difference β after one evaluation of G in order to cancel it. This will be successful if we can find a differential α β in the function G with a probability p higher than 2 -64 . In Section 2.2, we give a differential with probability p ≈ 2 -61.52 . This yields a forgery attack using a single known ciphertext (of at least two blocks), with a success probability of 2 -61.52 .

In addition, the truncated characteristic we use does not affect the leaked output, so that, if the tag is valid, the plaintext corresponding to (C ⊕ ∆, T ) is M ⊕ ∆.

Characteristics and differentials

We now introduce important notions for differential cryptanalysis.

A differential is given by an input difference α and an output difference β. The probability of the differential is the probability than a pair of plaintext with difference α gives a pair of ciphertext with difference β:

Pr [α β] = Pr K,x [E(x ⊕ α) = E(x) ⊕ β] .
The probability of differentials is important to evaluate the security of a cipher against differential cryptanalysis, but it is quite challenging to compute this probability. Therefore, we introduce the notion of characteristics.

A characteristic is given by an input difference α, the difference α i after each round, and the output difference β. Since all the intermediate difference are fixed, it is quite easy to evaluate the probability of a characteristic using the Markov cipher model (i.e. assuming that the rounds are independent). The probability of the differential α β is the sum of the probability of all characteristics with input difference α and output difference β.

The designers of LAC studied its resistance against differential cryptanalysis using truncated characteristics. They show that any characteristic must have at least 35 active S-Boxes. Since the best transitions for the S-Box have a probability of 2 -2 , any characteristic has a probability at most 2 -70 . However, this does not imply a lower bound for the probability of differentials: if many good characteristics contribute to the same differential, the probability can increase significantly.

Proving an upper bound on the probability of differential is much harder than proving an upper bound for characteristics, and very few results are known in this setting. A notable example is the AES, for which an upper bound of 2 -150 for any 4-round characteristic can easily be shown [START_REF] Daemen | The Design of Rijndael: AES -The Advanced Encryption Standard[END_REF], and an upper bound of 1.881 × 2 -114 for any 4-round differential was proved using significantly more advanced techniques [START_REF] Keliher | Exact maximum expected differential and linear probability for two-round Advanced Encryption Standard[END_REF].

In this work we give a more accurate estimation of the probability of differentials in the G function of LAC by considering more than one characteristic. Our results actually lead to a lower bound on the probability of some differential.

Characteristics following the same truncated trail

Truncated differential cryptanalysis was introduced by Knudsen in 1994 [START_REF] Knudsen | Truncated and Higher Order Differentials[END_REF]. A truncated characteristic D does not specify the exact value of the differences at each step but uses partial information. The state is divided in words of a fixed size (usually bytes, but we use nibbles for LAC), and D only specifies whether the difference in each word in zero (inactive word) or non-zero (active word).

For a given truncated characteristic D, there exist many ways to instantiate the input/output differences and the intermediate differences. For a given input/output difference (α, β), we consider all the possible intermediate differences following D; this defines a collection of characteristics that all contribute to the same differential. If we can efficiently compute the sum of the probabilities of all those characteristics, this will give a more accurate lower bound of Pr [α β] than by considering a single characteristic.

Related work

Recently, a technique was proposed to find differential characteristics using Mixed Integer Linear Programming (MILP) [START_REF] Sun | Automatic Security Evaluation and (Related-key) Differential Characteristic Search: Application to SIMON, PRESENT, LBlock, DES(L) and Other Bit-Oriented Block Ciphers[END_REF][START_REF] Sun | Constructing Mixed-integer Programming Models whose Feasible Region is Exactly the Set of All Valid Differential Characteristics of SIMON[END_REF]. When a good characteristic α β is found, this technique can also be used to find a collection of characteristics following the same differential α β, by adding this constraint to the MILP problem. This has been applied quite successfully, but it inherently requires to enumerate all the considered characteristics.

An analysis of TWINE by Biryukov, Derbez and Perrin is also based on clustering differential characteristics [START_REF] Biryukov | Differential Analysis and Meet-in-the-Middle Attack against Round-Reduced TWINE[END_REF], using the same technique as presented here. TWINE is very similar to LBlock (and LAC), but the S-Box has a more uniform differential probability which limits this clustering effect compared to our results on LAC.

Computation of the probability of a truncated characteristic

In this work we use a technique to compute the probability of a collection of characteristics without having to explicitly list all the characteristics. This allows to take into account a large number of characteristics. The collection of characteristics is defined by a truncated characteristic D, which specifies whether each word is active (i.e. with a non-zero difference), or inactive.

We denote by Pr [D : α β] the probability that a pair with input difference α gives an output difference β, in a way that all the intermediate differences follow the truncated characteristic D. We also denote the reduced version of D with only i rounds as D i . We will compute exactly Pr [D : α β], i.e. we consider the collection of all characteristics corresponding to the truncated characteristics, with all possible choices of non-zero values.

In order to compute Pr [D : α β] for a given (α, β), we will first compute Pr D 1 : α α

(1) j for all the differences α for all α (i)

k following D i using the results for D i-1 :

Pr D i : α α (i) k = j Pr D i-1 : α α (i-1) j × Pr α (i-1) j α (i) k
This corresponds to a matrix multiplication, where the matrix

M i = Pr[α (i-1) j α (i)
k ] contains the probability of all the transitions α

(i-1) j α (i)
k corresponding to round i of the truncated characteristic. However, we don't explicitly perform a vector-matrix product, because the matrix is very sparse; instead we deduce the possible α (i-1) j with a non-zero Pr α

(i-1) j α (i) k from each α (i) k .

Application to LAC

In order to apply this analysis to LAC, we first have to identify a good truncated characteristic. We use an automatic search for truncated characteristics, where we represent the state with a 16-bit vector, with zero and one to represent active and inactive nibbles. After computing all the possible transitions (there are at most 2 8 × 2 16 allowed transitions because of the Feistel structure), the problem of finding an optimal r-round truncated differential is reduced to the search of a shortest path in graph with (r + 1) × 2 16 nodes, and at most (r + 1) × 2 24 edges. Moreover, the graph is structured with edges only from node of round i to nodes of round i + 1. This allows a very efficient search, round by round, with complexity (r + 1) × 2 24 .

We found several truncated characteristics with 35 active S-Boxes, and we use the one given in Figure 3. Gray square denote active nibbles. When two active nibbles are xor-ed, the truncated characteristic specifies whether the sum should be zero (slashed square) or non-zero (black square). We note that this characteristic has at most 6 active nibbles at a given round; therefore there are at most 2 24 possible differences α (i) j at round i, and the vector Pr D i : α α (i) j has at most 2 24 entries. Moreover, each step has at most 3 active S-Boxes, therefore we have at most 2 9 possible transitions to consider for any fixed α (i) j . Using this truncated characteristic, the algorithm can compute Pr [D : α β] for a fixed α and for all differences β following D with at most 16 × 2 9 × 2 24 = 2 37 simple operations.

After running this computation with all input differences α allowed by the truncated characteristic, we identified 17512 differentials with probability higher than 2 -64 ; the best differential identified by this algorithm has a probability Pr [D : α β] ≈ 2 -61.52 . More precisely, the best differentials found are:

Pr 0000000000004607 16 0000040000004400 ≥ 2 -61.52

Pr 0000000000004607 16 0000060000004400 ≥ 2 -61.52

These probabilities correspond to a collection of 302116704 truncated characteristics. The use of multiple characteristics allows to improve the estimation of the probability of the differential from 2 -70 to 2 -61.52 .

Experimental Verification

In order to check that the algorithm is correct, we ran it with a reduced version of LAC with 8 rounds. We used the second half of the truncated differentials of Figure 3, with 17 active S-boxes. We found that this leads to differentials with probability at least 2 -29.76 :

Pr 0000000000006404 8 0000040000004400 ≥ 2 -29.76

Pr 0000000000006404 8 0000060000004400 ≥ 2 -29.76

In this case, the use a multiple characteristics allows to improve the estimation of the probability of the differential from 2 -34 (17 active S-Boxes) to 2 -29.76 . For this reduced version, we ran experiments with 2 40 random plaintext pairs following the first differential, and random round keys. We detected 1204 pairs with the expected output difference, which match very closely our prediction (2 40 • 2 -29.76 ≈ 1209). This indicates that our computation is correct, and the lower bound is quite tight in this case.

Conclusion

Our analysis shows that there exists differentials for the full G function of LAC with probability higher than 2 -64 . This allows a simple forgery attack with probability higher than 2 -64 on the full version of LAC, contradicting the security claims. This shows that the security margin of LAC is insufficient.

Our analysis is based on aggregating a collection of characteristics following the same truncated characteristic. While each characteristic has a probability at most 2 -70 , a collection of characteristics can have a probability as high as 2 -61.52 , giving a lower bound on the probability of the corresponding differential.

Since this technique is relatively simple, we recommend all designers to check whether it can be applied to their designs.

Fig. 3 .

 3 Fig. 3. Truncated characteristic for LAC with 35 active S-boxes.


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

Generic Attacks against MAC Algorithms

Message Authentication Codes (MACs) are important cryptographic constructions, used to ensure the authenticity of messages. MACs can be built from scratch (SipHash, Chaskey), from block ciphers (CBC-MAC, PMAC), from hash functions (HMAC), or from universal hash functions (GMAC, Poly1305). Constructions based on a lower level primitive are usually studied with a provable security approach: for commonly used MAC algorithms, security proofs rule out any attack on the MAC with complexity less than 2 n/2 (the birthday bound), when using an ideal n-bit block cipher or compression function. On the other hand, a generic collision attack against iterated MACs by Preneel and van Oorschot [8] using 2 n/2 queries show that the security proofs are tight.

The security of MAC algorithms seems to be well understood, but the generic attack of Preneel and van Oorschot is only an existential forgery attack, and stronger attacks (e.g. key-recovery attacks) are usually more expensive. In order to evaluate the security of common MAC algorithms below the birthday bound, we now focus on generic attacks, rather than on security proofs. The two approaches are complementary: generic attacks yields upper bounds on the security of a mode, and security proofs yield a lower bound. It is important to comin both, because constructions with a similar security proof can actually have a very different loss of security after the birthday bound.

For instance, there is a collision-based almost universal forgery attack against several CBC-MAC variants with birthday complexity [START_REF] Jia | Distinguishing and Second-Preimage Attacks on CBC-Like MACs[END_REF]. There is also an attack with birthday complexity recovering the secret mask in PMAC using collisions [START_REF] Lee | Forgery and Key Recovery Attacks on PMAC and Mitchell's TMAC Variant[END_REF]; this implies a universal forgery attack. More recently, a similar attack was shown against AEZ v3, but it yields a full key-recovery attack because of the way the secret mask is derived from the master key [START_REF] Fuhr | Collision Attacks against CAESAR Candidates[END_REF].

Hash-based MACs also have varying security beyond the birthday bound. The main constructions process the message with an unkeyed iteration, and use the key only in the initialization (secret-prefix MAC), in the finalization (secret-suffix MAC), or both in the initialization and finalization (HMAC, envelope MAC, sandwich MAC). All these constructions are good MACs when used with a random oracle, but they offer different levels of security in practice. Constructions using the key only in the finalization are much less secure, because collisions in the hash function directly lead to forgeries independently of the key. In particular, these collisions can be computed offline, and do not require any queries to a MAC oracle. Secret-suffix MAC and envelope MAC are also susceptible to a key-recovery attack based on collisions with partial blocks [START_REF] Preneel | On the Security of Two MAC Algorithms[END_REF]. Interestingly, the key-recovery attack can be applied to envelope MAC but not to sandwich MAC, although the construction are very close and have a similar security proof.

Over the last years, a series of papers have studied more complex generic attacks against HMAC and similar hash-based MAC algorithms [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]. This proved that distinguishing-H, state-recovery, and universal forgery attacks against HMAC require less than 2 n operations, contrary to what was previously assumed. The first attacks used the structure of the cycle graph of random functions in an elegant way to build a distinguishing-H and state-recovery attack with complexity 2 n/2 [START_REF] Leurent | New Generic Attacks against Hash-Based MACs[END_REF]. Variants with short messages were also given, using the entropy loss of random functions (with complexity 2 2n/3 ), and later extended to HAIFA hash functions (with complexity 2 4n/5 ) [START_REF] Dinur | Improved Generic Attacks against Hash-Based MACs and HAIFA[END_REF]. Surprisingly, extensions of those techniques also lead to universal forgery attacks against long messages [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]. In addition, the state recovery attacks can be extended to key-recovery attacks for HMAC based on a hash function with an internal checksum. In particular, this gives a key-recovery attack with complexity 2 192 against HMAC-GOST (with n = 256), and 2 419 against HMAC-Streebog (with n = 512).

All those examples show a large variety in the attack techniques and complexity, with several key-recovery attacks more efficient than exhaustive search. This highlights the importance of studying generic attacks in addition to the provable security driven approach to the design of MAC algorithms.