Practical Second-Order Correlation Power Analysis on the Message Blinding Method and Its Novel Countermeasure for RSA

ETRI Journal

关键词: second-order DPA;    BRIP;    message blinding method;    side channel attacks;    RSA cryptosystems;   

Others  :  1185997
DOI  :  10.4218/etrij.10.0109.0249

【 摘 要 】

Recently power attacks on RSA cryptosystems have been widely investigated, and various countermeasures have been proposed. One of the most efficient and secure countermeasures is the message blinding method, which includes the RSA derivative of the binary-with-random-initial-point algorithm on elliptical curve cryptosystems. It is known to be secure against first-order differential power analysis (DPA); however, it is susceptible to second-order DPA. Although second-order DPA gives some solutions for defeating message blinding methods, this kind of attack still has the practical difficulty of how to find the points of interest, that is, the exact moments when intermediate values are being manipulated. In this paper, we propose a practical second-order correlation power analysis (SOCPA). Our attack can easily find points of interest in a power trace and find the private key with a small number of power traces. We also propose an efficient countermeasure which is secure against the proposed SOCPA as well as existing power attacks.

   

【 参考文献 】

• [1]P. Kocher, J. Jaffe, and B. Jun, "Differential Power Analysis," CRYPTO, LNCS 1666, 1999, pp. 388-397.
• [2]T. Messerges, E. Dabbish, and R. Sloan, "Power Analysis Attacks of Modula Exponentiation in Smartcards," CHES, LNCS 1717, 1999, pp. 144-157.
• [3]B. Chevallier-Mames, M. Ciet, and M. Joye, "Low-Cost Solutions for Preventing Simple Side-Channel Analysis: Side-Channel Atomicity," IEEE Trans. Computers, vol. 53, no. 6, 2004, pp. 760-768.
• [4]J.S. Coron, "Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems," CHES, LNCS 1717, 1999, pp. 292-302.
• [5]T. Izu and T. Takagi, "A Fast Parallel Elliptic Curve Multiplication Resistant against Side Channel Attacks," PKC, LNCS 2274, 2002, pp. 280-296.
• [6]F. Amiel, B. Feix, and K. Villegas, "Power Analysis for Secret Recovering and Reverse Engineering of Public Key Algorithms," SAC, LNCS 4876, 2007, pp. 110-125.
• [7]K. Okeya and K. Sakurai, "Power Analysis Breaks Elliptic Curve Cryptosystems Even Secure against the Timing Attack," INDOCRYPT, LNCS 1977, 2000, pp. 178-190.
• [8]C. Clavier and M. Joye, "Universal Exponentiation Algorithm: A First Step towards Provable SPA-Resistance," CHES, LNCS 2162, 2001, pp. 300-308.
• [9]M. Ciet and M. Joye, "(Virtually) Free Randomization Technique for Elliptic Curve Cryptography," ICICS, LNCS 2836, 2003, pp. 348-359.
• [10]H. Mamiya, A. Miyaji, and H. Morimoto, "Efficient Countermeasures against RPA, DPA, and SPA," CHES, LNCS 3156, 2004, pp. 343-356.
• [11]K. Itoh, T. Izu, and M. Takenaka, "Improving the Randomized Initial Point Countermeasure against DPA," ACNS, LNCS 3989, 2006, pp. 459-469.
• [12]F. Amiel and B. Feix, "On the BRIP Algorithms Security for RSA," WISTP, LNCS 5019, 2008, pp. 136-149.
• [13]K. Okeya and K. Sakurai, "A Second-Order DPA Attack Breaks a Window Method Based Countermeasure against Side Channel Attacks," ISC, LNCS 2433, 2002, pp. 389-401.
• [14]P.A. Fouque and F. Vallette, "The Doubling Attack: Why Upwards Is Better than Downwards," CHES, LNCS 2779, 2003, pp. 269-280.
• [15]A.C. Menezes, P.C. van Oorschot, and S.A. Vanstone, Handbook of Applied Cryptography, CRC Press, Boca Raton, 1996.
• [16]E. Oswald et al., "Practical Second-Order DPA Attacks for Masked Smart Card Implementations of Block Cipher," CT-RSA 2006, LNCS 3860, 2006, pp. 192-207.
• [17]E. Oswald and K. Schramm, "An Efficient Masking Scheme for AES Software Implementation," WISA 2005, LNCS 3786, 2006, pp. 292-305.
• [18]W. Schindler, "A Timing Attack against RSA with the Chinese Remainder Theorem," CHES, vol. 1965, 2000, pp. 109-124.