Enumeration RankKey

Key enumeration and key Rank estimation. As far as side-channel attacks are concerned, security evaluations do not take adversarial computing power into account, only their ability to acquire encryption traces. However, the computing bound usually used in classical cryptanalysis is of 2^80. We proposed an algorithm that gives an adversary the ability to exploit the available computing power. The enumeration algorithm exploits the output of a typical side-channel attacks, that is a set of probability mass functions (or scores such as correlation coefficients) for the different subkeys. It then outputs key candidates by decreasing order of posterior likelihood, and they can be tested. In a sense, we have enhanced a brute force attack using side-channel information, in order to minimize the expected number of keys to test. The impact of enumeration has been shown in the context of the DPA contest v2, see the hall of fame. While the enumeration algorithm is an important tool for attackers, as far as security evaluation are concerned it can only give the rank of a correct key when this rank is enumerable (about 2^40 for now). In order to provide a useful answer for an evaluator, one needs to be able to estimate key ranks up to the total key space. A device can be considered secure only if the key rank stays above the enumeration limit considered for the adversary. We proposed an rank estimation algorithm that provides tight bounds for the security level of a device. It allows one to analyze the full complexity of standard side-channel attacks, in terms of tradeoffs between time, data and memory complexities.