Skip to Main content Skip to Navigation
Journal articles

Branch Prediction Attack on Blinded Scalar Multiplication

Abstract : In recent years, performance counters have been used as a side channel source to monitor branch mispredictions, in order to attack cryptographic algorithms. However, the literature considers blinding techniques as effective countermeasures against such attacks. In this work, we present the first template attack on the branch predictor. We target blinded scalar multiplications with a side-channel attack that uses branch misprediction traces. Since an accurate model of the branch predictor is a crucial element of our attack, we first reverse-engineer the branch predictor. Our attack proceeds with a first online acquisition step, followed by an offline template attack with a template building phase and a template matching phase. During the template matching phase, we use a strategy we call Deduce & Remove, to first infer the candidate values from templates based on a model of the branch predictor, and subsequently eliminate erroneous observations. This last step uses the properties of the target blinding technique to remove wrong guesses and thus naturally provides error correction in key retrieval. In the later part of the paper, we demonstrate a template attack on Curve1174 where the double-and-add always algorithm implementation is free from conditional branching on the secret scalar. In that case, we target the data-dependent branching based on the modular reduction operations of long integer multiplications. Such implementations still exist in open source software and can be vulnerable, even if top level safeguards like blinding are used. We provide experimental results on scalar splitting, scalar randomization, and point blinding to show that the secret scalar can be correctly recovered with high confidence. Finally, we conclude with recommendations on countermeasures to thwart such attacks.
Document type :
Journal articles
Complete list of metadata

Cited literature [45 references]  Display  Hide  Download

https://hal.inria.fr/hal-02866753
Contributor : Clémentine Maurice <>
Submitted on : Friday, June 12, 2020 - 5:14:58 PM
Last modification on : Tuesday, May 18, 2021 - 3:34:37 PM

File

ieee-tc20_bhattacharya.pdf
Files produced by the author(s)

Identifiers

Citation

Sarani Bhattacharya, Clémentine Maurice, Shivam Bhasin, Debdeep Mukhopadhyay. Branch Prediction Attack on Blinded Scalar Multiplication. IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers, 2020, 69 (5), pp.633-648. ⟨10.1109/TC.2019.2958611⟩. ⟨hal-02866753⟩

Share

Metrics

Record views

61

Files downloads

686