On the BRIP Algorithms Security for RSA
Power Analysis has been intensively studied since the first publications in 1996 and many related attacks on naive implementations have been proposed. Nowadays algorithms in tamper resistant devices are protected by different countermeasures most often ba
- PDF / 1,725,317 Bytes
- 14 Pages / 430 x 659.996 pts Page_size
- 18 Downloads / 204 Views
AMESYS, 1030, Avenue Guillibert de la Lauzire, 13794 Aix-en-Provence, Cedex 3, France [email protected] 2 INSIDE CONTACTLESS 41 Parc Club du Golf 13856 Aix-en-Provence, Cedex 3, France [email protected]
Abstract. Power Analysis has been intensively studied since the first publications in 1996 and many related attacks on naive implementations have been proposed. Nowadays algorithms in tamper resistant devices are protected by different countermeasures most often based on data randomization such as the BRIP algorithm on ECC and its RSA derivative. However not all of them are really secure or in the best case proven to be secure. In 2005, Yen, Lien, Moon and Ha introduced theoretical power attacks on some classical and BRIP exponentiation implementations, characterized by the use of a chosen input message value ±1. The first part of our article presents an optimized implementation for BRIP that takes advantage of the Montgomery modular arithmetic to speed up the mask inversion operation. An extension of the Yen et al. attack, based on collision detection through power analysis, is also presented. Based on this analysis we give security advice on this countermeasure implementation and determine the minimal random length to reach an appropriate level of security. Keywords: Power analysis, collision attacks, RSA, BRIP, modular multiplication and exponentiation.
1
Introduction
Asymmetric cryptography was introduced by Diffie and Hellman [DH76] in 1976. The most widely used algorithms today are: RSA [RSA78] invented in 1978 by Rivest, Shamir, and Adleman, and elliptic curve cryptosystems (ECC) independently introduced by Koblitz [Kob87] and Miller [Mil86]. Compared with symmetric cryptography, public key algorithms are computationally very intensive. In practice long integer arithmetic is most often handled by specific coprocessors designed for efficient computation in GF (p). This is the case for embedded solutions with strict power consumption and/or timing constraints. Initially smart cards were considered inherently tamper resistant because any private data was embedded and thus physically inaccessible to an unauthorized J.A. Onieva et al. (Eds.): WISTP 2008, LNCS 5019, pp. 136–149, 2008. c IFIP International Federation for Information Processing 2008
On the BRIP Algorithms Security for RSA
137
user. However in 1996 timing attacks were publicly introduced by Kocher in [Koc96]. Two years later he also introduced power analysis attacks with Jaffe and Jun [KJJ99]. Side Channel Analysis (SCA) is a group of techniques including simple power analysis (SPA) and differential power analysis (DPA). SCA threatens any naive cryptographic algorithm implementation. Since these first articles were published, power analysis has been widely investigated, some publications have focused on countermeasures and their drawbacks [FV03, MPO05, YLMH05] whereas others have focused on improving the efficiency of the attacks [ABDM00, BK03, BCO04]. One such countermeasure is the Binary with Random Initial Point (BRIP) algorithm(s) by Mamiya, Miyaji, M
Data Loading...
