Fast Analytical Rank Estimation

Rank estimation is an important tool for a side-channel evaluations laboratories. It allows estimating the remaining security after an attack has been performed, quantified as the time complexity and the memory consumption required to brute force the key given the leakages as probability distributions over d subkeys (usually key bytes). These estimations are particularly useful when the key is not reachable with exhaustive search. We propose a new framework for rank estimation that is conceptually simple, and more time and memory efficient than previous proposals. Our main idea is to bound each subkey distribution by an analytical function, and estimate the rank by a closed formula. To demonstrate the power of the framework, we instantiate it with Pareto-like functions to create the PRank algorithm. Pareto-like functions have long-tails that model empirical SCA distributions, and they are easily calculable. We evaluated the performance of PRank through extensive simulations based on two real SCA data corpora, and compared it to the currently-best histogram-based algorithm. We show that PRank gives a good rank estimation with much improved time and memory efficiency, especially for large ranks: For ranks between \(2^{80}-2^{100}\) PRank estimation is at most 10 bits above the histogram rank and for ranks beyond \(2^{100}\) the PRank estimation is only 4 bits above the histogram rank—yet it runs in milliseconds, and uses negligible memory. One could employ our framework with other classes of functions and possibly achieve even better results.