Fast and memory-efficient key recovery in side-channel attacks

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

20 Citations (Scopus)

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 divideand- 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 publicationSelected Areas in Cryptography - SAC 2015 - 22nd International Conference, 2015, Revised Selected Papers
PublisherSpringer Verlag
Pages310-327
Number of pages18
Volume9566
ISBN (Print)9783319313009
DOIs
Publication statusPublished - 2016
MoE publication typeA4 Article in a conference publication
EventSelected Areas in Cryptography - Sackville, Canada
Duration: 12 Aug 201514 Aug 2015
Conference number: 22

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9566
ISSN (Print)03029743
ISSN (Electronic)16113349

Conference

ConferenceSelected Areas in Cryptography
Abbreviated titleSAC
CountryCanada
CitySackville
Period12/08/201514/08/2015

Fingerprint Dive into the research topics of 'Fast and memory-efficient key recovery in side-channel attacks'. Together they form a unique fingerprint.

Cite this