Chris Karlof and David Wagner

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-03-1244

, 2003

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/CSD-03-1244.pdf

We present HMM attacks, a new type of cryptanalysis based on modeling randomized side channel countermeasures as Hidden Markov Models (HMM's). We also introduce Input Driven Hidden Markov Models (IDHMM's), a generalization of HMM's that provides a powerful and unified cryptanalytic framework for analyzing countermeasures whose operational behavior can be modeled by a probabilistic finite state machine. IDHMM's generalize previous cryptanalyses of randomized side channel countermeasures, and they also often yield better results. We present efficient algorithms for key recovery using IDHMM's. Our methods can take advantage of multiple traces of the side channel and are inherently robust to noisy measurements. Lastly, we apply IDHMM's to analyze two randomized exponentiation algorithms proposed by Oswald and Aigner. We completely recover the secret key using as few as ten traces of the side channel.

---

BibTeX citation:

@techreport{Karlof:CSD-03-1244,
    Author= {Karlof, Chris and Wagner, David},
    Title= {Hidden Markov Model Cryptanalysis},
    Year= {2003},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5545.html},
    Number= {UCB/CSD-03-1244},
    Abstract= {We present HMM attacks, a new type of cryptanalysis based on modeling randomized side channel countermeasures as Hidden Markov Models (HMM's). We also introduce Input Driven Hidden Markov Models (IDHMM's), a generalization of HMM's that provides a powerful and unified cryptanalytic framework for analyzing countermeasures whose operational behavior can be modeled by a probabilistic finite state machine. IDHMM's generalize previous cryptanalyses of randomized side channel countermeasures, and they also often yield better results. We present efficient algorithms for key recovery using IDHMM's. Our methods can take advantage of multiple traces of the side channel and are inherently robust to noisy measurements. Lastly, we apply IDHMM's to analyze two randomized exponentiation algorithms proposed by Oswald and Aigner. We completely recover the secret key using as few as ten traces of the side channel.},
}

EndNote citation:

%0 Report
%A Karlof, Chris 
%A Wagner, David 
%T Hidden Markov Model Cryptanalysis
%I EECS Department, University of California, Berkeley
%D 2003
%@ UCB/CSD-03-1244
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5545.html
%F Karlof:CSD-03-1244