Practical Evaluation of Protected Residue Number System Scalar Multiplication

  • 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
Keywords: SCA evaluation, TVLA, residue number system, elliptic curve cryptography, scalar multiplication, template attacks

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.

Published
2018-11-09
How to Cite
Papachristodoulou, L., Fournaris, A., Papagiannopoulos, K., & Batina, L. (2018). Practical Evaluation of Protected Residue Number System Scalar Multiplication. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019(1), 259-282. https://doi.org/10.13154/tches.v2019.i1.259-282
Section
Articles