Data Dependent Power Use in Multipliers
Colin D. Walter
Comodo Research Laboratory,
7 Campus Road, Bradford, BD7 1HR, UK

David Samyde
FemtoNano,Parise-mail: Colin.Walter@comodo.com

e-mail: David.Samyde@FemtoNano.com

Abstract
Recent research has demonstrated the vulnerability ofcertain smart card architectures to power and electromagnetic analysis when multiplier operations are insufficiently shielded from external monitoring. Here several
standard multipliers are investigated in more detail in order to provide the foundation for understanding potential
weaknesses and enabling the subsequent successful repairof those systems. A model is built which accurately predicts
power use as a function of the Hamming weights of inputs
without the combinatorial explosion of exhaustive simulation. This confirms that power use is indeed data dependent at least for those multipliers. Laboratory experiments
confirm that EMR also corresponds closely to these power
predictions over a wide range of frequencies.
Key Words — Differential power analysis, DPA, EMA,
smart card, multiplication, multiplier, RSA cryptosystem.

1 Introduction
Security is an increasingly important issue thesedays, even for computer arithmetic. Typical RSA [11]hardware performs long integer modular multiplications
 using a modification of the standard primary school method for multiplication where modular reductions are interleaved with the additions of digit multiples of the multiplicand. Normally this is done using a  bit multiplier to compute digit products   and   .
Because switching gates in a circuit requires more power
than keeping them in their current states, the amount of
power consumed during a multiplication is data dependent.
With sufficiently sensitive monitoring equipment, such variations can be observed and perhaps used to deduce properties of the data being processed. This is called power
analysis [6]. It has serious economic consequences if it can Work partly undertaken while the authors were at UCL Crypto Group(DICE), Université catholique de Louvain, Louvain-la-Neuve, Belgium.

be applied to attack an electronic purse on a smart card, asignature key on a credit card or rights keys on pay-perview cards. Electro-magnetic radiation (EMR) from thegate switching also leaks substantial information, especiallywhen conducted along power supply lines and network cables [1, 5, 9, 10]. With detectable radiation typically carrying 15 metres or more, this is a security problem not just for
smart cards, but particularly also for certificate authorities
that are frequently signing with private keys.
Some defences against such side channel leakage are
mentioned by Anderson [2], including dual rail logic andbus encryption [3], which may cure the most major sourceof data dependent power variation, namely the bus. Random transformations of inputs, random register re-location,
randomising algorithms, random noise generators, random
clock fluctuations and concurrent calculations on anotherprocessor are further methods used to blind calculations anddata movements so that recovery of secret keys becomes
more difficult during their deliberately limited lifespan.
Since they occupy a substantial part of most CPUs andcryptographic co-processors, multipliers now become oneof the strongest sources of data leakage which may need
protection. On a chip with no security measures and little
other than a multiplier, Sommer [7] observed a correlation
between power traces and values by looping through a particular cycle of values. Here power variations for several
standard multipliers are investigated. This confirms that attacks such as that in [12] should indeed be possible at least
for small multipliers. Complexity issues can be used toshow that larger multipliers are less vulnerable to such attacks, but different designs also vary in vulnerability.
The investigation was based initially on simulations
which computed gate switching activity in software models of some multipliers. Then several smartcard multipliers
were tested in order to confirm the predicted connection between power use and gate switching and verify that similar
properties held for EMR. This data agreed with the simulations, and so it is reasonable to conclude that the simulations predict what might be measured successfully andnon-invasively by EMR probes or RF scanning devices.

The problem with exhaustive simulations is combinatorial explosion:     for a  -bit multiplier as a resultof initialisation with two arguments followed by the   multiplication of two further arguments. For larger cases
which may be met in practice, less accurate random sampling must be performed. This prompts the need for more
efficient models to aid the design of less leaky hardware.
Often an attacker just needs information about the Hamming weight of arguments, as in [12], to recover a secretkey: the weights of individual digits are sufficient to identify re-use of long integer arguments in an exponentiation,and this may be enough to determine the precise operationsin the exponentiation scheme, and hence reveal the secretexponent used. So, for cases when Hamming weights are ofinterest, a model is constructed which predicts power use in
only    time. This is tailored to the precise constructionof the target multiplier to give very accurate results.
The model has to make a strong assumption to achieve
such a large reduction in computational complexity, namelythat certain groups of bits generated within the multiplier
have independent values. In reality this is far from the case,but the accuracy was still verifiable in two ways. First, themodel and simulation were compared for small multipliers. Then the model was compared with multipliers usedin practice by obtaining power and EMR traces in the laboratory. In both cases the results matched closely.
The main conclusions are: i) power use in standard multipliers is closely related to input Hamming weights; ii) the
simplifications described here enable fairly accurate modelsof power use to be constructed, so that designs can be tested
more easily in the search for less leaky hardware; and iii)
that some multiplier designs (such as one with binary Booth
re-coding) leak less information about Hamming weights
than others (such as the standard add-and-shift multiplier).





 

 



tracted to keep within any required bounds. The first assignment breaks down into a number of sequential multiplyaccumulate operations on digits with carry digit :Most smart card cryptographic processors make use of asingle, unpipelined  -bit multiplier, where typically 
although is becoming the norm. Then the long integers used in public-key cryptography are represented using
-bit digits. The RSA crypto-system uses modular exponentiation to encrypt, decrypt, sign and verify [11]. The
attacker’s aim is to recover the factorisation of the modulus
 or, equivalently, the secret decryption exponent.
The exponentiation is comprised of modular multiplications  which loop round the code:

 

 

 


 


 

 

 

(or a similar variation such as is given by Montgomery [8]).
Here holds the partial product,  is a digit of in base





 

(1)



The hardware for this leaks data which an attacker can
extract by observing variations in current or EMR. The
question here is whether or not he can determine the Hamming weight of  , say, by averaging over the  in (1) since,by [12], this would enable him to determine which multiis used in the exponentiation. With the standard
plier
square-and-multiply or -ary exponentiation methods, thiseasily leads to reconstruction of the secret exponent.
A significant complication is that power variation fromgate switching depends not just on the input data but also
on the initial state of the multiplier. Some technique, suchas averaging, is needed to remove such dependencies on
the initial state and other irrelevant inputs. The repeated
re-use of data in (1) provides just the opportunity for this.
The main problem faced by implementors is the removal ofsuch handles by which attackers are able to isolate useful
subsets of observations over which averaging proves productive: the handle used in [12] was based on the Hamming
weight of digits. So part of our interest here is in how averaged data from the multiplier determines Hamming weight.

3 Multiplier Simulation
Two software simulations of  -bit multipliers were builtwith variable  in order to verify empirical claims by previous authors that gate switching activity was related to theHamming weights of the inputs. The simulated circuits
were constructed from logic gates, -bit to -bit full adders(Fig. 1) and -bit half adders using a standard Wallace tree
configuration and carry-propagate adder. They followed the
add-and-shift model ([4], Fig. 3.1) and the binary Boothrecoding model ([4], Fig. 3.4). Pipelined multipliers were
not considered as they are too large for smart cards and simultaneous processing of several multiplications is likely
to mask much of the effect of interest here that designers
need to eliminate. (Indeed, pipelining may be an effective
counter-measure to power attacks on the multiplier.)
For convenience, we assume that the power consumed byswitching AND, OR and XOR gates is the same and identicalwhichever way they are switched. Then, to obtain a goodoverall picture, it suffices to count gates which are switchedwithout any weighting for different power use. So the number of gates switched between the registers was recorded,
but no term was included for switching within the registers,
nor any for the multiplexing of input bits which is required
to feed the initial AND gates. Such switching activity simply increases the strength of our conclusions. Furthermore,

2 Notation  , and  is the digit multiple of  which must be sub-the accumulation of the carry digit was ignored: it makes
little difference to the results except that further averaging
would be necessary to eliminate the variation caused by it.

 
 

Figure 1. A -bit Counter (Full Adder).

4 Gate Count Digit Order
Of interest here is the order of the digits according to thenumber of gates switched. We write    when the
average switched gate count (gc) for digit  is less thanthat for  in a specified situation. Not only was it verified
by the simulation that the (averaged) gate count is indeed
closely related to the Hamming weight of the argument, butmore detailed patterns emerged for the ordering of individual digits according to these gate switching counts.

 The Hamming Weight Principle: Let HW denotethe Hamming weight of a digit , i.e. the sum of its bits.
Then HW   HW  implies    .


Different constructions were tried corresponding to thedifferent groups of three bits which can be chosen for eachfull adder. Their effect on the simulation results were notusually substantial. So similar results would seem to holdfor every multiplier within a major design class, whateverits detailed layout. However, the initial simulation model
was over-simplified and gave poor results. Thus, the multiplier model used in simulations should matchthe hardware design as closely as possible.

Ideally, the gates in the simulation would be initialised. For each choice ofby executing an initial product, say
and , the product   would then be performed and thenumber of gate switches counted. For each , the average
would be computed as , and varied over all values andthis used to characterise . This is only possible for small
multipliers, and was done for all the results here with   .
For larger multipliers some simplifications had to be made:only a subset of random values and were chosen, and,
when necessary, only a random set of values for  were used
to derive data supposedly characteristic of .
For such input sets, the number of gate changes fromhigh to low or low to high were counted. These were averaged for a given first argument  and also for a given second
argument . The first arguments  (the multipliers) and thesecond arguments  (the multiplicands) were then orderedaccording to these averages and used to create tables, suchas Table 1, and graphs, such as Fig. 2, for different  .
The orders for multipliers and multiplicands are usuallyslightly different because the inputs cannot be treated symmetrically. Typically this results from using a row of fulladders to combine three multiples of the multiplicand into
two. Then, in the add-and-shift multiplier, bits of multiplicand  are processed uniformly, but those of multiplier are not. As a result, we distinguish between the multiplicand (always  here) and the multiplier (always  here).
For obvious reasons, the difference between these is moremarked for the Booth-recoding case.

For the add-and-shift multiplier, this principle held without
exception for both arguments and for all values of  thatwere investigated, whether by exhaustive simulation as in
the cases of   , or by random approximation as described above for   . Indeed, for small  there is a visible jump in the average number of gates switched when theHamming weight of an argument is increased (see Fig. 2).
In the case of the Booth multiplier, the Hamming Weight
Principle also held without exception for the multiplicand and all tested values of  . However, the multiplierargument, namely the input which is re-coded, behaved erratically with respect to Hamming weight. A much better measure was given by using Booth weight, which, in asense, corresponds to the Hamming weight of the recoding:Definition 1 The Booth Weight of a number with binary
representation    is the sum of the weights of all
has weight ,triples      (  ) where
has weight and all other triples have weight .







 

(Ends are padded with zeros as necessary.) In the Booth
multiplier with recoded multiplier, apart from the end conditions, triple
leads to a string of 0s being added to theleads to a string of 1s being
accumulating sum, triple
added, and otherwise a shifted copy of the multiplicand,or its complement, is added. On average, these contributerespectively, as in the definition.
weights in the ratio
Here is an illustrative example showing the behaviour:







 For the Booth multiplier with   , the average gate
count order is 0, 4, 1, 5, 7, 3, 6, 2, 12, 8, 13, 9, 11, 10,
15, 14 for the multiplier  but 0, 2, 4, 1, 8, 6, 5, 10, 3,
12, 9, 7, 14, 13, 11, 15 for the multiplicand .

The Booth weights of multiplier  are all in ascending order,
as are the Hamming weights of multiplicand .
More detailed ordering of digits with equal Hamming(or Booth) weight follows several rules-of-thumb. These
depend on the multiplier type, with exceptions arising fromhow bits are grouped for feeding into the compressors. The
two add-and-shift multiplier “guidelines” below hold foraround 75% and 85% respectively of cases with   :



0

1

2

4

5

3

6

7



Averages

6.31

7.31

7.88

8.30

9.80

9.87

10.41

12.27

0
1
2
4
5
3
6
7

6.31
7.44
7.88
8.17
9.80
9.88
10.39
12.27

6.31
6.31
6.31
6.31
6.31
6.31
6.31
6.31

6.31
6.81
7.06
7.06
7.56
7.56
7.81
8.31

6.31
7.06
7.31
7.69
8.44
8.06
8.69
9.44

6.31
7.31
7.69
7.91
8.91
8.69
9.28
10.28

6.31
7.81
8.44
8.66
11.78
9.94
10.78
14.69

6.31
7.56
8.06
8.44
9.69
10.81
13.16
14.91

6.31
8.06
8.69
9.28
11.03
12.97
12.00
14.94

6.31
8.56
9.44
10.03
14.69
14.72
15.13
19.31

Table 1. Average Gate Switching in a -bit Add-and-Shift Multiplier, with ordered Arguments.

 

I. Suppose  and  are odd digits with HW 
HW  and    . Then usually    
for  in the add-and-shift multiplier.

 





  for   .
For the add-and-shift case with   , these imply  
 and   , which are readily verified (see Table 1).
With the Hamming Weight Principle, this gives a total ordering of all digits when   . Grouping bits in threes for
II. Normally,  

Number of Gate Switchings
20

Digit 715

Digits
wt. 2





the 3-to-2 counters means that digits of the same weight
can behave quite differently, as is the case for weight 2 (seeFig. 2). Hence there are higher order properties that might
be exploited to deduce more than just Hamming weight.
the order varies slightly between multiplier
When 
and multiplicand, but the Hamming Weight rule still holds:

 For the add-and-shift multiplier with   , the aver-age gate count order is 0, 1, 2, 4, 8, 3, 9, 5, 10, 6, 12,
11, 7, 13, 14, 15 for the multiplier  but 0, 1, 2, 4, 8, 9,
3, 5, 10, 12, 6, 13, 7, 11, 14, 15 for the multiplicand .

The second rule-of-thumb always holds also, but the first
fails (at least for our multiplier) in a quarter of cases, suchas for the multiplicand pairs (3,5), (3,10) and (7,11).
Similar but more complex results apply to the multiplicand of the Booth multiplier, but other guidelines areneeded to characterise the order for the recoded argument.
A further principle relates the order of digits as  is increased when the hardware is constructed in the same way:
III. For add-and-shift multipliers, if  ¼ in  -bit arith-bit arithmetic.
metic, then usually  ¼ in  Thus, the digit order for   is contained within that of   except that the pair (5,3) is reversed. Like the firsttwo, this rule is frequently violated. Re-ordering of digits isinevitable: it is difficult to combine rows of full adders in aconsistent manner as  is increased.
It is now clear that there are general principles for any
multiplier which determine a broad ordering of the digits
under average gate switching, with the detailed order being
determined only once the multiplier is defined precisely.

10

Digitswt. 1
Digit 0

5
0

1

2

4

5

3

6

7

First Argument Digit

Figure 2. Gate Switching for the Second
Argument of a -Bit Add-and-Shift Multiplier.

5 Hamming Weights
Gate count results for digit products   can be translated easily into statistics relating Hamming weights by
averaging over all digits with the same Hamming weight.
Table 2 shows this for the -bit add-and-shift multiplier.
Fig. 3 illustrates the same data graphically. From this it
is clear that there is a close and potentially predictable
relationship between Hamming weight and average gate
switching activity. This relationship is close to linear ineach Hamming weight except for values close to . Moreover, from the above, digits of the same Hamming weight
behave in a broadly similar way. Thus, if one can obtain ameasure of the average gate switching activity for   as varies uniformly over all digits, or uniformly over all digitsof a known Hamming weight, then it should be possible toextract the exact Hamming weight of . Fortunately for the
security of an embedded RSA cryptosystem, this does notlead easily to a deduction of the value of  except in theunusual circumstances of extreme Hamming weights: thevariance in average gate counts between individual digitsof the same weight is not high, and for the middle weights
there are many alternative choices which can be made. Because of this, increasing the digit size  makes life muchharder for the attacker. However, just an approximate Hamming weight may be all that the attacker requires [12].





HW´ µ

HW´µ

0
1
2
3
4
5
6
7
8

0

1

2

3

4

5

6

7

8



77.30

81.49

88.26

95.88

103.82111.86119.87127.80135.60

77.30
81.49
88.24
95.90
103.84111.85119.84127.75135.60

77.30
77.30
77.30
77.30
77.30
77.30
77.30
77.30
77.30

77.30
78.35
79.40
80.45
81.49
82.54
83.59
84.64
85.69

77.30
79.40
81.72
84.47
87.83
91.77
95.63
99.27
102.97

77.30
80.45
84.47
89.78
95.69
101.56
107.69113.91
119.62

77.30
81.49
87.84
95.68
103.59111.81119.94128.15136.04

77.30
82.54
91.77
101.56111.84121.97132.05141.71152.00

77.30
83.59
95.54
107.76120.02132.06
143.64155.46167.58

77.30
84.64
99.12
114.15128.21141.70155.43168.97181.1477.30
85.69
102.86120.10136.04151.61167.50181.18193.14

Av

Table 2. Switching in -bit Add-and-Shift Multiplier averaged over Arguments of equal Hamming Wt.

;and two and a half gates are switched if Æiii) Suppose the full adder has been initialised with input
bits which are independent with probability  of being ,and the following input bits are independently with probability ¼ . Define  and ¼ ¼ . Then the average
number of gates switched by the latter input is

Gates
200
175



150
125
100
75



0

2
4
HW(a)

2
6

8

 

8
6
4
HW(b)

when Æ

0

Figure 3. Gate Switching in an -bit Multiplier
as a Function of input Hamming Weights.



¼

¼





 

  and, when Æ  , it is       


¼

¼

iv) For the situation in (iii), the average difference in thenumber of gates switched between cases Æand Æ
is: a) at least  for all    with equality for   ,b) a decreasing function of  for most values of ¼ , andc) positive for all  less than approximately  .



6 Trees of ¿-bit Counters
Full adders, i.e. -bit counters, form the main body of atypical multiplier. This section studies how the distributionof bits changes as the bits progress down a tree of counters.
The changes affect the number of gates that are switched:interesting data-dependent activity occurs near the inputs,
but any non-uniformity in the distribution of input bits dissipates lower down the tree so that, by the output, s ands turn up with roughly equal probability. Multipliers constructed from other compressors behave similarly.
The next theorem describes how a single counter experiences a data-dependent amount of gate switching activity
and affects the probabilities of bits as they pass through.



Theorem 1 In a -bit full adder, let Æ be the number of input bits set to minus the resulting number of output bits
set to .
i) Æ is either or . If the input bits are independent withprobability  of being and , then Æwithprobability     and Æwith probability    ;ii) If all inputs are independently and uniformly dis,tributed then, on average, two gates are switched if Æ




 

















Theorem 2 i) For inputs to a -bit counter which are independent and equal to with probability , an (unspecified)
output bit is with probability    where .
ii) Assume the output bits from -bit counters are independent. If bits are fed in a random order from one row to
the next in a tree of -bit counters, then the probability ofan output bit from the final row being tends monotonicallytowards  as the number of rows is increased.









Proof. These are easy exercises for the reader. 
Theorem 2 provides probabilities of 1s down a tree ofadders and then, using Theorem 1(iii) with ¼
, onecan obtain the average gate switching difference  at depth
 . These are tabulated in Table 3 starting at   . Dependency on the initial distribution of data clearly diminishes as distance increases down the multiplier. Over threesuccessive counters, the position dependent differences areapproximately halved e.g. from 1.5417–0.5 to 1.0461–0.5(where 0.5 is the limiting value).








0
1
2
3
4
5
0.2500 0.2969 0.3393 0.3753 0.4045 0.4275
1.5417 1.3635 1.1950 1.0461 0.9218 0.8221





6
7
8
9
10
11
0.4453 0.4588 0.4690 0.4767 0.4825 0.4869
0.7442 0.6843 0.6388 0.6044 0.5784 0.5589

As in Theorem 1, let undashed characters such as  denote probabilities during initialisation and let dashed characters such as ¼ denote probabilities during execution. Theprobability of a bit of input  being is ¼
HW  . Let
us denote these bit probabilities for , , and by ¼ ,  ¼ , and  , respectively. Then the multiplier model is initialisedby computing
and then executing   during whichgate switching is calculated probabilistically.



Table 3. Probability  of a and the extra average Gate Switching  when a Bit is removed
by a counter at depth  in the Tree.



 




 












 





 

8 The Hamming Weight Multiplier

The simulation of Section 3 uses  time becauseof the  choices for each of , , and . This makes it infeasible to model 16-bit or larger multipliers. To investigate
behaviour in terms of Hamming weights, it is necessary tobuild a multiplier which computes (average) gate switchingactivity just from the weights of , , and . Ideally thisshould have polynomial, not exponential, time complexity
so that any expected size for a multiplier can be processed.







The contribution from the multiplexors and AND gates iseasy to assess exactly. Each of the initial  input bits isfirst multiplexed to  AND gates at the top of the multiplier.
Those corresponding to the first argument ( then ) arechanged from 0 to 1 with probability  ¼ and from 1
to 0 with probability  ¼ . Thus, taking both arguments
into account, the multiplexors introduce a power variation
proportional to  ¼  ¼   ¼   ¼ . As this is linear
in  and  , the average over all initial conditions is given by  . The formula is then constant, showing
taking 
the power variation resulting from multiplexors is constant.
So this contribution is of no further concern.
On average, the AND gates will be initialised with
their outputs set towith probability  and, when  is computed, the AND gates output a with probability ¼  ¼ . So  ¼  ¼ is the probability that an
AND gate will be switched fromto and  ¼  ¼
is the probability that it will be switched in the opposite direction. So it will be switched with probability  ¼  ¼  ¼  ¼ .
This must be multipliedby   to obtain the expected number of AND gates
which will change state: HW HW
HW  HW    HW HW HW  HW  . Averaging over all initialising inputs and yields     HW  HW  .
This is a very reliable component of the total variationin gate counts, almost independent of the multiplier construction. It is a substantial part of the total data-dependent
variation of the multiplier. There are HW  HW  input 1s
to the counter tree, and this is an upper bound on the numberof 1s removed by the adder tree. Each removal of a 1 causes
a data dependent increase of about  gates switching foran average initialisation (by Table 3 and an estimate of thenumber of counters in each row). Comparing the resulting
total of  HW  HW  gate switches with the total fromthe AND gates, we expect AND gate switching to accountfor about 0.5/(1.2+0.5), i.e. 30%, of the total data dependent variation, which is what we find.

The add-and-shift hardware multiplier was simulated
without pipelining or bit recoding. It is best described via
bit slices where the th slice processes all bits corresponding
to . In order for the multiplier to compute  , multiplexors first produce  copies of each bit from its two arguments.
These are then ANDed in pairs to create   bits   .
Bit slice 0 just outputs bit   from its AND gate. For bit
slice  with  , there are  input bits from AND gatesand  carry bits from slice  . These are added using
 3-bit counters and a single 2-bit counter, generating
one output bit and  carries. Slice  has   inputs fromthe AND gates and   carries in from slice   . These
are added using   3-bit counters and a 2-bit counter
which generate   carries up to slice and one output
bit. Lastly, for bit slice   where  , there are 
input bits from AND gates and  carries in from the previous
slice. These are added using  3-bit counters which
generate  carries to the next slice and one output bit.
To minimise critical path lengths a Wallace tree was built
for each bit slice, i.e. the full adders were arranged so thatbits with the shortest critical path were always added together first. The multiplier contains    full adders,
and the first row in the Wallace tree has about one third ofthese. Subsequent rows have about  rds of the number inthe previous row. So, although the two theorems indicate
a decrease in the data-dependent gate switching as one descends the tree, the decrease is of less importance because
so many of the 3-bit counters are at the top of the tree.



8.1 The Multiplexors and AND Gates

7 The Add-and-Shift Multiplier Model





 


 



 









 









      
 
 



    

8.2 The Compressor Tree
To prevent combinatorial explosion in the counter tree,some simplification is necessary.

HW´ µHW´µ
0
1
2
3
4
5
6
7
8

0

1

2

3

4

5

6

7

8

73.54
73.54
73.54
73.54
73.54
73.54
73.54
73.54
73.54

73.54
74.90
76.32
77.82
79.39
81.05
82.79
84.60
86.48

73.54
76.32
79.39
82.79
86.48
90.35
94.32
98.30
102.25

73.54
77.82
82.79
88.40
94.32
100.28106.14111.82117.28

73.54
79.39
86.48
94.32
102.25109.95117.28124.21130.76

73.54
81.05
90.35
100.28109.95119.05
127.53135.46143.00

73.54
82.79
94.32
106.14117.28127.53136.99145.95154.92

73.54
84.60
98.30
111.82124.21135.46145.95156.46168.3473.54
86.48
102.25117.28130.76143.00154.92168.34
193.46

Table 4. Gate Switching Activity for the -bit Hamming Weight Add-and-Shift Multiplier.

 Independence Assumption for Counters: The inputs toeach full adder and each half adder are independent.

16



14

HW(a *b )

12
10
8
6
4

16
12

2
8

HW(b )016

14

HW(a )

12

10

6

4
8

2

0

0
4

In practice this assumption is absurd because there are only
 bits fed into the multiplier but  bits which are generated from them and processed by the counters. Moreover,strong dependencies can persist if related bits are grouped
together for input into counter sub-trees.
It is necessary just to know the probability of input bits
to a counter being 1 in order to apply Thm. 2 to computethe probability of output bits being 1. Then Thm. 1 with theassumption enables the average number of gate changes tobe computed for the whole tree once input bit probabilities
are chosen for the initialisation and execution phases. After averaging over all initial states, expected gate switchingactivity was obtained, as in Table 4.

Figure 4. Average Hamming Weights of Products for a 16-bit Multiplier.

8.3 Evaluation
This model matches the actual values very well: themaximum relative error between entries in Tables 2 and 4
is in the region of 7.5%. Moreover, for all small  the formsof the discrepancies are similar, and therefore predictable.
For example, model values for input weights   are consistently marginally smaller than true values by about 5%.
So it seems reasonable to assume that extrapolating to largecases will yield fairly accurate results and that a standard
correction could be applied to remove most of the error.
There is a rather beautiful connection between Hamming
weights of inputs to a product and the average Hamming
weight of the result. This is illustrated in Fig. 4. The samefeatures appear for all word lengths  . The difference between these weights is, of course, the number of bits removed by the counters, which is proportional to the average number of gates switched in the multiplier. So a usefulhealth check for the model is to construct a table of output
weights and compare it with these expected values.
In the model, the output digit is a vector of probabilities
associated with its bits. The sum of these is the average
Hamming weight predicted by the model for the output.
The table of these output weights was created for various  up to   . The same overall features were foundbetween the surface for the model and that for the true values: steep sides when one Hamming weight is small, a large
plateau region for the majority of values, and a small peakjust before the value   . The only main feature missing
from the model is the slight depression near   .

 

 

8.4 Extrapolated Results
It is now apparent that the Hamming weight model forthe add-and-shift multiplier describes an overall level ofdata-dependent power consumption which has essentiallythe same properties for multipliers of any size. Total gate
switching for weights  and   is listed in Table 5.
In all cases where  
the model gives values for 
which are almost exactly 95% of the correct values, and so it
is possible to predict the true values for  when   .
For   the values for the model seem to increase at aslightly faster rate than the actual values, thereby providing.
an upper bound on actual values above 
Switching for weights  always gives the minimal

 


 

 

 

 



 




4

5

6

7

8

12

16

24

32

48

64

Actual´¼ ¼µ
Model´¼ ¼µ

13.81
13.13

24.47
23.24

38.71
36.70

56.46
53.66

77.30
73.54

194.8
186.9

353.5
353.1

822.8
842.0

1486
1540

3395
3563

6081
6422

Actual´ µModel´ µ

40.12
39.57

68.23
67.65

103.05102.65144.40144.40193.14
193.46

456.3
458.6

824.5
834.7

1887
1921

3380
3453

7662
7851

13669
14030

Table 5. Minimum and Maximum Gate Switching Activity, namely that for Hamming Weights  . (Predicted Values in italics).

     

9 The Booth-Hamming Weight Multiplier
Following the above simplifications, a binary Booth
multiplier was also built for simulating power consumption
as a function of the Hamming weight of one input, and the
Booth weight of the other, recoded input. However, the simplifications used for the add-and-shift multiplier failed to
produce a sufficiently accurate model of the behaviour here.
The problem seems to lie in the independence assumption:a sizeable proportion of the addends are not the random bitsof the multiplicand (or its complement) but strings of all 0s
or all 1s. Further research is merited here.
For the Booth-recoding multiplier behaviour is much
more consistent over the re-coded input when measured using Booth weight instead of Hamming weight. Moreover,average gate switching for any pair of digits shows muchless variance than for the add-and-shift multiplier. Conse-

12
10
8
6
4
2
0
0

8

16
12
HW(b )

16

HW(a )

1248

       
 

14

4

 

16

0



18

Power & EMR 

activity, and that for   gives the maximal activity. For
all small  this coincides with the minimum and maximum for digit-by-digit averages. So we can assume that thetable also accurately predicts minimum and maximum gate
switching activity during any multiplication performed bya multiplier built according to the specification in Section
7 when averaged over all possible initialisations. Without
such averaging the extremes are greater: for example,  followed by   should result in no gate switching at all.
As the total number of gates in the model multiplier isquadratic in  , namely     , it seems worth trying to fit
a quadratic curve to the values in Table 5: gate switching for is approximated by      in the actual multiplier, compared with        in theHamming weight model; and that for   is approximatedby         in the actual multiplier, comparedwith         in the model. These functions fit
within the bounds imposed by the hardware. As they also
provide a very good fit to all ten (resp. 15) points used rather
than just three (with about 3% relative error in the worstcase), they were used to suggest approximations for the true
values which were too costly to compute in Table 5. Thus,on average between about a quarter and just over a half ofthe gates are switched during each multiplication.

  and

Figure 5. Combined Power & EMR Trace Results for -Bit Multiplier.



quently there is much less variation between the behaviourof different Hammming/Booth weight classes here than for
the add-and-shift multiplier. So this multiplier should be
more resistant to a weight-based side channel attack.

10 Laboratory Results
To verify the accuracy of our models in practice rather
than compared with a simulation, power and EMR fromseveral hardware multipliers were measured following practices described in [9, 10]. We had access to unpipelined
add-and-shift 16- and 32- and 64-bit multipliers. Data wasloaded in one cycle, the product computed in the next, andthe output written to memory in the third. Our model applies to the middle cycle.
For each pair of Hamming weights, five random inputs and  were chosen with those weights, and the current andelectromagnetic traces of the multiplication cycle obtained
after an unknown initialisation which we assumed was random. Thus there were  traces to be averaged for each
Hamming weight pair. The traces consisted of 12-bit current and EMR measurements made at 35 times the (internal)
clock frequency of the multiplier. They included information about the execution address and the last instruction ex-ecuted, so this was removed using an accurate template. As
the traces still included further noise from other sources, anaverage of two traces for each input pair was taken. Thus,
points was taken as the data dependent
the average of
output for each multiplication.
The results from the 16-bit case are illustrated in Fig. 5.
As expected from the theory, there is a remarkable correspondence between this and the average Hamming weightof the products as illustrated in Fig. 4. An attacker witha side channel value can therefore predict a small set of
possible Hamming weight pairs for the arguments using theHamming weight multiplier above or perhaps reference values from the target multiplier itself.

 

11 Conclusion
By simulation, theoretical modelling and laboratory experimentation, it has been confirmed that the variation in
power used by an add-and-shift multiplier and the EMR it
generates are closely related to the Hamming weights of the
inputs when averaged over all possible initial states. This isa potential weak point which attackers of embedded cryptosystems may try to exploit to extract secret keys.
A model was derived which determines power usage accurately from the Hamming weights of inputs. It executesin polynomial time with respect to the number of bits, contrasting markedly with the exponential time required to consider all input bit patterns in a full simulation. Hence it canbe used to predict behaviour accurately in larger multipliers
for which a full simulation is computationally infeasible.
The same construction principles may be applicable tobuild Hamming (and Booth) weight multipliers which will
predict side channel leakage from any multiplier design.
Research is on-going for a binary Booth recoding multiplier, but it was clear that gate switching exhibited less variation than in the add-and-shift case. Although more complex in construction, this seems to make such multipliers
more resistant to side channel attack.

References[1] D. Agrawal, B. Archambeault, J. R. Rao, and P. Rohatgi.
The EM side-channels. In B. Kaliski, Ç. Koç, and C. Paar,
editors, Cryptographic Hardware and Embedded Systems –CHES 2002, volume 2523 of Lecture Notes in Computer Science, pages 29–45. Springer-Verlag, 2002.
[2] R. Anderson and M. Kuhn. Tamper resistance - a cautionary note. Proc 2nd USENIX Workshop on Electronic Commerce, Oakland, California, pages 1–11, 18th-21st November 1996.
[3] R. M. Best. Microprocessor for executing enciphered programs. US Patent 4,168,396, 8th September 1979.

[4] M. Flynn and S. Oberman. Advanced Computer Arithmetic
Design. John Wiley & Sons Inc., New York, 2001. ISBN
0-471-41209-0.
[5] K. Gandolfi, C. Mourtel, and F. Olivier. Electromagnetic
analysis: Concrete results. In Ç. Koç, D. Naccache, andC. Paar, editors, Cryptographic Hardware and Embedded
Systems – CHES 2001, volume 2162 of Lecture Notes in
Computer Science, pages 251–261. Springer-Verlag, 2001.
[6] P. Kocher, J. Jaffe, and B. Jun. Differential power analysis.
In M. Wiener, editor, Advances in Cryptology – Crypto ’99,
volume 1666 of Lecture Notes in Computer Science, pages
388–397. Springer-Verlag, 1999.
[7] R. Mayer-Sommer. Smartly analyzing the simplicity and thepower of simple power analysis on smartcards. In C. Paar
and Ç. Koç, editors, Cryptographic Hardware and Embedded Systems (Proc CHES 2000), volume 1965 of Lecture
Notes in Computer Science, pages 78–92. Springer-Verlag,
2000.
[8] P. L. Montgomery. Modular multiplication without trial division. Math. Computation, 44:519–521, 1985.
[9] J.-J. Quisquater and D. Samyde. Electromagnetic analysis(EMA): Measures and counter-measures for smart cards. In
Smart Card Programming and Security (E-smart 2001), volume 2140 of Lecture Notes in Computer Science, pages 200–
210. Springer-Verlag, 2001.
[10] J.-J. Quisquater and D. Samyde. Eddy current for magnetic
analysis with active sensor. Proc. e-Smart 2002, Nice, pages
183–194, September 2002.
[11] R. L. Rivest, A. Shamir, and L. Adleman. A method for
obtaining digital signatures and public-key cryptosystems.
Comm. ACM, 21:120–126, 1978.
[12] C. D. Walter. Sliding Windows succumbs to Big Mac attack.
In Ç. Koç, D. Naccache, and C. Paar, editors, Cryptographic
Hardware and Embedded Systems – CHES 2001, volume2162 of Lecture Notes in Computer Science, pages 286–299.
Springer-Verlag, 2001.
[13] C. D. Walter and S. Thompson. Distinguishing exponent
digits by observing modular subtractions. In D. Naccache,editor, Topics in Cryptology – CT-RSA 2001, volume 2020of Lecture Notes in Computer Science, pages 192–207.
Springer-Verlag, 2001.