
CARDIS '02 Paper
[CARDIS '02 Tech Program Index]
Breaking the LiardetSmart
Randomized Exponentiation Algorithm Colin D.
Walter Comodo Research Laboratory 10 Hey Street, Bradford, BD7 1DQ, UK colin.walter@comodo.net www.comodo.net Abstract. In smartcard encryption and signature applications, randomised
algorithms are used to increase tamper resistance against attacks based on side
channel leakage. Recently several such
algorithms have appeared which are suitable for RSA exponentiation and/or ECC
point multiplication. We show that under
certain apparently reasonable hypotheses about the countermeasures in place and
the attacker’s monitoring equipment, repeated use of the same secret key with the
algorithm of Liardet and Smart is insecure against any side channel which leaks
enough data to differentiate between the adds and doubles in a single scalar
multiplication. Thus the scalar needs to
be blinded in the standard way, or some other suitable countermeasures
employed, if the algorithm is to be used safely in such a context. Key words: mary
exponentiation, LiardetSmart randomized algorithm, ECC, addition chains,
sliding windows, additionsubtraction chains, power analysis, SPA, SEMA,
blinding, smartcard. 1 Introduction Major progress in the theory and practice of side
channel attacks [5, 6] on embedded cryptographic systems threatens to enable
the capture of secret keys from single
applications of cryptographic functions [10, 11, 14]. This is particularly true for the more
computationally intensive functions such as exponentiation, which is a major
process in many cryptosystems such as RSA, ECC and DiffieHellman. Timing attacks on modular multiplication can usually
be avoided easily by removing datadependent conditional statements [16], but,
with timing variations removed, attacks which make use of datadependent
variation in power and electromagnetic radiation become easier. Initial attacks of this type required
averaging over a number of exponentiations [8].
One countermeasure is to modify the exponent from e to e+rg
where r is a random number, typically
32bits, and g is the order of the
(multiplicative) group in which the exponentiation is performed [5]. This results in a different exponentiation
being performed every time. However, if
squares and multiplications can be distinguished during a single
exponentiation, then use of the standard binary exponentiation algorithm immediately
leads to exposure of the secret key. For elliptic curve cryptography (ECC), the most
efficient schemes for point addition and point doubling involve different
numbers of operations in the field over which the curve is defined, and these
numbers vary depending on the representation used for the curve. A countermeasure which reduces the
likelihood of distinguishing between these point operations involves equalising
the number and type of the component field operations [12] or making the point
addition look exactly the same as two point doublings [1]. However, squares and multiplications in the field
behave differently [13] and so there is no reason to believe that such recoding
will necessarily hide fully the distinction between point additions and point
doublings: for example, in [12], field squares appear for point additions, but
field cubes when the same formula is used for point doublings. Side channels can distinguish these if the
Hamming weight of arguments can be deduced.
So exponentiation algorithms are chosen in which there is still an
ambiguity in the correspondence between multiplications (i.e. point additions
in ECC terms) and properties of the secret key (such as bit or digit values). Mary
exponentiation [4] for m > 2
provides one solution because each addition represents an unknown choice from a
set of several nonzero digits. If the same unblinded key value is reused for many exponentiations,
there is a danger that the repeated use of the same operand can be determined [14]. This would enable individual digits of the
exponent base m to be identified and
hence the key recovered. Unfortunately,
particularly for ECC as opposed to RSA, applying the above exponent blinding technique is
expensive when the secret key is typically only 192 bits. It adds about 17% to the cost of point
multiplication. Hence randomised
exponentiation algorithms may be a preferred option for ECC. There are currently several algorithms which randomise
the operations associated with specific inputs so that the exponentiation
scheme is different on successive runs with the same data [7, 9, 17, 2, 3]. That of Liardet and Smart [7] uses a sliding
window of random, variable width. If the
attacker’s equipment is insufficient to obtain information from a single EC
point multiplication, then it seems that averaging over different
multiplications with the same key would dilute any data dependency in the side
channel leakage. However, we will show
here that if individual point multiplications do leak information about what
operation is being performed, then the secret key can be obtained
straightforwardly. Indeed, one might
even be better off with mary multiplication. We begin by recalling the algorithm and looking at various
parameters which might be chosen to improve efficiency or security. Next, the assumptions about the attacker’s
equipment and cryptosystem countermeasures are outlined. These are initially quite tight to make the
presentation of the attack easier. The
attack starts with extracting a least significant digit, and then uses this
repeatedly to reconstruct one possible representation for the secret key. An essential part of the discussion is an
assessment of the probability that the attack can be completed successfully. Before
concluding with some countermeasures and alternatives, we explain how the
attack can still be performed in a more realistic environment where the side
channel leakage is much poorer. 2 The
Algorithm This section contains a brief outline of the
(exponentiation) algorithm of Liardet and Smart. Because it generates an additionsubtraction
chain rather than simply an addition chain, inverses have to be computed when
it is applied. This means that
applications to RSA cryptography are unlikely because of the expense of
computing inverses. However, in elliptic
curve cryptography (ECC), inverses are essentially for free. Hence, we will assume the algorithm is
applied to an additive group, such as that formed by the points on an elliptic
curve, and use appropriate terminology. Processing
of the secret key k therefore
produces a sequence of instructions which result in additions (A) and doublings (D) of group elements. Suppose we wish to compute the element Q = kP for a given positive integer k (the secret key) and a given member P of some group E. As in mary exponentiation, Liardet and Smart
precompute the odd multiples iP of P for integers i Î (–½m, ½m] where m = 2^{R}, and
then employ the standard sliding windows technique but with a window which has
a random width showing up to R bits. In other words, k is recoded to obtain digits k_{i}
(0 ≤ i ≤ n)
which are determined using a randomlychosen variable base m_{i} which divides m. The digits are chosen in the order k_{0}, k_{1}, ..., k_{n}
and the digit representation k_{n}k_{n}_{–}_{1}...k_{1}k_{0} satisfies k = ((...((k_{n})m_{n}_{–}_{1}+k_{n}_{–}_{1})m_{n}_{–}_{2}+...)m_{1}+k_{1})m_{0}+k_{0}
(1) The group element multiplication processes these
digits from most to least significant following the related
scheme defined by kP = m_{0}(m_{1}(...m_{n}_{–}_{2}(m_{n}_{–}_{1}(k_{n}P)+k_{n}_{–}_{1}P)+...)+k_{1}P)+k_{0}P (2) 2.1 Code for the Key Recoding More explicitly, if minmod is the function which returns a residue of minimal
absolute value, the algorithm for choosing the digits is this: Randomised Signed mary Window
Decomposition [7]: i ← 0 ; While k > 0 do { If (k mod 2) = 0 then { m_{i} ← 2 ; k_{i} ← 0 ; } else { Randomly
choose base m_{i} Î {2^{1},2^{2},..., 2^{R}}
; k_{i} ← k
minmod m_{i} ; } ; k ← (k–k_{i})/m_{i}
; i ← i+1 ; } ; Here, both 1 and _{} could be allowed as
digits for base 1, but that involves the added complication of a random bit to
decide which to select, and also (to avoid nontermination) restricting the
choice to only 1 when k reaches 1. Our attack would work also in these
circumstances with few changes. 2.2 Efficiency Considerations There are still some parameters to be chosen in the
algorithm. Varying these affects
efficiency, but there are also security implications. As we see later, certain choices will
increase the difficulty of mounting the attack, forcing, in particular, more
samples to be required. The value for R
has the greatest effect on efficiency. In
elliptic curve applications, subtraction may have the same cost as addition. Then it will be unnecessary to store the
negative precomputed multiples of the input point. So only space for 2^{R}–2 multiples is likely to be required. Increasing R improves speed, but with diminishing returns for the space
required for precomputed values. No suggestions are made in [7] about how to choose the
m_{i} randomly. A uniform distribution is not very efficient,
and indeed perhaps the least secure under this attack. It is most efficient to make the maximum
possible use of the precomputed values by choosing the maximum base size 2^{R} always. But, to maintain generality for later,
suppose m_{i }= 2^{j} is chosen with probability p_{j} when k is odd and p_{0}
= 1 is the probability of selecting base 2 when k is even. Choosing p_{R}
= 1 means that m_{i} = 2^{R} whenever k is odd. This yields the usual mary sliding window method with fixed m = 2^{R}. Taking R
= 1 yields the usual binary “squareandmultiply” algorithm. However, such choices would remove any
nondeterminism from the sequence of point operations. Observe that biasing in the choice of m_{i} does not change the
uniformity in the distribution of residues k
mod m_{i} inherited from k,
assuming k is randomly chosen. This means that every new key value k generated during the recoding retains
the same random properties: in particular, residues modulo 2^{j} will be uniform for every
key encountered. 3 The Attack 3.1 Introduction & Initial Hypotheses The purpose of randomised exponentiation algorithms is
to frustrate side channel analysis by an attacker. In particular, they are countermeasures
against using knowledge of the exponentiation process to extract the secret key
k.
Several different levels of leakage are possible, depending on the
resources of the attacker. A poor
signaltonoise ratio (SNR) means that many samples have to be taken, and
averaging the side channel leakage is one way of improving the SNR. So a critical parameter is whether or not the
attacker’s equipment is good enough for him to extract sufficient meaningful
data from the side channel trace of a single scalar multiplication. If it is, then the standard key blinding
described earlier suddenly fails to provide the data hiding protection afforded
by averaging away local data dependencies.
Improved equipment and laboratory techniques mean that this barrier
might soon be breached without excessive expenditure [10, 11]. The categories of leakage which could be considered
include the following: i) individual point operations can be observed
on power, EM or other side channel traces; ii) point doublings and point additions can be
distinguished from each other; iii) reuse of operands can be observed; and iv) operand addresses can be deduced. Point (i) may hold simply because program instructions
and data need to be fetched at the start of each point operation, and these
cause different effects on the side channels than field operations. Point (ii) may then hold as a result of
different patterns of field operations for point additions than for point
multiplications. Properties (iii) and
(iv) might hold as a result of being able to deduce Hamming weights of data and
address words travelling along the bus. Randomisation prevents the obvious averaging of the
traces of many point multiplications which was used in initial power analysis
attacks on the binary “squareandmultiply” algorithm. Here every point multiplication determines a
different sequence of doublings and additions.
With matched code for additions and doublings, averaging may hide the
difference between the two operations because they are no longer separated in
time, but in current implementations such averaging will certainly reveal the
start and end of the individual point operations which make up the scalar
multiplication. The attack described here requires the SNR to be good
enough to extract some useful data from single multiplications on the curve. Specifically, initially we assume that ·
Adds
and doublings can always be identified correctly and distinguished from each
other using traces obtained from side channel leakage for a single point
multiplication, and ·
A
number of traces are available corresponding to the same secret key value
applied to different scalar multiplications. Both of these hypotheses will be relaxed later to some
extent, providing a more realistic scenario. 3.2 Overview of the Attack & Notation The outline of the attack is as follows. For simplicity, by the first hypothesis, ·
Every
trace can be viewed as a word over the alphabet {A,D}. Every occurrence of an A (add) in the trace splits the word into a prefix and a suffix
which correspond to two integers k_{p}
and k_{s} that are precisely
defined in terms of k and the
position of A in the trace. All traces determine the same values to
within ±1. By looking at the patterns to
the left of a given A, one obtains
the residue of k_{p} modulo a
small power of 2, and hence a few bits of k. Repeating this for the position of each A enables all the bits of k to be recovered. Definition. The position of a specific instance of character A or D in a trace word is the
number of Ds which are to the right of the selected character. We will exploit a close relationship between positions
in which A appears in traces and bits
which are 1 in the corresponding position of the binary representation of k. In order to be able to give examples, we fix the
character order of words over {A,D} to correspond to a lefttoright processing
order. Thus, the digit sequence 1_{2}0_{2}_{}_{4}0_{4}, with most significant bit on the
left, is processed from most to least significant bit, i.e. from left to right,
and so would result in the word DADDDADD. There are As
in positions 2 and 5, and Ds in
positions 0 to 5. In fact, every A is paired with a preceding D with the same position, and so one
could view the DA combination as a
single character. Then the position
would correspond directly to a character index, counting from 0 at the right
hand end, as in a binary representation. The initial DA
corresponds to the digit 1_{2} and might be omitted if efficient
initialisation takes place instead. Assuming
this is the case, we will delete any initial Ds but leave the initial A
as an unambiguous reminder that there is an initial digit to take into account. Thus words always commence with A.
In the above example, ADDDADD
will be the word corresponding to the given digit sequence. 3.3 Properties of Key Digits We now look at the sequence of digits generated by the
LiardetSmart algorithm. The notation
used here is the same as for a fixed base, and many standard properties have
analogues. Lemma 1. Suppose k_{n}k_{n}_{–}_{1}...k_{1}k_{0} is a digit representation of k generated by the LiardetSmart algorithm,
with sequence m_{n}, m_{n}_{–}_{1}, ..., m_{1},
m_{0} of bases. For some i, let k_{p}^{(i)} denote the integer
corresponding to the prefix k_{n}k_{n}_{–}_{1}...k_{i}
and let k_{s}^{(i)}
denote the integer corresponding to the
suffix k_{i}_{–}_{1}...k_{1}k_{0}. Then
k = k_{p}^{(i)}m^{(i)}+k_{s}^{(i)} where m^{(i)} = _{} and k_{s}^{(i)} < m^{(i)}. This lemma is obvious from the definition of the digit
sequence given by equation (1) except, perhaps, for the last part. That part follows easily by induction. Digit k_{i}
is chosen with k_{i} ≤ ½m_{i} ≤ m_{i}–1. This property for i = 0 starts the induction. Then
the induction step is k_{s}^{(i+1)} = k_{i}m^{(i)}+k_{s}^{(i)} < (k_{i}+1)m^{(i)} ≤ m_{i}m^{(i)} = m^{(i+1)}. We will continue to use the notation m^{(i)} for _{} and k_{p}^{(i)} and k_{s}^{(i)} for the key values associated respectively
with the prefix k_{n}k_{n}_{–}_{1}...k_{i}
and the suffix k_{i}_{–}_{1}...k_{1}k_{0} of the digit sequence. The next lemma uses the equality and bound of
Lemma 1 to identify two possible values for k_{s}^{(i)}, corresponding to it being a
positive or negative residue of k
modulo m^{(i)}: Lemma 2. With
the previous notation, either
i) k_{s}^{(i)} = k
mod m^{(i)} and k_{p}^{(i)} = k div m^{(i)}, or ii) k_{s}^{(i)} = (k
mod m^{(i)})–m^{(i)} and
k_{p}^{(i)} = (k div m^{(i)})+1 where mod returns
the least nonnegative residue, and
div is integer division given by rounding
down the real quotient. This shows that, whatever choices are made for the
base elements, a given digit suffix can determine only one of two possible
values when the product of the corresponding base elements is fixed. We would like at least the occurrence of the
one which will make the corresponding prefix odd because it leads to an
addition (A) which can be used to
identify a corresponding point in the trace. Lemma 3. For all powers 2^{j}
≤
k, there is a choice of base elements m_{i'} and an integer
i such
that 2^{j} = m^{(i)}. On average, for at least 1–2^{–}^{R} of
all values of j, there are choices which make k_{p}^{(i)} odd, and, for at least half of all values of j,
there are choices which make k_{p}^{(i)} even. Proof. The existence of the choice of basis elements is clear: taking m_{i'} = 2 for all i' allows one to satisfy the equality
for m^{(i)} with i = j. For that choice, k_{i} is the usual index i bit of k, and takes
either parity with equal probability. It
is the lowest bit of k_{p}^{(i)}, and so k_{p}^{(i)}
is the desired parity with probability ½.
Other choices of base elements exist, and they may
result in k_{p}^{(i)} being odd even when the bit of
interest in k is even. This increases the average number of cases
for which oddness occurs. Instead of
choosing m_{j}_{–}_{1} = 2, we try choosing m_{j}_{–}_{i'} = 2^{i'}
for any i' with 1 ≤ i' ≤ R. The ability to select them depends on a
corresponding bit of k_{p}^{(j}^{–}^{R}^{)} being 1 (otherwise base 2 must be chosen). These bits are independent and so the
alternative bases can be chosen with probability ½. Each will give odd parity to the next k_{p} if chosen. Hence the prefix key corresponding to 2^{j} can be made odd with
probability at least 1–2^{–}^{R}. ■ Of course, this argument just gives a lower bound on
how many js will give rise to two key
prefix and two suffix values. It doesn’t
guarantee that when both values are possible they will both appear with nonnegligible
frequencies. The actual relative
frequencies appear to depend on the lowest R
bits of the k_{p}
corresponding to m^{(i')} = 2^{j}^{–}^{R}. However, in
the next section, a lower bound on the ratio will be produced as necessary for
each choice of these bits. 3.4 Recovering One Digit of k In this section we show how to recover the least
significant digit k_{0} and
associated base m_{0} in one
representation of k and how to
identify the subset of traces which correspond to the associated prefix key k_{p} such that k = k_{p}m_{0}+k_{0}. Exactly the same process yields other digits
of k independently. Those digits can then be assembled together
to give k in the manner described in
the next section. If Tr is the
full set of all sample traces, then we denote by Tr_{i} the set of traces obtained by taking each member of Tr and deleting the suffix to the right
of, but not including, the D of
position i. Thus Tr_{0}
= Tr.
Tr_{i} is partitioned
into two complementary subsets: Tr_{i}^{A}
which consists of those traces which terminate with A, and Tr_{i}^{D}
which consists of those traces which terminate with D. We need to identify one
of these subsets for each digit choice so that its neighbour to the left can be
selected correctly. Tr_{i}^{A} always represents the odd choice for k_{p}^{(i)}, but some traces in Tr_{i}^{D}
may contain only some of the operations for the rightmost prefix digit, and so
not represent any k_{p}^{(i)} properly. The derivation here does make specific use of the fact
that in this implementation _{} is not allowed as a
digit for base 2. Similar arguments
apply when _{} is allowed, but there
is a duality which leaves a complicating ambiguity between the two values of ±k_{s} throughout the
reconstruction process. This is only
resolved when the complete value of k
is reconstructed and under the assumption that the true sign of k is known. Lemma 4. Select any trace for key k. Then
k is
exactly divisible by 2^{i}
where i is the uniquely defined integer
such that AD^{i} is a suffix of the trace. Proof. Clearly, if k is divisible by
2^{i} then base 2 must be
chosen for the lowest i digits, which
are then all zeros. This leads to a
character sequence D^{i} of i consecutive Ds as a suffix in every trace.
If k is not divisible by 2^{i+}^{1} then, whatever
the next choice of base, the digit will be nonzero and hence cause A to be appended to the sequence,
yielding the suffix AD^{i}. ■ This result enables these i occurrences of D to be
identified with i least significant
digits 0, each of base 2. Moreover, all
traces confirm this conclusion. So,
removing the digits one at a time, Lemma 5. If every trace in Tr has
final character D then we may take k_{0} = 0, m_{0} = 2 and the traces of Tr_{1}
all represent the associated k_{p}. If k is odd,
no digit has been deduced yet, and further work must be done. Lemma 6. Suppose k
≡ 1 mod 2^{i} where i ≤ R. Then k ≡ 2^{i}+1 mod 2^{i+}^{1}
if Tr contains a trace with
suffix AD^{i}A. If k ≡ 2^{i}+1 mod 2^{i+}^{1} then the probability that Tr contains no
trace with suffix AD^{i}A is (1– p_{i}')^{Tr}
where p_{i}' = p_{1}+p_{2}+...+p_{i}. Proof. If k ≡ 1 mod 2^{i+}^{1} then a base of
m_{0} = 2^{i}^{+1} or larger will lead to suffix D^{i+}^{1}A.
However, a smaller base m_{0}
= 2^{j} will lead to suffix D^{j}A with digit k_{0} = 1 and the forced
selection of base 2 at least i+1–j
times. This again leads to suffix D^{i}^{+1}A. Now suppose k
≡ 2^{i}+1 mod 2^{i}^{+1}. A base of m_{0}
= 2^{i}^{+1} or
larger again leads to suffix D^{i+}^{1}A.
However, the choice of base m_{0}
= 2^{i} means lowest digit k_{0} = 1 and next digit
determined by k div 2^{i}, which is odd. Hence the suffix is AD^{i}A for that choice.
Similarly, a base m_{0}
= 2^{j} with j < i, will lead to suffix D^{j}A,
digit k_{0} = 1 and k_{p} ≡ 2^{i–j} mod 2^{i–j}^{+1}.
So this choice is followed by the forced selection of base 2 exactly i–j times with associated digit 0. The
subsequent digit is then odd, resulting in the overall suffix AD^{i}A. Thus, suffix AD^{i}A
guarantees k ≡ 2^{i}+1 mod 2^{i}^{+1} and it occurs precisely when the least significant
base choice is 2^{j} with j ≤ i. These choices occur for a
given trace with probability p_{i}'
= p_{1}+p_{2}+...+p_{i}. Hence suffix AD^{i}A will not happen for any trace in Tr with probability (1–p_{i}')^{Tr}.
■ Lemma 7. Suppose k
≡ 1 mod 2^{i}. If Tr contains
a trace with suffix AD^{i}A then k ≡ 2^{i}+1 mod 2^{i}^{+1},
we may take k_{0} = 1 and m_{0} = 2^{i}, and the traces
of Tr_{i}^{A} all
represent the associated k_{p}. This lemma deals with the recognisable instances of k ≡ 2^{i}+1 mod 2^{i}^{+1}. When base 2^{j} is chosen for any j
≤ i, the suffix is AD^{i}A for these cases. As this occurs in p_{i}' of cases, so we expect Tr_{i}^{A} to contain approximately p_{i}'Tr elements. We will assume k
≡ 1 mod 2^{i}^{+1}
if there is no suffix AD^{i}A
but we know k ≡ 1 mod 2^{i}. By Lemma 6, this introduces a small
probability of error which can be decreased by taking a larger sample if
necessary, or by further analysis, such as through a more exhaustive analysis
of suffixes and their expected frequencies than there is space for here. Note, however, that if p_{i}' = 0 then this choice of m_{0} will not resolve which residue mod 2^{i}^{+1} is correct. Hence an increase in security might be
obtained by having p_{1} = p_{2} = ... = p_{i} = 0 where i is as large as possible. Theorem 1. Assume each base 2^{i}
is selected with probability p_{i}
for odd key values, and digit _{} is only used for bases greater than 2. Let p_{i}'
= p_{1}+p_{2}+...+p_{i}
and _{} = 1–p_{i}'. Suppose k is a random odd integer
that has generated trace set Tr and
j (1 ≤ j ≤ R+1) is
such that Tr contains no trace with suffix AD^{i}A for any i < j. Then
k ≡ 1 mod 2^{j} with probability
_{}. Proof. We prove this by induction on j. For j
= 1 the statement claims nothing, and so holds.
For the induction step, assume the statement holds for some j ≤ R. Suppose also that Tr contains no trace with suffix AD^{i}A for any i ≤ j.
By the induction hypothesis, k
≡ 1 mod 2^{j} with
probability _{}. Since k is
random, the two possibilities for k mod
2^{j}^{+1} are
equally likely. So, by Lemma 6, no
occurrence of suffix AD^{j}A
means k ≡ 1 mod 2^{j}^{+1} with
probability _{}. This factor just
needs multiplying into the product to obtain the claim for j+1 in place of j. ■ Theorem 2. With assumptions and notation
as in Theorem 1, suppose k is odd and j is minimal such that 1 ≤ j
≤
R+1 and Tr contains a trace with suffix AD^{j}A. Then
k ≡ 2^{j}+1 mod 2^{j}^{+1} with probability _{}. If j ≤ R
we may take k_{0} = 1 and
m_{0} = 2^{j} and then the set of traces for the
associated k_{p} is Tr_{j}^{A}. Proof. Theorem 1 shows that, for the given definition of j, k ≡ 1 mod 2^{j} with probability _{}. If k ≡ 1 mod 2^{j}^{+1} then, as in the proof of Lemma 6, all
traces must terminate with suffix D^{j}^{+1}A, which is not the case. Hence k
≡ 2^{j}+1 mod 2^{j}^{+1} with the
stated probability. For the base m_{0}
= 2^{j}, k ≡ 1 mod m_{0}
and so the associated digit is k_{0}
= 1. However, k_{p} = k div 2^{j} is odd, which forces the
next digit to be nonzero. Hence A is the next operation leftwards after
the suffix D^{j}A which
corresponds to m_{0}. Thus, the relevant traces for the next digit
are those of Tr_{j}^{A}. ■ The values of k
for which no least significant digit has yet been assigned are those satisfying
k ≡ 1 mod 2^{R}^{+1}. Picking
maximal base m_{0} = 2^{R} gives k_{0} = 1 and makes k_{p}
even. The associated set of prefix
traces should be Tr_{R}^{D}. A possible difficulty with this definition is
that for some traces removing the suffix D^{R}A
may split subsequences which correspond to one digit. However, every choice of base 2^{i} corresponds to a suffix D^{i}A where i ≤ R, and must
be followed by a number of instances of base 2 with digit 0 which makes the
total modular division by at least 2^{R}^{+1}. Hence the suffix D^{R}A corresponds to the operations for a whole number of
digits. Therefore Tr_{R}^{D} does indeed contain traces which
represent only operations for sequences of complete digits, and so those traces
all represent the same key value. Theorem 3. With the same assumptions and
notation as in Theorem 1, suppose every trace in Tr has suffix D^{R}^{+1}A.
Then, with probability _{}, k ≡ 1 mod 2^{R}^{+1} and we may pick m_{0} = 2^{R}. For this choice k_{0}
= 1, k_{p} is the common key for Tr_{R}^{D}, k_{p} is even, and Tr_{R}^{D} = Tr_{R} has the same cardinality as Tr. 3.5 Combining Digits to Recover k For every position
j at which there is an occurrence of A
in some trace of Tr, the procedures
of the previous subsection can be applied to Tr_{j}^{A} to obtain a base and digit at that point. These digits are used when determining a
digit sequence for k. Starting at j = 0, the digits are selected iteratively. As well as a digit and base, each trace set Tr_{j}^{A} gives rise to
another trace set defined at some position j'
> j. We will show that: ·
For
this definition of j', the next digit
is determined by whichever is appropriate of Tr_{j'}^{A} or (Tr_{j}^{A})_{R}^{D}. Here we need to check on the definition of the trace
subsets. If applied iteratively, the
procedures above would actually determine smaller and smaller subsets: each
time we apparently take a subset of the traces from the previous step. However, because only two key values (one odd,
one even) are associated with any position, every prefix which represents the
operations of a complete number of digits must correspond to the odd key if it
terminates with A and the even key if
it terminates with D. Of course, every trace prefix terminating
with A must consist of the operations
for a whole number of digits since A
cannot appear in the middle of the sequence of operations for a single digit. So every trace in Tr_{j'}^{A} is generated from a key value which is
common to them all. Hence, the full set Tr_{j'}^{A} can be used
to determine the next digit, not just the subset of Tr_{j}^{A} determined by the procedures above. In the case of the prefix trace set Tr_{j}_{+R}^{D}, it
is not clear which traces are generated by a complete key. In some cases, the final D may not be the final operation of the digit sequence from which
it was derived. Hence, the subset (Tr_{j}^{A})_{R}^{D} must be used,
not Tr_{j}_{+R}^{D}. However, the
construction observed that every such trace had suffix D^{R}^{+1}A. So (Tr_{j}^{A})_{R}^{D} has the same
cardinality as Tr_{j}^{A}.
Hence the trace subsets bulletted above
are indeed the correct ones to use for the key digits, and they do not
progressively decrease in size. The process of digit determination only begins to fail
once a leading instance of A is
encountered: Theorem 2 guarantees progress up to that point. Traces are not all the same length. Some will use a large base for the most
significant digit. Their initial Ds are deleted, giving them fewer
instances of D overall, making their
traces shorter. These traces are simply
discarded when fully processed. The
procedures above still apply to the subset.
Again, following Theorem 2, further digits can still be defined until
the trace set becomes empty. However,
once the first (i.e. shortest) traces run out, the remaining key is
representable by a single digit, so it is bounded in absolute value by 2^{R}^{–}^{1}–1. Each increment of the position in the trace
set reduces the representable key by a factor of 2. Eventually, assuming there are enough traces,
the initial A of the longest trace
has a digit bounded by 1, and so must be 1.
Hence k is completely
determined. “Enough” traces would be
present if, for example, base 2 were chosen for the most significant digit. Insufficient traces just increases the number
of possible values of k which may
need testing by a small factor (under 2^{R}^{–1}). 3.6 The Probability of Error We have been careful to obtain the probability of
error in each digit in order i) to see if it is feasible to recover the key and
ii) to see how the probabilities p_{i}
might be adjusted in the algorithm definition to provide improved security. The procedures of §3.4 define the probabilities in
terms of the size of the trace set being employed at that time. Generally, it is equal to the cardinality of
a set of the form Tr_{j}^{A}. This is equal to Tr times the number of DAs
in position j divided by the number
of DAs or Ds in that position. This
can be approximated by Tr times the
overall probability p_{A} of DA divided by the overall probability p_{D} of DA or D. Since the choice of base m = 2^{i}
produces i–1 occurrences of D followed by one of DA when
i > 0, Tr_{j}^{A} ≈ π Tr where π = _{} = _{} For a uniform distribution this works out at π = _{} where typically we
might expect R = 3; and for 2^{R}ary sliding windows it
works out at π = _{}. In fact, the formula underestimates the average size
of Tr_{j}^{A}. Some positions do not have any occurrences of
A, and we do not use the associated
trace subsets. This increases the
average for those positions which do have occurrences of A. Next, the distribution of base choices in the
reconstructed key differs from that generated by the recoding process. Suppose k
is odd for the set of traces at some point during the reconstruction. In Theorem 2, the distribution of odd
residues k mod 2^{R}^{+1} is uniform. So, neglecting the assumed small numbers of
incorrectly assigned cases resulting from some of the possible suffixes not
occurring, base 2^{j} will be
selected for the reconstructed key with probability 2^{–}^{j} for 0 < j
≤
R and produce an odd next key. Further, base 2^{R} will turn up in the remaining 2^{–}^{R} cases of odd keys but produce an even next key. In half of all cases, an even key will lead
to an even key. Consequently, out of
every 2^{R}+2 digit choices
in the reconstruction, on average 2^{R}
will be odd and 2 will be even. By Theorems 2 and 3, the probability of the
reconstructed key being correct is a product of factors of the form _{}. These factors can be
approximated by _{}. Since choosing base
2^{j} leads to j such factors, there is essentially one
such factor for every bit of k. The exceptions are where an even key causes
base 2 and digit 0. Then there is no
doubt about the correctness of the digit 0.
This last case occurs for 2(2^{R}+2)^{–}^{1}log_{2}k bits of the initial key k. Otherwise, for odd keys, the relative
frequency of different bases means that the factor _{} will appear on average
for 2^{R}^{–}^{i}(2^{R}+2)^{–}^{1}log_{2}k bits if 0 < i < R and for 2(2^{R}+2)^{–}^{1}log_{2}k
bits if i = R. Because p_{R}'
= p_{1}+p_{2}+...+p_{R}
= 1, the factor for i = R is 1, and so can be ignored. Hence, Lemma 8. The key k can be recovered
with a probability approximately _{} where n = (1+2^{1}^{–}^{R})^{–}^{1}log_{2}k
and π is as defined above. The property _{}≤ 1–p_{1}
provides a lower bound for this product. Consequently, Lemma 9. For a uniform distribution of
base, the key k can be recovered
with a probability at least (1+_{}^{π}^{Tr})^{–}^{n} where n = (1–2^{1}^{–}^{R})(1+2^{1}^{–}^{R})^{–}^{1}log_{2}k
and
π
= _{}. For specific choices, it is possible to evaluate the
product in Lemma 8 exactly. A typical
choice would be to have a key with 192 bits, R = 3 (which requires storing two precomputed multiples, namely P and 3P), and a uniform choice of base, i.e. p_{1} = p_{2}
= p_{3} = ⅓. Then π
= ⅓ and the product in Lemma 8 is just under 2^{–31} for Tr = 9.
So, if a key can be reconstructed and checked for correctness in unit
time, Theorem 4. If doubles and adds can be
distinguished on individual traces, and traces are captured from 9 applications
of the same unblinded 192bit key,
then the LiardetSmart algorithm with
uniform selection of base ≤ 2^{3} can be broken with a computational effort of about O(2^{31}). With
twice as many traces, the computational effort falls to under O(2^{10}). Of course, the full force of all the patterns
available and their relative frequencies has not yet been applied. Hence the danger is probably substantially
underestimated. Once a possible key has
been recovered, there is considerable unused data in the traces that has not
yet been used and can be investigated for checking purposes. In the uniform case, about _{} of the data is so far unused
– that in the complementary sets Tr_{j}^{D}. This contains information about digits whose
bases were not aligned with those of the reconstructed representation of k.
Choosing a different base from that of the reconstruction process
described above will provide confirmation about the correctness of each bit of k.
Indeed, each trace has to be consistent with some choice of bases, and
the rightmost inconsistency in a trace will usually be very close to the
rightmost bit in error. There is
insufficient space here to improve the probabilities which are a consequence of
this approach, but the computational feasibility of the attack is already assured. If the attacker is unable to distinguish clearly
between adds and doubles, then the unused data vastly increases his ability to
make corrections. Moreover, as each
digit is obtained through a purely local extraction of data from traces, it is
easy to automate an exhaustive process to check for the overall best digit
solutions using all traces, and hence prioritise the order for considering the
most likely values for k. However, for the data that has been used, any
indistinctness between A and D is unimportant. In this attack, it is only necessary to
establish whether or not an A has
appeared at each position. The relative
frequency of As means that the
certainty of this can be determined with high degree just by increasing the
number of traces sufficiently. 4 CounterMeasures Our formulae for bounding the accuracy repeatedly used
the probabilities of smaller bases much more than larger bases, and the
accuracy improves when these probabilities are increased at the expense of the
probabilities of larger bases. This is
consistent with the greater ambiguity afforded by digits of larger bases. Thus we recommend not using a uniform choice
for the base, but employing a strong bias towards large bases, such as was
illustrated in §2.2. In the extreme, the
standard, nonrandomised, mary
exponentiation technique is obtained, and this is not susceptible to the
attack. The cost of key masking is not entirely trivial in the
context of ECC. Adding a 32bit random
multiple of the group order to the key increases the point multiplication cost
by some 17% for 192bit keys, although it is a much smaller fraction of the
total encryption cost. Adding a smaller
random multiple is probably ineffective if it results in a number of
repetitions of the same key value within the lifetime of the key. The highly repetitive nature of the traces
resulting from the same prefix keys turning up again and again means that a
duplicated key could be assumed if, and only if, traces matched closely enough. The “doubleandaddalways” method of computation
provides a good measure of protection, but is expensive. The attacker then has to determine whether or
not the result of the addition is used before he can mount the attack. This is much more difficult than
distinguishing the two operations. Hence
traces will be susceptible to much more frequent errors, and a much greater
number of traces will have to be recovered. There are alternative randomised algorithms for which
this type of attack does not apply, and others that display similar weaknesses. That of Oswald and Aigner [9] can be attacked
in a similar way. Mist [15, 17] does not exhibit the same
repetition of key values during key processing, and so may be a safer choice. A new algorithm by Itoh et al. [18] may also be worthy of consideration. 5 Conclusion It might have been hoped that the LiardetSmart
algorithm would avoid the cost of any additional countermeasures such as key
blinding when the same secret key is repeatedly reused, but this now appears
not to be so. Specifically, the key
needs to be masked, or the pattern of adds and doubles has to be well hidden
for individual point multiplications. Of course, there are many circumstances in which the
algorithm is clearly of value, such as ECDSA, for which a different random key
is used every time. Then, for suitable
parameter choices, the space of keys generating a given pattern of adds and
doubles is infeasibly large, and so cannot be attacked successfully without additional
data. References [1] C. H. Gebotys & R. J. Gebotys, Secure Elliptic Curve Implementations: An
Analysis of Resistance to Power Attacks in a DSP Processor, Cryptographic
Hardware and Embedded Systems – CHES 2002, B. Kaliski, Ç. Koç & C. Paar (editors),
Lecture Notes in Computer Science, 2523,
SpringerVerlag, 2002, to appear. [2] J. C. Ha & S. J. Moon, Randomized SignedScalar Multiplication of
ECC to Resist Power Attacks, Cryptographic Hardware and Embedded Systems – CHES 2002, B. Kaliski,
Ç. Koç & C. Paar (editors), Lecture Notes in Computer Science, 2523, SpringerVerlag, 2002, to appear. [3] K. Itoh, J. Yajima, M. Takenaka & N. Torii,
DPA Countermeasures by Improving the
Window Method, Cryptographic Hardware and Embedded Systems – CHES 2002, B. Kaliski,
Ç. Koç & C. Paar (editors), Lecture Notes in Computer Science, 2523, SpringerVerlag, 2002, to appear. [4] D. E. Knuth, The Art of Computer Programming, vol. 2, “Seminumerical Algorithms”,
2nd Edition, AddisonWesley, 1981, 441–466. [5] P. Kocher, Timing Attack on Implementations of DiffieHellman, RSA, DSS, and other
systems, Advances in Cryptology – Crypto
’96, N. Koblitz (editor), Lecture Notes in Computer Science, 1109, SpringerVerlag, 1996, 104–113. [6] P. Kocher, J. Jaffe & B. Jun, Differential Power Analysis, Advances in
Cryptology – Crypto ’99, M. Wiener
(editor), Lecture Notes in Computer Science, 1666, SpringerVerlag, 1999, 388–397. [7] P.Y. Liardet & N. P. Smart, Preventing SPA/DPA in ECC Systems using the
Jacobi Form, Cryptographic Hardware and Embedded Systems – CHES 2001, Ç. Koç,
D. Naccache & C. Paar (editors), Lecture Notes in Computer Science, 2162, SpringerVerlag, 2001, 391–401. [8] T. S. Messerges, E. A. Dabbish & R. H. Sloan,
Power Analysis Attacks of Modular
Exponentiation in Smartcards, Cryptographic Hardware and Embedded Systems
(Proc CHES 99), C. Paar & Ç. Koç (editors), Lecture Notes in Computer
Science, 1717, SpringerVerlag,
1999, 144–157. [9] E. Oswald & M. Aigner, Randomized AdditionSubtraction Chains as a
Countermeasure against Power Attacks, Cryptographic Hardware and Embedded
Systems –
CHES 2001, Ç. Koç, D. Naccache & C. Paar (editors), Lecture Notes in
Computer Science, 2162,
SpringerVerlag, 2001, 39–50. [10] J.J. Quisquater & D. Samyde, ElectroMagnetic Analysis (EMA): Measures and
CounterMeasures for Smart Cards, Smart Card Programming and Security
(Esmart 2001), Lecture Notes in Computer Science, 2140, SpringerVerlag, 2001, 200–210. [11] J.J. Quisquater & D. Samyde, Eddy current for Magnetic Analysis with
Active Sensor, Smart Card Programming and Security (Esmart 2002), Lecture
Notes in Computer Science, SpringerVerlag, 2002, to appear. [12] M. Joye & J.J. Quisquater, Hessian Elliptic Curves and Side Channel
Attacks, Cryptographic Hardware and Embedded Systems – CHES 2001, Ç. Koç,
D. Naccache & C. Paar (editors), Lecture Notes in Computer Science, 2162, SpringerVerlag, 2001, 402–410. [13] C. D. Walter & S. Thompson, Distinguishing Exponent Digits by Observing
Modular Subtractions, Topics in Cryptology – CTRSA 2001, D. Naccache (editor), Lecture
Notes in Computer Science, 2020,
SpringerVerlag, 2001, 192–207. [14] C. D. Walter, Sliding Windows succumbs to Big Mac Attack, Cryptographic Hardware
and Embedded Systems – CHES 2001, Ç. Koç, D. Naccache & C. Paar
(editors), Lecture Notes in Computer Science, 2162, SpringerVerlag, 2001, 286–299. [15] C. D. Walter, Improvements in, and relating to, Cryptographic Methods and Apparatus,
UK Patent Application 0126317.7, Comodo Research Laboratory, 2001. [16] C. D. Walter, Precise Bounds for Montgomery Modular Multiplication and Some
Potentially Insecure RSA Moduli, Proceedings of CTRSA 2002, Lecture Notes
in Computer Science, 2271,
SpringerVerlag, 2002, 30–39. [17] C. D. Walter, Mist: An Efficient,
Randomized Exponentiation Algorithm for Resisting Power Analysis,
Proceedings of CTRSA 2002, Lecture Notes in Computer Science, 2271, SpringerVerlag, 2002, 53–66. [18] K. Itoh, J.
Yajima, M. Takenaka & N. Torii, DPA Countermeasures by Improving the Window Method, Cryptographic Hardware and Embedded
Systems –
CHES 2002, B. Kaliski, Ç. Koç & C. Paar (editors), Lecture Notes in
Computer Science, 2523,
SpringerVerlag, 2002, to appear. 
This paper was originally published in the
Proceedings of the Fifth Smart Card Research and Advanced Application Conference,
November 21–22, 2002, San Jose, CA, USA
Last changed: 11 Oct. 2002 aw 
