Paper published in a book (Scientific congresses, symposiums and conference proceedings)
Efficient Implementation of ECDH Key Exchange for MSP430-Based Wireless Sensor Networks
Liu, Zhe; Seo, Hwajeong; Hu, Zhiet al.
2015 • In Bao, Feng; Miller, Steven; Zhou, Jianyinget al. (Eds.) ASIACCS'15: Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security, April 14-17, 2015, Singapore
[en] Public-Key Cryptography (PKC) is an indispensable building block of modern security protocols, and, thus, essential for secure communication over insecure networks. Despite a significant body of research devoted to making PKC more "lightweight," it is still commonly perceived that software implementations of PKC are computationally too expensive for practical use in ultra-low power devices such as wireless sensor nodes. In the present paper we aim to challenge this perception and present a highly-optimized implementation of Elliptic Curve Cryptography (ECC) for the TI MSP430 series of 16-bit microcontrollers. Our software is inspired by MoTE-ECC and supports scalar multiplication on two families of elliptic curves, namely Montgomery and twisted Edwards curves. However, in contrast to MoTE-ECC, we use pseudo-Mersenne prime fields as underlying algebraic structure to facilitate inter-operability with existing ECC implementations. We introduce a novel "zig-zag" technique for multiple-precision squaring on the MSP430 and assess its execution time. Similar to MoTE-ECC, we employ the Montgomery model for variable-base scalar multiplications and the twisted Edwards model if the base point is fixed (e.g. to generate an ephemeral key pair). Our experiments show that the two scalar multiplications needed to perform an ephemeral ECDH key exchange can be accomplished in 4.88 million clock cycles altogether (using a 159-bit prime field), which sets a new speed record for ephemeral ECDH on a 16-bit processor. We also describe the curve generation process and analyze the execution time of various field and point arithmetic operations on curves over a 159-bit and a 191-bit pseudo-Mersenne prime field.
Disciplines :
Computer science
Author, co-author :
Liu, Zhe ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Seo, Hwajeong; Pusan National University > School of Computer Science and Engineering
Hu, Zhi; Central South University > School of Mathematics and Statistics
Huang, Xinyi; Fujian Normal University > School of Mathematics and Computer Scienc
Groszschädl, Johann ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
External co-authors :
yes
Language :
English
Title :
Efficient Implementation of ECDH Key Exchange for MSP430-Based Wireless Sensor Networks
Publication date :
April 2015
Event name :
10th ACM Symposium on Information, Computer and Communications Security (ASIACCS 2015)
Event place :
Singapore, Singapore
Event date :
from 15-04-2015 to 17-04-2015
Audience :
International
Main work title :
ASIACCS'15: Proceedings of the 10th ACM Symposium on Information, Computer and Communications Security, April 14-17, 2015, Singapore
I. F. Akyildiz and M. C. Vuran. Wireless Sensor Networks. John Wiley and Sons, 2010.
D. J. Bernstein. Curve25519: New Diffie-Hellman speed records. In Public Key Cryptography | PKC 2006, vol. 3958 of Lecture Notes in Computer Science, pp. 207-228. Springer Verlag, 2006.
D. J. Bernstein, P. Birkner, M. Joye, T. Lange, and C. Peters. Twisted Edwards curves. In Progress in Cryptology | AFRICACRYPT 2008, vol. 5023 of Lecture Notes in Computer Science, pp. 389-405. Springer Verlag, 2008.
D. J. Bernstein and T. Lange. SafeCurves: Choosing safe curves for elliptic-curve cryptography. Avialable online at http://safecurves.cr.yp.to, 2013.
C. P. Gouvêa and J. López. Software implementation of pairing-based cryptography on sensor networks using the MSP430 microcontroller. In Progress in Cryptology | INDOCRYPT 2009, vol. 5922 of Lecture Notes in Computer Science, pp. 248-262. Springer Verlag, 2009.
J. Groffschädl. A family of implementation-friendly MoTE elliptic curves. Technical report TR-LACS-2013-01, Laboratory of Algorithmics, Cryptology and Security (LACS), University of Luxembourg, Luxembourg, 2013.
N. Gura, A. Patel, A. S. Wander, H. Eberle, and S. Chang Shantz. Comparing elliptic curve cryptography and RSA on 8-bit CPUs. In Cryptographic Hardware and Embedded Systems | CHES 2004, vol. 3156 of Lecture Notes in Computer Science, pp. 119-132. Springer Verlag, 2004.
D. R. Hankerson, A. J. Menezes, and S. A. Vanstone. Guide to Elliptic Curve Cryptography. Springer Verlag, 2004.
G. Hinterwälder, C. Paar, and W. P. Burleson. Privacy preserving payments on computational RFID devices with application in intelligent transportation systems. In Radio Frequency Identification Security and Privacy Issues | RFIDSec 2012, vol. 7739 of Lecture Notes in Computer Science, pp. 109-122. Springer Verlag, 2012.
G. Hinterwälder, A. Moradi, M. Hutter, P. Schwabe, and C. Paar. Full-size high-security ECC implementation on MSP430 microcontrollers. In Progress in Cryptology | LATINCRYPT 2014, vol. 8895 of Lecture Notes in Computer Science, pp. 22-38. Springer Verlag, 2015.
H. Hişil, K. K.-H. Wong, G. Carter, and E. Dawson. Twisted Edwards curves revisited. In Advances in Cryptology | ASIACRYPT 2008, vol. 5350 of Lecture Notes in Computer Science, pp. 326-343. Springer Verlag, 2008.
C. Lederer, R. Mader, M. Koschuch, J. Groffschädl, A. Szekely, and S. Tillich. Energy-eficient implementation of ECDH key exchange for wireless sensor networks. In Information Security Theory and Practice | WISTP 2009, vol. 5746 of Lecture Notes in Computer Science, pp. 112-127. Springer Verlag, 2009.
L. Li, J. Groffschädl, Z. Liu, and Q. Xu. Energy-eficient elliptic curve cryptography for MSP430-based wireless sensor nodes. Preprint, submitted for publication, 2015.
A. Liu and P. Ning. TinyECC: A configurable library for elliptic curve cryptography in wireless sensor networks. In Proceedings of the 7th International Conference on Information Processing in Sensor Networks (IPSN 2008), pp. 245-256. IEEE Computer Society, 2008.
Z. Liu, J. Groffschädl, and D. S. Wong. Low-weight primes for lightweight elliptic curve cryptography on 8-bit AVR processors. In Information Security and Cryptology | INSCRYPT 2013, vol. 8567 of Lecture Notes in Computer Science, pp. 217-235. Springer Verlag, 2014.
Z. Liu, E. Wenger, and J. Groffschädl. MoTE-ECC: Energy-scalable elliptic curve cryptography for wireless sensor networks. In Applied Cryptography and Network Security | ACNS 2014, vol. 8479 of Lecture Notes in Computer Science, pp. 361-379. Springer Verlag, 2014.
J. Lopez and J. Zhou. Wireless Sensor Network Security, vol. 1 of Cryptology and Information Security Series. IOS Press, 2008.
L. Marin, A. J. Jara, and A. F. Gómez-Skarmeta. Shifting primes: Extension of pseudo-Mersenne primes to optimize ECC for MSP430-based future Internet of things devices. In Availability, Reliability and Security for Business, Enterprise and Health Information Systems, vol. 6908 of Lecture Notes in Computer Science, pp. 205-219. Springer Verlag, 2011.
P. L. Montgomery. Speeding the Pollard and elliptic curve methods of factorization. Mathematics of Computation, 48(177):243-264, Jan. 1987.
C. Pendl, M. Pelnar, and M. Hutter. Elliptic curve cryptography on the WISP UHF RFID tag. In RFID Security and Privacy | RFIDSec 2011, vol. 7055 of Lecture Notes in Computer Science, pp. 32-47. Springer Verlag, 2012.
H. Seo, Y. Lee, H. Kim, T. Park, and H. Kim. Binary and primeéld multiplication for public key cryptography on embedded microprocessors. Security and Communication Networks, 7(4):774-787, Apr. 2014.
H. Seo, K.-A. Shim, and H. Kim. Performance enhancement of TinyECC based on multiplication optimizations. Security and Communication Networks, 6(2):151-160, Feb. 2013.
P. Szczechowiak, L. B. Oliveira, M. Scott, M. Collier, and R. Dahab. NanoECC: Testing the limits of elliptic curve cryptography in sensor networks. In Wireless Sensor Networks | EWSN 2008, vol. 4913 of Lecture Notes in Computer Science, pp. 305-320. Springer Verlag, 2008.
Texas Instruments, Inc. MSP430x1xx Family User's Guide (Rev. F). Manual, vailable for download at http://www.ti.com/lit/ug/slau049f/slau049f.pdf, 2006.
H. Wang, B. Sheng, and Q. Li. Elliptic curve cryptography-based access control in sensor networks. International Journal of Security and Networks, 1(3-4):127-137, Dec. 2006.
E. Wenger. Hardware architectures for MSP430-based wireless sensor nodes performing elliptic curve cryptography. In Applied Cryptography and Network Security | ACNS 2013, vol. 7954 of Lecture Notes in Computer Science, pp. 290-306. Springer Verlag, 2013.
E. Wenger and M. Werner. Evaluating 16-bit processors for elliptic curve cryptography. In Smart Card Research and Advanced Applications | CARDIS 2011, vol. 7079 of Lecture Notes in Computer Science, pp. 166-181. Springer Verlag, 2011.