Paper 2010/394

Horizontal Correlation Analysis on Exponentiation

Christophe Clavier, Benoit Feix, Georges Gagnerot, Mylene Roussellet, and Vincent Verneuil

Abstract

Power Analysis has been widely studied since Kocher et al. presented in 1998 the initial Simple and Differential Power Analysis (SPA and DPA). Correlation Power Analysis (CPA) is nowadays one of the most powerful techniques which requires, as classical DPA, many execu- tion curves for recovering secrets. We introduce in this paper a technique in which we apply correlation analysis using only one execution power curve during an exponentiation to recover the whole secret exponent manipulated by the chip. As in the Big Mac attack from Walter, longer keys may facilitate this analysis and success will depend on the arithmetic coprocessor characteristics. We present the theory of the attack with some practical successful results on an embedded device and analyze the efficiency of classical countermeasures with respect to our attack. Our technique, which uses a single exponentiation curve, cannot be pre vented by exponent blinding. Also, contrarily to the Big Mac attack, it applies even in the case of regular implementations such as the square and multiply always or the Montgomery ladder. We also point out that DSA and Diffie-Hellman exponentiations are no longer immune against CPA. Then we discuss the efficiency of known countermeasures, and we finally present some new ones.

Note: This is the extented version of the ICICS 2010 paper.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. ICICS 2010 (extended version)
Keywords
Public Key CryptographySide-Channel AnalysisHorizontal and Vertical Power AnalysisExponentiationArithmetic Coprocessors.
Contact author(s)
bfeix @ insidefr com
History
2010-11-29: revised
2010-07-13: received
See all versions
Short URL
https://ia.cr/2010/394
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/394,
      author = {Christophe Clavier and Benoit Feix and Georges Gagnerot and Mylene Roussellet and Vincent Verneuil},
      title = {Horizontal Correlation Analysis on Exponentiation},
      howpublished = {Cryptology ePrint Archive, Paper 2010/394},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/394}},
      url = {https://eprint.iacr.org/2010/394}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.