Optimal Recovery of Secret Keys from WeakSide Channel Traces
Werner Schindler1 and Colin D. Walter2
1

Bundesamt für Sicherheit in der Informationstechnik (BSI)
Godesberger Allee 185-189, 53175 Bonn, Germany
Werner.Schindler@bsi.bund.de2
Royal Holloway, University of London,
Egham, Surrey, TW20 0EX, United Kingdom
Colin.Walter@rhul.ac.uk

Abstract. It should be difficult to extract secret keys using weak sidechannel leakage from embedded crypto-systems which employ standard
counter-measures. Here we consider the case of key re-use with randomised exponent recoding. An optimum strategy is presented and proved,
but it has the disadvantage of impracticality for realistic key sizes. Developed from the basis of an optimal decision strategy, some modified,computationally feasible versions are studied for effectiveness. This shows
how to modify existing algorithms and pick their parameters for the best
results.
Key Words. Side channel leakage, power analysis, optimal strategy.

1

Introduction

The academic parents of this work are the optimal strategies of Schindler [10]and the algorithms of Walter [13] for deducing secret keys using weak side channel leakage from an exponentially based public key crypto-system in which the
key is re-used a number of times in some form. The optimal decision strategy
is practically feasible if the key can be guessed in small parts as in [10], for instance, while under the present conditions it remains feasible only for artificiallysmall key sizes. However, the algorithms discussed in [13] still remain feasible fortypical cryptographic key sizes. Here a comparison of the two approaches leadsto i) the determination of the best parameters to choose in existing computationally feasible algorithms and ii) the identification of points in the developmentof the algorithm where it seems impossible to derive a computationally feasible method from the optimal algorithm. Although standard hardware countermeasures nowadays make side channels extremely weak in embedded systems,
the methods here were used in simulations to recover keys using substantiallyweaker leakage than has been reported in the past.

©Springer-Verlag Berlin Heidelberg 2009

M. Parker (Ed): IMACC 2009, LNCS 5921, pp. 446–468, 2009.

Schindler & Walter, Optimal Key Recovery

447

The earliest published work on such secret key recovery is that of Kocher
et al. [6, 7]. For RSA and similar crypto-systems, (unprotected) classical exponentiation algorithms employ the same sequence of multiplicative operations
every time the key is re-used, and this allows leakage (in a certain sense) to beaveraged over many traces to guess the key in small portions, such as bit by bit.
With enough data, the operation types can be determined as squarings or multiplications, and this is sufficient to yield the key for the binary exponentiation
algorithm. Randomised recoding of the exponent causes operations corresponding to the same key bit to be mis-aligned and variable for different uses of thekey. A number of such re-codings exist [9, 8, 4, 15] and they were generally believed to lead to much more secure systems – attacks on such re-codings seemed
to require significantly stronger side channel leakage to succeed than is the casewhere Kocher’s attack applies. However, this no longer seems to be the case.
Karlof & Wagner [5], Green et al. [3] and Walter [13] provide increasingly robust
details for attacking such systems without using such strong leakage, thereby
emphasising the need to combine a number of counter-measures rather than relying on just one or two to defeat the opponent. None of these works provides
justification for the efficacy of their algorithms. Thus there is a gap between
what has been achieved at a computationally feasible level and what has been
derived theoretically. Here we describe a search to bridge that gap by explaining
the computationally efficient choices in terms of the optimal strategies describedby Schindler in [10]. As a result, much more powerful means of exploiting theleakage are now identified.

2

The Leakage Model

The context of the side channel attack is the repeated use of a randomised
exponentiation algorithm for computing C K in any cryptographic group where
K is a fixed secret key which is not blinded by a random multiple of the grouporder1 , and C is an unknown ciphertext (or unknown plaintext) which may varyand may be blinded2 . Of course, all the following considerations apply equallywell to randomised scalar multiplications in additive groups (as in ECC).
The adversary is assumed to know all the details of the exponentiation algorithm. Use of the key provides him with a side channel trace for the exponentiation itself, but no further information is assumed: in particular, he is notexpected to be able to choose or see any direct input to the exponentiation, norview any output, nor usefully observe any pre- or post-processing.
It is assumed that occurrences of multiplicative operations in the exponentiation can be identified accurately from the corresponding side channel trace, butthat their identities as squares or multiplications (and, in the case of methods
with pre-computed tables, multiplications by particular table entries) can only
be determined with a substantial degree of inaccuracy [1]. The adversary’s aim
12

Another standard counter-measure to Kocher’s averaging of side channel traces.
The base in the exponentiation is frequently unknown due, for example, to “Rivest”
blinding [2] or because of an unknown modular reduction when applying the CRT.

448

Cryptography and Coding, LNCS Vol. 5921 ©Springer, 2009is to discover K using computationally feasible resources. The multiplicative operations are assigned probabilities that they represent squares or multiplications
as a result of previous experience by the adversary. For this he uses knowledgeof the stochastic behaviour of the operations in the side channel, and the extent
to which this behaviour varies.
In order to model noisy measurement data in the simulations we assumed
that these probabilities were distributed binomially and independently for all
multiplications with mean probabilities depending on the true type of the operation, so that some were known correctly with high probability, but most were
known with little confidence. However, Theorem 1 also covers more general leakage scenarios.

3

The Randomised Exponentiation

Examples of the randomised exponentiation algorithms which can be attacked
in the way described here include those of Liardet-Smart [8], Oswald-Aigner [9]and Ha-Moon [4, 15]. Their common, underlying basis is a recoding of the binary
representation of the key K into a form
R = ((...(rm−1 2mm−2 + rm−2 )2mm−3 + ... + r2 )2m1 + r1 )2m0 + r0
for digits ri and exponents mi in some fixed, pre-determined sets D ⊆ Z (which,for convenience, contains 03 ) and M ⊆ N+ respectively. In this recoding, bothri and mi are selected according to some finite state automaton (FA) which has
the bits of K and the output from a random number generator (RNG) as inputs.
For convenience, we assume the bits of K are consumed by the FA from least to
most significant. Different bit streams from the RNG result in different recodings
R of K.
The exponentiation C R begins with the pre-calculation of the table {C d | d ∈D, d6= 0}. Then for i = m−2, m−3, ...2, 1, 0 the main iterative step of the exponentiation consists of mi squarings followed by a multiplication by the tableentry C ri when ri 6= 0. This results in a sequence of multiplicative operations
which is most easily presented using ri to denote multiplication by C ri and mi
copies of 0 to denote the mi squarings. We call this the recoding sequence forR, and it belongs to D*. For example, the exponent K = 1310 = 11012 may
have a recoding R = (1.22 +3)21 +1̄ which gives the operation sequence 100301̄,the recoding sequence associated with the recoding R. For convenience (e.g. in
Section 7), the leading recoded digit is translated in the same way as the others
into multiplicative operations of the recoding sequence even when that digit is0; alternatives in processing the leading bits are ignored. (This matches the situation where the exponentiation algorithm begins with 1 instead of C.) However,the leading digits are invariably treated differently in practice, and appropriate
modifications need to be made in the methods here to handle them properly.
3

Recodings which do not allow 0 in representations are not excluded here, but wewant to include it for another use, namely to represent a squaring operation.

Schindler & Walter, Optimal Key Recovery

449

Thus, we are using the same set D to represent both the set of recoding digits
and the set of corresponding recoding operations. In our examples, we will makethe distinction clearer by using, for example, ‘S’ for the squaring operation andreserving ‘0’ for the digit. We will rarely be working with recodings. It will bemuch more frequently be with recoding sequences.
The exponentiation algorithms of interest are assumed to have the property that perfect knowledge of the multiplication/squaring sequences (without
necessarily knowledge of the choice of respective table entries in the case of multiplications) for a small number of recodings R of K yields enough information toreconstruct the secret key K with at most a small number of ambiguities. This is
the case for the algorithms listed above: attacks on them using such information
are described in [11], [12] and [15] respectively. The theory here, however, allows
for the possibility of distinguishing between the use of different table entries in
the multiplications, and this enables one to deal with recodings for which only
non-zero digits are used.

4

The Optimal Decision Strategy

The optimal decision strategy for discovering the secret key K begins by identifying a key K ∗ with the highest probability of having generated the observedside channel leakage. If the most likely key candidate fails the attacker tries
the key candidates that are ranked 2, 3, . . .. This maximises the use of known
information about K and hence minimises the effort in searching for K.
For each use of the secret key K, the side channel leakage leads to a best
guess G at the recoding that was used: the locations of multiplicative operations
are identified, and the most likely digit values are selected for those operations.
Associated with a set of these recoding guesses there are optimal choices K ∗ forthe key value – those which maximise how well the key collectively matches theguessed recodings.
Remark 1. To be successful in real-world attacks we must assume there is enoughleakage to ensure that the correct key is among the best, i.e. most probable, fits
to the recoding guesses for otherwise it will be computationally infeasible to findit. If not correct, the most plausible keys typically are at least related to thecorrect one, which means that their bit representations or their recodings are
similar to that of the correct key in some sense. E.g., long sequences of bits inthese most probable keys may either be identical to those in the correct key or,
depending on the recoding scheme, related to them in very specific, predictableways4 . Hence the errors in using a most probable key to predict the correct
key should also be relatively few in number, generally isolated, and effectively
independent. Consequently, virtually all errors will be equally easy to correct
although finding them may not be so easy.
4E.g. two keys which are bit-wise complements of each other can have almost identical
recodings, as may two keys of which one is almost the same as a shift of the other.

450

Cryptography and Coding, LNCS Vol. 5921 ©Springer, 2009

Definition 1.
(i) Let K ⊆ F2 * denote the set of all admissible keys in binary representation andR ⊆ D* the set of all possible recoding sequences of keys for the chosen recoding
scheme. Recoding to an operation sequence is defined by a map φ: K×Z → R
where z ∈ Z denotes a random number in a finite set Z. The set φ(K, Z) ⊆ R
of possible recoding sequences of K is denoted R(K) or RK .
(ii) The set of possible recoding sequence guesses which can be deduced from sidechannel leakage is denoted by G where R ⊆ G ⊆ D*, and len(G) is the number of
elements in a guess G ∈ G when viewed as a sequence over D. The ith elementof G is gi where the index runs from len(G)−1 (the most significant operation)
down to 0 (the least significant operation).
(iii) The random variable XQ assumes values in the set Q.
Clearly the subsets R(K) are disjoint for different K’s – each recoding sequence specifies exponentiation to a particular power, and that power is K. We
seek to determine K ∈ K from guesses G1 , . . . , GN ∈ G based on side channel
leakage with the disadvantage that the Gj are probably inconsistent because oferroneous operation deductions, i.e. they may not all represent the same key K;
some Gj may even represent ‘impossible’ recoding sequences (i.e. not belonging
to any K).
Starting with key K ∈ K a guessed recoding sequence G may be interpreted
as the result of two consecutive random experiments. The first step (recoding toan operation sequence) is determined by a random number z (and K, of course).
The second step (adding noise), namely recoded operation sequence → recoding
guess, is determined by a hidden parameter y ∈ Y which represents the influenceof noise of various forms such as that arising from the measurement process itself
or from implemented countermeasures. Formally, the guessing step R 7→ G canbe expressed by a function ψ: R×Y → G, (R, y) 7→ ψ(R, y) since the guessed
recoding sequence G depends on the actual recoding sequence R = φ(K, z) ∈ R
but not directly on K ∈ K or z.
The random variable XK describes the selection of the key K during initialisation of the attacked cryptosystem. Without loss of generality we may assume
the probability η(K) of each key is non-zero:defη(K) = Prob(XK = K) > 0

for all K ∈ K.

(1)

The distributions of XK and XZ and, of course, the applied recoding scheme
def
determine the distribution ν of the random variable XR = φ(XK , XZ ). The
random variable XG quantifies the distribution of random recoding sequencesthat are guessed by the attacker. Theorem 1 considers the situation where an
attacker observes N re-uses of the key K. We assume that the associated randomvariables XK , XZ,1 , . . . , XZ,N , XY,1 , . . . , XY,N are independent.
Theorem 1. (i) Given recoding sequence guesses G1 , . . . , GN ∈ G, the optimal
decision strategy τ∗ : G N → K selects a key K ∗ ∈ K that maximises the expres-Schindler & Walter, Optimal Key Recovery

451

sion
N
X


log 

j=1
N
X


X

ν(R)Prob(XG,j =Gj | XR =R) − (N −1) log (η(K)) = (2)R∈R(K)


log 

j=1


X

ν(R | XK =K)Prob(XG,j =Gj | XR =R) + log (η(K)) .

(3)

R∈R(K)

If this maximum is attained for several keys the first key is chosen under any
pre-selected order on K.
(ii) Assume that the adversary is able to detect whenever an operation of therecoded sequence R is carried out and guesses the types of these operations
independently to obtain G ∈ G. Assume also that the conditional probabilitiesdefp(g|r) = Prob(guessed opn type is g given the true opn type is r) for guessed
operations g do not depend on the position of the operation r but only on theoperation types g, r ∈ D. Then len(R) = len(G), and the optimal decision K ∗with respect to the N such guesses G1 , . . . , GN maximises
len(Gj )−1
N
Y
X
X


ν(R)
p(gj,i | ri ) − (N −1) log (η(K)) = (4)
log 
j=1

N
X

i = 0

R∈R(K):
len(R)=len(Gj )



log 

j=1

len(Gj )−1XY

ν(R | XK =K)p(gj,i | ri ) + log (η(K)) . (5)i = 0R∈R(K):
len(R)=len(Gj )(iii) Assume that D = {0, 1, 1}. Suppose also that (ii) holds with p(0|0) = 1,p(1|1) = p(1|1) = q ∈ [0, 0.5] and p(0|1) = p(0|1) = 0. Then the optimal decisionK ∗ maximises


N
X



log 


j=1

X
R∈R(K):
len(R)=len(Gj ),supp0 (R)=supp0 (Gj )


ν(R)

q
1−q

Ham(R,Gj )  − (N −1) log (η(K)) = (6)




N
X



log 


j=1


X
R∈R(K):
len(R)=len(Gj ),supp0 (R)=supp0 (Gj )ν(R | XK =K)q
1−qHam(R,Gj )  + log (η(K)) (7)where supp0 (R) and supp0 (Gj ) are the sets of positions in R = (rlen(R)−1 , . . . , r0 )and Gj = (gj,len(R)−1 , . . . , gj,0 ) for which the type of operation is a squaring, i.e.
ri = 0. Further, Ham(R, Gj ) denotes Hamming distance, viz. the number of
positions for which the operations in R and Gj differ.

Cryptography and Coding, LNCS Vol. 5921 ©Springer, 2009452

(iv) If XK is uniformly distributed on K the terms “(N −1) log (η(K))” in (2),(4), (6) and “log (η(K))” in (3), (5), (7) may be omitted.
(v) For any constant c > 0, multiplying the probability ν(R) in (2), (4) or (6)(resp. the conditional probability ν(R | XK = K) in (3), (5) or (7)) by c for all
R ∈ R does not change the optimal decision strategy in (i), (ii), (iii) or (iv),respectively, but may simplify concrete calculations.
Proof. To prove (2) we apply Theorem 3(i) from the Appendix (originally proved
as Theorem 1(i) in [10]) with Θ = K, Ω = G N , µ = the counting measure on G N ,
def

def

and the loss function s(θ, a) = 0 if θ = a and s(θ, a) = 1 otherwise since, as
noted at the start of this section, any kind of false key guess is equally harmful.
Let ProbK (A) be the probability of the event A if K is the correct key.
Then the optimal decision strategy τ ∗ : G N → K assigns to the guess tuple ω =(G1 , . . . , GN ) a key K ∗ ∈ K which minimisesXs(K 0 , K ∗ )η(K 0 )ProbK 0 ((XG,1 , . . . , XG,N ) = ω) =K 0 ∈KX

η(K 0 )ProbK 0 ((XG,1 , . . . , XG,N )=ω) − η(K ∗ )ProbK ∗ ((XG,1 , . . . , XG,N )=ω)K 0 ∈Kor, equivalently, maximises η(K ∗ )ProbK ∗ ((XG,1 , . . . , XG,N )=ω). Recall that XK ,XZ,1 , . . . , XZ,N , YZ,1 , . . . , YZ,N are independent and XG,j = ψ(φ(XK , XZ,j ), XY,j ).
For each fixed K ∈ K and ω = (G1 , . . . , GN ) ∈ G N we have
ProbK ((XG,1 , . . . , XG,N ) = ω) =N
Y

ProbK (XG,j = Gj )

j=1

=

N
Y
X

Prob(XZ,j = zj ) Prob(XG,j = Gj | XZ,j = zj , XK = K)

j=1 zj ∈Z

=

N
Y
X

Prob(XZ,j = zj ) Prob(XG,j = Gj | XR = φ(K, zj ))j=1 zj ∈Z= η(K)−NN
YX

Prob(XK =K, XZ,j =zj ) Prob(XG,j =Gj | XR =φ(K, zj ))j=1 zj ∈Z−N= η(K)NYX

ν(R) Prob(XG,j = Gj | XR = R)

j=1 R∈R(K)since φ(K, Z) = R(K) and the sets R(K 0 ) are mutually disjoint for different keys
K 0 . As the logarithm function is strictly increasing, the last formula implies (2).
Moreover, since the sets R(K 0 ) are mutually disjoint, for any R ∈ R(K) we haveν(R | XK = K) = ν(R)/η(K), which proves (3). Substituting the additional
conditions from (ii) into (2) and (3) yields (4) and (5).

Schindler & Walter, Optimal Key Recovery

453

Assertion (iii) follows from (ii) since, when supp0 (R) = supp0 (Gj ),len(Gj )−1Yp(gj,i , ri )=q Ham(R,Gj ) (1 − q)len(Gj )−|supp0 (Gj )|−Ham(R,Gj )

i = 0


=

q
1−q

 Ham(R,Gj )(1 − q)len(Gj )−|supp0 (Gj )| .

Otherwise the product is zero. Since the last factor only depends on Gj (fixed)
but not on R it can be factored out in (4) and (5). In particular, it has no
impact on the location of the maximum, and thus may be dropped. Similarly, in (iv) η(K) is assumed to be the same for all K ∈ K and thus may
be dropped. Assertion (v) follows immediately from the functional propertylog(ab) = log(a)+ log(b) of the logarithm function.
Remark 2. (i) Theorem 1(i) is very general. It covers any recoding scheme as longas the random variables XK , XZ,1 , . . . , XZ,N , XY,1 , . . . , XY,N are independent.
In particular, there are no restrictions on maps φ: K × Z → R or ψ: R × Y → G.
(ii) In the case of several best candidates in Theorem 1 (which should be a rare
event in practice) the rule that one of them is selected according to some predefined order has ‘technical reasons’, namely, to ensure the measurability of thedecision strategy. Alternatively, one could pick one of the best key candidates at
random (defining a randomised decision strategy).
Definition 2. With regard to expression (2), define the (weighted) “credibility”
function cred: G × K → R byX
defcred(G, K) =ν(R)Prob(XG = G | XR = R).
(8)
R∈R(K)

A large value for this credibility function implies that G is a likely recoding
sequence guess for key K.
Corollary 1. If η is uniformly distributed on K (i.e. if all keys are equally likely)
for recoding sequence guessesPG1 , . . . , GN the optimal decision strategy selects aN
key K ∗ ∈ K that maximises j=1 log(cred(Gj , K)) for K ∈ K.
Q As in theorem Theorem 1(ii), suppose that Prob(XG = G | XR = R) =0≤i<len(G) p(gi |ri ). Then the computation of cred(G, K) is computationallyfeasible because recodings are performed by a finite automaton (FA) which typically has very few states. The state of the finite automaton incorporates thedifference between the key suffix which has been read and the recoded key suffix
which has been generated. The finite automaton reads the next key bit and uses
a random input to decide the next recoded digit to output and which transition
to make to its next state. For each state s of the automaton, defineX
defcred(G, K 0 , s) =ν(R, s)Prob(XG =G|XR =R)(9)R∈R(K 0 )

Cryptography and Coding, LNCS Vol. 5921 ©Springer, 2009454

where ν(R, s) corresponds to the FA reaching state s after generating the recoding R of key suffix K 0 . All the component functions can be evaluated iteratively
by processing the bits of K sequentially (here from right to left): ν(R, s) is givenby the product of the state transition probabilities for the path through the FA
to s which yields R, and, if K 00 = d||K 0 has leading (i.e. most significant) bitd, then cred(G, K 00 , s0 ) can be expressed easily as a linear combination of values
cred(G, K 0 , s) for the suffix K 00 of K. The work is then proportional to the lengthof K and the number of FA states. Algorithm 1 (in the Appendix) provides aconcrete example for the Ha-Moon recoding scheme.

5

Traces

The rest of this paper investigates the extent to which the main theorem (Theorem 1) applies to real-world scenarios and, in subsequent sections, enables thecomputationally feasible recovery of a secret key K. From here on, it is assumed
that side channel leakage is sufficient to identify the trace sections which correspond to individual long integer multiplicative operations (or elliptic curve point
operations) when the key is used. Given that a standard counter-measure to timing attacks is to ensure that these operations always take the same number ofclock cycles, it should be relatively straight-forward to divide the trace correctlyfrom knowledge of the expected number of operations.
The decision about whether a section of side channel leakage represents aparticular type of multiplicative operation is not clear cut. As a result of noise,the decision can only be made with a certain probability of correctness. Initialprocessing of the leakage from each operation uses templates of the expectedleakage from each operation type and takes account of the relative probabilities
with which the particular digits of D occur in the given recoding scheme. This
yields a set of probabilities, one for each r ∈ D and summing to 1, that theoperation involved digit r. For convenience, we define a trace to be the result of
this pre-processing:
Definition 3. T ⊆ ([0, 1]|D| )* denotes the set of traces considered by an attacker. The ith element ti of T ∈ T is a list of probabilities, one for each r ∈ D,that the corresponding side channel measurement represents the operation r.
Formally, for power attacks for example, each operation r ∈ D induces a probability distribution on the set of all possible power traces. The exact probability
vector ti follows from the convex combination of these probability distributions
with regard to the probabilities with which the particular operations occur (generally) in the recoding scheme. In real-world scenarios the probability vectors ti
can hardly be determined exactly, but roughly estimated.
Using the above definition of a trace, we need to convert each trace Tj ∈ Tinto a guess Gj ∈ G before applying Theorem 1(ii) to this situation. The straightforward strategy is to treat each operation separately and to select the most
likely candidate gj,i ∈ D, i.e. the operation that maximises tj,i . Formally, theconditional probabilities p(g... |r... ) used in Theorem 1 are given by first averaging

Schindler & Walter, Optimal Key Recovery

455

over sections of side channel traces (such as those described in the previous paragraph) which correspond to the execution of the same multiplicative operationr... ∈ D at the same position within the recoding sequence. Then, secondly, these
conditional probabilities are averaged over the different positions in the recoding
sequence. Practically, these conditional probabilities can simply be estimated byapplying this procedure (assigning trace sections, deciding on the most probable
operation etc.) to a sample of side channel traces with known recodings.
For many applications this strategy should be appropriate. However, depending on the concrete scenario it may have two difficulties. The first is that theprobabilities in Theorem 1(ii) neither depend on the particular side channel
trace nor (which may be of less importance) on the position i. In contrast to
Theorem 2 below, Theorem 1(ii) applies averaged probabilities. An advantage ofTheorem 1(ii) and, in particular, of Theorem 1(iii) is their simple formulae. But
using Theorem 2 and traces avoids the second difficulty, namely that of explicitly
determining the best values Gj to use in advance5 .
Formally, for N = 1, Theorem 2 may be viewed as a special case of Theorem 1(i), which considers the whole recoding sequence R1 and the guess G1 at
the same time. (Note that each tj,i,ri may formally be replaced by a trace- andposition-dependent conditional probability pj,i (gj,i | ri ) with some guess gj,i .) A
straight-forward generalisation of Theorem 1(i), allowing trace-dependent conditional probabilities Probj (XG,j =Gj | XR =R), comprises the general case N ≥ 1.
In particular, the proof of Theorem 1 can easily be adapted to Theorem 2. Theorem 1(iv) and (v) also remain valid for traces.
Theorem 2. Given traces T1 , . . . , TN ∈ T , the optimal decision strategy τ∗ : T N→ K selects a key K ∗ ∈ K that maximises the expressionlen(Tj )−1
N
X
Y
X


log 
ν(R)
tj,i,ri  − (N −1) log (η(K)) .
(10)
j=1

R∈R(K):
len(R)=len(Tj )i=0

If this maximum is attained for several keys the first is chosen under any preselected order on K.

6

Application of the Main Theorem

In Sections 4 and 5 we determined optimal decision strategies. To demonstrate
the power of its optimal decision strategy, Theorem 1(ii) was applied to small
key sizes with the Ha-Moon recoding scheme using Algorithm 1 of the Appendix.
Algorithm 1 allows one to compute efficiently the credibility function cred(G, K)
for any required (G, K) and key size. The Ha-Moon recoding scheme maps thebinary representation of key K into a representation that uses the digits 0, 1 and−1. Rather than using D = {0, 1, 1} also for the recoding sequences, to avoid
5

Indeed, choosing the gj,i first and independently for all positions may lead to impossible guesses which are not recoding sequences of any key.

Cryptography and Coding, LNCS Vol. 5921 ©Springer, 2009456

confusion we will write these operation sequences using ‘S’ to denote a squaring,‘M ’ a multiplication by the base C, and ‘M ’ a multiplication by C −1 . Thendigits 0, 1, and −1 in the recoding correspond to the operation sequences ‘S’,
‘SM ’ and ‘SM ’ respectively.
A large number of stochastic simulations were performed. In each simuladeftion we generated: a random key K ∈ K = {0, 1}n \ {(0, . . . , 0)} where n denotes the length of K, N random recodings which delivered operation sequences
R1 , . . . , RN and some related recoding guesses G1 , . . . , GN . More precisely, theguess Gj was derived from the operation sequence Rj by replacing the correct
operations independently with the conditional probabilities p(‘M ’|‘S’) = 0.2,p(‘M ’|‘S’) = 0.1, p(‘M ’|‘M ’) = 0.2, p(‘S’|‘M ’) = 0.1, p(‘M ’|‘M ’) = 0.2 andp(‘S’|‘M ’) = 0.1, which corresponds to noise in the side channel traces. Hencep(‘Y ’|‘Y ’) = 0.7 for each operation ‘Y ’. Given G1 , . . . , GN we applied Algorithm 1 exhaustively to all 2n − 1 admissible keys K 0 . For each row in Table 1 we
performed 100 simulations. The integers in the column entitled “The correct key
was ranked 2”, for instance, give the number of simulations out of 100 for which
the correct key was ranked second for the given parameter set (Key length, N ),e.g. 5 out of 100 for key length 15 and N = 10.

Key length
15
15
15
15
20

N
2
3
5
10
10

1
9
10
45
84
57

2
2
7
12
5
20

The correct key was ranked
3-9
10-99
100-999
19
38
27
26
36
19
20
18
4
9
1
1
20
2
1

> 100072
1
00

Table 1. Ha-Moon recoding scheme: simulation results for short keys.

These results clearly underline the strength of the optimal decision strategy.
However, a major problem with the optimal decision strategy is that it is computationally infeasible for keys of cryptographic size – there are too many keys
to search for the best one. Unlike in, e.g., [6, 7] or in several examples in [10] wecannot handle single key bits or small blocks of key bits either independently
or at least sequentially. Instead, the optimal strategy does not describe how torecover part of a key, only how to recover the whole key. In general it is notpossible to associate the key bits independently yet correctly with recoding operations. Where such an association is possible, the key bits might be recovered
independently and in parallel or sequentially with effort which is linear rather
than exponential in the key length.

Schindler & Walter, Optimal Key Recovery

7457

Incremental Key Construction

General complexity and other issues (see [13], §1) seem to dictate that the best fit(i.e. most probable) key that it is feasible to find has to be generated sequentially
bit by bit. We take this approach here, following [13], and this enables theprocessing of partial keys to be closely related to the theory already presented
for full length keys.
It makes sense to determine the bits in the order that recoding takes place,which is assumed here, for convenience, to start at the least significant (rightmost) end. So key suffixes of increasing length will be generated. This is doneusing corresponding suffixes of ‘traces’ in the sense of Definition 3. In order tomaximise the expression in Theorem 2, each key suffix must normally have, foreach trace, a very good fit between one (or more) of its recoding sequences andthe suffix of the trace with the same length. In subsequent sections we try tojustify this reasonable assumption while working out its implications. If a sufficiently large set of good key suffixes are processed the best fit key suffix should
always be included, so that the best key emerges at the end of the algorithm.
However, the longer the key the more likely there is to be a suffix which is toopoor a fit to be retained, and our algorithm will fail more frequently in thesecases.
Suppose we select a key suffix K (n) of length n which yields the best match
to all the leakage from that point onwards, i.e. the best match to trace suffixes.
Formally, under the optimal decision strategy model K (n) provides the maximum
of


N
X
j=1

len(R)−1


log 


X
R∈R(K 0 ):len(R)≤len(Tj )

ν(R)

Y
i=0


0
tj,i,ri  − (N −1) log (η(K ))(11)over all keys K 0 of n bits. (There are some minor issues with end conditions which
we will ignore.) If all bits of K (n) are accepted as belonging to the near best-fit
full length key K then a decision is being made on the initial, i.e. leftmost, bits ofK (n) which does not take into account all available information. Recoding choices
are not made independently of previous input; they depend on the state of therecoding finite automaton arising from the previous input, and the influence canpersist measurably for several bits. Hence we should ignore the first λ bits, say,of K (n) and choose only its last n−λ bits. Thus, the obvious algorithm is tocompute iteratively for n = 1, 2, 3... the fitness of every K (n) which extends thepreviously chosen K (n−λ−1) , select the best, and use that to determine K (n−λ) .
This algorithm with the above formula was applied to the (first) Ha-Moon
recoding scheme [4], but so far without success. Even worse, under the leakage
model described in [13], the resulting “best fit” full length key was indistinguishable from a randomly chosen key – on average half the bits were incorrect. This
spurred an investigation into what modifications are necessary to obtain useful
results as it is known (e.g. from [3, 5, 13]) that it is possible to recover the secret
key when leakage is weak. It was hoped that the optimal decision strategy would
lead to a much more powerful algorithm.

Cryptography and Coding, LNCS Vol. 5921 ©Springer, 2009

458

8

Simulation Experiments

With the Ha-Moon scheme [4] as a test case, the formula (11) was modified in alarge number of ways to discover what choices lead to a useful, computationallyfeasible algorithm. By Theorem 1(iv) choice of a uniform key space K allowed
the formula to be simplified by ignoring the log(η(K)) term.
Of all the modifications attempted, only one seemed essential to obtain anything better than how a random
P key choice would perform, and that was substituting Max for the secondin (11). Thus we became interested in iteratively
finding the n-bit suffix K (n) which closely maximises
len(R)−1NXYlog Max{ ν(R)tj,i,ri | R ∈ R(K (n) ), len(R) ≤ len(Tj )} . (12)
j=1

i=0

(Note that (12) moves the search for a maximum within subsets of recoding
sequences to individual recoding sequences. This is computationally more easy.)
With sufficiently strong leakage and enough traces, this change results in a significant portion of the predicted bits of K being correct. However, it exposes
the factor ν(R) which gives undue weight to shorter recoding sequences. In theoriginal formula (10) recoding sequences which were too short could not arise
because of the constraint len(R) = len(Tj ). Now, with only an upper bound on
the length, some re-balancing is necessary. Normalising using len(R) yields themuch more frequently successful formulalen(R)−1NXYlog Max{tj,i,ri 1/len(R) | R ∈ R(K (n) ), len(R) ≤ len(Tj ) } .
j=1

i=0

(13)
We could have added a weighting that accounted more for the expected lengthof a recoding sequence for an n-bit key which has given trace length for the fullkey, but did not do so.
It was noted above that only the final n−λ bits should be chosen from K (n) .
This provides the possibility of treating the first λ bits differently from the later
ones. In particular, the two modifications described for (11) can be applied only
to the recoding operations corresponding to the last n−λ bits or only to theoperations corresponding to the first λ bits. However, this different treatment of
the two sequences of bits did not give better results.
The formula (13) and related algorithm are now close to what was usedin [13]. The main difference is that here we have a product of probabilities tomaximise rather than the following sum of distances to minimise:
N
X

1
Min{
len(R)
j=1

len(R)−1X(1−tj,i,ri ) | R ∈ R(K (n) ), len(R) ≤ len(Tj ) }. (14)i=0However, the absence of the “log” from this formula suggests that the contributions from each trace might be either multiplied or added together. So a

Schindler & Walter, Optimal Key Recovery

459

promising alternative to (13) might be found in
N

1 X
Max{
N j=1

len(R)−1Ytj,i,ri 1/len(R) | R ∈ R(K (n) ), len(R) ≤ len(Tj ) } (15)i=0which is normalised with respect to the number of traces N . In practice, thesimulations did work a little better for this formula than for (13), so that it
became our final choice. Moreover, this “most probable” version proved to besignificantly better than the “best fit” version (14) which appears in [13] unlessa very specific choice of parameters is made in [13].

9An Ordered Search

The algorithm of the previous section rarely identifies the correct key although,with enough traces and sufficiently strong leakage, the resulting key K ∗ =K (len(K)) should yield a close to maximal value for (2), as should the correct
key. The remaining problem is therefore to organise a computationally feasibleordered search of the key space to find the correct key K from K ∗ .
In a simulation, a quick scan of this close-to-most-probable key K ∗ showsthat, unless the strategy failed, most of the key bits are correct, or differ fromthe correct ones according to specific patterns which make no difference to thelikelihood of the key (such as a sequence of one or more inverted bits). Thus,
the correct key might be found by allowing for all the related patterns of equal
probability and by looking at each bit and obtaining an estimate of confidence
in its correctness. This estimate is naturally based on the values returned by theexpression (15) which was used to choose the bit initially. Then the search of
the key space is performed by changing more and more of those bits for which
confidence is lowest (and any subsequent related pattern) until the correct key
is found.
With the last n−λ−1 bits of K ∗ already chosen, there are 2λ+1 choices for(n)Kwhich are supplied to (15). There are 2λ cases for which bit n−λ is 0,
λand 2 cases for which bit n−λ is 1. Let cred(0, n−λ) and cred(1, n−λ) denotethe maximum values returned by (15) when evaluated over these two partial
key subsets. Whichever is larger determines the choice of bit n−λ, and so it isnatural to use some measure of their proximity to provide a confidence value forthe bit decision. Out of several possibilities,• an effective discriminant was found to be the larger of the two ratios
cred(1, n−λ)/cred(0, n−λ) or cred(0, n−λ)/cred(1, n−λ).
The larger this ratio, the greater the confidence that the bit is chosen correctly.
When evaluating (15) over the 2λ keys of interest, the variance of cred(b, n−λ)decreases as n increases. This implies that, on average, the confidence function
will return smaller values with increasing key size. Of course, this is what happens, and it corresponds to the fact that bits are predicted with decreasing accuracy as n becomes larger. A re-scaling to compensate for this is the modification

Cryptography and Coding, LNCS Vol. 5921 ©Springer, 2009460

to (15) which results in the following expression for maximising:
N

1 X
Max{
N j=1

len(R)−1Ytj,i,ri n/len(R) | R ∈ R(K (n) ), len(R) ≤ len(Tj ) } (16)i=0This re-scaling may give some benefit when applied, but was usually marginallypoorer than (15) over all the choices of parameters we tried, such as variationsin the level of leakage and in the key lengths.

10Complexity

This section considers the space and time complexity for obtaining a near best-fit
key K ∗ using expression (15). We are assuming that all necessary pre-processing
has already been performed to derive traces in the sense of Definition 3 from theside channel measurements and template information.
Our model assumes 1 unit of time for any arithmetic operation involving one
or two bits. It also assumes one unit of time for moving (reading, writing etc.)
or copying a single bit and one unit of space to store a single bit. This is notquite realistic since address sizes and wire connect grow as the logarithm of thevolume of data, but is adequate for the quantities of data under consideration.
Moreover, since most bits are effectively random and we avoid storing multiple
copies of data, there are no data compression techniques which are likely to be
useful.
For convenience, we further assume that all probabilities can be stored with
sufficient accuracy using O(1) bits. In practice our simulations worked using 32bit real arithmetic without any hint of problems. Overall this complexity model
enables one to run small trial cases first, and scale up using the complexity
results to obtain good approximations to the space and time requirements for
an attack on secret keys of cryptographic size.
Following earlier notation, we have a key K ∗ of nK bits which is constructed
bit by bit, N traces, and λ leading bits of the suffixes which we ignore whenselecting the next bit of K ∗ . At any one time we have decided the least significant
n − λ − 1 bits of K ∗ . We have 2λ+1 possibilities for the remaining bits of then-bit suffix and hence that number of keys to consider when determining thenext bit of K ∗ .
Recall our assumption that recodings are converted into sequences of operations with digit 0 generating one operation (a squaring) and non-zero digits
generating two (a squaring and a multiplication). Consequently, when the recoding finite automaton (FA) has read a suffix of n bits, the resulting recoding
sequences may have any length from n up to 2n. Suppose also that the recoding
FA has F possible states. These states include, but are not limited to, storing
the shifted difference (i.e. carry or borrow) between the value of the key suffix
read by the FA and the recoding output by it. (For the Ha-Moon scheme this isalways 0 or 1, and the corresponding FA has two states.) Whenever two recoding
sequences have the same length and left the FA in the same state, we can ignore

Schindler & Walter, Optimal Key Recovery

461

the one with the smaller value of the product of trace values in (15). It cannot
give the maximum, nor contribute to any maximum when the FA recodes more
bits. Hence there are only up to F (n + 1) sequences which need to be maintainedin order to select the best recoding.
The iterative step starts at n = λ + 1 in order to determine the bit of index
0. If there were just one trace then, after incrementing n, the general induction
step would start with a set of best recoding sequences for the least significant
n − λ − 1 bits of K ∗ and the corresponding values for the product of traces
values needed in (15). There are up to (n − λ)F of these, so O((n − λ)F ) space isrequired for this. In fact, this is needed for all N traces, so O((n−λ)F N ) space isused to hold the data required by the induction step. A three dimensional arrayis used for this in order to have direct access in unit time to the data elements.
The total space order is also enough to include the decided bits of K ∗ .
Extending the recoding sequences from representing a suffix of length n−λ−1
to a suffix of length n just means generating the same set of data incrementallyfor longer suffixes. A depth first traversal is made of the binary tree of depth λ+1
representing the remaining choices for the n-bit suffix of K ∗ . Along each branchof the tree one such data set needs to be stored at each node. So O(nF N λ) spaceis required for data storage during the induction step. At each node in the tree,
each recoding sequence of the parent node’s data set is extended by processing
the key bit value which labels the current node. The FA generates O(F ) choices
which are used to create or update the items in the data set of this node. Thismeans O(F ) time per recoding sequence, and a total of O(nF 2 N ) per node of
the tree. With 2λ+2 − 2 nodes to treat, the time order is O(2λ nF 2 N ).
If, instead, we are able to hold all the data sets for all the nodes in the above
tree simultaneously, then we do not need to regenerate the same data for up to
λ consecutive values of n. Instead we traverse the leaves of the tree from thepreceding value of n and generate the data for the leaves of the tree for thecurrent value of n. However, as this still means traversing 2λ+1 nodes, the timeorder is not reduced although there will be a speed-up by a factor of about 2.
Whenever the data set for a leaf of the tree has been generated, we have thevalue of the product term in (15) for all the O(F n) recoding sequences associatedwith each trace. Hence the maximum value can be obtained for each trace, andthe sum over all traces calculated. This does not add to the time complexity as
it requires O(1) time per sequence. Finally, we must obtain the maximum valueof (15) over the 2λ+1 key choices in order to determine bit n − λ of K ∗ . Again,
this does not add to the time order. If we want to rank the bits in order of
certainty, then the ratio of credibility values is obtained at this point by taking
the maximums over the two sub-trees corresponding to the two choices for bitn − λ.
Thus, neglecting special processing for the most significant λ bits of K ∗ (when
we must decrease λ rather than increase n), the iterative process to compute K ∗takes O(nK F N ) space and O(2λ nK F 2 N ) time.

462

11

Cryptography and Coding, LNCS Vol. 5921 ©Springer, 2009

Numerical Results

Direct comparison of the improved algorithms here with the results of [13] ismade difficult by the fact that [13] limits the key search to a fixed maximum
number of recoding states6 whereas here the number is not limited. Specifically,in (15) the maximum is given by incrementally extending a set of best recoding
sequences whenever another key bit is decided, and there must be a best recoding
sequence for every recoding state that might have been reached so far. For an nbit key suffix, the Ha-Moon algorithm could have generated a recoding sequenceof up to 2n operations and left the recoding finite automaton in one of two states.
Hence there are up to 4n best recoding sequences per trace which need to beextended in order to extract the maximum, and restricting this number turns out
to be detrimental. Hence, in order to generate comparative values we modified
our simulation to use Walter’s metric but without his bound on recoding states.
On its own, this modification arising from the optimal strategy approach led tothe majority of the improvement in performance tabulated below – witness thefirst two rows in Table 2.
Unlike the example in Section 6 we assume a side-channel leakage which
only allows us to distinguish between squarings and multiplications with somecertainty but not between the two multiplicative operations ‘M ’ and ‘M ’ corresponding to digits 1 and −1. This is easy to model. The ith element ti of a trace
T is a set of three probabilities, one for each operation type: ti = {pi0 , pi1 , pi1 }in which we ensure that pi1 = pi1 . We selected this scenario to have a faircomparison with the results in [13].
Let L denote the average level of side channel leakage, that is, the fractionof square or multiply operations which are independently guessed correctly. So
L = ½ means no leakage, when blind guessing makes half the bits correct, andL = 1 corresponds to full leakage, when all operations and hence all bits are completely determined7 . For several realistic cryptographic key lengths and numbersof traces, Table 2 gives the probability that all the incorrectly guessed bits ofthe most likely key are among the 24 bits which the credibility metric shows
are most likely to be in error (see Section 9). It is computationally feasible tocorrect all errors in such guessed keys and thereby recover the true key. The lastcolumn explores the possibility that the most probable key guesses are those forwhich the bit errors are confined to the 24 most dubious positions. This newmeasure is not in previous literature, and clearly indicates that the adversary
can select cases for which the method is more likely to succeed. He collects setsof side channel data for a number of different keys, computes the best-fitting
key in each case, and then selects the 10%, say, which yield the highest value for(15). Then, in parallel for the selected keys, he modifies more and more of the
6

The recoding state is a pair consisting of the state of the recoding finite automaton
and the number of operations it has generated.
7
Guessing all operations to be squarings in the binary exponentiation algorithm makes
two thirds of the operations correct (on average), not a half. Here we are modellingthe noise which is added to the actual recoding sequence, changing the averagecorrectness of the decision between squaring or multiplication from 1 to L.

Schindler & Walter, Optimal Key Recovery

463

most dubious bit values in decreasing order of likelihood until a correct key isfound.
Method Leakage Key No. of Av. No. Fraction with all Fraction for 10%
Level L Length Traces Bit Errors errors in worst 24 best-fitting Keys
[13]1
0.7
192
5
−
0.0027
−
[13]2
0.7
192
5
23.2
0.011
0.020
Here
0.7
192
5
20.7
0.013
0.014
[13]2
0.7
384
10
19.0
0.003
0.002
Here
0.7
384
10
18.2
0.003
0.010
[13]2
0.7
1024
40
13.5
0.3
0.3
Here
0.7
1024
40
13.4
0.28
0.28
”
0.6
192
64
30.9
0.19
0.43
”
0.6
384
128
39.4
0.12
0.24
Table 2. Fraction of key guesses with all bit errors in the 24 most dubious positionsfor Ha-Moon recoding [4]. 1 = original for 10 recodings, 2 = improved version (see text).

12

Conclusion

A computationally feasible algorithm has been presented for determining thesecret key used repeatedly in exponentiations where there is weak side channel
leakage and randomised recoding has been employed in an attempt to nullify
the effect of that leakage. The algorithm was derived from an optimal decision
strategy and is an improvement over prior techniques. Using it, it is easy both todetermine which results have few bit errors, and to locate the potential bit errors.
Hence it is frequently possible to recover the key using much weaker leaked data
than before. The derivation also highlights points where significant modifications
had to be made to the optimal strategy to obtain a computationally feasible
algorithm.

References
1. E. Brier & M. Joye, Weierstraß Elliptic Curves and Side-Channel Attacks, Public
Key Cryptography (Proc. PKC 2002), D. Naccache & P. Paillier (editors), LNCS
2274, Springer-Verlag, 2002, pp. 335–345.
2. D. Chaum, Blind Signatures for Untraceable Payments, Advances in Cryptology –Crypto ’82, D. Chaum, R.L. Rivest & A.T. Sherman (editors), Plenum Press, New
York, 1983, pp. 199–203.
3. P. J. Green, R. Noad & N. Smart, Further Hidden Markov Model Cryptanalysis,
Cryptographic Hardware and Embedded Systems – CHES 2005, J.R. Rao & B.
Sunar (editors), LNCS 3659, Springer-Verlag, 2005, pp. 61–74.

464

Cryptography and Coding, LNCS Vol. 5921 ©Springer, 2009

4. J. C. Ha & S. J. Moon, Randomized Signed-Scalar Multiplication of ECC to Resist
Power Attacks, Cryptographic Hardware and Embedded Systems – CHES 2002,
B. Kaliski, Ç. K. Koç & C. Paar (editors), LNCS 2523, Springer-Verlag, 2002, pp.
551–563.
5. C. Karlof & D. Wagner, Hidden Markov Model Cryptanalysis, Cryptographic Hardware and Embedded Systems – CHES 2003, C. D. Walter, Ç. K. Koç & C. Paar
(editors), LNCS 2779, Springer-Verlag, 2003, pp. 17–34.
6. P. Kocher, Timing Attack on Implementations of Diffie-Hellman, RSA, DSS, andother systems, Advances in Cryptology – Crypto ’96, N. Koblitz (editor), LNCS
1109, Springer-Verlag, 1996, pp. 104–113.
7. P. Kocher, J. Jaffe & B. Jun, Differential Power Analysis, Advances in Cryptology– Crypto ’99, M. Wiener (editor), LNCS 1666, Springer-Verlag, 1999, pp. 388–
397.
8. P.-Y. Liardet & N. P. Smart, Preventing SPA/DPA in ECC Systems using theJacobi Form Cryptographic Hardware and Embedded Systems – CHES 2001, Ç.
K. Koç, D. Naccache & C. Paar (editors), LNCS 2162, Springer-Verlag, 2001, pp.
391–401.
9. E. Oswald & M. Aigner, Randomized Addition-Subtraction Chains as a Countermeasure against Power Attacks, Cryptographic Hardware and Embedded Systems– CHES 2001, Ç. K. Koç, D. Naccache & C. Paar (editors), LNCS 2162, SpringerVerlag, 2001, pp. 39–50.
10. W. Schindler, On the Optimization of Side-Channel Attacks by Advanced Stochastic
Methods, Public Key Cryptography (Proc. PKC 2005), S. Vaudenay (editor), LNCS
3386, Springer-Verlag, 2005, pp. 85–103.
11. C. D. Walter, Breaking the Liardet-Smart Randomized Exponentiation Algorithm,
Proc. Cardis ’02, San José, November 2002, Usenix Association, Berkeley, 2002,
pp. 59–68.
12. C. D. Walter, Issues of Security with the Oswald-Aigner Exponentiation Algorithm,
Topics in Cryptology – CT-RSA 2004, T. Okamoto (editor), LNCS 2964, SpringerVerlag, 2004, pp. 208–221.
13. C. D. Walter, Recovering Secret Keys from Weak Side Channel Traces of Differing Lengths, Cryptographic Hardware and Embedded Systems – CHES 2008, E.
Oswald & P. Rohatgi (editors), LNCS 5154, Springer-Verlag, 2008, pp. 214–227.
14. H. Witting, Mathematische Statistik I, Teubner, Stuttgart 1985.
15. S.-M. Yen, C.-N. Chen, S. J. Moon & J. C. Ha, Improvement on Ha-Moon Randomized Exponentiation Algorithm, Information Security and Cryptology – ICICS
2004, C. Park & S. Chee (editors), LNCS 3506, Springer-Verlag, 2005, pp. 154–167.

A

Appendix

A.1

Algorithmic Treatment of Ha-Moon Recodings

In this subsection we provide an efficient algorithm to compute cred(G, K), defined by (8), for the Ha-Moon recoding scheme [4] for any fixed G ∈ G andK ∈ K. In the recoding step the binary representation K is mapped onto a recoding which is a sequence of digits in {−1, 0, 1} with length len(K) or len(K)+1.
Again, we follow a standard convention in which the letters ‘S’, ‘M ’, and ‘M ’denote a squaring, a multiplication by the base C, and a multiplication by C −1 ,respectively. So, to obtain the corresponding operation sequence, apart from theSchindler & Walter, Optimal Key Recovery

465

most significant digit (= 1), each digit of the recoding is substituted as follows:
0 7→ ‘S’, 1 7→ (‘S’,‘M ’), and −1 7→ (‘S’,‘M ’), yielding an element R ∈ R(K). In
particular, the recoding sequence has length ≤ 2len(K). Note that the probabilities ν(R) are not identical for all R ∈ R(K) in the Ha-Moon recoding scheme.
Assumption 1: We consider the scenario from Theorem 1(ii). We assumedeffurther that K ∈ K = {0, 1}n , and that XK is uniformly distributed on K, i.e.,each admissible key is equally likely. If the next recoding step is not unique therecoding algorithm decides with probability ½ for one of the two alternatives.
Definition 4. (Ha-Moon recoding scheme [4].) For 0 ≤ v ≤ len(K) and K ∈ K
the term R(K, v, len, cv ) ⊆ R(K) denotes the subset of recoding sequences that
require exactly len operations (‘S’, ‘M ’, ‘M ’) and the carry bit cv to encode thev least significant bits of K. Guesses of recoding sequences G = (gj )0≤j<len(G)and recoding sequences R = (rj )0≤j<len(R) are extended to length 2n by defining
def

def

a further symbol, ∞, and setting gj = ∞ for j ≥ len(G) and rj = ∞ forj ≥ len(R). Further, the conditional probability function p(· | ·) is extended so
def

def

def

that p(∞|∞) = 1 and p(a|∞) = p(∞|a) = 0 for a ∈ {‘S’,‘M ’,‘M ’}. This
allows one to increase the upper bound of the product in (4) beyond len(R) − 1
to 2n − 1. For v ≥ 0 the ‘intermediate’
S credibility function associated with theguess G and any subset M ⊆ R(K) = v≤len≤2v; c∈{0,1} R(K, v, len, c) islenv (R)−1defcredv (G, M ) =

X
R∈M

ν(R)

Y

p(gi | ri ).

(17)

i=0

The term lenv (R) denotes the number of operations in R which are used to
encode the key bits kv−1 , ..., k0 . (In particular, for all R ∈ R(K, v, len, c) it islenv (R) = len.)
During recoding, the Ha-Moon scheme generates either one or two operations
per bit of K, and a carry bit equal to 0 or 1. Hence for given v the length ofa recoding sequence ranges from v to 2v, and so R(K) is the disjoint unionof 2(v + 1) (possibly empty) subsets R(K, v, len, c) with v ≤ len ≤ 2v andc ∈ {0, 1}. Algorithm 1 below computes sequentially the credv (G, ·)-values forincreasing parameters v and subsets R(K, v, len, c) ⊆ R(K), which finally yields
the desired value cred(G, K). The definition of the subsets R(K, v, len, c) andthe credv (·, ·)-function are closely related to the components of definition (9)used in the generic description of an algorithm for the efficient computationof cred(G, K). Indeed, both approaches are essentially equivalent. In definition(9) ‘truncated’ recoding sequences are considered, and the product in (17) only
considers these operations. The recoding sequences are elements of R(K) but
the probabilities of all recoding sequences with a fixed suffix add up to theprobability of the truncated recoding sequence. However, the approach chosen
in the appendix is more convenient for Algorithm 1 which splits and merges
subsets of R(K).
The goal of Algorithm 1 is the efficient computation of cred(G, K) for arbitrary but fixed G ∈ G and K ∈ K.

466

Cryptography and Coding, LNCS Vol. 5921 ©Springer, 2009

Remark 3. Our implementation of Algorithm 1 requires the binary representation of key K to contain at least one ‘1’, while Theorems 1 and 2 clearly also
cover the zero key. In our simulation experiments presented in Section 6 werestricted the key space to {0, 1}n \ {(0, . . . , 0)} for simplicity.
def

Algorithm 1. Initialise by setting cred0 (G, R(K, 0, 0, 0)) = Prob(XK = K).
(Note that R(K) = R(K, 0, 0, 0).) Assume that we know the ‘truncated’ credibilities credv (G, R(K, v, u, cv )) for all u ∈ {v, . . . , 2v} and cv ∈ {0, 1}. The next
task is therefore to consider key bit kv and to determine the values credv+1 (G,R(K, v + 1, u, cv+1 )) for v + 1 ≤ u ≤ 2(v + 1) and cv+1 ∈ {0, 1}.
Induction Step (over v):
For each len ∈ {v, . . . , 2v} and cv ∈ {0, 1}:Case A: If (kv , cv ) = (0, 0) the next digit (viewed from right to left) in any recoding is 0 and thus ‘S’ is the next operation in the recoding sequence. In particular,
credv+1 (G, R(K, v+1, len+1, 0) ∩ R(K, v, len, 0)) = p(glen |‘S’)credv (G, R(K, v,
len, 0)).
Case B: If (kv , cv ) = (1, 0) the next digit of the recoding is 1 or −1 (and thus
cv+1 = 0 or cv+1 = 1, respectively), each with probability ½. Consequently,
credv+1 (G, R(K, v+1, len+2, 0)∩R(K, v, len, 0)) = ½p(glen+1 | ‘S’)p(glen | ‘M ’)×
credv (G, R(K, v, len, 0)) and credv+1 (G, R(K, v+1, len+2, 1)∩R(K, v, len, 0)) =½p(glen+1 | ‘S’)p(glen | ‘M ’)credv (G, R(K, v, len, 0)).
Cases C and D: The cases (kv , cv ) = (0, 1) and (kv , cv ) = (1, 1) are treated analogously with R(K, v, len, 1) in place of R(K, v, len, 0). As in Case B above theset R(K, v, len, 1) splits into two subsets if (kv , cv ) = (0, 1), i.e. in Case C.
When this has been completed for all values len ∈ {v, . . . , 2v} and cv ∈ {0, 1},
the credibility values for the subsets R(K, v + 1, len0 , cv+1 ) are easily computed.
For each v + 1 ≤ len0 ≤ 2(v + 1) and cv+1 ∈P{0, 1} ‘related’ subsets are merged to
give: credv+1 (G, R(K, v+1, len0 , cv+1 )) =credv+1 (G, R(K, v+1, len0 , cv+1 ) ∩00 00
R(K, v, len , c )), where the sum extends over all (len00 , c00 ) ∈ {len0 −1, len0 −2}
× {0, 1}. This equality holds because the subsets on the right side of the equation
have a disjoint union equal to the set on the left side. Clearly, credv (G, ∅) = 0 andcredv+1 (G, ∅) = 0, and this enables instances of credv+1 (G, R(K, v+1, len0 , c0 ))to be evaluated without taking a sum over subsets when the second parameteris the empty set.
This completes the induction step from v to v + 1.
This procedure is continued until v = len(K) − 2 (inclusively). The most significant bit of K then needs special treatment because different operations
are used to initialise the exponentiation. Finally, cred(G, K) = credlen(K) (G,R(K, len(K), len(G), 0)).
tuNote that for R ∈ R(K) we have ν(R) = Prob(XK = K)2−bif(R) wherebif(R) stands for the number of ‘bifurcations’ in generating the recoding sequence
R from K, i.e. the number of positions where two recoding choices are possible,
i.e. when (kv , cv ) = (0, 1) or (1, 0). This causes the factor ½ for Cases B and C.

Schindler & Walter, Optimal Key Recovery
A.2

467

Statistical Decision Theory

This subsection provides a brief introduction to statistical decision theory as
far as is relevant to understand the concepts of Theorems 1 and 2. We omit allmathematical details. For a more comprehensive treatment we refer the interested reader to [10], Section 2, or to textbooks in this field (e.g. [14]). Reference[10] illustrates the merits of statistical decision theory for side-channel analysis
by several examples.
Our focus is side-channel analysis. We interpret side-channel measurements
as realisations of random variables, i.e. as values assumed by these randomvariables. The relevant part of the information is covered by noise but an attacker
clearly aims to exploit the available information in an optimal way. Statisticaldecision theory quantifies the impact of the particular pieces of information on
the strength of a decision strategy, and so the search for the optimal decision
strategy can be formalised.
Formally, a statistical decision problem is given by a 5-tuple (Θ, Ω, s, DST , A).
The statistician (in our context the attacker) observes a sample ω ∈ Ω that heinterprets as a realisation of a random variable X with unknown distributionpθ . On basis of this observation he guesses the parameter θ ∈ Θ where Θ denotes the parameter space, i.e., the set of all admissible hypotheses (= possible
parameters). Further, the set Ω is called the observation space, and the letter A
denotes the set of all admissible alternatives the statistician can choose. In thefollowing we assume Θ = A with finite sets Θ and A.
Example 1. ([10], Example 1)(i) Assume that the attacker guesses a particular (single) RSA key bit and that
his decision is based upon N measurements. Then Θ = A = {0, 1}. For timing
attacks, we may assume Ω = RN while Ω = RT N for power attacks where T is
the number of relevant measurement points per power trace.
(ii) Consider a power attack on a DES implementation where the attacker guesses
a particular 6-bit subkey that affects a single S-box in the first round. ThenΘ = A = {0, 1}6 .
The term DST denotes the set of all decision strategies between which thestatistician can choose. A (deterministic) decision strategy is given by a mappingτ : Ω → A. This means that if the statistician applies decision strategy τ hedecides on τ (ω) ∈ A = Θ whenever he observes ω ∈ Ω. (It may be noted thatfor certain statistical applications it is reasonable to consider the more generalclass of randomised decision strategies ([10], Remark 1(i)). For our purposes weneed only concentrate on deterministic decision strategies.)
Finally, the loss function s: Θ × A → [0, ∞) quantifies the harm of a wrong
decision, i.e., s(θ, a) gives the loss if the statistician decides on a ∈ A althoughθ ∈ Θ = A is the correct parameter. In the context of side-channel attacks theloss function quantifies the efforts to detect, to localise and to correct a wrong
def
decision, usually a wrong guess of a key part. Clearly, s(θ, θ) = 0 since a correct
guess does not cause any loss. We point out that for some side-channel attacks

468

Cryptography and Coding, LNCS Vol. 5921 ©Springer, 2009certain types of errors are easier to detect and correct than others ([10], Sect. 6).
The optimal decision strategy takes such phenomena into account.
Assume that the statistician uses the deterministic decision strategy τ : Ω →A and that θ is the correct parameter. The expected loss (= average loss if the
hypothesis θ is true) is given by the r isk functionZ
defr(θ, τ ) =s(θ, τ (ω)) pθ (dω).
(18)Ω

In the context of side-channel attacks one can usually determine (at least approximate) probabilities with which the particular parameters occur. This is quantified by the so-called a priori distribution η, a probability measure on the parameter space Θ.
Example 2. ([10], Example 2)(i) (Continuation of Example 1(i).) Assume that k exponent bits remain to be
guessed and that the attacker knows that r of them are 1. If the secret key was
selected randomly it is reasonable to assume that a particular exponent bit is 1
with probability η(1) = r/k.
(ii) (Continuation of Example 1(ii).) Here η(x) = 2−6 for all x ∈ {0, 1}6 .
Assume that η denotes the a priori distribution. If the statistician applies thedeterministic decision strategy τ : Ω → A the expected loss is given by
X
XZ
def
R(η, τ ) =r(θ, τ )η(θ) =s(θ, τ (ω)) pθ (dω) η(θ).
(19)
θ∈Θ

θ∈Θ

Ω

A decision strategy τ 0 is optimal against η if it minimises the right-hand term.
Such a decision strategy is also called a Bayes strategy against η.
Theorem 3. ([10], Theorem 1(i), (iii))
Assume that (Θ, Ω, s, DST , A) defines a statistical decision problem with finite
parameter space Θ = {θ1 , . . . , θt } = A where DST contains all deterministic
decision strategies. Further, let µ denote a σ-finite measure on Ω with pθi =fθi · µ, i.e. pθi has µ-density fθi , for each i ≤ t.
(i) The deterministic decision strategy τ : Ω → A,
( t
)
t
X
X
def
0
τ (ω) = a ifs(θi , a)η(θi )fθi (ω) = mins(θi , a )η(θi )fθi (ω)
(20)
0
i=1

a ∈A

i=1

is optimal against the a priori distribution η. (If the minimum is attained forseveral decisions, we chose a ∈ A according to any pre-selected order on A.)(ii) Assume that C ⊆ Ω with pθi (C) = p > 0 for all θi ∈ Θ. Then (i) and (ii)remain valid if fθ is replaced by the conditional density fθ|C .
Remark 4. ([10], Remark 2)(i) A σ-finite measure µ on Ω with the properties claimed in Theorem 3 always
exists (e.g. µ = pθ1 + · · · + pθt ).

Schindler & Walter, Optimal Key Recovery

469(ii) For Ω = Rn the well-known Lebesgue measure λn is σ-finite.
(The Lebesgue
Qnmeasure on Rn is given by λn ([a1 , b1 ] × · · · × [an , bn ]) = i=1 (bi − ai ) if bi ≥ ai
for all i ≤ n.) If Ω is finite or countable the counting measure µC is σ-finite.
The counting measure is given by µC (ω) = 1 for all ω ∈ Ω. In particular, theprobabilities Probθ (X = ω) = pθ (ω) can be interpreted as densities with respect
to µC .
(iii) The examples mentioned in (ii) and combinations thereof cover the casesthat are relevant in the context of side-channel analysis.
The probability densities fθ , the a priori distribution η, and the loss functions have an impact on the optimal decision strategy. The probability densities fθ
clearly have most influence, and usually their determination is the tough part of
the work.