Efficient Exponentiation With Resistance To Channel Attack Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Security of information is of high priority in today's world. The mathematical complexity of the cryptosystems only protects it from logical/mathematical attacks. However, there are other means of attack such as those using side channel information to obtain power, voltage, leakage etc. statistics of the cryptographic device. This paper attempts to examine the different proposed algorithms concentrating on the efficient exponentiation methods that prove useful against side channel attacks.

Key words: RSA, Side Channel Attack, Power Analysis, Montgomery Multiplication method, m-ary method

1. Introduction:

Cryptography is the science of hiding information. For example, during the roman era, Julius Ceasar encrypted his texts by shifting each alphabet of his sentences by three alphabets. Through the advancement of modern science many algorithms for encrypting and decrypting a message have been developed. However, these algorithms are prone to attacks. That is, if the encrypted message is intercepted, it is likely that the interceptor develops ways to "crack" the original message. This project will deal with Side - Channel - Attacks with major emphasis on how to resist such attacks using exponentiation.

1.1 Side Channel Attack:

Side channel attacks are those attacks which make use of side channel information which can be retrieved from the encryption device. This information is neither the plain text not the encrypted text. When the plain text to be encrypted is fed into the encryption device, the input not only contains the plain text but also some additional inputs that are not part of the plain text. For example, the encryption devices produce timing information (this is easily measurable), radiations, power statistics etc. in most cases, the encryption device has voltage inputs that can be modified to give predictable outcomes. All or some of this information is used in side channel attacks to recover the key.

The side channel attack method was introduced by Kocher in 1996. Using side channel attacks, any cryptographic system can be broken using only a few hundred trials. The Fault attacks (FA) and Simple Power attacks (SPA) are the most effective. Side Channel attack devices are comparatively less expensive and range from couple of hundred to thousand dollars.

The first crypto system to be attacked using side channel information was the RSA (Rivest, Shamir and Adleman) cryptographic algorithm. RSA is a widely used public key cryptographic algorithm. It is classified as a one way function, which means that it cannot be reversed without knowing the private key. The extensive uses of RSA include electronic transactions, public signature applications, authentication schemes, smart cards, mobile phones etc. A bit length of 1024 for middle term applications and that of 2048 for long term applications is usually sufficient to be resistant against mathematical attacks.

Shamir, one of the creators of the RSA algorithm, distinguished between two types of attacks.

Active attack where a chip card (for instance) can be extracted, probed, partially destroyed, or used in varied environments,

Passive attack where a chip card can be externally watched during normal interaction with a chip card reader.

Active attacks are very powerful and often extract wide information about a system. These attacks are very rarely used to find individual secret keys as they are highly complex and expensive. Currently, the problem of protecting chip cards against active attacks has been unsolvable. On the other hand, passive attacks are due to the fact that an attacker has unsupervised access to the chip.

2. Power Analysis.

A chip card is known to be tamper resistant, and highly secure taking into consideration determined and well-financed attackers. The chip card is made of semiconductor logic gates made of transistors. When a cryptographic operation takes place, charges are applied to or taken from these transistor gates. The aggregate of all these charges are then tracked through the power consumption. If we connect a resistor in series with the chip's ground and the true ground, we can easily measure the power consumption. The current can be calculated using Ohm's law, i.e, the difference of voltage across the resistor divided the value of resistance would give the current flowing through the resistor. Hence, the power consumption can be used as a side channel to retrieve the key.

According to Kocher, Power Analysis (PA) attacks are a type of side channel attack. They are passive in the sense that they measure the power generated by the circuit while the circuit is carrying out encryption of decryption. The measured data gives the private key or some kind of information about it. Power Analysis have two types:

Simple Power Analysis (SPA)

Differential Power Analysis. (DPA)

Simple power analysis attacks measures the power consumption trace of the device in operation (when the device is encypting or decrypting) in order to retrieve the key or information about the key.

Differential Power Analysis attacks, tracks a large set of power consumption data and attempts to recover the key from observations and statistical analysis.

SPA is much less sophisticated as compared to DPA in general and is also less expensive. In SPA, a small number of rogue chip card readers can be used to analyze the power of a large number of individual cards. Since SPA requires only a minute trace of power consumption, the attacker can realize the attack without the knowledge of the cards owner. When the card owner uses his chip card for a transaction, an attacker can simply test the chip card for traces of power consumption using reasonable methods. These types of attacks can occur in secure Internet banking, Web Access and also remote corporate access networks.

However, in the case of RSA algorithm, it is easy to shield the encrypted message against DPA. The requirements of DPA demands that secret exponent is used to perform the attack with different input values. In order to effectively protect the message from DPA attacks, a random multiple of the group order is added to the exponent. Summing this up in equation form, it is represented as

cd+rφ(n) = cd mod n

This does not change the result, rather it changes the exponent itself. Hence, the side channel information recorded through different power samples is not related. The SPA however, though it is relatively simple compared to DPA, requires sophisticated countermeasures and is a pre-requisite to DPA because for the attacker the modified exponent d+rφ(n) is very similar to the exponent itself.

The RSA Algorithm.

The following notes show the calculations and methods involved in the encryption of RSA cryptosystems.

Choose a number 'N' such that it is a product of two large secret prime numbers 'p' and 'q'.

Calculate N=p x q

Calculate Z= (p-1) x (q-1)

Choose an integer 'e' such that it is co-prime to z.

Note: 1<E<z

Verify gcd [E,z] = 1

Finally compute 'D' such that D=E-1 mod [z]

The public keys are now 'N' and 'E' whereas the private key is 'D'.

Let 'C' be the encrypted message.

The receiver can decrypt this message by computing M=CD mod (N)

Modular computation cost and time are major factors that determine the performance of the RSA system. There are many different approaches to computation of the modular exponent which reduce cost and effort. Some of them will be discussed in this paper.

4. The m-ary Method

Exponentiation especially to very high powers can become tedious and time consuming. The m-ary method is a way to reduce the number of computations (multiplications) required in the exponentiation. Let the exponent be E, the number of bits scanned at a time be r, and the bit length of E is k. Now:

m=2r and sr=k

The powers of M mod N are calculated from 2 to m-1. This is the preprocessing required for m-ary method. The following algorithm gives the m-ary method.

Algorithm: The m-ary Method - left to right

Inputs: N = (nk−1, . . . , n1, n0)2,

E = (ek−1, . . . , e1, e0)2,

M = (mk−1, . . . , m1,m0)2

Output: C = ME mod N

1: Compute and store Mw mod N for w = 2, 3, . . . , m − 1.

2: Split E into r-bit words Fi for i = 0, 1, . . . , s − 1, sr = k

3: C = MFs−1 mod N

4: for i from s − 2 downto 0

5: C = CC2r mod N

6: if Fi not = 0 then C = CMFi mod N

5. Modified Representation of the Message

To effectively counter against SPA attacks, the exponent of the message can be represented in alternate form. This makes it well protected not only from SPA but also other types of power attacks.

R : Dk → {0, 1, ..., 2L − 1}; D is the digit set of the representation. For example, this can be a binary set representation. Larger representations of these digits can be used with pre computations to enable faster processing. Representations using signs can also be advantageous [example 0, +1] especially in the case of elliptic curves. This allows easy inversions. In RSA systems, inversions are very expensive and the symbolic representations do not have any significance. The user gains control of the control operations and hence control of side channel leaks by changing the representations without changing the values of the message itself.

One method to shield RSA from SPA attacks is to insert a dummy operation in a manner that the operation sequence does not depend on the message. This method of protection is flawed in the sense that computational cost is increased and also the message will now be vulnerable to safe - error - attacks.

5.1 Exponentiation with Integral Width Recoding.

Unsigned SPA resistant recoding of 'd' involves computing gd. The operation pattern is w-squares and 1 multiplication. The following algorithm illustrates this kind of exponentiation method.

Algorithm 1: Conversion to unsigned integral SPA-resistant representation

Input: L +2-bit exponent d = (10dL−1 . . . d0)2, width w;

Output: Recoded exponent (uL . . . u0);

1. i ← 0; γ ← 0;

2. while i ≤ L−w do

(a) ui ← (di+w−1 . . . di)2 − γ;

(b) if ui ≤ 0 then ui ← ui + 2w; γ ← 1; else γ ← 0;

(c) ui+1 ← 0, . . . , ui+w−1 ← 0; i ← i + w;

3. if i < L then

(a) ui ← (dL−1 . . . di)2 − γ;

(b) if ui ≤ 0 then ui ← ui + 2L−i; γ ← 1; else γ ← 0;

(c) ui+1 ← 0, . . . , uL−1 ← 0;

4. uL ← 2 − γ; return (uL . . . u0);

Algorithm 2: Integral width pre-computations and exponentiation

Input: L +2-bit exponent d = (10dL−1 . . . d0)2, width w, basis g;

Output: c = gd;

1. g[1] ← g;

2. for i from 2 to 2w step 2 do g[i] ← g[i/2]2; g[i + 1] ← g[i] âˆ- g;

3. recode d with Algorithm 1; i ←L−1; c ← g[uL];

4. while i ≥ 0 do

(a) c ← c2;

(b) if ui > 0 then c ← c âˆ- g[ui];

(c) i ← i − 1;

5. return c;

The above algorithm is a table based exponentiation. This can be a disadvantage as the table size becomes limited. Cost of pre computations become high and the table size increases exponentially with the width w, for large values, the number of bits that are scanned at one time soon becomes impractical for large values of w. The SPA resistant coding technique can also be modified to an unsigned fractional width recoding

5.2 Unsigned Fractional width recoding.

Here, we compute parameters x and y simultaneously. x corresponds to the width w and y corresponds to the width w - 1. The values of x and y are such that it should not be feasible for attackers to access the message. To do this, first a set of pre-computed values are calculated/randomized. More precisely,when the pre-computed table has k entries, define w = [log2(k)]. Then, the 2w−1 elements {c, c2, . . . , c2^(w−)1} are always pre-computed, but k−2w−1 additional pre-computed elements are randomly chosen in the set {c2^(w−1)+1, c2^(w−1)+1, . . . , c2^w}. In the following, we call B the set of the exponents of the chosen pre-computed elements.

The main idea in the following Algorithm is that the choice of recoding a sequence of bits with the width w or w - 1 looks random to the attacker. The principle of the recoding is the same as in the signed fractional width algorithm. B is the set of exponents of the pre-computed values, define the width w = [log2(k)] and the probability p = k/2w−1 − 1. Then, for x computed with width w and y with width w − 1, we apply the following rules:

Algorithm 1: Conversion to unsigned fractional SPA-resistant representation

Input: L +2-bit exponent d = (10dL−1 . . . d0)2, table size k, index set B;

Output: Recoded exponent (uL . . . u0);

1. i ← 0; γ ← 0; w ← [log2(k)];

2. while i ≤ L−w do

(a) x ← (di+w−1 . . . di)2 − γ;

(b) y ← (di+w−2 . . . di)2 − γ;

(c) if x ≤ 0 then x ← x + 2w; γx ← 1; else γx ← 0;

(d) if y ≤ 0 then y ← y + 2w−1; γy ← 1; else γy ← 0;

(e) if x ≤ 2w−1 then

i. rnd ← generate w − 1 random bits;

ii. if rnd < k − 2w−1 then ui ← x; γ ← γx; r ← w;

iii. else ui ← y; γ ← γy; r ← w − 1;

(f) else if x ∈ B then ui ← x; γ ← γx; r ← w;

(g) else ui ← y; γ ← γy; r ← w − 1;

(h) ui+1 ← 0, . . . , ui+r−1 ← 0; i ← i + r;

3. if i < L then

(a) ui ← (dL−1 . . . di)2 − γ;

(b) if ui ≤ 0 then ui ← ui + 2L−i; γ ← 1; else γ ← 0;

(c) ui+1 ← 0, . . . , uL−1 ← 0;

4. uL ← 2 − γ; return (uL . . . u0);

1. if x ≤ 2w−1 then choose x with probability p or y with probability 1 − p,

2. else if x ∈ B (in other words, gx is pre-computed), choose x (this occurs with probability p),

3. else choose y (in that case, gx is not pre-computed, this happens with probability 1 − p).

Therefore, for randomly chosen exponents, the width w is chosen with probability p and w−1 with probability 1−p. Additionally, since the set B is randomized for each new recoding, the two patterns can actually appear for the same sequence of bits.

5.3 Exponentiation With Fractional Width Recoding.

The technique for the exponentiation with a fractional SPA-resistant width is almost the same as in the integral case, with the exception of the pre-computation step. Indeed, since the pre-computed table is de-generated, the values in the upper half part of the table are computed with a special procedure. Since gi = gi−2^(w−1) âˆ- g2^(w−1) , the pre-computations use the value g2^(w−1) which is already available in order to compute the upper half part of the table. Note that in Algorithm 2, for the sake of simplicity, the pre-computed table is indexed with the exponent of the pre-computed values. In reality, a look-up table should be used in order to save memory: such table could be indexed with the exponents of pre-computed values, and would additionally store a pointer to the actual location of the pre-computed value.

Algorithm 2. Fractional width pre-computations and exponentiation

Input: L +2-bit exponent d = (10dL−1 . . . d0)2, table length k, basis g;

Output: c = gd;

1. g[1] ← g;

2. for i from 2 to 2w−1 step 2 do g[i] ← g[i/2]2; g[i + 1] ← g[i] âˆ- g;

3. for all i > 2w−1, i ∈ B do g[i] ← g[i − 2w−1] âˆ- g[2w−1];

4. recode d with Algorithm 1; i ←L−1; c ← g[uL];

5. while i ≥ 0 do

(a) c ← c2;

(b) if ui > 0 then c ← c âˆ- g[ui];

(c) i ← i − 1;

6. return c;

6. The Montgomery Modular Multiplication Method (MMM)

The basic representation of this method is X.Y.R-1 mod N. This is slightly different from the usual RSA representation which is X.Y mod N. According to many researchers the MMM is the best approach on minimizing computation cost of modular multiplication. By redesigning the original RSA expression, the extra constant R-1 is removed. The method which will be discussed is with reference to Apostolos P. Fournaris's research paper.

To design a high FA and SPA resistant modular exponentiation, a carry and save logic is used in all inputs, intermediates and outputs of the MMM.

Montgomery Modular Multiplication method calculates the value of X.Y.R-1 mod. R is taken as a constant number, usually R is set to 2n. The value of R is chosen such that the greatest common divisor of R and N is 1 (which implies R and N are co-prime). But since N is the product of two prime numbers (all prime numbers except 2 are odd) the condition gcd(R,N)=1 will always be true for R=2n .

6.1 Montgomery Modular Multiplication algorithm:

The Montgomery algorithm replaces the division operation with 'k' divided by a power of two. Let a, b and N be binary numbers of bit size 'k'. We see that the computation time is greatly reduced and also the area for hardware implementation is reduced. MMM is defined as R = a'b'r−1 mod N, where r = 2k. The numbers a and b need to be converted to their N residue form such that a'= ar mod N.The multiplication of two N-residue numbers is also an N - residue number. The multiplication operation performed by the MMM is R' = arbrr−1 mod N = abr mod N. We require that R' and 1 are multiplicands of MMM as R = (abr) 1r−1 mod N = ab mod N.

A slight modification of the original MMM algorithm omits the final subtraction stage as proposed by Walter. The following algorithm uses MMM without the final subtraction step.

Algorithm: MMM with No Final Subtraction

Input: N = (nk−1, . . . , n1, n0)2,

X = (xk, . . . , x1, x0)2,

Y = (yk, . . . , y1, y0)2,

r = 2k+2 mod N, n0 = 1.

Output: T = MonPro_NFS(X, Y,N) = XY r−1 mod N

1: T = 0

2: for i from 0 to k + 1

3: if (T + xiY ) is even then T = (T + xiY ) /2

4: else T = (T + xiY + N) /2

We use adders for the MMM in step 4 of the. CSA is a very convenient way to reduce 3 k-bit operands to 2 k-bit operands. The result is represented as a carry save operation (C,S). If we wish to reduce the results from 2 k-bit operands to 1 k-bit operands, a final addition step is necessary to convert back to the normal number representation. A convenient way to do this is by using, Carry Ripple Pipelined Adder (CRPA) The CRPA takes in k-bit operands one word per k/w clock cycles using a w-bit carry ripple adder. The figure for the CRPA is shown below. MMM block has been realized with MonPro NFS CSA algorithm, which is given as Algorithm below.

Algorithm: MMM with No Final Subtraction using CSA Representation

Input: N = (nk−1, . . . , n1, n0)2,

XC = (xck+1, . . . , xc1, xc0)2,

XS = (xsk+1, . . . , xs1, xs0)2,

Y C = (yck+1, . . . , yc1, yc0)2,

Y S = (ysk+1, . . . , ys1, ys0)2,

r=2k+2 mod N, n0 = 1.

Output: (TC,TS) = (XC,XS) (Y C,Y S) r−1 mod N

1: TC = 0, TS = 0

2: for i from 0 to k + 1

3: xi = xci + xsi, (C1, S1) = TC + TS + xiY C0,

(C2, S2) = C1 + S1 + xiY S0

4: if s20 = 0 then (TC,TS) = (C2 + S2) /2

5: else (TC,TS) = (C2 + S2 + N) /2

Fig 1: The Carry Ripple Pipelined Adder

7. Conclusions:

Security of information is of high concern in present times. As the methods of encryption improve so do the methods of attacks. RSA is a widely used cryptosystem and like any other algorithm is vulnerable to security breaches. Mathematical attacks can be easily shielded against by increasing the complexity of the algorithm. However, there are also other methods to analyze the cryptosystem and find a loop hole to attack it.

One such method is the side - channel - attack which makes use of the power spectrum generated by the cryptograph. To protect the message from side channel attack, we can use different methods of exponentiation with regards to the RSA algorithm. One of the most effective methods is the Montgomery Multiplication Method. There are also other methods such as simply modifying the initial definition of the RSA, i.e by adding an extra constant in the form of the expression X.Y.R-1 mod N.

Exponentiation not only protects the Cryptosystem from power attacks but also does so against timing attacks, cache attacks and simple power analysis. In order to design an effective exponentiation method, it is required that the method be efficient, not affect the performance of the system and also should be fast. The methods explained in this paper aim for the same, and are proven to be some of the most efficient and secure methods.