Computational Aspects of Correlation Power Analysis

Abstract. Since the discovery of simple power attacks, the cryptographic research community has developed significantly more advanced attack methods. The idea behind most algorithms remains to perform a statistical analysis by correlating the power trace obtained when executing a cryptographic primitive to a key-dependent guess. With the advancements of cryptographic countermeasures, it is not uncommon that sophisticated (higher-order) power attacks require computation on many millions of power traces in order to find the desired correlation. In this paper, we study the computational aspects of calculating the most widely used correlation coefficient: the Pearson product-moment correlation coefficient. We study various time-memory trade-off techniques which apply specifically to the cryptologic setting and present methods to extend already completed computations using incremental versions. Moreover, we show how this technique can be applied to second-order attacks, reducing the attack cost significantly when adding new traces to an existing dataset. We also present methods which allow one to split the potentially huge trace set into smaller, more manageable chunks in order to reduce the memory requirements. Our concurrent implementation of these techniques highlights the benefits of this approach as it allows efficient computations on power measurements consisting of hundreds of gigabytes on a single modern workstation