Fault Attack revealing Secret Keys of Exponentiation Algorithms from Branch Prediction Misses.
Sarani Bhattacharya, Debdeep Mukhopadhyay · 2014
Abstract—Performance monitors are provided in modern day computers for observing various features of the underlying micro-architectures. However the combination of underlying micro-architectural features and performance counters lead to side-channels which can be exploited for attacking cipher imple-mentations. 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 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 per-formance 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 gath-ered from the performance counters) are utilized 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 targeting 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. Keywords-Fault attacks, branch misses, performance counters,