Source code for Key enumeration and Key Rank estimation

Homepage
Research
Teaching
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.

Open-source implementations

Both algorithms for key enumeration and key ranking are available here as open source. Our implementations of the algorithms are written in C++11, with mex files for use with matlab.[source] [readme]

Below is an example for integrating our algorithms at the end of an attack when the key PDFs are available.

#include "Enumeration.h" [...] Enumeration<> myEnum(keyPMF); // enumeration object bool found = false; unsigned long long rank = 0; pair< double, array< unsigned char, 0x10>> candidate; // key candidate while (!found) { candidate = myEnum.nextCandidate(); // enumerate next candidate found = testKey(candidate.second); }

#include "RankKey.h" [...] RankKey rankEstimation(keyPMF, posteriorProbability); rankEstim.mergeDistribution(24); // merge lists up to 2^24 auto estimation = rankEstim(10); // estimate key rank for 10 seconds for(auto& v0 : estimation) // output log2 estimations of rank cout << log((double)v0) / log(2) << ' '; cout << endl;The output of this code will appear as: "

meaning that the key rank is inside [2^89.7; 2^90.2], and that no candidates with the exact key probability were found (yet). See also the presentation given for the

Please refer to the compagnion papers when using the source code

Nicolas Veyrat-Charvillon, Benoît Gérard, Mathieu Renauld, François-Xavier Standaert:

An optimal Key Enumeration Algorithm and its Application to Side-Channel Attacks

in the proceedings of *SAC 2012, Lecture Notes in Computer Science, vol 7707, pp 391-407, Windsor, Ontario, Canada, August 2012, Springer.* [pdf]

Nicolas Veyrat-Charvillon, Benoît Gérard and François-Xavier Standaert:

Security Evaluations Beyond Computing Power: How to Analyze Side-Channel Attacks you Cannot Mount?

to appear in the proceedings of *Eurocrypt 2013, Lecture Notes in Computer Science, May 2013 * [pdf]