Paper 2008/508

Some Formal Solutions in Side-channel Cryptanalysis - An Introduction

Fabrice J. P. R. Pautot

Abstract

We propose to revisit Side-channel Cryptanalysis from the point of view, for instance, of C. E. Shannon: The calculation of a posteriori probabilities is the generalized problem of cryptanalysis. So, our goal will be to provide analytic formulae for the marginal posterior probability mass functions for the targets of those attacks. Since we are concerned with the probabilities of single and perfectly determined cases, we need above all to place ourselves in a probabilistic system enjoying an epistemic “interpretation”. We select Probability as Logic, the most suitable system for our purpose. With this powerful and flexible system at hand, we first solve two independent problems for known, non-chosen messages: the determination of side-channel leakage times (generalized for high-order attacks) and the determination of the target, given those leakage times. The first problem belongs to Hypotheses Testing Theory and admits a formal solution in terms of Bayes Factors in the parametric framework. The calculation of those factors requires marginalizing over all possible values of the target, so that this new procedure has no equivalent in frequentist Statistics and we indicate how it could be proved to outperform previous procedures more and more, as the target space size increases. We present preliminary experimental results and give some clues on how to extend this solution to the nonparametric framework. The second problem is a classical Parameter Estimation problem with many hyperparameters. It also admits a unique maximum a posteriori solution under 0-1 loss function within Decision Theory. When it is not possible to solve both problems independently, we must solve them simultaneously in order to get general solutions for Side-channel Cryptanalysis on symmetric block ciphers, at least. Taking benefit of the duality between Hypotheses Testing and Parameter Estimation in our system of inference, we transform the determination of the generalized leakage times into a parameter estimation problem, in order to fall back into a global parameter estimation problem. Generally speaking, it appears that (marginal) side-channel parametric leakage models are in fact averages between attack and “non-attack” models and, more generally between many conditional models, so that likelihoods can not be frequency sampling distributions. Then, we give the marginal posterior probability mass function for the targets of the most general known-messages attacks: “correlation” attacks, template attacks, high-order attacks, multi-decision functions attacks, multi-attack models attacks and multi-“non-attack” models attacks. Essentially, it remains to explain how to assign joint prior and discrete direct probability distributions by logical inspection, to extent this approach to the nonparametric framework and other cryptographic primitives, to deal with analytic, symbolic, numerical and computational implementation issues and especially to derive formal adaptive chosen-messages attacks.

Note: Even more typos removed!