Abstract
In 2005, Yen et al. firstly proposed the N − 1 attack against cryptosystems implemented based on BRIP and square-multiply-always algorithms. This attack uses the input message N − 1 to obtain relevant side-channel information from the attacked cryptosystem. In this paper we conduct an in-depth study on the N − 1 attack and find that two more special values taken as the input message also can be exploited by an attacker. According to this, we present our chosen-message attack against Boscher’s right-to-left exponentiation algorithm which is a side-channel resistant exponentiation algorithm. Furthermore, immunity of the Montgomery Powering Ladder against the N − 1 attack is investigated. The result is that the Montgomery Powering Ladder is subjected to the N − 1 attack. But a different approach to retrieve the key is used which derives from the relative doubling attack. To validate our ideas, we implement the two algorithms in hardware and carry out the attacks on them. The experiment results show that our attacks are powerful attacks against these two algorithms and can be easily implemented with one power consumption curve.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Kocher, P.C., Jaffe, J., Jun, B.: Differential Power Analysis. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 388–397. Springer, Heidelberg (1999)
Joye, M., Yen, S.-M.: The montgomery powering ladder. In: Kaliski Jr, B.S., Koç, Ç.K., Paar, C. (eds.) CHES 2002. LNCS, vol. 2523, pp. 291–302. Springer, Heidelberg (2003)
Fumaroli, G., Vigilant, D.: Blinded fault resistant exponentiation. In: Breveglieri, L., Koren, I., Naccache, D., Seifert, J.-P. (eds.) FDTC 2006. LNCS, vol. 4236, pp. 62–70. Springer, Heidelberg (2006)
Schmidt, J.-M., Medwed, M.: Fault attacks on the montgomery powering ladder. In: Rhee, K.-H., Nyang, D. (eds.) ICISC 2010. LNCS, vol. 6829, pp. 396–406. Springer, Heidelberg (2011)
Boscher, A., Handschuh, H., Trichina, E.: Blinded fault resistant exponentiation revisited. In: Breveglieri, L., et al. (eds.) Fault Diagnosis and Tolerance in Cryptography - FDTC 2009, pp. 3–9. IEEE Computer Society (2009)
Yen S.-M., Lien W.-C., Moon S., Ha J.: Power analysis by exploiting chosen message and internal collisions-vulnerability of checking mechanism for RSA-decryption. In: Dawson, E., Vaudenay, S. (eds.) Mycrypt 2005. LNCS, vol. 3715, pp. 183-195. Springer, Heidelberg (2005)
Coron, J.-S.: Resistance against differential power analysis for elliptic curve cryptosystems. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 292–302. Springer, Heidelberg (1999)
Mamiya, H., Miyaji, A., Morimoto, H.: Efficient countermeasures against RPA, DPA, and SPA. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 343–356. Springer, Heidelberg (2004)
Miyamoto, A., Homma, N., Aoki, T., Satoh, A.: Enhanced power analysis attack using chosen message against RSA hardware implementations. In: ISCAS, pp. 3282–3285 (2008)
Courrège, J.-C., Feix, B., Roussellet, M.: Simple power analysis on exponentiation revisited. In: Gollmann, D., Lanet, J.-L., Iguchi-Cartigny, J. (eds.) CARDIS 2010. LNCS, vol. 6035, pp. 65–79. Springer, Heidelberg (2010)
Homma, N., Miyamoto, A., Aoki, T., Satoh, A., Samir, A.: Comparative power analysis of modular exponentiation algorithms. IEEE Trans. Comput. 59(6), 795–807 (2010)
Clavier, C., Feix, B.: Updated recommendations for blinded exponentiation vs. single trace analysis. In: Prouff, E. (ed.) COSADE 2013. LNCS, vol. 7864, pp. 80–98. Springer, Heidelberg (2013)
Aidong, C., Sen, X., Yun, C., Zhiguang, Q.: Collision-based chosen-message simple power clustering attack algorithm. Communications, China, 114–119 (2013)
Yen, S.-M., Ko, L.-C., Moon, S.-J., Ha, J.C.: Relative doubling attack against montgomery ladder. In: Won, D.H., Kim, S. (eds.) ICISC 2005. LNCS, vol. 3935, pp. 117–128. Springer, Heidelberg (2006)
Miyamoto, A., Homma, N., Aoki, T., Satoh, A.: Systematic design of RSA processors based on high-radix Montgomery multipliers. In: IEEE Transactions on Very Large Scale Integration (VLSI) Systems, pp. 1136–1146 (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Ding, Z., Guo, W., Su, L., Wei, J., Gu, H. (2014). Further Research on N-1 Attack against Exponentiation Algorithms. In: Susilo, W., Mu, Y. (eds) Information Security and Privacy. ACISP 2014. Lecture Notes in Computer Science, vol 8544. Springer, Cham. https://doi.org/10.1007/978-3-319-08344-5_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-08344-5_11
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08343-8
Online ISBN: 978-3-319-08344-5
eBook Packages: Computer ScienceComputer Science (R0)