Common Criteria Vulnerability Quotation System versus High-Order Side-Channel Attacks (A13b)
Side-channel attacks have been, for a long time, a threat on devices embedding cryptography. In terms of taxonomy, it is known as “Inherent Information Leakage (T.Leak-Inherent)”. Recently, the field of cryptography has been getting disrupted by two mega trends. Firstly, the advent of novel primitives, such as post-quantum cryptography (hash-based and lattice-based replacements for digital signatures and key exchange), lightweight cryptography (ASCON), white box cryptography, etc. And secondly, the systematization of the use of random masking as a protection against side-channel attacks.
Also, we are witnessing the emergence of new masking paradigms that are more and more evolved (code-based, threshold implementation, etc.) which do resist practically to regular (so-called first-order) attacks, despite implementation specificity (such as “transitional leakage”, “glitches”, etc.) that can weaken some less robust legacy masking schemes. All in one, evaluators nowadays face cryptographic implementations that shall be attacked using high-order attacks. Over time, side-channel acquisition benches have become better and better, in that they are able to collect reliable (with reduced noise, perfect alignment, etc.) traces datasets at a very high sampling rate. Thus, today, the bottleneck of side-channel attacks is the analysis: it is well-known that high-order attacks are computationally challenging. Said differently, the difficulty is shifting from “data complexity” to “computation complexity”.
In this talk, we study in depth the algorithms ruling high-order attacks.
Informally, those consist in multiplicatively combining the leakage from different samples, in order to cancel out the random masking and thus to restore a venue for hypothesis testing as a function of the key values.
More precisely, these operations are carried out on all values of key chunks, such as “bytes” for instance.
Therefore, the key reconstruction amounts to a “divide-and-conquer” attack whereby the key is unveiled chunk by chunk, by selection of the chunks that correlate best.
The attack therefore involves exhaustive computations (on key chunks) of averages (over the masks) of products of leakage values.
It happens that such computations are complex because they require exhaustive “accumulations” of multiplications over key chunks and corresponding masks.
By noticing that key chunks and masks have reciprocal roles in such computations, it is possible to rewrite it as a convolution product over the traces’ leakage points.
Now, it is well-known that convolutions can be evaluated efficiently leveraging a “Fourier transform”.
This therefore changes the odds of high-order attacks, which are way easier conducted leveraging this spectral transformation than when implementing them naïvely.
Namely, convolution-based computations in Fourier retalk bring an exponential speed-up, which occurs for high-order attacks both in keyspace and in the number of masks (e.g., the order of the masking countermeasure).
Advantageously, this technique works both for unsupervised attacks (such as high-order correlations attacks) and supervised attacks (such as template attacks).
Let us precise that template attacks enjoy advantages: they are not prone to model mismatch (unsupervised attacks “assume” a leakage model, which can deviate from a learnt one), and they naturally apply to multivariate leakage, whereby not only “punctual” trace samples are combined, but complete sub-traces made up of several samples.
In conclusion, this talk aims at introducing to the ICCC audience the objective complexity of performing multivariate high-order attacks, and at discussing its impact on their Common Criteria quotation.