Transcript Hidden Markov Model Cryptanalysis

Hidden Markov Model Cryptanalysis
Chris Karlof and David Wagner
The Context: Side Channels and
Countermeasures




The “Side Channel”: data gathered from the
operation of a crypto scheme’s
implementation
Example: measuring power fluctuations of
Pentium III processor when performing RSA
decryption (SPA, DPA)
Many processors draw different power for
adds and multiplies or other operations
Countermeasures: obscure the signature of
key-related operations
Randomized Countermeasures




Introduce random computations
Example: randomized projective coordinates
in Elliptic Curve computations
Projective coordinates (X,Y,Z) of P = (x,y) are
given by:
Before each execution of the scalar mult to
compute Q = dP, (X,Y,Z) are randomized with
a random 
for every ≠ 0 in the finite field
Coron, J.S.. “Resistance Against Differential Power Analysis for Elliptic Curve Cryptosystems”, 1999.
Attacks on Randomized Countermeasures


Existing attacks are specific to each
countermeasure
No general framework or model exists for all
randomized side channel countermeasures
Modeling Side-Channel Countermeasures


To attack a randomized countermeasure, it
would be great to model it first
One model for simple countermeasures:
Probabilistic Finite State Machine (PFSM)
Red lines
indicate
optional
state
transitions
From Oswald, E. and Aigner, M. “Randomized Addition-Subtraction Chains as a Countermeasure against Power
Attacks.” (2001)
Key Recovery/Inference Problem for PFSM
Need to assume PFSM is “faithful”
i.e. no ambiguity in state transitions
 For all si and sj  S, set of states in
PFSM, and  = S x S x I (input bit):
If  (si, sj, 0) > 0 then  (si, sj, 1) = 0

Key Recovery/Inference Problem for
PFSM

We want to infer the sequence of states
traversed in a given execution of state
machine M given


M and
Traces of the side channel, y = {y1, y2,…,
yN} (N = number of key bits i.e. number of
state transitions)
Solution to PFSM Inference Problem

Maximum Likelihood Decoding:
Input: trace y, PFSM M, state transition s, set of states S, Q =
random variable of execution of M
1. Calc Pr [Q = s|y] for each s  SN+1
2. Output q = argmax Pr[Q = s|y]


Running Time: Exponential
This paper presents how to transform
PFSM into HMM, which has poly-time
solution to its inference problem (using
Viterbi Algorithm)
Hidden Markov Models (HMMs)



Sequence of hidden, probabilistic states
(S)
Corresponding observable outputs (O)
Each state is independent of every
other (memoryless)
P (S1 = x1)
P (S2 = x2)
P (S3 = x3)
O1
O2
O3
HMMs: The Inference Problem



Definition: infer the values of the hidden
states given only the observable outputs
Viterbi algorithm solves the Inference
Problem efficiently: O(|S|2 * N)
Are we done, then?
Input-Driven Hidden Markov Models




HMMs do not model inputs
Inputs are present in crypto systems i.e.
secret keys
The Viterbi algorithm on HMMs does not
benefit from analysis of multiple traces of the
side channel
The paper presents IDHMMs and an
algorithm on IDHMMs that benefits from
multiple traces (useful in a noisy
environment)
Input-Driven Hidden Markov Models

IDHMMs extend HMMs by


Treating inputs as random variable Kn at
each step n
Add other random variables to capture
multiple execution/trace pairs



Ynr (list of R trace outputs) and
Qnr (R sequences of state transitions)
The solution to IDHMMs is a sequence
of random variables, not quantities {0,1}
Solution to I-D Hidden Markov Models


Can’t use Maximum Likelihood
Decoding: exponential
Can’t use Viterbi Alglorithm: (1) inputs
are present and (2) can’t leverage
multiple trace data
Solution to IDHMMs (cont.)


Tried variation on Viterbi -> also
exponential with R, number of traces
Belief Propagation: new technique:



Compute a separate inference of the key K
for each trace, Kr, for trace r
For the r +1 trace, use Pr [Kr | yr] posterior
distribution of keys as inputs
We “propagate” biases derived in prior
trace analyses to the following trace
analyses
Solution to IDHMMs (cont.)

Algorithm Progression:


Compute each r single-trace inference
using the r-1 key probability distribution as
input (r0 = Uniform distribution)
Best estimate of the key: for probability
distribution of keys KR ->

INFER(K11)
K11
If Pr [KiR = 1 | Y=y] > 0.5 then k = 1, else k = 0
INFER(K1
2)
K1
2
INFER(K1
r)
K1
r
k1 =1
k1 = 0
An Attack Experiment




The authors use two randomized
countermeasures as targets.
The countermeasures must be modeled in a
specific way to be attacked using the authors’
method
The authors transform the countermeasures’
models into compatible models (PFSMs)
They run their attack with errors introduced
into the traces. Pr [error] is assumed to be
known to attacker.
Attack Experiment


A PFSM for
randomized
exponentiation e.g.
15P = 16P - P =
2(2(2(2P))) - P
The transformation is
applied at any step of
the algorithm with
Pr[0.5]
Attacking Randomized Countermeasures


182 key bits must be minimally recovered to
be “successful.” Meet-in-the-middle search
for last 10 bits takes 238 work.
Error-less observations lead to key recovery
with less than 10 traces
Conclusion



Authors introduced HMM attacks for
randomized side channel
countermeasures modeled by PFSMs
Presented IDHMMs and efficient
approximate inference algorithm for
inputs (keys)
Demonstrated input inference algorithm
on two randomize countermeasures in
which keys could be recovered with less
than 10 traces