Charles Bouillaguet
email: charles.bouillaguet@ens.fr

Orr Dunkelman
email: orr.dunkelman@weizmann.ac.il

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

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

Attacks on Hash Functions based on Generalized Feistel Application to Reduced-Round Lesamnta and SHAvite-3 512

In this paper we study the strength of two hash functions which are based on Generalized Feistels. We describe a new kind of attack based on a cancellation property in the round function. This new technique allows to efficiently use the degrees of freedom available to attack a hash function. Using the cancellation property, we can avoid the non-linear parts of the round function, at the expense of some freedom degrees. Our attacks are mostly independent of the round function in use, and can be applied to similar hash functions which share the same structure but have different round functions. We start with a 22-round generic attack on the structure of Lesamnta, and adapt it to the actual round function to attack 24-round Lesamnta (the full function has 32 rounds). We follow with an attack on 9-round SHAvite-3 512 which also works for the tweaked version of SHAvite-3 512.

Introduction

Many block ciphers and hash functions are based on generalized Feistel constructions. In this paper we treat such generalized Feistel constructions and especially concentrate on the case where an n-bit round function is used in a 4n-bit structure. Two of these constructions, shown at Figure 1,1 used in the Lesamnta and the SHAvite-3 512 hash functions, are the main focus of this paper.

S T U V S T U V Ki F Lesamnta structure V U T S V U T S Ki K ′ i F ′ F SHAvite-3 512 structure
Fig. 1. The Generalized Feistel Constructions Studied in this paper While in the ideal Luby-Rackoff case, the round functions are independent random functions, in practice, most round functions F (k, x) are usually defined as P (k ⊕ x), where P is a fixed permutation (or function). Hence, we introduce several attacks which are based on cancellation property: if the fixed function P accepts twice the same input, it produces twice the same output. In a hash function setting, as there is no secret key, the adversary may actually make sure that the inputs are the same.

For Lesamnta we start with generic attacks that work independent of the actual P in use, but then use the specific properties of Lesamnta's round functions to offer better attacks. The attack on SHAvite-3 512 is a more complicated one, following the more complex round functions (and the structure which uses two functions in each round), but at the same time, is of more interest as SHAvite-3 512 is still a SHA3 candidate.

Overview of the Attacks

Our attacks are based on a partial preimage attack, i.e. we can construct specific inputs where part of the output H is equal to a target value H. To achieve such a partial preimage attack, we use truncated differentials built with the cancellation property, and we express the constraints needed on the state of the Feistel network in order to have the cancellation with probability one. We use degrees of freedom in the inputs of the compression function to satisfy those constraints. Then, we can compute some part of the output as a function of some of the remaining degrees of freedom, and try to invert the equation. The main idea is to obtain a simple equation that can be easily inverted using cancellations to limit the diffusion.

A partial preimage attack on the compression function allows to choose k bits of the output for a cost of 2 t (with t < k), while the remaining n -k bits are random. We can use such an attack on the compression function to target the hash function itself, in several scenarios. Preimage Attacks By repeating such an attack 2 n-k times, we can obtain a full preimage attack on the compression function, with complexity 2 n+t-k . This preimage attack on the compression function can be used for a second preimage attack on the hash function with complexity 2 n+(t-k)/2 using a standard unbalanced meet-in-the middle [START_REF] Lai | Hash Function Based on Block Ciphers[END_REF]. Note that 2 n+(t-k)/2 < 2 n if t < k.

Moreover, we point out that Lesamnta is built following the Matyas-Meyer-Oseas construction, i.e. the chaining value is used as a key, and the message enters the Feistel rounds. Since our partial preimage attack does not use degrees of freedom in the key (we only need the key to be known, not chosen), we can use a chaining value reached from the IV as the key. We have to repeat the partial preimage attack with many different keys in order to build a full preimage, but we can use a first message block to randomize the key. This gives a second preimage attack on the hash function with complexity 2 t+n-k .

Collision Attacks

The partial preimage attack can also be used to find collisions in the compression function. By generating 2 (n-k)/2 inputs where k bits of the output are fixed to a common value, we expect a collision thanks to the birthday paradox. This collision attack on the compression function costs 2 t+(n-k)/2 . If t < k/2, this is more efficient than a generic birthday attack on the compression function.

If the compression function is built with the Matyas-Meyer-Oseas mode, like Lesamnta, this attack translates to a collision attack on the hash function with the same complexity. However, if the compression function follows the Davies-Meyer mode, like SHAvite-3 , this does not translate to an attack on the hash function.

Our results

The first candidate for the technique is the Lesamnta hash function. The best known generic attack against this structure is a 16-round attack by Mendel described in the submission document of Lesamnta [START_REF] Hirose | SHA-3 Proposal: Lesamnta[END_REF]. Using a cancellation property, we extend this attack to a generic attacks on 22-round Lesamnta. The attack allows to fix one of the output words for an amortized cost of 1, which gives collisions in time 2 3n/8 and second preimages in time 2 3n/4 for Lesamnta-n. Moreover, the preimage attack can be extended to 24 rounds using 2 n/4 memory. We follow with adaptations of the 24-round attacks without memory using specific properties of Lesamnta's round function.

The second target for our technique is the hash function SHAvite-3 512 . We show a 9-round attack using a cancellation property on the generalized Feistel structure of SHAvite-3 512 . The attack also works for the tweaked version of SHAvite-3 512 , and allows fixing one out of the four output words. This allows a second preimage attack on 9-round SHAvite-3 512 that takes about 2 448 time. Note that this attack has recently been improved in a follow-up work [START_REF] Gauravaram | Cryptanalysis of the 10-Round Hash and Full Compression Function of SHAvite[END_REF]. First a new technique was used to add one extra round at the beginning, leading to attacks on 10 rounds of the compression function. Second, a pseudo-attack against the full SHAvite-3 512 is described, using additional degrees of freedom in the salt input. The follow-up work has been published first because of calendar issues, but it is heavily based on this work which was available as a preprint to the authors of [START_REF] Gauravaram | Cryptanalysis of the 10-Round Hash and Full Compression Function of SHAvite[END_REF]. Moreover, in this paper, we describe a more efficient way to find a suitable key for the attack, which improves the 10-round attack of [START_REF] Gauravaram | Cryptanalysis of the 10-Round Hash and Full Compression Function of SHAvite[END_REF].

Finally, we show some applications to block ciphers. We describe an integral attack on 21 rounds of the inner block cipher of Lesamnta using a cancellation property, and a new truncated differential for SMS4 .

The paper is organized as follows. Section 2 explains the basic idea of our cancellation attacks. Our results on Lesamnta are presented in Section 3, while application to SHAvite-3 512 is discussed in Section 4. Finally, application to the inner block cipher of Lesamnta is shown in Appendix A, while an attack on SMS4 is described in Appendix B.These results are summarized in Section 5.

The Cancellation Property

In this paper we apply cancellation cryptanalysis to generalized Feistel schemes. The main idea of this technique is to impose constraints on the values of the state in order to limit the diffusion in the Feistel structure. When attacking a hash function, we have many degrees of freedom from the message and the chaining value, and it is important to find efficient ways to use those degrees of freedom.

Table 1. Cancellation property on Lesamnta. On the left side, we have full diffusion after 9 rounds. On the right side, we use the cancellation property to control the diffusion of the differences.

i Si Ti Ui Vi Si Ti Ui Vi 0 x - - - x - - - 1 - x - - - x - - 2 - - x - - - x - 3 y1 - - x x → y1 y - - x x → y 4 x y1 - - x y - - 5 - x y1 - - x y - 6 z - x y1 y1 → z z - x y y → z 7 y ′ z - x x → y2, y ′ = y1 ⊕ y2 - z - x x → y 8 x y ′ z - x - z - 9 w x y ′ z z → w w x - z z → w
Table 1 shows the diffusion of a single difference in Lesamnta. After 9 rounds, all the state words are active. However, we note that if the transitions x → y 1 at rounds 3 and x → y 2 at round 7 actually go to the same y, i.e. y 1 = y 2 , this limits the diffusion. In the ideal case, the round functions are all independent, and the probability of getting the same output difference is very small. However, in practice, the round functions are usually all derived from a single fixed permutation (or function). Therefore, if we add some constraints so that the input values of the fixed permutation at round 3 and 7 are the same, then we have the same output values, and therefore the same output difference with probability one. This is the cancellation property.

Table 2. Cancellation property on SHAvite-3 512 . On the left side, we have full diffusion after 4 rounds. On the right side, we use the cancellation property to control the diffusion.

i Si Ti Ui Vi Si Ti Ui Vi 0 x - - - x - - - 1 - x - - - x - - 2 - y1 x - x → y1 - y x - x → y 3 - z y1 x y1 → z - z y x y → z 4 x w z y ′ x → y2, y ′ = y1 ⊕ y2 x w z - x → y
Similarly, Table 2 shows the diffusion of a difference in SHAvite-3 512 . If the transitions x → y 1 at round 2 and x → y 2 at round 4 actually go to the same y, we can limit the diffusion.

Our attacks use an important property of the Feistel schemes of Lesamnta and SHAvite-3 512 : the diffusion is relatively slow. When a difference is introduced in the state, it takes several rounds to affect the full state and two different round functions can receive the same input difference x. Note that the slow diffusion of Lesamnta is the basis of a 16-round attack in [START_REF] Hirose | SHA-3 Proposal: Lesamnta[END_REF] (recalled in Section 3.2), and the slow diffusion of SHAvite-3 512 gives a similar 8-round attack [START_REF]A preimage attack on 8-round SHAvite-3-512[END_REF]. Our new attacks can be seen as extensions of those.

We now describe how to enforce conditions of the state so as to have this cancellation with probability 1. Our attacks are independent of the round function, as long as all the round functions are derived from a single function as

F i (X i ) F (K i ⊕ X i ). 2.1 Generic Properties of F i (X i ) = F (K i ⊕ X i )
We assume that the round functions F i are built by applying a fixed permutation (or function) F to K i ⊕ X i , where K i is a round key and X i is the state input. This practice is common in many primitives like DES, SMS4 , GOST, or Lesamnta.

This implies the followings, for all i, j, k:

(i ) ∃c i,j : ∀x, F i (x ⊕ c i,j ) = F j (x). (ii ) ∀α, # x : F i (x) ⊕ F j (x) = α is even. (iii ) x F k F i (x) ⊕ F j (x) = 0. Property (i )
is the basis of our cancellation attack. We refer to it as the cancellation property. It states that if the inputs of two round functions are related by a specific fixed difference, then the outputs of both rounds are equal. The reminder of the paper is exploring this property.

Properties (ii ) and (iii ) can be used in an integral attack, as shown in Appendix A. Note that Property (ii ) is a well known fact from differential cryptanalysis.

Proof.

(i ) Set c ij = K i ⊕ K j . (ii ) If K i = K j , then ∀x, F i (x) ⊕ F j (x) = 0. Otherwise, let x be such that F i (x) ⊕ F j (x) = α. Then F i (x ⊕ K i ⊕ K j ) ⊕ F j (x ⊕ K i ⊕ K j ) = F j (x) ⊕ F i (x) = α.
Therefore x is in the set if and only if x ⊕ K i ⊕ K j is in the set, and all the elements can be grouped in pairs. (iii ) Each term F k (α) in the sum appears an even number of times following (ii ).

⊓ ⊔

2 a b c d 3 F2(c) ⊕ d a b c 4 F3(b) ⊕ c F2(c) ⊕ d a b 5 F4(a) ⊕ b F3(b) ⊕ c F2(c) ⊕ d a 6 F5(F2(c) ⊕ d) ⊕ a F4(a) ⊕ b F3(b) ⊕ c F2(c) ⊕ d 7 F6(F3(b) ⊕ c) ⊕ F2(c) ⊕ d F5(F2(c) ⊕ d) ⊕ a F4(a) ⊕ b F3(b) ⊕ c

Using the Cancellation Property

To better explain the cancellation property, we describe how to use it with the truncated differential of Table 1. In Table 3, we show the values of the registers during the computation of the truncated differential, starting at round 2 with (S 2 , T 2 , U 2 , V 2 ) = (a, b, c, d). To use the cancellation property, we want to make S 7 independent of c. Since we have S 7 = F 6 (F 3 (b) ⊕ c)⊕F 2 (c)⊕d, we can cancel the highlighted terms using property (i ). The dependency of S 7 on c disappears if

F 3 (b) = K 2 ⊕ K 6 , i.e. if b = F -1 3 (K 2 ⊕ K 6 ): S 7 = F 6 (F 3 (b) ⊕ c) ⊕ F 2 (c) ⊕ d = F (K 6 ⊕ F 3 (b) ⊕ c) ⊕ F (K 2 ⊕ c) ⊕ d = F (K 2 ⊕ c) ⊕ F (K 2 ⊕ c) ⊕ d = d.
Therefore, we can put any value c in U 2 , and it does not affect S 7 as long as we fix the value of

T 2 to be F -1 (K 2 ⊕ K 6 ) ⊕ K 3 .
Note that in a hash function, we can compute F -1 (K 2 ⊕ K 6 ) ⊕ K 3 since the keys are known to the adversary (or controlled by him), and we can choose to have this value in T 2 .

This shows the three main requirements of our cancellation attacks:

-The generalized Feistel structures we study have a relatively slow diffusion. Therefore, the same difference can be used as the input difference of two different round functions. -The round functions are built from a fixed permutation (or a fixed function), using a small round key. This differs from the ideal Luby-Rackoff case where all round functions are chosen independently at random. -In a hash function setting the key is known to the adversary, and he can control some of the inner values.

Note that some of these requirements are not strictly necessary. For example, we show a 21-round integral attack on Lesamnta, without knowing the keys in Section A. Moreover, in Section 4 we show attacks on 9-round SHAvite-3 512 , where the round functions use more keying material.

3 Application to Lesamnta

A Short Description of Lesamnta

Lesamnta is a hash function proposal by Hirose, Kuwakado, and Yoshida as a candidate in the SHA-3 competition [START_REF] Hirose | SHA-3 Proposal: Lesamnta[END_REF]. It is based on a 32-round unbalanced Feistel scheme with four registers used in MMO mode. The key schedule is also based on a similar Feistel scheme. The round function can be written as:

S i+1 = V i ⊕ F (U i ⊕ K i ) T i+1 = S i U i+1 = T i V i+1 = U i
Alternatively, we can write it with a single register X, equivalent to the original S

X i+4 = X i ⊕ F (X i+1 ⊕ K i+3 )
where K 0 , . . . , K 31 are round keys derived from the chaining value, and the state register X is initialized with the message in X -3 , X -2 , X -1 , X 0 . The output of the compression function is

X -3 ⊕ X 29 , X -2 ⊕ X 30 , X -1 ⊕ X 31 , X 0 ⊕ X 32 .

Previous Results on Lesamnta

The best known attack on Lesamnta is the self-similarity attack of [START_REF] Bouillaguet | Another Look at the Complementation Property[END_REF]. Following this attack, the designers have tweaked Lesamnta by changing the round constants [12]. In this paper we consider attacks that work with any round constants, and thus are applicable to the tweaked version as well.

Several attacks on reduced-round Lesamnta are presented in the submission document [START_REF] Hirose | SHA-3 Proposal: Lesamnta[END_REF]. A series of 16-round attacks for collisions and (second) preimage attacks are presented, all of which are based on the following 16-round truncated differential with probability 1:

i S i T i U i V i 0 x 1 x 2 x 3 x ⊕ x 4 1 x x 1 x 2 x 3 x 3 → x 4 2 - x x 1 x 2 x 2 → x 3 3 - - x x 1 x 1 → x 2 4 - - - x x → x 1 5 x - - - 6 - x - - 7 - - x - 8 ? - - x 9
x ? --11 -

x where2

x 3 = M 2 ⊕ F -1 (F (M 2 ⊕ K 0 ) ⊕ x 4 ) ⊕ K 0 , i.e. F 0 (U 0 ) ⊕ F 0 (U 0 ⊕ x 3 ) = x 4 x 2 = M 1 ⊕ F -1 (F (M 1 ⊕ K 1 ) ⊕ x 3 ) ⊕ K 1 , i.e. F 1 (U 1 ) ⊕ F 1 (U 1 ⊕ x 2 ) = x 3 x 1 = M 0 ⊕ F -1 (F (M 0 ⊕ K 2 ) ⊕ x 2 ) ⊕ K 2 , i.e. F 2 (U 2 ) ⊕ F 2 (U 2 ⊕ x 1 ) = x 2 x = (M 3 ⊕ F (M 2 ⊕ K 0 )) ⊕ F -1 (F (M 3 ⊕ K 3 ⊕ F (M 2 ⊕ K 0 )) ⊕ x 1 ) ⊕ K 3 , i.e. F 3 (U 3 ) ⊕ F 3 (U 3 ⊕ x ) = x 1
and M i are the corresponding message words of the message block. This truncated differential allows fixing the fourth output word to a constant value determined by the adversary using two queries to the compression function. One first picks a random message m, and computes the difference x 4 between the desired value H 4 and the actual value H 4 = V o ⊕ V 16 of the fourth output word. Since the key is known, it is easy to compute x 3 from x 4 , and similarly x 2 , x 1 and x, as shown above. Then, by picking m ′ = m ⊕ (x 1 , x 2 , x 3 , x ⊕ x 4 ), it is assured that the fourth output word is equal to H 4 .

This allows a collision attack (of expected time complexity 2 97 ) and second preimage attack (of expected time complexity 2 193 ). We note that this property is independent of F (as long as F is bijective), and can be applied even when the round functions are ideal independent permutations.

In the next sections we show new attacks using the cancellation property. We first show some attacks that are generic in F , as long as the round functions are defined as F i (X i ) = F (K i ⊕X i ), and then improved attacks using specific properties of the round functions of Lesamnta.

Generic Attacks

Our attacks are based on the differential of Table 4, which is an extension of the differential of Table 1. In this differential we use the cancellation property three times to control the diffusion. Note that we do not have to specify the values of y, z, w, r and t. This specifies a truncated differential for Lesamnta: starting from a difference (x, -, -, -), we reach a difference (?, ?, ?, x 1 ) after 22 rounds. In order to use this truncated differential in our cancellation attack, we use two important properties: first, by adding constraints on the state, the truncated differential is followed with probability 1; second, the transition x → x 1 is known because the key and values are known. Therefore, we can actually adjust the value of the last output word. In order to express the constraints that we need for the cancellation properties, we look at the values of the registers for this truncated differential. In Table 5, we begin at round 2 with (S 2 , T 2 , U 2 , V 2 ) = (a, b, c, d), and we compute the state values up to round 19. This is an extension of the values computed in Table 3.

Table 4. Cancellation Property on 22 Rounds of Lesamnta

i Si Ti Ui Vi 0 x - - - 1 - x - - 2 - - x - 3 y - - x x → y 4 x y - - 5 - x y - 6 z - x y y → z 7 - z - x x → y 8 x - z - 9 w x - z z → w 10 z w x - 11 x1 z w x x → x1 12 r x1 z w w → x ⊕ r 13 - r x1 z z → w 14 ? - r x1 15 x1 + t ? - r
We can see that we have

X 19 = F (c ⊕ α) ⊕ β, where α = K 10 ⊕ F 7 (F 4 (a) ⊕ b) ⊕ F 3 (b) and β = d
provided that (a, b, d) is the unique triplet satisfying the following cancellation conditions:

Round 7: we have F 6 (F 3 (b) ⊕ c) ⊕ F 2 (c). They cancel if: F 3 (b) = c 2,6 = K 2 ⊕ K 6 i.e. b = F -1 3 (K 2 ⊕ K 6 ) Round 13: we have F 12 (F 9 (d) ⊕ F 5 (F 2 (c) ⊕ d) ⊕ a) ⊕ F 8 (F 5 (F 2 (c) ⊕ d) ⊕ a). They cancel if: F 9 (d) = c 8,12 = K 8 ⊕ K 12 i.e. d = F -1 9 (K 8 ⊕ K 12 ) Round 19: we have F 18 (F 15 (F 4 (a) ⊕ b) ⊕ X 12 ) ⊕ F 14 (X 12 ). They cancel if: F 15 (F 4 (a) ⊕ b) = c 14,18 = K 14 ⊕ K 18 i.e. a = F -1 4 (F -1 15 (K 14 ⊕ K 18 ) ⊕ b) Note that a,
i Xi(= Si) -1 d 0 c 1 b 2 a 3 F2(c) ⊕ d 4 F3(b) ⊕ c 5 F4(a) ⊕ b 6 F5(F2(c) ⊕ d) ⊕ a 7 F6(F3(b) ⊕ c) ⊕ F2(c) ⊕ d 8 F7(F4(a) ⊕ b) ⊕ F3(b) ⊕ c 9 F8(F5(F2(c) ⊕ d) ⊕ a) ⊕ F4(a) ⊕ b 10 F9(d) ⊕ F5(F2(c) ⊕ d) ⊕ a 11 F10(F7(F4(a) ⊕ b) ⊕ F3(b) ⊕ c) ⊕ d 12 F11(F8(F5(F2(c) ⊕ d) ⊕ a) ⊕ F4(a) ⊕ b) ⊕ F7(F4(a) ⊕ b) ⊕ F3(b) ⊕ c 13 F12(F9(d) ⊕ F5(F2(c) ⊕ d) ⊕ a) ⊕ F8(F5(F2(c) ⊕ d) ⊕ a) ⊕ F4(a) ⊕ b 14 ? 15 F14(X12) ⊕ F10(F7(F4(a) ⊕ b) ⊕ F3(b) ⊕ c) ⊕ d 16 F15(F4(a) ⊕ b) ⊕ X12 17 ? 18 ? 19 F18(F15(F4(a) ⊕ b) ⊕ X12) ⊕ F14(X12) ⊕ F10(F7(F4(a) ⊕ b) ⊕ F3(b) ⊕ c) ⊕ d

22-round Attacks

The truncated differential of Table 4 can be used to attack 22-round Lesamnta. We start with the state at round 2 (S 2 , T 2 , U 2 , V 2 ) = (a, b, c, d) satisfying the cancellation properties, and we can compute how the various states depend on c, as shown in Table 6. A dash (-) is used to denote a value that is independent of c. We know exactly how c affects the last output word, and we can select c in order to get a specific value at the output. Suppose we are given a set of subkeys, and a target value H for the fourth output word. Then the attack proceeds as follows:

1. Set a, b, and d to the values that allow the cancellation property.

Then we have V 0 ⊕ V 22 = η ⊕ F (c ⊕ α) ⊕ β, as shown in Table 6.

0 c - - η 1 - c - - 2 - - c - 2-19
Repeated Cancellation Property: Table 5 19

F (c ⊕ α) ⊕ β ? ? ? 20 ? F (c ⊕ α) ⊕ β ? ? 21 ? ? F (c ⊕ α) ⊕ β ? 22 ? ? ? F (c ⊕ α) ⊕ β FF ? ? ? η ⊕ F (c ⊕ α) ⊕ β
η, α and β can be computed from a, b, d and the key:

η = b ⊕ F0(a ⊕ F3(d)), α = K11 ⊕ F8(F5(a) ⊕ b) ⊕ F4(b), β = d.
, V 4 ) = (a, b, c, d) i Xi -3 d ⊕ F0(c ⊕ F1(b ⊕ F2(a ⊕ F3(d)))) -2 c ⊕ F1(b ⊕ F2(a ⊕ F3(d))) -1 b ⊕ F2(a ⊕ F3(d)) 0 a ⊕ F3(d) 1 d 2 c 3 b 4 a V0 = X-3 = λ ⊕ F0(c ⊕ γ), with λ = d 2. Compute c as F -1 (H ⊕ η ⊕ β) ⊕ α.
3. This sets the state at round 2: (S 2 , T 2 , U 2 , V 2 ) (a, b, c, d).

With this state, we have V 0 ⊕ V 22 = H. 4. Compute the round function backwards up to round 0, to get the input (S 0 , T 0 , U 0 .V 0 ). This costs less than one compression function call, and does not require any memory.

For a given chaining value (i.e. a set of subkeys), this algorithm can only output one message. To build a full preimage attack or a collision attack on the compression function, this has to be repeated with random chaining values. Since the attack works for any chaining value, we can build attacks on the hash function using a prefix block to randomize the chaining value. This gives a collision attack with complexity 2 96 (2 192 for Lesamnta-512), and a second-preimage attack with complexity 2 192 (2 384 for Lesamnta-512).

24-round Attacks

We can add two rounds at the beginning of the truncated differential at the cost of some memory. The resulting 24-round differential is given in Table 8. The output word we try to control is equal to F (c ⊕ γ) ⊕ F (c ⊕ α), for some constants α, and γ that depend on the chaining value (note that β = λ in Table 8). We define a family of functions h µ (x) = F (x) ⊕ F (x ⊕ µ), and for a given target value H, we tabulate ϕ H (µ) = h -1 µ (H). For each µ, ϕ H (µ) is a possibly empty set, but the average size is one (the non-empty values form a partition of the input space). In the special case where H = 0, ϕ 0 (µ) is empty for all µ = 0, and ϕ 0 (0) is the full space.

We store ϕ H in a table of size 2 n/4 , and we can compute it in time 2 n/4 by looking for values such that F (x) ⊕ F (y) = H (this gives ϕ H (x ⊕ y) = x). Using this table, we are able to choose one output word just like in the 22-round attack.

We start with a state (S 4 , T 4 , U 4 , V 4 ) = (a, b, c, d) such that a, b, d satisfy the cancellation conditions, and we compute α, β, γ, λ.

If we use c = u ⊕ α, where u ∈ ϕ H (α ⊕ γ) = h -1 α⊕γ (H),
i Si Ti Ui Vi 0 - - c ⊕ γ F (c ⊕ γ) ⊕ λ 1 - - - c ⊕ γ 2 c - - - 3 - c - - 4 - - c -

4-21

Repeated Cancellation Property: Table 5 21

F (c ⊕ α) ⊕ β ? ? ? 22 ? F (c ⊕ α) ⊕ β ? ? 23 ? ? F (c ⊕ α) ⊕ β ? 24 ? ? ? F (c ⊕ α) ⊕ β
α, β, γ and λ can be computed from a, b, d and the key by:

α = K13 ⊕ F10(F7(a) ⊕ b) ⊕ F6(b), β = d and γ = F1(b ⊕ F2(a ⊕ F3(d))), λ = d
we have:

V 0 ⊕ V 24 = F (c ⊕ γ) ⊕ F (c ⊕ α) = F (u ⊕ α ⊕ γ) ⊕ F (u) = h α⊕γ (u) = H
On average this costs one compression function evaluation to find a n/4-bit partial preimage.

If the target value is 0, this only succeeds if α ⊕ γ = 0, but in this case it gives 2 n/4 solutions. This gives a preimage attack with complexity 2 3n/4 using 2 n/4 memory. Note that it is possible to make a time-memory trade-off with complexity 2 n-k using 2 k memory for k < n/4.

Dedicated 24-round Attacks on Lesamnta

We now describe how to use specific properties of the round functions of Lesamnta to remove the memory requirement of our 24-round attacks.

Neutral Subspaces in F 256 The F function of Lesamnta-256 has a property that limits the difference propagation to linear subspaces. Namely, we identified two linear subspaces Γ and Λ for which

x ⊕ x ′ ∈ Γ ⇒ F (x) ⊕ F (x ′ ) ∈ Λ
The subspaces Γ and Λ have dimensions of 16 and 48, respectively. The AES-like round function of Lesamnta-256 achieves full diffusion of the values after its four rounds, but some linear combinations of the output are not affected. Starting from a single active diagonal, we have:

SB SR MC SB SR MC SB SR MC SB SR MC
All the output bytes are active, but there are some linear relations between them. More precisely, the inverse MixColumns operation leads to a difference with two inactive bytes. Therefore, we can equivalently say that there are 16 linear relations of the output bits that are not affected by 16 input bits.

Collision and Second Preimage Attacks on Lesamnta-256 Using this property, we can choose 16 linear relations of the output of the family of function h µ , or equivalently, choose 16 linear relations of the output of the compression function.

Let Λ be a supplementary subspace of Λ. Any 64-bit value x can be written as x = x Λ + x Λ, where x Λ ∈ Λ and x Λ ∈ Λ. We show how to find values x such that h µ (x) Λ = H Λ for an amortized cost of one, without memory:

1. Compute h µ (u) for random u's until h µ (u) Λ = H Λ 2. Far all v in Γ , we have h µ (u + v) Λ = H Λ
This gives 2 16 messages with 16 chosen relations for a cost of 2 16 . It allows a second-preimage attack on 24-round Lesamnta-256 with complexity 2 240 , and a collision attack with complexity 2 120 , both memoryless.

Symmetries in F 256 and F 512 The AES round function has strong symmetry properties, as studied in [START_REF] Le | Complementation-Like and Cyclic Properties of AES Round Functions[END_REF]. The round function F of Lesamnta is heavily inspired by the AES round, and has similar symmetry properties. More specifically, if an AES state is such that the left half is equal to the right half, then this property still holds after any number of SubBytes, ShiftRows, and MixColumns operations. Explicitly, after one AES-like round of Lesamnta-256, we have:

w x w x y z y z AES-like ------→ w ′ x ′ w ′ x ′ y ′ z ′ y ′ z ′ where w ′ = 2 • S[w] ⊕ S[z] x ′ = 2 • S[x] ⊕ S[y] y ′ = S[w] ⊕ 2 • S[z] z ′ = S[x] ⊕ 2 • S[y]
And similarly in Lesamnta-512:

w x w x y z y z s t s t u v u v AES ---→ w ′ x ′ w ′ x ′ y ′ z ′ y ′ z ′ s ′ t ′ s ′ t ′ u ′ v ′ u ′ v ′
When we consider the F functions of Lesamnta, have that:

if x ⊕ K i is symmetric, then F i (x) = F (x ⊕ K i ) is also symmetric.
More precisely, if we denote the set of symmetric values by S, we use the following property:

x, x ′ ∈ S ⇒ F (x) ⊕ F (x ′ ) ∈ S
Collision Attacks on Lesamnta-256 and Lesamnta-512 This property can be used for an improved collision attack. As seen earlier we have V 0 ⊕ V 24 = F (c ⊕ γ) ⊕ F (c ⊕ α). In order to use the symmetry property, we first select random chaining values, and we compute the value of α and γ until α ⊕ γ is symmetric (α ⊕ γ ∈ S). Then, if we select c such that c ⊕ γ ∈ S, we also have c ⊕ α ∈ S, and this gives V 0 ⊕ V 24 ∈ S.

We need to try 2 32 (respectively, 2 64 for Lesamnta-512) random chaining values in order to get α ⊕ γ ∈ S, but once we have a good chaining value, we can use it with 2 32 (respectively, 2 64 ) messages, and in each one V 0 ⊕ V 24 ∈ S. So we can have 32 equalities between output bits (respectively, 64 equalities) for an average cost of one compression function call. This leads to a collision attack with complexity 2 112 for Lesamnta-256, and 2 224 for Lesamnta-512. In Appendix C, we give an example of inputs where 64 bits of the output are set to 1 using this property.

4 Application to SHAvite-3 512 SHAvite-3 is a hash function designed by Biham and Dunkelman for the SHA-3 competition [START_REF] Biham | The SHAvite-3 Hash Function[END_REF]. It is based on a generalized Feistel construction with an AES-based round function, used in Davies-Meyer mode. In this section we study SHAvite-3 512 , the version of SHAvite-3 designed for output size of 257 to 512 bits. The cancellation property can not be used on SHAvite-3 256 because the Feistel structure is different and has a faster diffusion. We describe an attack on the SHAvite-3 512 hash function reduced to 9 rounds out of 14. An earlier variant of our attack was later extended in [START_REF] Gauravaram | Cryptanalysis of the 10-Round Hash and Full Compression Function of SHAvite[END_REF] to a 10-round attack. We note that our improved 9-round attack can be used to offer an improved 10-round attack. The compression function of SHAvite-3 512 accepts a chaining value of 512 bits, a message block of 1024 bits, a salt of 512 bits, and a bit counter of 128 bits. As this is a construction, the message block, the salt, and the bit counter enter the key schedule algorithm of the underlying block cipher. The key schedule algorithm transforms them into 112 subkeys of 128 bits each. The chaining value is then divided into four 128-bit words, and at each round two words enter the nonlinear round functions and affect the other two:

Yi+1 Xi Xi+1 Yi Yi Xi-1 Xi Yi-1 Ki K ′ i F ′ F Xi+1 = Yi-1 ⊕ Fi(Xi) Yi+1 = Xi-1 ⊕ F ′ i (Yi) Xi-1 = Yi+1 ⊕ F ′ i (Yi) Yi-1 = Xi+1 ⊕ Fi(Xi)
S i+1 = V i T i+1 = S i ⊕ F ′ i (T i ) U i+1 = T i V i+1 = U i ⊕ F i (V i )
The nonlinear function F and F ′ are composed of four full rounds of AES, with 4 subkeys from the message expansion:

F i (x) = P (k 3 0,i ⊕ P (k 2 0,i ⊕ P (k 1 0,i ⊕ P (k 0 0,i ⊕ x)))) F ′ i (x) = P (k 3 1,i ⊕ P (k 2 1,i ⊕ P (k 1 1,i ⊕ P (k 0 1,i ⊕ x))))
where P is one AES round (without the AddRoundKey operation).

In this section we use an alternative description of SHAvite-3 512 with only two variables per round, as shown in Figure 2. We have

S i = Y i-1 T i = X i U i = X i-1 V i = Y i
The message expansion is detailed in Appendix D. Note that with the original key schedule of SHAvite-3 , a specific set of message, salt, and counter leads to all the subkeys being zero [START_REF] Nandi | OFFICIAL COMMENT: SHAvite-3[END_REF][START_REF] Peyrin | Chosen-salt, chosen-counter, pseudo-collision on SHAvite-3 compression function[END_REF]. Thus, the key schedule was tweaked for the second round of the SHA-3 competition. Our attack applies both to the original message expansion and to the tweaked version.

Cancellation Attacks on SHAvite-3 512

The cancellation path is described in Table 9, which is an extension of Table 2. We use the cancellation property twice to control the diffusion. Note that we do not have to specify the values of y, z, and w. Like in the Lesamnta attack, this path is a truncated differential, and we use constraints on the state to enforce that it is followed. Moreover, the transitions x → x 1 and x 1 → x 2 are known because the key is known.

Note that the round functions of SHAvite-3 512 are not defined as F (k, x) = P (k ⊕ x) for a fixed permutation P . Instead, each function takes 4 keys and it is defined as:

F (k 0 i , k 1 i , k 2 i , k 3 i , x) = P (k 3 i ⊕ P (k 2 i ⊕ P (k 1 i ⊕ P (k 0 i ⊕ x))))
where P is one AES round. In order to apply the cancellation property to SHAvite-3 512 , we need that the subkeys k 1 , k 2 , k 3 of two functions be equal, so that F i (x) collapses to P ′ (k 0 i ⊕ x) and F j to P ′ (k 0 j ⊕ x), where P ′ (x) P (k

3 i ⊕ P (k 2 i ⊕ P (k 1 i ⊕ P (x)))) = P (k 3 j ⊕ P (k 2 j ⊕ P (k 1 j ⊕ P (x)))).
Table 9. Cancellation Property on 9 Rounds of SHAvite-3 512 i Si Ti Ui Vi

0 ? x2 ? x 1 x - x2 x1 2 x1 x - - x1 → x2 3 - - x - x → x1 4 - - - x 5 x - - y x → y 6 y x - z y → z 7 z - x w x → y, z → w 8 w z - ? 9 ? - z ? z → w FF ? ? ?
Table 10. Values of the Registers for the 9-round Cancellation Property of SHAvite-3

512 i Xi/Yi X0 b ⊕ F3(c) ⊕ F ′ 1 (c ⊕ F2(d ⊕ F ′ 3 (a))) Y0 d ⊕ F ′ 3 (a) ⊕ F1(a ⊕ F ′ 2 (b ⊕ F3(c))) X1 a ⊕ F ′ 2 (b ⊕ F3(c)) Y1 c ⊕ F2(d ⊕ F ′ 3 (a)) X2 d ⊕ F ′ 3 (a) Y2 b ⊕ F3(c) X3 c Y3 a X4 b Y4 d X5 a ⊕ F4(b) Y5 c ⊕ F ′ 4 (d) X6 d ⊕ F5(a ⊕ F4(b)) Y6 b ⊕ F ′ 5 (c ⊕ F ′ 4 (d)) X7 c ⊕ F ′ 4 (d) ⊕ F6(d ⊕ F5(a ⊕ F4(b))) Y7 a ⊕ F4(b) ⊕ F ′ 6 (b ⊕ F ′ 5 (c ⊕ F ′ 4 (d))) X8 b ⊕ F ′ 5 (c ⊕ F ′ 4 (d)) ⊕ F7(c) Y8 d ⊕ F5(a ⊕ F4(b)) ⊕ F ′ 7 (a ⊕ F4(b) ⊕ F ′ 6 (b ⊕ F ′ 5 (c ⊕ F ′ 4 (d)))) X9 a ⊕ F4(b) ⊕ F ′ 6 (b ⊕ F ′ 5 (c ⊕ F ′ 4 (d))) ⊕ F8(b ⊕ F ′ 5 (c ⊕ F ′ 4 (d)) ⊕ F7(c))
In order to express the constraints needed for the cancellation properties, we look at the values of the registers for this truncated differential. In Table 10, we begin at round 4 with (S 4 , T 4 , U 4 , V 4 ) = (Y 3 , X 4 , X 3 , Y 4 ) = (a, b, c, d), and we compute up to round 9.

We have a cancellation property on 9 rounds under the following conditions:

Round 7 We have F ′ 4 (d) ⊕ F 6 (d ⊕ F 5 (a ⊕ F 4 (b))). They cancel if: F 5 (a ⊕ F 4 (b)) = k 0 1,4 ⊕ k 0 0,6 and (k 1 1,4 , k 2 1,4 , k 3 1,4 ) = (k 1 0,6 , k 2 0,6 , k 3 0,6 ). Round 9 We have F ′ 6 (b ⊕ F ′ 5 (c ⊕ F ′ 4 (d))) ⊕ F 8 (b ⊕ F ′ 5 (c ⊕ F ′ 4 (d)) ⊕ F 7 (c)). They cancel if: F 7 (c) = k 0 1,6 ⊕ k 0 0,8 and (k 1 1,6 , k 2 1,6 , k 3 1,6 ) = (k 1 0,8 , k 2 0,8 , k 3 0,8
). Therefore, the truncated differential is followed if:

F 5 (a ⊕ F 4 (b)) = k 0 1,4 ⊕ k 0 0,6 F 7 (c) = k 0 1,6 ⊕ k 0 0,8 (C0) (k 1 1,4 , k 2 1,4 , k 3 1,4 ) = (k 1 0,6 , k 2 0,6 , k 3 0,6 ) (k 1 1,6 , k 2 1,6 , k 3 1,6 ) = (k 1 0,8 , k 2 0,8 , k 3 0,8 ) (C1)
The constraints for the cancellation at round 7 are easy to satisfy and allow a 7-round attack on SHAvite-3 512 . However, for a 9-round attack we have more constraints on the subkeys, and this requires special attention.

Dealing with the Key Expansion

Let us outline an algorithm to find a suitable message (recall that SHAvite-3 512 is used in a Davies-Meyer mode) for a given salt and counter value. We have to solve a system involving linear and non-linear equations, and we use the fact that the system is almost triangular. We note that it might be possible to improve our results using the technique of Khovratovich, Biryukov and Nikolić [START_REF] Khovratovich | Speeding up Collision Search for Byte-Oriented Hash Functions[END_REF] to find a good message efficiently.

For the cancellation attack on 9-round SHAvite-3 512 , we need to satisfy a 768-bit condition on the subkeys, i.e.: Propagation of the Constraints First, we propagate the constraints and deduce new equalities between the variables. Figure 3 shows the initial constraints and the propagated constraints.

(k 1 1,4 , k 2 1,4 , k 3 1,4 ) = (k 1 0,6 , k 2 0,6 , k 3 0,6 ) (k 1 1,6 , k 2 1,6 , k 3 1,6 ) = (k 1 0,8 , k

9-round Attacks

The cancellation property allows to find a key/message pair with a given value on the last 128 bits. The attack is the following: first find a message that fulfills the conditions on the subkeys, and set a, b and c at round 4 satisfying the cancellation conditions (C0). Then the second output word is:

T 9 ⊕ T 0 = X 9 ⊕ X 0 = a ⊕ F 4 (b) ⊕ b ⊕ F 3 (c) ⊕ F ′ 1 c ⊕ F 2 (d ⊕ F ′ 3 (a)) If we set d = F -1 2 F ′-1 1 H ⊕ a ⊕ F 4 (b) ⊕ b ⊕ F 3 (c) ⊕ c ⊕ F ′ 3 (a)
we have X 9 ⊕ X 0 = H. Each key (message) can be used with 2 128 different a,b,c, and the cost of finding a suitable key is 2 96 . Hence, the amortized cost for finding a 128-bit partial preimage is one compression function evaluation. The cost of finding a full preimage for the compression function is 2 384 , as described in Algorithm 1.

Algorithm 1 SHAvite-3 512 cancellation attack on 9 rounds

Input: Target value H Output: A message M and a chaining value X s.t. F (X, M ) = H Running Time: 2 384 1: loop 2: Find M such that (k 1 1,4 , k 2 1,4 , k 3 1,4 ) = (k 1 0,6 , k 2 0,6 , k 3 0,6 ) and (k 1 1,6 , k 2 1,6 , k 3 1,6 ) = (k 1 0,8 , k 2 0,8 , k 3 0,8 ) 3: c ← F -1 7 (k 0 1,6 ⊕ k 0 0,8 ) 4:
for all a do 5:

b ← F -1 4 (F -1 5 (k 0 1,4 ⊕ k 0 0,6 ) ⊕ a) 6: Compute d as F -1 2 " F ′-1 1 `H4 ⊕ a ⊕ F4(b) ⊕ b ⊕ F3(c) ´⊕ c " ⊕ F ′ 3 (a) 7:
Compute 4 rounds backwards and 5 rounds forwards from a, b, c, d 8:

Then H4 = X0 ⊕ X9 = H4 9:

if H = H then 10:

return X, M 11:

end if 12:

end for 13: end loop Second Preimage Attack on the Hash Function We can use the preimage attack on the compression function to build a second preimage attack on the hash function reduced to 9 rounds. Using a generic unbalanced meet-in-the-middle attack the complexity is about 2 448 compression function evaluations and 2 64 memory. Note that we cannot find preimages for the hash function because we cannot find correctly padded message blocks.

Conclusion

In this paper we explore new ways to use efficiently degree of freedom in generalized Feistel structures. In addition to the attacks on Lesamnta and SHAvite-3 512 , we describe an attack against SMS4 in Appendix B. We summarize the obtained attacks in Tables 11,12, and 13. A An Integral Attack against 21-Round Lesamnta

In this section, we show the applicability of the cancellation technique to block ciphers analysis by giving an application to the implicit block cipher of Lesamnta. The main difference with the hash function attacks is that in a block cipher the attacker does not know the key, and cannot build a message satisfying the cancellation conditions. Therefore, we use an attack based on integral cryptanalysis. The basic idea is to use several sets of messages, so that the messages in one of the sets follow the cancellation path.

In the original submission document of Lesamnta [START_REF] Hirose | SHA-3 Proposal: Lesamnta[END_REF] a 19-round Square distinguisher is described. This Square is very straightforward, and suggests an efficient distinguisher for Lesamnta. However, by experimenting with reduced versions, we found that the original Square is faulty. We first give an explanation of why the Square attack does not work. Then we suggest an improved and corrected 20-round integral distinguisher attack which relies on the cancellation property. This distinguisher gives a 21-round key-recovery attack using partial decryption of the last round. We use the term integral cryptanalysis rather than Square to describe our new attack, because we use a higher order property.

In Table 14, the symbols b 1 , b 2 , b 3 are used to denote three variables that independently take all possible values. So, in the first round, T 0 , U 0 , V 0 take all the 2 3n/4 possible values. At round 1, we have S 1 = F 1 (U 0 ) ⊕ V 0 . We see that F 1 (U 0 ) ⊕ V 0 , T 0 , U 0 take all possible values, so we can reuse the symbol b 3 for S 1 . This can be seen as a change of variables.

Starting from round 4, we have two values denoted by b 3 in the original Square. This is used to denote that R 4 , S 4 , T 4 take all possible values, while S 4 , T 4 , U 4 also take all possible values. However, this leads to a contradiction later on because there is an implicit change of variables when we reuse symbols and this cannot be done for a variable that appears twice. The first problem appears at round 7. We have that S 6 , T 6 , V 6 and S 6 , U 6 , V 6 take all possible values. The original Square suggests that this implies that S 7 , S 6 , T 6 take all possible values, where S 7 = F 7 (U 6 ) ⊕ V 6 . However this is not true in general. For instance, we could have

U 6 = F -1 7 (T 6 ⊕ V 6
). This is compatible with the assumptions of independence but in this case we have S 7 = T 6 and S 7 , S 6 , T 6 do not take all possible values.

Actually the Square described in this attack can be detected after 18 rounds, but not after 19 rounds.

Table 14. The originally suggested Square, and its actual development. We see that the independence assumptions of round 7 do not hold.

i Si Ti Ui Vi 0 - b1 b2 b3 1 b3 - b1 b2 2 b2 b3 - b1 3 b1 b2 b3
-4 b3 b1 b2 b3 5 b3 b3 b1 b2 6 b2 b3 b3 b1 7 b1 b2 b3 b3 Suggested in [START_REF] Hirose | SHA-3 Proposal: Lesamnta[END_REF] i Si Ti Ui Vi

0 - b1 b2 b3 1 b3 - b1 b2 2 b2 b3 - b1 3 b1 b2 b3 - 4 F (b3) b1 b2 b3 5 F (b2) ⊕ b3 F (b3) b1 b2 6 F (b1) ⊕ b2 F (b2) ⊕ b3 F (b3) b1 7 F (F (b3)) ⊕ b1 F (b1) ⊕ b2 F (b2) ⊕ b3 F (b3) Actual Square

A.1 The New Attack

Our new attack is based on the cancellation path of Table 15. Starting with (S 0 , T 0 , U 0 , V 0 ) = (a, b, c, d), we have the following condition:

Round 8: we have F 7 (F 4 (F 1 (b) ⊕ c) ⊕ F 0 (c) ⊕ d) ⊕ F 3 (F 0 (c) ⊕ d). They cancel if: F 4 (F 1 (b) ⊕ c) = K 3 ⊕ K 7
Table 15. Cancellation path for the integral attack on Lesamnta

i Xi(= Si) -3 d -2 c -1 b 0 a 1 F0(c) ⊕ d 2 F1(b) ⊕ c 3 F2(a) ⊕ b 4 F3(F0(c) ⊕ d) ⊕ a 5 F4(F1(b) ⊕ c) ⊕ F0(c) ⊕ d 6 F5(F2(a) ⊕ b) ⊕ F1(b) ⊕ c 7 F6(F3(F0(c) ⊕ d) ⊕ a) ⊕ F2(a) ⊕ b 8 F7(F4(F1(b) ⊕ c) ⊕ F0(c) ⊕ d) ⊕ F3(F0(c) ⊕ d) ⊕ a
Since we do not know the value of K 3 ⊕ K 7 , we cannot build a message that would satisfy the cancellation condition with probability one. However, in an integral attack, if we iterate over all values of c while b if fixed, we know that for one value there is a cancellation. Moreover, for each c, we can iterate over d and study properties of the set of ciphertexts generated in this way.

More precisely, for a random choice of A and B, we define the following sets of messages:

S C = {(A, B, C, d) : d ∈ F 2 64 } (d ∈ F 2 128 for Lesamnta-512)
We consider 2 64 sets (2 128 for Lesamnta-512) with all possible values of C, while A and B are fixed. We know that one particular set satisfies

F 4 (F 1 (B) ⊕ C) = K 3 ⊕ K 7 .
For this set, we show the dependencies of the state on d in Table 16. Note that:

-At round 8, the values F 7 (d) ⊕ F 3 (d) cancels out for this particular set.

-At round 14 we have

F 13 (F 6 (F 3 (d))) ⊕ F 9 (F 6 (F 3 (d))
). This has the special property that each value is taken an even number of times, according to Property (ii ).

-At round 17, we have

F 16 F 13 F 6 (F 3 (d)) ⊕F 9 F 6 (F 3 (d)) ⊕F 12 F 9 (F 6 (F 3 (d))
) ⊕d. When we sum this over all d's, this gives:

d F 16 F 13 F 6 (F 3 (d)) ⊕ F 9 F 6 (F 3 (d)) ⊕ d F 12 (F 9 (F 6 (F 3 (d)))) ⊕ d d
The first term sums to zero because each input to F 16 is taken an even number of times (cf. Property (iii )), and the two last terms sum to zero because they are permutations of d.

Since X 17 is the fourth output word after 20 rounds (X 17 = V 20 ), this gives an integral property on 20 rounds. This has been experimentally verified on reduced versions.

Table 16. Integral Attack. We only gives the dependencies in d.

i Xi

-3 d -2 - -1 - 0 - 1 d 2 - 3 - 4 F3(d) 5 d 6 - 7 F6(F3(d)) 8 F7(d) ⊕ F3(d) 9 d 10 F9(F6(F3(d))) 11 F6(F3(d)) 12 F11(d) 13 F12(F9(F6(F3(d)))) ⊕ d 14 F13(F6(F3(d))) ⊕ F9(F6(F3(d))) 15 F14(F11(d)) ⊕ F6(F3(d)) 16 F15(F12(F9(F6(F3(d)))) ⊕ d) ⊕ F11(d) 17 F16(F13(F6(F3(d))) ⊕ F9(F6(F3(d)))) ⊕ F12(F9(F6(F3(d)))) ⊕ d
This property can be used to attack the block cipher of Lesamnta. One has to encipher the 2 n/4 plaintexts in the sets S C for each C, and to compute the sum of V 20 over each set. If the data was generated using the compression function of Lesamnta, then at least one of the sets S C give a zero sum. Otherwise, there is only a probability 1/e that all the sums are non-zero. Moreover, when a set with a zero sum is found, it is possible to verify that this is due to the cancellation property, by building a new set S * C with the same C and B, but a different value A. As seen earlier, the cancellation condition does not depend on A, so this new set also gives a zero sum if C is the correct value for the cancellation condition.

This gives a distinguisher on 20-round Lesamnta with complexity 2 n/2 . Moreover, using partial decryption of the last round, it can be extended to a key recovery attack on 21 rounds with complexity 2 3n/4 .

B An Attack on 19-Round SMS4

SMS4 is a block cipher used in WAPI (the Chinese national standard for wireless networks) [START_REF] Diffie | SMS4 Encryption Algorithm for Wireless Networks[END_REF], based on a generalized Feistel network. SMS4 accepts a 128-bit plaintext and a 128-bit user key as inputs, and is composed of 32 rounds. In each round, the least significant three words of the state are XORed with the round key and the result passes the F transformation. The F transformation uses an 8-bit to 8-bit bijective SBox four times in parallel to process each byte, then the concatenated bytes are processed using a linear transformation L. The general structure is described by Figure 4, and can be written as:

S i+1 = V i ⊕ F (S i ⊕ T i ⊕ U i ⊕ K i ) T i+1 = S i U i+1 = T i V i+1 = U i
where the K i is the ith round subkey.

B.1 New Attack on SMS4

Our attack on SMS4 is not based on the same cancellation property as used to attack Lesamnta and SHAvite-3 512 . However, it shares the same core idea: we describe a generic attack on the Feistel structure based on a truncated differential, using available degrees of freedom to control the non-linearity. While this attack is not as efficient as the best attacks on SMS4 , we believe it is interesting because it is generic in the round function.

Our attack is based on the following truncated differential on four rounds:

i S i T i U i V i 0 x x a b x = a ⊕ b 1 x a b x 2 a b x x b → u let c = a ⊕ u 3 b x x c c → u let d = b ⊕ u 4 x x c d x = c ⊕ d
In this truncated differential, we do not specify the values of a, b, c, d and u. We start with any difference (x, x, a, b) with x = a ⊕ b, and we end up with a difference of the same form: (x, x, c, d) with x = c ⊕ d. The only condition for this truncated differential to be followed is that the transitions at step 2 and 3, b → u and c → u have to go to the same u. Since we do not care about the particular value of u, this happens with probability 2 -32 (the words are 32-bit wide).

We can iterate this truncated differential four time, and add two extra rounds at the end. This gives the following characteristic: For a random mapping, this characteristic has probability 2 -96 . Therefore, to detect the bias, we need a few times 2 64+96 = 2 160 input pairs. We can build the input pairs using structures: for a random A and B, we generate 2 64 messages M i,j = (A ⊕ i ⊕ j, B ⊕ i ⊕ j, i, j), by varying i and j. This gives 2 128 input pairs for the differential: each pair M i,j , M i ′ ,j ′ has a difference (i ⊕ j ⊕ i ′ ⊕ j ′ , i ⊕ j ⊕ i ′ ⊕ j ′ , i ⊕ i ′ , j ⊕ j ′ ). If we repeat this with a few times 2 32 choices of A and B, we have enough pairs to detect the bias. This gives a distinguisher on 18 rounds of SMS4 with a few times 2 96 chosen plaintexts. Experiments on reduced versions confirm this analysis. This distinguisher can be used for a 19-round attack, using partial decryption of the last round. The corresponding differential is: We can recover the subkey of rounds 19 with the following algorithm:

i S i T i U i V i 0 x
1. Repeat 2 40 times the following: 2. Choose a random A and B 3. Query the block cipher on the 2 64 messages M i,j = (A ⊕ i ⊕ j, B ⊕ i ⊕ j, i, j) 4. Let the plaintext/ciphertext be (q i,j , r i,j , s i,j , t i,j ) → (α i,j , β i,j , γ i,j , δ i,j ), respectively. Store the plaintext/ciphertext pair of ((q i,j , r i,j , s i,j , t i,j ), (α i,j , β i,j , γ i,j , δ i,j )) in a hash table indexed by q i,j ⊕ α i,j , q i,j ⊕ β i,j . 5. We search for collisions in the table, each offering a pair of plaintexts and ciphertexts (q i,j , r i,j , s i,j , t i,j ) → (α i,j , β i,j , γ i,j , δ i,j ) and (q i ′ ,j ′ , r i ′ ,j ′ , s i ′ ,j ′ , t i ′ ,j ′ ) → (α i ′ ,j ′ , β i ′ ,j ′ , γ i ′ ,j ′ , δ i ′ ,j ′ ) for which q i,j ⊕ q i ′ ,j ′ = α i,j ⊕ α i ′ ,j ′ = β i,j ⊕ β i ′ ,j ′ (= r i,j ⊕ r i ′ ,j ′ ). This defines the difference x.

There should be 2 63 collisions on average. 6. For each of these pairs, obtain the input difference (f ) to round 19, and the expected output difference (e⊕δ i,j ⊕δ i ′ ,j ′ ), and retrieve the one subkey suggestion (on average) for the subkey of round 19 which satisfies the differential transition3 .

The right subkey is expected to be suggested 2 71 + 2 39 times, while the wrong ones are expected to be suggested 2 71 times. With very high probability (of more than 85%), the most suggested subkey is the correct one. This gives a key-recovery attack on 19-round SMS4 with 2 104 chosen plaintexts, and a complexity of 2 104 time.

C Implementation of the 24-round Lesamnta Attack

To verify our attacks, we implemented the attack on 24-round Lesamnta based on symmetry properties of the round function. We cannot find a full preimage because the complexity is too high, but we can show a partial preimage to prove the validity of our attack: Chaining Value 33212102 5c23803f 00957df0 94a1d777 4953d309 0b3b6624 8c8d523c b14eec82 Message 904fe6d0 cdb99073 1949261e de5b3575 70e209ed 1fe0a8d0 e7bc6031 6a88ceef Output 03874543 a3a0eef7 3665a8bd 163bdaea 8a227d57 a6b6210f ffffffff ffffffff

D SHAvite-3 512 Message Expansion

The message expansion of SHAvite-3 512 accepts a 1024-bit message block, a 128-bit counter, and a 512-bit salt. All are treated as arrays of 32-bit words (of 32, 4, and 16 words, respectively), which are used to generate 112 subkeys of 128 bits each, or a total of 448 32-bit words.

Fig. 2 .

 2 Fig. 2. The Underlying Block Cipher of C 512

Fig. 3 .

 3 Fig. 3. Constraints in the Key Expansion of SHAvite-3 512 Initial constraints in pink, constraints from steps 1 to 3 in yellow, constraints from step 4 in green

Fig. 4 .

 4 Fig. 4. The Generalized Feistel structure of SMS4

  (x, x, a, b) |a⊕b=x 18rounds------→ (e, f, x, x) |e⊕f =x with probability 2 -128

  x a b x = a ⊕ b . . . 4 x x c d x = c ⊕ d . . . 16 x x e f x = e ⊕ f 17 x e f x 18 e f x x 19 f x x ?

Table 3 .

 3 Values of the Registers for Five Rounds of Lesamnta.

	i	Si	Ti	Ui	Vi

Table 5 .

 5 b, d and α, β are uniquely determined from the subkeys. Hence, one can set X 19 to any desired value X Values of the Register for the 22-round Cancellation Property of Lesamnta

* 19 by setting c = F -1 (X * 19 ⊕ β) ⊕ α.

Table 6 .

 6 Collision and Preimage Characteristic for the 22-Round Attack

	i	Si	Ti	Ui	Vi

Table 7 .

 7 Computing Values Backwards from the State (S 4 , T 4 , U 4

Table 8 .

 8 Collision and Preimage Path for the 24-round Attack

  Therefore we have 8 degrees of freedom. The relations between the variables are shown in Figure3, while the full key expansion of SHAvite-3 512 is described in Appendix D.

								2 0,8 , k 3 0,8 )	(C1)
	Or in rk[•] terms:
	rk[148, . . . , 159] = rk[196, . . . , 207]	rk[212, . . . , 223] = rk[260, . . . , 271]
	We are actually trying to solve a system of equation with:
	-224 variables: tk[128..159], tk[192..223] and rk[128..287]
	-192 equations from the key schedule (64 non-linear and 128 linear)
	-24 constraints
	AES	AES	AES	AES	AES	AES	AES	AES
	AES	AES	AES	AES	AES	AES	AES	AES

rk[256 ... 259,260 ... 263,264 ... 267,268 ... 271,272 ... 275,276 ... 279,280 ... 283,284 ... 287] LFSR2: rk[i]=rk[i-32]⊕rk[i-7] rk[224 ... 227,228 ... 231,232 ... 235,236 ... 239,240 ... 243,244 ... 247,248 ... 251,252 ... 255] LFSR1: rk[i]=tk[i-32]⊕rk[i-4] tk[192 ... 195,196 ... 199,200 ... 203,204 ... 207,208 ... 211,212 ... 215,216 ... 219,220 ... 223] rk[192 ... 195,196 ... 199,200 ... 203,204 ... 207,208 ... 211,212 ... 215,216 ... 219,220 ... 223] LFSR2: rk[i]=rk[i-32]⊕rk[i-7] rk[160 ... 163,164 ... 167,168 ... 171,172 ... 175,176 ... 179,180 ... 183,184 ... 187,188 ... 191] LFSR1: rk[i]=tk[i-32]⊕rk[i-4] tk[128 ... 131,132 ... 135,136 ... 139,140 ... 143,144 ... 147,148 ... 151,152 ... 155,156 ... 159] rk[128 ... 131,132 ... 135,136 ... 139,140 ... 143,144 ... 147,148 ... 151,152 ... 155,156 ... 159] (c3, c2, c1, c0)

  From the key expansion, we have rk[191] = rk[223]⊕rk[216], and rk[239] = rk[271]⊕rk[264]. Since we have the constraints rk[223] = rk[271] and rk[216] = rk[264], we can deduce that rk[191] = rk[239] Similarly, we get rk[187..191] = rk[235..239]. 3. From the linear part of the expansion, we have rk[186] = rk[190] ⊕ tk[158] and rk[234] = rk[238] ⊕ tk[206]. We have seen that rk[190] = rk[238] at step 2 and tk[158] = tk[206] at step 1, therefore rk[186] = rk[234] Similarly, we get rk[176..186] = rk[224..234]. 4. Again, from the linear part of the key expansion, we have rk[211] = rk[218] ⊕ rk[186] and rk[259] = rk[266] ⊕ rk[234]. We have seen that rk[186] = rk[234] at step 3 and we have rk[218] = rk[266] as a constraint, thus rk[211] = rk[259] Similarly, we obtain rk[201..211] = rk[249..259] Note that we have rk[201..207] = rk[153..159] as a constraint, so we must have rk[249..255] = rk[153..159]. Finding a Solution To find a solution to the system, we use a guess and determine technique. We guess 11 state variables, and we show how to compute the rest of the state and check for consistency. Since we have only 8 degrees of freedom, we expect the random initial choice to be valid once out of 2 32×3 = 2 96 times. This gives a complexity of 2 96 to find a good message. -Choose random values for rk[200], rk[204..207], rk[215..216], rk[220..223] -Compute tk[220..223] from rk[220..223] -Compute rk[248..251] from tk[220..223] and rk[252..255] (= rk[204..207]) are known, we know that tk[216..219] is a linear subspace of dimension 64 over F 2 . -Similarly, tk[208..211] is in a linear subspace of dimension 64 (rk[208] and rk[209] are known). -Moreover, there are linear relations between tk[216..219] and tk[208..211]: we can compute rk[240..243] from tk[208..211] and rk[236..239]; rk[244..247] from rk[240..243] and tk[212..215]; tk[216..219] from rk[244..247] and rk[248..251]. -On average, we expect one solution for tk[216..219] and tk[208..211]. -At this point we have computed the values of rk[200..223]. We can compute tk[200.223] and rk[228..255]. -Compute rk[176..179] from rk[201..204] and rk[208..211] -Since rk[224..227] = rk[176..179], we have a full state rk[224..255]. We can check consistency of the initial guess.

	1. The non-linear equations of the key-schedule give:
	tk[156..159] = AESR (rk[157, 158, 159, 156]) ⊕ (salt[12..15])

tk[204..207] = AESR (rk[205, 206, 207, 204]) ⊕ (salt[12..15]) since rk[156..159] = rk[204..207], we know that tk[156..159] = tk[204..207]. Similarly, we get tk[148..159] = tk[196..207] 2. -Deduce rk[201..203] = rk[249..251], so rk[200..207] is known -Compute tk[152..159] from rk[152..159] (= rk[200..207]) -Compute rk[190..191] from rk[215..216] and rk[222..223] -Compute rk[186..187] from rk[190..191] and rk[158..159] -Compute rk[182..183] from rk[186..187] and rk[154..155] -Compute rk[214] from rk[207] and rk[182] -Compute rk[189] from rk[214] and rk[219]; then rk[185] and rk[181] -Compute rk[213] from rk[206] and rk[181] -Compute rk[188] from rk[213] and rk[220], then rk[184] and rk[180] -Compute rk[212] from rk[205] and rk[180] -Compute rk[219] from rk[212] and rk[187] -Compute rk[208, 209] from rk[215, 216] and rk[183, 184] -We have tk[216..219] = AESR (rk[216..219]) with a known key. Since rk[216] and rk[219]

Table 11 .

 11 Summary of the Attacks on the Lesamnta Hash Function

	Lesamnta-256	Lesamnta-512

Table 12 .

 12 Summary of the Attacks on SHAvite-3 512

	Comp. Fun.	Hash Fun.

Table 13 .

 13 Summary of the Attacks on SMS4 Shoichi Hirose, Hidenori Kuwakado, H.Y.: Security Analysis of the Compression Function of Lesamnta and its Impact. Available online (2009) 13. Taehyun Kim, Jongsung Kim, S.H., Sung, J.: Linear and Differential Cryptanalysis of Reduced SMS4 Block Cipher. Cryptology ePrint Archive, Report 2008/281 (2008) http://eprint.iacr.org/. 14. Zhang, L., Zhang, W., Wu, W.: Cryptanalysis of Reduced-Round SMS4 Block Cipher. In Mu, Y., Susilo, W., Seberry, J., eds.: ACISP. Volume 5107 of Lecture Notes in Computer Science., Springer (2008) 216-229

	Attack		Rounds	Data	Time
	Boomerang	[13]	18	2 120 ACPC	2 120
	Rectangle	[13]	18	2 124 CP	2 124
	Differential	[14]	21	2 118 CP	2 126.6
	Differential	[13]	22	2 118 CP	2 125.7
	Linear	[13]	22	2 117 KP	2 117
	Truncated Differential (Sect. B.1)	19	2 104 CP	2 104

Note that the direction of the rotation in the Feistel structure is not really important: changing the rotation is equivalent to considering decryption instead of encryption.

Note that the expression given for x in[START_REF] Hirose | SHA-3 Proposal: Lesamnta[END_REF] is incorrect.

Note that we only need the differential table of the 8-bit S-Box for this step.

Acknowledgements

We would like to thank the members of the Graz ECRYPT meeting. Especially, we would like to express our gratitude to Emilia Käsper, Christian Rechberger, Søren S. Thomsen, and Ralf-Philipp Weinmann for the inspiring discussions. We are grateful to the Lesamnta team, and especially to Hirotaka Yoshida, for helping us with this research. We would also like to thank the anonymous referees for their comments.

Let rk[•] be an array of 448 32-bit words whose first 32 words are initialized with the message. After the initialization of rk[0, . . . , 31], two processes are repeated, a nonlinear one (which generates 32 new words using the AES round function) and a linear one (which generates the next 32 words in a linear manner). These processes are repeated 6 times, and then the nonlinear process is repeated once more. The computation of rk[•] is done as follows:

Using the counter: the counter is used at 4 specific positions.

In order to simplify the description, we define a new table holding the preprocessed counter:

Once rk[•] is initialized, its 448 words are parsed as 112 words of 128-bit each, which are the subkeys (14 double quartets of 128-bit words each), i.e.: