Counting keys in parallel after a side channel attack

Daniel P. Martin; Jonathan F. O’Connell; Elisabeth Oswald; Martijn Stam

doi:10.1007/978-3-662-48800-3_13

Counting keys in parallel after a side channel attack

Daniel P. Martin^*, Jonathan F. O’Connell, Elisabeth Oswald, Martijn Stam

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English
Title of host publication	Advances in Cryptology – ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
Editors	Tetsu Iwata, Jung Hee Cheon
Publisher	Springer Verlag
Pages	313-337
Number of pages	25
ISBN (Print)	9783662487990
DOIs	https://doi.org/10.1007/978-3-662-48800-3_13
Publication status	Published - 2015
Event	21st International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2015 - Auckland, New Zealand Duration: 29 Nov 2015 → 3 Dec 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9453
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2015
Country/Territory	New Zealand
City	Auckland
Period	29/11/15 → 3/12/15

Bibliographical note

Funding Information:
We would like to thank Benjamin Sach and Raphael Clifford for there valuable insight and advice during the developement of the algorithm. This work was carried out using the computational facilities of the Advanced Computing Research Centre, University of Bristol - http://www.bris.ac.uk/acrc/. Daniel, Jonathan and Elisabeth have been supported by an EPSRC Leadership Fellowship EP/I005226/1.

Publisher Copyright:
© International Association for Cryptologic Research 2015.

Keywords

Key enumeration
Key rank
Side channels

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-662-48800-3_13

Cite this

Martin, D. P., O’Connell, J. F., Oswald, E., & Stam, M. (2015). Counting keys in parallel after a side channel attack. In T. Iwata, & J. H. Cheon (Eds.), Advances in Cryptology – ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (pp. 313-337). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9453). Springer Verlag. https://doi.org/10.1007/978-3-662-48800-3_13

Martin, Daniel P. ; O’Connell, Jonathan F. ; Oswald, Elisabeth et al. / Counting keys in parallel after a side channel attack. Advances in Cryptology – ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. editor / Tetsu Iwata ; Jung Hee Cheon. Springer Verlag, 2015. pp. 313-337 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{814fbbd534e6475f9dc2d376e1ccfd0b,

title = "Counting keys in parallel after a side channel attack",

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 {\textquoteleft}deep{\textquoteright} (at most) is the unknown key in the remaining key space, and second, how {\textquoteleft}expensive{\textquoteright} 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.",

keywords = "Key enumeration, Key rank, Side channels",

author = "Martin, {Daniel P.} and O{\textquoteright}Connell, {Jonathan F.} and Elisabeth Oswald and Martijn Stam",

note = "Funding Information: We would like to thank Benjamin Sach and Raphael Clifford for there valuable insight and advice during the developement of the algorithm. This work was carried out using the computational facilities of the Advanced Computing Research Centre, University of Bristol - http://www.bris.ac.uk/acrc/. Daniel, Jonathan and Elisabeth have been supported by an EPSRC Leadership Fellowship EP/I005226/1. Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2015.; 21st International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2015 ; Conference date: 29-11-2015 Through 03-12-2015",

year = "2015",

doi = "10.1007/978-3-662-48800-3_13",

language = "English",

isbn = "9783662487990",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "313--337",

editor = "Tetsu Iwata and Cheon, {Jung Hee}",

booktitle = "Advances in Cryptology – ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Proceedings",

}

Martin, DP, O’Connell, JF, Oswald, E & Stam, M 2015, Counting keys in parallel after a side channel attack. in T Iwata & JH Cheon (eds), Advances in Cryptology – ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9453, Springer Verlag, pp. 313-337, 21st International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2015, Auckland, New Zealand, 29/11/15. https://doi.org/10.1007/978-3-662-48800-3_13

Counting keys in parallel after a side channel attack. / Martin, Daniel P.; O’Connell, Jonathan F.; Oswald, Elisabeth et al.
Advances in Cryptology – ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. ed. / Tetsu Iwata; Jung Hee Cheon. Springer Verlag, 2015. p. 313-337 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9453).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Counting keys in parallel after a side channel attack

AU - Martin, Daniel P.

AU - O’Connell, Jonathan F.

AU - Oswald, Elisabeth

AU - Stam, Martijn

N1 - Funding Information: We would like to thank Benjamin Sach and Raphael Clifford for there valuable insight and advice during the developement of the algorithm. This work was carried out using the computational facilities of the Advanced Computing Research Centre, University of Bristol - http://www.bris.ac.uk/acrc/. Daniel, Jonathan and Elisabeth have been supported by an EPSRC Leadership Fellowship EP/I005226/1. Publisher Copyright: © International Association for Cryptologic Research 2015.

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Key enumeration

KW - Key rank

KW - Side channels

UR - http://www.scopus.com/inward/record.url?scp=84952642864&partnerID=8YFLogxK

U2 - 10.1007/978-3-662-48800-3_13

DO - 10.1007/978-3-662-48800-3_13

M3 - Conference contribution

AN - SCOPUS:84952642864

SN - 9783662487990

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 313

EP - 337

BT - Advances in Cryptology – ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Proceedings

A2 - Iwata, Tetsu

A2 - Cheon, Jung Hee

PB - Springer Verlag

T2 - 21st International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2015

Y2 - 29 November 2015 through 3 December 2015

ER -

Martin DP, O’Connell JF, Oswald E, Stam M. Counting keys in parallel after a side channel attack. In Iwata T, Cheon JH, editors, Advances in Cryptology – ASIACRYPT 2015 - 21st International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Springer Verlag. 2015. p. 313-337. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-662-48800-3_13

Counting keys in parallel after a side channel attack

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this