×

Safe-errors on SPA protected implementations with the atomicity technique. (English) Zbl 1405.94062

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, 479-493 (2016).
Summary: ECDSA is one of the most important public-key signature scheme, however it is vulnerable to lattice attack once a few bits of the nonces are leaked. To protect Elliptic Curve Cryptography (ECC) against Simple Power Analysis, many countermeasures have been proposed. Doubling and Additions of points on the given elliptic curve require several additions and multiplications in the base field and this number is not the same for the two operations. The idea of the atomicity protection is to use a fixed pattern, i.e. a small number of instructions and rewrite the two basic operations of ECC using this pattern. Dummy operations are introduced so that the different elliptic curve operations might be written with the same atomic pattern. In an adversary point of view, the attacker only sees a succession of patterns and is no longer able to distinguish which one corresponds to addition and doubling. Chevallier-Mames, Ciet and Joye were the first to introduce such countermeasure.
In this paper, we are interested in studying this countermeasure and we show a new vulnerability since the ECDSA implementation succumbs now to C Safe-Error attacks. Then, we propose an effective solution to prevent against C Safe-Error attacks when using the Side-Channel Atomicity. The dummy operations are used in such a way that if a fault is introduced on one of them, it can be detected. Finally, our countermeasure method is generic, meaning that it can be adapted to all formulae. We apply our methods to different formulae presented for Side-Channel Atomicity.
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] Aranha, D.F., Fouque, P.-A., Gérard, B., Kammerer, J.-G., Tibouchi, M., Zapalowicz, J.-C.: GLV/GLS decomposition, power analysis, and attacks on ECDSA signatures with single-bit nonce bias. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 262–281. Springer, Heidelberg (2014) · Zbl 1306.94023
[2] Boneh, D., Venkatesan, R.: Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 129–142. Springer, Heidelberg (1996) · Zbl 1329.94054
[3] Brumley, B.B., Tuveri, N.: Remote timing attacks are still practical. In: Atluri, V., Diaz, C. (eds.) ESORICS 2011. LNCS, vol. 6879, pp. 355–371. Springer, Heidelberg (2011) · Zbl 05975865
[4] Chevallier-Mames, B., Ciet, M., Joye, M.: Low-cost solutions for preventing simple side-channel analysis: side-channel atomicity. IEEE Trans. Comput. 53(6), 760–768 (2004) · Zbl 1300.94045
[5] 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
[6] 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
[7] 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
[8] Howgrave-Graham, N., Smart, N.P.: Lattice attacks on digital signature schemes. Des. Codes Cryptogr. 23(3), 283–290 (2001) · Zbl 1006.94022
[9] Liu, M., Nguyen, P.Q.: Solving BDD by enumeration: an update. In: Dawson, E. (ed.) CT-RSA 2013. LNCS, vol. 7779, pp. 293–309. Springer, Heidelberg (2013) · Zbl 1312.94070
[10] Longa, P.: Accelerating the scalar multiplication on elliptic curve cryptosystems over prime fields. Master’s thesis, School of Information and Engineering, University of Ottawa, Canada (2007)
[11] De Mulder, E., Hutter, M., Marson, M.E., Pearson, P.: Using Bleichenbacher’s solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA: extended version. J. Cryptogr. Eng. 4(1), 33–45 (2014)
[12] Naccache, D., Nguyên, P.Q., Tunstall, M., Whelan, C.: Experimenting with faults, lattices and the DSA. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 16–28. Springer, Heidelberg (2005) · Zbl 1081.94533
[13] Nguyen, P.Q., Shparlinski, I.: The insecurity of the elliptic curve digital signature algorithm with partially known nonces. Des. Codes Cryptogr. 30(2), 201–217 (2003) · Zbl 1039.94008
[14] Nguyen, P.Q., Tibouchi, M.: Lattice-based fault attacks on signatures. In: Joye, M., Tunstall, M. (eds.) Fault Analysis in Cryptography. Information Security and Cryptography, pp. 201–220. Springer, Heidelberg (2012) · Zbl 1267.94087
[15] Rondepierre, F.: Revisiting atomic patterns for scalar multiplications on elliptic curves. In: Francillon, A., Rohatgi, P. (eds.) CARDIS 2013. LNCS, vol. 8419, pp. 171–186. Springer, Heidelberg (2014)
[16] Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288–303. Springer, Heidelberg (2002) · Zbl 1026.94541
[17] ANSI X9.62. Public key cryptography for the financial services industry: the elliptic curve digital signature algorithm (ECDSA). ANSI, USA (1998)
[18] Yen, S.-M., Kim, S., Lim, S., Moon, S.-J.: A countermeasure against one physical cryptanalysis may benefit another attack. In: Kim, K. (ed.) ICISC 2001. LNCS, vol. 2288, pp. 414–427. Springer, Heidelberg (2002) · Zbl 0999.94540
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.