Optimal Recovery
of Secret Keys fromWeak Side Channel Traces
Werner Schindler

Colin D. Walter

BSI, Germany

RHUL, UK

Werner.Schindler@bsi.bund.de

Colin.Walter@comodo.com

Outline• The problem, background & history• A typical randomised exponentiation algorithm• The optimal decision strategy– General strategy and the Main Theorem– Example• A metric to measure fitness of recoding guesses• Results• Conclusion
IMA 2009

2/24
Werner Schindler (BSI) & Colin Walter (RHUL)Background
Several standard SW measures to counteract
Side Channel Leakage from Exponentiation:1. Blind the exponent by adding
a random multiple of the group order.
2. Pick an algorithm where the pattern is
independent of the secret exponent, e.g.
– Square-and-always-multiply– Montgomery Powering Ladder

3. Use an algorithm where the pattern is randomised:– Liardet-Smart– Oswald-Aigner– Ha-Moon– Mist

We look at the strength of (3) with Ha-Moon for examples.
IMA 2009

3/24
Werner Schindler (BSI) & Colin Walter (RHUL)Problems for an Attacker•There is always a lot of noise in measurements.

•Averaging to determine correct key bits is essential.

•For randomised exponentiation algorithms,
Square & Multiply operations
cannot be aligned directly with key bits.

•Incorrect bit deductions will always occur.

•The locations of likely errors must be identified
for a computationally feasible algorithm.

IMA 2009

4/24
Werner Schindler (BSI) & Colin Walter (RHUL)Example: Ha-Moon
Recode the binary representation of key K from right to left:• Add in the Carry of 0 or +1 to give new K.
• Choose digit 0 if K even.
• Randomly choose digit ±1 if K odd.
• Set Carry to be 1 for digit –1, otherwise 0, & shift K down.
Exponentiation MK in ECC:
• Repeatedly:i) read next digit (from left to right)ii) perform point doubleiii) do point add if d =1 or point subtract if d = –1.
Traces may have different lengths: the ith operation isassociated with different bits in different traces.
IMA 2009

5/24
Werner Schindler (BSI) & Colin Walter (RHUL)Ha-Moon (II)Here are some recodings of 32n+13:(D = double, A = add)
…0 1 1 0 1…
D D A D A D D A… 0 1 1 1 –1

… D D A

D A

D A

D A

… 1 0 0 –1 –1

…

D A

D D

D A

D A

… 1 0 –1 0 1…

D A

D DA DD A… 1 0 –1 1 –1

… D A D

D A

D A

D A

… 1 –1 1 0 1… D A D

A D

A D

D A

Aim: to recover K from leakage like the above.
The average operator yields almost no information:
data from the top bit gets spread over several columns.
IMA 2009

6/24
Werner Schindler (BSI) & Colin Walter (RHUL)

History
Karlov & Wagner (CHES 2003)
Green, Noad & Smart (CHES 2005)••••

Uses a Hidden Markov Model
Applies Viterbi’s algorithm to find the best fit key.
Treats traces serially one by one
Convergence is unlikely with weak leakage – it can’t get started.

Walter (CHES 2008)•••

Restructured to process traces in parallel, and bits serially
Better convergence on weak leakage
Lack of sound theoretical justification

Schindler (PKC 2005)••

Optimal decision strategy identifying most likely key
Computationally infeasible in this context

IMA 2009

7/24
Werner Schindler (BSI) & Colin Walter (RHUL)A Formal Approach (I)Set of admissible keys:• K ⊆ F2*
Set of all possible recoding sequences:• R ⊆ D* where D = {admissible recoding digits}
Strategy (generic description):• For each power trace powj (1≤j≤N) guess the individual
recoding digits, yielding (disturbed, possibly invalid)
noisy recoding sequences G1,…,GN ⊆ D*.
• Select the key K* that fits G1,…,GN best.

8/24

IMA 2009
Werner Schindler (BSI) & Colin Walter (RHUL)A Formal Approach (II)Interpretation of the noisy recoding sequences
as a two-step random experiment:• jth randomised recoding sequence:
φ: K × Y → R , ϕ(K,yj) := Rj
where yj is a random number. The target
device contains a Finite Automaton to do this.
• jth noisy recoding guess:ψ: R × Z → D*, ψ(R,zj) := Gj
where zj is a random number. The result of
the adversary’s inaccurate measurements.
9/24

IMA 2009
Werner Schindler (BSI) & Colin Walter (RHUL)

Main Theorem (I)Theorem 1(ii) (a special case):
Assumptions:• The unknown key K has been selected randomly
according to some probability distribution η• Given recoding sequence guesses G1,…,GN.
• The adversary can detect whenever an operation of
the recoded sequence R is carried out and guesses
the types of these operations independently.
Notation: p(g|r) :=Prob(guessed opn type is g given the true opn type is r)
10/24

IMA 2009
Werner Schindler (BSI) & Colin Walter (RHUL)

Main Theorem (II)Theorem 1(ii) (special case, ctd’):
The optimal decision strategy selects a key K* ∈ Kthat maximises the termlen ( G j ) −1N∑ log( ∑j =1R∈R ( K ):len ( R ) =len ( G j )∏ p( g | r ))j ,iii =0assuming keys and recodings are distributed uniformly.
Note: Theorem 1(i) in the paper treats the most general case.

11/24

IMA 2009
Werner Schindler (BSI) & Colin Walter (RHUL)Traces
The side channel gives a sequence of probabilities that theunderlying operations correspond to particular digits.
• So we define a trace by T = (ti){0 ≤ i < len(G)}with ti = probability distribution on D(depending on the power trace)• Thm 2 (a corollary of Thm 1 for traces) enables us toreplace p(gj|r) by ti and so avoid guessing recodings G.

12/24

IMA 2009
Werner Schindler (BSI) & Colin Walter (RHUL)Example (I)Application of Theorem 1(ii):Ha-Moon recoding with artificially_ small parameters:• K = {0,1}n \ {(0,…,0)}, D = {‘S’,’M’, ‘M’}
Stochastic simulations– Select K randomly– Generate N recoding sequences R1,….,RN– Generate N noisy recoding sequences G1,….,GNby flipping recoding digits randomly• More precisely:_p(‘M’_ | ‘S’ ) = 0.2, p(‘M’ | ‘S’ ) = 0.1p(‘M’ | ‘M’_ ) = 0.2, p(‘S’ | ‘M’_ ) = 0.1p(‘M’ | ‘M’ ) = 0.2, p(‘S’ | ‘M’ ) = 0.1
13/24

IMA 2009
Werner Schindler (BSI) & Colin Walter (RHUL)Example (II)Application of Theorem 1(ii):Ha-Moon recoding with artificially small parameters:• 100 stochastic simulations per table row
The correct key was ranked
Keylength# traces

1st2nd

3rd 9th

10th 99th100999>1000

15108459110201057202021014/24

IMA 2009Werner Schindler (BSI) & Colin Walter (RHUL)Example (III)Application of Theorem 1(ii): Ha-Moon recoding withartificially small parameters:• These numerical results are remarkable since each
recoding digit is correctly recognised despite
probability of only 70% for individual operations!
However,• unlike in many other side-channel attacks the optimal
decision strategy cannot be applied to small portionsof the key.
• Hence the application of Theorem 1 is infeasible
for real-world key parameters.
• Starting from the optimal decision strategy acomputationally feasible approximator is derived.
15/24

IMA 2009
Werner Schindler (BSI) & Colin Walter (RHUL)

The Metric (I)Replace CHES08 distance between a trace t and recoding rµ(t,r) = ∑i (1-pi)

by “credibility” µ(t,r) = ∏i pi

where pi is probability that the ith operation in t is thesame as the ith operation for r. (Hamming dist. vs Proby.)
p1

A

p3 p4
p2

p5

D
Double/Add pattern of recoding
Trace probabilities of matching “A” or “D”µ = p1 × p2 × p3 × p4 × ...
IMA 2009

16/24
Werner Schindler (BSI) & Colin Walter (RHUL)

The Metric (II)•Define the credibility of key choice K for a trace t byµ(t,K) = ∑r { µ(t,r) | r is a recoding of K }This selects the best match recoding of K.
11... max µ
10

100

1

Apply to trace prefix:
Build tree of depth λ,0Select leaf with max µ,
Pick bit at root of that branch
IMA 2009

010

Werner Schindler (BSI) & Colin Walter (RHUL)

17/24

The Metric (II)•Define the credibility of key choice K for a trace t byµ(t,K) = ∑r { µ(t,r) | r is a recoding of K }This selects the best match recoding of K.
11Oops! Nothing works!

... max µ
101001

Apply to trace prefix:
Build tree of depth λ,0Select leaf with max µ,
Pick bit at root of that branch
IMA 2009

010Werner Schindler (BSI) & Colin Walter (RHUL)

18/24

The Metric (III)•Modify the credibility definition, replacing “sum” by “max”:µ(t,K) = max { µ(t,r) | r is a recoding of K }to select the best match recoding of K.
11... max µ
10100

1

Apply to trace prefix:Build tree of depth λ,0
Select leaf with max µ,
Pick bit at root of that branch
IMA 2009

010

Werner Schindler (BSI) & Colin Walter (RHUL)

19/24

The Metric (III)•Define the credibility of key choice K for a trace t byµ(t,K) = max { µ(t,r) | r is a recoding of K }This selects the best match recoding of K.
1
1This works!

... max µ101001

Apply to trace prefix:
Build tree of depth λ,0
Select leaf with max µ,
Pick bit at root of that branch
IMA 2009

010

Werner Schindler (BSI) & Colin Walter (RHUL)

20/24

The Metric (IV)
1. Define the credibility of a recoding r for trace t byµ(t,r) = ∏i pi
where pi is probability that the ith operation in t
is the same as the ith operation for r.
This should be large for correct interpretation of the trace.
2. Define the credibility of a key choice K for trace t byµ(t,K) = max { µ(t,r) | r is a recoding of K }to select the best match recoding of K.
3. Define the credibility of a key K for trace set T byµ(T,K) = ∑t∈∈T log(µ(t,K)) or ∑t∈∈T µ(t,K)
The best fit key maximises this. (The latter is slightly better.)
IMA 2009

21/24
Werner Schindler (BSI) & Colin Walter (RHUL)Properties•

Traces become aligned correctly (or almost correctly)with key bits/digits by selecting the best fit recoding.

•Summing the metric values for best recodings of each traceprovides the averaging that reduces noiseand enables the best key bit to be selected.

•Locations for incorrect bits can be determinedby looking at the difference in the credibilityof the 0- and 1- branches of a node in the tree.
A small difference means lack of certainty about the decision.

•Key bit positions can be orderedaccording to this probability of correctness.
IMA 2009

22/24
Werner Schindler (BSI) & Colin Walter (RHUL)

Some Figures•

Take the Ha-Moon 1 recoding.

•

Assume a 70% chance of deciding correctly between
a square or multiplication from the side channel trace,
but unable to distinguish the multiplications for –1 and +1.

•Take typical 192-bit ECC key & only 5 traces.

•On average there are only 20.7 bit errors•

In 1.3% of cases there are no errors in the 168 bits we aremost certain of, leaving just 24 known bits to check.

•It is computationally feasible to correct all errors in these.

IMA 2009

23/24
Werner Schindler (BSI) & Colin Walter (RHUL)

Conclusion• Traces from randomised exponentiation algorithms
can be aligned effectively to pool weak side channel
leakage associated with individual key bits.
• Locations of possible bit errors are identified with ease,making it computationally feasible to correct them.
• Theoretical results on the optimal decision strategy wereapplied to redesign a previous algorithm for this.
• A more successful algorithm resulted, with sounder basis
and better understanding of good parameters to choose.
IMA 2009

24/24
Werner Schindler (BSI) & Colin Walter (RHUL)