Statistical Bounds to Expedite (High-Order) Side-Channel Attacks (M31c)
Side-channel analyses are well-known threats to assets contained in Targets of Evaluation (ToE). They are very often contemplated in AVA_VAN evaluation. The reason is that such attacks are stealthy: millions if not billions of side-channel traces can be collected without the device noticing that it is under attack. Over time, side-channel attacks have been demystified. In particular, methods have been put forward to avoid performing costly attacks end-to-end. Typically, leakage assessment (via T-Test) allows spotting leakage points if present, without launching any attack.
Such assessment is deemed enough as a piece of evidence for schemes such as FIPS 140-3, which entrusts ISO/IEC 17825 “non-invasive attack testing”. But two problems arise with such a test:
1. If the test detects a leakage, how to prove (or disprove) that it is exploitable at all?
2. The test is designed for a limited amount of traces (typically 10,000 and 100,000 for FIPS 140-3 levels 3 and 4).
But what if a (tiny) leakage occurs beyond? Indeed AVA_VAN considers attacks that can be long in time, beyond the 100k traces prescription of ISO/IEC 17825.
This talk will survey the state-of-the-art tools to process side-channel analysis at the scale of AVA_VAN, up to AVA_VAN.5 (several months of evaluation as per CEM’s “Estimated Time” metric). Two recent threads of work allow to bound the number of traces for an attack to succeed, whilst being agnostic in the attack. This is powerful, as again, performing end-to-end attacks can be very costly in efforts.
The first progress is the computation of bounds on implementations protected by masking. A conservative bound can be achieved as a factorization of bounds on each share (recall that masking consists of splitting sensitive variables into random shares). Such bound on the number of traces to recover the key resorts to a theoretical tool referred to as “Ms. Gerber lemma”. Several pieces of work have been published in this respect, each further optimizing the bounds.
One can cite [CARDIS 2022], [ITW 2023], [COSADE 2023]. The improvements have been achieved by studying some variants of mutual information, namely Rényi and Sibson’s alpha-information.
The second progress relates to leveraging leakage metrics that are better fitted than mutual information. In particular, we explain the gist of a novel metric, termed “Doeblin coefficient”, which allows to derive a “tight bound” [CRYPTO 2024]. This has the advantage of bringing “exact” limits in the number of traces but at the expense of estimating this coefficient. Indeed, many mutual information estimation methods exist (histograms, parametric, neural networks, etc.), but the “Doeblin coefficient” (whilst not new) has not been explored in depth yet. In conclusion, this talk will show that the side-channel community has brought practical methodological tools to speed up evaluations, which should allow to reduce the evaluation time, even without performing lengthy attacks.
Bibliography addressed pedagogically in the talk:
[CARDIS 2022] “A Nearly Tight Proof of Duc et al.’s Conjectured Security Bound for Masked Implementations,” Masure, Rioul, & Standaert CARDIS 2022
[ITW 2023] “Improved Alpha-Information Bounds for Higher-Order Masked Cryptographic Implementations,” Liu, Béguinot, Cheng, Guilley, Masure, Rioul, Standaert, ITW 2023
[COSADE 2023] “Removing the Field Size Loss from Duc et al.’s Conjectured Bound for Masked Encodings,” Béguinot, Cheng, Guilley, Liu, Masure, Rioul, Standaert, COSADE 2023
[CRYPTO 2024] “Formal Security Proofs via Doeblin Coefficients: Optimal Side-channel Factorization from Noisy Leakage to Random Probing,” Julien Béguinot, Wei Cheng, Sylvain Guilley, Olivier Rioul, CRYPTO 2024.”