Issues of Se urity with the Oswald-Aigner
Exponentiation Algorithm

Colin D. Walter
Comodo Resear h Lab
10 Hey Street, Bradford, BD7 1DQ, UK

Colin.Walter omodogroup. om

www. omodogroup. om

Abstra t. In smart ard en ryption and signature appli ations, randomized algorithms an be used to in rease tamper resistan e against atta ks
based on averaging data-dependent power or EMR variations. Oswald
and Aigner des ribe su h an algorithm for point multipli ation in ellipti urve ryptography (ECC). Assuming an atta ker an identify anddistinguish additions and doublings during a single point multipli ation,
it is shown that the algorithm is inse ure for repeated use of the same seret key without blinding of that key. Thus blinding should still be usedor great are taken to minimise the di eren es between point additions
and doublings.

Addition-subtra tion hains, randomized exponentiation,
ellipti urve ryptography, ECC, point multipli ation, power analysis,
SPA, DPA, SEMA, DEMA, blinding, smart ard.
Key words:

1 Introdu tion
Side hannel atta ks [6, 7℄ on embedded ryptographi systems show that substantial data about se ret keys an leak from a single appli ation of a ryptographi fun tion through data-dependent power variation and ele tro-magneti
radiation [12, 13℄. This is parti ularly true for rypto-systems whi h use theomputationally expensive fun tion of exponentiation, su h as RSA, ECC andDiÆe-Hellman. Early atta ks required averaging over a number of exponentiations [9℄ to extra t meaningful data, but improved te hniques mean that single
exponentiations using traditional algorithms may be inse ure. In parti ular, it
should be assumed that the pattern of squares and multiplies an be extra ted
fairly a urately from side hannel leakage, perhaps by using Hamming weights
to identify operand re-use. Where the standard binary \square-and-multiply"
algorithm is used, this pattern reveals the se ret exponent immediately.
In this ontext, Oswald and Aigner proposed a randomized point multipli ation algorithm [10℄ for whi h there is no bije tion between s alar key values andsequen es of urve operations. They randomly swit h to a di erent pro edure
for whi h multipli ations appear to o ur instead for zero bits but not for one
bits. This alternative orresponds to a standard re oding of the input bits toremove long sequen es of 1s and introdu es other non-zero digits su h as 1. On

C. D. Walter, The Oswald-Aigner Exponentiation Algorithm

209

the one hand, the pattern of squares and multipli ations is no longer xed, sothat averaging power tra es from several exponentiations does not make sense,
and, on the other hand, there is ambiguity about whi h digit value is asso iatedwith ea h multipli ation.
This arti le analyses the set of randomized tra es that would be generated byrepeated re-use of the same unblinded key k . By aligning orresponding doublings
in a number of tra es, the possible operation sequen es asso iated with bit pairs
and bit triples of the se ret key k an be extra ted. With only a few tra es(ten or so) this provides enough information to determine half the bits of kunequivo ally, and the rest with a very high degree of ertainty.
Previous work in this area in ludes [11℄ and [14℄. In [11℄ Oswald takes a similar
but deterministi algorithm and shows how to determine a spa e of possible keys
from one sequen e of urve operations, but not how to ombine su h resultsfrom di erent sequen es. Here randomization minimises the inter-dependen e
between onse utive operations and so it is un lear whether or not her te hniqueslead to an intra table amount of omputing. Okeya & Sakurai [14℄ treat thesimple version of the randomized algorithm and su eed in ombining resultsfrom di erent multipli ations by the same key. They require the key k to be reused 100+ log2 k times. Here we treat the more omplex version of the algorithm
in an extended form whi h might in rease se urity. The analysis of Okeya &Sakurai is inappli able here be ause it depends on a xed nite automaton stateo urring after pro essing a zero bit. However, using new methods we nd that a)measurements from only O(10) uses of the se ret key reveal the key by applying
theory whi h onsiders pairs of bits at a time, b) software whi h onsiders longer
sequen es of bits an pro ess just two uses to obtain the key in O(log k ) time,and ) for standard key lengths and perfe t identi ation of adds and doubles,a single use will dis lose the key in a tra table amount of time. In addition, ouratta k seems less sus eptible to error: key bits are dedu ed independently sothat any in orre t dedu tions a e t at most the neighbouring one or two bits.
In omparison, the atta k of Okeya & Sakurai re overs bits sequentially, making
re overy from errors more omplex.
Although only one algorithm is studied here, a similar overall approa h an
be used to break most randomized re oding pro edures under the same onditions. The two main properties required are: i) after a given sequen e of point
operations, the unpro essed part k 0 of the key an only have one of a small,bounded number of possible values (determined from k by the length of theoperation sequen e but independent of other hoi es); and ii) it is possible toidentify an asso iated subset of tra e suÆxes for whi h all members orrespondto the same value of k 0 . These also hold for the algorithm proposed by Liardet& Smart [8℄, whi h uses a sliding window of random, variable width. They seemto be the key properties required in [16℄ to demonstrate similar weaknesses inthat algorithm.
Several ounter-measures exist against this type of atta k. As well as standard blinding by adding a random multiple of the group order to the exponent,

210

CT-RSA 2004, LNCS 2964, pp. 208{221,Springer-Verlag, 2004

di erent algorithms an be employed, su h as [3, 5℄. Moreover, formulae for point
additions and doublings an be made indistinguishable [1, 2, 4, 8℄.

2 The Oswald-Aigner Exponentiation Algorithm
This se tion ontains a brief outline of the Oswald-Aigner algorithm [10℄ in termsof the additive group of points on an ellipti urve E . Rational integers are
written in lower ase while points on the urve are written in apitals and Greekhara ters denote probabilities. The algorithm omputes the point P = kQ for
a given positive integer k (the se ret key) and a given point Q on E .
     

 



 
  

 
 
 

Fig. 1.

        
 





 
     
 

Finite automaton for an extension of the algorithm. rb is a random bit.

The algorithm randomly introdu es alternative re- odings to the representation of k . It an be viewed as pre-pro essing bits of k from right to left into a
new digit set f 1; 0; +1; +2g. Then the resulting s heme for point multipli ation
an be performed in either dire tion. The onversion uses a arry bit set initiallyto 0. When this bit is summed with the urrent bit of k , the result 0, 1 or 2 an
be re- oded in di erent ways: 0 always gives a new digit 0 with arry 0; 1 angive either new digit 1 and arry 0, or new digit 1 with arry 1; and 2 gives either
new digit 0 and arry 1, or new digit 2 and arry 0. Fig. 1 illustrates this as anite automaton for a slight extension of the original right-to-left algorithm. It
has 4 states, numbered 0 to 3 with the arry being 1 if, and only if, the state is
2. For the transition from state 2 to state 1, the normal order of doubling andadding is reversed. This a hieves the pro essing for digit value 2. The extension
here allows a new transition from state 0 to state 2; the original algorithm is theC. D. Walter, The Oswald-Aigner Exponentiation Algorithm211

spe ial ase in whi h the random bit rb = 1 always for state 0. The extension
also allows the random bits to be biased for ea h state. However, if the same distribution of random bits is used for ea h of the states 0, 1 and 3, the automaton
simpli es to just two states, obtained by merging states 0, 1 and 3.
Figure 2 provides equivalent ode for the asso iated right-to-left point multipli ation. A left-to-right version is also possible, and an be atta ked in the same
way.
P
O;
/* O is the zero of the ellipti urve */
State
0 ;
While k > 0 do{
If (k mod 2) = 0 thenase State of{
0,1,3 : Q
2Q ; State
0 ;
2
: P
P+Q ; Q
2Q ; State
3 ;
}
else
ase State of{
0,1,3 : If rb = 0 then/* rb is a Random Bit */{ P
P-Q ; Q
2Q ; State
2 }
else
{ P
P+Q ; Q
2Q ; State1 } ;2: If rb = 0 then/* rb is a Random Bit */{ Q
2Q ; P
P+Q ; State
1 }
else
{ Q
2Q } ;} ;kk div 2 ;} ;If State = 2 then P
P+Q ;Fig. 2.

Oswald & Aigner's randomized signed binary exponentiation (extended).

3 EÆ ien y Considerations
De nition 1. Let, ,and Æ be the probabilities that the random bit rb ishosen to be 1 when the urrent state is 0, 1, 2 or 3 respe tively.

These probabilities an be hosen to improve eÆ ien y or, as we shall see, se urity. For a key k whose bits are sele ted independently and at random from a
uniform distribution, the matrix of transition probabilities between states of the

212

CT-RSA 2004, LNCS 2964, pp. 208{221,automaton is then

Springer-Verlag, 2004

3
2
1 1 0 1
2 2
2 7
6
6
1
Æ 7
6
2 2 2 2 7761
65
4 1 2 2 2 12Æ 7
0

0

1
2

0

Lemma 1. The transition matrix has an eigen-ve tor ( 12 ; 21 2, 2; ) where = 12 2 2 4 4 +2Æ . Its elements are the probabilities asso iated with ea h state.
Moreover, 0    41 .
This is an easy exer ise for the reader. Taking the dot produ t of this eigenve tor with the ve tor ( 12 ; 21 ; 1 12 ; 21 ) of average additions asso iated with ea hstate provides the expe ted number of additions per bit: 12 +(1 ). The numberof doublings is onstant at one per bit. So, to minimise the total time we require(1 ) = 0, i.e. (1 )(2) = 0, i.e. disallow either the transition from state
2 ba k to state 1, or both transitions to state 2 from states 0 and 1. Avoiding these
extremes provides greater randomness. In parti ular, and/or should be kept
away from 1 so that states 2 and 3 are rea hable. In the limit as
Æ!1 (whi h
optimises eÆ ien y), on average there is half an addition per bit of k . Thus, atypi al addition hain has a little over 21 log2 k additions (or subtra tions). Evena modest bias towards eÆ ien y, su h as taking = = = Æ  34 , hanges
this by just 2% or less.

4 The Atta k
4.1 Initial Hypotheses, Notation & Overview of the Atta k
The atta k here assumes suÆ iently good monitoring equipment and a suÆiently weak implementation. Spe i ally it is assumed that:{ Adds and doublings an always be identi ed and distinguished orre tly inside hannel leakage from a single point multipli ation; and{ Side hannel tra es are available for a number of di erent uses of the same,
unblinded key value.

For ease in al ulating probabilities, we assume adds and doublings an always
be distinguished. Similar results hold if this is only usually the ase. By the rst
hypothesis,{ every side- hannel tra e tr an be viewed as a word over the alphabet fA; Dg
where A denotes the o urren e of an addition and D that of a doubling. Here, as
expe ted, the tra e is written with time in reasing from left to right. However,this is the opposite of the binary representation of the se ret key k whi h is
pro essed from right to left, so that the re- oding an be done on the y (Fig. 2).
For example, if the ma hine were to y le round only states 0 and 1 giving theC. D. Walter, The Oswald-Aigner Exponentiation Algorithm

213

sequen e of operations for square-and-multiply exponentiation, then the tra e
would be essentially the same as the binary, but reversed: every o urren e of
0 would appear as D, and every o urren e of 1 would appear as AD. So thebinary representation 11001 would generate the tra e ADDDADAD. There is
one D for every bit, and we index them to orrespond:

De nition 2. The position of an instan e of D in a tra e is the number ofurren es of D to its left.

oThus, the leftmost D of ADDDADAD has position 0 and arises from pro essing
the rightmost bit of 11001, whi h has index 0.
The atta k onsists of a systemati treatment of observations like the following. The only transition whi h pla es D before rather than after an asso iatedo urren e of A is the transition (21). Hen e, every o urren e of the substring
DAAD in a tra e tr orresponds to traversing transition (21) then (12) or (11) in
the nite automaton. This must orrespond to pro essing a bit 1 to rea h state
2, and then two further 1 bits. The tra e an be split between the two adja ent
As into a pre x and a suÆx. There is a orresponding split in the binary representation of the se ret key k su h that the suÆx of k has a number of bits equal
to the number of Ds in the pre x of tr. This enables the position of the substring
111 to be determined in k . Moreover, by the next lemma, most o urren es of
111 an be lo ated in this way if enough tra es are available: DAAD appears
exa tly when the middle 1 is represented by the transition (21).

Lemma 2. If 11 o urs in the binary representation of k then the probabilityof the left-hand 1 being represented by transition (21) in a tra e for k is  =4(1 ).
Proof. 4 is the probability of being in state 2 as a result of the right-hand 1

and 1

is the (independent) probability of sele ting transition (21) next.

ut

4.2 Properties of the Tra es
Figure 3 lists the transitions and operation sequen es whi h an o ur for ea h
bit pair, in luding the probability of ea h. It assumes that initial states have theprobabilities determined by Lemma 1, and that neighbouring bits are unknown.
The gure enables one to see whi h bit pairs an arise from given patterns in a
tra e, and to al ulate their probabilities:

Lemma 3. Let ki denote the bit of k with index i, and  be as in Lemma 1.

Then,i) For a given tra e, if the Ds in positions i and i+1 are not separated by any
As, then the bit pair ki+1 ki is 00 with probability (2 2(1 )) 1 , whi h is atleast 21 . If the Ds are separated by one or more As in any tra e, then the bit pairis ertainly not 00.

ii) For a given tra e, if the Ds in positions i and i+1 are separated by one A,
then the bit pair ki+1 ki is 10 with probability 12 . If the Ds are separated by noCT-RSA 2004, LNCS 2964, pp. 208{221,214

Springer-Verlag, 2004

As or two As in any tra e, then the bit pair is ertainly not 10.
iii) For a given tra e, if the Ds in positions i and i+1 are separated by two As,
then the bit pair ki+1 ki is ertainly 11. The probability of two As when the bitpair is 11 is 2(1), assuming bit ki 1 is unknown.
iv) For a set of n tra es, suppose the Ds in positions i and i+1 are separated by

no As in some ases, by one A in some ases, and by two As in no ases. Thenthe bit pair ki+1 ki is 01 with probability (1+(1 2(1))n ) 1 .

Bit
P air
00
10

01

11

Operation
State
P robabilities;
P atterns
Sequen es
given the bit pair
D:D000; 100; 300
1 2
AD:D
230
2
1
D:AD
001; 002
2 
1
D:AD
101; 1022 2
AD:AD231; 232
2
D:AD
301; 3021
AD:D; AD:AD
010; 023( 2 ) ; ( 21 )(1 )AD:D; AD:AD
110; 123( 21 2) ; ( 12 2)(1 )DA:D; D:AD
210; 223
2(1 ); 2
AD:D; AD:AD
310; 323
Æ; (1 Æ )1
AD:AD; AD:AD 011; 012( 2 ) ; ( 12 ) (1 )1
AD:DA; AD:D
021; 022( 2 )(1 )(1 ); ( 21 )(1 )AD:AD; AD:AD 111; 112( 21 2) 2 ; ( 21 2) (1 )AD:DA; AD:D
121; 122 ( 12 2)(1 )(1 ); ( 21 2)(1 )DA:AD; DA:AD 211; 212
2(1 ) ; 2(1 )(1 )D:DA; D:D
221; 222
2 (1 ); 2 2
AD:AD; AD:AD 311; 312Æ ; Æ (1 )AD:DA; AD:D
321; 322
(1 Æ )(1 ); (1 Æ )Fig. 3. All possible operation sequen es for all bit pairs, and their probabilities given
the bit pair o urs. (Bit pairs are pro essed right to left and operations left to right.)

Proof. i) First, by inspe tion of the nite automaton, the only possible operation sequen es for 00 are ADD and DD. So the Ds are always adja ent. Theintervention of an A will prove that the bit pair is not 00.
Suppose there is no intervening A between the two spe i ed Ds. Using Figure
3, if the bit pair is 00 then the probability of this is 00 = 1; if the bit pair is
10 then the probability is 10 = 0; if the bit pair is 01 then the probability is01 = ( 12 ) +( 21 2) +Æ; and if the bit pair is 11 then the probability is11 = ( 12 )(1 )+( 21 2)(1 )+ 2 +(1 Æ). Thus, the orre t dedu tionof 00 is made with probability00 =(00 +10 +01 +11 ) = 1=(2 2(1 ))  21 .

C. D. Walter, The Oswald-Aigner Exponentiation Algorithm

215ii) Similarly, from Figure 3 the bit pair 10 must always in lude the operation A
on e between the two o urren es of D, but this is not the ase for any otherbit pair. Thus the absen e of an A, or the presen e of two As, guarantees the bitpair is not 10. However, suppose there is exa tly one A between the spe i ed Ds.
0 = 1 00 = 0;
By Figure 3, if the bit pair is 00 then the probability of this is 00
0
if the bit pair is 10 then the probability is 10 = 1 10 = 1; if the bit pair
0 = 1 01 ; and if the bit pair is 11 then theis 01 then the probability is 01
0
probability is 11 = 1 11 2(1 ). Thus, the orre t dedu tion of 10 is madewith probability
0 =(00
0 +100 +01
0 +110 ) = 1.
102iii) This part is immediate from Figure 3.
iv) Finally, by parts (i) and (ii), a bit pair whi h in ludes both the possibilities
of no As and of one A between the spe i ed Ds annot be 00 or 10; it must be
01 or 11. The probability of not having two As in any tra e when the digit pairis 01 is 1, of ourse. By Fig. 3 the probability of not having two As in any of then tra es when the digit pair is 11 is n = (1 2(1 ))n . Hen e the probabilityof the pair being 01 rather than 11 is 1=(1+n ).
ut
We must be a little areful in the appli ation of this lemma. Firstly, ea hpart assumes no knowledge of bit ki 1 . Knowing it hanges the probabilities.
In most ases, the di eren es are small enough to be onsidered negligible; fora urate gures the table an be used to sele t just the ases starting in states
0 or 3 when the pre eding pro essed bit is 0, and the ases starting in states 1
or 2 when that bit is 1. The only ase where a qualitative di eren e o urs isfor 11 when AA only o urs if ki 1 = 1. In the ase of ki 1 = 0 this means weannot distinguish 01 from 11 so easily. This is a typi al problem to solve whenre onstru ting the whole key.
Se ondly, dedu tions from di erent tra es are not independent. For example,
suppose all of n tra es have one A between the Ds in positions i and i+1. From(ii) of the lemma it is tempting to dedu e that the bit pair is 10 with probability
1 ( 12 )n . However, the probability of this may still only be 21 . In parti ular, thishappens when the parameters = = Æ = 0 are sele ted. Then the bit pairs 10
and 01 would always have exa tly one A between the Ds, and bit pairs 00 and 11
would never have any As. So 01 and 10 would be equally likely with probability
1
2 if exa tly one A always o urred. The independent de isions whi h an beombined are those based on the independent hoi es of random bits, as in (iv).

4.3 Re onstru ting the Key
For this se tion we assume the default values whi h give the original algorithm,
1 . Later we onsider
namely = 1 and = = Æ = 12 . This means  = 14
alternatives whi h might improve se urity. Then Figure 3 immediately yields:

Lemma 4. For the above default values of the parameters,i) the bit pair 01 has no intervening A between the asso iated Ds of a tra e with
9 and one intervening A with probability 5 ;probability 14
14

216

CT-RSA 2004, LNCS 2964, pp. 208{221,Springer-Verlag, 2004ii) the bit pair 11 has no intervening A between the asso iated Ds with probability
29
1
7 , one intervening A with probability 14 , and two As with probability 14 .

The hoi es whi h lead to the probabilities in the previous lemma are madeindependently for ea h tra e. Hen e, for n tra es and a pair 01, there are no As9 )n and one A in every tra e with probability
in every tra e with probability ( 145n
( 14 ) . A similar result holds for the pair 11. By averaging:

Lemma 5. For the default values of the parameters and n tra es, in every tra ea bit pair of the form 1 has:i) no As between the asso iated Ds with probability5 )n + ( 9 )n =2.
ii) one A with probability ( 14
14

f

g

f( 149 )n + ( 27 )n g=2 ; andTo re onstru t the key k , rst lassify every bit pair as 00 if there are nointervening As in any tra e, 10 if there is always one intervening A, 11 if there isan intervening AA, and, otherwise, 1 if there is a variable number of intervening
As. This orre tly lassi es all pairs 00 and 10, and pairs lassed as 11 or 1 are
ertainly all 11 or of the form 1 respe tively. For n = 10 both probabilities in9 )10  1=166. Thus about 1 in 83 bits pairs
the lemma are bounded above by 21 ( 1401 and 11 will be in orre tly lassi ed as 00 or 10. Also, by the next lemma,
1 ( 76 )10 > 34 of pairs 11 will be lo ated orre tly by o urren es of AA when
they are the left pair in triplets 111. The proof of it goes ba k to Lemma 2.

Lemma 6. For the default values of the parameters and n tra es, the bit pair

11 has at least one tra e exhibiting AA with probability 1 ( 67 )n if it has a 1 to
the right and with probability 0 if it has a 0 to the right.
This is now enough information to dedu e almost all the bits of a standard
length ECC key. Every bit whi h is dedu ed as the right member of a pair 1 isorre tly lassi ed as 1 sin e the mixture of patterns used in the lassi ation
is not possible for pairs of the form 0. However, about 1 in 83+1 of the bits
whi h are dedu ed to be right members of a pair 0 is in orre tly lassi ed as 0
be ause not all the possible patterns for the bit pair have o urred. In an ECC
key of, say, 192 bits, about two bits will then be in orre t.
Ea h bit b belongs to two pairs: b and b, say. Tra es for the pair b havebeen used to lassify b. In half of all ases, there is a 0 bit to the right andthe hara teristi patterns of tra es for the pair b0 an be used to ross- he k
the lassi ation. In the other half of ases the patterns for b1 also indi ate theorre t value for b as a result of the ratios between the numbers of o urren esof ea h pattern. However, the patterns observed for overlapping bit pairs are notindependent. Although unlikely, one set of patterns may reinfor e rather thanontradi t a wrong dedu tion from the other set. There is no spa e for further
detail, but the following is now lear:

Theorem 1. Suppose ellipti

urve adds and doubles an be distinguished a urately on a side hannel. If the original Oswald-Aigner exponentiation algorithm
is used with the same unblinded 192-bit ECC key k for 10 point multipli ations
then approximately half the bits an be dedu ed unambiguously to be 1, and theremaining bits dedu ed to be 0 with an average of at most about two errors.

C. D. Walter, The Oswald-Aigner Exponentiation Algorithm

217

This theorem says that a typi al ECC se ret key an usually be re overed ona rst attempt using a dozen tra es with very little omputational e ort beyond
extra ting the add and double patterns from ea h tra e. By he king onsisten y
between dedu tions of overlapping bit pairs, most errors should be eliminated.
However, it is omputationally feasible to test all variants of the dedu ed key for
up to two or three errors. The orre t one from this set an surely be establishedby su essfully de rypting some iphertext.

4.4 Se ure Parameter Choi es?
From the last se tion, it is lear that greater se urity ould only arise frommaking it less easy to distinguish between pairs of the form 0 and those of theform 1. This requires hoosing parameters for whi h 01 and 11 are less likely
to exhibit both no As and one A between the relevant Ds. From Fig. 3, theprobability of no As for 01 and the probability of one A for 11 are the same, viz.
 = ( 21 ) + ( 21 2) + Æ:So this must be made lose to 0 or lose to 1. For example, hoosing == 1 makes  = 0 and so  = 1, whereas hoosing = = Æ = 0 makes
 = 0. Thus both limits are possible. In general, for  = 1 (the rst ase) thetra es mat h the pattern of operations for normal square-and-multiply, so weexpe t ea h A to orrespond to the multiply of a 1 bit. Although 00 and 01 areindistinguishable from the patterns, and 10 and 11 are indistinguishable (unlessperhaps AA ould o ur), the atta ker now re ognises that patterns for the pairs0 have no intervening A and patterns for the pairs 1 have one intervening A.
This gives him ea h bit unequivo ally. At the opposite extreme, if  = 0 (these ond ase) then 10 and 01 be ome indistinguishable from the patterns as do
00 and 11 (again, unless perhaps AA ould o ur). Now the atta ker re ognises
pairs with equal bits from pairs with di erent bits. Knowing the rst bit is 1, hean dedu e all the bits one by one from left to right, and hen e the key k .
In general the atta ker an exploit the omplementary frequen ies of one A
for the pairs 01 and 11. Either they are lose enough to ensure n tra es usuallydisplay both patterns (as in the previous se tion) or they are distin t enough forthe patterns to be strongly biased in opposite dire tions in the tra e set (as in
the previous paragraph). He an then re ognise either the equality of the se ond
bits or the di eren e in the rst bit respe tively, and use the fa t that ea h bit
belongs to two pairs to ross- he k the dedu tion of many bits. Consequently,
there are no se ure hoi es of the parameters under repeated use of the unblinded
key k .
Identi al working to the previous se tion shows that similar omputations
an be performed for keys of any length. With the hoi e of parameters there,
the number of tra es needed to a hieve a spe i ed degree of on den e in thendetermined bits is n = O(log log k ) be ause we want at most one error in ( 149) =O(log k) bits. The same al ulations apply for any  whi h is not 0 or 1, giving
the same size order for n. For the working above in this se tion, mistakes are
only made when too many tra es re ord the opposite pattern to that expe ted

218

CT-RSA 2004, LNCS 2964, pp. 208{221,Springer-Verlag, 2004

from the value of  . Then, for  lose enough to 0 or 1, the same bound on thesize of n an be obtained for limiting the errors. So,

Theorem 2. No hoi e of algorithm parameters is se ure for a reasonable key
length under the above atta k if O((log k )2 ) de ipherings are omputationallyfeasible and O(log log k ) tra es are available from point multipli ations using thesame unblinded key.
When adds and doubles are not distinguished with 100% ertainty, the proportions of numbers of As an be used to assign a likelihood to the orre tnessof the sele ted bit pair. Those whi h are most likely to be wrong an be modi ed
rst, thereby de reasing the sear h time to determine the orre t key.

4.5 Counter-Measures

In the absen e of a se ure set of parameter hoi es, further ounter-measures are
required. The most obvious ounter-measure is to restore key blinding. A small
number of blinding bits might still result in the atta ker's desired 10 or so tra es
for the same key eventually be oming available. These might be identi ed easily
within a mu h larger set of tra es by the large number of hara ter subsequen es
shared between their tra es. So the size of the random number used in blinding
annot reasonably be less than the maximum lifespan of the key in terms of thenumber of point multipli ations for whi h it is used. Thus 16 or more bits areneeded, adding around 10% to the ost of point multipli ation.
Identi al formulae for additions and doublings are in reasingly eÆ ient andappli able to wider lasses of ellipti urves, those of Brier and Joye [1℄ in parti ular. These should make it more diÆ ult to distinguish adds from doubles.
Another favoured ounter-measure is the add-and-always-double approa h.
Then the pattern of adds and doubles is not key dependent. Ea h o urren eof DD has an add inserted to yield the pattern DAD, but the add output is
dis arded without having been used. This an also be done for the Oswald-Aigner
algorithm provided, in addition, an extra double is performed to onvert ea hDAAD into DADAD. The output of this double is likewise ignored.
Alternatives algorithms exist. That des ribed by Joye and Yen [5℄ is anotheradd-and-always-double algorithm. There are also several randomized methods [3,15℄ whi h seem to be more robust be ause they do not satisfy the two properties
identi ed in the introdu tion as those to whi h the above atta k an be applied.

5 One Tra e
It is interesting to spe ulate on how mu h data leaks from a single point multipli ation sin e the above ounter-measures should prevent re-use of identi alvalues for the same key. Oswald [10℄ noted that for some deterministi re- oding
algorithms in whi h several non-zero digits generate indistinguishable As, theoperation patterns resulting from numbers of up to 12 bits ould only represent
at most 3 keys. By breaking a standard ECC key into 12-bit se tions, this meansvery few keys a tually generate an observed patterns of operations. Moreover,C. D. Walter, The Oswald-Aigner Exponentiation Algorithm219

these an be ordered a ording to their likelihood of o urren e, and this onsiderably redu es the average sear h time for the orre t key. Hen e the key an
be re overed quite easily.
Is the same possible here? In [10℄ she also writes that the same atta k ispossible on randomized algorithms with weaker results, but provides no detail.
Randomized algorithms have mu h weaker inter-dependen ies between adja ent
operation patterns. This should substantially in rease the number of keys whi h
mat h a spe i pattern of point operations. The key Lemma 3 above does notprovide ertainty for many bits unless a number of tra es are available; only
the infrequent instan es of AA seem to allow de nite determination of any bitsfrom one tra e. Of ourse, an analysis of sub-sequen es of more than two bits ispossible, as in [14℄, but, besides better probabilities, this gives no further insight
into whether it is omputationally feasible to re over the key from a single tra e.
Instead, software was written to enumerate all the keys whi h ould represent
a given string. On average, for the extended version of thep algorithm, the trend
up to 16-bit keys indi ates learly that a little over O( 4 k ) keys will mat h agiven pattern { under 20 mat h a given 16-bit pattern. This would appear toensure the strength of the algorithm when a key is used just on e but only if the
key has at least 28 bits or there is onsiderable ambiguity in the side hannel
about whether the operations are adds or doubles. The original algorithm has
fewer random hoi es, and so has even fewer keys mat hing a given pattern.
Thus, a standard ECC key ould be re overed from a single tra e in feasible
time if adds and doubles are learly distinguishable.

6 Con lusion
One of several, similar, randomized exponentiation algorithms has been investigated to assess its strength against a side hannel atta k whi h an di erentiate
between ellipti urve point additions and point doublings. Straightforward theory shows that at most O(10) uses of the same unblinded key will enable a se ret
key of standard length to be re overed easily in a omputationally feasible time.
No hoi e of parameters improves se urity enough to alter this on lusion. Using
longer bit sequen es than the theory, it is also lear that software an sear hsu essfully for keys when just one side hannel tra e is available. However, thisnumber may need in reasing if adds and doubles might be onfused or standards
for key lengths are in reased.
The main property whi h is ommon to algorithms whi h an be atta ked
in this way seems to be that the next subsequen e of operations at a given
point in the pro essing of the key must be hosen from a small, bounded set of
possibilities whi h is derived from the key and the position, but is independentof previous hoi es. Hen e, our overall on lusion is that su h algorithms should
be avoided for repeated use of the same unblinded key if adds and doubles an
be di erentiated with any degree of ertainty. Furthermore, for typi al ECC key
lengths, a single use may be suÆ ient to dis lose the key when adds and doubles
are a urately distinguishable.

220

CT-RSA 2004, LNCS 2964, pp. 208{221,Springer-Verlag, 2004

Referen es
1. E. Brier & M. Joye, Weierstra Ellipti Curves and Side-Channel Atta ks, Publi
Key Cryptography, P. Paillier & D. Na a he (eds), LNCS 2274, Springer-Verlag,
2002, pp. 335{345.
2. C. Gebotys & R. Gebotys, Se ure Ellipti Curve Implementations: An Analysis ofResistan e to Power-Atta ks in a DSP Pro essor, CHES 2002, B. Kaliski, C. Ko
& C. Paar (eds), LNCS 2523, Springer-Verlag, 2003, pp. 114{128.
3. K. Itoh, J. Yajima, M. Takenaka & N. Torii, DPA Countermeasures by improving
the Window Method, CHES 2002, B. Kaliski, C. Ko & C. Paar (eds), LNCS 2523,
Springer-Verlag, 2003, pp. 303{317.
4. M. Joye & J.-J. Quisquater, Hessian Ellipti Curves and Side Channel Atta ks,
CHES 2001, C
 . Ko, D. Na a he & C. Paar (eds), LNCS 2162, Springer-Verlag,
2001, pp. 402{410.
5. M. Joye & S.-M. Yen, The Montgomery Powering Ladder, CHES 2002, B. Kaliski,C . Ko & C. Paar (eds), LNCS 2523, Springer-Verlag, 2003, pp. 291{302.
6. P. Ko her, Timing Atta k on Implementations of DiÆe-Hellman, RSA, DSS, andother Systems, Advan es in Cryptology { Crypto '96, N. Koblitz (ed), LNCS
1109, Springer-Verlag, 1996, pp. 104{113.
7. P. Ko her, J. Ja e & B. Jun, Di erential Power Analysis, Advan es in Cryptology{ Crypto '99, M. Wiener (ed), LNCS 1666, Springer-Verlag, 1999, pp. 388{397.
8. P.-Y. Liardet & N. P. Smart, Preventing SPA/DPA in ECC Systems using theJa obi Form, CHES 2001, C. Ko, D. Na a he & C. Paar (eds), LNCS 2162,
Springer-Verlag, 2001, pp. 391{401.
9. T. S. Messerges, E. A. Dabbish & R. H. Sloan, Power Analysis Atta ks of Modular
Exponentiation in Smart ards, Pro . CHES 99, C. Paar & C. Ko (eds), LNCS
1717, Springer-Verlag, 1999, pp. 144{157.
10. E. Oswald & M. Aigner, Randomized Addition-Subtra tion Chains as a Countermeasure against Power Atta ks, CHES 2001, C. Ko, D. Na a he & C. Paar (eds),
LNCS 2162, Springer-Verlag, 2001, pp. 39{50.
11. E. Oswald, Enhan ing Simple Power-Analysis Atta ks on Ellipti Curve Cryptosystems, CHES 2002, B. Kaliski, C. Ko & C. Paar (eds), LNCS 2523, SpringerVerlag, 2003, pp. 82{97.
12. J.-J. Quisquater & D. Samyde, Ele troMagneti Analysis (EMA): Measures andCounter-Measures for Smart Cards, Smart Card Programming and Se urity (eSmart 2001), I. Attali & T. Jensen (eds), LNCS 2140, Springer-Verlag, 2001, pp.
200{210.
13. J.-J. Quisquater & D. Samyde, Eddy urrent for Magneti Analysis with A tive Sensor, Pro . Smart Card Programming and Se urity (e-Smart 2002), Ni e,
September 2002, pp. 183{194.
14. K. Okeya & K. Sakurai, On Inse urity of the Side Channel Atta k Countermeasureusing Addition-Subtra tion Chains under Distinguishability between Addition andDoubling, Information Se urity and Priva y (ACISP 2002), L. Batten & J. Seberry(eds), LNCS 2384, Springer-Verlag, 2002, pp. 420{435.
15. C. D. Walter, MIST: An EÆ ient, Randomized Exponentiation Algorithm for
Resisting Power Analysis, Pro . CT-RSA 2002, B. Preneel (ed), LNCS 2271,
Springer-Verlag, 2002, pp. 53{66.
16. C. D. Walter, Breaking the Liardet-Smart Randomized Exponentiation Algorithm,
Pro . Cardis '02, San Jose, November 2002, Usenix Asso iation, Berkeley, 2002,
pp. 59{68.