A.: Algebraic Side-Channel attacks beyond the Hamming weight leakage model

Abstract. Algebraic side-channel attacks (ASCA) are a method of crypt-analysis which allow performing key recoveries with very low data com-plexity. In an ASCA, the side-channel leaks of a device under test (DUT) are represented as a system of equations, and a machine solver is used to find a key which satisfies these equations. A primary limitation of the ASCA method is the way it tolerates errors. If the correct key is ex-cluded from the system of equations due to noise in the measurements, the attack will fail. On the other hand, if the DUT is described in a more robust manner to better tolerate errors, the loss of information may make computation time intractable. In this paper, we first show how this robustness-information tradeoff can be simplified by using an optimizer, which exploits the probability data output by a side-channel decoder, instead of a standard SAT solver. For this purpose, we describe a way of representing the leak equations as vectors of aposteriori probabilities, enabling a natural integration of template attacks and ASCA. Next, we put forward the applicability of ASCA against devices which do not con-form to simple leakage models (e.g. based on the Hamming weight of the manipulated data). We finally report on various experiments that illus-trate the strengths and weaknesses of standard and optimizing solvers in various settings, hence demonstrating the versatility of ASCA.