Seminar on Security of Embedded Electronic Systems

Home     Presentation     Previous years

Guilherme Perin

Robustness Evaluation of RNS Implementations of RSA Against Side-Channel Attacks

Implement public-key algorithms in software and hardware without any source of leakage through side-channels is a challenging task. At least, the designers of cryptographic devices can implement these algorithms with different countermeasures at different levels of abstraction. Algorithmic (masking/blinding) and hardware countermeasures (hinding) aim at defeating well-known side-channel attacks (SPA, DPA, CPA, chosen-message, template). However, in the case of RSA or ECC , most of the existing countermeasures keep the system vulnerable to attacks based on single-execution of an exponentiation, that is, attacks that are able of recovering the secret information using a single trace. Horizontal correlation attacks [1][2], template-based attacks and, recently, attacks based on unsupervised learning [3][4] may still explore the remaining and exposed information. Residue Number System (RNS) is considered as an arithmetic countermeasure when applied to RSA. It naturaly masks the internal operations and defeats multi-trace attacks by randomizing and permuting the RNS bases before or during the modular exponentiation (Leak Resistant Arithmetic - LRA [5]). By doing so, single-execution attacks can only exploit the leakage of information presented through incorrect implementation of algorithmic countermeasures (address-bit, control decisions and RAM addressing). Therefore, the combination of RNS (LRA) with countermeasures at different levels of abstraction is a promising way to thwart side-channel attacks. This work presents how implementation aspects of RNS in hardware and software can defeat state-of-art side-channel attacks on exponentiations.

[1] Christophe Clavier, Benoit Feix, Georges Gagnerot, Mylene Roussellet, and Vincent Verneuil. Horizontal correlation analysis on exponentiation. ICICS, vol. 6476 of LNCS, pages 46 61. Springer, 2010.

[2] Christophe Clavier, Benoit Feix, Georges Gagnerot, Christophe Giraud, Mylene Roussellet, and Vincent Verneuil. Rosetta for single trace analysis. INDOCRYPT, vol. 7668 of LNCS, pages 140 155. Springer, 2012.

[3] Johann Heyszl, Andreas Ibing, Stefan Mangard, Fabrizio De Santis, and Georg Sigl. Clustering algorithms for non-profiled single-execution attacks on exponentiations. IACR Cryptology ePrint Archive, 2013:438, 2013.

[4] Guilherme Perin, Laurent Imbert, Lionel Torres and Philippe Maurine. Attacking randomized exponentiation using unsupervised learning. To appear in COSADE 2014.

[5] Jean-Claude Bajard, Laurent Imbert, Pierre-Yvan Liardet, and Yannick Teglia. Leak resistant arithmetic. CHES 2004, vol. 3156 of LNCS, pages 62 75, 2004. résumé à venir