Technical reports

Efficient multivariate statistical techniques for extracting secrets from electronic devices

Marios O. Choudary

September 2015, 164 pages

This technical report is based on a dissertation submitted July 2014 by the author for the degree of Doctor of Philosophy to the University of Cambridge, Darwin College.

Abstract

In 2002, Suresh Chari, Rao Josyula and Pankaj Rohatgi presented a very powerful method, known as the ‘Template Attack’, to infer secret values processed by a microcontroller, by analysing its power-supply current, generally known as its ‘side-channel leakage’. This attack uses a profiling step to compute the parameters of a multivariate normal distribution from the leakage of a training device, and an attack step in which these parameters are used to infer a secret value (e.g. cryptographic key) from the leakage of a target device. This has important implications for many industries, such as pay-TV or banking, that use a microcontroller executing a cryptographic algorithm to authenticate their customers.

In this thesis, I describe efficient implementations of this template attack, that can push its limits further, by using efficient multivariate statistical analysis techniques. Firstly, I show that, using a linear discriminant score, we can avoid some numerical obstacles, and use a large number of leakage samples to improve the attack, while also drastically decreasing its computation time. I evaluate my implementations on an 8-bit microcontroller, using different compression methods, including Principal Component Analysis (PCA) and Fisher’s Linear Discriminant Analysis (LDA), and I provide guidance for the choice of attack algorithm. My results show that we can determine almost perfectly an 8-bit target value, even when this value is manipulated by a single LOAD instruction.

Secondly, I show that variability caused by the use of either different devices or different acquisition campaigns can have a strong impact on the performance of these attacks. Using four different Atmel XMEGA 256 A3U 8-bit devices, I explore several variants of the template attack to compensate for this variability, and I show that, by adapting PCA and LDA to this context, we can reduce the entropy of an unknown 8-bit value to below 1.5 bits, even when using one device for profiling and another one for the attack.

Then, using factor analysis, I identify the main factors that contribute to the correlation between leakage samples, and analyse the influence of this correlation on template attacks. I show that, in some cases, by estimating the covariance matrix only from these main factors, we can improve the template attack. Furthermore, I show how to use factor analysis in order to generate arbitrary correlation matrices for the simulation of leakage traces that are similar to the real leakage.

Finally, I show how to implement PCA and LDA efficiently with the stochastic model presented by Schindler et al. in 2005, resulting in the most effective kind of profiled attack. Using these implementations, I demonstrate a profiled attack on a 16-bit target.

Full text

PDF (14.5 MB)

BibTeX record

@TechReport{UCAM-CL-TR-878,
  author =	 {Choudary, Marios O.},
  title = 	 {{Efficient multivariate statistical techniques for
         	   extracting secrets from electronic devices}},
  year = 	 2015,
  month = 	 sep,
  url = 	 {https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-878.pdf},
  institution =  {University of Cambridge, Computer Laboratory},
  doi = 	 {10.48456/tr-878},
  number = 	 {UCAM-CL-TR-878}
}