Paper 2015/1236

A Bounded-Space Near-Optimal Key Enumeration Algorithm for Multi-Dimensional Side-Channel Attacks

Liron David and Avishai Wool

Abstract

Enumeration of cryptographic keys in order of likelihood based on side-channel leakages has a significant importance in cryptanalysis. Previous algorithms enumerate the keys in optimal order, however their space complexity is $\Omega(n^{d/2})$ when there are d subkeys and n candidate values per subkey. We propose a new key enumeration algorithm that has a space complexity bounded by $O(d^2 w+dn)$, when w is a design parameter, which allows the enumeration of many more keys without exceeding the available space. The trade-off is that the enumeration order is only near-optimal, with a bounded ratio between optimal and near-optimal ranks. Before presenting our algorithm we provide bounds on the guessing entropy of the full key in terms of the easy-to-compute guessing entropies of the individual subkeys. We use these results to quantify the near-optimality of our algorithm's ranking, and to bound its guessing entropy. We evaluated our algorithm through extensive simulations. We show that our algorithm continues its near-optimal-order enumeration far beyond the rank at which the optimal algorithm fails due to insufficient memory, on realistic SCA scenarios. Our simulations utilize a new model of the true rank distribution, based on long tail Pareto distributions, that is validated by empirical data and may be of independent interest.

Note: This ePrint version includes all the proofs omitted from the CT-RSA version

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. Proc. RSA Conference Cryptographers Track (CT-RSA’17), LNCS 10159, pages 311–327, San Francisco, February 2017. Springer Verlag.
Contact author(s)
yash @ eng tau ac il
lirondavid @ gmail com
History
2018-11-11: revised
2015-12-28: received
See all versions
Short URL
https://ia.cr/2015/1236
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1236,
      author = {Liron David and Avishai Wool},
      title = {A Bounded-Space Near-Optimal Key Enumeration Algorithm for Multi-Dimensional Side-Channel Attacks},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1236},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1236}},
      url = {https://eprint.iacr.org/2015/1236}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.