Paper 2015/689

Counting Keys in Parallel After a Side Channel Attack

Daniel P. Martin, Jonathan F. O'Connell, Elisabeth Oswald, and Martijn Stam

Abstract

Side channels provide additional information to skilled adversaries that reduce the effort to determine an unknown key. If sufficient side channel information is available, identification of the secret key can even become trivial. However, if not enough side information is available, some effort is still required to find the key in the key space (which now has reduced entropy). To understand the security implications of side channel attacks it is then crucial to evaluate this remaining effort in a meaningful manner. Quantifying this effort can be done by looking at two key questions: first, how `deep' (at most) is the unknown key in the remaining key space, and second, how `expensive' is it to enumerate keys up to a certain depth? We provide results for these two challenges. Firstly, we show how to construct an extremely efficient algorithm that accurately computes the rank of a (known) key in the list of all keys, when ordered according to some side channel attack scores. Secondly, we show how our approach can be tweaked such that it can be also utilised to enumerate the most likely keys in a parallel fashion. We are hence the first to demonstrate that a smart and parallel key enumeration algorithm exists.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in ASIACRYPT 2015
Keywords
key enumerationkey rankside channels
Contact author(s)
j oconnell @ bris ac uk
History
2015-09-04: last of 2 revisions
2015-07-13: received
See all versions
Short URL
https://ia.cr/2015/689
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/689,
      author = {Daniel P.  Martin and Jonathan F.  O'Connell and Elisabeth Oswald and Martijn Stam},
      title = {Counting Keys in Parallel After a Side Channel Attack},
      howpublished = {Cryptology ePrint Archive, Paper 2015/689},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/689}},
      url = {https://eprint.iacr.org/2015/689}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.