Fast and Memory-Efficient Key Recovery in Side-Channel Attacks

Andrey Bogdanov, Ilya Kizhvatov, Kamran Manzoor, Elmar Wolfgang Tischhauser, Marc Witteman

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Side-channel attacks are powerful techniques to attack implementations of cryptographic algorithms by observing its physical parameters such as power consumption and electromagnetic radiation that are modulated by the secret state. Most side-channel attacks are of divide-and-conquer nature, that is, they yield a ranked list of secret key chunks, e.g., the subkey bytes in AES. The problem of the key recovery is then to find the correct combined key.

An optimal key enumeration algorithm (OKEA) was proposed by Charvillon et al. at SAC’12. Given the ranked key chunks together with their probabilities, this algorithm outputs the full combined keys in the optimal order – from more likely to less likely ones. OKEA uses plenty of memory by its nature though, which limits its practical efficiency. Especially in the cases where the side-channel traces are noisy, the memory and running time requirements to find the right key can be prohibitively high.

To tackle this problem, we propose a score-based key enumeration algorithm (SKEA). Though it is suboptimal in terms of the output order of candidate combined keys, SKEA’s memory and running time requirements are more practical than those of OKEA. We verify the advantage at the example of a DPA attack on an 8-bit embedded software implementation of AES-128. We vary the number of traces available to the adversary and report a significant increase in the success rate of the key recovery due to SKEA when compared to OKEA, within practical limitations on time and memory. We also compare SKEA to the probabilistic key enumeration algorithm (PKEA) by Meier and Staffelbach and show its practical superiority in this case.

SKEA is efficiently parallelizable. We propose a high-performance solution for the entire conquer stage of side-channel attacks that includes SKEA and the subsequent full key testing, using AES-NI on Haswell Intel CPUs.
Original languageEnglish
Title of host publication22nd International Conference on Selected Areas in Cryptography (SAC 2015) : Revised Selected Papers
EditorsOrr Dunkelman, Liam Keliher
PublisherSpringer
Publication date2016
Pages310-327
ISBN (Print)978-3-319-31300-9
ISBN (Electronic)978-3-319-31301-6
DOIs
Publication statusPublished - 2016
Event22nd International Conference on Selected Areas in Cryptography - Sackville, Canada
Duration: 12 Aug 201514 Aug 2015
Conference number: 22
http://mta.ca/sac2015/

Conference

Conference22nd International Conference on Selected Areas in Cryptography
Number22
CountryCanada
CitySackville
Period12/08/201514/08/2015
Internet address
SeriesLecture Notes in Computer Science
Volume9566
ISSN0302-9743

Cite this

Bogdanov, A., Kizhvatov, I., Manzoor, K., Tischhauser, E. W., & Witteman, M. (2016). Fast and Memory-Efficient Key Recovery in Side-Channel Attacks. In O. Dunkelman, & L. Keliher (Eds.), 22nd International Conference on Selected Areas in Cryptography (SAC 2015): Revised Selected Papers (pp. 310-327). Springer. Lecture Notes in Computer Science, Vol.. 9566 https://doi.org/10.1007/978-3-319-31301-6_19