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

Liron David; Avishai Wool

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 $Ω (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 + d n)$ , 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: 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},
      url = {https://eprint.iacr.org/2015/1236}
}