Simple Power Analysis of Unified Codefor ECC Double and Add
Colin D. Walter
Comodo Research Laboratory
10 Hey Street, Bradford, BD7 1DQ, UK
Colin.Walter@comodogroup.com

Abstract. Classical formulae for point additions and point doublings
on elliptic curves differ. This can make a side channel attack possible
on a single ECC point multiplication by using simple power analysis(SPA) to observe the different times for the component point operations.
Under the usual binary exponentiation algorithm, the deduced presenceor absence of a point addition indicates a 1 or 0 respectively in the secretkey, thus revealing the key in its entirety.
Several authors have produced unified code for these operations in order
to avoid this weakness. Although timing differences are thereby eliminated from this code level, it is shown that SPA attacks may still bepossible on selected single point multiplications if there is sufficient sidechannel leakage at lower levels. Here a conditional subtraction in Montgomery modular multiplication (MMM) is assumed to give such leakage,
but other modular multipliers may be equally susceptible to attack.
The techniques are applicable to a single decryption or signature evenunder prior blinding of both the input text and the secret key. This meansthat one should use a constant time implementation of MMM even if thesecret key is blinded or replaced every time, and all side channel leakage
should be minimised, whatever multiplier is used.
Key Words. Side channel leakage, simple power analysis, SPA, elliptic
curve cryptography, ECC, unified code, Montgomery modular multiplication.

“To ensure that the data carrier consumes the same amount of current
whether the requested operation is authorized or unauthorized, a bit isstored in the memory in either event.” [Abstract, US Patent 4211919,“Portable data carrier including a microprocessor”, filed 28 Aug 1978.]“No one sews a patch of unshrunk cloth on an old garment, for the patch
will pull away from the garment, making the tear worse.” [Matt 9:16, The
Bible (New International Version)]

1

Introduction

Side channel leakage of secret key information from cryptographic devices has
been known publicly for a number of years [1]. In elliptic curve cryptography
M. Joye and J.-J. Quisquater (Eds.): CHES 2004, LNCS 3156, pp. 191–204, 2004.
c International Association for Cryptologic Research 2004

192

C.D. Walter(ECC) [9,13], techniques to reduce this leakage include the use of unified codefor point additions and point doublings [3,7,8,12]. When properly implemented,
this should eliminate the ability to distinguish the two operations by timing
measurements on an appropriate side channel such as power variation [10,11].
However, for a point doubling some of the arguments are inevitably repeatedunless extra precautions are taken. This means that doublings might be separated from additions simply by observing when identical operands, identicalarithmetic computations, or identical results are likely to have occurred1 . Thismight be done using timing, current or EMR variation [4,5,6,10,11,15]. The generality of such an attack shows that it may be unwise to attempt to patch upold (i.e. leaky) hardware using new, leak-resistant software counter-measures.
Here, to make the details concrete and quantifiable, this is considered for a
specific choice of the algorithms and form of side channel leakage, namely: i) point
multiplication using the standard square-and-multiply exponentiation algorithm,
together with ii) the version of unified code presented by Brier and Joye [3]and their suggested implementation, iii) field multiplication using a version ofMontgomery modular multiplication (MMM) [14] which includes a conditional
subtraction and iv) a cryptographic device in which every such subtraction canbe observed on some side channel or combination of side channels. It is shownthat this association leaks sufficiently for it to be computationally possible todeduce some keys for standard elliptic curves over the smaller fields even if they
are used just once. The choice of Montgomery, while perhaps not natural for
the EC-DSA prime fields, has the benefit of being very well studied, so that therequired probabilities are known. Almost any other leaky modular multiplier
could be substituted.
One of the standard, recommended, EC-DSA elliptic curves is chosen for
illustration, namely P-192 [2]. Some theoretical analysis shows that there aresome input texts which are weaker than average in terms of the number of
additions which can be positively identified as not being doublings. Increasing
the sample size yields still weaker cases. Experimental results confirm the theory
very strongly, showing indeed that there are even weaker instances where thesecret key can be recovered without significant computational resources.
The discussion overturns several potential misconceptions. First, unified codeon its own is not a panacea against simple power analysis. It protects only one
aspect of the implementation. Secondly, the three standard blinding techniques
helpfully listed by Coron [4] can provide no protection at all against some attacks. And thirdly, modular multiplication can leak sufficient data for a successful
attack even when a key is used just once, such as in the Digital Signature Algorithm (DSA) [2]. Previously, MMM was only known to leak so severely if thesame, unblinded key was used repeatedly.
1

For example, for both the redundant-operation-enhanced formulae of [7] and theHessian form in [8], doubling reveals itself if field squares can be detected. Further,
the Jacobi form in [12] suffers from essentially the same potential weakness as is
explored here for the Weierstraß form in [3], namely repeated evaluation of identicalfield products.

Simple Power Analysis of Unified Code193

In conclusion, even with modern leak-resistant algorithms, field multiplication should clearly be implemented in a time independent manner and, indeed,although the case is not detailed here, in a manner which has a low probability of emitting enough side channel leakage to distinguish successfully between
identical and non-identical pairs of multiplications.

2

The Unified Point Addition/Doubling Formula of Brier& JoyeBrier and Joye [3] provide formulae which unify the classical formulae for point
addition and point doubling on the Weierstraß form of an elliptic curve. They
describe a number of cases, including the use of either affine or projective coordinates.
In their point addition formula for affine coordinates, there is no longer adenominator which becomes zero for point doubling. So a separate formula is notneeded. Although there is still a denominator which may be zero, this special
case is no longer associated with point doubling, but with the sum being theexceptional point O at infinity. So the formula breaks the previously strong
connection between bit values of the secret key and sub-sequences of arithmetic
operations.
Assume projective coordinates are used for the representation of points P =(x, y, z) on the Weierstraß form of an elliptic curvey 2 z = x3 + axz 2 + bz 3
where the field characteristic is not 2 or 3. Then, for points Pi = (xi , yi , zi ),1 ≤ i ≤ 3, the point addition P3 = P1 +P2 is achieved by Brier and Joye using:x3 = 2f w
y3 = r(g − 2w) − l2z3 = 2f 3(1)

u1 = x1 z2 , u2 = x2 z1 , t = u1 + u2 ;s1 = y1 z2 , s2 = y2 z1 , m = s1 + s2 ;z = z1 z2 , f = zm, l = mf, g = tl;
r = t2 − u1 u2 + az 2 , w = r2 − g.

(2)

where

This involves eighteen field multiplications, of which one is by the constant a,five are in the equations (1) and thirteen in the equations (2). Without loss ofgenerality, it is assumed that the implementation under attack computes thecoordinates of P3 by taking each of these last equations (2) and calculating theright sides in the order presented before calculating those for (1).

3The Point Multiplication Algorithm

We assume point multiplication is done using the standard square-and-multiply(or double-and-add) exponentiation method of Fig. 1. There are two main properties of this algorithm which are used here. First, each bit 1 in the key generates

194

C.D. Walter
Input: P, k = (kN −1 ....k1 k0 )2 with kN −1 = 1
Output: Q = kPQ←P;
For i ← N −2 downto 0 do
Begin
Q ← 2Q ;If ki 6= 0 then Q ← Q + P ;EndFig. 1. Left-to-Right Binary “Double-and-Add” Algorithm.

a point doubling followed by a point addition, but a bit 0 in the key generates apoint doubling which is followed by another point doubling. Hence, it is easy totranslate from a sequence of adds and doubles obtained through a side channel
into a sequence of bits which reveals the secret key. Secondly, the initial input
P is an argument in every point addition. Although this may save some data
manipulation, it occasionally produces the bias in each point addition which is
exploited here. Choosing instead the right-to-left version of binary exponentiation or m-ary exponentiation (m > 2) would probably render the attack here
computationally infeasible.

4

Notation and Montgomery Multiplication

For simplicity, we assume the main side channel leakage is from an implementation of field multiplication using Montgomery Modular Multiplication (MMM)[14] in which there is an observable, final, conditional subtraction. However, it
must be emphasised that this choice is only for convenience in evaluating theprobabilities. A similar attack could be mounted against any modular multiplier
exhibiting data-dependent side-channel leakage.
Suppose the elliptic curve is defined over the Galois field GF (P ) = FP ∼=Z/P Z and elements of this prime field are represented as long integers modulo P
Pn−1
written to base r with digits in lowercase. Thus, for example, A = i=0 ai ri ∈FP . Suppose R (≥P ) is the upper bound we wish to have on the inputs andoutputs for MMM. Then we assume the version of MMM given in Fig. 2.
Input: A and B such that A, B < R ≤ rn and P prime to r.
Output: C such that C ≡ ABr−n mod P and C < R
C ← 0 ;For i ← 0 to n-1 do
Beginqi ← -(c0 +ai b0 )p0 −1 mod r ;C ← (C+ai B+qi P) div r ;End ;{ Invariant: Crn ≡ A×B mod P and ABr−n ≤ C < P +ABr−n }If C ≥ R then C ← C-P ;Fig. 2. Montgomery’s Modular Multiplication Algorithm (MMM).

Simple Power Analysis of Unified Code195

The invariant after the loop is easy to establish, and, if desired, the digits
qi could be formed into a quotient Q giving the multiple of P which has been
subtracted. The post-condition C < R then holds providing n and R satisfy
the right properties, namely that the maximum possible value for C is less thanR+P , i.e. P +R2 r−n ≤ R+P , which is just the stated pre-condition R ≤ rn .
This post-condition enables output from one execution of MMM to be fed intoanother instance of it.
The usual values for R to take are rn or P . The former gives a cheap testin the conditional statement, whereas the latter yields the least non-negative
residue as output. Decreasing R or increasing n reduces the frequency of the
final subtraction and so reduces the leakage from the timing side channel. In
fact, the subtraction ceases to occur if P +R2 r−n ≤ R, i.e. if P ≤ R(1−Rr−n )[18]. As this requires P < R < rn , we would take R as a power of 2 to make thecondition easy to evaluate – say R = 12 rn – and demand that n be large enough– say P < 14 rn . Indeed, this choice for R permits the maximum possible value of
P to give no final subtraction for a given n. Hence, for a given maximum valueof P , it is possible to deduce values for n and R which will always prevent the
final subtraction occurring.
Where side channel attacks are possible, the final, conditional subtraction
should be protected from timing variation by performing the subtraction in allcases if it can occur at all and then selecting the new or old value of C as
appropriate. Eliminating the need for the final subtraction may lead to less sidechannel leakage, but an extra loop iteration may be the result of choosing nsufficiently large for this to happen.
Because, unlike RSA, the ECC-related equations (2) involve field additions
or subtractions between some field multiplications, here it is most convenient
to take R = P . Then, as noted, the final subtraction will occur occasionally.
Observe from the post-loop invariant that its occurrence is independent of theorder of inputs. So changing the input order is not a counter-measure to any
attack on the final subtraction.

5

The Probability of a Conditional Subtraction

To estimate the probability of the extra subtraction of P in MMM, observethat P is large and so one can switch from discrete to continuous methods.
For all practical purposes, inputs to MMM are uniformly distributed modulo
P . Thus, if the random variable X represents a typical input to MMM, its
probability density function f is given by f (x) = P −1 on the interval [0, P ],and f (x) = 0 otherwise. Furthermore, outputs are also effectively uniformly
distributed modulo P . So the probability of the extra subtraction for random
inputs can be deduced from the invariant formula after the loop in MMM [18].
Derivations of this probability are given in [16,17,19] for various contexts2 . In
2

Taking R equal to a power of 2 leads to some interesting non-uniform distributions
which are illustrated graphically in [17].

196

C.D. Walter

the case of squaring X, the probability is pS = prob(X 2 r−n +Z > P ) where Z
is uniform on [0, P ]. Hence
Z P
P −1 f (x)x2 r−n dx = 13 P r−n
pS =
(3)
0

In the case of multiplying two independent, random residues X and Y , theprobability of the conditional subtraction is pM = prob(XY r−n +Z > P ) for
equi-distributed Z, namely
Z PZ PP −1 f (x)f (y)xyr−n dy dx = 41 P r−n
pM =
(4)
0

0

However, for the standard exponentiation algorithm of Fig. 1, the point doublings
require field multiplications by a fixed constant, namely a coordinate of theinitial (plaintext) point P. If pC is the probability of the final subtraction when
multiplying a random input X by a constant C, then pC = prob(CXr−n +Z>P )so that
Z
P

pC =
0

P −1 f (x)Cxr−n dx = 12 Cr−n(5)

The different coefficients of r−n in these three equations enable the different
operations to be distinguished by their subtraction frequencies when a numberof exponentiations occur with the same secret key k [19,16]. Here cases will beselected where C has the most extreme values in order to force final subtraction
behaviour that proves two products have different inputs.

6

Side Channel Leakage

In addition to the assumptions about the algorithms used, in this instance of
the attack, it is supposed that every occurrence of the conditional subtraction
in MMM can be observed. With good monitoring equipment and a lack of otherhardware counter-measures, successive data loading cycles can be observed andhence the operations timed, thereby enabling the occurrences to be deduced.
Previous authors have described in detail how timing and power attacks canbe performed [10,11,5,15,6]. In fact, all we require here is a reasonable probability of determining whether or not two given instances of modular multiplication
have the same pair of inputs. This might be done equally well by power or EMR
analysis rather than by timing – the power consumption curves may be sufficiently characteristic of the inputs for this to be possible [20]. Furthermore, thisproperty of distinguishability may occur for any modular multiplier, implyingthat the attack described here is not restricted only to Montgomery multipliers.

7

Distinguishing Doublings from Additions

To provide outline theoretical justification for the later experimental results, inthis section a particular single signing or decryption is selected from a randomlySimple Power Analysis of Unified Code197

generated set of samples. This selection has properties which increase the numberof point operations that can be definitely determined as additions or doublings
from knowledge of the conditional subtractions. Consequently, for this choice
there is a reduction in the computational effort to traverse the space of possible
keys and recover the key used.
Brier and Joye [3] provide an algorithm for computing P3 = P1 +P2 by imposing a suitable ordering on equations (2). In the case of the point doubling
operation with P1 = P2 = (x, y, z), the arithmetic of (2) specialises to:u ← x ∗ z; u ← x ∗ z; t ← u + u;s ← y ∗ z; s ← y ∗ z; m ← s + s;z ← z ∗ z; f ← z ∗ m; l ← m ∗ f ; g ← t ∗ l;r ← t2 − u2 + a ∗ z 2 ;w ← r2 − g;(6)Here the first two applications of MMM are identical, as are the second two. So
both pairs exhibit identical behaviour with respect to the occurrence of the final
conditional subtraction. It is the repeated or different behaviour within the pairs
which creates the handle for an attack. If the recorded behaviour is different atthese points, the curve operation must be a point addition.
From a sample of signatures or decryptions, the attacker starts by selecting
the case which has the smallest number of undetermined operations. The initial,naı̈ve way to do this is just to count the total number of operations, and subtract
the number of those for which the computations of either u1 and s1 , or u2 ands2 , or both, involve differences regarding the final subtraction.
Point additions involve the initial input P = P1 = (x1 , y1 , z1 ) where thenatural variation in random (or randomized) coordinates means that occasionallyx1 and y1 will both be small (i.e. close to 0) and z1 will be large (i.e. close to P ).
By equation (5), this means the computations of u1 and s1 in (2) will be less likely
than average to include the additional subtraction, while the computations of u2
and s2 will be more likely than average to include the additional subtraction. For
such initial P, this enhances the likelihood of different behaviour with respect
to subtractions in these pairs of multiplications, thus increasing the number ofpoint operations which can be definitely determined to be additions rather thandoublings.
Such a point is used below to develop some theory3 . But, in fact, with theselection criterion above and others developed later, the attacker is actually likely
to choose a case which is much more amenable to an attack than that where P
has such extreme coordinates.
3

A case with small x1 , small y1 and large z1 is almost always obtained by choosing
the side channel trace which maximises the average number σ of differences per
operation:P
op {δop (u1 , u2 )+δop (s1 , s2 )}σ =#operations
where δop (x1 , x2 ) is 1 or 0 depending on whether or not the products x1 and x2 differ
with respect to the occurrence of a final subtraction in operation op of a complete
point multiplication.

198

C.D. Walter

Suppose the sample size is 512. This is a reasonably practical number ofsamples to obtain. In one eighth of cases, x1 will lie in the interval [0, 18 P ] and1have an average value of 16
P . So, from 512 = 83 cases we can expect one instance
where the initial input is
1
1
P, 16
P, 15
P0 ≈ ( 1616 P )(7)

P0 is always an input, say P1 , to each point addition. It is constant over the setof all point additions of the associated signing or decryption. The other input,
P2 , for these point additions is, for all practical purposes, a point with random
coordinates. Hence (5) is the formula to apply.
For each of the example EC-DSA curves [2] over a field of odd characteristic
P , the field order is a generalized Mersenne prime. For example, P-192 uses
P = 2192 −264 −1. Consequently, P is very close to a large power of 2 and, in
MMM, rn will certainly be taken equal to that power of 2 (except perhaps for
P-521). So rn = 2192 for P-192. Therefore, the ratio P r−n will be essentially 1
for most EC-DSA curves used in practice.
Using P0 and this value for P r−n in (5), u1 ← x1 ×z2 incurs a final sub1
, and the same holds for thetraction with probability approximately psmall = 32
computation of s1 . Similarly, u2 ← x2 ×z1 incurs a final subtraction with proba15, and the same holds for the computation of s2 .
bility approximately plarge = 32
As the different inputs are independent, the probability pdiff of u1 incurring asubtraction but not u2 , or vice versa, ispdiff = psmall ×plarge + psmall ×plarge =

241
512

≈

1
2

There is the same probability of distinguishing between s1 and s2 in this way.
As the outputs from the loop of MMM are uniformly distributed over aninterval of length P , the subtractions for the four products are all independentof each other even though some share a common input. So the probability paddof proving that a point addition occurs as a result of observing differences insubtractions for at least one of the pairs is4
padd = (pdif f )2 =188703262144

≈

3
4

(8)

In a similar way, one can obtain the probabilities pA00 , pA02 , pA20 and pA22
of a point addition displaying, respectively, no subtractions, no subtractions fortwo multiplications then two subtractions, two subtractions then no subtractions, and four subtractions. These are the cases where the subtractions leave it
ambiguous as to whether the operation is a point addition or a point doubling.
For the fixed input P0 given in (7) and a random input P2 ,pA00 = psmall ×plarge × psmall ×plarge =pA02 = psmall ×plarge × psmall ×plarge =pA20 = psmall ×plarge × psmall ×plarge =pA22 = psmall ×plarge × psmall ×plarge =427772910485767905
10485767905
1048576
225
1048576(9)

The accuracy here and later is absurd, but it should enable readers to understandand check the calculations more easily.

Simple Power Analysis of Unified Code199

In the case of a (random) doubling, the field multiplications of interest have two
independent random inputs and so, by (4), the corresponding probabilities are:9
pD00 = pM × pM = 16
3
pD02 = pM × pM = 16(10)

3
pD20 = pM × pM = 161
pD22 = pM × pM = 16

These last probabilities sum to 1 because it is not possible for the multiplications
within a pair to behave differently.
By (8), about three quarters of the additions are determined immediately.
On average, this leaves about 26 34 additions unrecognised for P-192 (30 if thesample size is reduced to only 64). In fact, simulations below in Table 2 showthat the attacker, with a better selection criterion, has a mere 19 14 additions
unrecognised for the same sample size of 512.
For undetermined cases, the number of final subtractions can still be used tomake a probabilistic decision between an add or a double. Suppose an operation
is known to be a point addition with probability πA and a point doubling withprobability πD = πA , and the subtractions do not distinguish the operation as
an addition. Using the same notation as above for counting subtractions, theprobabilities of a point addition in the various cases can be deduced from (9)and (10) as:
πA 277729
293764≈ π +πAπ 9
padd|00 = π 277729+π 9
A 293764

padd|02 = padd|20 =padd|22 =

D 16

A

D 16

7905
πA 293764
7905
3
πA 293764+ πD 16225
πA 293764
1225+ πD 16πA 293764

≈ 0

(11)

≈ 0

Consequently, no subtractions are most likely in such a situation, and the bias
to one or other depends on the context, such as neighbouring operations, whichmight influence the value of πA . In the unlikely event of two or four subtractions,the attacker would be unfortunate if more than one or two such operations were7905+7905+225≈ 23 suchnot doublings: on average he expects only 26 34 × 277729+7905+7905+225
operations for P-192.

8

Reconstructing the Secret Key

This section covers both the deduction of unclear key bits from the overall structure of the point operations, and a search of the subspace of keys which areconsistent with that structure and with previously determined operations.
Again, for this section, numerical examples apply to the standard P-192 curve
defined in FIPS 186-2 [2] for EC-DSA. This has the advantage of a short key
length. The methods apply in exactly the same way to other curves, but it will
become evident that larger fields require more computational effort.
From Fig. 1, the structure of point operations during signing or decryption
can be viewed as a string S over the alphabet {A, D} in which the first character

200

C.D. Walterof S is ‘D’ (a double), each ‘A’ (an add) is preceded by a ‘D’, and there are a
known, fixed number of occurrences of ‘D’, namely N −1 where N is the numberof bits in the key k. On average, there will be 12 (N −1) ‘A’s, but for each casethis can be established exactly by taking the total number of operations (thelength of S) and subtracting the number of doublings.
By (8), a substantial number of the ‘A’s are known. Each known ‘A’ determines its neighbours as ‘D’ on either side (see Table 1). Some occurrences of‘D’ are determined by two ‘A’s. The probability of this for an interior ‘D’ is( 12 padd )2 . Neglecting differences caused by end conditions (such as the last ‘A’is, or is not, followed by a ‘D’ and the initial ‘D’ is known), the total number ofdetermined operations is, on average, about3122 (N −1)padd − (N −2)( 2 padd )(12)

For the on-going P-192 example, about 68 34 additions are determined fromthe subtractions and so, by (12), around 181.6 operations in total. This leaves
about 26 34 ‘A’s to allocate among approximately 286.5−181.6 = 104.9 unknown
82
positions – approximately 104.9
choices. However, these choices cannot
26.75 ≈ 2
be made freely.
Two thirds of the string S is accurately determined as above. This leaves
a number of short substrings to be guessed. These are restricted to patterns
which do not have consecutive ‘A’s. For our parameter choices, the number ofthese substrings decreases exponentially with their length. So, most frequently,
the unknown substrings are of length 1. They can be either ‘A’ or ‘D’. Eachpossibility can occur. However, substrings of length 2 are constrained to ‘AD’,‘DA’ or ‘DD’, and those of length 3 to only ‘ADA’, ‘ADD’, ‘DAD’, ‘DDA’or ‘DDD’. So only 43 of choices are possible for length 2 substrings, only 58 forlength 3, and one half or less for longer substrings. (The numerators go up in a
Fibonacci sequence: 2, 3, 5, 8, 13,...; and the denominators in powers of two.)In the P-192 example, about 7 substrings of length 2 occur, 4 of length 3,
and 7 of longer lengths. So fewer than ( 34 )7 ( 85 )4 ( 12 )7 of the 282 choices, and, more
precisely, only roughly one in 215.6 , satisfies the constraint of preceding each ‘A’
by a ‘D’ (see Table 2). The search space is therefore reduced to under 267 .
In allocating the ‘A’s, we can also note that ‘D’ is much more likely in some
7
cases, and ‘A’ perhaps in others. For example, by (10), 16
of doubles will exhibit
2 or 4 subtractions, but, by (11), very few operations with this behaviour could
7(191−(2×68 34 −24.6)) ≈ 34 doubles canbe additions. In the example, about 16
be so identified with high probability and on average it is only necessary to try
up to 2 of them as doubles. Thus, in estimating the computational effort, the
104
34
70
71
26.75 can be replaced by 2
24.75 ≈ 2 . With the substring constraints, this56
now reduces the search space to below 2 .
Suppose each key in the search space is checked by applying it once in a point
multiplication – some 286.5 point operations, each containing 18 field multiplications. With 32-bit arithmetic, MMM requires 6×(1+6×2) = 78 native machine
multiplications. Thus, about 219 muls are required per key, giving a time complexity of O(275 ) machine multiplications to break one member of the sample ofSimple Power Analysis of Unified Code201

512 P-192 signings/decryptions. This is probably not yet computationally feasibility at O(218 ) Pentium R IV years, although it could be distributed easily overa number of machines. However, ...

9Worked Examples

This section provides more detail for a typical P-192 attack and assesses theimpact of changing various parameters. In particular, the attacker invariably
chooses very much better examples than those of the previous section, showingthat the attack is, in fact, already feasible. Sequences of conditional subtractions
were simulated using equations (3)–(5) and continuous mathematics on randomly
generated keys k and inputs P . Different sized samples were generated and one
member selected to:minimize the number of point operations which were not distinguishable
as additions by virtue of the conditional subtractions, nor distinguishable
as doublings by adjacency to a known addition.
Table 1 shows the initial few bits, point operations, conditional subtractions
and deductions for a typical example selected using this criterion. There is one
column for each point add (A) or double (D). The penultimate row records differences (marked Y) within the first or the second pair of subtractions. These are
all adds and the final row extends this to include the doubles on either side of aknown add. The attacker computes this for each signature, and chooses the one
with the fewest unknowns (marked *) in the last line.
1 1 1 1 1 1 1 100 100 100 100 1 1 100 1 1 1 1 10 1 10 1 1 1 1 1 1
Key
Pt Opn DADADADADADADADDDADDDADDDADDDADADADDDADADADADADDADADDADADADADADA
u1 subn 0101100000010101000011001100010101010001010000001000101000001100
u2 subn 0100100101000001010011001000000100010000000000000000111000011101
s1 subn 0000101111000010001110010100001111000000100011000100001000100000
s2 subn 0100101011010110001110010100011010000101100111001110011000110001
DiffnceY Y
Y Y Y YYYY Y Y
Y Y Y YY Y YYYKnown YYYYY*YYYYYYYYY*YYY*****YYY*YYYYYYY*YYYYYYYYY**YYYYYYYY***YYY*YYTable 1. Example Deductions of Operation Types
Table 2 shows how the average number of undetermined operations in theselected sequence varies according to the sample size from which it is taken.
The most significant benefit from larger samples is the decrease in the total
number of indeterminate operations. The undetermined point additions, α innumber, must be chosen from the undetermined operations, τ in number. The
number of such combinations is given lower in the table. The longer substringsof unknown operations have more pattern restrictions. The average factor bywhich this cuts the search space is given in the penultimate line, and the lastline presents the resultant overall order of the search space. The computational
effort is this multiplied by the work involved in verifying a single key.

202

C.D. Walter
P-192

Sample Size

32

64

128

256

512

1024

Total Ops
292.5 293.7 294.8 295.9 296.9 297.9
Unknown Ops (τ )
54.4
49.2
44.4
40.0
36.2
32.7
Unknown Adds (α)
22.4
21.4
20.4
19.9
19.2
18.7
Unknown 1-strings
11.2
11.5
11.7
11.7
11.9
12.2
Unknown 2-strings
7.1
7.1
7.1
7.2
7.2
7.0
Unknown 3-strings
4.6
4.5
4.5
4.5
4.4
4.1
Unknown 4-strings
3.0
2.9
2.8
2.7
2.6
2.6
1.9
1.8
1.8
1.7
1.6
1.4
Unknown 5-strings
Longer unknown strings
3.5
3.1
2.8
2.6
2.4
2.4

τ
Combinations α
250 245.5 241.1 237.0 233.2 229.4
Substring restrictions
219
218
217 216.2 215.6 215.0
31
27.5
24.1
Search Space Order222
220.8 217.6 214.4

Table 2. Average Numbers of Operations in the selected Point Multiplication.
The figures make it clear that the criterion just given for selecting the sidechannel trace is hugely more powerful than if an extremal initial point P wereused. For the sample size of 512, there is a reduction in workload by a factorof 238 . This means that the computational effort is reduced to O(236.6 ) native
multiplications, i.e. about a minute on a Pentium IV processor running at 232
cycles per second. This is certainly feasible for any back street attacker withaccess to suitable monitoring equipment, not just for government organisations.
Indeed, less than a week of computing reveals 1 in 32 keys.
The table also shows that twice as many keys can be extracted from a given
sample for about 10 times the effort – the easiest keys are found first, after which
they become steadily more difficult to find.
Key Length

192

224

256

384

521

Total Ops
296.9 345.7 394.2 588.4 795.7
Unknown Ops (τ )
36.2
45.9
55.7
96.3 141.6
Unknown Adds (α)
19.2
23.0
26.6
41.5
57.9

τ
Combinations α
233.2 242.8 252.4 291.4 2134.3
Substring restrictions 215.6 218.8 222.0 235.4 250.1
Search Space Order

217.6

224.0

230.4

256.0

284.2

Table 3. Search Space Sizes for Different Key Lengths (Sample of 512).

Finally, in Table 3 a comparison is made of the search spaces for the otherrecommended EC-DSA curve sizes5 . It would appear that it is still computationally feasible to attack some keys over fields as large as that of P-256.
5Here P r−n is assumed to be essentially 1. However, 521-bit numbers cannot be
partitioned into words of equal length without loss. So, for P-521, P r−n may not be
close to 1. This would result in many fewer final subtractions and so more unknown
operations than tabulated.

Simple Power Analysis of Unified Code

10

203

Conclusion

The clear conclusion is that, on its own, unified code for point operations provides insufficient security in some standard implementations of ECC which employ arithmetic hardware that is subject to side channel leakage. In particular,
we demonstrated the feasibility of attacking hardware that uses a time-varying
implementation of Montgomery modular multiplication with the Brier-Joye formulae for point addition [3].
Several easy counter-measures would defeat the attack. For example, it should
be possible to re-code the point evaluation to avoid repeated field operations
when a doubling occurs. The formulae of [7] and [8] avoid the problem, but havefield squares precisely when a doubling occurs – leaky hardware might still reveal
this. Alternatively, picking any other exponentiation algorithm than the standard
binary one may reduce or entirely eliminate the bias given in some decryptions
as a result of re-using an extremal input in every point addition. Thus, using
m-ary exponentiation with m > 2 would reduce the frequency of weak cases aswell as introducing ambiguities about which point addition is being performed.
Certainly, using a more leak-resistant multiplier would improve matters.
However, the three standard counter-measures listed by Coron [4] are insufficient here; they may make no difference or even make the attack more feasible.
Key blinding only helps if more than one decryption is required for key recovery.
Only one decryption was used here, but if side channel leakage is weak thenseveral decryptions with the same key could help to distinguish additions fromdoublings with enough certainty for it to be computationally feasible to search
the key space. So this counter-measure might ameliorate the situation, although
not solve it. Message blinding only helps against chosen ciphertext attacks, butthat was not required here. Indeed, the third counter-measure of randomizing the
input point coordinates may help the attack to succeed by guaranteeing a uniform distribution of coordinate values which will contain the necessary examplesof attackable extremal points.
Previously it was uncertain that time variation was a serious threat except
when unblinded keys were used at least several hundred times in an embedded
cryptographic device [19]. Now it is clear that constant time modular multiplication is essential for security even when secret keys are always blinded.

References
1. Portable data carrier including a microprocessor, Patent no. 4211919 (Abstract),
US Patent and Trademark Office, July 8, 1980.
2. Digital Signature Standard (DSS), FIPS PUB 186-2 (Appendix 6), U.S. National
Institute of Standards and Technology, 27 Jan 2000.
3. E. Brier & M. Joye, Weierstraß Elliptic Curves and Side-Channel Attacks, Public
Key Cryptography (Proc. PKC 2002), D. Naccache & P. Paillier (editors), LNCS
2274, Springer-Verlag, 2002, pp. 335–345.
4. J.-S. Coron, Resistance against Differential Power Analysis for Elliptic Curve
Cryptosystems, Cryptographic Hardware and Embedded Systems (Proc. CHES99), C. Paar & Ç. Koç (editors), LNCS 1717, Springer-Verlag, 1999, pp. 292–302.

204

C.D. Walter

5. J.-F. Dhem, F. Koeune, P.-A. Leroux, P. Mestré, J.-J. Quisquater & J.-L. Willems,
A practical implementation of the Timing Attack, Proc. CARDIS 1998, J.-J.
Quisquater & B. Schneier (editors), LNCS 1820, Springer-Verlag, 2000, pp. 175–
190.
6. K. Gandolfi, C. Mourtel & F. Olivier, Electromagnetic Analysis: Concrete Results,
Cryptographic Hardware and Embedded Systems – CHES 2001, Ç. Koç, D. Naccache & C. Paar (editors), LNCS 2162, Springer-Verlag, 2001, pp. 251–261.
7. C. Gebotys & R. Gebotys, Secure Elliptic Curve Implementations: An Analysis
of Resistance to Power-Attacks in a DSP Processor, Cryptographic Hardware andEmbedded Systems – CHES 2002, B. Kaliski, Ç. Koç & C. Paar (editors), LNCS
2523, Springer-Verlag, 2003, pp. 114–128.
8. M. Joye & J.-J. Quisquater, Hessian Elliptic Curves and Side Channel Attacks,
Cryptographic Hardware and Embedded Systems – CHES 2001, Ç. Koç, D. Naccache & C. Paar (editors), LNCS 2162, Springer-Verlag, 2001, pp. 402–410.
9. N. Koblitz, Elliptic Curve Cryptosystems, Mathematics of Computation 48, 1987,
pp. 203–209.
10. P. Kocher, Timing attack on implementations of Diffie-Hellman, RSA, DSS, andother systems, Advances in Cryptology – Crypto ’96, N. Koblitz (editor), LNCS
1109, Springer-Verlag, 1996, pp. 104–113.
11. P. Kocher, J. Jaffe & B. Jun, Differential Power Analysis, Advances in Cryptology– Crypto ’99, M. Wiener (editor), LNCS 1666, Springer-Verlag, 1999, pp. 388–
397.
12. P.-Y. Liardet & N. P. Smart, Preventing SPA/DPA in ECC Systems using theJacobi Form, Cryptographic Hardware and Embedded Systems – CHES 2001, Ç.
Koç, D. Naccache & C. Paar (editors), LNCS 2162, Springer-Verlag, 2001, pp.
391–401.
13. V. Miller, Use of Elliptic Curves in Cryptography, Advances in Cryptology –Crypto ’85, H. C. Williams (editor), LNCS 218, Springer-Verlag, 1986, pp. 417–
426.
14. P. L. Montgomery, Modular Multiplication without Trial Division, Mathematics ofComputation 44, no. 170, 1985, pp. 519–521.
15. J.-J. Quisquater & D. Samyde, ElectroMagnetic Analysis (EMA): Measures andCounter-Measures for Smart Cards, Smart Card Programming and Security (Proc.
e-Smart 2001), I. Attali & T. Jensen (editors), LNCS 2140, Springer-Verlag, 2001,
pp. 200–210.
16. W. Schindler, A Combined Timing and Power Attack, Public Key Cryptography(Proc. PKC 2002), P. Paillier & D. Naccache (editors), LNCS 2274, SpringerVerlag, 2002, pp. 263–279.
17. W. Schindler & C. D. Walter, More detail for a Combined Timing and Power
Attack against Implementations of RSA, Cryptography and Coding, K.G. Paterson(editor), LNCS 2898, Springer-Verlag, 2003, pp. 245–263.
18. C. D. Walter, Precise Bounds for Montgomery Modular Multiplication and Some
Potentially Insecure RSA Moduli, Topics in Cryptology – CT-RSA 2002, B. Preneel(editor), LNCS 2271, Springer-Verlag, 2002, pp. 30–39.
19. C. D. Walter & S. Thompson, Distinguishing Exponent Digits by Observing Modular Subtractions, Topics in Cryptology – CT-RSA 2001, D. Naccache (editor),
LNCS 2020, Springer-Verlag, 2001, pp. 192–207.
20. C. D. Walter, Sliding Windows succumbs to Big Mac Attack, Cryptographic Hardware and Embedded Systems – CHES 2001, Ç. Koç, D. Naccache & C. Paar
(editors), LNCS 2162, Springer-Verlag, 2001, pp. 286–299.