Paper 2014/790

Fault Attack revealing Secret Keys of Exponentiation Algorithms from Branch Prediction Misses

Sarani Bhattacharya and Debdeep Mukhopadhyay

Abstract

Performance monitors are provided in modern day computers for observing various features of the underlying microarchitectures. However the combination of underlying micro-architectural features and performance counters lead to side-channels which can be exploited for attacking cipher implementations. In this paper, to the best of our knowledge we study for the first time, the combination of branch-predictor algorithms and performance counters to demonstrate a fault attack on the popular square-and-multiply based exponentiation algorithm, used in the RSA. The attacks exploiting branching event like branch taken can be foiled by Montgomery Ladder based implementation of the exponentiation algorithm, while attacks based on branch miss are more devastating. We demonstrate the power of the attack exploiting branch misses from performance monitors by formalizing a fault attack model, where the adversary is capable of performing a bit flip at a desired bit position of the secret exponent. The paper characterizes the branch predictors using the popular two-bit predictor and formulates the dependence on the number of branch misses on the fault induced. This characterization is exploited to develop an iterative attack algorithm where knowledge of the previously determined key-bits and the difference of branch misses (as gathered from the performance counters) are utilised to determine the next bit. The attack has been validated on several standard Intel platforms, and puts to threat several implementations of exponentiation algorithms ranging from standard square-and-multiply, Montgomery Ladder to RSA-CRT and which are often used as side-channel counter measures. The attacks show that using the fault attack model featuring branch predictors one can attack implementations of exponentiation: both square and multiply, and Montgomery ladder, which forms the central algorithm for several standard public key ciphers.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Fault attacksbranch missesperformance countersBranch Prediction UnitSquare and Multiply AlgorithmMontgomery Ladder AlgorithmRSA-CRT
Contact author(s)
sarani bhattacharya @ cse iitkgp ernet in
History
2014-10-10: received
Short URL
https://ia.cr/2014/790
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/790,
      author = {Sarani Bhattacharya and Debdeep Mukhopadhyay},
      title = {Fault Attack revealing Secret Keys of Exponentiation Algorithms from Branch Prediction Misses},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/790},
      year = {2014},
      url = {https://eprint.iacr.org/2014/790}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.