Home   >   CSC-OpenAccess Library   >    Manuscript Information
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 
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
J. M. Schmidt and M. Medwed. “Fault attacks on the montgomery powering ladder”. Information Security and Cryptology ICISC-2010, pp. 396-406, 2011.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
Mr. David Tinoco Varela
UNAM - Mexico
dativa19@comunidad.unam.mx