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 cadidate 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.
Category / Keywords: side channel attacks, DPA, key enumeration, AES-NI Original Publication (with minor differences): SAC 2015 Date: received 8 Aug 2015, last revised 2 Oct 2015 Contact author: ilya kizhvatov at gmail com Available format(s): PDF | BibTeX Citation Note: Typos fixed, plots improved, a related paper cited. Version: 20151002:095359 (All versions of this report) Short URL: ia.cr/2015/795 Discussion forum: Show discussion | Start new discussion