International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Practical Evaluation of Protected Residue Number System Scalar Multiplication

Authors:
Louiza Papachristodoulou , Digital Security Group, Radboud University Nijmegen
Apostolos P. Fournaris , Electrical and Computer Engineering Dpt., University of Patras
Kostas Papagiannopoulos , Digital Security Group, Radboud University Nijmegen
Lejla Batina , Digital Security Group, Radboud University Nijmegen
Download:
DOI: 10.13154/tches.v2019.i1.259-282
URL: https://tches.iacr.org/index.php/TCHES/article/view/7341
Search ePrint
Search Google
Presentation: Slides
Abstract: The Residue Number System (RNS) arithmetic is gaining grounds in public key cryptography, because it offers fast, efficient and secure implementations over large prime fields or rings of integers. In this paper, we propose a generic, thorough and analytic evaluation approach for protected scalar multiplication implementations with RNS and traditional Side Channel Attack (SCA) countermeasures in an effort to assess the SCA resistance of RNS. This paper constitutes the first robust evaluation of RNS software for Elliptic Curve Cryptography against electromagnetic (EM) side-channel attacks. Four different countermeasures, namely scalar and point randomization, random base permutations and random moduli operation sequence, are implemented and evaluated using the Test Vector Leakage Assessment (TVLA) and template attacks. More specifically, variations of RNS-based Montgomery Powering Ladder scalar multiplication algorithms are evaluated on an ARM Cortex A8 processor using an EM probe for acquisition of the traces. We show experimentally and theoretically that new bounds should be put forward when TVLA evaluations on public key algorithms are performed. On the security of RNS, our data and location dependent template attacks show that even protected implementations are vulnerable to these attacks. A combination of RNS-based countermeasures is the best way to protect against side-channel leakage.
Video from TCHES 2019
BibTeX
@article{tches-2019-29055,
  title={Practical Evaluation of Protected Residue Number System Scalar Multiplication},
  journal={IACR Trans. Cryptogr. Hardw. Embed. Syst.},
  publisher={Ruhr-Universität Bochum},
  volume={2019, Issue 1},
  pages={259-282},
  url={https://tches.iacr.org/index.php/TCHES/article/view/7341},
  doi={10.13154/tches.v2019.i1.259-282},
  author={Louiza Papachristodoulou and Apostolos P. Fournaris and Kostas Papagiannopoulos and Lejla Batina},
  year=2019
}