Abstract: Algebraic side channel analysis (ASCA) is a method of cryptanalysis which allows key recovery attacks to be performed with very low data complexity. In an ASCA attack the side-channel leaks of the 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 excluded from the system of equations due to noise in the measurements, the attack will fail. If, on the other hand, the DUT is described in a more robust manner to better tolerate errors, the loss of information may make computation time intractable. We show how this robustness-information tradeoff can be avoided by using an optimizer, which uses the probability data output by the decoder, instead of a standard SAT solver.
Using the additional flexibility allowed by the optimizer, we then describe a novel way of directly representing leak equations as vectors of aposteriori probability. This form of representation allows ASCA attacks to be carried out on devices which do not conform to the Hamming weight leakage model. More importantly, it allows natural integration of template attacks and ASCA attacks, combining the versatility of templates with the low data complexity of solver-based approaches.