×

Improving the Big Mac attack on elliptic curve cryptography. (English) Zbl 1405.94056

Ryan, Peter Y. A. (ed.) et al., The new codebreakers. Essays dedicated to David Kahn on the occasion of his 85th birthday. Berlin: Springer (ISBN 978-3-662-49300-7/pbk; 978-3-662-49301-4/ebook). Lecture Notes in Computer Science 9100, 374-386 (2016).
Summary: At CHES 2001, C. D. Walter, Lect. Notes Comput. Sci. 2162, 286–299 (2001; Zbl 1007.68994)] introduced the Big Mac attack against an implementation of RSA. It is an horizontal collision attack, based on the detection of common operands in two multiplications. The attack is very powerful since one single power trace of an exponentiation permits to recover all bits of the secret exponent. Moreover, the attack works with unknown or blinded input. The technique was later studied and improved by C. Clavier et al. and presented at INDOCRYPT 2012 [Lect. Notes Comput. Sci. 7668, 140–155 (2012; Zbl 1295.94039)]. At SAC 2013, A. Bauer et al. [Lect. Notes Comput. Sci. 8282, 553–570 (2014; Zbl 1362.94018)] presented the first attack based on the Big Mac principle on implementations based on elliptic curves with simulation results.
In this work, we improve the attack presented by Bauer et al. (loc. cit.) to considerably increase the success rate. Instead of comparing only two multiplications, the targeted implementation permits to compare many multiplications. We give experiment results with traces taken from a real target to prove the soundness of our attack. In fact, the experimental results show that the original Big Mac technique given by Walter was better that the technique given by Clavier et al. (loc. cit.). With our experiments on a real target, we show that the theoretical improvements are not necessarily the more suitable methods depending on the targeted implementations.
For the entire collection see [Zbl 1334.94030].

MSC:

94A60 Cryptography
14G50 Applications to coding theory and cryptography of arithmetic geometry
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bauer, A., Jaulmes, É., Prouff, E., Wild, J.: Horizontal and vertical side-channel attacks against secure RSA implementations. In: Dawson, E. (ed.) CT-RSA 2013. LNCS, vol. 7779, pp. 1–17. Springer, Heidelberg (2013) · Zbl 1283.68029
[2] Bauer, A., Jaulmes, É., Prouff, E., Wild, J.: Horizontal Collision Correlation Attack on Elliptic Curves. In: SAC 2013 (2013, to appear) · Zbl 1362.94018
[3] Barrett, P.: Implementing the rivest shamir and adleman public key encryption algorithm on a standard digital signal processor. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 311–323. Springer, Heidelberg (1987)
[4] Ciet, M., Joye, M.: (Virtually) free randomization techniques for elliptic curve cryptography. In: Qing, S., Gollmann, D., Zhou, J. (eds.) ICICS 2003. LNCS, vol. 2836, pp. 348–359. Springer, Heidelberg (2003) · Zbl 1300.94047
[5] Clavier, C., Feix, B., Gagnerot, G., Giraud, C., Roussellet, M., Verneuil, V.: ROSETTA for single trace analysis. In: Galbraith, S., Nandi, M. (eds.) INDOCRYPT 2012. LNCS, vol. 7668, pp. 140–155. Springer, Heidelberg (2012) · Zbl 1295.94039
[6] Clavier, C., Feix, B., Gagnerot, G., Roussellet, M., Verneuil, V.: Horizontal correlation analysis on exponentiation. In: Soriano, M., Qing, S., López, J. (eds.) ICICS 2010. LNCS, vol. 6476, pp. 46–61. Springer, Heidelberg (2010) · Zbl 1295.94040
[7] Cohen, H., Miyaji, A., Ono, T.: Efficient elliptic curve exponentiation using mixed coordinates. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 51–65. Springer, Heidelberg (1998) · Zbl 0939.11039
[8] 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) · Zbl 0955.94009
[9] Chevallier-Mames, B., Ciet, M., Joye, M.: Low-cost solutions for preventing simple side-channel analysis: side-channel atomicity. J. IEEE Trans. Comput. 53(6), 460–468 (2004) · Zbl 1300.94045
[10] Clavier, C., Joye, M.: Universal exponentiation algorithm. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, p. 300. Springer, Heidelberg (2001) · Zbl 1007.68995
[11] Giraud, C., Verneuil, V.: Atomicity improvement for elliptic curve scalar multiplication. In: Gollmann, D., Lanet, J.-L., Iguchi-Cartigny, J. (eds.) CARDIS 2010. LNCS, vol. 6035, pp. 80–101. Springer, Heidelberg (2010) · Zbl 05695182
[12] Joye, M.: Fast point multiplication on elliptic curves without precomputation. In: Gathen, J., Imaña, J.L., Koç, Ç.K. (eds.) WAIFI 2008. LNCS, vol. 5130, pp. 36–46. Springer, Heidelberg (2008) · Zbl 1202.94184
[13] Joye, M., Tymen, C.: Protections against Differential Analysis for Elliptic Curve Cryptography. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 377–390. Springer, Heidelberg (2001) · Zbl 1012.94550
[14] Montgomery, P.L.: Modular multiplication without trial division. J. Math. Comput. 44(170), 519–521 (1985) · Zbl 0559.10006
[15] Side-channel Attack Standard Evaluation Board (SASEBO). http://www.rcis.aist.go.jp/special/SASEBO/
[16] Walter, C.D.: Sliding windows succumbs to Big Mac attack. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, p. 286. Springer, Heidelberg (2001) · Zbl 1007.68994
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.