Welcome to the resource topic for 2015/1236
Title:
A Bounded-Space Near-Optimal Key Enumeration Algorithm for Multi-Dimensional Side-Channel Attacks
Authors: Liron David, 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.
ePrint: https://eprint.iacr.org/2015/1236
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .