Duc-Phong Le

Chik How Tan

Michael Tunstall
email: michael.tunstall@cryptography.com

Randomizing the Montgomery Powering Ladder

Keywords: Montgomery Powering Ladder, Side-Channel Analysis, Countermeasures

In this paper, we present novel randomized techniques to enhance Montgomery powering ladder. The proposed techniques increase the resistance against side-channel attacks and especially recently published correlation collision attacks in the horizontal setting. The first of these operates by randomly changing state such that the difference between registers varies, unpredictably, between two states. The second algorithm takes a random walk, albeit tightly bounded, along the possible addition chains required to compute an exponentiation. We also generalize the Montgomery powering ladder and present randomized (both left-to-right and right-to-left) m-ary exponentiation algorithms.

Introduction

Side-channel analysis is one of the most serious threats to the security of a given implementation of a cryptographic algorithm. In the traditional model, a given cryptographic algorithm is typically proven secure against various attacks under assumptions regarding the computational complexity of an attack. However, in a more practical scenario, Kocher noted that the time required to compute a cryptographic algorithm could reveal information on the keys used [START_REF] Kocher | Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[END_REF]. This was then extended to analyze differences in the power consumption of a microprocessor [START_REF] Kocher | Differential power analysis[END_REF] and the variations in the surrounding electromagnetic field [START_REF] Quisquater | Electromagnetic analysis (EMA): Measures and counter-measures for smart cards[END_REF][START_REF] Gandolfi | Electromagnetic analysis: Concrete results[END_REF]. The simplest such attack is based on the inspection of an acquired power consumption (resp. electromagnetic emanation) trace to derive information. This is referred to as Simple Power Analysis (SPA) (resp. Simple ElectroMagnetic Analysis (SEMA)). The exploitation of statistical differences in the instantaneous power consumption proposed by Kocher et al. [START_REF] Kocher | Differential power analysis[END_REF] is termed Differential Power Analysis (DPA) (resp. Differential ElectroMagnetic Analysis (DEMA)), and alternatives have been proposed using, for example, a model and Pearson's correlation coefficient [START_REF] Brier | Correlation power analysis with a leakage model[END_REF] or mutual information [START_REF] Gierlichs | Mutual information analysis[END_REF].

In choosing an exponentiation algorithm for a secure implementation, one needs to consider the possible attacks that could be applied. One can often discount attacks where input values need to be known, such as the doubling attack [START_REF] Fouque | The doubling attack -Why upwards is better than downwards[END_REF], template attacks [START_REF] Chari | Template attacks[END_REF] or DPA [START_REF] Kocher | Differential power analysis[END_REF]. Such attacks can typically be prevented by blinding input values [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF] or by using a suitable padding scheme. That is, these attacks are not typically prevented by choosing a specific exponentiation algorithm. However, one also needs to consider attacks based on inspecting a limited number of traces, such as SPA [START_REF] Kocher | Differential power analysis[END_REF], or power attacks in the horizontal setting [START_REF] Walter | Sliding windows succumbs to big mac attack[END_REF][START_REF] Clavier | ROSETTA for single trace analysis[END_REF]. The later was first introduced by Walter [START_REF] Walter | Sliding windows succumbs to big mac attack[END_REF]. His attack, the so-called Big Mac attack, applied to m-ary exponentiation, although only simulated attacks are described. Clavier et al. [START_REF] Clavier | Horizontal correlation analysis on exponentiation[END_REF] then exploited the collision correlation between selected points from two subtraces to derive information. Recent work by Bauer et al. [START_REF] Bauer | Horizontal collision correlation attack on elliptic curves[END_REF] has also detailed how one could apply such collision attacks to implementations of scalar multiplications over elliptic curves. Witteman et al. [START_REF] Witteman | Defeating RSA multiplyalways and message blinding countermeasures[END_REF] demonstrated that this attack works on an ASIC implementation. Kim et al. [START_REF] Kim | Practical second-order correlation power analysis on the message blinding method and its novel countermeasure for RSA[END_REF] also determined how one could apply such an attack to the Montgomery ladder [START_REF] Montgomery | Speeding the Pollard and elliptic curve methods of factorization[END_REF][START_REF] Joye | The Montgomery powering ladder[END_REF]. The attack model was extended by Hanley et al. [START_REF] Hanley | Exploiting collisions in addition chain-based exponentiation algorithms using a single trace[END_REF] to include an attacker that computes the correlation between carefully chosen points in a trace to detect where the output of one operation is used as the input to another operation.

In this paper, we present randomized variants of the Montgomery powering ladder that are resistant to SPA and power collision correlation attacks in the horizontal setting. The first algorithm is based on an amalgamation of two simple variants of the Montgomery powering ladder, where the content of the registers becomes unpredicable. The second algorithm is based on blinding addition chains, i.e. it takes tightly bounded random walks to compute an exponentiation. We also generalize the Montgomery powering ladder and present randomized m-ary exponentiation algorithms.

Preliminaries

Attack Model

In this paper we shall predominantly be considering an adversary that is able to take power consumption traces (or something equivalent) while a microprocessor is computing a group exponentiation algorithm. The adversary is then able to make deductions on what the microprocessor is computing. We shall consider three different attacks that require a limited number of traces when discussing the effects of our modifications to the Montgomery powering ladder.

1. The first attack is Simple Power Analysis (SPA) where one observes differences in the power consumption caused by different operations taking place. This was first demonstrated by Kocher et al. [START_REF] Kocher | Differential power analysis[END_REF] who showed that one could, given a naïve implementation, observe the difference between operations during the computation of an exponentiation in (Z/N Z) * .

2. Another attack is the use of Pearson's correlation coefficient to detect collisions in variables to deduce key values [START_REF] Clavier | ROSETTA for single trace analysis[END_REF]. For example, during the computation of an exponentiation in (Z/N Z) * using Coron's square-and-multiplyalways exponentiation algorithm, one could seek to determine the locations of multiplications with the same input. That is, operations that both take the same input should show a significant cross-correlation. 3. An extension to the collision correlation attack given above is where an adversary is able to detect collisions between the output of one operation and the input of another operation. This provides an attack where a complete defense is not possible. However, limiting the information available to an adversary can make the attack impractical since it has been shown that the error rate for this attack is significantly higher than a straightforward comparison of operations [START_REF] Hanley | Exploiting collisions in addition chain-based exponentiation algorithms using a single trace[END_REF].

We do not consider attacks that require chosen inputs, such as the doubling attack [START_REF] Fouque | The doubling attack -Why upwards is better than downwards[END_REF] or statistical differences in the power consumption over time [START_REF] Kocher | Differential power analysis[END_REF][START_REF] Brier | Correlation power analysis with a leakage model[END_REF]. This is because these attacks are typically prevented by padding or blinding the input by using a redundant representation where the details depend on the group being used [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF][START_REF] Win | On the performance of signature schemes based on elliptic curves[END_REF]. Typically, a blinded exponent is used, which is equivalent to the actual exponent, meaning that each trace must be attacked independently. The discussion of the security of the proposed algorithms will be largely informal, except where we wish to make specific claims about the amount of information available to an adversary.

The Montgomery Powering Ladder

The Montgomery powering ladder was originally proposed as a means of speeding up scalar multiplication over elliptic curves [START_REF] Montgomery | Speeding the Pollard and elliptic curve methods of factorization[END_REF], and was later shown to be applicable to all multiplicatively written abelian groups [START_REF] Joye | The Montgomery powering ladder[END_REF].

We recall the description of the Montgomery powering ladder given by Joye and Yen [START_REF] Joye | The Montgomery powering ladder[END_REF]. We consider the problem of computing y = x k in G for inputs x and k. Let n-1 i=0 k i 2 i be the binary expansion of κ with bit length n. For ease of expression we shall also denote this as (k n-1 , . . . , k 0 ) 2 . The Montgomery powering ladder relies on the following observation. Defining L j = n-1 i=j k i 2 i-j and H j = L j + 1, we have

L j = 2 L j+1 + k j = L j+1 + H j+1 + k j -1 = 2 H j+1 + k j -2 (1)
and so we obtain

(L j , H j ) = (2 L j+1 , L j+1 + H j+1 ) if k j = 0 , (L j+1 + H j+1 , 2 H j+1 ) if k j = 1 . (2)
If we consider one register containing x Lj and another containing x Hj then (2) implies that

(x Lj , x Hj ) =    x Lj+1 2 , x Lj+1 • x Hj+1 if k j = 0 , x Lj+1 • x Hj+1 , x Hj+1 2 if k j = 1 .
Given that L 0 = κ one can build an exponentiation algorithm that requires two group operations per bit of the exponent. Joye and Yen give several different versions of such an algorithm [START_REF] Joye | The Montgomery powering ladder[END_REF]. Algorithm 1 describes the most resistant to side-channel analysis version in their paper (as noted by Kim et al. [START_REF] Kim | Practical second-order correlation power analysis on the message blinding method and its novel countermeasure for RSA[END_REF] who describe implementations of cross correlation attacks on other versions).

Algorithm 1: Montgomery Powering Ladder

Input: x ∈ G, an n-bit integer κ = (kn-1, kn-2, . . . , k0)2 Output:

x κ 1 R0 ← 1 G ; R1 ← x ; 2 for i = n -1 down to 0 do 3 R ¬k i ← R k i • R ¬k i ; 4 R k i ← (R k i ) 2 ; 5 end 6 return R0
The Montgomery powering ladder, as described in Algorithm 1, has several properties that make it useful when defining a side-channel resistant implementation of an exponentiation. However, the Montgomery Powering ladder also has been shown to be vulnerable to recent collision correlation attacks in the horizontal setting [START_REF] Clavier | Horizontal correlation analysis on exponentiation[END_REF][START_REF] Hanley | Exploiting collisions in addition chain-based exponentiation algorithms using a single trace[END_REF]. In the reminder of this paper we propose alternative versions of the Montgomery powering ladder to enhance its security against horizontal collision correlation attacks. Definition 1. We define a variant of the Montgomery powering ladder as an exponentiation algorithm that has the following properties.

1. The algorithm uses two registers in the main loop containing group elements, both of which are updated in each iteration.

Each iteration of the main loop treats one bit of the exponent and contains

no more than two group operations. 3. The operands in the first group operation will only involve one or both of the registers used in the main loop. 4. The operands in the second group operation can involve one or both of the registers used in the main loop and/or some precomputed value.

The 3rd and 4th properties allow for variants of the Montgomery ladder to be defined. That is, the Montgomery ladder is in the set of possible algorithms that satisfy these criteria.

For brevity in defining algorithms, we shall concentrate on the main loop of the algorithm. The computation before and after the main loop may contain if-statements. We shall not give fully secure versions where solutions are widely known, e.g. dummy operations or redundant representations [START_REF] Coron | Resistance against differential power analysis for elliptic curve cryptosystems[END_REF][START_REF] Win | On the performance of signature schemes based on elliptic curves[END_REF][START_REF] Mangard | Power Analysis Attacks -Revealing the Secrets of Smart Cards[END_REF].

Randomizing the Montgomery Powering Ladder

We note that when computing x n using the Montgomery powering ladder, as defined in Algorithm 1, then at the end of each iteration we will have the condition where R 1 /R 0 = x, or equivalently R 0 • x = R 1 . Thus, using the notation given above, and we allow some precomputed values to be used in the algorithm, then (2) can be rewritten as

(L j , H j ) = (2 L j+1 , L j + 1) if k j = 0 , (L j+1 + H j+1 , L j + 1) if k j = 1 . (3)
Implying that

(x Lj , x Hj ) = x Lj+1 2 , x Lj • x if k j = 0 , x Lj+1 • x Hj+1 , x Lj • x if k j = 1 .
From which we can define Algorithm 2.

Algorithm 2: A Straightforward Variant I Input: x ∈ G, an n-bit integer κ = (kn-1, kn-2, . . . , k0)2 Output: x κ 1 R0 ← 1 G ; R1 ← x ; 2 for i = n -1 down to 0 do 3 R0 ← R0 • R k i ; 4 R1 ← R0 • x ; 5 end 6 return R0 Algorithm 3: A Straightforward Variant II Input: x ∈ G, an n-bit integer κ = (kn-1, kn-2, . . . , k0)2, and kn-1 = 1 Output: x κ 1 R0 ← 1 G ; R1 ← 1 G ; 2 for i = n -1 down to 0 do 3 R1 ← R0 • R ¬k i ; 4 R0 ← R1 • x ; 5 end 6 return R0
Following the reasoning used to define (1), we can instead define

L j = n-1 i=j k i 2 i-j and H j = L j -1, giving L j = 2 L j+1 + k j = L j+1 + H j+1 + k j + 1 = 2 H j+1 + k j + 2 (4)
and so, as with (3), we obtain

(L j , H j ) = (H j + 1, L j+1 + H j+1 ) if k j = 0 , (H j + 1, 2 L j+1 ) if k j = 1 . (5)
If we consider one register containing x Lj and another containing x Hj then (5) implies that

(x Lj , x Hj ) = x Hj • x, x Lj+1 • x Hj+1 if k j = 0 , x Hj • x, x Lj+1 2 if k j = 1 .
From which we can define Algorithm 3. We note that at the end of each iteration we will have the condition where

R 0 /R 1 = x, or equivalently R 1 • x = R 0 .
Suppose that an adversary can distinguish multiplications from squaring operations, then the two above variants of Montgomery powering ladder are not immune to SPA. In line 3 of both algorithms, a squaring operation will occur for certain bit values. That is, a squaring operation will be computed if the bit value k i = 0 in Algorithm 2 and in Algorithm 3 a squaring operation occurs when k i = 1. The following randomized algorithm will deal with this problem.

We observe that Algorithms 2-3 can be blended together. That is, in loop , for some ∈ {1, . . . , n -1}, of Algorithm

2 if k = 1 one could compute R 1 ← (R 0 ) 2 followed by R 0 ← R 1 •x . Before this step R 1 /R 0 =
x, and afterwards one bit of the exponent is treated and R 0 /R 1 = x . Hence, one could continue to compute an exponentiation using Algorithm 3.

Likewise, in loop , for some ∈ {1, . . . , n -1}, of Algorithm 3, if k = 0, one could compute R 0 ← (R 0 )

2 followed by R 1 ← R 0 • x . Afterwards one bit of the exponent is treated and R 1 /R 0 = x. Hence, one could continue to compute an exponentiation using Algorithm 2. We define Algorithm 4 as an example of how Algorithms 2 and 3 could be randomly blended together. We use a random generator producing a random bit b to determine when to change from one algorithm to the other, and to determine which algorithm is used to start the exponentiation algorithm. If b = 0, the exponentiation is computed by using Algorithm 2, that is R 1 /R 0 = x. Otherwise, the exponentiation is computed by using Algorithm 3, that is,

R 0 /R 1 = x.
Suppose that an adversary is able to distinguish a multiplication from a squaring operation. Then, she would be able to determine individual bits of the exponent if she could determine if R 0 /R 1 = x or R 1 /R 0 = x . However, the following lemma shows that this information is not available. Lemma 1. An adversary analyzing an instance of Algorithm 4 is able to reduce the hypotheses for the exponent from κ to κ 11 12 by distinguishing a multiplication from a squaring operation.

Proof. If an adversary observes a squaring operation followed by a multiplication in the loop using index i, then the adversary knows one of the following operations has occurred:

Algorithm 4: Randomized Montgomery Powering Ladder

Input: x ∈ G, an n-bit integer κ = (kn-1, kn-2, . . . , k0)2, and kn-1 = 1 Output:

x κ 1 b R ← -{0, 1} ; R0 ← 1 G ; 2 if b = 0 then 3 R1 ← x ; 4 else 5 R1 ← 1 G ; 6 end 7 for i = n -1 down to 0 do 8 if b ⊕ ki = 1 then 9 b R ← -{0, 1} ; 10 end 11 R b ← R0 • R b⊕k i ; 12 R ¬b ← R b • x ; 13 end 14 return R0 1. Where R 1 /R 0 = x and k i = 0. 2. Where R 0 /R 1 = x and k i = 1. 3. Where R 1 /R 0 = x changes to R 0 /R 1 = x and k i = 1. 4. Where R 0 /R 1 = x changes to R 1 /R 0 = x and k i = 0.
At an arbitrary point, each of these occur with probability 1 4 . Likewise, if an adversary observes two multiplications in the loop using index i, hence the adversary knows one of the following operations has occurred:

1. Where R 1 /R 0 = x and k i = 1. 2. Where R 0 /R 1 = x and k i = 0.
Each of these occur with probability 1 2 . Hence, there is no information available to an adversary since for any observed sequence of operations Pr(k i = 0) = Pr(k i = 1) = 1 2 . However, if an adversary observes y consecutive pairs of multiplications then the adversary will know that y consecutive bits have the same value. If an attacker observes a pair of multiplications then the distribution of the number of subsequent pairs W of multiplications is geometric. That is, W ∼ Geometric( 3 4 ) , since the following bit has to be the same and the randomly generated bit has to be a specific value. The, by definition, the expected length of a run of multiplication is 4 3 operations, where each observation would therefore provide an expected 4 3 -1 = 1 3 of a bit of the exponent. A pair of multiplications will occur with probability 1 4 , giving an expected n/4 bits for an n-bit exponent. For an n-bit exponent an expected 1 3 × n 4 = n 12 bits can expected to be derived. Hence, κ hypotheses can be expected to be reduced to κ 11 12 hypotheses.

As with the Montgomery powering ladder shown in Algorithm 1, an attack using collisions based on the reuse of variables is not possible, but a collision attack based in the use of the output of operations is possible. One can attempt to observe whether the second operand in line 11 of Algorithm 4 is created from line 11 or line 12 in the previous iteration of the exponentiation loop. However, an analysis based on this will return the wrong key hypothesis when the algorithm changes from using (3) to (5). Lemma 2. An adversary analyzing an instance of Algorithm 4 using a collision attack an adversary would be able to reduce the hypotheses for the exponent from κ to κ Proof. If we, arbitrarily, consider the -th loop of the exponentiation loop, we have Pr(b ⊕ k i = 1) = 1 2 and the probability that b changes, and hence the algorithm being used, is also 1 2 . An adversary making a deductions using a collision attack will have to guess the value of b in two consecutive loops of the algorithm. Given a correct guess for b it will remain the same with probability 3 4 . On the assumption that an attack will validate b in the first loop the value of b in the second loop will remain the same with probability 3 4 . If it changes an incorrect result will be given. Hence, the probability that a collision would detect an incorrect key bit is 1 4 , and an adversary would be able to determine a given bit with a probability 3 4 leading to a reduction in the number of hypotheses from κ to κ

Random Walk Method

In this section, we generalize the difference between the two registers used in the Montgomery powering ladder to be some arbitrary power of the input. This leads to an algorithm that computes a group exponentiation taking a random, albeit tightly bounded, walk through the possible addition chains.

If one is working in a group where computing the inverses of an element can be readily computed, then other options for a variant of the Montgomery powering ladder are possible. We note that (2) can be rewritten as

(L j , H j ) = (H j -1, L j+1 + H j+1 ) if k j = 0 , (L j+1 + H j+1 , L j + 1) if k j = 1 . (6)
Implying that

(x Lj , x Hj ) = x Hj • x -1 , x Lj+1 • x Hj+1 if k j = 0 , x Lj+1 • x Hj+1 , x Lj • x if k j = 1 .
(6) can be rewritten as follows:

(L j , H j ) = (L j+1 + H j+1 , L j -1) if k j = 0 , (L j+1 + H j+1 , L j + 1) if k j = 1 . (7)
Implying that

(x Lj , x Hj ) = x Lj+1 • x Hj+1 , x Lj • x -1 if k j = 0 , x Lj+1 • x Hj+1 , x Lj • x if k j = 1 .
From which we can define Algorithm 5. In previous examples of Montgomery powering ladders presented in this paper R 0 has acted as an accumulator and returned the result. In Algorithm 5 the accumulator, i.e. the register containing the correct power of x at the end of each loop, shifts depending on the value of the bit of the exponent being treated. Hence, R ¬k0 is returned at the end of the algorithm.

Algorithm 5: Variant with Inverses

Input: x ∈ G, an n-bit integer κ = (k n-1 , k n-2 , . . . , k 0 ) 2 Output: x κ 1 R 0 ← 1 G ; R 1 ← x ; 2 U 0 ← x -1 ; U 1 ← x ; 3 for i = n -1 down to 0 do 4 R 0 ← R 0 • R 1 ; 5 R 1 ← R 0 • U ki ; 6 end 7 return R ¬k0
In analyzing an instance of Algorithm 5, an adversary would not be able to determine any information on bits of the exponent based on distinguishing a multiplication from a squaring operation, since no squaring operations take place. However, a collision attack is possible by observing where the multiplication with U i , for i ∈ {0, 1}, collides with the multiplications used to generate these values in line 2. If an adversary is able to determine whether U ki = x -1 or U ki = x was used, for some i ∈ {0, . . . , n -1}, then individual bits of the exponent can be determined.

We can modify [START_REF] Fouque | The doubling attack -Why upwards is better than downwards[END_REF] by choosing L j+1 = L j+1 + α and

H j+1 = H j+1 + β, giving (L j , H j ) = (L j+1 + H j+1 , L j -1) if k j = 0 , (L j+1 + H j+1 , L j + 1) if k j = 1 . ( 8
)
where L j = L j + γ, H j = H j + µ, and γ = α + β . If we choose γ as a random element from {-h, . . . h} for some small integer h, then α and β can be chosen such that γ = α + β . If we assume that α is fixed then

β = γ -α, i.e., H j+1 = H j+1 + γ -α.
Given that H j+1 is computed from L j+1 this can be done by

H j+1 = L j+1 + (γ -α -1) = L j+1 + (γ -2 α -1) if k j = 0 , L j+1 + (γ -α + 1) = L j+1 + (γ -2 α + 1) if k j = 1 .
This also removes the need to have the accumulating register change as described for Algorithm 5. If we define a value L j = L j + γ j then (8) can be rewritten as

(L j + γ j , H j + (γ j-1 -γ j ) = Lj+1 + γj+1 + Hj+1 + (γj -γj+1), L j + (γj-1 -2 γj -1) if kj = 0 , Lj+1 + γj+1 + Hj+1 + (γj -γj+1), L j + (γj-1 -2 γj + 1) if kj = 1 . ( 9
)
If we consider one register containing x L j and another containing x H j then (9) implies that (x

L j , x H j ) = x L j+1 • x H j+1 , x L j • x ∆ where ∆ = γ j-1 -2 γ j -1 if k j = 0 , γ j-1 -2 γ j + 1 if k j = 1 .
Given that L 0 = κ one can build an exponentiation algorithm as shown in Algorithm 6 where we set γ 0 = 0 to produce the correct result. Assume that γ can be arbitrarily chosen from the set {-h, . . . , h} in each iteration of computation, then ∆ ∈ {-3 h -1, . . . , 3 h + 1}. Hence, our algorithm makes use of an array of 6 h + 3 elements that stores the required values of x ∆ .

Algorithm 6: Blinded Montgomery Powering Ladder

Input: x ∈ G, an n-bit integer κ = (kn-1, . . . , k0)2, small integer h ∈ Z Output: x κ Uses: U a 6 h + 3 element array.

1 U 3 h+1 ← 1 G ; 2 for i = 1 to 3 h + 1 do 3 U 3h+1+i ← U 3h+i • x ; 4 U 3h+1-i ← U 3h+2-i • x -1 ; 5 end 6 R0 ← 1 G ; R1 ← 1 G ; α = 0 ; 7 for i = n -1 down to 1 do 8 R0 ← R0 • R1 ; 9 γ R ← -{-h, . . . , h} ; 10 ← γ -2 α + ki -¬ki ; 11 R1 ← R0 • U 3 h+1+ ; 12 α ← γ ; 13 end 14 R0 ← R0 • R1 ; 15 R0 ← R0 • U 3 h+1-α-¬k 0 ; 16 return R0
An adversary who is able to distinguish a multiplication from a squaring operation would not be able to determine any information on bits of the exponent used since no squaring operations take place. However, a cross correlation attack is possible by observing where the multiplication with U d , for d ∈ {0, . . . , 6 h+2}, collides with the multiplications used to generate these values in line 11. From these values, an adversary can derive the addition chain that was used to compute the exponentiation. This will not give an adversary the exponent, since there is no means to map the digits used to bits of the exponent, but would give an adversary an equivalent addition chain.

In determining whether an attack is practical Hanley et al. [START_REF] Hanley | Exploiting collisions in addition chain-based exponentiation algorithms using a single trace[END_REF] determine that when analyzing an implementation 192-bit exponentiation, the error rate need to be less than 22 bits. This is determined to be less than 2 54 operations, based on the boundary set for block ciphers by Biryukov et al. [START_REF] Biryukov | Key recovery attacks of practical complexity on AES-256 variants with up to 10 rounds[END_REF]. The expected number of operations can be determined using Stinson's algorithm [START_REF] Stinson | Some baby-step giant-step algorithms for the low Hamming weight discrete logarithm problem[END_REF], where an t-bit error in a n-bit hypothesis leads to the exponent in time complexity O n t/2 i=0 n/2 i [START_REF] Stinson | Some baby-step giant-step algorithms for the low Hamming weight discrete logarithm problem[END_REF]. Then one can apply a version of Stinson's algorithm where one has to treat all the values that digits can take. Given a small integer h, as defined in Algorithm 6, a t-digit error in an µ-bit hypothesis leads to the exponent in time complexity O µ µ/2 t/2 (2 h + 1)

µ 2
. That is, there are µ possible divisions of the digits, each of which will have µ/2 t/2 ways of selecting t/2 digits and each digit can take (2 h + 1) values. In practice, t will not be known so the analysis will have time complexity O µ t/2 i=0 µ/2 i (2 h + 1) i further reducing the required error rate for a successful attack.

We note that an adversary is required to derive the entire exponent as information on part of the exponent is not useful. Moreover, an adversary will not know the exponent but an equivalent addition-chain. If we consider the group exponentiation algorithm used in ECDSA (Elliptic Curve Digital Signature Algorithm) [START_REF]Public key cryptography for the financial services industry, the elliptic curve digital signature algorithm[END_REF] this provides a significant increase in security. Howgrave-Graham and Smart [START_REF] Howgrave-Graham | Lattice attacks on digital signature schemes[END_REF] noted that if a few bits of the ephemeral exponent are known for sufficiently many signatures, then the scheme can be broken, based on the so-called hidden number problem introduced by Boneh and Venkatesan [START_REF] Boneh | Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes[END_REF].

A more memory-efficient version of Algorithm 6 is described in Algorithm 7. This is a security-memory trade off where the value of γ j is still chosen at random, but the value range depend on the previous value γ j+1 . Although the available choices for γ j decreases, Algorithm 7 requires only 2 h + 2 registers to store pre-computed values instead of 6 h + 3 registers in Algorithm 6.

Generalizing the Montgomery Powering Ladder

The square-and-multiply (left-to-right and right-to-left)) exponentiation algorithms are the most efficient implementations for raising x to the power κ when the exponent is treated bit-by-bit. Furthermore, these exponentiation algorithms extend easily to any radix m for the purpose of speeding the computation. In this section, by using the random walk technique, we generalize the (both leftto-right and right-to-left) exponentiation algorithms and present new blinded m-ary exponentiation algorithms.

Algorithm 7: Blinded Montgomery Powering Ladder II

Input: x ∈ G, an n-bit integer κ = (kn-1, kn-2, . . . , k0)2, small integer h ∈ Z, U a look-up table of 2h + 2 precomputed values x -h , . . . , x h+1 . Output:

x κ 1 U h ← 1 G ; 2 for i = 1 to h do 3 U h+i ← U h+i-1 • x ; 4 U h-i ← U h+1-i • x -1 ; 5 end 6 U 2 h+1 ← U 2 h • x ; R0 ← 1 G ; R1 ← 1 G ; α ← 0 ; 7 for i = n -1 down to 1 do 8 R0 ← R0 • R1 ; 9 if α ≥ 0 then 10 γ R ← -{2 α -h, . . . , h + 1 -ki} ; 11 end 12 else 13 γ R ← -{-h -ki, . . . , 2 α + h -1}; 14 end 15 R1 ← R0 • U h+γ+k i ; 16 α ← 2 α -γ ; 17 end 18 R0 ← R0 • R1 ; 19 R0 ← R0 • U h+α+k 0 ; 20 return R0

Left-to-right algorithms

We first consider the left-to-right exponentiation. Let κ = (w -1 , w -2 , . . . , w 0 ) 2 be the m-ary representation of κ, where 0 = w i < m, w -1 = 0, and is the length of κ in radix m. As in Section 2.2, by defining L j = -1 i=j w i m i-j , we have

L j = m L j+1 + w j (10)
From then, the exponentiation algorithm will perform x Lj = (x Lj+1 ) m • x wj . Noting that x L0 = x κ . Using the random walk technique as in Section 4, we modify L j = L j + γ j where γ j can be chosen from a pre-defined set {-h, . . . , h} for some small integer h. Then (10) can be rewritten as

L j + γ j = m L j+1 + γ j + w j = m L j+1 -m γ j+1 + γ j + w j (11)
This leads to a randomized algorithm (Algorithm 8) that computes a group exponentiation taking a random, albeit tightly bounded, walk through the possible addition chains. As with Algorithm 7, Algorithm 8 also requires a look-up table of 2(m + 1) h + m -1 values to stores precomputated values. Algorithm 8 can be used in the cases where the computation of inversions is cheap, otherwise Algorithm 9 is more suitable.

-1 = 0, small integer h ∈ Z, T a look-up table of 2(m + 1) h + m -1 precomputed values x -(m+1)h-m+1 , . . . , x (m+1)h+m-1 . Output: x κ 1 R ← 1 G , α ← 0 2 for i = -2 to 1 do 3 R ← R m ; 4 γ R ← -{-h, . . . , h} ; 5 R ← R • x m α-γ+w i ; 6 α ← γ; 7 end 8 R ← R m ; 9 R ← R • x m α+w 0 ; 10 return R
m (h + 1) -1 precomputed values x, . . . , x m(h+1)-1 . Output: x κ 1 R ← 1 G , α ← 0 2 for i = -2 to 1 do 3 R ← R m ; 4 γ R ← -{0, . . . , min(h, m α + wi)} ; 5 R ← R • x m α-γ+w i ; 6 α ← γ; 7 end 8 R ← R m ; 9 R ← R • x m α+w 0 ; 10 return R
We note that Algorithm 9 works in a similar way to the Overlapping Windows method [START_REF] Itoh | Dpa countermeasures by improving the window method[END_REF] for a fixed base m = 2 k-h OW M and m(h + 1) = 2 k3 . The main difference is that our algorithm generates on-the-fly a randomized recoding of the binary representation of the secret exponent κ. This allows our algorithm to avoid side-channel attacks in the recoding phase.

Right-to-left algorithm

Likewise, we can devise a randomized right-to-left m-ary algorithm. Let κ = (w -1 , w -2 , . . . , w 0 ) m , where w -1 = 0, the principle of the right-to-left m-ary exponentiation algorithm, as shown by Yao [START_REF] Yao | On the evaluation of powers[END_REF], makes use of the is relied on the following equality:

x κ = 0≤i≤ -1 di=1 x m i • 0≤i≤ -1 di=2 x 2•m i • • • 0≤i≤ -1 di=m-1 x (m-1)•m i = m-1 j=1 0≤i≤ -1 di=j
x m i j .

The

L j+1 = m j+1 • w j+1 + Lj (12)
Noting that L -1 = κ. Similar, we use the random walk technique and modify L j = L j -m j+1 • γ j , then equation ( 12) can be rewritten as:

L j+1 -m j+2 • γ j+1 = m j+1 • w j+1 + L j -m j+2 • γ j+1 = m • w j+1 + L j + m j+1 • γ j -m j+2 • γ j+1 = (γ j -m • γ j+1 + w j+1 )m j+1 + L j

Conclusion

In this paper we presented variants of the Montgomery powering ladder which have properties that increase the side-channel resistance of the exponentiation algorithm. The first of these operates by randomly changing states such that the difference between the two registers varies, unpredictably, between two states. The second variant of the Montgomery powering ladder that we presented takes a random walk, albeit tightly bounded, among the possible addition chains required to compute an exponentiation. While this variant is not resistant to all side-channel analysis, it will prevent lattice-based attacks when used, for example, in implementations of ECDSA. In other cases, significantly more computation is required to derive any exploitable information and, therefore, an adversary requires a lower error rate to succeed. By applying the random walk method, we also generalized the Montgomery powering ladder and present randomized (both left-to-right and right-to-left) m-ary exponentiation algorithms.

Algorithm 8 :

 8 Randomized Leftto-Right m-ary Exponentiation Input: x ∈ G, an integer κ = (w -1 , w -2 , . . . , w0)m, where 0 ≤ wi < m and w

Algorithm 9 :

 9 Randomized Leftto-Right m-ary Exponentiation without Inversions Input: x ∈ G, an integer κ = (wn-1, wn-2, . . . , w0)m, where wi is m-bit words, small integer h ∈ Z, T a look-up table of

  right-to-left m-ary exponentiation algorithm uses (m -1) accumulators, R[1], . . . , R[m-1]. At each iteration, it applies w successive squarings to compute A = x m j from x m (j-1) , then multiplies the result to some accumulators R[k]. Let R[k] (j) (resp. A (j)) denote the value of the accumulator R[k] (resp. A) before entering step j. We have:R[k] (j+1) = R[k] (j) • A (j) for k = w j , R[k] (j+1) = R[k] (j)for k = w j , and A (j+1) = (A (j) ) m . At the end of the loop each accumulator R[k] contains the product 0≤j≤ -1 wj =kx m j . The different accumulators are finally aggregated as0≤j≤ -1 R[k] k = x κ. By defining L j = j i=0 w i • m i , we have

  This leads to a randomized right-to-left m-ary exponentiation algorithm (Algorithm 10). In this algorithm, we make use of 2(m + 1)h + m -1 accumulators R[j], where -(m + 1)h -m + 1 ≤ j ≤ (m + 1)h + m -1. Each R[j] is initialized to 1 G ,and then updated if α -mγ + w i = j. The different accumulators are finally aggregated as h j=1 R[j] • (R[-j]) -1 j = x κ .

We use the notation hOW M instead of h as in[START_REF] Itoh | Dpa countermeasures by improving the window method[END_REF] to distinguish it from the notation h in our algorithms.

Algorithm 10: Randomized Right-to-Left m-ary Exponentiation Input: x ∈ G, an n-bit integer κ = (w -1 , w -2 , . . . , w0)m, small integer h ∈ Z. Output:


Qiao Hu

Lavinia Mihaela Dinca

Gerhard Hancke

Device Synchronisation: A Practical Limitation on Reader Assisted Jamming Methods for RFID Confidentiality

Keywords: RFID, jamming, eavesdropping, physical-layer security

Radio frequency identification (RFID) is a core component of the Internet-of-Things. In certain cases the communication between the tag and the reader needs to be confidential. Some passive RFID tags have very limited computational power and can therefore not implement standard cryptographic mechanisms. This has led to several proposals where data sent by the RFID tag is 'hidden' by noisy signals generated by the RFID reader. The RFID reader can remove the noise but third-party adversaries cannot, thereby ensuring a confidential backward-channel for tag data without the need for cryptography. Although this is a promising research direction there are also some practical limitations on the effectiveness of such schemes. This paper shows that at least one recent scheme is vulnerable to data recovery despite varying the reader's transmission power if there is a slight difference in the phase of the reader's blocking signal and the tag's data. We experimentally verify our attack and conclude that our eavesdropping and data recovery approach is effective and realistic. Finally we test three possible mitigation methods and show that two of the three approaches can provide protection against our attack while having little impact on the bit error rate of the reader in decoding the tag data.

Introduction

Radio frequency identification (RFID) is one of the main technologies enabling the Internet-of-Things. There are many types of RFID systems, which cover devices from contactless payment smart cards to item-identification tags. The latter type of inexpensive RFID tags have several limitations, including storage, computational capability and power [START_REF] Grover | A Survey of RFID Deployment and Security Issues[END_REF]. Given the popularity of RFID technology in various types of systems, security services have become an important aspect of RFID systems, including within the Internet-of-Things [START_REF] Hancke | Security Challenges for User-Oriented RFID Applications within the Internet of Things[END_REF],. There are generally two major kinds of security concerns [START_REF] Hancke | Security Challenges for User-Oriented RFID Applications within the Internet of Things[END_REF]: privacy and authentication. In this paper we focus on mechanisms that provide data encryption for the purpose of ensuring data confidentiality and privacy. As RFID uses wireless communication, eavesdropping is potentially an effective attack to obtain tag information and has been demonstrated against RFID systems [START_REF] Hancke | Eavesdropping Attacks on High-Frequency RFID Tokens[END_REF][START_REF] Hancke | Practical Eavesdropping and Skimming Attacks on High-Frequency RFID Tokens[END_REF]. In general, to protect against eavesdropping attacks, we usually apply some cryptography to encrypt messages that will be transmitted over the air [START_REF] Juels | RFID security and privacy: A research survey[END_REF]. However, this approach obviously needs some computational ability, which adds costs to minimalist tags. This resulted in research work on how tags responses could be 'encrypted' without the need for dedicated cryptographic mechanisms on the tag.

Recently, Huo et. al. [START_REF] Huo | A Framework to Securing RFID Transmissions by Varying Transmitted Reader's Power[END_REF] has proposed a new physical-layer security method (we will refer to it as Power Varying in the rest of our paper). Passive tags derive their power from the radio carrier transmitted by the RFID reader. Tags also do not transmit their own radio signals, due to power constraints, but rather modulate their response data on the reader's carrier. The reader can observe this 'backscatter' approach to determine the tag's response. Huo's scheme requires the reader to vary the amplitude of the carrier during the tag's response. This means that the response is modulated onto a 'noisy' signal. The reader, as it is sending this signal can cancel it out and determine the tag's response. A third party, who observes the mixed signal, cannot recover the response. The basic concept had been proposed before [START_REF] Archard | Cross-Layer Approach to Preserve Privacy in RFID ISO/IEC 15693 systems[END_REF][START_REF] Hancke | Noisy Carrier Modulation for HF RFID[END_REF][START_REF] Savry | RFID Noisy Reader How to Prevent from Eavesdropping on the Communication?[END_REF] but this scheme used a simpler, non-random step function as the intentionally introduced noise.

In this paper, we show that under certain realistic conditions we can reliably circumvent the basic Power Varying scheme. If the reader noise signal and the tag's response are not exactly in phase, i.e. perfectly synchronized, we can successfully start to recover tag response data from the mixed signal. Although RFID tags are generally adapt at loosely synchronizing responses with each other and to the timings expected by the reader there are in practice still variations in the response times. In publishing our research we wish to illustrate that, even though this general approach shows some promise, designs should carefully take into account the actual channel environments and device characteristics of RFID systems. Not doing so could have unintended consequences that could compromise the security of the entire scheme.

The rest of our paper is organized as follows: Section II provides a brief overview of related work and introduces the details of the Power Varying method by Hou et. al. We then describe how we can break this method with only one eavesdropper in section III, and demonstrate our attack through realistic simulation. In section IV, we show how the scheme could be improved using ideas from existing literature and show the effectiveness of mitigation methods on our earlier attack.

Background and Related Work

RFID System

In the Power Varying scheme the authors mention using a 915 MHz carrier as the signal from the RFID reader. We therefore assume that the scheme is primarily intended to work with RFID systems adhering to ISO/IEC 18000-6 (although the idea could feasibly also be applied to 13.56 MHz systems like ISO/IEC 14443/15693). As such, we will provide a brief overview of the communication channel specified in this standard in terms of the encoding and modulation characteristics of the response transmitted by the tag. In ISO/IEC 18000-6, the tag transmits data to the reader through backscatter modulation, i.e. modifying and 'reflecting' the incident reader signals. Data that is transmitted by the tag is coded with the FM0 technique, as shown in Fig. 1.a, For logic bit 1, we can just see an instant electrical level change at the start of the symbol period. For logic bit 0, we can see not only an instant electrical level change at the start of the symbol period but also at the middle of the symbol period. The modulation method adopted is 10% Amplitude Shift Keying (ASK). If the logic bit is 1, the amplitude is α, otherwise it will be β. A modulation index of 10% means that (α -β)/(α + β) is equal to 10%.

The Power Varying Method

Power Varying aims to prevent eavesdropping by changing the power/amplitude of the transmitted reader's signal. Huo et. al. [START_REF] Huo | A Framework to Securing RFID Transmissions by Varying Transmitted Reader's Power[END_REF] claims that the changing amplitude can effectively hide the backscattered signal transmitted by tags from eavesdroppers. Given that the reader is responsible for the power variation it can effectively cancel out this variation and reliably recover the noise. The basic format of the power varying signal is shown in Fig. 1.b. First, it will choose a minimum amplitude that satisfies the minimum power needed to activate and power the passive tags. Next, the amplitude of the signal will increase step-bystep until it reaches the maximum chosen amplitude. It will then return to the minimum amplitude and the cycle will start again.

The authors describes the variations of this step signal. In the first variation the period of the signal is equal to the bit period of the tag's response. The second variation uses a varying signal that has a period that is 10% of the bit period. The basic scheme defines that the changing step amplitude is equal to the difference between the amplitude of tag signals containing logic bit 0 or 1. In other words, when a symbol period of tag containing logic bit 0 arrives, the amplitude of the signal observed by eavesdropper will be the same as the amplitude of the signal during the previous step if the symbol period of the tag containing logic bit 1 arrived. We give an example of the first variation of this scheme in Fig. 2. From this figure, we can observe that amplitude differences between two continuous signals received by the attacker are different depending on the logic bit carried by corresponding tag signals. For example, the amplitude difference between two periods with logic bits sequence in 10 is near zero. And the amplitude difference between two periods with logic bits sequence in 01 is almost double of that with sequence in 11. This means that if we know which logic bit is carried during a step period, we can deduce the previous or next logic bit by the amplitude difference between these periods. How to know the logic bit? If we observe near zero amplitude difference, which happens quite often, we know that these two periods represent logic bits 00.

As this constant amplitude increasing method is vulnerable, its authors suggest to use random amplitude. Fig. 3.a illustrates this improved method in the first variation mentioned above. We can see that the amplitude difference between two continuous step periods has no relationship with the logic bit sequence. Even the logic bit sequence is 10, there is also a large amplitude difference. In other words, it is unclear whether the 2th bit is a large step with a logic 0 or a smaller step with a logic 1.This result demonstrates that the randomly increasing amplitude method has fixed the previous vulnerability.

Related Work

There are several works on physical-layer security and cryptographic-less encryption based on the general concept put forward by Wyner in the 1970s [START_REF] Wyner | The Wire-Tap Channel[END_REF]. The foundation of all these schemes are that the legitimate receiver is less effected by, or can cancel out, noise. This allows for reliable reception of data while an eavesdropper cannot recover the data. At first schemes relied on environmental noise, but to ensure that there is sufficient noise to hide the data, schemes started introducing intentional noise. For example, the introduction of friendly jamming, where the system could either use multiple antennas in one node or multiple trusted nodes, could co-operate to transmit 'friendly' noise that is known to the receiver [START_REF] Negi | Secret Communication Using Artificial Noise[END_REF]. Subsequently many researchers tried to apply this idea to RFID technology, e.g [START_REF] Archard | Cross-Layer Approach to Preserve Privacy in RFID ISO/IEC 15693 systems[END_REF][START_REF] Castelluccia | Noisy Tags: Pretty Good Key Exchange Protocol for RFID Tags[END_REF][START_REF] Haselsteiner | Security in Near Field Communication (NFC)[END_REF], where either the reader or other tags would transmit noise to cover data signals transmitted by the tag of interest. There has also work been done on how to generate appropriate noise for jamming high-frequency RFID devices [START_REF] Savry | RFID Noisy Reader How to Prevent from Eavesdropping on the Communication?[END_REF]. This method has also been applied to other technologies, such as short-range audio communication channels in mobile phones. In such cases, one device would transmit data and the receiving device would transmit noise [START_REF] Nandakumar | Dhwani: Secure Peer-to-Peer Acoustic NFC[END_REF][START_REF] Zhang | PriWhisper: Enabling Keyless Secure Acoustic Communication for Smartphones[END_REF]. There has not much work been done on attacking jamming schemes in practical environments. Hancke [START_REF] Hancke | Noisy Carrier Modulation for HF RFID[END_REF] showed that the natural variation in modulation index, which derives from the inherent impedance of the tags between the device transmitting the response data and the device transmitting the blocking noise, could reveal the hidden response. In this paper we investigate the effect of variations on the response time of the tags, i.e. difference in phase of the blocking noise and the response. Fig. 2: Signals received by an attacker under the constant amplitude increasing method

3 Overview of Our Attack

Adversarial Model

In this subsection we introduce the adversarial model used throughout this work. In the rest of this paper we apply the increasing amplitude Power Varying scheme. We calculate the number of steps m by the following formula proposed in [START_REF] Huo | A Framework to Securing RFID Transmissions by Varying Transmitted Reader's Power[END_REF].

m = x high -x low αx (1)
x high and x low mean the maximum and minimum amplitude of the reader signal respectively. x is given by:

x = x high -x low 2 (2)
We set α as 0.1, then m equals 21. Given that there is no standard prescribed in the Power Varying scheme we take two approaches. We attack the scheme assuming that no specific standard is used, i.e. non-return to zero encoding with basic amplitude modulation, and then analyse the scheme if it was implemented as per the ISO/IEC 18000-6 standard. In our adversarial model we have one RFID reader communicating with one passive RFID tag. The adversary is a passive attacker and only obtains the combined signal resulting from the tag response and the varying signal. We do not specify the position of the adversary relative to the tag and reader but assume that the attacker cannot derive any additional advantage from directional monitoring techniques to isolated reader and tag transmissions. Our attacker has knowledge of the standard used, i.e. the communication parameters, and of the Power Varying scheme. This means that the attacker knows that a step function is used to vary the power and he knows the period of the steps, but not necessarily the amplitude of the steps.

Analysis of Power Varying

1) General Attack

We first analyze the scheme taking into consideration no specific standard. We accept that the method is secure when the mixed signal received by the attacker is as shown in Fig. 3. We can see from Fig. 3 that the data is effectively hidden if the symbol period and the step period is synchronized, with the attacker unable to distinguish the response data as we talked about in Section 2. However, in reality it is unlikely that the reader would be able to perfectly synchronise his step function to the response of the tag. As shown is [START_REF] Haselsteiner | Security in Near Field Communication (NFC)[END_REF], even similar tags, i.e. same technology and manufacturer, exhibit slighlty different modulation and timing characteristics. We refer to this desynchronisation as the phase offset, or offset for short. The result of an offset on the combined signal is illustrated in Fig. 4, where the step period is not synchronized with the symbol period. In Fig. 3, there is no amplitude change during each symbol period. However, in Fig. 4, due to the desynchronization, the attacker could infer the effect of the step. For example, if two logic 1's are transmitted we expect the second to have a higher amplitude due to the step, but ideally there should be an uncertainty whether it might also be a large step with a logic 0. If we notice that halfway through the first one the signal increases that is evidently the size of the step. If there is then an additional increase if the next bit period starts we also know that the bit is a one. Therefore, depending on these amplitude discontinuities caused by the offset we can distinguish the logic bits of the response.

2) Results of the General Attack

We simulate the general attack in Matlab. In this experiment, we consider no specific standard and the tag signal is as shown in Fig. 4. And we also assume that there is no additional environmental noise. Between the minimum amplitude and the maximum amplitude there are 10 step periods (we use this setting at the rest of our experiments). This means that the power signal is a periodic signal with a 10 step cycle (with step period equal to either the bit period or 10% of the bit period). The only factor that may effect the result of our attack is the degree of desynchronization (or phase offset) between the two signals. For step equal to bit period, we set the offset from zero to a step period with interval equals to one fifth of a step period. For the step period 10% of the bit period, we set the offset from zero to two and a half step periods with interval equals to half of a step period. We use bit error rate(BER) to evaluate our experimental results. Our results show that apart from the case where the offset is 0 the resultant BER was always 0 for any amount of offset.

3) Specific Attack under ISO/IEC 18000-6

We then attempted the same attack as in the previous section, but we use the FM0 coding scheme as per ISO 18000-6. This means there is a slight variation in the signal when a logic 0 is encoded in that there is a signal change in the middle of the period, which results in a slightly different combined signal as shown in Fig. 5. Although this case appears at first similar there is now some uncertainty as to whether a discontinuity in the middle of the bit period is caused by the step of the logic 0 transition in some cases. If there is an instant level change at the beginning of each symbol period or at the middle of the period then the symbol represents logic 0. If the step period and the symbol period are not well synchronized, during one step period, we may also observe a similar level change.

We therefore need two steps to recover logic bits. First, we need to find the start of the tag response signal. If there is no tag signal, then there is no amplitude difference in one step period. Because we know the time of all step periods, we can distinguish whether the amplitude difference is caused by the tag signal or by the power signal. So we assume that the first amplitude difference means the start of the tag signal. Then we can calculate the middle area of each symbol period to search for the level change to judge the logic bit of this symbol period, as each symbol period has the same length. These two steps seem the simplest to find amplitude differences caused by electrical level changes. We also simulate the specific attack in Matlab. In this experiment, we have the same configuration as with the previous experiment. We also do the experiment under one or one tenth of a symbol period situation. We set the offset as we do in the general attack experiment. Interestingly the results differ from the general case as shown in Figure 6. Let's first see the result of a situation with a period ratio equals to 1, which means a step period is equals to a symbol period shown in Fig 5 .a. We can observe three high BER periods. The first and the last period happen when the offset nears zero or one step period, which means the starting point of a symbol period is overlapping with the beginning of a step period. The second period happens with a 1/2 step period offset, which represents the overlap between the middle point of a symbol period and the beginning of a step period. The result of a period ratio equal to 10 has a similar but a little different reason as the previous result. The difference is that the distance between the starting point and the middle point of a symbol period can be divided by a step period, which is illustrated in Fig 5 .b. If the starting point of a symbol period is overlapping with the beginning of a step period, we may get a high BER at the attacker. We can observe that except for the area of overlapping, the BER is 0, which means the attack is a success.

Logic

5) Eavesdropping in a Noisy Environment

Up to now the attack implementation did not consider any additional noise. However, this is not a realistic assumption in real operating environments. Therefore we also consider our attack against Power Varying in the presence of background noise. Such noise should in theory hinder the attacker and the valid receiver. We only analyze the impact of noise for the attack scenario against ISO 18000-6. As noise will change the amplitude of signals, we should calculate the average amplitude to deduce the impact of noise. To evaluate the impact of additional background noise, we add Additive White Gaussian Noise (AWGN) to our simulation. We set the SNR (Signal to Noise Ratio) of the received signal in the attacker as ∞ (no noise), 20dB and 30dB. These are realistic noise figure in radio environments, e.g. WiFi under normal conditions operates at around 40 dB. We again run the experiment with the two kinds of step period length. The final result, as shown in Fig. 7, is as expected. It shows the BER of the attacker increasing but large parts of the message could still be recovered.

Mitigation Methods

In this section we consider ways to mitigate the weaknesses of the basic scheme. As we only analyze the randomly increasing amplitude method, we try to analyze the random amplitude method that allows the amplitude increasing or decreasing. We will refer to this as the random amplitude method. Another approach is to use the reader signal and a phase shifted version of the reader signal as the reader's signal. This is similar to the approach in [START_REF] Archard | Cross-Layer Approach to Preserve Privacy in RFID ISO/IEC 15693 systems[END_REF] where noise and

This formula tells us that the new reader signal is a cyclic signal with a period of 2π during one step period. We refer to this as the artificial noise method. Finally, we propose that we can improve the random amplitude method by also adding a random variation of the step length. In other words, choose the step period length randomly. We call it the random step period and amplitude method. We implement these three methods for the ISO/IEC 18000-6 standard and repeat the attacks tests in the previous sections. In experiments on the first two methods, we set the period ratio as 1. We also evaluated these methods if the SNR of the received signal at the attacker are ∞ (no noise), 30db and 20db.

Results of these tests are shown in Fig 8 . Thise figure show that when the energy of noise is very low compared to the mixed signal, the first two methods increase the BER by a small amount but the third method utilizing both the random step size and random step amplitude works much more effectively. We believe this is because our attack depends mostly on the amplitude difference caused by the tag signal and the time of amplitude changes caused by the power signal can be calculated by us. As the first method only change the amplitude of the power signal and the second method only change the original power signal to another power signal with the same cycle time, these have minimal effect on our attack. The last method is also successful at causing the attack to calculate the incorrect start point which would lead to error decoding most of the message.

Conclusion

In this article, we analyze the vulnerability of Power Varying method proposed by Hou et. al. [START_REF] Huo | A Framework to Securing RFID Transmissions by Varying Transmitted Reader's Power[END_REF]. This method can be broken when the step period of the signal from a reader and the symbol period of the backscatter signal from a tag are not well synchronized. This desynchronization causes amplitude differences in the step period which can be used to distinguish tag signals. We describe our attack under general situation and for communication adhering to ISO/IEC 18000-6. Then we analyze factors including noise and phase offset that can affect our attack. Results show that our attack works well in less noisy environment and that even a small phase offset can result in effective recovery of the tag's response. Lastly, we test three mitigation methods: a random step amplitude method, artificial noise addition method and a combined random step period and amplitude method. Results show that the latter approach, which is propose by us, is the best mitigation method. The combined random step period and amplitude method can protect communication from recovery while have little impact on the bit decoding error rate of the tag signal at the reader.

Fig. 1 :

 1 Fig. 1: Basic concepts of RFID tag response and Power Varying

  received by the attacker (b) Step with period equal to 10% of bit period

Fig. 3 :Fig. 4 :Fig. 5 :

 345 Fig. 3: Signals received by an attacker with perfect synchronization

Fig. 6 :

 6 Fig. 6: Results of the attack on ISO 18000-6

Fig. 7 :Fig. 8 :

 78 Fig. 7: Impact of noise on the attack


David Jaeger

Amir Azodi

Feng Cheng

Christoph Meinel

Normalizing Security Events with a Hierarchical Knowledge Base

Keywords: network security, event logs, normalization, knowledge base

An important technique for attack detection in complex company networks is the analysis of log data from various network components. As networks are growing, the number of produced log events increases dramatically, sometimes even to multiple billion events per day. The analysis of such big data highly relies on a full normalization of the log data in realtime. Until now, the important issue of full normalization of a large number of log events is only insufficiently handled by many software solutions and not well covered in existing research work. In this paper, we propose and evaluate multiple approaches for handling the normalization of a large number of typical logs better and more efficient. The main idea is to organize the normalization in multiple levels by using a hierarchical knowledge base (KB) of normalization rules. In the end, we achieve a performance gain of about 1000x with our presented approaches, in comparison to a naive approach typically used in existing normalization solutions. Considering this improvement, big log data can now be handled much faster and can be used to find and mitigate attacks in realtime.

Introduction

During the last years, the number and complexity of cyber-attacks has dramatically increased [1,2]. An important instrument for the monitoring and mitigation of attacks is the logging of suspicious activities in networks and on hosts. This logging is usually performed by operating systems, applications or security software [START_REF] Kent | Guide to Computer Security Log Management[END_REF] and creates huge amounts of log events for even relatively small networks. Handling these amounts of events manually or automatically by software with typical normalization approaches is almost impossible. Besides that, the incoming information cannot be handled in realtime, which is extremely important to detect ongoing attacks.

A difficult challenge that has to be mastered in software are the variety of formats for event logs that do not follow a common standard. Additionally, the formats usually represent a major part of the activity in an unstructured textual format, which is easy to read for humans, but not for machines [START_REF] Kent | Guide to Computer Security Log Management[END_REF].

At the moment, most solutions that gather and interpret event logs, so called Security Information and Event Management (SIEM) systems, only focus on structured event information and do not sufficiently interpret the unstructured information. Only a few SIEMs and log interpreters, such as HP's ArcSight1 or Flowerfire's SawMill2 , actually interpret the contents of unstructured data but lack in performance when it comes to huge amounts of events or when data of different formats is mixed.

Although the use of structured log-formats is encouraged, they can also bring up new challenges for normalization, i.e. the structure often introduces a hierarchy of sub-formats. At the moment, there is only limited research on how such hierarchically structured formats can be efficiently normalized.

This paper provides a solution for effective normalization of events in general and for hierarchical log-formats in particular and is structured as follows. Section 2 gives an overview of related work to event normalization. Section 3 shows how a single event can be normalized. The following Section 4 then introduces the concept of a knowledge base for event normalization and shows two possible designs for it. Then, in Section 5, the hierarchical design is further detailed and features are described, that can improve normalization performance. In order to show the applicability of the mentioned concept, Section 6 shows performance values for two concrete scenarios. In the end, Section 7 gives a conclusion and an outlook to further research.

Related Work

Log-Formats

Several efforts have been made to normalize log-formats and simplify the interpretation by machines. Examples for such efforts are the general purpose formats Syslog [START_REF] Gerhards | The Syslog Protocol[END_REF], Common Event Expression (CEE) [START_REF] Chuvakin | Common Event Expression[END_REF] or the Common Event Format (CEF) [START_REF] Hewlett-Packard | Implementing ArcSight CEF. 20[END_REF]. Another set of formats have been introduced for specific domain applications, such as Cyber Observable eXpression (CybOX) [START_REF] Barnum | The CybOX Language Specification[END_REF] for network and host-based detection systems.

However, all of the formats allow event normalization on very different levels of detail. Whereas the popular Syslog-format only provides rudimentary semistructured normalization, the rarely used CybOX provides normalization for almost every imaginable information. Due to this situation, log information is mostly available in semi-structured formats and requires further processing to obtain relevant information.

In this paper, we focus on the Object Log Format (OLF) [START_REF] Sapegin | Hierarchical Object Log Format for Normalisation of Security Events[END_REF], which combines extensibility and object orientation of CEE and the variety of attributes of CEF.

Event Normalization and Analysis

The normalization and analysis of log events has already been implemented in a variety of methods and has been integrated into many existing software solutions.

Normalization Methods There are mainly four normalization methods that can be observed on the market and the research community.

Rule Matching (e.g., Regular Expressions) The normalization of each event log type is described in a rule that specifies how important information can be extracted from a concrete event. A popular approach in this category are regular expressions, especially Named-Group Regular Expressions (NGRE) [START_REF] Jeffrey | Mastering Regular Expressions[END_REF]. This method associates information in the event to concrete event fields, which can be very useful for normalization. However, choosing the right regular expression for a random event type is processing intensive. Tokenization A concrete event log is split up into tokens. These tokens could be the words of the human readable part of the log event or even phrases or certain notations in the log. The most common approach for tokenization is by word, which allows to group event logs containing the same words. However, this method heavily relies on static words in logs. A concrete implementation for tokenization is Apache Lucene3 . Natural Language Processing (NLP) A human readable log line is decomposed by its language structure into subject, object, verbs and more. Once the information is extracted, it can be used to understand the meaning behind the phrase, as a human reader would see it. However, the method relies on the human readability of the log. Examples for NLP implementations are Stanford's CoreNLP library or SAP HANA's text analysis capabilities [START_REF] Sparvieri | SAP HANA Text Analysis[END_REF].

A concrete usage of this technique for log analysis has been proposed by Kobayashi et al. [START_REF] Kobayashi | Towards an NLPbased log template generation algorithm for system log analysis[END_REF]. Custom Normalization The most effective but also most complex method is to use custom code for the normalization of each log format. As an example, one format is read with a CSV parser, while another one is parsed with a special Syslog parser and yet another one is handled with a combination of multiple regular expressions being applied in order. This type of normalization can be partially observed in the log analysis tools Logstash4 and Sawmill.

Normalization Software There are a variety of software solutions that perform normalization based on event logs. Log analysis tools like the OSSEC IDS 5 monitors important event log files and extracts potential threats from these using regular expressions. On the other hand, there are complex SIEM systems like HP's ArcSight and RSA Security Analytics6 . Both solutions have limited capabilities when it comes to normalization and hence also for complex attack detection. Firstly, event streams have to be associated with the right log-format to be used for normalization. Secondly, log events are mostly normalized by their structured parts and only a few log events are normalized completely.

Basic Normalization of Log Events

Different log sources produce events in different formats and encodings. Whereas almost all log sources produce logs in a textual way, the formats are different.

The information in event log-formats can usually be categorized into dynamic, static and semantic parts. Listing 1.1 applies the concept of different information categories on a Syslog event.

The static information defines the structure of the log, including white spacing and glue words, such as for or from, for the dynamic parts. Because of the structure-defining property of the static information, it perfectly fits the purpose of identifying the type of log that is at hand.

The dynamic information bears the explicit information for a concrete instance of an event type. This information can change for each log event, but still has a common format, such as a time or a number. For example the port number and IP address in the listing are dynamic, but always have a certain format.

Besides the explicit information, semantic information provides a classification of the event through tagging. In the example, the marked text Failed password indicates that the event refers to a failure for a login activity on an account. So, the semantic tags for the given event could be failure, login and account.

Azodi et al. [START_REF] Azodi | Pushing the Limits in Event Normalisation to Improve Attack Detection in IDS/SIEM Systems[END_REF][START_REF] Azodi | A New Approach to Building a Multi-Tier Direct Access Knowledge Base For IDS/SIEM Systems[END_REF] describe the process of extraction into the OLF-format in detail.

Knowledge Base Approaches

An event can theoretically be normalized with the help of a knowledge base that consists of entries of regular expressions and corresponding static fields and tags. However, as soon as multiple log-formats have to be supported for normalization, choosing the right entry becomes an issue. Assuming a KB of n normalization rules would mean that on average n 2 entries have to be checked, i.e. applying the entry's NGRE on the event, before the right matching entry is found.

To overcome this processing overhead, NGREs have to be applied more efficiently to a given event. The following subsections show different approaches for applying regular expressions more efficiently by changing the organization of the KB.

For a better demonstration of the concepts, the two example log events in Figure 1

Flat Knowledge Base

The simplest approach to organize a KB is to have one normalization rule per possible event type. We call it flat KB, because there is no multi-level organization of the rules. Rather, each rule describes an event type in its entirety, including an NGRE matching the entire event text and all static fields. Figure 2 demonstrates the processing of the two log events from Figure 1.

There are two raw events to be normalized. In a flat KB, there is a separate normalization rule for each event. Rule #1 handles a Snort event of type 648, which is embedded into a Syslog event. Rule #2 handles a Snort-event of type 1807. Looking closer at the two rules, it can be seen that the rule parts for Syslog and Snort are identical. The only difference in the rules is the inner part being specific to the concrete Snort rule. It is obvious that flat normalization rules have many redundancies that can be eliminated with a more sophisticated KB approach.

Hierarchical Knowledge Base

The structure of typical logs is that more specific log parts are wrapped in parent formats, such as Syslog. In the case of Snort log events, there is an intermediary Snort wrapping format, as already indicated in the processing of the flat KB in Figure 2. An approach to overcome the redundancies in normalization rules of a flat KB is to organize normalization rules in multiple levels, i.e. hierarchically. Our hierarchical KB has one rule per identified parent format and one rule per event type. All these rules are loosely coupled by specifying possible parents for each rule. A concrete example for the events from Figure 1 is illustrated in Figure 3.

In the example, there could be four normalization rules. There are the two parent formats, for Syslog and Snort, being specified in rule #1 and #2. #2 has a link to #1 as possible parent. Rule #3 and #4 specify the concrete parts of the two given event types and both link to rule #2 as parent.

In order to match one of the given log events, we look for rules that are applicable in the current matching context. We call these rules candidate rules. This means, at the beginning we first check all rules that can stand alone, which in this case is only Syslog, because it has no parents. When the Syslog part is matched, its message part is used to match the next-level rule, which has the Syslog-rule as its parent. In our concrete example, this would be the Snort-rule. Once Snort is matched, the rule's message part is extracted and then checked against the rules that have the Snort-rule as parent. This could be rule #3 and #4. According to the concrete content, the right rule would be matched.

Comparison of approaches

Structuring Taking the effort of defining rules, the hierarchical approach is much more organized, if many event types of similar structure have to be described. For example, taking the thousands of existing Snort rules, the hierarchical approach only defines Syslog and the basic Snort event once and then specifies Snort's event type specific parts in separate simple normalization rules. In the flat approach, all parts, especially Syslog and Snort, have to be repeated for every Snort-rule.

Another benefit with the hierarchical approach is that static fields and tags can be defined at parent-level rules. As an example, to tag an event as a networkrelated event (expressed with tag.domain = net), a corresponding tag only has to be attached to the Snort-rule, because Snort only deals with network data.

Performance When it comes to performance, the structuring can help to improve the performance of normalization significantly, too. Let us assume there are logs and normalization rules for two different applications, namely Snort and sshd being wrapped in Syslog. For the flat approach, as seen in Figure 4, in the worst case a Snort event has to be checked against all sshd-related normalization rules until the Snort normalization rule is found as a match.

For the hierarchical approach, as seen in Figure 5, in the worst case only a single Syslog-and sshd-rule is checked until the Snort normalization rules are found as a match. So taking the fact that log events of many applications have to be supported by the KB, the hierarchical approach can have major performance benefits.

Improving Knowledge Base Matching Performance

While the main idea, to organize the KB hierarchically, can already bring major performance benefits, further improvements can speed up the normalization even further. Following subsections give an overview of the different approaches we have evaluated. Additionally, we point out which technologies and libraries have been used for our implementation in the Java programming language. The evaluation results of the approaches are presented in Section 6.

Rule Indexing

When working with hierarchical rules, it is important to choose the right candidate rules as fast as possible. These candidate rules are selected by a number of criteria that effectively filter the number of rules to be applied on a given log fragment. We came up with following criteria:

-Standalone: This rule matches an event that can stand on its own. These rules do not require a parent. -Level: Logs are constructed in multiple levels. There are global wrapper formats, such as Syslog, application wrappers, such as Snort, and event parts that are specific to the event type. Based on the current level, rules of upper levels do not have to be checked again. -Parent: Some event parts can only appear as a child of another format.

As an example, a specific Snort rule can only appear in the general Snort wrapper. This property can rule out most of the available rules.

Based on these criteria, we tried three different strategies to search applicable rules more efficiently.

Iteration

In the easiest case, the program would iterate through all available rules and check the criteria for each rule. However, iteration over large amounts of rules creates major performance impacts.

CQEngine

A straight-forward approach is to index all available rules by the presented criteria. For our evaluation, we used a library called CQEngine7 , a NoSQL indexing and query engine.

Lucene

Another approach is to create a similarity measure between a given event and the events a rule is able to match. A detailed description of this approach for a flat knowledge base can be found in a paper [START_REF] Azodi | A New Approach to Building a Multi-Tier Direct Access Knowledge Base For IDS/SIEM Systems[END_REF] by Azodi et. al.

Rule Selectors

Log-formats with many different event types as a child give an indication of the child's type. For example, Syslog has an application name that indicates what kind of application logs are in the message part. Such indicators can be used to directly select the right normalization rules without searching through all possible candidate rules for the parent. An example of this rule selection can be seen in Figure 6.

Result Caching

The searching for candidate rules can be seen as one of the most processing intensive tasks in the normalization process. We propose to cache the search results for a given set of criteria. Caching can then make candidate rules directly accessible and improve normalization of logs without format indicators.

Priority Lists

A feature that can be added in conjunction with result caching is the ordering of all candidate rules by their frequency they have been used for the normalization of previous events. Creating a priority list with every log event is unfeasible, because the sorting would result in major performance drops. Rather, ordering by frequency should be performed in a time interval that takes the required processing overhead and the actuality of the frequencies into account.

Evaluation

We have implemented all of the above mentioned knowledge bases, indexing strategies and other proposed improvements into our Real-time Event Analysis and Monitoring System (REAMS) [START_REF]Real-time Event Analysis and Monitoring System (REAMS)[END_REF] and ran performance tests for various combinations of these on two data sets. Each combination was run 10 times per data set, so that a mean runtime could be calculated. As our implementation is highly parallelized and can run multiple normalization threads simultaneously, we decided to run the performance tests on eight parallel normalization threads on our server8 .

Experiment 1: Normalizing Hierarchical Logs

In the first experiment, we have normalized all Snort event logs, i.e., 69039 log events, from Honeynet Challenge #34 [START_REF]Honeynet Challenges: Scan of the Month 34[END_REF]. We have generated normalization rules for all Snort rules from the rule snapshot 9 for registered users and the emerging threats open rules 10 . These rules, altogether 55547, cover all Snort events that were present in the challenge's logs. The performance results of normalization are visualized in the box and whisker diagram in Figure 7.

We see that the flat KB performs at least a magnitude worse than the hierarchical KB. This is because the handling and checking of more and longer rules as used with the flat KB is more time consuming than with a hierarchical one. Both factors have a major impact on hierarchically structured formats as used by Snort.

We can also deduce that direct indexing with CQ is faster for the hierarchical KB than normal iteration. The better indexing with CQ is not relevant for the flat KB, because there is almost no data to index. The Lucene indexing generally performs better than iteration and CQ, but because of its mechanisms the rules cannot be further cached or prioritized. Unfortunately, Lucene cannot outperform the benefits of caching and prioritization. Within the hierarchical performance results, prioritization and rule selectors achieve the biggest performance benefits. Both concepts can reduce the number of rules to be checked per log event dramatically. In comparison to the plain KB performance, both concepts also bring the most stable runtime values. The other concepts all heavily rely on the ordering of the rules, because they match rules in the order they are stored in memory. Prioritization and rule selectors mostly choose the right rule directly. It should be mentioned that we intentionally did not fix the rule order, because in reality the correct order is not known and is highly dependent on the concrete distribution and order of log events.

The caching of results can bring benefits, if a large number of varying data lookups would have to be performed. As an example, it is not so relevant for caching of big data sets (e.g. H:-↔ H:C), but for caching of smaller data sets that apply to only a few log events (e.g.: H:SL ↔ H:C+SL).

Experiment 2: Normalizing Mixed Logs

In the second experiment, we applied our algorithm to mixed logs consisting of Snort and Apache events, i.e., 76659 log events, from Honeynet Challenge #34 [START_REF]Honeynet Challenges: Scan of the Month 34[END_REF]. In comparison to experiment 1, the performance test results are almost unchanged, because there are only roughly 11% more events now, which are even easier to normalize.

Summary

Altogether, a combination of a hierarchical KB with CQ indexing, caching, prioritization and rule selectors seems to have the best normalization performance.

In our experiments, we could reach a normalization speed of 37,000 events/s for a highly hierarchical log-format on eight threads.

Conclusion and Future Work

In this paper, we have shown how the speed of event log normalization can be drastically improved by using normalization algorithms that consider the typical hierarchical structure of log events. We have performed normalization with Lucene on a flat KB before, which did not perform well enough for big data. However, by using hierarchical normalization rules in combination with CQ indexing, caching and prioritization of rules we could speed up normalization by approximately 3 orders of magnitude. Altogether, we were able to normalize around 37,000 events/s, which should already be enough for large network environments. This fast speed can even be achieved, if logs with different parent formats are intermixed, like in real world log environments.

A starting point for further research could be the improvement of the normalization speed in a way that even event logs of companies with multiple billion events per day can be handled. One direction could be the parallelization of the processing on multiple machines.

Additionally, normalized logs can be used for further analysis. For example, inventory information can be extracted from logs to create an overview of machines, software and users in a network. Furthermore, the log information can be used to detect or prevent intrusions in a network environment.

Fig. 2 .Fig. 3 .

 23 Fig. 2. Normalization with a flat KB

Fig. 4 .Fig. 5 .

 45 Fig. 4. Matching with a flat KB

Fig. 6 .

 6 Fig. 6. Rule selector approach on log event from Listing 1.2

Fig. 7 .

 7 Fig. 7. Evaluation results for normalizing 69039 Snort log events, left (F) -flat knowledge base, right (H) -hierarchical knowledge base (C -Cache, P -Prioritization, SL -Rule Selector)

  are chosen. Both are Syslog events typically created by Snort and have a similar structure, but they are of different event types.

	Listing 1.2. Event #1 for a Snort event of type 648, i.e. an attempt to execute shellcode	Listing 1.3. Event #2 for a Snort event of type 1807, i.e. an attempt to inject commands over HTTP
	Mar 1 16:02:40 bastion snort: [1:648:7] SHELLCODE x86 NOOP [Classification: Executable code was detected] [ Priority: 1]: {TCP} 4.152.207.238:3521 -> 11.11.79.83:80	Mar 1 16:03:01 bastion snort: [1:1807:10] WEB-MISC Chunked-Encoding transfer attempt [Classification: Web Application Attack] [Priority: 1]: { TCP} 4.152.207.238:3718 -> 11.11.79.84:80

Fig. 1. Two log events produced by Snort with a similar structure

ArcSight Enterprise Security Managementhttp://www8.hp.com/us/en/ software-solutions/arcsight-esm-enterprise-security-management/

SawMillhttp://sawmill.co.uk

Apache Lucene -http://lucene.apache.org/

Elasticsearch Logstashhttps://www.elastic.co/products/logstash

OSSEChttp://www.ossec.net

RSA Security Analyticshttp://www.emc.com/security/security-analytics/

CQEnginehttps://code.google.com/p/cqengine/

Virtual Machine (Debian 7.8, 32GB RAM(dedicated), 8 cores(dedicated)) on VMware ESXi host with 256GB RAM and 8x Intel Xeon X7560 CPUs @ 2.27GHz

Snort Ruleset (Registered User)https://www.snort.org/downloads

ETOpen Rulesethttps://portal.emergingthreats.net/etpro/open

Acknowledgment

We would like to thank HPI FutureSoC lab for providing us with the latest and powerful computing resources, which make the testing and experiments specified in the paper possible.