Marine Minier

C.-W Phan

C.-W Raphaël

Phan

Tuple Cryptanalysis: Slicing & Fusing Multisets

Keywords: Slicing and Fusing Multisets Block ciphers, Square, saturation, integrals, multisets, bit patterns, tuples, bitslice, Slice & Fuse paradigm, division property

whether they are published or not. The documents may come

Introduction

Cryptanalysis based on a multiset of related texts aims for some property of the multiset to pass through cipher components with a probability that is furthest away as possible from the uniform distribution. Given a bijective function S : {0, 1} w → {0, 1} w , then with a multiset M of 2 w elements such that ∀x j , x j ∈ M, x j = x j (so-called a multiset with the permutation property P, or called an active set), we have that ∀x j , x j ∈ M, S(x j ) = S(x j ), i.e. such a P multiset passes through S without having its property changed. Given such a P, its presence can be detected by checking if the exclusive-OR ( ) sum of all elements of this multiset equals zero. This was rst observed by Knudsen in 1997 [START_REF] Daemen | The Block Cipher Square[END_REF] as part of the analysis of the Square cipher, hence subsequently it was de facto known in the cryptographic community as the Square attack.

The term multiset was in fact rst used for this cryptanalysis context by Lucks [START_REF] Lucks | The Saturation Attack -A Bait for Twosh[END_REF], within a so-called saturation attack framework. This naming convention makes sense, because essentially, only the active set (only later known as the permutation P set) is a proper set, other types e.g. the even (E) set, the passive (also called constant C) set, are actually multisets because any distinct value could appear more than once in such sets. The saturation term is named after the so-called saturated property, which is used to denote a dth-order P multiset. Furthermore, the semi-saturated property was used to refer to a multiset with 2 w-1 unique values instead of 2 w . Lucks noted that when viewed in terms of separate bit positions, one such bit position is xed to a constant value while the other w -1 are allowed to vary. To our knowledge, this was the rst mention of viewing multisets in terms of their bitwise channels.

Paper C2, pre-proceedings of Mycrypt 2016.

Knudsen & Wagner later proposed a formalisation of this type of cryptanalysis within the group theoretic setting as the Integral cryptanalysis [START_REF] Knudsen | Integral Cryptanalysis[END_REF], focussing on how the sum of a P multiset could propagate through dierent cipher components; presenting ways to determine such an integral sum for multisets of dierent types i.e.

C, P and those whose integral sum equals some xed value.

Meanwhile, Biryukov & Shamir [START_REF] Biryukov | Structural Cryptanalysis of SASAS[END_REF] initiated a formal study of multiset calculus by considering how multiple words of multisets propagate through the substitution and ane layers of a cipher, i.e. the notion of multiple multiset words M 1 . . . M composing to a multi-word multiset. This type of analysis is crucial as a multiset input in any word of a block eventually spreads to other words through the diusing properties of the ane layers. Nakahara Jr et al. [START_REF] Nakahara | New Multiset Attacks on Rijndael with Large Blocks[END_REF] at Mycrypt 2005 built on this notion by focussing on how an n-bit P word multiset M can be decomposed into its constituent subword multisets V i each of length w < n. Z'aba et al. [START_REF] Raddum | Bit-Pattern based Integral Attack[END_REF] took this decomposition notion further by focussing on constituent bitslice multisets i.e. w = 1. Indeed, when the cardinality of a bitslice multiset V is more than two, i.e. |V| > 2, the elements of the bitslice multiset are then seen to form a bit pattern. Using such bit patterns that are either constant c, regularly alternating a i or non-alternating b i , they were able to trace how such patterns behave through the exclusive-OR (XOR) operation and through the Sbox layer.

Aumasson et al. [START_REF] Aumasson | Tuple Cryptanalysis of ARX with Application to BLAKE and Skein[END_REF] emphasized on the internal ordering of the elements within a multiset, therefore such ordered multisets are better known as tuples. Keeping track of ordered tuple elements is useful in order to better trace the eects of operations among elements of dierent multisets, as well as be exploited to cancel out dierences among elements of dierent tuples.

More recently, Todo [START_REF] Todo | Structural Evaluation by Generalised Integral Property[END_REF][START_REF] Todo | Integral Cryptanalysis on Full MISTY1[END_REF] generalized the integral cryptanalysis approach by taking the integral sum on the low-order polynomial subsets of all the elements in the output multisets, such that due to the higher-order dierential type property linked to the algebraic normal form (ANF) representation of the cipher component, a zero sum is obtained; so-called the division property. The approach was then formalised by Boura and Canteaut [START_REF] Boura | Another View of the Division Property[END_REF] in relation to Reed-Muller codes, based on parity computation across dierent multiple bits of each multiset element, which is related to the ANF representation of functions and the algebraic degree. In contrast, our proposed approach considers each bitslice channel independently and the focus is on the internal ordering of such bitslice elements rather than on their integral sum.

The Slice-&-Fuse Paradigm. In this paper, we put forth a rened multiset calculus, wherein we propose new types of bitslice tuples to better represent the rich internal structures of multiset constituents, analyse the behaviour of such tuples through dierent cipher components including exclusive-OR, addition, AND and Sboxes, and discuss how these constituent bitslice tuples can be recomposed (fused) to form structured multisets.

We demonstrate such tuple formulations on the ciphers Threesh, Prince, Present and Rectangle. For Threesh, more structured multiset properties are detected analytically in contrast to best-known results in [START_REF] Aumasson | Tuple Cryptanalysis of ARX with Application to BLAKE and Skein[END_REF], while for Prince we are able to extend the multiset tracking by one more round compared to previous work [START_REF] Morawiecki | Practical Attacks on the Round-reduced PRINCE[END_REF]. For Present and Rectangle, we need much smaller multisets (thus less data complexity) and/or are able to detect a sum property in more number of output bits compared to the literature. Moreover, as side results, in Appendix A we also improve the previous integral attacks against Crypton and mCrypton.

Multiset Calculus

Multiset & Bitslice Channels

A w-bit multiset M = {x j } 2 w -1 j=0 = β w-1 . . . β 0
is a collection of 2 w w-bit word elements. The multiset can also collectively be viewed as a concatenation of w bitslice channels β i , i = 0, . . . , w -1, one for each bit position within the word; and where each channel comprises 2 w bit elements. The bit elements within these bitslice channels will follow some internal ordering, and thus for the rest of this paper, we will use the term bit tuples (these have also been called bit patterns [START_REF] Raddum | Bit-Pattern based Integral Attack[END_REF]) to refer to such ordered bitslice channels. By denition, the elements {x j } within a multiset can take the same w-bit values, therefore it is at times useful to explicitly denote, using the multiset notation, the multiplicity/frequency m(x j ) of element values. Thus a multiset can alternatively be expressed as a set of unordered pairs of the form {x j , m(x j )}, where each distinct value of x j is taken from a so-called root set R. Obviously, |M| ≥ |R|.

Denition 1 (Multiset Properties): Depending on the values of its elements, a multiset is said to have (one or more of) any of the following properties:

• P: ∀x j , x j ∈ M, x j = x j ; thus m(x j ) = m(x j ) = 1.
This is known as a permutation multiset, where all elements are distinct.

• C: ∀x j ∈ M, x j = c for some constant value c; thus m(c) = 2 w . This is called a constant multiset, where all elements equal some constant c.

• E k : ∀x j ∈ M, m(x j ) mod k = 0,
where k is of the form 2 n . For simplicity reasons, E 2 will be denoted by E. This is an even multiset, where each element value from R appears an even number of times in M.

• B: 2 w -1 j=0 x j = 0.

Multisets with this property are said to be balanced. Essentially, this property is detected by the existence of a zero integral sum.

• A:

2 w -1 j=0 x j = 0.
This is the additive variant of the zero sum.

• F:

2 w -1 j=0 x j = 2 w-1 .
This is similar to A except that the sum is non-zero.

• Q: ∀x j ∈ M, ∀x j ∈ M , 2 w -1 j=0 x j = 2 w -1 j=0 x j .
This equality property exists for two multisets when their respective sums are equal. It has been observed [START_REF] Aumasson | Tuple Cryptanalysis of ARX with Application to BLAKE and Skein[END_REF] that these multiset properties are essentially of two categories:

• those characterized by the multiplicity of the elements: P,C,E • those characterized by relations among the elements: B,A,F,Q Denition 2 (Bit Tuples): A bitslice channel β can be (one or more of) any of the following bit tuples:

• c: a contiguous sequence of all `0' or all `1' bits, i.e. c ∈ {00 . . . 00, 11 . . . 11}.

• a i : alternating segments of length 2 i . e.g. a 1 = 00 11 00 11 . . . 00 11 .

• âi : the segment dual of a i such that their segment boundaries are out of sync by half of the segment length. e.g. â1 = 01 10 01 10 01 10 . . . 10 or 10 01 10 01 10 01 . . . 01 . Note. For any a i where i = 0, its segment dual âi is palindromic. • ãi : the cyclic variant(s) of a i such that their segment boundaries are out of sync.

Note that âi is a special case of ãi . e.g. Given a 2 = 0000 1111 0000 1111 . . . 0000 1111 , then we could have ã2 = 000 1111 0000 1111 . . . 0000 1111 0 or ã2 = 0 1111 0000 1111 . . . 0000 1111 000 • p ij : palindromic dual to a i with alternating ipped pattern segments of length 2 j .

See Example 1(a).

• pij : the segment dual of p ij such that their segment boundaries are out of sync by half of the segment length. See Example 1(a).

• c ij : complement dual to âi with alternating ipped pattern segments of length 2 j .

Note. Observe that c ij is to âi what p ij is to a i . See Example 1(b).
• m ij (resp. s ij ): masked dual of a i where every other contiguous sequence of 2 j bits is masked to `0' (resp. set to `1'). e.g. m 02 = 0000 0101 0000 0101 . . . and s 02 = 1111 0101 1111 0101 . . . . • z j : a bit tuple of pattern cycle length 2 j+1 , that begins with contiguous `0' bits followed by 2 j-1 `1' bit(s). e.g. z 2 = 00000011 00000011 . . . 00000011 . • f j : a bit tuple with alternating ipped pattern segments each of length 2 j . e.g. f 3 = 00101011 11010100 . . . 00101011 11010100 . • l j : a bit tuple with alternating pattern segments each of length 2 j comprising contiguous runlengths of `0's and `1's. e.g. l 2 = 0111 0111 . . . 0111 or l 2 = 0001 0001 . . . 0001 . • e: unlike the above tuples where bit elements within the tuple conform to some dened ordering, the e is just used to denote the property of a bit tuple such that its bit elements appear an even number of times.

Note that a i and c were dened in [START_REF] Raddum | Bit-Pattern based Integral Attack[END_REF]. The other bit tuple denitions are new and will be useful later when we trace how dierent bit tuples are changed by the various cipher operations e.g. ARX (addition, rotation, exclusive-OR) and AND.

Example 1(a): For bit tuple a 0 = 01010101 . . . 01 , its palindromic duals p 0j include: • . . .

Note. An a i and any of its palindromic duals p ij dier in half of their bits. Similarly, an âi and any of its complement duals c ij also dier in half of their bits. Since a i and âi are e (even), therefore their respective duals p ij and c ij are also e.

Denition 3 (Segment Length):

The length s of a segment within a multiset or bit tuple is dened as the number of times that a unique element value is repeated contiguously within the dened ordering of the multiset/tuple. Note that for a multiset to have property P, its s needs to be 1.

Denition 4 (Pattern Cycle):

The cycle of a multiset or bit tuple is dened as the point when a pattern of elements repeats. The number of elements traversed before this occurs is known as the cycle length c . Note that for a multiset M to have property P, its c needs to equal |M|. The above multiset is said to have the permutation property P as all elements are distinct, each of multiplicity 1. M has segment length s = 1 and cycle length s = |M| = 8. Observe that the multiset also has property B and F.

Denote M = β 2 β 1 β 0 . The bitslice channel β 0 of M corresponding to the least signicant bit (LSB) position of any element of M is an a 0 bit tuple, while β 1 and β 2 are respectively of the form a 1 and a 2 . The segment and cycle lengths of these bitslice channels are:

• s (a 0 ) = s ( 01010101 ) = 1, c (a 0 ) = c ( 01 01 01 01 ) = 2, • s (a 1 ) = s ( 00 11 00 11 ) = 2, c (a 1 ) = c ( 0011 0011 ) = 4, • s (a 2 ) = s ( 0000 1111 ) = 4, c (a 2 ) = c ( 00001111 ) = 8.
Multiset Equivalence. Note that our denition of the bit tuple is cyclic. For instance, if the elements in the multiset of Example 2 were permuted to be: M = 001, 010, 011, 100, 101, 110, 111, 000 the bit tuples are still considered to be of the form a 2 a 1 a 0 . We say that two multisets are equivalent if they have the same property, up to cyclic shift as in the previous example. For two multisets that are not equivalent in this sense, there is a need to distinguish between them. For this purpose, we can dene more precisely the P property as it could be mapped into two dierent bit tuples that are not equivalent.

Denition 5 (Rened P Property): We rene the P property as follows:

• P ord : the property P ord corresponds to a multiset that could be written as the composition of bit tuples of the form . . . a 2 a 1 a 0 .

• P nord : the property P nord corresponds to a multiset that could not be written as the composition of bit tuples of the form . . . a 2 a 1 a 0 .

When required, we precise if P is of the form P ord or P nord .

Slicing a Multiset. To our knowledge, Nakahara Jr. et al. [START_REF] Nakahara | New Multiset Attacks on Rijndael with Large Blocks[END_REF] at Mycrypt 2005 were the rst to consider viewing a w-bit multiset in terms of the properties of its constituent v-bit (v < w) channels; i.e. slicing a multiset. This may allow to better trace how multiset properties propagate through cipher components.

For instance, removing any bitslice channel from the 3-bit P multiset M of Example 2 results in a 2-bit multiset that is no longer P but rather is E. Thus, we could directly state that any v-bit (v < w) subset V of a w-bit P multiset M cannot be P but must be E.

Fusing the Slices of a Multiset

Decomposing a w-bit multiset M into its constituent bitslice channels or some v-bit (v < w) subset V could allow to better track the changes in its properties through cipher round operations. After going through round operations, it is helpful to evaluate if the multiset retains its original properties e.g. P is preserved. For this, we need to recompose the subset V, i.e. fuse some concatenation of bitslice channels back into the w-bit multiset M and to infer if a multiset property at the w-bit level is preserved or if a new multiset property is obtained.

The most structured property that has the ability to go through round operations is the property P, thus it is interesting to study its constituent bitslice channel tuples.

From Example 2, we see that bit tuples of the form a i1 a i2 . . . a iw , for any pairwise indices i j = i k (j, k ∈ {1, . . . , w}), compose to a word multiset of property P. We are interested in other constituent bit tuples that compose to a P. Example 3. To motivate the idea, consider the multiset M as below:

M = 011, 111, 101, 010, 001, 100, 000, 110

At rst glance, such a multiset has no obvious bit tuple form. To facilitate extracting its bit tuples, some prior reordering is helpful before bitslicing. We introduce some notation to keep track of the elementwise permutations ρ, to enable subsequent unwinding to the element ordering of the original, i.e. ρ(M). For instance, permute M according to (1 3 4) and we get a multiset ρ(M) with property P, of the form a 0 a 2 a 2 :

ρ(M) = 010, 111, 011, 101, 001, 100, 000, 110

This example highlights that a P can be formed by a i 's that may have the same index, e.g. in this case, there are two a 2 s. However, from closer inspection, these two a 2 s are not identical in form, in fact their segment boundaries are out of sync.

We dene a pair of a i s whose segment boundaries are out of sync by half of the segment length, as segment duals of each other, denoted as a i , âi . Note that such pairwise duals are equal in half of their elements. In fact, when concatenated, these two bitslice channels form 2-bit elements that occur an even number of times.

With this in place, the above permuted multiset ρ(M) is actually of the form a 0 a 2 â2 . It is worth to investigate what property is obtained when fusing (recomposing) two dual bit tuples to form a 2-bit multiset V. Continuing from the above example, V = a 2 â2 gives: Since its cycle length is already 8, what remains is to cause its segment length to reduce to 1, in order for this multiset V to be used to form a multiset M of property P.

To do this, we append another bitslice channel such that the resultant segment length s reduces to 1. Consider appending a bit tuple a 0 (note that this has segment length s = 1) to V, thus we can get either a 0 a 2 â2 , a 2 a 0 â2 or a 2 â2 a 0 , as follows: Consider instead, to append the bit tuple â1 (note that this has segment length s = 2) to V, but such that its segment boundary is out of sync with the segment boundary of V. Thus we get either â1 a 2 â2 , a 2 â1 â2 or a 2 â2 â1 : Therefore, the only appropriate bit tuple to append to this would be of the form a 2 which has cycle length c = 8. This is why the example M , which is of the form â1 a 2 a 1 , is a P.

We now have the notations, denitions and criteria for representing, slicing (decomposing) and fusing (recomposing) multisets. These are crucial in order to facilitate the tracking of multiset & bit tuple properties through cipher rounds.

Tuples through Cipher Operations

In this section, we analyze the propagation of bitslice tuples through some main primitive operations commonly used in block ciphers and hash functions; notably the exclusive-OR (XOR), the AND operation, and substitution boxes (Sboxes). Tuples through XOR. The emphasis we place here is on constituent tuples obtained from slicing the multisets that have property P, since this has the richest structure that can survive through round operations better than multisets of other properties.

Therefore it is vital that we understand what happens to P inputs after going through XOR; the most complex being P ⊕ P.

As a P multiset comprises bitslice tuples of the form a j , then any P ⊕ P will cause the following types of XOR between its a j (or cyclic variants âj , ãj ) bitslice tuples:

• a j ⊕ a j = c • a j ⊕ âj; j =0 = a j-1 • a j ⊕ a j-1 = âj • a i ⊕ a j; j>i+1 = p ij • a i ⊕ âj; j>i+1 = pij • âi ⊕ a j; j>i+1 = c ij • a j ⊕ âj-1 = p(j-2) j • a j ⊕ ãj; j =0,1 = j • a i ⊕ ãj; j>i = f j • ãi ⊕ a j; j>i = f j • ãi ⊕ ãj; j>i = f j • âi ⊕ ãj; j>i = f j • ãi ⊕ âj; j>i = f j
Note that these properties are more rened than the ones observed in [START_REF] Raddum | Bit-Pattern based Integral Attack[END_REF], and better allow to retain the internal rich structures within a P.

Furthermore, the following XOR relations can also be observed between other types of bitslice tuples:

• a j ⊕ p (j-2)(j-1) = p(j-2) j

• a j ⊕p ik; i,k<j : this leads to the complement dual of p ik , i.e. p ik but with alternating ipped pattern segments of length 2 j

Note. All the above bit tuples have the bit tuple property e.

Tuples through AND. As the AND operation serves as one of the primitives in recent ciphers such as Prince, Simon, and Simeck, as well as when Sbox output bits are expressed in ANF representation, we consider bit tuple propagations through this AND operation.

In more detail, we analyze the bit tuple interactions involving one or two a j :

• c ∧ a j = a j or 0 . . . 0 (i.e. the all `0' sequence)

• a j ∧ a j = a j • a j ∧ a j-1 = z j • a i ∧ a j;j>i+1 = m ij
Intuitively, this leads to a bit tuple that equals a i except that every other contiguous sequence of length 2 j corresponding to `0' bits in a j contains bits masked to `0'

Note. All the above output bit tuples have even parity. Furthermore, their segment and/or pattern cycles are based on a i , therefore their pattern boundaries are aligned with the segment boundaries (if any) of the a i 's.

Tuples through Sboxes. Any output bit of an Sbox can be viewed as the output of a coordinate Boolean function constituting the Sbox, and can be expressed in ANF representation, thereby relating each output bit as a function of input bits. While the ANF representation of Sboxes has been exploited in the literature to track the development of the algebraic degrees of Sbox outputs, in this paper we propose the novel approach of using the ANF to enable the tracking of how bit tuples propagate through an Sbox. Essentially, from the ANF, it can be observed that any Sbox output bit is the result of ANDing and then XORing the input bits. Therefore, the problem of tracking how bit tuples behave as they pass through an Sbox can be reduced to the problem of tracking how bit tuples propagate through AND and XOR operations.

Details of this approach of tracking bit tuples through Sboxes appear in the later subsections 3.3 and 3.4 on the Present and Rectangle ciphers.

3 Multiset Properties through Ciphers

Threesh & ARX

To concisely exemplify our approaches, notably in terms of the slicing of multisets and analysing their constituent bitslice tuples, we will rst consider here the MIX operation within the round function of the Threesh block cipher [START_REF] Ferguson | The Skein Hash Function Family, version 1.3[END_REF], before moving on the other ciphers. MIX is dened as follows:

MIX(x, y) = x + y, (x + y) ⊕ (y ≫ r) .

Note that this MIX function is essentially of the ARX form, i.e. addition (ADD), rotation (ROT), and exclusive-OR (XOR).

The multisets' behaviours as they propagate through the Addition, XOR and Rotation operations are shown in Table 1 as reported in [START_REF] Aumasson | Tuple Cryptanalysis of ARX with Application to BLAKE and Skein[END_REF]. Our aim here is to derive more internal structures and corresponding properties within these output multisets, based on our formulations of multisets and their bitslice channels.

Table 1. Truth tables of Addition (ADD), XOR, and Rotation (ROT) on multisets as reported in [START_REF] Aumasson | Tuple Cryptanalysis of ARX with Application to BLAKE and Skein[END_REF].

+ A B C E F P A A X A X F F B X X X X X X C A X C E F P E X X E X X X F F X F X A A P F X P X A A ⊕ A B C E F P A X X X X X X B X B B B X B C X B C E X P E X B B B X B F X X X X X X P X B P B X B ≫ A B C E F P n X B C E X P
Multisets through Rotation (ROT). We commence by looking at the simplest operation in terms of inuence on multiset properties, i.e. the rotation (ROT), also denoted by ≫.

To see why (≫P) still gives P, consider its bitslice channels, e.g. for a P = a 2 a 1 a 0 , then we have: (≫ a 2 a 1 a 0 ) → a 0 a 2 a 1 = P. Multisets through Addition (ADD). In [START_REF] Aumasson | Tuple Cryptanalysis of ARX with Application to BLAKE and Skein[END_REF] it was shown that P + P → A based on detecting a zero sum with respect to modulo addition. Alternatively, using bitslice tuples enables to show why we get the property: P+P = a 2 a 1 a 0 + a 2 a 1 a 0 → a 1 a 0 c = E.

More importantly, crucial to the analysis of multisets through MIX is the behaviour of C + P. W.l.o.g. consider a multiset P 1 comprising the bit tuples a 2 a 1 a 0 , e.g. whose elements are ordered ascendingly. It is known that when added to a C, this results in a P 2 where the same ordering is preserved. However, if we focus on the constituent bitslice tuples, we see that these tuples may no longer have segment boundaries aligned with those of a 2 , a 1 , a 0 , i.e. its bitslice tuples would be from the set ∈ {a j , âj;j =0 , ãj;j =0,1 }.

Multisets through Exclusive-OR (XOR).

We consider the XOR of dierent types of P, or with A, as typically encountered when propagating multisets through ARX constructions, e.g. the MIX function of Threesh; in terms of the constituent bitslice channels of such multiset types. Without loss of generality, we describe the analysis with respect to 3-bit multisets for better clarity.

• P ⊕ P: a 2 a 1 a 0 ⊕ a 2 a 1 a 0 → ccc = C.
This case considers the XOR of P multisets comprising the same bitslice tuples. The next case considers the XOR of P multisets comprising dierent orderings of bitslice tuples caused by rotation of P. • P ⊕ (≫P): a 2 a 1 a 0 ⊕ a 0 a 2 a 1 = a 2 ⊕ a 0 , a 1 ⊕ a 2 , a 0 ⊕ a 1 → p 02 â2 â1 = E. It could be generalized to E k for larger P sets.

• P 1 ⊕ P 2 : here we utilize the tuples formulation of this paper to show why in some cases, where dierent types of P structures can be precise in their bitslice tuples, that the XOR of two P can still produce a P. It remains an open problem whether all types of P can be similarly dened, including P nord which is not captured in our tuples formulation. In our earlier work i.e. [START_REF] Aumasson | Tuple Cryptanalysis of ARX with Application to BLAKE and Skein[END_REF] 2.2, it was stated with an example that this was possible for non-trivial cases of P, though no detailed analysis could be provided as to why this behaviour exists because we lacked the formulations to precisely detail dierent types of P. It was also mentioned in 3.2 that properties observed from empirical results were stronger than analytical predictions because tracking analytically was dicult. By using the tuples formulation, one can answer the question as to why a P could be empirically detected after P 1 ⊕ P 2 although state-of-the-art integral and multiset analysis techniques were to date not able to explain why it is a P. To show that we can get a P, consider P ord,1 = a 2 a 1 a 0 and P 2 = a 0 â2 a 1 , then P ord,1 ⊕ P 2 = a 2 a 1 a 0 ⊕ a 0 â2 a 1 = a 2 ⊕ a 0 , a 1 ⊕ â2 , a 0 ⊕ a 1 = p 02 a 2 â1 = P 3 . This results in a permutation P multiset because the segment length s of the multiset is 1 due to the tuple p 02 while the cycle pattern length c = 8 due to the tuples a 2 and p 02 .

• A ⊕ P: a 1 a 0 c ⊕ a 2 a 1 a 0 = a 1 ⊕ a 2 , a 0 ⊕ a 1 , c ⊕ a 0 → â2 â1 a 0 = P, for the specic type of A that can be formulated as a 1 a 0 c e.g. when it is produced from P + P. Note that such an A is also an E. To see this why this XOR results in a P, we can recall our discussions on fusing in subsection 2.2, notably the segment length s of this multiset is 1, while its cycle length c is 8 equaling the size of this multiset.

⊕ A B C E F P A X X X X X P/X B X B B B X B C X B C E X P E X B B B X P/B F X X X X X X P P/X B P P/B X P/E/C
Multisets through MIX. With the enriched multiset properties based on bitslice tuples as discussed above, we can more precisely trace the following multiset propagations through the MIX function of Threesh, w.l.o.g. consider 3-bit multisets for simplicity of description: MIX(C, P) = C + P, (C + P) ⊕ (≫ P) = P, β 2 β 1 β 0 Consider a P multiset of the form a 2 a 1 a 0 , thus (≫ P) = a 0 a 2 a 1 . From our above discussion in the subsection for the case of multisets through ADD, we see that C+P → P = α 2 α 1 a 0 where α 2 ∈ {a 2 , â2 , ã2 }, α 1 ∈ {a 1 , â1 }. Therefore, we can see that the output bit tuples β 2 β 1 β 0 would form the multiset (C + P) ⊕ (≫ P) as follows:

• β 2 = α 2 ⊕ a 0 = • a 2 ⊕ a 0 = p 02 , or • â2 ⊕ a 0 = p02 , or • ã2 ⊕ a 0 = f 2 . • β 1 = α 1 ⊕ a 2 = • a 1 ⊕ a 2 = â2 , or • â1 ⊕ a 2 = p02 . • β 0 = a 0 ⊕ a 1 = â1 .
These results have been corroborated by experiments on up to 8-bit multisets. Examples of an output multiset (C + P) ⊕ (≫ P) = β 2 β 1 β 0 with such properties are as follows:

• β 2 = p 02 = 0101 1010 or p02 = 01 1010 01 or f 2 = 1011 0100 • β 1 = â2 = 00 1111 00 or p02 = 01 1010 01

• β 0 = â1 = 01100110
Thus, we can deduce more structure through MIX at its output, answering the question left partially open in previous work i.e. [START_REF] Aumasson | Tuple Cryptanalysis of ARX with Application to BLAKE and Skein[END_REF] where it was stated that dependencies between tuples of words were dicult to track analytically, after having remarked that there was a dierence in precision between what could be empirically observed and what could be analytically predicted.

In addition, for the cases where the input multiset going into MIX is P, P , e.g. when via chosen-ciphertext attacks such structures are input to MIX, we can obtain:

MIX(P, P) = P + P, (P + P) ⊕ (≫ P) = E, P/E rather than the A, B previously observed. To see this, rst note that for the left half of the output multiset, as per the subsection discussion in the case of multisets through Addition (ADD), we have (P + P) → E = a 1 a 0 c. For the right half (P + P) ⊕ (≫ P) of the multiset, recall that (≫ P) = a 0 a 2 a 1 . Thus we have the right output multiset as:

a 1 ⊕ a 0 , a 0 ⊕ a 2 , c ⊕ a 1 = â1 , p 02 , a 1 = P.
An example of when the right half of the output multiset becomes E is where P = a 3 a 2 a 1 a 0 , such that (P + P) ⊕ (≫ P) = (a 2 a 1 a 0 c) ⊕ (a 0 a 3 a 2 a 1 ) = a 2 ⊕ a 0 , a 1 ⊕ a 3 , a 0 ⊕ a 2 , c ⊕ a 1 = p 02 p 13 p 02 â1 = E, since the same bit tuple p 02 is present twice in the multiset, with the same boundary alignment. Alternatively, one could obtain a P multiset for other parameters, e.g. for dierent rotation amounts, for instance

(P + P) ⊕ (≫ 2 P) = (a 2 a 1 a 0 c) ⊕ (a 1 a 0 a 3 a 2 ) = a 2 ⊕ a 1 , a 1 ⊕ a 0 , a 0 ⊕ a 3 , c ⊕ a 2 =
â2 â1 p 03 a 2 = P, where ≫ r denotes rotation to the right by r amounts.

These examples show that one could analytically deduce better properties for MIX(P,P), lling the gap between what could be observed via analysis and what was actually observed via experiments.

Prince

Prince is an SPN block cipher with a particular involutive structure for low latency [START_REF] Borgho | PRINCE -A Low-Latency Block Cipher for Pervasive Computing Applications[END_REF]. Its 64-bit block can be represented as a 4 × 4 state of nibbles, which goes through initial keying, 5 forward SPN rounds, an unkeyed middle layer, and then 5 more backward SPN rounds before nal keying.

where v ij denotes a nibble of i bits taking only j values.

• M in R2: To see this, note from our previous discussion of tuple propagations through the XOR operation, that the above bit tuples input to the Sbox S are of the form:

→ c α 0 α 0 α 0 α 1 c α 1 α 1 α 2 c α 2 α 2 c α 3 α 3 α 3 α 0 c α 0 α 0 α 1 α 1 c α 1 α 2 α 2 c α 2 α 3 c α 3 α 3 α 0 α 0 c α 0 α 1 α 1 α 1 c α 2 α 2 α 2 c α 3 α 3 c α 3 α 0 α 0 α 0 c c α 1 α 1 α 1 c α 2 α 2 α 2 α 3 α 3 α 3 c • SR in R2: → c α 0 α 0 α 0 α 1 c α 1 α 1 α 2 c α 2 α 2 c α 3 α 3 α 3 α 1 α 1 c α 1 α 2 α 2 c α 2 α 3 c α 3 α 3 α 0 c α 0 α 0 α 2 α 2 α 2 c α 3 α 3 c α 3 α 0 α 0 c α 0 α 1 α 1 α 1 c c α 1 α 1 α 1 c α 2 α 2 α 2 α 3 α 3 α 3 c α 0 α 0 α 0 c • S in
• α 01 = α 0 ⊕ α 1 ∈ {c ⊕ c, a 0 ⊕ c, c ⊕ a 1 , a 0 ⊕ a 1 } = {c, a 0 , a 1 , â1 } • α 12 = α 1 ⊕ α 2 ∈ {c ⊕ c, a 1 ⊕ c, c ⊕ a 2 , a 1 ⊕ a 2 } = {c, a 1 , a 2 , â2 } • α 02 = α 0 ⊕ α 2 ∈ {c ⊕ c, a 0 ⊕ c, c ⊕ a 2 , a 0 ⊕ a 2 } = {c, a 0 , a 2 , p 02 } • α 012 = α 0 ⊕ α 1 ⊕ α 2 ∈ {c, a 0 , a 1 , a 2 , â1 , â2 , p 02 , p02 }.
All these possible bit tuples are even (e) tuples. Therefore, as S is bijective, the output bit tuples will also be e. These will remain as e after the subsequent M layer. Therefore, after 3 rounds of Prince, we have that all the output bits give a zero integral sum.

Note that there exist many such properties positioned at dierent places of the block with the three bits aligned in a column and for dierent combinations of three rounds. Note that this property leads to be able to build a distinguisher with only 2 3 plaintexts on 3 rounds SM , SM and SM .

Moreover, and due to the structure of the Prince matrix, we could transform the 4th order integral property on 4 rounds described in [START_REF] Jean | Security Analysis of Prince[END_REF] requiring 2 16 chosen plaintexts into a 3-th order integral property on 4 rounds requiring only 2 12 chosen plaintexts as noticed in [START_REF] Posteuca | Integral Cryptanalysis of Round-Reduced PRINCE cipher[END_REF]. Indeed:

C C C C C C C C C C C C C C C A 4
is computed, inverting one round, from:

C C C A 12 C C C A 12 C C C C C C C A 12
Thus, this Integral property on 4 rounds could be extended by one more round at the beginning leading to a 5 rounds distinguisher with 2 48 chosen plaintexts remarking that

C C C A 12 A 48 C A 48 A 48 C C C A 12 is obtained from A 48 C A 48 A 48 C C C C A 48 C A 48 A 48 C C C A 12 A 48 C A 48 A 48
and do not required the whole codebook but only 2 48 chosen plaintexts. Thus, we are able to construct an Integral attack on 7 rounds with a time complexity of about 2 48 encryptions to recover half of the key improving the state-of-the-art concerning the best Integral attack on Prince.

Present

Present [START_REF] Bogdanov | Present: an Ultra-Lightweight Block Cipher[END_REF] is a popularly analysed lightweight cipher, published in 2007 and having been cited for over 1000 times by the end of 2015. Present has a block size of 64 bits, and consists of 31 rounds, where each round is simply involving an XOR with a round key, a layer S comprising 16 parallel applications of a 4 × 4 Sbox and a bit permutation layer L such that the output bits of each Sbox spread uniformly to bit locations which are 16 bits apart. We can thus view Present as being an NX structured cipher, similar to Prince.

For our purpose, we will exploit the ANF of the Sbox outputs of Present, which is listed as follows [START_REF] Wu | Integral Attacks on Reduced-round Present[END_REF]:

y 3 = 1 ⊕ x 0 ⊕ x 1 ⊕ x 3 ⊕ x 1 x 2 ⊕ x 0 x 1 x 2 ⊕ x 0 x 1 x 3 ⊕ x 0 x 2 x 3 (1)
y 2 = 1 ⊕ x 2 ⊕ x 3 ⊕ x 0 x 1 ⊕ x 0 x 3 ⊕ x 1 x 3 ⊕ x 0 x 1 x 3 ⊕ x 0 x 2 x 3
(2)

y 1 = x 1 ⊕ x 3 ⊕ x 1 x 3 ⊕ x 2 x 3 ⊕ x 0 x 1 x 2 ⊕ x 0 x 1 x 3 ⊕ x 0 x 2 x 3 (3)
y 0 = x 0 ⊕ x 2 ⊕ x 3 ⊕ x 1 x 2 (4)
Note that from the above, the algebraic degree of the coordinate Boolean functions of the Present Sbox is 2 for the LSB y 0 and 3 for the rest.

We begin with a multiset of 2 4 elements such that the 4 rightmost bitslices collectively form a 4-bit P word, which the other bitslices are c. For compactness of notation, we denote by c s the contiguous sequence of s bitslices each of which is a bit tuple of the form c.

• Input: c 16 , c 16 , c 16 , c 12 a 3 a 2 a 1 a 0 • S in R1: → c 16 , c 16 , c 16 , c 12 a 3 a 2 a 1 a 0
The bit tuples propagate unchanged through the Sbox layer in Round 1.

• L in R1: → c 15 a 3 , c 15 a 2 , c 15 a 1 , c 15 a 0 The linear layer L in Round 1 moves the a i bit tuples (i ∈ {0, . . . , 3}) to other bitslice positions, such that there is one a i bit tuple in each 16-bit word state of Present.

• S in R2: → c 12 α 3 3 a 3 , c 12 α 3 2 a 2 , c 12 α 3 1 a 1 , c 12 α 3 0 a 0 where α i ∈ {c, a i } Remark. On input c 3 a i , the output from the Sbox is α 3 i a i , where each α i is either a c tuple (all constant '0's or constant '1's), or a i including its bitwise complement. This can be seen by analyzing the ANF of the Sbox, noting that in this case only the input bit x 0 varies as per the bit tuple sequence, while the other bits x 1 x 2 x 3 are constants. Therefore y 0 will be x 0 or its complement x 0 , thus will be an a i tuple.

• L in R2: → (c 3 α 3 c 3 α 2 c 3 α 1 c 3 α 0 ) 3 c 3 a 3 c 3 a 2 c 3 a 1 c 3 a 0
The linear layer causes each 4-bit input to the Sbox in the next layer to be of the form c i α i or c 3 a i .

• S in R3: → (α 4 3 α 4 2 α 4 1 α 4 0 ) 3 α 3 3 a 3 α 3 2 a 2 α 3 1 a 1 α 3 0 a 0 As per the above analysis for S in R2, we have discussed how an input c 3 a i propagates through the Sbox. What remains is to analyze the propagation of the input c 3 α i through the Sbox. Recall that α i ∈ {c, a i }, thus an input c 3 α i is in fact the union of two types of inputs, i.e. c 3 a i ∪ c 3 c. The output will therefore be α 3 i a i or c 4 .

• L in R3: → (α 3 α 2 α 1 α 0 ) 15 a 3 a 2 a 1 a 0

The linear layer permutes the bit tuples such that every Sbox input in the next layer is of the form α 3 α 2 α 1 α 0 except for the rightmost Sbox whose input is a 3 a 2 a 1 a 0 .

• S in R4: → (e 4 ) 15 a 3 a 2 a 1 a 0 An α 3 α 2 α 1 α 0 input to an Sbox comprises four bitslices α i , each of which could be a c or a i tuple. This means that each bitslice is either (in the case that it is c) a bit multiset with one unique element of multiplicity 2 4 , or (in the case that it is a i ) a bit multiset with two unique elements ('0' and '1') each of multiplicty 2 3 . In either case, the bit multiset exhibits even parity, i.e. its elements have even multiplicity.

Composing the four bitslices back into the 4-bit word, the 4-bit input α 3 α 2 α 1 α 0 to the Sbox is therefore also a multiset of property E. Since the Sbox is bijective, therefore this E property is preserved through to the output. Denote its output by e 4 with each e to represent a bit tuple of even parity.

• L in R4: → e 15 a 3 , e 15 a 2 , e 15 a 1 , e 15 a 0 The linear layer causes the 4-bit inputs to the Sbox in the next layer to be of the form e 4 .

• S in R5: → (? 3 e) 16 All four input bit tuples going into any Sbox have even parity (note that the same is also true for a i ).

We focus on the LSB output y 0 of any Sbox, whose expression is given in equation ( 4). Notably, the only nonlinear term is the AND (x 1 ∧x 2 ) term between x 1 and x 2 , which is in this case (e ∧ e), leading to an output bit tuple that is also e, preserving the segment/pattern boundaries.

As each of the other terms in y 0 i.e. x 0 , x 2 , x 3 to be XORed to x 1 x 2 also has even parity, therefore the output bit y 0 of the Sbox would have even parity.

• L in R5: → ? 48 (e) 16 The linear layer moves all the LSB output bits y 0 of all 16 Sboxes to the rightmost 16 bit positions, therefore at the end of Round 5, all the 16 rightmost bit tuples have even parity, and thus are balanced, i.e. = 0.

We have empirically tested this for several runs, each time with 2 16 random structures of plaintext multisets and keys: it is veried that the rightmost 16 bits after 5 rounds of Present have zero integral sum with probability 1. This result contrasts with the best-known integrals for Present reported in [START_REF] Wu | Integral Attacks on Reduced-round Present[END_REF], where a 5-round and a 7-round integral were demonstrated such that a zero integral sum is detected only in the single rightmost bit after ve (resp. seven) rounds.

On the contrary, our tuple integral based on a multiset of size 2 4 , has 16 times more checkable bits that provide more bit ltering conditions, thus better ltration power during the key recovery stage.

Furthermore, the single-bit integrals in [START_REF] Wu | Integral Attacks on Reduced-round Present[END_REF] were tracked based on the maximal algebraic degree d of the coordinate Boolean function producing the rightmost LSB at the nal output. This is done by collecting enough dierent texts within a multiset such that there are more than 2 d texts in order to exploit the higher-order derivative property [START_REF] Knudsen | Truncated and Higher Order Dierentials[END_REF], which basically tests for a zero sum.

In contrast, our integral is tracked by bitslice tuples through the round operations, notably through the Sbox's output bits, and within the Sboxes through the AND and XOR operations that make up the ANF expressions of an Sbox's coordinate Boolean functions. Such a bit tuple approach thus enables to observe richer internal structures within the multisets and bitslice tuples.

Rectangle

Rectangle [START_REF] Zhang | Rectangle: a Bitslice Lightweight Block Cipher Suitable for Multiple Platforms[END_REF] is a bit-sliced lightweight cipher, such that in each round it comprises an XOR based key addition, and then just an Sbox layer S followed by bitwise rotation layer R, thus Rectangle can be viewed as an NRX cipher, i.e. involving the primitive operations AND, rotation (ROT) and exclusive-OR (XOR). It has a 64-bit block size and 25 number of rounds.

Zhang et al. [START_REF] Zhang | Integral Attack against Bit-oriented Block Ciphers[END_REF] reported a 7-round integral distinguisher needing a multiset of 2 36 elements. Kosuge et al. [START_REF] Kosuge | Integral Attack on Reduced-Round Rectangle[END_REF] reported an 8-round integral distinguisher requiring a huge multiset of 2 60 elements. Both these integrals track that the integral sum equals zero in some output bits.

In contrast, we demonstrate how tuples can apply to Rectangle by using much smaller multisets, and track more structures in the output bits in contrast to zero sums, i.e. we track the bitslice tuples.

The Sbox S of Rectangle can be represented in terms of its ANF as:

y 3 = x 1 ⊕ x 3 ⊕ x 0 x 2 ⊕ x 0 x 3 ⊕ x 1 x 2 ⊕ x 1 x 2 x 3 (5)
y 2 = 1 ⊕ x 2 ⊕ x 3 ⊕ x 0 x 1 ⊕ x 0 x 2 ⊕ x 1 x 2 ⊕ x 2 x 3 ⊕ x 0 x 1 x 2 (6)
y 1 = 1 ⊕ x 0 ⊕ x 1 ⊕ x 2 ⊕ x 1 x 3 (7)
y 0 = x 0 ⊕ x 2 ⊕ x 3 ⊕ x 0 x 1 (8)
As an aside, note that the algebraic degree of the coordinate Boolean functions producing two of its output bits i.e. y 0 and y 1 is 2, versus degree of 3 for the other two output bits. Rectangle's state can be represented as a rectangle of 4 × 16 bits as follows:

x Consider if we had an input multiset of 2 4 elements of the following form:

a 0 ccc cccc cccc cccc a 1 ccc cccc cccc cccc a 2 ccc cccc cccc cccc a 3 ccc cccc cccc cccc
We then observe its progagation as detailed below:

• S in R1: This propagates essentially unchanged through the Sbox layer in round 1, because we have four bit tuples a 3 a 2 a 1 a 0 forming the leftmost column, entering one Sbox, and constant bit tuples entering the other Sboxes. Alternatively, viewed as 4-bit column-words, we have: PCCC CCCC CCCC CCCC

• R in R1: After bitwise rotation in round 1, we have: • S in R2: At the leftmost column, we have ccca 0 entering the Sbox. Analyzing the Sbox's ANF, we see that the following bit tuples will be obtained at the output: y 0 : α 0 ∈ {a 0 , c}; y 1 : a 0 ; y 2 : α 0 ∈ {a 0 , c}; y 3 : α 0 ∈ {a 0 , c} Similarly, for the other input tuples with one a j entering the Sbox, we have:

x 3 x 2 x 1 x 0 = cca 1 c →        y 0 : α 1 ∈ {a 1 , c} y 1 : α 1 ∈ {a 1 , c} y 2 : α 1 ∈ {a 1 , c} y 3 : α 1 ∈ {a 1 , c} x 3 x 2 x 1 x 0 = ca 2 cc →        y 0 : a 2 y 1 : a 2 y 2 : α 2 ∈ {a 2 , c} y 3 : α 2 ∈ {a 2 , c} x 3 x 2 x 1 x 0 = a 3 ccc →        y 0 : a 3 y 1 : α 3 ∈ {a 3 , c} y 2 : α 3 ∈ {a 3 , c} y 3 : α 3 ∈ {a 3 , c}
• R in R2: Therefore, after going through rotation, we have: • R in R4: After rotation, we have:

α 0 α 1 α 3 * * α 0 ⊕ α 2 α 1 α 3 * * α 0 α 2 α 3 α 2 α 3 α 2 α 3 α 2 α 1 α 0 α 1 α 0 α 1 α 1 α 3 * * α 0 ⊕ α 2 α 1 α 3 * * α 0 α 2 α 3 α 2 α 3 α 2 α 3 α 2 α 1 α 0 ⊕ α 1 α 0 ⊕ a 0 α 1 α 0 α 2 α 1 α 0 α 1 α 0 α 1 α 0 α 1 α 3 * * α 0 α 2 α 1 α 3 * * α 0 α 2 α 3 α 2 α 3 α 2 α 3 α 1 α 0 ⊕ α 1 * α 0 α 1 α 3 * * α 0 α 2 α 1 α 3 * * α 0 α 2 α 3 α 2 α 3 α 2 α 3 α 2
• S in R5: In Round 5, passing through the Sbox layer obtains: To see why e tuples are obtained at the output of the Sbox in the leftmost column, note that the input tuples are of the form (α 1 , α 2 , α 1 α 3 , α 0 ), and recall that α i ∈ {a i , c}. Therefore, the possible input tuples to the Sbox are:

Thus, we have a 5-round integral distinguisher for Rectangle that requires only 2 4 texts, and the integral zero sum can be detected in at least 6 bits. This has been corroborated by experiments, repeated for several runs. In fact, there is more structure existing in other bits that require much in-depth analysis, indeed empirical results show that the zero sum is detected in 22 bits after 5 rounds.

Analysing the rounds via tuples enables us to precisely track the evolution of multisets through more rounds than previously possible, because tuples allow to represent much richer structure than conventional integral/multiset analysis. This is why using only much smaller amounts of text (2 4 in our case for Rectangle) we can track at the bit level granularity for up to ve rounds.

Concluding Remarks

The Slice-&-Fuse paradigm considered in this paper enables to move between word and bitslice granularities when tracking the evolution of multisets and their constituent tuples through cipher rounds. Towards that aim, our proposed new types of tuples capture more structures than previously known, that are inherent in multisets and yet which have largely remained unexplored until now. Open questions include whether much richer types of tuples exist as constituents of multisets, and developing advanced approaches to track the propagation of tuples through other cipher component operations including modulo multiplications that make up exotic ciphers such as Xmx [START_REF] M'raïhi | Xmx: a Firmware-oriented Block Cipher based on Modular Multiplications[END_REF] as well as the more celebrated Idea cipher [START_REF] Lai | A Proposal for a New Block Encryption Standard[END_REF].

•

  p 01 = 01 10 01 10 . . . 01 10 • p 02 = 0101 1010 0101 1010 . . . 0101 1010 • p 03 = 01010101 10101010 01010101 10101010 . . . 01010101 10101010 • p 04 = 0101010101010101 1010101010101010 . . . 0101010101010101 1010101010101010 . • . . . and the corresponding segment duals p0j of these p 0j , j = 1 are: • p02 = 01 1010 0101 1010 . . . 0101 1010 01 • p03 = 0101 10101010 01010101 10101010 . . . 01010101 10101010 0101 . • p04 = 01010101 1010101010101010 . . . 0101010101010101 1010101010101010 01010101 . • . . . Example 1(b): For the bit tuple â1 = 0 11 00 11 00 . . . 00 11 00 11 0 , then its complement duals can be: • c 12 = 0110 1001 0110 1001 . . . 0110 1001 0110 1001 • c 13 = 01100110 10011001 01100110 10011001 . . . 01100110 10011001 • c 14 = 0110011001100110 1001100110011001 0110011001100110 1001100110011001 . . . 0110011001100110 1001100110011001

Example 2 :

 2 Note. A w-bit multiset M is said to have property P if its segment length s = 1 and its cycle length c = |M|. Consider a 3-bit multiset, thus comprising 8 elements: M = 000, 001, 010, 011, 100, 101, 110, 111

  10, 11, 11, 01, 01, 00, 00, 10 which is a 2-bit multiset with elements of segment length s = 2, and cycle length c = 8.

  all of which are multisets of property P. Notice that appending such a bit tuple a 0 has caused the resultant segment length s to become 1.

  all of which are multisets of property P. Notice that appending such a bit tuple, though of segment length s = 2, yet due to the out of sync in segment boundaries, causes the resultant segment length s to be halved, i.e. reduces to 1.

Example 4 .

 4 Consider another example 3-bit P multiset: M = 011, 111, 110, 010, 001, 101, 100, 000 which has the form â1 a 2 a 1 . Focussing on the concatenation of the two dual bit tuples â1 a 1 gives: 01, 11, 10, 00, 01, 11, 10, 00 which is a 2-bit multiset with elements of segment length s = 1, and cycle length c = 4. As the segment length s is already 1, what remains is to cause the cycle length c to increase to |M | = 8, in order for the resultant multiset to have the P property.

  R3: → e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e

• M in R3: → e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e

α 0 c c a 3 a 2 c c c c c c c c c c α 1 c c α 3 a 2 c c c c c c c c c c α 1 a 0 c c c α 1 α 0 c c α 3 α 2 e α 0 α 2 c α 3 α 2 α 3 α 2 c c c c c α 1 α 0 α 1 α 0 c α 1 α 3 e α 0 α 2 c α 3 α 2 α 3 α 2 c c c c c α 1 α 0 ⊕ α 1 •α 0 c α 1 ⊕ α 3 e α 0 ⊕ α 2 c α 3 α 2 ⊕ α 3 α 2 c c c c c α 1 a 0 α 1 c α 1 α 3 e α 0 ⊕ a 2 c α 3 α 2 ⊕ α 3 α 2 c c c c c α 1 α 0 ⊕ α 1 α 0 c c α 1 α 0 α 1 α 0 c α 1 ⊕ α 3 e α 0 α 2 c α 3 α 2 α 3 α 2 c c c c α 1 α 0 ⊕ α 1 α 0 c α 1 α 3 e α 0 α 2 c α 3 α 2 α 3 α 2 c c c c •α 2 α 3 α 2 α 3 α 2 α 3 α 2 α 1 α 0 α 1 α 0 α 1 α

 2122c1 c c c c c c c c c α 1 α 0 c c α 3 α 2 c c c c c c c c • S in R3: Passing through a subsequent Sbox layer gives:α 0 c α 1 ⊕ α 3 e α 0 ⊕ α 2 c α 3 α 2 ⊕ α 3 α 2 c c c c c α 1 a 0 α 1 α 0 c α 1 α 3 e α 0 ⊕ a 2 c α 3 α 2 ⊕ α 3 α 2 c c c c c α 1 α 0 ⊕ α 1 α 0 c α 1 ⊕ α 3 R in R3:After rotation, we have: S in R4: Going through another Sbox layer results in the following:α 0 α 1 α 3 * * α 0 ⊕ α 2 α 1 α 3 * * α 0 0 α 1 α 3 * * α 0 ⊕ α 2 α 1 α 3 * * α 0 α 2 α 3 α 2 α 3 α 2 α 3 α 2 α 1 α 0 ⊕ α 1 α 0 ⊕ a 0 α 1 α 0 α 1 α 3 * * α 0 α 2 α 1 α 3 * * α 0 α 2 α 3 α 2 α 3 α 2 α 3 α 2 α 1 α 0 α 1 α 0 α 1 α 0 α 1 α 3 * * α 0 α 2 α 1 α 3 * * α 0 α 2 α 3 α 2 α 3 α 2 α 3 α 2 α 1 α 0 ⊕ α 1 α 0 ⊕ a 0 α 1

e * * * α 0 ⊕ α 2 * * * α 0 α 2 * * * e α 1 α 0 α 1 α 0 α 1 eα 2 α 3 α 2 α 3 α 2

 12 * * * α 1 α 3 * * * α 3 * * * e α 0 ⊕ α 1 α 0 ⊕ a 0 α 1 α 0 * * * * α 0 * * * α 0 α 2 * * * e α 3 α 2 α 3 α 2 α 3 e * * * α 1 α 3 * * * α 1 α 3 * * * *

Table 2

 2

summarizes the revised truth table for XOR based on our analysis in this subsection.

Table 2 .

 2 Revised truth table of XOR on multisets based on tuple formulations.

  15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 x 0 x 31 x 30 x 29 x 28 x 27 x 26 x 25 x 24 x 23 x 22 x 21 x 20 x 19 x 18 x 17 x 16 x 47 x 46 x 45 x 44 x 43 x 42 x 41 x 40 x 39 x 38 x 37 x 36 x 35 x 34 x 33 x 32 x 63 x 62 x 61 x 60 x 59 x 58 x 57 x 56 x 55 x 54 x 53 x 52 x 51 x 50 x 49 x 48

Acknowledgements

We thank the anonymous Mycrypt 2016 reviewers and Ana S l mean for constructive and critical comments that have improved this paper. RP is supported in part by the Malaysian Ministry of Education's Fundamental Research Grant Scheme under the project ProvAdverse.

A forward SPN round mainly consists of an Sbox layer S acting on nibbles and a diusion layer M = SR • M , before a typical keyed XOR operation; where SR is the AES ShiftRows operation and M is an involutive operation acting on independent columns at a time. [START_REF] Morawiecki | Practical Attacks on the Round-reduced PRINCE[END_REF] observed that M can be expressed in terms of bitwise equations as follows. For the leftmost and rightmost columns, the output nibbles (one in each row below, and each row comprising its constituent four bits) are of the form:

On the other hand, the output nibbles of the inner two columns are:

The middle layer is of the form: S -1 • M • S, while a backward SPN round comprises the functions M -1 and S -1 . Since Prince rounds essentially comprise the Sbox layer and the diusion layer M , the entire cipher consists of only AND and exclusive-OR (XOR) operations, thus it is an AND-XOR structured cipher.

Some previous results on integral and bitslice tuple tracking through Prince have been proposed in [START_REF] Jean | Security Analysis of Prince[END_REF][START_REF] Morawiecki | Practical Attacks on the Round-reduced PRINCE[END_REF]. More precisely, in [START_REF] Jean | Security Analysis of Prince[END_REF][START_REF] Morawiecki | Practical Attacks on the Round-reduced PRINCE[END_REF] a classical integral property was presented as follows: with one active nibble (i.e. 2 4 chosen plaintexts) is transformed into a balanced property on each nibble after rounds of the form SM , SM , SR -1 M SR, M -1 S -1 SM , SM , SR -1 , S -1 , which is seen eectively as 2.5 rounds since SR -1 oers little diusion. This rst-order integral property could be extended by one additional round SM at the beginning using a 4th-order integral property requiring 2 16 chosen plaintexts. Another 1st-order integral was presented in [START_REF] Morawiecki | Practical Attacks on the Round-reduced PRINCE[END_REF] needing 2 4 texts, covering the rounds SM ,SM ,S -1 M -1 , which can be considered eectively as 2.5 rounds since M does not provide full diusion compared to M . Moreover, a bitslice tuple property with three particular active bits (i.e. requiring 2 3 chosen plaintexts) was also proposed for the rounds of the form SM , SM in [START_REF] Morawiecki | Practical Attacks on the Round-reduced PRINCE[END_REF], which is eectively at most seen to be 2 rounds of Prince.

In fact, we found the following bitslice tuple property on 3 rounds of the form SM , SM and SM : cccc cccc cccc ccca 2 cccc cccc cccc ccca 1 cccc cccc cccc cccc cccc cccc cccc ccca 0 gives after three rounds of SM , SM and SM : eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee eeee This property stays true for triplets of bits placed on the 3 least signicant bits of the Sbox output.

In more detail, this property starts with an input multiset as follows:

A Integrals of Crypton and mCrypton Crypton v1.0 and mCrypton are two block ciphers proposed by C. H. Lim et al. [START_REF] Lim | A Revised Version of Crypton -Crypton V1.0[END_REF][START_REF] Lim | Korkishko: mCrypton -A Lightweight Block Cipher for Security of Low-Cost RFID Tags and Sensors[END_REF]. Crypton was one of the candidates of the AES competition, acting on 128-bit blocks under keys of length 128, 192 or 256 bits whereas mCrypton is its equivalent lightweight version acting on 64-bit blocks under keys of length 64, 96 or 128 bits.

Both have the same design principle based on an SPN structure with an Sbox layer and a linear layer composed of a bit permutation and a matrix transposition. The bit permutation could be represented by a matrix multiplication where the MDS bound is not reached (few column elements have an input/output weight of 4 instead of 5 in the case of an MDS transformation). For the rest of this subsection, we will denote the block size as 16n with n = 8 for Crypton and n = 4 for mCrypton.

We are not able to directly exhibit bitslice properties in the cases of Crypton and mCrypton. We conjecture that this fact is linked with the inherent design of the ciphers: the Sbox layer and the bit permutation act on dierent word sizes leading to impeding the possible properties at bit level. However, we are able to improve the classical integral property used in [START_REF] D'halluin | Attack on Six Rounds of Crypton[END_REF] on Crypton and that also works on mCrypton: we start with one active word at the beginning (whereas the other words are constant) and that gives a zero integral sum in each word after three rounds. As the linear layer does not have the MDS property, we are able to construct a new four-round integral property that works for both Crypton and mCrypton. More precisely, the following 3rd-order integral property holds on 4 rounds requiring only 2 3n chosen plaintexts. Indeed: Thus, we could improve in the case of Crypton the data/time complexity of the 6round attack presented in [START_REF] D'halluin | Attack on Six Rounds of Crypton[END_REF] by a factor 2 16 for the time complexity and by a factor 2 8 for the data complexity. Indeed, we add two rounds at the end of the previous 4-round integral property leading to guess 5 key words of the subkeys K 5 and K 6 for a cost of