Distinguishing Exponent Digits
by Observing Modular Subtractions
Colin D. Walter? & Susan Thompson
Datacard platform7 seven
6th-8th Floors, 1-2 Finsbury Square, London EC2A 1AA, UK
www.platform7.com

We analyse timing variations in an implementation of modular multiplication which has certain standard characteristics. This showsthat squarings and multiplications behave di erently when averaged overa number of random observations. Since power analysis can reveal suchdata, secret RSA exponents can be deduced if a standard square andmultiply exponentiation algorithm is used. No knowledge of the modulus or input is required to do this. The technique generalises to the m-ary
and sliding windows exponentiation methods since di erent multipliers
can be distinguished. Moreover, only a small number of observations (independent of the key size and well under 1k) are required to perform thecryptanalysis successfully. Thus, if the modular multiplication algorithm
cannot be made any safer, the exponent must be modi ed on every use.
Abstract.

Exponentiation, modular multiplication, Montgomery multiplication, RSA cryptosystem, m-ary method, sliding windows, timing
attack, power analysis.

Key words:

1 Introduction
Smart cards may contain sensitive data, such as private RSA keys [7], which
may be of great value to an attacker if they can be retrieved. These may wellbe used for all authentication and key exchange processes, and so must not becompromised. However, we illustrate how one likely source of timing variation
during modular multiplication can be exploited to reveal such keys with very
few observations.
Kocher [5] wrote one of the earliest, relevant, publicly available documents ontime-based attacks and he relies for success on knowing the plaintext inputs. The
causes of time variations are explicit conditional statements in the software, andimplicit conditionals introduced by the compiler or hardware, most usually in thecause of optimisation. Skipping a multiplication by 0 is a typical example of the? contact address: Computation Department, UMIST, Manchester, M60 1QD, UK,www.co.umist.ac.uk

2

LNCS Vol.

2020 Springer Verlag, 2001, pp 192-207

latter which causes unexpected time variation. An example of the former is thatthe standard modular multiplication algorithms make conditional subtractionsof the modulus to keep the result within a xed upper bound. It is this extra
subtraction that is the subject of study here. Dhem et al. [2] provided practicaldetails for using it in Kocher's attack to obtain RSA keys. They repeatedly
assume the next unknown exponent bit is 1 and partition the known plaintext
inputs into two sets according to whether or not the extra subtraction occurs forthem in the corresponding multiplication of the exponentiation routine. With
enough observations, if di erent average times occur for the two sets, the bit
must be 1 and otherwise it is 0. For 512-keys 300,000 timings must be collected
for the attack to succeed.
Recent independent work at Platform7 Seven [1] and by Schindler [8] has provided theoretical justi cation for this. Both show that in Montgomery's modular
multiplication algorithm [6], the need for a nal subtraction to obtain a result
less than the modulus is di erent for squares and multiplications. Borovik andWalter [1] used this in the way described here to read secret RSA exponent
bits directly using unknown plaintexts. Schindler [8] used it to attack implementations which make use of the Chinese Remainder Theorem to reduce thearithmetic. However, Schindler's is a chosen plaintext attack.
Here we develop the attacks to a much wider setting and, in particular, tounknown or blinded inputs with unknown modulus and more general exponentiation algorithms. The paper commences with theoretical explanation of theobserved frequency of modular subtractions, enabling predictions about the average behaviour of squares and multiplies. This provides a much clearer pictureof how to use timing measurements to reveal a secret RSA exponent. A little
more strongly than Schindler, it is assumed that power, timing, or other measurements during each exponentiation are clear enough to enable the presenceor absence of an extra modular subtraction to be detected for each individual
multiplication. For each multiplication or squaring in an exponentiation scheme,
the frequency of subtractions can then be computed for a set of observations
and used to di erentiate between the two operations.
If the usual square and multiply exponentiation algorithm has been used, thisprocess yields the exponent bits immediately. Indeed, straightforward statistics
can be applied to noisy data to deduce how many observations need to be made toobtain the exponent with a given probability. For clean data, this number turns
out to be so small as to make the smart card totally insecure, and therefore
useless, unless adequate counter-measures are employed.
By carefully selecting appropriate subsets of observations, the same techniques can be applied to any sequence of multiplications which only uses multipliers from a small set, in order to identify which multiplier has been used. As
a result, the usual m-ary [3] or sliding window methods [4] of exponentiation
are also vulnerable to this attack. For m = 4, under 1000 observations suÆce.
Moreover this result is independent of the key length because the exponent digits
are determined independently, not sequentially.

Walter & Thompson, Distinguishing Exponent Digits

3

The conclusion is clear: if suÆcient timing information can be gleaned, theneither such numerous conditional modular adjustments must be avoided (as they
can be e.g. see [9]) or the exponent must be adjusted before each new decryption in order to confound the averaging process [5].

2 Timing Variations in Modular Multiplication
2.1 Initial Assumptions

For the purpose of this paper we consider a generic multi-precision implementation of Montgomery multiplication [6] used in the context of an RSA decryption,
but similar timing attacks can be mounted against other modular multiplication
algorithms which display the same weakness as is exploited here.
We assume that arithmetic is based on an m-bit architecture. Hence all numbers are presented in radix r = 2m . Let k be the xed number of digits used torepresent the arguments and intermediate results of the exponentiation. Thenl = mk is the number of bits in such numbers. For convenience and because it is
to be expected, we will assume the modular multiplication algorithm performs
l addition cycles so that the Montgomery scaling constant is R = 2l [10]. It isnatural to use as large a modulus N as possible, and so{ We assume that R=2 < N < R.
This is perhaps the major drawback of many implementations, because it forces
a conditional modular subtraction to be made if an over ow bit is to be avoided.

2.2 Analysis of the Modular Reduction

Let R 1 be the integer uniquely determined by the conditions R  R 1  1 mod N
and 0 < R 1 < N . This exists because R is a power of 2, ensuring that it
has no non-trivial common factor with the odd modulus N . Given non-negative
integers A < R and B < R, the main loop of Montgomery multiplication returns
a numberM  ABR 1 mod N
in the range 0  M < B +N . Hence an extra subtraction of N or even of 2N
may be required to get a residue less than N because B < 2N . In particular, thissubtraction might be deemed worthwhile to avoid the result over owing into an
extra digit position.
In this paper we perform a cryptanalysis based on the conditions under whichsuch extra subtractions are performed at the end of each modular multiplication.
Since M N < B < R, we concentrate on the version of the algorithm for which
the reduction is made at most once to a level below R:{ We assume the modular multiplication algorithm includes a nal conditional
statement for modular subtraction, namely

M :=



M
if M < R
M N if M  R :4

LNCS Vol.

2020 Springer Verlag, 2001, pp 192-207

This reduction is easier and faster to implement in hardware than obtaining theleast non-negative residue, and it suÆces for RSA exponentiation which employs
repeated modular multiplication. However, the version of the algorithm with themodular reduction to a level below N (as in [8]) can be analysed analogously and,from the practical point of view, the analysis yields similar results in exactly thesame way. Of course, obtaining such a tight bound, i.e. the minimal non-negative
residue mod N , is computationally more expensive and so is often performed onlyat the very end of the exponentiation.
Hardware limitations require that both multiplicands A and B and the modulus N are smaller than R. So, written to the base r, they have the forms

A = (ak 1 ak 2 : : : a1 a0 )r ,B = (bk 1 bk 2 : : : b1 b0 )rand

N = (nk 1 nk 2 : : : n1 n0 )rwhere 0  ai < r, 0  bi < r and 0  ni < r.
Let n0 := (r n0 ) 1 mod r. Then the Montgomery multiplication routine
runs as follows:
S0 := 0 ;for i := 0 to k 1 do
Si+1 := fSi + ai B + ((Si + ai B )  n0 mod r)  N g=r

end

Here (Si +ai B ) mod r is given by the rightmost digit of Si +ai B to the base r
which is, of course, equal to (si0 +ai b0 ) mod r. Si+1 is clearly always an integer.
Notice that, by induction,ri Si  (ai 1 : : : a0 )r  B mod N
and we can also prove by induction on i that Si < B + N . Indeed S0 = 0 gives
us the basis of induction, anda(S +a B )  n0 mod r
Si + i B + i i 0
N
r
r
r
1
r 1
r 1
< (B +N ) +
B+
N
r
r
r
= B +N

0  Si+1 =

Hence
and

1

Sk 1  ABR 1 mod N

Sk 1 < B +N < R+N < 2R
Note the asymmetry between multiplicand A and multiplier B in this bound.
To return a value of M = ABR 1 +N which is strictly less than R, we need to

set

M :=



Sk 1
Sk 1

if Sk 1 < R
N if Sk 1  RWalter & Thompson, Distinguishing Exponent Digits

5This last adjustment is a possible cause of time variations in modular multiplications. It might be avoided by performing the subtraction whether it is necessary
or not, and then selecting one of the two results. However, timing variations
may still creep in here because of compiler optimisations or because a di erent
number of register movements is performed. Be warned!

{ We assume that timing or other variations enable all or almost all occurrencesof this nal subtraction to be observed.

Notice now that the value of Sk 1 has very strong dependence on B throughthe middle term of the expression for it:

Sk 1 =a(S +a B )  n0 mod r
Sk 2 + k 1 B + k 2 k 1 0
N
r
r
r

1

So one has to expect much more frequent \long" multiplications (that is, multiplications which involve the nal modular adjustment) for larger values of B .
These can be expected particularly as N approaches R.

2.3 Analytical Approximation
The modular adjustment happens when the random variable  = Sk 1 =R isgreater than or equal to 1. Then  can be expressed in terms of other randomvariables, namely =  + +where

ak 1 + 21
 RA ,r
B,=
R(Sk 2 +ak 1 B )0  n0 mod r N
N
 =

+
,
r
R 2rR
B +N
S
= k 2
rR
2rR
=

are random variables distributed in some way over the intervals (0,1), [0,1),(0,N=R) and ( 1r , r1 ) respectively. Let us investigate the distributions that theserandom variables might have in the context of exponentiation. For this,{ We assume that A and B are uniformly distributed mod N .

This may not hold for the initial one or two operations of an exponentiation
because of the manner in which the initial input is formed. But, the whole valueof modular exponentiation as an encryption process is its ability to give what
appears to be a uniform, random output mod N no matter what the input has
been. Since 3 is accepted as a suitable encryption exponent, we can reasonably
assume that after two or three multiplicative operations, the inputs to further

6

LNCS Vol.

2020 Springer Verlag, 2001, pp 192-207

operations in an exponentiation are close enough to being uniform modulo N
for our purposes.
Since the coeÆcient0 (Sk 2 + ak 1 B )0  n0 mod rr

 1 1rof N=R in the expression for  is suÆciently randomised by modulo r arithmetic,
we can assume that  is independent of and and is uniformly distributed in
the interval (0; N=R). (It is easy to deduce from earlier multiplications that thisis the case even if B has been shifted up to make the computation easier.) We
will argue that A and B are piecewise uniformly distributed on their intervals
so that the same is true for and . Clearly and are not independent
for squaring operations since then A = B , but we will justify that they are
essentially independent for almost all of the multiplications.
We will now prove that is smaller than + by a factor of order r1 so thatits contribution to  may be neglected. Since A is assumed uniformly distributed
mod N , for non-small i, Si can also be expected to be randomly and uniformly
distributed mod N because its residue class is determined by a (large) suÆx of
A times B . As Si belongs to the interval [0; B +N ) but can achieve both end
points, and the added multiple of N is essentially random, the most reasonable
expectation is that Si is piecewise uniformly distributed over the three subintervals [0; B ), [B; N ) and [N; B +N ) with probabilities 21N , N1 and 21N respectively.
This leads to an average of 12 (B +N ) for Si and therefore to an expected averageof 0 for .
Consider the case when B +N < R. Then Sk 1 < B +N ensures that nonal subtraction takes place. Hence, under the uniformity assumption mod N ,the distribution of the output will be identical to that of Sk 1 given above. So,such output provides a mean of 12 (B +N ), which is less than 12 R. Otherwise, topreserve uniformity mod N , when the subtraction takes place the output distribution will be close to uniform on each of the subranges [0; R N ), [R N; N )and [N; R), yielding instead an average of 21 R for the output. Thus,{ For a given input B, the output from a modular multiplication is approximately piecewise uniform on the interval [0; R). For B +N < R the intervalsof uniformity depend on B . In both cases there are three intervals with
non-zero probabilities 21N , N1 and 21N respectively.

By the above, if modular multiplier outputs are used for the inputs A and
B of a subsequent multiplication, then their average values match or exceed
1(B +N ), which is bounded below by 41 R. Thus we obtain lower bounds of at2

least 14 for each of and . So, and are at least 4r times larger than
average. Hence, we can ignore the contribution of providing:on{ We assume that the radix r is not too small.

Commonly used bases such as r = 28 , 216 and 232 are quite acceptable here.
From the above, we can expect that the statistics for nal adjustments in theWalter & Thompson, Distinguishing Exponent Digits

7

Montgomery multiplication(A; B )

! A N B  ABR

1

mod N

are suÆciently close to the statistics of occurrences of the subtraction in the
product

+
if
+ <1
=
+   if+ 1where  = N=R. The radix r is large enough for the discreteness of the original
problem to make only a marginal di erence to the calculations if we substitute continuous random variables for the discrete ones: the relative errors willinvariably be bounded above by at most about r1 which, by assumption, is small.

2.4 Heuristic Estimates for Multiplications
In order to get some intuition regarding the behaviour of Montgomery multiplication, let us assume, like Schindler [8], that{is uniformly distributed on (0; 1)

The previous section clearly shows that this is a simpli cation. The average
output of the modular multiplier is less than R=2 so that the distribution ofover [0; R) cannot be uniform. However, providing N is close to R, such anassumption is only slightly frayed at the edges.
N
R



6

H(HH , )
HHH
+ =1
R N N
B
R
B
R

O

(1; NR )HHH
HH(1H; 1 )BR

1Fig. 1.

Computation of P (+  1).

Suppose has the xed value = B=R. (So this is not a squaring.) The
modular adjustment takes place when the point ( ;  ) belongs to the upper
right corner cut from the rectangle [0; 1][0; N=R] by the line + = 1 (seeFigure 1). The probability of this event is the ratio of the area of the triangle tothat of the rectangle, namely

Pmult(B ) = P ( +  1) (0

if N +B < R

B +N R)2 if N +B  R:
2BN

(

8

LNCS Vol.

2020 Springer Verlag, 2001, pp 192-207

As expected, the reductions occur more frequently the larger B +N is, and, inparticular, they normally occur in a sizeable proportion of all observations.
It is possible to obtain a more precise formula for Pmult as a function of B
using the piecewise uniform probability function described in the previous section. However, this detail is unnecessary for the attack which we describe. It issuÆcient to note that when we select a set of observations involving smaller than
average values of B then we can expect fewer subtractions to occur. This will
happen, paradoxically, if such B are the outputs of previous modular multiplications for which the extra subtraction did not occur (since we saw the average
was 21 R after a subtraction, but only 12 (B +N ) < 12 R otherwise).

2.5 Probability Estimates for Multiplications & Squarings
With the same de nitions as before, the probability of modular adjustment in a
Montgomery multiplication of independent arguments is

Z1

Pmult  P ( +  1) =

1

Z1

N=R

(1

Z N=R

N=R)=xxy

1p(x; y; z )dzdydx

where p is the probability density function for   . The randomising e ect ofraising to an odd power of at least 3 means that most operands in the multiplications of an encryption or decryption will be e ectively independently distributed
mod N . Hence, assuming this is the case, we could write p as a product of threefunctions of a single variable, representing the individual density functions for, and  respectively. As noted above,  is uniform on [0,N=R]. If we simplify
by assuming p (x) = p (x) = 1 then

Pmult

 NR

Z1

Z1
N=R

Z

1

R 1
=
N 1 N=R
R
=
(1 (1
4N

1
(1

Z N=R
N=R)=x1

xy

dzdydx



N
1
N 21
dx
x (1
) + (1
)
2
R
2
R x
N 2
N
R
N 2
N
) ) (1)(1) log(1
)
R
R
2N
R
R

In the same way, the probability of a modular adjustment in a Montgomery
square is

Psquare  P ( +  1) =
2

Z1

p N=R

Z N=R

1

1

x2

p(x; y)dydx

where p is now the probability density function for  . Since
independent and  is uniform on [0,N=R], we can re-write this as

Psquare  P ( +  1) =
2

Z1

p N=R
1

Z N=R
1

x2

and  arep (x)R=Ndydx

Walter & Thompson, Distinguishing Exponent Digits
=

R
N

Z1

N

p N=R ( R9

1 + x2 )p (x)dx

1

Once more, we will simplify by assuming that A is uniformly distributed on[0,R). Then p (x) = 1, so that

Psquare  1



2R
1
3N

(1

N 3 =2)RAt the upper end of the range for N , namely N close to R, we see that theexpression for the square is approximately 31 , while that for the multiplicationis only about 41 . Hence squares can easily be distinguished from multiplications
with independent arguments by the frequencies of the extra subtractions. Although the density functions become progressively more badly approximated by
1 as N decreases, the piecewise linear nature of the true density function can beused to obtain accurate formulae which demonstrate a similar di erence for all
values of N in the interval ( 12 R,R).
These formulae display a potentially useful dependence on N which might
be exploited to deduce an approximate value for N from observing the actual
value of Psquare or Pmult . Moreover, if input A can be restricted in some way,
the density function may be modi ed enough to provide detectable changes in
Psquare or Pmult .
For example, suppose the multiplicative operation Op1 (square or multiply)
generates the input A to the multiplicative operation Op2 as part of some process,such as an exponentiation. Partition a set of observations of the process into two
subsets, one for which Op1 applies the extra adjustment and the other for which
it does not. The study in a previous section shows the related density functions
for A are suÆciently di erent to yield distinct averages for A and so will usually
yield two di erent values for the frequencies of extra subtractions at the endof Op2 . This enables us to determine which multiplicative operation Op1 hasgenerated the argument used in Op2 . If the wrong operation Op1 is selected, we
expect a much lower di erence between the density functions so that there islittle di erence between the observed frequencies for the two subsets.

3 Attacks on Exponentiation with Unknown Modulus

3.1 Unknown Plaintext Attack on the Square & Multiply Method
The standard square and multiply method of exponentiation uses the binary
representation

e =

n
X
j =0

ej 2j

of the exponent e. It scans the bits of e in descending order and applies a Hornerstyle evaluation

X e = ((: : : ((X en )2 X en 1 )2 : : :)2 X e1 )2 X e0 :

10

LNCS Vol.

2020 Springer Verlag, 2001, pp 192-207

Multiplication by X ei is performed conditionally whenever the bit ei is 1.
When computing X e mod N using modular Montgomery exponentiation we
rst replace X by XR mod N using a Montgomery multiplication by R2 . After
that, the identity
AR  BR  R 1  ABR mod N
allows us to carry out the multiplication of (Montgomery) powers of XR until
we get X e R mod N . Montgomery multiplying this result by 1, we obtain thedesired power X e of X modulo N .
Thus, in this section and the next section all multiplications are understoodas Montgomery multiplications modulo N . To make notation more transparent,
we write X N Y instead of XY R 1 mod N and assume that the nal modular
reduction is done, when required, within the computation of X N Y . Thus all
the intermediate products are smaller than R and satisfy the conditions for thearguments of the modular Montgomery multiplication as set out in the previous
section.
An immediate corollary from the statistical analysis of the previous sectionis that the probabilities of modular adjustments in a Montgomery square anda Montgomery multiplication are suÆciently large to make the adjustment detectable from only a few power traces, assuming that the timing di erences canbe seen. They should be noticeably more frequent in the positions of squares
than those of multiplication. This makes it possible to read directly the bits ofthe exponent from the observational data since, except perhaps for the rst multiplication, we can expect the arguments of each multiplication to be suÆciently
independent of each other. So a timing attack is easy to perform on the squareand multiply algorithm using unknown inputs.

3.2 Unknown Plaintext Attack on the m-ary Method

The m-ary method for the exponentiation X ! X e [3, pp. 441{466] is a generalisation of the square and multiply method. The exponent e is expressed interms of a base m,

e =

n
X

ej mj :j =0i
The powers X for i = 1; 2; : : : ; m 1 are precomputed and stored for multiplying

into the partial result when required. The corresponding evaluation rule is

X e = ((   ((X en )m X en 1 )m   )m X e1 )m X e0 :In the process, whenever the non-zero digit ej = i is encountered, the stored
power X i is multiplied in. For example, for m = 4, X , X 2 and X 3 are precom-

puted and stored.
The base m is usually a power of 2, so that computation of the m-th power ofthe partial result consists of several consecutive squarings. The sliding windows
method [4] employs some recoding of the exponent and, among other things,
performs a squaring when the next exponent bit is 0. This means that the evenpowers of X need not be stored. Now we describe our attack.

Walter & Thompson, Distinguishing Exponent Digits

11{ We assume that we do not know the modulus N of the exponentiation, norhave control or knowledge of plaintext inputs.

Suppose we observe k runs of the exponentiation procedure involving di erent
unknown plaintexts A = A1 ; A2 ; : : : ; Ak . These plaintexts should have been randomly generated in some manner but need not be uniformly distributed mod N .
The initialisation process generates Xi = Ai R mod N for input into the exponentiation. After this multiplication (by R2 ), the numbers Xi will be more orless random mod N and belong to the interval [0; R). Hence, after any necessary
modular subtraction, the Xi will be distributed fairly uniformly over each of
three sub-intervals according to the value of R2 mod N .
As before, assume that we can detect whether or not the modular adjustment
has taken place during the j -th multiplicative operation. If k is not too small,then these observations of essentially independent random encryptions enablefairly accurate determinations of the probabilities for the j th operation to require
the modular adjustment. The previous section describes how these data can thenbe used to distinguish squares from multiplies.

{ Now assume also that the initially generated powers of X are used as the B
inputs to the Montgomery modular multiplication process.

Recall that the frequency of extra subtractions depends on the value of theB input. Because multiplications corresponding to the same exponent digit will
make use of the same multiplier B , the expected frequency of extra subtrac-

tions will be the same for both multiplications whatever the set of observations.
However, the randomness of these multipliers means that for di erent exponent
digits, the multipliers will generally have di erent values and individually lead todi erent probabilities for an extra subtraction. So, if a subset of observations canbe identi ed in which the multipliers corresponding to two exponent digit values
have di erent properties, then potentially this will be re ected in di erent average frequencies for the extra subtractions in the multiplications corresponding
to occurrences of these two digits.
In fact, it is possible to determine such observation subsets from any multiplication and, in particular, from behaviour during the initialisation stage when
the powers X i (i = 1; 2; : : : ; m) are formed. For example, for an exponent digit i,partition the observations into two subsets according to whether or not the generating modular multiplication for X i included an extra subtraction. We noted
before that the average values for X i must be di erent for the two sets. This
will result in di erent frequencies for the extra subtraction when X i is used
as a multiplier in the exponentiation and when it is not. Hence, occurrences of
exponent digit i should stand out. We illustrate this in Section 4.
Suppose this process has already been applied for each i to identify which
exponent digits are most likely to be equal to i. Any pair of multiplications
during the exponentiation can then be compared in the same way, providing across-check on the initial assignment.
Let M be the total number of multiplicative operations in the pre-computationand exponentiation combined. Then we could form a k M observation matrix

12

LNCS Vol.

2020 Springer Verlag, 2001, pp 192-207

Z = (zij ) by writing zij = 1 if there was a modular adjustment in the j -th operation (a multiplication or squaring) of the i-th exponentiation, and zij = 0 otherwise. We have argued that there are strong dependencies between the columns Zs
and Zt of the matrix Z if the s-th and t-th multiplication in the exponentiation
routine are multiplications by the same power Xiej of Xi and which correspondto the same digit ej in the exponent. Moreover, there are also strong dependencies between the column corresponding to the precomputations of Xiej andXiej +1 and the columns Zs , Zt corresponding to digit ej . This, again, allows us
to perform more advanced statistical analysis and deduce e ectively the digitsof the exponent from observation of adjustments.

3.3 The Danger of Signing a Single Unblinded Message
In this section we describe how it is possible to attack the exponent of a Montgomery based exponentiation, without the statistical analysis described in sections 2.3 to 2.5, if the modulus and a single plaintext input are known. This
would be the case if an RSA signature were computed directly without use of
the Chinese Remainder Theorem or appropriate counter-measures. The attack
may be applied to both the square and multiply and m-ary methods although,for simplicity, only the square and multiply attack is described here.
Consider the single sequence of modular operations, squares and multiplies,
formed by exponentiation of a known input A with secret exponent e andknown modulus N . For any t, denote the most signi cant t bits of e by e(t) =en en 1 ; : : : ; en t+1 . Let f (t) denote the number of modular operations (including
precomputations) that result from using e(t) as the exponent and let Z = (zj )be the observation vector indicating the extra subtractions. (We don't make useof any initial elements representing the precomputations.)
A binary chop on e may now proceed as follows. Suppose the t most signi cantbits of the exponent are known. We want to establish the value of the next bit.
So far, X = AR mod N and Y = Ae(t) R mod N can be computed independentlyof the target device. Therefore Y is known and the observation vector Z 0 = (zj0 )obtained from this exponentiation with e(t) should match the rst f (t) elementsof Z exactly.
To determine e(t + 1) compute the two Montgomery operations Y := Y N Y
followed by Y = Y N X . Extend the observation vector Z 0 = (zj0 ) by adding
the two extra elements associated with these operations. Elements f (t)+1 shouldmatch in Z and Z 0 since the same square is being performed. If they don't match,a previous bit of e has been incorrectly assigned and backtracking is necessary
to correct it [5]. Assuming the elements match and earlier bits were correctly
assigned, if elements f (t)+2 do not match in both vectors then certainly en t =0 since di erent operations must be being performed for the two observation
vectors. Otherwise, we assume en t = 1 and continue.
Backtracking to x incorrect bits is not expensive, and one simply has tochoose exponent bits which are consistent with the vector Z . The average numberof incorrect bits chosen before an inconsistency is discovered is very small. For

Walter & Thompson, Distinguishing Exponent Digits

13

simplicity, suppose that a subtraction occurs 1 in 4 times for both multiplications
and squares, and that the numbers of subtractions required in two successive
operations are independent. (As noted in section 2, this is close to what happens
in reality.) Then the probability of a match between two elements is about 85 whena previous bit has been incorrectly assigned. So the average number of matchingelements after picking an incorrect bit is just (1 58 ) 1 = 38 . This shows that asingle power trace suÆces to determine e completely except perhaps for the nal
two or three bits and they are easily determined by comparing nal outputs,
which should equal Y = Ae mod N  1 N (Ae R).
We conclude that, as a matter of routine, any document digest should be
combined with an unseen random component prior to signing. In particular [5],if v is random and d is the public key associated with e, then the attack is
confounded by rst replacing A with ARv d , exponentiating as before, and thendividing by v mod N . However, such a blinding process fails to disrupt theattacks of x3.1 and x3.2 since they do not depend on knowledge of the inputs.

4 Computer Simulation
We built a computer simulation of 4-ary exponentiation for 384-bit exponents
using 8-, 16- and 32-bit arithmetic and an implementation of Montgomery multiplication which included the nal conditional modular adjustment which has
been assumed throughout. The size of the arithmetic base made no di erence tothe results, as one can easily ascertain.
First, a random modulus and exponent were generated and xed for the set ofobservations. Then a random input in the range (0,N ) was generated and scaledby R in the usual way, namely Montgomery-multiplying it by R2 . This rst
scaling enabled the observations to be partitioned according to whether or not
an extra subtraction occurred. If X was the output from this, the next processcomputed and stored X 2 and X 3 . The output data was partitioned according
to whether or not subtractions were observed here too, giving 8 subsets in all.
The exponentiation algorithm then repeatedly squared the running total twice
and, according to the value of the next pair of exponent bits, multiplied in either
X , X 2 or X 3 . These three initial powers of X were always chosen as the \B "argument in the modular multiplication. The A input was the accumulating
partial product and therefore the output from two successive squares. For eachof the 8 subsets, the total number of extra subtractions were recorded for each
multiplicative operation in the exponentiation.
As in Schindler [8], squares showed up clearly from multiplications by theirlower number of subtractions when the full set of all observations (the union of
the 8 subsets) was considered. To complete the determination of the exponent,
it was necessary to establish which of X , X 2 or X 3 had been used in each
multiplication. Already, a sequence of 4 successive squares indicated the positionsof all the 00 bit pairs in the exponent. The partitioning into 8 subsets resulted
in values for the B inputs which had di erent average properties. Consequently,
for each subset, di erent frequencies of extra subtractions were observed. For

14

LNCS Vol.

2020 Springer Verlag, 2001, pp 192-207

multiplications with the same value of B the proportion of extra reductions inthe subset tended to the same limit, but for those with di erent values of B ,as expected, the limits were di erent. Selecting di erent subsets of the partition
accentuated or diminished these di erences. Combining the results from the best
di erentiated subsets, it was easy to determine which exponent bit pair had
been used. Not only did the investigation enable the deduction of equivalenceclasses of equal digits, but knowledge of which subset was associated with which
combination of subtractions in the initialisation process enabled the digits tobe correctly assigned. Only the rst one or two exponent digits were unclear,and this was because of the lack of independence between the arguments in thecorresponding multiplications.

Fig. 2. Simulation: Set for Squares with Subtraction

Fig. 3. Simulation: Subset for Cubes without Subtraction
It turned out that it was most helpful to look at the one third of observations
for which the initial computation of X 2 generated an extra subtraction andpartition this set according to whether the initial formation of X 3 had an extra
subtraction or not. For both subsets, exponent digit 1 = 014 generated the largest
number of extra subtractions, digit 2 = 104 the next largest and digit 3 = 114
the smallest number. So a graph of digit positions marked along a frequency

Walter & Thompson, Distinguishing Exponent Digits

15

axis showed the digit positions clustering around three distinct sites. Switching
between the two sets shifted the relative position of the digit 3 = 114 instancesin relation to the other two, making it possible to distinguish those digits fromthe others.
This is illustrated in Figures 2 and 3, where the three thick lines under thegraph bracket together the positions of equal digits. The two sets enable animmediate, clear, correct association of digits with exponent positions. The illustrations are for 1000 samples when N=R  0:99. Certainly, a smaller sample
would have suÆced: half this number can almost be done by eye. For N=R  0:51,
about twice these sample sizes are required for the same degree of resolution.
Notice that these sample sizes are independent of the key size because the probability of an extra subtraction is independent of the key size.
We did not attempt to perform a thorough analysis of the simulation output to see how few observations were necessary to guarantee that the correct
exponent could be obtained. The digits which were most likely to be incorrectly
assigned were those with subtraction frequencies furthest from the average forthe digit. With suÆcient observations to separate most of the non-zero digits into
one of three classes, the potentially incorrect digits were clearly visible. Then,providing the number of such digits was small enough, every alternative could
have been tested individually using other known data. Of course, in the presenceof noisy readings, many more observations may need to be made, whilst if thedata is clean enough, the results show that, in the absence of counter-measures,the safe lifetime of the key is too short for practical purposes.

5 Discussion
Any modular multiplication algorithm used in a smart card may su er a problematic conditional subtraction of the type considered here in order to keep theresult from over owing. This is true not just for Montgomery modular multiplication but also for the classical algorithm, where the multiple of the modulus for
subtraction is estimated from the top two or three digits of the inputs. Since theresult is an approximation, a further conditional subtraction may be requested
to obtain a least non-negative result. This subtraction is also open to attack in
the above manner.
If the conditional modular reduction is performed every time and the previous
value or new value is selected as appropriate, the movement of data may still
betray whether or not the reduction is happening. Alternatively, an over ow
bit can be stored and processed like another digit of the operand. This may
cause exactly the timing variation that we should be trying to avoid. If not, thenprocessing a top digit of 0 or 1 might still be easily recognised.
A general conclusion is therefore that N should be reduced away from a wordboundary or register working length suÆciently for the modular multiplication
algorithm to avoid any over ow to an extra word.

16

LNCS Vol.

2020 Springer Verlag, 2001, pp 192-207

6 Counter-Measures & Conclusion

A detailed analysis has been presented showing how conditional subtractions
at the end of Montgomery modular multiplications can be used very e ectively
to attack an RSA exponentiation with unknown modulus and secret exponent.
The attack does not require knowledge of the plaintext input and can be applied
successfully to the m-ary and sliding windows methods of exponentiation as wellas to the standard square-and-multiply methods. Moreover, it applies in thesame way to many other implementations of modular multiplication.
Computer simulations showed that if the data is clean enough to pick out
each subtraction with high accuracy, then very few encryptions (under 1000)
need to be observed before the exponent can be determined as a member of asmall enough set for all possibilities to be tested individually. Furthermore, thisnumber is independent of the key length.
There are simple counter-measures to avoid the problem. One of these is tomodify the exponent by adding a random multiple of (N ) before each exponentiation [5] so that the exponent digits are changed every time. This defeats
the necessary averaging process over many observations which is the usual key
to a successful side-channel attack.
Acknowledgment. The authors would like to thank A. V. Borovik who contributed to the key ideas presented here through a private communication [1].

References

1. A. V. Borovik & C. D. Walter, A Side Channel Attack on Montgomery Multiplication, private technical report, Datacard platform7 seven, 24th July 1999.
2. J.-F. Dhem, F. Koeune, P.-A. Leroux, P. Mestre, J.-J. Quisquater & J.-L. Willems,
A practical implementation of the Timing Attack, Proc. CARDIS 1998, Lecture
Notes in Computer Science, 1820, Springer-Verlag, 2000, 175{190.
3. D. E. Knuth, The Art of Computer Programming, vol. 2, Seminumerical Algorithms, 2nd edition, Addison-Wesley, 1981.
4. C
 . K. Koc, High Radix and Bit Recoding Techniques for Modular Exponentiation,
International J. of Computer Mathematics, 40 (1991) no. 3-4, 139{156.
5. P. Kocher, Timing attack on implementations of DiÆe-Hellman, RSA, DSS, andother systems, Proc. Crypto 96 (N. Koblitz, ed.). Lecture Notes in Computer Science, 1109, Springer-Verlag, 1996, 104{113.
6. P. L. Montgomery, Modular multiplication without trial division, Mathematics ofComputation, 44 (1985), no. 170, 519{521.
7. R. L. Rivest, A. Shamir and L. Adleman, A method for obtaining digital signaturesand public-key cryptosystems, Comm. ACM, 21 (1978), 120{126.
8. W. Schindler, A Timing Attack against RSA with Chinese Remainder Theorem,
Cryptographic Hardware and Embedded Systems (CHES 2000), Christof Paar &C etin Koc, editors, LNCS 1965, Springer-Verlag, 2000, to appear.
9. C. D. Walter, Montgomery Exponentiation Needs No Final Subtractions, Electronics Letters, 35, no. 21, October 1999, 1831{1832.
10. C. D. Walter, An Overview of Montgomery's Multiplication Technique: How tomake it Smaller and Faster, Cryptographic Hardware and Embedded Systems(CHES '99), C. Paar & C. Koc, editors, LNCS 1717, Springer-Verlag, 1999, 80{93.