Paper 2016/609

How low can you go? Using side-channel data to enhance brute-force key recovery

Jake Longo, Daniel P. Martin, Luke Mather, Elisabeth Oswald, Benjamin Sach, and Martijn Stam

Abstract

Side-channel analysis techniques can be used to construct key recovery attacks by observing a side-channel medium such as the power consumption or electromagnetic radiation of a device while is it performing cryptographic operations. These attack results can be used as auxiliary information in an enhanced brute-force key recovery attack, enabling the adversary to \emph{enumerate} the most likely keys first. We use algorithmic and implementation techniques to implement a time- and memory-efficient key \emph{enumeration} algorithm, and in tandem identify how to optimise throughput when bulk-verifying quantities of candidate AES-128 keys. We then explore how to best distribute the workload so that it can be deployed across a significant number of CPU cores and executed in parallel, giving an adversary the capability to enumerate a very large number of candidate keys. We introduce the tool \textsc{labynkyr}, developed in C++11, that can be deployed across any number of CPUs and workstations to enumerate keys in parallel. We conclude by demonstrating the effectiveness of our tool by successfully enumerating $2^{48}$ AES-128 keys in approximately 30 hours using a modest number of CPU cores, at an expected cost of only 700 USD using a popular cloud provider.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. Minor revision.
Keywords
Side channel analysiskey enumeration
Contact author(s)
luke t mather @ gmail com
dan martin @ bristol ac uk
elisabeth oswald @ bristol ac uk
martijn stam @ bristol ac uk
jake longo @ bristol ac uk
History
2016-06-14: received
Short URL
https://ia.cr/2016/609
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/609,
      author = {Jake Longo and Daniel P.  Martin and Luke Mather and Elisabeth Oswald and Benjamin Sach and Martijn Stam},
      title = {How low can you go? Using side-channel data to enhance brute-force key recovery},
      howpublished = {Cryptology ePrint Archive, Paper 2016/609},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/609}},
      url = {https://eprint.iacr.org/2016/609}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.