Paper 2015/260

Computational Aspects of Correlation Power Analysis

Paul Bottinelli and Joppe W. Bos

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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
Side-channel analysisCPAPearson correlation coefficienthigher-order attacks
Contact author(s)
joppe bos @ nxp com
History
2015-04-10: revised
2015-03-22: received
See all versions
Short URL
https://ia.cr/2015/260
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/260,
      author = {Paul Bottinelli and Joppe W.  Bos},
      title = {Computational Aspects of Correlation Power Analysis},
      howpublished = {Cryptology ePrint Archive, Paper 2015/260},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/260}},
      url = {https://eprint.iacr.org/2015/260}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.