Home   >   CSC-OpenAccess Library   >    Manuscript Information
Full Text Available

(119.41KB)
This is an Open Access publication published under CSC-OpenAccess Policy.
Blinded Montgomery Powering Ladder Protected Against the Jacobi Symbol Attack
David Tinoco Varela
Pages - 15 - 27     |    Revised - 15-05-2012     |    Published - 20-06-2012
Volume - 6   Issue - 3    |    Publication Date - June 2012  Table of Contents
MORE INFORMATION
KEYWORDS
Modular Exponentiation, Cryptography, Jacobi Symbol, Montgomery ladder, Fault Attacks
ABSTRACT
Many physical attack types (Timing attacks, Power consumption attacks, Fault attacks, etc.) have been developed against cryptosystems, and specifically against the modular exponentiation which is the core operation of many cryptosystems, in the recent years. Indeed there is a real necessity to eliminate the vulnerabilities of the cryptosystems, like CRT-RSA or the Elliptic Curve Cryptosystem, that make them susceptible to those attacks. In 2006 Boreale described a new type of physical attack which is based in the Jacobi symbol concept, and after that, Schmidt used the same concept as Boreale to break the security of the blinded Montgomery powering ladder. In this paper a countermeasure against the Schmidt\'s attack is presented in order to make the blinded Montgomery powering ladder resistant to the Jacobi symbol attack.
CITED BY (1)  
1 Varela, D. T. (2012).How to avoid the n-1 attack without costly implementations. International Journal of Network Security & Its Applications, 4(4), 109.
1 Google Scholar
2 CiteSeerX
3 refSeek
4 Scribd
5 slideshare
6 PdfSR
1 P. Kocher. “Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems.” In Koblitz, N., ed.: Advances in Cryptology-CRYPTO 96. Volume 1109 of Lecture in Notes in Computer Science, 1996, pp. 104-113.
2 D. Boneh, R. DeMillo and R. Lipton. “On the importance of checking cryptographic protocols for faults.” In Fumy, W., Ed.: Advances in Cryptology-EUROCRYPT ’97. Volume 1233 of Lecture Notes in Computer Science, 1997, pp. 37-51.
3 J.S. Coron. “Resistance against differential power analysis for elliptic curve cryptosystems.” In Ko, Paar, C., Eds.: Cryptographic Hardware and Embedded Systems-CHES 2002. Volume 1717 of Lecture Notes in Computer Science, 1999, pp. 292-302.
4 S.M. Yen, S. Kim, S. Lim, and S. Moon. “A countermeasure against one physical cryptanalysis may benefit another attack”. Information Security and Cryptology-ICISC 2001, 2288 of Lecture Notes in Computer Science, 2001, pp.414-427.
5 M. Joye and S.M. Yen. “The montgomery powering ladder.” In Cryptographic Hardware and Embedded Systems-CHES 2002, 2523 of Lecture Notes in Computer Science, 2003, pp. 291-302.
6 C. Giraud. “An rsa implementation resistant to fault attacks and to simple power analysis”. IEEE Transactions on computers, Vol. 55, No. 9, pp. 1116-1120, 2006.
7 S.M. Yen, L.C. Ko, S.J. Moon, and J.C. Ha. “Relative doubling attack against montgomery ladder.” In Information Security and Cryptology-ICISC 2005, 3935 of Lecture Notes in Computer Science, 2005, pp. 117-128.
8 P.A. Fouque and F. Valette. “The doubling attack–why upwards is better than downwards.” In Cryptographic Hardware and Embedded Systems-CHES 2003, LNCS 2779, 2003, pp. 269-280.
9 G. Fumaroli and D. Vigilant. “Blinded fault resistant exponentiation.” Fault Diagnosis and Tolerance in Cryptography, 4236 of Lecture Notes in Computer Science, 2006, pp. 62-70.
10 M. Boreale. “Attacking right-to-left modular exponentiation with timely random faults.” Fault Diagnosis and Tolerance in Cryptography, 4236 of LNCS, pp. 24-35, 2006.
11 J. M. Schmidt and M. Medwed. “Fault attacks on the montgomery powering ladder”. Information Security and Cryptology ICISC-2010, pp. 396-406, 2011.
12 H. Mamiya, A. Miyaji, and H. Morimoto. “Efficient countermeasures against rpa, dpa, and spa.” Cryptographic Hardware and Embedded Systems-CHES 2004, 3156 of Lecture Notes in Computer Science, 2004, pp. 343-356.
13 C.C. Lu, S.Y. Tseng, and S.K. Huang. “A secure modular exponential algorithm resists to power, timing, c safe error and m safe error attacks.” In 19th International Conference on Advanced Information Networking and Applications, 2005. AINA 2005, pp. 151-154.
14 C.H. Kim and J.J. Quisquater. “How can we overcome both side channel analysis and fault attacks on rsa-crt?.” Workshop on Fault Diagnosis and Tolerance in Cryptography, pp. 21– 29, 2007.
15 A. Boscher, R. Naciri, and E. Prouff. “Crt rsa algorithm protected against fault attacks.” Information Security Theory and Practices. Smart Cards, Mobile and Ubiquitous Computing Systems, 4462 of LNCS, pp.229-243, 2007.
16 J.C. Ha, C.H. Jun, J.H. Park, S.J. Moon, and C.K. Kim. “A new crt-rsa scheme resistant to power analysis and fault attacks.” Third 2008 International Conference on Convergence and Hybrid Information Technology, 2008, pp. 351-356.
17 A. Boscher, H. Handschuh, and E. Trichina. “Blinded fault resistant exponentiation revisited.” In L. Breveglieri, S. Gueron, I. Koren, D. Naccache, and J.-P. Seifert, editors, Workshop on Fault Diagnosis and Tolerance in Criptography - FDTC’09, 2009, pp. 3-9.
18 S.M. Yen, W.C. Lien, S.J. Moon, and J.C. Ha. “Power analysis by exploiting chosen message and internal collisions-vulnerability of checking mechanism for rsa-decryption.” Progress in Cryptology–Mycrypt 2005, 3715 of Lecture Notes in Computer Science, 2005, pp. 183-195.
19 C. Kim and J.J. Quisquater. “Fault attacks for crt based rsa: New attacks, new results, and new countermeasures.” Information Security Theory and Practices. Smart Cards, Mobile and Ubiquitous Computing Systems, 4462, pp. 215-228, 2007.
20 S. Chari, J. Rao, and P. Rohatgi. “Template attacks.” Cryptographic Hardware and Embedded Systems-CHES 2002, 2523 of Lecture Notes in Computer Science, 2002, pp. 12–28.
21 S.M. Yen and M. Joye. “Checking before output may not be enough against fault-based cryptanalysis.” IEEE Transactions on Computers, 49(9), pp. 967-970, 2000.
22 S.M. Yen and C.S Laih. “Common-multiplicand multiplication and its application to publickey cryptography.” Electronic Letters, 29(17), pp. 1583-1584, August 1993.
23 P.C. Kocher, J. Jaffe, and B. Jun. “Differential Power Analysis.” In Wiener, M., Ed.: Advances in Cryptology-CRYPTO ’99. Volume 1666 of Lecture Notes in Computer Science, Springer 1999, pp. 388-397.
24 M. Joye. “Highly regular right-to-left algorithms for scalar multiplication.” Cryptographic Hardware and Embedded Systems-CHES 2007, 4727 of Lecture in Notes in Computer Science, 2007, pp. 135–147.
25 C.H. Kim. “New fault attacks using jacobi symbol and application to regular right-to-left algorithms.” Information Processing Letters, 110(20), pp. 882-886, 2010.
26 E. Dottax, C. Giraud, M. Rivain, and Y. Sierra. “On second-order fault analysis resistance for CRT-RSA implementations.” Information Security Theory and Practice. Smart Devices, Pervasive Systems, and Ubiquitous Networks, pp. 68-83, Springer 2009.
Mr. David Tinoco Varela
UNAM - Mexico
dativa19@comunidad.unam.mx