Attacking embedded ECC implementations through CMOV side channels. (English) Zbl 1412.94194
Avanzi, Roberto (ed.) et al., Selected areas in cryptography – SAC 2016. 23rd international conference, St. John’s, NL, Canada, August 10–12, 2016. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10532, 99-119 (2017).
Summary: Side-channel attacks against implementations of elliptic-curve cryptography have been extensively studied in the literature and a large tool-set of countermeasures is available to thwart different attacks in different contexts. The current state of the art in attacks and countermeasures is nicely summarized in multiple survey papers, the most recent one by J. L. Danger et al. [A synthesis of side-channel attacks on elliptic curve cryptography in smart-cards. J. Cryptogr. Eng. 3, No. 4, 1–25 (2013)]. However, any combination of those countermeasures is ineffective against attacks that require only a single trace and directly target a conditional move (cmov) - an operation that is at the very foundation of all scalar-multiplication algorithms. This operation can either be implemented through arithmetic operations on registers or through various different approaches that all boil down to loading from or storing to a secret address. In this paper we demonstrate that such an attack is indeed possible for ECC software running on AVR ATmega microcontrollers, using a protected version of the popular \(\mu \mathrm{NaCl}\) library as an example. For the targeted implementations, we are able to recover 99.6% of the key bits for the arithmetic approach and 95.3% of the key bits for the approach based on secret addresses, with confidence levels 76.1% and 78.8%, respectively. All publicly available ECC software for the AVR that we are aware of uses one of the two approaches and is thus in principle vulnerable to our attack.
For the entire collection see [Zbl 1378.94001].
For the entire collection see [Zbl 1378.94001].
MSC:
| 94A60 | Cryptography |
References:
| [1] | Amaxilatis, D.: A generic algorithms library for heterogeneous, distributed, embedded systems. https://github.com/ibr-alg/wiselib |
| [2] | Aranha, D.F., Gouvêa, C.P.L.: RELIC is an Efficient LIbrary for Cryptography. https://github.com/relic-toolkit/relic |
| [3] | Atmel. Atmega328P datasheet (2016). http://www.atmel.com/devices/atmega328p.aspx |
| [4] | Bajard, J-C; Imbert, L.; Liardet, P-Y; Teglia, Y.; Joye, M.; Quisquater, J-J, Leak resistant arithmetic, Cryptographic Hardware and Embedded Systems - CHES 2004, 62-75 (2004), Heidelberg: Springer, Heidelberg · Zbl 1104.68464 · doi:10.1007/978-3-540-28632-5_5 |
| [5] | Batina, L.; Chmielewski, Ł.; Papachristodoulou, L.; Schwabe, P.; Tunstall, M.; Meier, W.; Mukhopadhyay, D., Online template attacks, Progress in Cryptology - INDOCRYPT 2014, 21-36 (2014), Cham: Springer, Cham · Zbl 1344.94030 |
| [6] | Bauer, A.; Jaulmes, É.; Paul, G.; Vaudenay, S., Correlation analysis against protected SFM implementations of RSA, Progress in Cryptology - INDOCRYPT 2013, 98-115 (2013), Cham: Springer, Cham · Zbl 1295.94017 · doi:10.1007/978-3-319-03515-4_7 |
| [7] | Bauer, A.; Jaulmes, É.; Prouff, E.; Reinhard, J.; Wild, J., Horizontal collision correlation attack on elliptic curves - extended version -, Cryptogr. Commun., 7, 91-119 (2015) · Zbl 1365.94400 · doi:10.1007/s12095-014-0111-8 |
| [8] | Bauer, A.; Jaulmes, E.; Prouff, E.; Wild, J.; Dawson, E., Horizontal and vertical side-channel attacks against secure RSA implementations, Topics in Cryptology - CT-RSA 2013, 1-17 (2013), Heidelberg: Springer, Heidelberg · Zbl 1297.94044 · doi:10.1007/978-3-642-36095-4_1 |
| [9] | Bauer, S.; Schindler, W.; Huss, SA, Attacking exponent blinding in RSA without CRT, Constructive Side-Channel Analysis and Secure Design, 82-88 (2012), Heidelberg: Springer, Heidelberg · Zbl 1352.94026 · doi:10.1007/978-3-642-29912-4_7 |
| [10] | Benger, N.; van de Pol, J.; Smart, NP; Yarom, Y.; Batina, L.; Robshaw, M., “Ooh aah... just a little bit”: a small amount of side channel can go a long way, Cryptographic Hardware and Embedded Systems - CHES 2014, 75-92 (2014), Heidelberg: Springer, Heidelberg · Zbl 1332.94057 |
| [11] | Brier, E.; Clavier, C.; Olivier, F.; Joye, M.; Quisquater, J-J, Correlation power analysis with a leakage model, Cryptographic Hardware and Embedded Systems - CHES 2004, 16-29 (2004), Heidelberg: Springer, Heidelberg · Zbl 1104.68467 · doi:10.1007/978-3-540-28632-5_2 |
| [12] | Brier, É.; Joye, M.; Naccache, D.; Paillier, P., Weierstraß elliptic curves and side-channel attacks, Public Key Cryptography, 335-345 (2002), Heidelberg: Springer, Heidelberg · Zbl 1055.94512 · doi:10.1007/3-540-45664-3_24 |
| [13] | CertiVox. MIRACL Cryptographic SDK. https://github.com/CertiVox/MIRACL |
| [14] | Chari, S.; Rao, JR; Rohatgi, P.; Kaliski, BS; Koç, K.; Paar, C., Template attacks, Cryptographic Hardware and Embedded Systems - CHES 2002, 13-28 (2003), Heidelberg: Springer, Heidelberg · Zbl 1019.68541 · doi:10.1007/3-540-36400-5_3 |
| [15] | Chen, C-N; Lee, J.; Kim, J., Memory address side-channel analysis on exponentiation, Information Security and Cryptology - ICISC 2014, 421-432 (2015), Cham: Springer, Cham · Zbl 1344.94037 |
| [16] | Choudary, O.; Kuhn, MG; Francillon, A.; Rohatgi, P., Efficient template attacks, Smart Card Research and Advanced Applications, 253-270 (2014), Cham: Springer, Cham |
| [17] | Clavier, C.; Feix, B.; Gagnerot, G.; Giraud, C.; Roussellet, M.; Verneuil, V.; Galbraith, S.; Nandi, M., ROSETTA for single trace analysis, Progress in Cryptology - INDOCRYPT 2012, 140-155 (2012), Heidelberg: Springer, Heidelberg · Zbl 1295.94039 · doi:10.1007/978-3-642-34931-7_9 |
| [18] | Clavier, C.; Feix, B.; Gagnerot, G.; Roussellet, M.; Verneuil, V.; Soriano, M.; Qing, S.; López, J., Horizontal correlation analysis on exponentiation, Information and Communications Security, 46-61 (2010), Heidelberg: Springer, Heidelberg · Zbl 1295.94040 · doi:10.1007/978-3-642-17650-0_5 |
| [19] | Coron, J-S; Koç, ÇK; Paar, C., Resistance against differential power analysis for elliptic curve cryptosystems, Cryptographic Hardware and Embedded Systems, 292-302 (1999), Heidelberg: Springer, Heidelberg · Zbl 0955.94009 · doi:10.1007/3-540-48059-5_25 |
| [20] | Courrège, J-C; Feix, B.; Roussellet, M.; Gollmann, D.; Lanet, J-L; Iguchi-Cartigny, J., Simple power analysis on exponentiation revisited, Smart Card Research and Advanced Application, 65-79 (2010), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-12510-2_6 |
| [21] | Danger, J-L; Guilley, S.; Hoogvorst, P.; Murdica, C.; Naccache, D., A synthesis of side-channel attacks on elliptic curve cryptography in smart-cards, J. Cryptogr. Eng., 3, 4, 1-25 (2013) · doi:10.1007/s13389-013-0062-6 |
| [22] | Dugardin, M., Papachristodoulou, L., Najm, Z., Batina, L., Danger, J., Guilley, S., Courrège, J., Therond, C.: Dismantling real-world ECC with horizontal and vertical template attacks. Cryptology ePrint Archive, Report 2015/1001 (2015) |
| [23] | Düll, M.; Haase, B.; Hinterwälder, G.; Hutter, M.; Paar, C.; Sánchez, AH; Schwabe, P., High-speed curve25519 on 8-bit, 16-bit and 32-bit microcontrollers, Des. Codes Crypt., 77, 2, 493-514 (2015) · Zbl 1327.94042 · doi:10.1007/s10623-015-0087-1 |
| [24] | Dupaquis, V.; Venelli, A.; Prouff, E., Redundant modular reduction algorithms, Smart Card Research and Advanced Applications, 102-114 (2011), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-27257-8_7 |
| [25] | Fouque, P-A; Valette, F.; Walter, CD; Koç, ÇK; Paar, C., The doubling attack – why upwards is better than downwards, Cryptographic Hardware and Embedded Systems - CHES 2003, 269-280 (2003), Heidelberg: Springer, Heidelberg · Zbl 1274.94066 · doi:10.1007/978-3-540-45238-6_22 |
| [26] | Gopalakrishnan, K.; Thériault, N.; Yao, CZ; Srinathan, K.; Rangan, CP; Yung, M., Solving discrete logarithms from partial knowledge of the key, Progress in Cryptology - INDOCRYPT 2007, 224-237 (2007), Heidelberg: Springer, Heidelberg · Zbl 1153.94383 · doi:10.1007/978-3-540-77026-8_17 |
| [27] | Hanley, N.; Kim, HS; Tunstall, M.; Nyberg, K., Exploiting collisions in addition chain-based exponentiation algorithms using a single trace, Topics in Cryptology — CT-RSA 2015, 431-448 (2015), Cham: Springer, Cham · Zbl 1382.94118 |
| [28] | Herbst, C.; Medwed, M.; Chung, K-I; Sohn, K.; Yung, M., Using templates to attack masked montgomery ladder implementations of modular exponentiation, Information Security Applications, 1-13 (2009), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-00306-6_1 |
| [29] | Heyszl, J.; Ibing, A.; Mangard, S.; Santis, F.; Sigl, G.; Francillon, A.; Rohatgi, P., Clustering algorithms for non-profiled single-execution attacks on exponentiations, Smart Card Research and Advanced Applications, 79-93 (2014), Cham: Springer, Cham |
| [30] | Heyszl, J.; Mangard, S.; Heinz, B.; Stumpf, F.; Sigl, G.; Dunkelman, O., Localized electromagnetic analysis of cryptographic implementations, Topics in Cryptology - CT-RSA 2012, 231-244 (2012), Heidelberg: Springer, Heidelberg · Zbl 1292.94077 · doi:10.1007/978-3-642-27954-6_15 |
| [31] | Homma, N.; Miyamoto, A.; Aoki, T.; Satoh, A.; Shamir, A., Comparative power analysis of modular exponentiation algorithms, IEEE Trans. Comput., 59, 6, 795-807 (2010) · Zbl 1367.65222 · doi:10.1109/TC.2009.176 |
| [32] | Hutter, M.; Schwabe, P.; Youssef, A.; Nitaj, A.; Hassanien, AE, NaCl on 8-bit AVR microcontrollers, Progress in Cryptology - AFRICACRYPT 2013, 156-172 (2013), Heidelberg: Springer, Heidelberg · Zbl 1312.94059 · doi:10.1007/978-3-642-38553-7_9 |
| [33] | iSec Partners. nano-ecc - a very small ECC implementation for 8-bit microcontrollers (2016). https://github.com/iSECPartners/nano-ecc |
| [34] | Itoh, K.; Izu, T.; Takenaka, M.; Kaliski, BS; Koç, K.; Paar, C., Address-bit differential power analysis of cryptographic schemes OK-ECDH and OK-ECDSA, Cryptographic Hardware and Embedded Systems - CHES 2002, 129-143 (2003), Heidelberg: Springer, Heidelberg · Zbl 1019.68557 · doi:10.1007/3-540-36400-5_11 |
| [35] | Itoh, K.; Izu, T.; Takenaka, M.; Walter, CD; Koç, ÇK; Paar, C., A practical countermeasure against address-bit differential power analysis, Cryptographic Hardware and Embedded Systems - CHES 2003, 382-396 (2003), Heidelberg: Springer, Heidelberg · Zbl 1274.94080 · doi:10.1007/978-3-540-45238-6_30 |
| [36] | Izumi, M., Ikegami, J., Sakiyama, K., Ohta, K.: Improved countermeasure against address-bit DPA for ECC scalar multiplication. In: 2010 Design, Automation & Test in Europe Conference and Exhibition (DATE 2010), pp. 981-984. IEEE (2010) |
| [37] | Izumi, M., Sakiyama, K., Ohta, K.: A new approach for implementing the MPL method toward higher SPA resistance. In: International Conference on Availability, Reliability and Security, ARES 2009, pp. 181-186. IEEE (2009) |
| [38] | Kocher, PC; Koblitz, N., Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems, Advances in Cryptology — CRYPTO ’96, 104-113 (1996), Heidelberg: Springer, Heidelberg · Zbl 1329.94070 |
| [39] | Kocher, P.; Jaffe, J.; Jun, B.; Wiener, M., Differential power analysis, Advances in Cryptology — CRYPTO’ 99, 388-397 (1999), Heidelberg: Springer, Heidelberg · Zbl 0942.94501 · doi:10.1007/3-540-48405-1_25 |
| [40] | Lange, T.; Vredendaal, C.; Wakker, M.; Joye, M.; Moradi, A., Kangaroos in side-channel attacks, Smart Card Research and Advanced Applications, 104-121 (2015), Cham: Springer, Cham |
| [41] | Le, D-P; Tan, CH; Tunstall, M.; Akram, RN; Jajodia, S., Randomizing the montgomery powering ladder, Information Security Theory and Practice, 169-184 (2015), Cham: Springer, Cham · doi:10.1007/978-3-319-24018-3_11 |
| [42] | Liu, A., Ning, P.: TinyECC: A Configurable Library for Elliptic Curve Cryptography in Wireless Sensor Networks (Version 1.0). http://discovery.csc.ncsu.edu/software/TinyECC/ver1.0/index.html |
| [43] | Mackay, K.: micro-ecc - ECDH and ECDSA for 8-bit, 32-bit, and 64-bit processors (2016). https://github.com/kmackay/micro-ecc |
| [44] | Medwed, M.; Oswald, E.; Chung, K-I; Sohn, K.; Yung, M., Template attacks on ECDSA, Information Security Applications, 14-27 (2009), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-00306-6_2 |
| [45] | Montgomery, PL, Speeding the Pollard and elliptic curve methods of factorization, Math. Comput., 48, 177, 243-264 (1987) · Zbl 0608.10005 · doi:10.1090/S0025-5718-1987-0866113-7 |
| [46] | Nascimento, E.: SAC 2016 - Implementation of algorithm for ECDLP with errors based on a time-memory tradeoff (2016). https://github.com/enascimento/SCA-ECC-keyrecovery |
| [47] | Nascimento, E.: SAC 2016 - Targeted Curve25519 implementations for AVR (2016). https://github.com/enascimento/sac2016-avr-target-impls |
| [48] | Nascimento, E., Chmielewski, L., Oswald, D., Schwabe, P.: Attacking embedded ECC implementations through cmov side channels (2016). https://eprint.iacr.org/2016/923 · Zbl 1412.94194 |
| [49] | Nascimento, E.; López, J.; Dahab, R.; Chakraborty, RS; Schwabe, P.; Solworth, J., Efficient and secure elliptic curve cryptography for 8-bit AVR microcontrollers, Security, Privacy, and Applied Cryptography Engineering, 289-309 (2015), Cham: Springer, Cham · doi:10.1007/978-3-319-24126-5_17 |
| [50] | Negre, C.; Perin, G.; Foo, E.; Stebila, D., Trade-off approaches for leak resistant modular arithmetic in RNS, Information Security and Privacy, 107-124 (2015), Cham: Springer, Cham · Zbl 1358.94073 · doi:10.1007/978-3-319-19962-7_7 |
| [51] | O’Flynn, C.; Chen, ZD; Prouff, E., ChipWhisperer: an open-source platform for hardware embedded security research, Constructive Side-Channel Analysis and Secure Design, 243-260 (2014), Cham: Springer, Cham · Zbl 1440.94072 |
| [52] | Okeya, K.; Sakurai, K.; Koç, ÇK; Naccache, D.; Paar, C., Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a montgomery-form elliptic curve, Cryptographic Hardware and Embedded Systems — CHES 2001, 126-141 (2001), Heidelberg: Springer, Heidelberg · Zbl 1012.94551 · doi:10.1007/3-540-44709-1_12 |
| [53] | Otte, D.: Avr-crypto-lib (2016). https://git.cryptolib.org/avr-crypto-lib.git |
| [54] | Perin, G.; Chmielewski, Ł.; Homma, N.; Medwed, M., A semi-parametric approach for side-channel attacks on protected RSA implementations, Smart Card Research and Advanced Applications, 34-53 (2016), Cham: Springer, Cham · doi:10.1007/978-3-319-31271-2_3 |
| [55] | Perin, G.; Imbert, L.; Torres, L.; Maurine, P.; Prouff, E., Attacking randomized exponentiations using unsupervised learning, Constructive Side-Channel Analysis and Secure Design, 144-160 (2014), Cham: Springer, Cham · Zbl 1358.94075 |
| [56] | Sigma. ECDSA and ECDH cryptographic algorithms for 8-bit AVR microcontrollers. http://www.cmmsigma.eu/products/crypto/crs_avr010x.en.html |
| [57] | Walter, CD; Koç, ÇK; Naccache, D.; Paar, C., Sliding windows succumbs to big mac attack, Cryptographic Hardware and Embedded Systems — CHES 2001, 286-299 (2001), Heidelberg: Springer, Heidelberg · Zbl 1007.68994 · doi:10.1007/3-540-44709-1_24 |
| [58] | Wang, H.: WM-ECC is an Elliptic Curve Cryptography (ECC) primitive suite developed exclusively for wireless sensor motes. http://cis.csuohio.edu/ hwang/WMECC.html |
| [59] | Wenger, E.; Unterluggauer, T.; Werner, M.; Paul, G.; Vaudenay, S., 8/16/32 shades of elliptic curve cryptography on embedded processors, Progress in Cryptology - INDOCRYPT 2013, 244-261 (2013), Cham: Springer, Cham · Zbl 1295.94154 · doi:10.1007/978-3-319-03515-4_16 |
| [60] | wolfSSL. Embedded Web Server for AVR. https://www.wolfssl.com/wolfSSL/Blog/Entries/2010/11/16_Embedded_Web_Server_for_AVR.html |
| [61] | Zhang, Z., Wu, L., Mu, Z., Zhang, X.: A novel template attack on wNAF algorithm of ECC. In: 2014 Tenth International Conference on Computational Intelligence and Security (CIS), pp. 671-675. IEEE (2014) |
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.
