Robust and One-Pass Parallel Computation of Correlation-Based Attacks at Arbitrary Order

Abstract. The protection of cryptographic implementations against higher-order attacks has risen to an important topic in the side-channel commu-nity after the advent of enhanced measurement equipment that enables the capture of millions of power traces in reasonably short time. How-ever, the preprocessing of multi-million traces for such an attack is still challenging, in particular when in the case of (multivariate) higher-order attacks all traces need to be parsed at least two times. Even worse, partitioning the captured traces into smaller groups to parallelize com-putations is hardly possible with current techniques. In this work we introduce procedures that allow iterative computation of correlation in a side-channel analysis attack at any arbitrary order in both univariate and multivariate settings. The advantages of our pro-posed solutions are manifold: i) they provide stable results, i.e., by in-creasing the number of used traces high accuracy of the estimations is still maintained, ii) each trace needs to be processed only once and at any time the result of the attack can be obtained (without requiring to reparse the whole trace pull when adding more traces), and iii) the com-putations can be efficiently parallelized, e.g., by splitting the trace pull into smaller subsets and processing each by a single thread on a multi-threading or cloud-computing platform. In short, our constructions allow efficiently performing higher-order side-channel analysis attacks (e.g., on hundreds of million traces) which is of crucial importance when practical evaluation of the masking schemes need to be performed.