Security through Elliptic Curves for Wireless Network in Mobile Devices

I. INTRODUCTION

Elliptic curve cryptosystems (ECCs) are suitable for implementation on devices with limited memory and computational capability such as smart cards and also with limited power such as wireless handheld devices. This is due to the fact that elliptic curves over large finite fields provide the same security level as other cryptosystems such as RSA for much smaller key sizes.

Considering power analysis attacks, there are two main types that were presented by Kocher et al. These are simple and differential power analysis attacks (referred to as SPA and DPA respectively).

Both of them are based on monitoring the power consumption of a cryptographic token while executing an algorithm that manipulates the secret key.

The traces of the measured power are then analyzed to Hence, DPA attacks are, in general, more powerful than the SPA attack. Randomization of the data processed at some instant is essential in resisting this type of attack. Electromagnetic emanations present another powerful side channel since the information is leaked from the device via more than one channel and is a function of space as well as of time. In [2], Agrawal et al. presented both simple and differential electromagnetic analysis attacks on smart cards and on a Palm pilot. In these attacks they conclude that software countermeasures rely on signal information reduction, which is achieved by "randomization and/or frequent key refreshing within the computation", which agrees with the concept of resisting DPA attacks.

The point addition operation consists of finite field operations carried in the underlying field K. We denote the field inversion by I, the multiplication by M, the squaring by S. The point addition is denoted by A. When the two operands of the addition are the same point, the operation is referred to as point doubling and is denoted by D.

II. WINDOW METHODS

This method is sometimes referred to as the m-ary method. There are different versions of window methods. What is common among them is that, if the window width is w, some multiples of the point P up to are precomputed and stored and k is processed w bits at a time. k is recoded to the radix . k can be recoded in a way so that the average density of the nonzero digits in the recoding is , where depends on the algorithm. Let the number of precomputed points be t, in the Precomputation stage, each point requires either a doubling or an addition to be computed also depending on the algorithm.

This ECSM method is suitable for unknown or fixed-point P. The cost is Storage: t points, where depending on the algorithm. Precomputation: t point operations (A or D). Expected running time:

where depending on the algorithm. Note that the number of doublings is between n - w and n - 1.

2.1. Simultaneous multiple point multiplication

This method is used to compute kP +lS where P may be a known point. This algorithm was referred to as Shamir's trick in [10]. If k and l are n-bit integers, then their binary representations are written in a matrix called the exponent array. Given width w, the values iP +jS are calculated for . Now the algorithm performs iterations. In every iteration, the accumulator point is doubled w times and the current window over the exponent array determines the precomputed point that is to be added to the accumulator.

Algorithm 2.1. Simultaneous multiple point multiplication (Shamir-Strauss method)

Input: Window width w, d = ,

, and P, . 3 Also according to [Bero1], it is originally due to Straus [Str64]. Output: kP + lS.

1. Precomputation. Computefor all.

2. Q

3. for i from d - 2 down to o do

3.1 Q ← 2 Q.

3.2 Q Q + (K P + L S).

4. Return(Q).

Storage: points. For w = 1, 3 points.

Precomputation:

Expected running time:

Using sliding windows can save about 14 of the precomputed points and decrease the number of additions to , which is about 9% saving for .

2.2. Interleaving method

This method is also a multiple point multiplication method, that is we want to compute for points and integers . In the comb and simultaneous multiplication methods, each of the precomputed values is a sum of the multiples of the input points. In the interleaving method, each precomputed value is simply a multiple of one of the input points. Hence, the required storage and the number of point additions at the precomputation phase is decreased at the expense of the number of point additions in the main loop. This method is flexible in that each can have a different representation, e.g., different window size, as if a separate execution of a window method is performed for each with the doubling step performed jointly on a common accumulator, as shown in [12]. As an illustration, we provide the following algorithm that computes where both k and l are represented to the same base .

2.2. Interleaving

Input: width w, d = ,

, and P, S E(F q).

Output: kP + lS.

1. Precomputation. Computeandfor all.

5. Return(Q).

Storage: points.

Precomputation: . Expected running time: .

In general, if different basis and/or representations are used for k and l, we have Storage: 2t points, where depending on the particular window algorithm used as discussed in Section 2.1.3.

Precomputation: 2t point operations (A or D).

Expected running time: A, where depending on the algorithm

2.3. SPA Attack on ECCs and its Countermeasures

Coron [3] has transferred the power analysis attacks to ECCs and has shown that an unaware implementation of EC operations can easily be exploited to mount an SPA attack. Moreover, it may also enable it to recognize the exact instruction that has been executed. For example, if the difference in power consumption between point doubling (D) and point addition (A) is obvious in their respective power traces, then, by investigating one power trace of a complete execution of a double-and-add algorithm, the bits of the scalar k are revealed. That is, whenever a D otherwise if D is followed by another D, then . This sequence of point operations is referred to as the DA sequence.

Window methods process the key on a digit (window) level. The basic version of this method, that is where _ = 0 in Section 2.1.3, is inherently uniform since in most iterations, w D operations are followed by 1 A, except for possibly when the digit is 0. Therefore, fixed-sequence window methods were proposed in order to recode the digits of the key such that the digit set does not include 0.

2.4. DPA Attack on ECCs and its Countermeasures

As for the SPA attack, Kocher et al. were the first to introduce the DPA attack on a smart card implementation of DES. Techniques to strengthen the attack and a theoretical basis for it were presented by Messerges et al. in . Coron applied the DPA attack to ECCs .

In order to resist DPA attacks, it is important to randomize the value of the long-term key involved in the ECSM across the different executions. Some of the countermeasures that were based on randomizing the key representation were proven to be inadequate since the intermediate point computed in the accumulator Q at certain iteration remained one of two possible values. The constancy of the value of this intermediate point is an integral part in the success of first-order DPA attacks.

A potential DPA countermeasure is known as key splitting. It is based on randomly splitting the key into two parts such that each part is different in every ECSM execution. An additive splitting using subtraction is attributed to Clavier and Joye. It is based on computing

The authors mention that the idea of splitting the data was abstracted in [5]. where r is a n-bit random integer, that is, of the same bit length as k. Alternatively, Ciet and Joye [8] suggest the following additive splitting using division, that is, k is written as

Hence, if we let , and S = rP, we can compute

where the bit length of r is n/2. They also suggest that (II) should be evaluated with the Shamir-Strauss method as in Algorithm 2.3. However, they did not mention whether the same algorithm should be used to evaluate (I). The following multiplicative splitting was proposed by Trichina and Bellezza [o] where r is a random integer invertible modulo u, the order of P. The scalar multiplication kP is then evaluated as

To evaluate (III), two scalar multiplications are needed; first R = rP is computed, then is computed.

III. KEY SPLITTING METHODS

3.1. Introduction

We discuss different forms of key splitting along with their strengths and weaknesses. We also discuss the candidate SPA-resistant algorithms and compare the resulting performance when combined with each form of key splitting. At the end of the chapter, we present countermeasures to DPA attacks on the ECDSA and the ECMQV algorithms.

This approach was suggested by Clavier and Joye in [CJ01] and revisited by Ciet [Cie03] as follows. In order to compute the point kP, the n-bit key k is written as

such that and , where r is a random integer of length n bits. Then kP is computed as

It is important to note that each of the terms should be evaluated separately and their results combined at the end using point addition. That is the multiple-point multiplication methods that use a common accumulator to save doubling operations. Whether at the bit level or window level -should not be used, even when a countermeasure against SPA is employed. This observation is based on the following lemma.

Letdenoteor, simply, the bits offrom bit positiondown to bit position, with.

Lemma 3.2 Let splitting scheme I at the end of some iteration j, , there are only two possible values for Q, those are P or P.

Proof. Algorithm 2.3—and similarly Algorithm 2.4—computes the required point by scanning

from the most significant end down to the least significant end. Hence, at the end of iteration j, the accumulator Q contains the value

We can write k, and as

Since we have

and

The DPA attack would proceed in the same way, whether the algorithm processes a single bit or a digit per iteration, though it would be more involved in the latter case depending on the digit size. The attacker can double the number of traces gathered and compute the necessary intermediate points as if there was no countermeasure in place.

3.2 Modular Division:

In the following algorithm, a and b are integers internally represented each by an array of w-bit digits. The length of each array is digits. Note that for the modular inversion, as mentioned by Savas and Ko, c [25], b needs not be less than the modulus u, but be in , where m = dw. Also note that the values , where , and are computed once per modulus, i.e., per curve.

Algorithm 3.4. Modular division

Input: u: a n-bit prime, , m = dw, (mod u) = (2m) (mod u), , a and .

Output: ab (mod u).

1. Compute R (mod u) using Algorithm 6.6.

2. Compute x = a(b R)R (mod u) using Algorithm 6.5.

3. Return(x).

The following algorithm is Algorithm 14.36 in [21]. We include it here for the sake of completeness.

Algorithm 3.5 Montgomery multiplication

Input: u: a n-bit prime, , m = dw,

and

Output: xy2 (mod u).

2.2 A (A + x y + u m)/ 2

3. if (A > u) then

A A u.

The following algorithm was presented by Savas and Ko, c as the modified Kaliski-Montgomery Inverse.

Algorithm 3.6. Montgomery inversion

Input: u: a n-bit prime, , m = dw, , and .

Output: R (mod u).

1. Compute f and using Algorithm 6.7, Where .

2. if then

2.1 x ← xR R (mod u) using Algorithm 6.5. // x = b 2 (mod u)

3.using Algorithm 6.5. //

4. Return(x).

IV. EXISTING SYSTEM

Nevine Maurice Ebied modified the almost Montgomery inverse algorithm of [ScKKoo] to be resistant to SPA attacks as in the following algorithm. Swap Address(c, d) denotes interchanging the memory addresses of the integer's c and d. This is an inexpensive operation, hence its usage as a dummy operation to balance the branches of the main loop. We implemented the "if" statement in steps 3.4 and 3.5 such that the number of conditions checked per loop iteration is always three. In assembly language, this can be easily ensured. Written in Java, step 3.4 is implemented as

If the condition is false, due to short-circuit evaluation, the flow control will move to the following "if" after the first check, otherwise, it will perform the check three times. The following "if"—step 3.5—is similar but with the condition checked only two times if((yLSb == o) && (yLSb == o)).

{"algorithm_caption":[],"algorithm_content":[{"type":"text","content":"Algorithm 3.7. Almost Montgomery inverse\n:Input: u: a n-bit prime,\nd = "},{"type":"equation_inline","content":"\left\lceil n/w \right\rceil"},{"type":"text","content":", m = dw and b ∈ [1, 2 "},{"type":"equation_inline","content":"^{m}"},{"type":"text","content":" - 1].\nOutput: f and b "},{"type":"equation_inline","content":"^{-1}"},{"type":"text","content":" 2 "},{"type":"equation_inline","content":"^{f}"},{"type":"text","content":" (mod u), where n ≤ f ≤ m + n.\n1. x ← u; y ← b; r ← o; s ← 1.\n2. f ← o.\n3. while (v > o) do\n3.1 U ← x - y; V ← -U.\n3.2 T ← r + s.\n3.3 f ← f + 1.\n3.4 if (((lsb (x)=o))) then\n// This "if" is special SwapAddress(x, U);\nSwapAddress (x, U) // dummy\nSHR(x); SHL(s).\n3.5 else if ((lsb(y) = o)) then\n// This "if" is special SwapAddress(y, V);\nSwapAddress\n(y, V) // dummy\nSHR(y); SHL(r).\n3.6 else if (V >= o) then\nSwapAddress(y, V);\nSwapAddress(s, T)\nSHR(y); SHL(r).\n3.7 else\nSwapAddress(x, U);"}]}

{"code_caption":[],"code_content":[{"type":"text","content":"SwapAddress(r, T)\nSHR(x); SHL(s).\n4. T ← u - r; V ← u + T.\n5. if (T > 0) then\nReturn(f, T)\nelse\nReturn(f, V)."}],"code_language":"txt"}

The drawback of this algorithm is that an SPA of the number of iterations of the main loop directly leaks the value of f. If f is uniformly distributed, the search space of b is reduced from to , which is not a significant reduction. It is interesting to study how f is actually distributed.

4.1. PROPOSED SYSTEM

We modified the Nevine Maurice Ebied's Almost Montgomery inverse and A SECRET KEY of [ScKKoo] to be resistant to SPA attacks as in the following algorithm.

{"algorithm_caption":[],"algorithm_content":[{"type":"text","content":"Algorithm:4.2. E.KESAVULU REDDY (EKR) Modified Montgomery Inversion\nInput: u: a n-bit prime, "},{"type":"equation_inline","content":"d = \left\lceil n/w \right\rceil"},{"type":"text","content":",\n "},{"type":"equation_inline","content":"m = dw, R^{2} (\bmod u) = (2^{m})^{2} (\bmod u), u = u^{-1} \bmod 2^{w} \text{and} b \in [1, 2^{m} - 1]"},{"type":"text","content":", t is Secret key.\nt: No of precomputed points "},{"type":"equation_inline","content":"1 \leq t \leq n"},{"type":"text","content":" \nW: Window width least significant of bit\n "},{"type":"equation_inline","content":"2^{w-z} \quad t \leq 2^{w} - 1"},{"type":"text","content":" \nOutput: "},{"type":"equation_inline","content":"b^{-1} R (\bmod u)"},{"type":"text","content":".\nSelect a number b such that "},{"type":"equation_inline","content":"(b, 2^{m}) = 1"},{"type":"text","content":" \nCompute "},{"type":"equation_inline","content":"b^{-1}"},{"type":"text","content":" such that "},{"type":"equation_inline","content":"bb^{-1} \equiv 1 (\bmod 2^{m})"},{"type":"text","content":" \n3. If f > m then "},{"type":"equation_inline","content":"x = b^{-1} 2^{f} (\bmod u)"},{"type":"equation_inline","content":"X = b^{-1} 2^{f} (\bmod u)"},{"type":"text","content":" \n4. If "},{"type":"equation_inline","content":"f \leq m"},{"type":"text","content":" then\n5. "},{"type":"equation_inline","content":"x \leftarrow R^{2} R^{-1} (\bmod u)"},{"type":"equation_inline","content":"X = R = 2^{m}"},{"type":"text","content":" \n6. "},{"type":"equation_inline","content":"x = b^{-1} 2^{m+f} (\bmod u)"},{"type":"text","content":" \n7. "},{"type":"equation_inline","content":"f \leftarrow m+f"},{"type":"text","content":" \n8. Return(x)"}]} In the EKR modified Montgomery Inverse Algorithm of Savas and Koc, we select f such that x=253
f=10
x=507
f=11
x=1014
f=12
x=2029
f=13
x=4059
f=14
x=8118
BUILD SUCCESSFUL (total time: 29 seconds) {"algorithm_caption":[],"algorithm_content":[{"type":"text","content":"gcd "},{"type":"equation_inline","content":"(b,2^{m})=1"},{"type":"text","content":", m ≤ f ≤ m + n. So b is not reduced from "},{"type":"equation_inline","content":"2^{m}"},{"type":"text","content":" to "},{"type":"equation_inline","content":"2^{m-\log2^{m}}"},{"type":"text","content":". Therefore, this is significant reduction and hence f is not uniformly distributed and it can't leak the value package javaapplication1;\nimport java.util.ArrayList;\nimport java.util.Scanner;\npublic class Main {\n public static void main(String[] args)\n {\n Scanner s=new Scanner(System.in);\n System.out.println(\"Enter a Prime Integer(U):\");\n int u=s.nextInt();\n String binU=Integer.toBinaryString(u);\n int n=binU.length();\n System.out.println(\"Enter a secrete Key(t):\");\n int t=s.nextInt();\n double w=0;\n for(int wi=1;wi<=t;wi++)\n {\n int i1=(int)Math.pow(2,wi-2);\n int i2=(int)Math.pow(2,wi)-1;\n if(i1<=t && t<=i2)\n {\n w=wi;\n break;\n}\n}\n System.out.println(\"Window width(W): \"+w);\n int d=(int)Math.ceil(n/w);\n System.out.println(\"Length of Each Array(d): \"+d);\n int m=(int)(d*w);\n System.out.println(\"...(m): \"+m);\n int on1=(int)Math.floor(Math.pow(2,m-1));\n int n2=(int)Math.pow(2,m);\n for(int i=m;i<on1;i++)\n {int n1=i;\n while(n1!=n2)\n {\n if(n1>n2)\n n1=n1-n2;\n else\n n2=n2-n1;\n}\n //System.out.println(\"GCD of two number is \"+n1+\"and i is \"+i);\n if(n1==1){on1=i;break;}\n}\n}"}]}

V. CONCLUSION

We modified the Nevine Maurice Ebied's Almost Montgomery inverse and A New variant of [ScKKoo] of Montgomery Inversion i.e is the EKR Modified Montgomery Algorithm to be resistant to SPA attacks. The EKR Modified Montgomery Inverse Algorithm eliminate the number of Iterations of the main loop directly leaks the value of f and also it is mathematically proved that f is uniformly distributed with a significant reduction

A function that is easy to evaluate but infeasible to invert unless the secret trapdoor t is known. So, the attacker cannot guess the key (t) to retrieve the valuable information in smart cards and mobile devices.