P D'arco

R De Prisco

Design weaknesses in Recent Ultralightweight RFID Authentication Protocols

Keywords: Ultralightweight cryptography, authentication protocols, design weaknesses, attacks

In this paper we focus our attention on the design of several recently proposed ultralightweight authentication protocols and show that the underlying methodology is not sound. Indeed, the common feature of these protocols lies in the use of transforms, which are the main building blocks. We analyze these transforms and show that all of them present some weaknesses, which can be essentially reduced to poor confusion and diffusion in the input-output mappings. Then, exploiting the weaknesses of the transforms, we describe impersonation attacks against the ultralightweight authentication protocols in which they are used: precisely, RCIA, KMAP, SLAP, and SASI + . On average, an attack requires a constant number of interactions with the targeted tag, compared to the allegedly needed exponential number in the informal security analysis. Moreover, since the weaknesses are in the transforms, the attack strategies we describe can be used to subvert any other protocol that uses the same transforms or closely-related ones.

Introduction

Motivations for the current work. Secure authentication is a well-established research area in cryptography and several good solutions are available and used every day. Unfortunately, for low-cost inexpensive computing elements, like RFID tags, it is quite a challenging problem. These protocols involve two parties: a Reader and a Tag, both of which are small devices. The hardware imposes very strong constraints on the computing capabilities of these elements, especially on the Tag. Hence, standard techniques based on public key cryptography or on symmetric key primitives cannot be employed in the design.

Due to the above constraints, there are two choices: either to give up because it is difficult, or probably impossible, to achieve the security standard we get with other, much more powerful, digital devices, or to try to achieve a reasonable security level also in applications using these cheap computing elements. It goes without saying that they are becoming a crucial end point of smart automated solutions in the so called Internet of Things. Thus, it is desirable to follow the latter option.

However, unfortunately, the current state of knowledge is quite poor: we do not have any impossibility result within a model for such ultralightweight protocols but, at the same time, all ultralightweight authentication protocols, designed according to ad hoc approaches, proposed in the last years, have been shown to suffer several weaknesses of different significance and impact: in many cases the weaknesses have been used to break the protocols.

In some papers warnings have been rised against such solutions. In [START_REF] D'arco | On Ultralightweight RFID Authentication Protocols[END_REF] a full analysis of one of the most representative (at that time) ultralightweight authentication protocol was provided, and in general the limits of such approaches, not based on sound security arguments, were stressed. Moreover recently, in [START_REF] Avoine | Pitfalls in Ultralightweight Authentication Protocol Designs[END_REF], a full guide to the common pitfalls which are usually present in the design of ultralightweight authentication protocols has been provided to designers and practitioners.

As a matter of fact, ad hoc protocols with informal security analyses continue to be presented at a considerable rate and they are broken quickly after publication 1 . Compared to the first protocol proposals of a few years ago, the new feature which almost all newer protocols exhibit, is that some more involved transforms of the data stored in the tag memory are used in order to construct the messages the Reader and the Tag send to each other to be confident of the reciprocal identities. However, as for the earlier protocols, also for these, sort of generation 2.0 ultralightweight authentication protocols, the informal security analyses are based solely on the following, questionable and very weak, conclusion: since the transforms are complex, only the legitimate parties who share the secret keys can produce the correct messages required by the authentication protocol; for the same reason, no adversarial entity, without the secret keys, can be successful with non negligible probability, that is, the best attack that can be applied is to guess the secret keys, which belong to an exponentially large set. In other words the entire security proof, in most cases, reduces to the alleged complexity of the transforms.

Our Contribution. Among the many novel ultralightweight protocols appeared in the literature in the last two years, we concentrated our attention on: KMAP [START_REF] Mujahid | A New Ultrlightweight RFID Authentication Protocol for Passive Low Cost Tags: KMAP[END_REF], RCIA [START_REF] Mujahid | RCIA: A New Ultralightweight RFID Authentication Protocol Using Recursive Hash[END_REF], SASI + [START_REF] Mujahid | A New Ultralightweight RFID Mutual Authentication Protocol: SASI Using Recursive Hash[END_REF], and SLAP [START_REF] Luo | SLAP: Succint and Lightweight Authentication Protocol for Low-Cost RFID System[END_REF]. All these protocols base their security properties upon some transforms. Our attention was caught because they appear to be more structured, compared to other previous proposals. The transforms essentially try to protect their input values by masking them via a processing stage, in which some secret values are involved and elementary operations, allowed by the low-power computational devices, are applied. We have studied such transforms and pointed out that they achieve poor confusion and diffusion. Moreover, exploiting the weaknesses found, we construct impersonation attacks against KMAP, RCIA, SASI+ and SLAP, which reduce from exponential to constant the number of trials needed to an adversary to impersonate the Reader to a Tag. We remark that the results on the transforms can be used to attack any protocol based on them.

Preliminaries: transforms

Let us look at the transforms used in the authentication protocols we are dealing with. Due to lack of space, all proofs are omitted from this abstract. Pseudo-Kasami codes. Pseudo-Kasami codes, used in [START_REF] Mujahid | A New Ultrlightweight RFID Authentication Protocol for Passive Low Cost Tags: KMAP[END_REF], are defined as follows. Let x = x 1 , . . . , x n be a string of n bits and let s be an integer, called seed, such that 1 ≤ s ≤ n. Let y = CRshift(x, s), where y is obtained from x by a circular right shift of s positions. Then, the pseudo-Kasami code of x is defined as pKc(x, s) = x ⊕ y. Here is an example, where n = 24 and the seed s = 6: The following lemma holds: Lemma 1. Let x = x 1 , . . . , x n be a string of n bits, and let s be a seed for the pseudo-Kasami code pKc(x, s) such that n is a multiple of s. Let x be a new string obtained from x by flipping n/s bits, all at distance s from each other. Then pKc(x, s) = pKc(x , s).

An example helps in understanding the above result. Let us consider the same bitstring x considered before, and let us apply the lemma starting from position j = 2.

x = 110101 100101 111100 000110 y = 000110 110101 100101 111100 pKc(x , s) = 110011 010000 011001 111010 It is easy to check that pKc(x, s) and pKc(x , s) coincide. Let hw(•) denote the Hamming weight of a binary string, i.e., the number of bits equal to one. The following results also hold: Lemma 2. Let x = x 1 , . . . , x n be a string of n bits chosen uniformly at random, and let s be an integer chosen uniformly at random such that 1 ≤ s ≤ n. Moreover, let x be a new string obtained from x by flipping one bit. Then

Pr[hw(pKc(x, s)) = hw(pKc(x , s))] = n+1
2n . Lemma 3. Let x = x 1 , . . . , x n be a string of n bits chosen uniformly at random. Let x be a new string obtained from x by flipping two randomly selected bits. Then, for any seed s such that 1 ≤ s ≤ n, it holds that: a) pKc(x, s) and pKc(x , s) are equal with probability 1 (n-1) b) pKc(x, s) and pKc(x , s) differ in two bits with probability n•(n-2) n 2 (n-1) c) pKc(x, s) and pKc(x , s) differ in four bits with probability n 3 -3n+2

n 2 (n-1) d) Pr[hw(pKc(x, s)) = hw(pKc(x , s))] = 3n 2 +3n-2 8n•(n-1) .
Finally, the pseudo-Kasami code transform exhibits the following structural property: Lemma 4. Let x = x 1 , . . . , x n be a string of n bits chosen uniformly at random, and let the seed s be equal to n/2. Then, pKc(x, s) is the concatenation of two equal substrings of n/2 bits.

Recursive Hash. Recursive hash was defined in [START_REF] Mujahid | RCIA: A New Ultralightweight RFID Authentication Protocol Using Recursive Hash[END_REF]. Let x be a string of n bits, x = b 1 , b 2 , . . . , b n , and let and z be integers such that is a divisor of n and z = n/ . Moreover, let s be an integer value, called seed, such that 1 ≤ s ≤ z. Then, dividing x into z chunks x 1 , . . . , x z of bits each,

x i = b (i-1)• , b (i-1)• +1 , . . . , b i• -1
, and denoting with Rot(x, y) a right rotation of the string x by y positions 2 , the recursive hash of x and s, denoted by Rh(x, s) for short, is defined as:

x 1 ⊕ x s , . . . , x s-1 ⊕ x s , Rot(x s , hw(x s )), x s+1 ⊕ x s , . . . , x n ⊕ x s .
That is, each chunk c i of the recursive hash is the ⊕ of chunks x i and x s , except for chunk c s , which is equal to x s right rotated by its Hamming weight.

Let us look at an example: let n = 24 and x = 100100101011110101111110. Moreover, let = 6 and, thus, z = 4. We get:

x = x 1 x 2 x 3
x 4 100100 101011 110101 111110 Let the seed s be equal to 3. The selected chunk is x 3 = 110101 whose Hamming weight is hw(x 3 ) = 4. Hence, the right rotation of x 3 is 010111. The recursive hash Rh(x, s) is:

x = x 1 x 2 x 3
x 4 100100 101011 110101 111110 x 3 replicated 110101 110101 110101

x i ⊕ x 3 010001 011110 001011 x 3 rotated 010111 Rh(x, s) 010001 011110 010111 001011 c i c 1 c 2 c 3 c 4
Lemma 5. Let , n and z integers such that is a divisor of n and z = n/ . Moreover, let x = x 1 , . . . , x n be a string of n bits chosen uniformly at random, and x be a new string obtained from x by flipping two randomly selected bits.

Then, for any seed s ∈ {1, . . . , z}, Rh(x, s) and Rh(x , s) differ in two bits with probability equal to (n -)(n --1) n(n -1) .

Notice that the probability function is decreasing in . Since meaningful values of range from 2 to n/2, we have that the minimum value is obtained for = n 2 . Therefore, for = n 2 , it is ≈ 1 4 . Lemma 6. Let , n and z integers such that is a divisor of n and z = n/ . Moreover, let x = x 1 , . . . , x n be a string of n bits chosen uniformly at random, and x a new string obtained from x by flipping two randomly selected bits. Then, for any seed s ∈ {1, . . . , z}, Pr[hw(Rh(x, s)) = hw(Rh(x , s))] is at least

1 2 • (n -)(n --1) n(n -1) + 1 2 z • ( -1) n(n -1) + 1 2 • n - n • 1 n -1 • z-1 (z-1)/2 2 (z-1) + 1 2 • n - n • -1 n -1 • z+1 (z+1)/2

(z+1)

.

A simple study of the function (for example with a math program like Maple), shows that it is an increasing function. Since meaningful values of range from 2 to n/2, we have that the minimum value is obtained for = 2. For n = 64 the above probability is ≈ 1 2 . Conversion transform. In [START_REF] Luo | SLAP: Succint and Lightweight Authentication Protocol for Low-Cost RFID System[END_REF] the authors introduce the Cnv transform. It takes as input two binary strings of length n,

say 3 A = a n a n-1 . . . a 2 a 1 and B = b n b n-1 . . . b 2 b 1 ,
and a threshold t such that 1 ≤ t ≤ n, and produces in output a binary string Cnv(A, B, t) of length n by applying a three-step procedure. More precisely:

Step 1 (Grouping). Determine a bit grouping for both A and B. The grouping is a function of the Hamming weight of the string and of the threshold t. Let X = x n x n-1 . . . x 2 x 1 be the binary string to be bit-grouped. The grouping is defined recursively as follows: if the length of X is strictly shorter than t, then the recursion ends; otherwise, the string is split in two groups X L and X R according to its Hamming weight w = hw(X), by letting X L = x n x n-1 . . . x w+1 , the n -w leftmost bits, and X R = x w x w-1 . . . x 1 , the w rightmost bits. Then, the bit grouping procedure is applied recursively to both X L and X R . Let us consider an example. Let n = 24, X = 1011 0101 1111 1101 1101 1101 and t = 6. The Hamming weight of X is hw(X) = 18. Since |X| ≥ 6, the string is split into two substrings, the left one, X 1 , containing the leftmost 24 -18 = 6 bits, and the right one, X 2 , containing the rightmost 18 bits of X; that is, X 1 = 1011 01 and X 2 = 01 1111 1101 1101 1101.

Since |X 1 | ≥ 6, and hw(X 1 ) = 4, the string is split in X 1,1 = 10 and X 1,2 = 11 01. Both strings are shorter than the threshold 6. Hence, the recursion ends.

We proceed similarly for X 2 . Since |X 2 | ≥ 6, and hw(X 2 ) = 14, the string is split in X 2,1 = 0111 and X 2,2 = 11 1101 1101 1101. The recursion ends for X 2,1 , while X 2,2 is split in X 2,2,1 = 111 and X 2,2,2 = 101 1101 1101. Since X 2,2,1 is shorter than t = 6, then the recursion ends, while X 2,2,2 is split into X 2,2,2,1 = 101 and X 2,2,2,2 = 1101 1101. Thus, the recursion ends for the first substring, while it keeps going for the second. Indeed, since hw(X 2,2,2,2 ) = 6, then X 2,2,2,2 is split in X 2,2,2,2,1 = 11 X 2,2,2,2,2 = 01 1101. Finally, X 2,2,2,2,2 is split in X 2,2,2,2,2,1 = 01 and X 2,2,2,2,2,2 = 1101.

In the following table we report another example in a more concise form: the vertical lines indicate the splittings of the substrings. The starting string is X = 101101010101110101011111. Step 2 (Rearrangement). Once both A and B have been bit-grouped, the rearrangement phase simply swaps the two groupings, that is, the grouping found for A is applied to B and vice versa. Notice that the groupings might differ both in the number of groups and in the size of each group. Let us continue with an example. We prove the following result: Lemma 7. Given two binary strings A and B of length n, chosen uniformly at random, and a threshold t, with 1 < t ≤ n, if we flip two bits of A in the first t positions to obtain A , then

Pr[(Cnv(A, B, t), Cnv(A , B, t))differ in two bits] ≈ 1 2 • 1 6 • t 3 -2t 2 -t + 2 t(t -1) 2

KMAP

The protocol KMAP, introduced in [START_REF] Mujahid | A New Ultrlightweight RFID Authentication Protocol for Passive Low Cost Tags: KMAP[END_REF], is a mutual authentication protocol. According to the authors, "KMAP avoids unbalanced logical operations (or, and) and introduces a new ultralightweight primitive, the pseudoKasami code, which enhances the diffusion properties of the protocol messages and makes the Hamming weight of the secrets unpredictable and irreversible". The protocol is also claimed to be "highly resistive against all possible attacks" and efficient in terms of communication cost and computational operations.

In this section we show that this is not the case. By building on the previous analysis of the pseudo-Kasami transform, we construct an efficient impersonation attack.

Protocol description. Tags are identified with a static identifier ID which however is never exposed. Instead, a sequence of changing "pseudonyms" IDS is used. Tag and Reader share the pseudonym IDS and two secret keys, K 1 and K 2 ; these values are updated upon each successful completion of a session of the protocol. To cope with desynchronization attacks, the Tag and the Reader maintain both the current values and the previous ones. If a Tag receives twice the initial "Hello" message (see below), then the first time it replies with the current value of IDS, while the second time falls back to the old value, assuming that there has been a desyncronization with the Reader, which has been unable to recognize the newer value.

Hence, Tag and Reader maintain two triples of values: (IDS cur , K 1,cur , K 2,cur ) and (IDS old , K 1,old , K 2,old ). For the sake of simplicity of notation, sometimes, to save space, we omit the subscript of IDS, K 1 and K 2 when we are referring to the current values IDS cur , K 1,cur and K 2,cur .

Reader Message Tag

Hello → ←IDS A||B||C → ← D Fig. 1. KMAP general structure

The protocol is a four-message protocol whose general structure is shown in Fig. 1: 1. The Reader starts the protocol by sending an "Hello" message; 2. The Tag replies with the current value of the identifier IDS cur ; 3. The Reader checks the received value IDS: if it is equal to IDS cur , then the rest of the computation is performed using K 1 = K 1,cur and K 2 = K 2,cur ; if the received value is equal to IDS old , then the rest of the computation is performed using K 1 = K 1,old and K 2 = K 2,old -that is, the old values become the current ones; otherwise, the protocol is immediately terminated. The Reader performs some computation, computing some temporary values (a seed and two temporary keys K * 1 and K * 2 ), and three sequences of bits, A, B and C, and sends a message consisting of three parts. A, B and C, which are sent to the tag; 4. The Tag checks that the values received are consistent with its own information (if not, the protocol is immediately terminated) and performs some computation to obtain a sequence of bits D, which is sent to the Reader.

Upon completion of a session of the protocol, both the Tag and the Reader update the values of ID and of the keys K 1 and K 2 , storing in (IDS old , K 1,old , K 2,old ) the values of (IDS cur , K 1,cur , K 2,cur ), and updating the latter. The Tag maintains also a failure counter, so that if there are too many unsuccessful attempts, the Tag will stop its funcionality for a while, in order to introduce delays into the attacks 4 . The details of the computation of the messages A, B, C and D are shown in Fig. 2. More specifically, the Reader chooses two random values n 1 and n 2 , and computes their xor P = n 1 ⊕ n 2 and a seed s = hw(P ) mod 64. Then, A is computed by a double rotation of n 1 , the first of a number of positions given by the weight of IDS⊕K 1 , and the second of a number of positions given by the weight of K 2 ; similarly, B is computed by a double rotation of n 2 , the first of a number of positions given by the weight of K 2 ⊕IDS, and the second of a number of positions given by the weight of K 1 ⊕n 1 . The Reader, then, computes two temporary keys, K * 1 and K * 2 , namely K * 1 = Rot(pKc(K 1 , s), pKc(n 1 , s)) ⊕ K 2 ) and K * 2 = Rot(pKc(K 2 , s), pKc(n 2 , s)) ⊕ K 1 ), and, finally, computes C, again with a double rotation, namely C = Rot(Rot(pKc(n 1 , s), pKc(K * 2 ⊕ pKc(n 2 , s)), pKc(K * 1 , s) ⊕ n 2 )). The message consisting of the concatenation of A, B, C is sent to the tag.

The Tag, upon reception of the message A||B||C, extracts the value of n 1 from A, by computing n 1 = Rot -1 (Rot -1 (A, K 2 ), IDS⊕K 1 ), and n 2 from B, by computing n 2 = Rot -1 (Rot -1 (B, K 1 ⊕ n 1 ), IDS⊕K 2 ), then computes P = n 1 ⊕ n 2 , the seed s and the temporary keys K * 1 and K * 2 . At this point, the Tag can compute the value of C * in the same way as the Reader computed C, and compare the computed value C * with the received one C. If they are equal, the Tag completes the protocol by computing and sending D and updating IDS, K 1 and K 2 as detailed in Figure 3. On the other hand, if a mismatch is detected, then the protocol is aborted and the failure counter is incremented. The failure counter is reset when a session of the protocol is successful. Impersonation attack. Analyzing the equations used in the protocol, the following observations hold:

We have shown that the design of several recently proposed ultralightweight authentication protocols is affected by a common problem: the transforms, used as building blocks in the protocols, do not provide confusion and diffusion in the input-output mappings as they should. Exploiting the corresponding weaknesses, we have shown for example how impersonation attacks against the protocols can be mounted. Attacks defeating other properties of the schemes are possible (e.g., [START_REF] Safkhani | Generalized Desynchronization Attack on UMAP: Application to RCIA, KMAP, SLAP and SASI + Protocols[END_REF]). Moreover, we have not considered important practical issues in the implementation of ultralightweight protocols (e.g., [START_REF] Armknecht | Lightweight Authentication Protocols on Ultra-Constrained RFIDs -Myths and Facts[END_REF]). Our goal was to point out that the lack of confusion and diffusion can open the door to several breaches. In the future proposals the designers should primarily check whether such basic properties are achieved by the underlying transforms. A closer look at the standard strategies used in the design of lightweight symmetric primitives might help. Actually, the most important open problem in our opinion is to come up with a reasonable model for the class of ultralightweight protocols, in order to get an in-depth understanding of possibilities and limits for these protocols.

  pKc(x, s) = 110011 010000 011001 111010

X

  = 101101010101110101011111 X, len = 24, hw = 16 10110101 0101110101011111 len = 8, hw = 5 len = 16, hw = 11 101 10101 01011 10101011111 len = 11, hw = 8 101 01011111 len = 8, hw = 6 01 011111 len = 6, hw = 5 0 11111

Step 3 .

 3 Let A = 1011 0101 1111 1101 1101 1101 and B = 1011 0101 0101 1101 0101 1111 be the strings that we have used as examples before. The grouping obtained for each of them is summarized in the following tables. A = 10 1101 0111 111 101 11 01 1101 B = 101 10101 01011 101 01 0 11111 Swapping the groupings we get: A = 101 10101 11111 101 11 0 11101 B = 10 1101 0101 011 101 01 01 1111 At this point each group of bits gets (left circularly) rotated according to the Hamming weight of the group itself. Thus we obtain: A = 110 10101 11111 110 11 0 11110 B = 01 1110 0101 101 110 10 10 1111 The final step that produces the output bitstring is simply the ⊕ of the rearranged bitstrings A and B . Completing our example, we have:

We refer the interested reader to[START_REF] Avoine | Pitfalls in Ultralightweight Authentication Protocol Designs[END_REF] for an overview of the previous work on ultralightweight authentication protocols.

Notice that the Rot(x, y) operation is equal to the CRshift(x',s) used in the previous transform. To keep the same notations used in the original papers we are analyzing, we have maintained both of them.

Notice that in this case we are numbering the bits from left to right in descending order. This is to maintain the same notation used in[START_REF] Luo | SLAP: Succint and Lightweight Authentication Protocol for Low-Cost RFID System[END_REF].

This feature, however, if implemented, exposes the Tag to an easy DoS attack.

Acknowledgment. This article is based upon work from COST Action IC1403 CRYPTACUS, supported by COST (European Cooperation in Science and Technology). We would like to thanks G. Avoine and J. Hernandez-Castro for helpful discussions on the ultralightweight topic and the content of this paper.

Reader chooses n1 and n2 randomly P = n1 ⊕ n2 s= hw(P ) mod 64 A = Rot(Rot(n1,IDS⊕K1), K2) B = Rot(Rot(n2, K2⊕IDS), K1 ⊕ n1) K * 1 = Rot(pKc(K1, s), pKc(n1, s)) ⊕ K2) K * 2 = Rot(pKc(K2, s), pKc(n2, s)) ⊕ K1) C = Rot(Rot(pKc(n1, s), pKc(K * 2 ⊕ pKc(n2, s)), pKc(K * 1 , s) ⊕ n2)) D = Rot(Rot(pKc(IDS, s) ⊕ pKc(n1), pKc(IDS, s) ⊕ pKc(K1, s)), pKc(K2, s)) Fig. 2. KMAP message computation IDS old =IDScur; IDScur = Rot(pKc(IDScur, s) ⊕ n1, pKc(n2, s)) K 1,old = K1,cur; K1,cur = pKc(K * 1,cur , s) K 2,old = K2,cur; K2,cur = pKc(K * 2,cur , s) Fig. 3. KMAP pseudonym and keys update 1. Flipping two bits of B is equivalent to flipping two bits of n 2 in some unknown positions. 2. Let P = n 1 ⊕ n 2 , where n 2 is equal to n 2 up to two flipped bits. Then P is equal to P up to two flipped bits. If the two flipped bits are the complement of each other, i.e., they are 01 or 10 respectively, we have that hw(P ) = hw(P ). Since there 2 out of 4 bit patterns that satisfy the above, this event occurs with probability 1/2. 3. If hw(P ) = hw(P ), the structure of pKc(•, s) does not change since the seed is the same. 4. If hw(pKc(n 2 , s)) = hw(pKc(n 2 , s)), then the value K * 2 does not change.

pKc(K *

1 , s) ⊕ n 2 and pKc(K * 1 , s) ⊕ n 2 differs in two bits.

hw(pKc(K

with probability 1/2, since there are two patterns of bits, i.e., 01 and 10, such that, when flipped, the overall weight of the bitstring stays the same. 7. pKc(K * 2 , s) ⊕ pKc(n 2 , s) and pKc(K * 2 , s) ⊕ pKc(n 2 , s) have the same weight with probability at least 3/8, since there are six patterns of four bits out of sixteen such that, when flipped, the overall weight of the bitstring stays the same.

Putting everything together, we can prove the following: Lemma 8. Assume an adversary eavesdrops an authentication session and stores A||B||C. Let B be equal to B up to two bits which are flipped. Then, forcing the Tag to send the old IDS and replying with A||B ||C, the adversary succeeds in impersonating the legal Reader with probability roughly equal to 1 28 .

Thus, a few interactions are sufficient to break the security of the authentication protocol. Notice that, the authors specify that "a protocol message counter has also been integrated in the KMAP which stops the functionality of the Tag for some particular time, if the counter's value exceeds the threshold 8". It means that if the attack does not succeed during the first trials, an extra delay is added due to the temporary stop of the Tag.

RCIA

The protocol RCIA, introduced in [START_REF] Mujahid | RCIA: A New Ultralightweight RFID Authentication Protocol Using Recursive Hash[END_REF], is a mutual authentication protocol. It has been designed to "provide robust confidentiality, integrity, and authentication in a cost effective manner". In RCIA, Tags use only three main operations, the bitwise and, or, and bit rotation, and the recursive hash transform scrutinized before.

Protocol description. Since the protocol is very similar to the KMAP protocol, we describe it in a very concise way. The overall structure is the same as the one of KMAP (see Fig. 1): the differences lay in the way the messages A, B, C and D are constructed, and how the pseudonym and the keys are updated. The details of RCIA are described in Fig. 4 and Fig. 5.

Reader chooses randomly n1 and n2

Fig. 4. RCIA message computation

Fig. 5. RCIA pseudonym and keys update Impersonation attack. Analyzing the equations used in the protocol, the following observations hold:

1. Flipping two bits of B is equivalent to flipping two bits of n 2 in the same positions.

Let

where n 2 is equal to n 2 up to two flipped bits. Then, P is equal to P up to two flipped bits. If the two flipped bits are the complement of each other, i.e., they are 01 or 10 respectively, we have that hw(P ) = hw(P ). Since there are 2 good bit patterns out of 4 possible bit patterns, this event occurs with probability 1/2. Putting everything together, we prove the following: Lemma 9. Assume an adversary eavesdrops an authentication session and stores A||B||C. Let B be equal to B up to two bits which are flipped. Then, forcing the Tag to send the old IDS and replying with A||B ||C, the adversary succeeds in impersonating the legal Reader with probability roughly equal to 1 4 .

Thus, a few interactions are sufficient to break the security of the authentication protocol.

SASI +

The protocol SASI + , introduced in [START_REF] Mujahid | A New Ultralightweight RFID Mutual Authentication Protocol: SASI Using Recursive Hash[END_REF], is a mutual authentication protocol. It incorporates only bitwise operations, xor, rotation and, like RCIA, the recursive hash transform. The protocol has also been implemented in hardware and shown to be efficient in terms of communication and computation costs.

Protocol description. As for RCIA, also SASI + , is basically the same as KMAP, with differences due to the way in which the messages are constructed and the way the pseudonym and the keys are updated. Fig. 6 and Fig. 7 show the details.

Reader chooses randomly n1 and n2

Fig. 6. SASI + message computation Impersonation Attack. SASI + uses the recursive hash transform. Hence, applying a similar analysis to the one applied for RCIA, we notice that:

Fig. 7. SASI + pseudonym and keys update 1. Flipping two bits of B is equivalent to flipping two bits of n 2 in some unknown positions. 2. Let P = n 1 ⊕ n 2 , where n 2 is equal to n 2 up to two flipped bits. Then, P is equal to P up to two flipped bits. If the two flipped bits are the complement of each other, i.e., they are 01 or 10 respectively, we have that hw(P ) = hw(P ). Since there are 2 out of 4 bit patterns that satisfy the above, this event occurs with probability 1/2. 3. If hw(P ) = hw(P ), the structure of Rh(•, s) does not change since the seed is the same. 4. Due to Lemma 5, Rh(n 2 , s) and Rh(n 2 , s) differs in two bits with probability at least 1 4 . 5. If this is the case, the resulting string C differs from C in two bits.

Putting everything together, the following result holds: Lemma 10. Assume an adversary eavesdrops an authentication session and stores A||B||C. Let B and C be equal, respectively, to B and C up to two consecutive bits which are flipped. Then, forcing the Tag to send the old IDS and replying with A||B ||C , the adversary succeeds in impersonating the legal Reader with probability roughly 1 8 • 1 96 .

Thus, a linear (in the size of the bitstring) number of interactions is sufficient to break the security of the authentication protocol.

SLAP

The protocol SLAP, introduced in [START_REF] Luo | SLAP: Succint and Lightweight Authentication Protocol for Low-Cost RFID System[END_REF], is a mutual authentication protocol. It uses only bitwise operations like xor, rotations, and the conversion transform. The authors stress that the conversion transform is the main security component of the system "with properties such as irreversibility, sensibility, full confusion and low complexity", with better performance compared to previous protocols. Protocol description. As for the other protocols, the general structure is the same, although for SLAP the third message has a slightly different form. Fig. 8 shows the general structure of the protocol, while Figs. 9 and 10 provide the details. In SLAP the third message is composed of only two pieces, A and one half, either the left one or the right one, of B. Hamming weight of the string stays the same, i.e., hw(X) = hw(X ) and, with high probability, Cnv(X , Y ), where X denotes the modified bitstring, is different from Cnv(X, Y ) in two bits. For example, in the example presented in [START_REF] Luo | SLAP: Succint and Lightweight Authentication Protocol for Low-Cost RFID System[END_REF], by flipping the second and the third bits of A, it follows that the final value A * ⊕ B * is modified only in the first and fourth bits. As we have formally shown before, such an event occurs in general with probability p approximatively equal to 1 12 . Analyzing the equations of the protocol, notice that:

1. Flipping two bits of A is equivalent to flipping two bits of n in the same positions. 2. If the two flipped bits of n are complementary bits, i.e., 0 and 1 or 1 and 0, the resulting bitstring n is such that hw(n ) = hw(n) and, hence,

4. Since the bitstring K 2 ⊕ n differs from K 2 ⊕ n in two bits, it follows that Rot(Cnv(K 2 , K 2 ⊕ n ), K 1 ) differs in two bits from Rot(Cnv(K 2 , K 2 ⊕ n), K 1 ) with probability p 1 12 . 5. The resulting string B differs in two bits from B and, with probability 1 2 , they have the same weight.

Putting everything together, the following result holds: Lemma 11. Assume an adversary eavesdrops an authentication session and stores A||B LorR . Let A be equal to A up to two consecutive bits which are flipped. Forcing the Tag to send the old IDS and replying with A ||B LorR , the adversary succeeds in impersonating the legal Reader with probability roughly


Yuri Gil Dantas

Richard Gay

Tobias Hamann

Heiko Mantel

Johannes Schickel

An Evaluation of Bucketing in Systems with Non-Deterministic Timing Behavior

Timing side-channel vulnerabilities constitute a serious threat against privacy and confidentiality of data. In this article, we study the effects of bucketing, a previously proposed mitigation technique against timing side channels. We present two implementations of bucketing that reside at the application and at the kernel level, respectively. We experimentally evaluate the effectiveness of these implementations in a setting with non-deterministic timing behavior, a practically relevant setting that has not been studied before. Our results show that the impact of non-deterministic timing behavior is substantial. The bucket boundaries cannot be established sharply and this reduces the effectiveness of bucketing. Nevertheless, bucketing still provides a significant reduction of side-channel capacity.

Introduction

In a side-channel attack, an adversary exploits execution characteristics of a program to deduce secret information. Timing behavior, energy consumption, EM radiation are execution characteristics on which side-channel attacks can be based. By exploiting side-channel vulnerabilities, attacks have been able to deduce sensitive information like e.g., cryptographic keys. For instance, timing attacks that are able to recover the full secret key from AES [START_REF] Bernstein | Cache-timing attacks on AES[END_REF] and RSA [START_REF] Inci | Cache Attacks Enable Bulk Key Recovery on the Cloud[END_REF] implementations have been developed. Timing attacks have also been developed against web applications [START_REF] Albrecht | Lucky Microseconds: A Timing Attack on Amazon's s2n Implementation of TLS[END_REF][START_REF] Bortz | Exposing Private Information by Timing Web Applications[END_REF].

Multiple techniques against timing side-channel attacks have been proposed like, e.g., predictive mitigation [START_REF] Zhang | Predictive Mitigation of Timing Channels in Interactive Systems[END_REF], unification [START_REF] Köpf | Transformational Typing and Unification for Automatically Correcting Insecure Programs[END_REF], or cross-copying [START_REF] Agat | Transforming out Timing Leaks[END_REF]. This article focuses on the bucketing technique [START_REF] Köpf | A Provably Secure and Efficient Countermeasure against Timing Attacks[END_REF]. Bucketing is the discretization of a program's execution times such that the results of each program run are returned at only a fixed number of points in time (buckets). Security-wise, bucketing aims to reduce the amount of information that an adversary can learn for a secret by reducing the possible number of observations. Performance-wise, bucketing allows one to navigate in a flexible fashion in the trade-off between the security provided and the performance overhead cost.

Bucketing has been evaluated in [START_REF] Köpf | A Provably Secure and Efficient Countermeasure against Timing Attacks[END_REF][START_REF] Köpf | Vulnerability Bounds and Leakage Resilience of Blinded Cryptography under Timing Attacks[END_REF][START_REF] Doychev | Rational Protection against Timing Attacks[END_REF][START_REF] Smith | Tight Bounds on Information Leakage from Repeated Independent Runs[END_REF]. The bucketing technique has been proposed in [START_REF] Köpf | A Provably Secure and Efficient Countermeasure against Timing Attacks[END_REF], along with a theoretical bound on the amount of information about the secret key that can be extracted from a timing-channel. The effectiveness of bucketing for a cryptographic implementation of modular exponentiation was demonstrated using this bound. In subsequent studies, it has been shown that guarantees on semantic security of cryptosystems remain valid when applying bucketing to mitigate timing side channels [START_REF] Köpf | Vulnerability Bounds and Leakage Resilience of Blinded Cryptography under Timing Attacks[END_REF]. The same work also provided a tighter bound on the leakage of timing channels. In [START_REF] Doychev | Rational Protection against Timing Attacks[END_REF], a systematic approach is presented in order to determine the optimal instantiation of bucketing. Recently, an even tighter bound for timing-channel leakage has been proposed, that is about the square root of the previously considered bounds [START_REF] Smith | Tight Bounds on Information Leakage from Repeated Independent Runs[END_REF].

So far, the technique of bucketing has been studied for systems with deterministic timing behavior [START_REF] Köpf | A Provably Secure and Efficient Countermeasure against Timing Attacks[END_REF]. In such systems, each given input always leads to the same timing observation. In this article, we investigate a complementary setting, namely the effect of bucketing in systems with non-deterministic timing behavior. A better understanding for this setting is needed for clarifying the effects of bucketing in a non-deterministic setting.

Bucketing can be implemented at different levels of a layered system architecture. In our research project, we developed two implementations of bucketing: one implementation at the application level, and another one inside the operating-system kernel for reducing timing side channels in Java programs. Based on these implementations, we evaluate the effectiveness of bucketing in a non-deterministic setting. More concretely, we evaluate the effectiveness of bucketing in terms of leakage bounds and reduction of side-channel capacity. Moreover, we evaluate the efficiency of our implementations.

Our results indicate that our implementations are not able to release events instantaneously at the bucket boundary, but rather within a certain interval after the bucket boundary. This leads to a large number of possible observations that an adversary can make, increasing the leakage bound on information an adversary can learn about the secret. We provide empirical estimations of the side-channel capacity to show that our implementations can significantly reduce the channel capacity by 84% (application level) and 78% (kernel level). These numbers are similar to the reduction achieved by other established techniques for mitigating timing side channels like e.g., cross-copying, as shown in [START_REF] Mantel | Transforming Out Timing Leaks, More or Less[END_REF].

The remainder of the article is structured as follows. Section 2 briefly clarifies the concept of timing side channels. Section 3 presents an overview on bucketing. Section 4 discusses the design space options for bucketing implementations and presents implementations at both application and kernel level. Section 5 provides details on our empirical evaluation of bucketing for systems with nondeterministic timing behavior. After a discussion of the related work in Section 6, we conclude in Section 7. All machinery needed to reproduce our results are publicly available. 1

Timing Side Channels

Timing side channels go back to Kocher's seminal work on timing attacks [START_REF] Kocher | Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems[END_REF]. In a timing-side channel attack, an adversary exploits correlations between the execution time of a program and the secrets that the program processes. By gathering multiple timing observations, such an adversary can learn information about these secrets, and, in the worst-case, extract all secrets.

In RSA, modular exponentiation (modExp for short) operation has been a classic example of a timing side-channel vulnerability. Consider for instance the implementation in Figure 1, which can be used to implement encryption and decryption operations of the RSA encryption scheme [START_REF] Shamir | A Method for Obtaining Digital Signatures and Public-key Cryptosystems[END_REF]. For decryption in RSA one computes p = c d (mod n), where c is the ciphertext, d is the private exponent, and n is the modulus.

The timing behavior of modExp reveals the Hamming weight of the private exponent. The private exponent d is processed by modExp bit by bit. When a bit is set (Line 4), modExp performs an additional multiplication and mod operation (Line 5). Execution of these instructions takes additional time. Thus, an adversary can learn the Hamming weight of the private exponent by performing multiple timing observations. Knowing the Hamming weight of the private exponent might be sufficient for making a brute force attack (i.e. by trying out all possible private exponent values with that Hamming weight) feasible.

1 public int modExp(int c, int d) { 2 int r = 1; 3 for (int i = 0; i < this.keySize; i++) { 4 if (d % 2 == 1) 5 r = (r * c) % n; 6 c = (c * c) % n;

Bucketing

Bucketing is a technique against timing side-channel attacks. The approach of bucketing is to discretize the timing behavior of a program by grouping different execution times into so called buckets. More concretely, bucketing allows only a set of possible execution times by delaying program executions to a set of observable times, the so-called bucket boundaries. For each event that occurs within the limits of a given bucket, the event is delayed until the boundary of this corresponding bucket. Note that this delay inherently causes a performance penalty. What one gains in exchange is a reduction of the amount of information that can be leaked through a timing side channel.

Bucketing has been initially studied as mitigation technique in systems with deterministic timing behavior [START_REF] Köpf | A Provably Secure and Efficient Countermeasure against Timing Attacks[END_REF]. That is, each given input always leads to the same timing observation. Thus, bucketing can reduce the number of timing observations to the number of defined buckets. The same article shows that bucketing in combination with input blinding2 is effective in mitigating timing side channels in cryptographic implementations.

In contrast to constant-time implementations like, for instance, unification [START_REF] Köpf | Transformational Typing and Unification for Automatically Correcting Insecure Programs[END_REF], cross-copying [START_REF] Agat | Transforming out Timing Leaks[END_REF], conditional assignment [START_REF] Molnar | The Program Counter Security Model: Automatic Detection and Removal of Control-Flow Side Channel Attacks[END_REF], or transactional branching [START_REF] Rezk | Preventing Timing Leaks Through Transactional Branching Instructions[END_REF], the goal of bucketing is not to completely mitigate timing side channels. Rather, bucketing bounds the information that an adversary can learn for a secret by reducing the possible number of observations he can make. This allows an adversary to infer some information about the secret, but at the same time reduces the performance overhead caused by the mitigation technique. A careful choice of the bound of information that is allowed to be leaked, however, can prevent adversaries from learning the complete key.

It has been shown that the amount of information that is leaked to an adversary through a timing side channel can be bounded by

log 2 n + O -1 n (1)
where O denotes the number of different timing observations and n is the amount of measurements the adversary performed [START_REF] Köpf | Vulnerability Bounds and Leakage Resilience of Blinded Cryptography under Timing Attacks[END_REF]. A bigger value of O increases the bound on leaked bits. Conversely, reducing O decreases the bound of leaked bits. Example. To showcase the leakage reduction that can be achieved by bucketing, consider a hypothetical implementation of a crypto-algorithm with a 512-bit secret key. Assume a flawed implementation that leaks the Hamming weight of the secret key (e.g., the modExp implementation from Figure 1), and deterministic timing behavior. With these assumptions, an adversary of the non-mitigated program can at most make 512 different observations, depending on the Hamming weight of the key. Instantiating Expression (1) for this example and 153 measurements by an adversary, we get a bound on the leakage of 512 bits.

This means that, in the worst case, an adversary can determine the whole key within 153 measurements. When applying an instantiation of Expression [START_REF] Agat | Transforming out Timing Leaks[END_REF] with three buckets for this example, we get a bound on the leakage of 14 bits. This means that, in order to learn the complete key, an adversary needs at least 1.64 × 10 77 measurements. This illustrates how effective bucketing can be in a setting with deterministic timing behavior.

Implementations of Bucketing Mechanisms

This section presents two implementations of bucketing: one at the application level and one inside the operating-system kernel. These implementations meet design goals concerned with the effectiveness and efficiency of the mechanism. We also evaluate the design space w.r.t. the choice of a system level, the choice of a delay mechanism and the handling of events occurring outside the last bucket.

Terminologies and Design Goals

An implementation of bucketing shall facilitate an effective and efficient reduction of timing side channels in the target program. By effectiveness, we refer to the ability of the mechanism to reduce the number of possible observations to a limited amount of points in time. By efficiency, we refer to the overhead introduced to the target program by the mechanism.

For systems with non-deterministic timing behavior, releasing events instantaneously at the corresponding bucket boundary might not be possible, e.g., due to the non-deterministic behavior of garbage collection or just-in-time compilation in Java programs. In this case, the event will rather be delayed within a certain interval of possible observations after the bucket boundary. We refer to the width of this interval as the precision of the mechanism, and to the distance between the intended bucket boundary and the mean release time of our mechanism as the bias of the implementation. A high precision and thus a small release interval is the central aspect of the effectiveness of the mechanism.

Regarding user acceptance of security mechanisms, effectiveness alone is not sufficient. The mechanism should rather also be as transparent to end users as possible. Hence, the runtime overhead added by the mechanisms shall be as low as possible while still enforcing the desired security properties. The overhead added by a bucketing implementation has two aspects: the overhead added by the delay of events until the next bucket boundary, and effects that are induced by the implementation. The first aspect is mainly affected by the choice of bucket sizes and boundaries, and is thus induced by the mitigation technique itself. Previous work on bucketing has covered the overhead added by the mitigation technique itself [START_REF] Köpf | A Provably Secure and Efficient Countermeasure against Timing Attacks[END_REF], and how bucketing can be instantiated with minimal performance overheads [START_REF] Doychev | Rational Protection against Timing Attacks[END_REF]. In this article, we focus on the overhead added by our actual implementation. This overhead, in turn, has two main aspects. Firstly, an implementation of bucketing can add a general overhead to the program, for instance due to initialization steps of the mechanism. Secondly, the bias of the implementation directly adds to the perceived overhead of the mechanism.

A generic security mechanism shall be applicable to a wide range of target programs. In this work, our focus is on bucketing for Java applications. Hence, an implementation of bucketing shall abstract from the target program as much as possible, such that it can be applied to generic programs that include a timing vulnerability. However, a generic approach that can be used for a variety of programming languages can be preferable to language-specific implementations.

In summary, we identify three main design goals for an implementation of bucketing in practice: high precision, low overhead (including bias), and applicability to a wide range of programs.

Design Space

Choice of System Level. One central consideration of the implementation of the security mechanism is the system level where the mechanism is implemented. Security mechanisms can be placed directly at the kernel level of the operatingsystem, at the application level where the target programs of the mechanism reside, or in an intermediary middleware level that is specific to the intended application domain of target programs.

Placing our implementation of bucketing in an intermediary middleware level does not meet our design goal of applicability to a wide range of target programs. Specific middleware levels can differ between different systems, and would thus require specialized implementations for each middleware level to be supported. In the following, we focus on the application and kernel level.

Regarding the three design goals identified in Section 4.1, we see both alternatives fitting for an implementation of bucketing. An implementation in the kernel level offers the advantage of applicability to target programs in different programming languages, as long as they can interact with the system level. An implementation at application level facilitates a better portability between systems running different operating systems and requires no modification of the underlying system. We implement bucketing for Java programs at application level using the runtime enforcement framework CliSeAu [START_REF] Gay | CliSeAu: Securing Distributed Java Programs by Cooperative Dynamic Enforcement[END_REF]. We also implement bucketing at kernel level as a reference to validate our findings.

Delay Mechanisms. Regarding the precision of a bucketing implementation, it is vital to achieve a high precision of the delay mechanism that is used for delaying events. We have considered two alternative techniques for delaying events: sleep mechanisms and busy-waiting loops.

We evaluated the precision of these techniques at both application and kernel level. For each system level, we performed 2 19 measurements to assess the precision of sleep and busy-waiting. On the application level, busy-waiting is on average 199.55% more precise than sleep mechanisms. On the kernel level, the precision gain of busy-waiting is on average 199.85%. For this reason, we favored busy-waiting over sleep technique in our implementations.

Handling Events Outside the Last Bucket. The theory of bucketing assumes knowledge about the worst-case execution time (WCET) of a program. In practice, knowledge about this time is usually not given. In a setting with non-deterministic timing behavior, a clear boundary for WCET does not exist in general. Effects like e.g., scheduling affect the execution time of a program.

This drawback leads to the question how the last bucket boundary shall be chosen in practice, and how events that are observed outside this last bucket shall be handled by the mechanism. We leave the choice of the last bucket boundary underspecified, as this might differ between system environments or specific requirements on the mechanism for a given target program. Thus, the last bucket boundary can be instantiated by the end user of the mechanism. Regarding the aspect of handling events outside the last bucket, we see two alternatives: such events can either be released directly when they are observed, or they can be dropped completely. Releasing events directly when they are observed by the mechanism might introduce additional observations to an adversary. This can thus lead to additional leakage. Completely dropping events, however, might be unacceptable for end users of the mitigated application. We thus choose to release such events immediately for our implementations. However, adapting this behavior is straightforward and can be done easily in both implementations.

Application Level Implementation

We implement bucketing at the application level using the runtime enforcement framework CliSeAu [START_REF] Gay | CliSeAu: Securing Distributed Java Programs by Cooperative Dynamic Enforcement[END_REF]. CliSeAu is a generic framework used to harden Java programs by dynamically enforcing security requirements. CliSeAu has a modular architecture consisting of four components: interceptor, local policy, enforcer and coordinator. For our implementation of bucketing, we focus on the interceptor and the enforcer. The interceptor component is responsible for intercepting attempts of the target program to perform security-relevant events and the enforcer component enforces the decided countermeasures on the target program. For more details about CliSeAu's architecture, we refer the interested reader to [START_REF] Gay | CliSeAu: Securing Distributed Java Programs by Cooperative Dynamic Enforcement[END_REF]. The use of a generic enforcement framework enables the support for a wide range of target programs. To instantiate our mechanism, the signature of the sensitive methods and the sizes of the buckets are provided to the framework. The event notification step before the timing-sensitive computation is performed in CliSeAu by the interceptor component. To instantiate this interceptor component, users of the mechanism provide the method signatures of timing-sensitive computations. The event delay is performed in CliSeAu by the enforcer component. To instantiate this enforcer component, users of the mechanism provide the amount of buckets to be enforced, and their corresponding boundary times. Using these two components, the CliSeAu encapsulation process modifies the target program by inlining the bucketing mechanism to the target program. Following our design decision from Section 4.2, events outside the last bucket are released immediately without delay.

Instantiating our mechanism for a specific target program involves two aspects: the specification of the monitored methods in the target program, and the instantiation of the parameters for bucket boundaries. The first aspect is given in the form of AspectJ pointcuts, while the second aspect is implemented as instantiation of an EnforcerFactory in CliSeAu with an array containing the bucket boundaries to be enforced. In practice, an instantiation of our mechanism can be achieved in 12 LOC.

Kernel Level Implementation

Our bucketing implementation in the Linux kernel provides an interface for user space target programs to incorporate bucketing in timing-sensitive computations. The Linux kernel provides multiple interfaces that can be used from application level. Among these, regular system calls and so called virtual dynamically shared objects (vDSO) are the most interesting ones for our implementation. System calls provide developers of user space programs with the ability to interact with the kernel. However, system calls triggers a context switch from user space to kernel space, where the functionality implemented by the system call is executed. The need for this context switch can be avoided by using vDSO calls. The vDSO mechanism maps kernel methods into user space contexts, such that they can be executed directly in user space without the overhead of a context switch 3 . For this reason, we implement bucketing at the kernel level using vDSO calls.

The overall workflow of bucketing in the Linux kernel is depicted on the bottom of Figure 2. Both the event notification step and the event delay are performed as vDSO calls in the kernel. The bucketing mechanism is not inlined when using our kernel level implementation. Users of our mechanism include the vDSO calls to the mechanism directly in their target programs code 4 . For this, the event notification call is executed directly before starting the timing-sensitive computation. The call returns the current time stamp inside the Linux kernel, which is stored in a local variable in the target program. After executing the timing-sensitive computation, the event release call is executed, providing the returned initial time from the notification step. The kernel implementation then delays the event before returning to the target program. Events outside the last bucket are released immediately without delay.

Similar to our implementation at the application level, instantiating our mechanism for as specific target program involves two aspects: calling the event notification method does not involve any parameters and will only initialize our mechanism by returning the time from the kernel. When calling the event delay method, the number of buckets, their corresponding boundaries, and the initial time from the notification step are provided as arguments for the call. Hence, including the definition of a local variable for the initial time, our mechanism is instantiated with 3 LOC inside the target program.

Evaluation

Our empirical evaluation investigates the effectiveness of bucketing in a nondeterministic setting in terms of leakage bounds and reduction of side-channel capacity. Our evaluation compares our implementations of bucketing in terms of precision, bias and overhead.

Evaluation Setup and Metrics. All of our experiments are carried out on a desktop machine, Intel i5 3.3GHz with 4GB of memory, running Ubuntu 14.04 with kernel 4.9.18 and using OpenJDK 8.

In our experiments, we consider a vulnerable implementation of modExp (see Section 2) that can be used in RSA operations. We simulate blinding by randomizing each message before modExp. We assume a local adversary who measures the execution time of modExp using the maximum precision measurements provided by the JVM, System.nanoTime(). Following common practices by [START_REF] Georges | Statistically Rigorous Java Performance Evaluation[END_REF], our measurements consist of two phases: start-up and experimental. In both phases, we perform 2 19 timing measurements. Note that only the results obtained in the experimental phase are considered in this article, as these measurements relate to the steady-state of modExp. For each bucket boundary, we reject outliers that lie further than three median absolute deviations from the median.

In contrast to systems with deterministic timing behavior, a program running in a system with non-deterministic timing behavior can have different execution times for the same input. Thus, we conduct multiple samples to evaluate the practical impact of our results. For the sake of space, we present three specific samples in the following sections. To evaluate the effectiveness of our implementations in reducing timing side-channels, we consider the worst-case reduction observed. Whereas to evaluate our implementations in terms of precision, bias and overhead, we consider their mean values.

In our experiments, we measure the following metrics:

-Number of Timing Observations (O): The number of different timing observations (value-wise) an adversary can gather after performing timing measurements on the program. -Channel Capacity (CC): The estimation of the amount of information (in bits) leaked from the timing channel. -Average Response Time (T resp ): The average time a user whose request was processed by the program has to wait between the time that he sent the request and the time that he obtained the response.

Empirical Results for the Leakage Bounds

We evaluate how much bucketing can reduce the amount of bits leaked by reducing O. We measure the number of different timing observations an adversary can gather after performing 2 19 timing measurements on modExp. We compute the bound on leaked bits presented in Section 3. As a result, we obtain a bound on how many bits an adversary can learn in this setting.

Experimental Design. We conduct experiments in two scenarios: with and without bucketing. For all experiments, we use a static RSA 1024-bit key with Hamming weight 700. When using bucketing, we instantiate our implementations with four buckets. For this, we chose the first three buckets equidistantly to each other and the last bucket as the estimated worst case execution time of modExp.

Finally, we compute Expression 1 with our results.

Experimental Results. Three samples of our results are described in Figure 3. One of the samples is depicted in Figure 4. no-bucketing represents our results without bucketing, whereas bucketing APPL and bucketing KRNL represent our results when using bucketing at application and kernel level, respectively.

Bucketing reduces O by 99%. Conversely, O is much larger when applying bucketing in systems with non-deterministic timing behavior. While bucketing in systems with deterministic timing behavior can reduce O to the number of defined buckets, in our case 4, bucketing APPL and bucketing KRNL reduce O to 1461 and 3737, respectively. Thus, according to Expression 1, an adversary might be able to obtain the entire key after performing 2 19 An important question for these results is to find the cause for this large number of observations in our implementations. By taking a closer look at our results, we notice that our implementations are not precise when releasing events. That is, our implementations release events within a certain interval after the bucket boundary, as illustrated in Figures 3(b) and 3(c). This substantiates our claim, discussed in Section 4.1, that releasing events instantaneously at the bucket boundary seems not to be possible in a non-deterministic setting. A possible explanation for this effect is that activities in the CPU, e.g., scheduling and system load, can cause a latency in the response time of programs.

As a result of this imprecision, an adversary can gather a large number of observations from the program even when bucketing is applied5 . A possible conclusion to be drawn is that bucketing is not effective in reducing timing side channels in systems with non-deterministic timing behavior. This conclusion, however, seems to be premature because the large number of observations can be caused by the properties described above.

In the following section, we investigate more closely how much information is actually leaked by our implementations of bucketing. In contrast to leakage bounds, which provides the worst case leakage that could possibly arise, this estimation has more practical significance with regard to our implementations.

Empirical Assessment of Key Indistinguishability

We estimate the reduction of the timing side-channel capacity in modExp achieved by bucketing in isolation. By isolation, we refer to an instantiation of a 1bucketing. As in [START_REF] Mantel | Transforming Out Timing Leaks, More or Less[END_REF], we model a timing side channel as a discrete informationtheoretic channel [START_REF] Cover | Elements of Information Theory[END_REF] with input X and output Y . The input alphabet of the channel models the space of secret inputs to a program and the output alphabet models possible timing observations. We measure the correlation between the secret inputs and possible timing observations with the Shannon's channel capacity [START_REF] Shannon | A Mathematical Theory of Communication[END_REF], denoted C(X; Y ). We statistically estimate [START_REF] Chatzikokolakis | Statistical measurement of information leakage[END_REF] the channel capacity C(X; Y ) from empirically collected timing observations. As a result, we compute the percentage reduction of CC achieved by our implementations of bucketing.

Experimental Design. Following the experimental design from [START_REF] Mantel | Transforming Out Timing Leaks, More or Less[END_REF], we generate two keys, namely key 1 and key 2 , with different Hamming weights. The purpose of this setup is to evaluate the reduction of the timing side-channel capacity for keys with different execution times. For each of the keys, we carry out experiments with and without bucketing. When using bucketing, we instantiate a 1-bucketing (with the same bucket size for both keys). Finally, we compute the CC with the help of the leakiEst tool [START_REF] Chothia | A Tool for Estimating Information Leakage[END_REF].

Experimental Results. Three samples of our results are described in Figure 5. One of the samples is depicted in Figure 6. no-bucketing represents our results without bucketing, whereas bucketing APPL and bucketing KRNL represent our results when using bucketing at application and kernel level, respectively. In Figure 5(a), we can visually see that the timing distributions of key 1 and key 2 are not overlapping. Thus, the fact whether modExp has received key 1 or key 2 can be leaked via a timing side channel. In contrast, when using bucketing (see Figures 5(b) and 5(c)), the timing distributions of key 1 and key 2 are mostly overlapping. This gives us a first hint that our implementations of bucketing were effective in removing the timing side channel in modExp.

The table in Figure 5 summarizes the results of estimating the capacity of the timing side channel using the leakiEst tool. Since we are using two different keys, the capacity of the timing side channel is 1 bit, as an adversary can at most learn one bit of information: Whether key 1 has been used or whether key 2 has been used. While for systems with deterministic timing-behavior, bucketing can reduce the capacity of timing side channels by 100%6 , our results indicate that bucketing APPL and bucketing KRNL can reduce the capacity of timing side channels by roughly 84% and 78%, respectively.

The estimated capacity of timing side channels achieved by our implementations are in the range of the ones reported in [START_REF] Mantel | Transforming Out Timing Leaks, More or Less[END_REF] for program transformation techniques. Furthermore, similar to bucketing for systems with deterministic timing behavior, our implementations significantly reduced the timing side-channel capacity. Hence, based on our results, we believe that bucketing is also effective in reducing timing side channels in systems with non-deterministic timing behavior, despite the large number of possible timing observations.

Empirical Comparison of Our Implementations

We compare our implementations in terms of precision, bias and overhead (so called general overhead in Section 4.1). Our results are described in Figure 7. Fig. 7: Empirical comparison of our implementations bucketing APPL is roughly three times more precise than bucketing KRNL when releasing events. This difference directly affects the number of timing observations one can gather from the program. bucketing APPL is also more efficient when releasing events. While bucketing APPL has a bias of 201.7 ns, bucketing KRNL has a bias of 799.8 ns. Thus, on average, bucketing KRNL releases events four times slower than bucketing APPL . In both cases, we believe that the use of JNI calls to enforce bucketing at the kernel level was the reason for such a difference. On the other hand, bucketing APPL added slightly (∼40µs) more overhead than bucketing KRNL . The reason why this happened is unclear to us at this moment.

Related Work

Program transformation mechanisms like unification [START_REF] Köpf | Transformational Typing and Unification for Automatically Correcting Insecure Programs[END_REF], cross-copying [START_REF] Agat | Transforming out Timing Leaks[END_REF], or conditional assignment [START_REF] Molnar | The Program Counter Security Model: Automatic Detection and Removal of Control-Flow Side Channel Attacks[END_REF] aim to completely mitigate timing side channels introduced by critical conditionals (i.e., conditionals whose timing behavior is directly affected by the value of a secret). In this constant-time approach, the program is modified such that critical conditionals take the same execution time for all secret inputs. Thus, each mitigated program run takes the WCET of the unmitigated program. To reduce the runtime overhead of constant-time mitigation, several approaches that incorporate a tradeoff between security guarantees and runtime overhead have been proposed. Examples for such approaches include bucketing [START_REF] Köpf | A Provably Secure and Efficient Countermeasure against Timing Attacks[END_REF] and predictive mitigation of timing channels [START_REF] Zhang | Predictive Mitigation of Timing Channels in Interactive Systems[END_REF]. Predictive mitigation of timing channels, as proposed in [START_REF] Zhang | Predictive Mitigation of Timing Channels in Interactive Systems[END_REF], offers a tradeoff between security and performance by using predicted schedules for events. If the predicted schedule is met for event observations by the mitigated program, events are delayed according to the current schedule, as this does not provide information to an adversary. If the schedule is violated, however, the schedule is adapted dynamically and events are delayed to meet this adapted schedule. The tradeoff between security and overhead can be chosen by selecting a tailored adaptation strategy for the schedule, which is called penalty policy.

In contrast to existing work in the area of bucketing, we are the first to provide an empirical evaluation of the effectiveness of bucketing in systems with non-deterministic timing behavior. Previously, the effectiveness of bucketing has been evaluated based on leakage bounds in systems with deterministic timing behavior. We do not consider optimal choices of the instantiation of bucketing, as we are interested in the effectiveness of our implementation rather than efficient choices in the security-performance tradeoff. We are not the first to evaluate the effectiveness of timing side-channel mitigation techniques empirically in general. For instance, [START_REF] Mantel | Transforming Out Timing Leaks, More or Less[END_REF] provides an empirical evaluation of different program transformations in Java programs. Their evaluation compares the effectiveness and efficiency of different program transformations, enabling developers to choose a fitting transformation for their security requirements.

Conclusion

This article investigated the impact of non-deterministic timing behavior on bucketing. Our results show that the impact is substantial. Our bucketing implementations are not able to release events sharply at the bucket boundary, but rather within a certain interval after the bucket boundary. This leads to a large number of possible observations that an adversary can make, increasing the leakage bound on information an adversary can learn about the secret. Nevertheless, we provided empirical estimations of the side channel capacity to show that our implementations can reduce the channel capacity by roughly 84% (application level) and 78% (kernel level). These numbers are similar to the reduction achieved by other established techniques for mitigating timing side channels like e.g., cross-copying, as shown in [START_REF] Mantel | Transforming Out Timing Leaks, More or Less[END_REF]. Based on these results, we believe that the large number of observations can be caused by activities in the CPU, e.g., scheduling. This observation indicates that future work towards tighter leakage bounds for non-deterministic timing behavior are desirable. A tighter bound for timing channel leakage has been recently proposed [START_REF] Smith | Tight Bounds on Information Leakage from Repeated Independent Runs[END_REF]. Computing this bound with our results seems to be computationally expensive. Thus, experiments using this bound as well as evaluation of other algorithms are left to future work.

In this paper, we studied the effectiveness of bucketing as a countermeasure against timing side channels. Whether bucketing opens other possibilities for attacks was outside scope. This might be a direction for future work, as other security mechanisms have been exploited by attackers to mount attacks.

7 dFig. 1 :

 71 Fig. 1: Implementation of modExp containing a timing side-channel vulnerability

Fig. 2 :

 2 Fig. 2: High-level workflow of our bucketing implementationsThe overall workflow of our implementation is depicted on the top of Figure 2. After program initialization, but before starting the timing-sensitive computation, the mechanism is notified about the start of the computation. The timing-sensitive computation is then executed, notifying the mechanism once it has been finished. The mechanism delays the event until the next bucket boundary is reached, continuing regular program execution afterwards.The event notification step before the timing-sensitive computation is performed in CliSeAu by the interceptor component. To instantiate this interceptor component, users of the mechanism provide the method signatures of timing-sensitive computations. The event delay is performed in CliSeAu by the enforcer component. To instantiate this enforcer component, users of the mechanism provide the amount of buckets to be enforced, and their corresponding boundary times. Using these two components, the CliSeAu encapsulation process modifies the target program by inlining the bucketing mechanism to the target program. Following our design decision from Section 4.2, events outside the last bucket are released immediately without delay.Instantiating our mechanism for a specific target program involves two aspects: the specification of the monitored methods in the target program, and the instantiation of the parameters for bucket boundaries. The first aspect is given in the form of AspectJ pointcuts, while the second aspect is implemented as instantiation of an EnforcerFactory in CliSeAu with an array containing the bucket boundaries to be enforced. In practice, an instantiation of our mechanism can be achieved in 12 LOC. 7

Fig. 3 :Fig. 4 :

 34 Fig. 3: Reduction of timing observations and leakage bounds

Fig. 5 :

 5 Fig. 5: Estimated capacity of timing side channels with 95% confidence intervals

Fig. 6 :

 6 Fig. 6: Correlation between two secret keys and their timing distributions

  scenario

  timing measurements.

	scenario		sample 1	sample 2		sample 3
		O	bound reduction	O bound reduction	O	bound reduction
	no-bucketing 374341 880494	-	365596 933315	-	417749 933315	-
	bucketingAPPL	846	9053	99.77%	1162 11909	99.68%	1461 14495	99.65%
	bucketingKRNL 2429 22331	99.35%	2842 25489	99.22%	3737 32049	99.10%

http://www.mais.informatik.tu-darmstadt.de/assets/bucketing/machinery.tar.gz

Blinding [13] is a technique that decorrelates the messages from the decryption times.

cf. Linux man-pages: http://man7.org/linux/man-pages/man7/vdso.7.html

For Java programs, the whole procedure can be done via JNI calls.

Omitted here for the sake of space, we also evaluated that keys with other Hamming weight (other than 700) also led to a similarly large number of observations.

This is derived from the assumption that bucketing can reduce the number of observations to the number of defined buckets.

Acknowledgment. This work was funded by the DFG as part of project Secure Refinement of Cryptographic Algorithms (E3) in CRC 1119 CROSSING.