Montgomery’s Trick and Fast Implementation of Masked AES

Side Channel Analysis (SCA) is a class of attacks that exploit leakage of information from a cryptographic implementation during execution. To thwart it, masking is a common strategy that aims at hiding correlation between the manipulated secret key and the physical measures. Even though the soundness of masking has often been argued, its application is very time consuming, especially when so-called higher-order SCA (HO-SCA) are considered. Reducing this overhead at the cost of limited

RAM

consumption increase is a hot topic for the embedded security industry. In this paper, we introduce such an improvement in the particular case of the AES. Our approach consists in adapting a trick introduced by Montgomery to efficiently compute several inversions in a multiplicative group. For such a purpose, and to achieve security against HO-SCA, recent works published at CHES 2010 and ACNS 2010 are involved. In particular, the secure dirac computation scheme introduced by Genelle

et al.

at ACNS is extended to achieve security against SCA at any order. As argued in the second part of this paper, our approach improves in time complexity all previous masking methods requiring little

RAM

.