skip to main content
research-article

Implementing public-key infrastructure for sensor networks

Published: 04 September 2008 Publication History

Abstract

We present a critical evaluation of the first known implementation of elliptic curve cryptography over F2p for sensor networks based on the 8-bit, 7.3828-MHz MICA2 mote. We offer, along the way, a primer for those interested in the field of cryptography for sensor networks. We discuss, in particular, the decisions underlying our design and alternatives thereto. And we elaborate on the methodologies underlying our evaluation.
Through instrumentation of UC Berkeley's TinySec module, we argue that, although symmetric cryptography has been tractable in this domain for some time, there has remained a need, unfulfilled until recently, for an efficient, secure mechanism for distribution of secret keys among nodes. Although public-key infrastructure has been thought impractical, we show, through analysis of our original implementation for TinyOS of point multiplication on elliptic curves, that public-key infrastructure is indeed viable for TinySec keys' distribution, even on the MICA2. We demonstrate that public keys can be generated within 34 seconds and that shared secrets can be distributed among nodes in a sensor network within the same time, using just over 1 kilobyte of SRAM and 34 kilobytes of ROM. We demonstrate that communication costs are minimal, with only 2 packets required for transmission of a public key among nodes. We make available all of our source code for other researchers to download and use. And we discuss recent results based on our work that corroborate and improve upon our conclusions.

References

[1]
Adleman, L. M. 1979. A subexponential algorithm for the discrete logarithm problem with applications to cryptography. In Proceeding of the 20th IEEE Foundation of Computer Science Symposium. 55--60.
[2]
Arazi, O. and Qi, H. 2006. Load-balanced key establishment methodologies in wireless sensor networks. In Int. J. Secu. Networks. 1.
[3]
Barrett, P. 1987. Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. In Proceedings of Advances in Cryptology (CRYPTO'86), A. M. Odlyzko, Ed. Vol. 263.
[4]
Barwood, G. 1997. Elliptic curve cryptography FAQ v1.12 22nd. http://www.cryptoman.com/elliptic.htm.
[5]
Barwood, G. 2006. Pegwit (v8). http://www.george-barwood.pwp.blueyonder.co.uk/hp/v8/pegwit.htm.
[6]
Benenson, Z., Gedicke, N., and Raivio, O. 2005. Realizing robust user authentication in sensor networks. In Proceedings of Workshop on Real-World Wireless Sensor Networks (REALWSN'05). Stockholm, Sweden.
[7]
Biham, E., Biryukov, A., and Shamir, A. 1999. Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials. Lecture Notes in Computer Science, Vol. 1592, 12--23.
[8]
Blake, I., Seroussi, G., and Smart, N. 1999. Elliptic curves in cryptography. LMS Lecture Note Series 265.
[9]
Blass, E.-O. and Zitterbart, M. 2005. Towards acceptable public-key encryption in sensor networks. In Proceedings of the 1st International Workshop on Ubiquitous Computing (IWUC 2005).
[10]
Brown, M., Cheung, D., Hankerson, D., Hernandez, J. L., Kirkup, M., and Menezes, A. 2000. PGP in constrained wireless devices. In Proceedings of the 9th USENIX Security Symposium. USENIX Association.
[11]
Cerpa, A., Elson, J., Estrin, D., Girod, L., Hamilton, M., and Zhao, J. 2001. Habitat monitoring: application driver for wireless communications technology ACM SIGCOMM Comput. Comm. Rev. 31, 2 Supplement. ACM, NY.
[12]
Certicom Corporation. 2000. Remarks on the security of the elliptic curve cryptosystem. http://www.comms.engg.susx.ac.uk/fft/crypto/EccWhite3.pdf.
[13]
Certicom Corporation. 2004. Standards for efficient cryptography group. http://www.secg.org/.
[14]
Cohen, H., Miyaji, A., and Ono, T. 1998. Efficient elliptic curve exponentiation using mixed coordinates. In Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT'98). Springer-Verlag, London, UK, 51--65.
[15]
Crossbow Technology, Inc. 2004. MICA2: wireless measurement system. http://www.xbow.com/Products/Product_pdf_files/Wireless_pdf/6020-0042-0%4_A_MICA2.pdf.
[16]
Deng, J., Han, R., and Mishra, S. 2006. Secure code distribution in dynamically programmable wireless sensor networks. In Proceedings of the 5th International Conference on Information Processing in Sensor Networks (IPSN'06). ACM Press, New York, NY, 292--300.
[17]
Denis, T. S. 2004. LibTomCrypt. http://libtomcrypt.org/.
[18]
Diffie, W. and Hellman, M. E. 1976. New directions in cryptography. IEEE Trans. Inf. Theor. IT-22, 6, 644--654.
[19]
Diffie, W., van Oorschot, P. C., and Wiener, M. J. 1992. Authentication and authenticated key exchanges. Designs, Codes, Cryptogr. 2, 2, 107--125.
[20]
Dragongate Technologies Limited. 2003. jBorZoi 0.9. http://dragongate-technologies.com/products.html.
[21]
Du, W., Wang, R., and Ning, P. 2005. An efficient scheme for authenticating public keys in sensor networks. In Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc'05). ACM Press, New York, NY, 58--67.
[22]
Ernst, M., Jung, M., Madlener, F., Huss, S., and Blümel, R. 2002. A reconfigurable system on chip implementation for elliptic curve cryptography over GF(2n). In Proceedings of Cryptographic Hardware and Embedded Systems (CHES). Springer, 381--399.
[23]
Everyready Battery Company. 2004. Engineering datasheet: Energizer No. X91. http://data.energizer.com/datasheets/library/primary/alkaline/energizer/consumer_oem/e91.pdf.
[24]
Frey, G. and Gangl, H. 1998. How to disguise an elliptic curve (Weil descent). In Proceedings of Elliptic Curve Cryptography (ECC'98).
[25]
Gaubatz, G., Kaps, J.-P., and Sunar, B. 2004. Public key cryptography in sensor networks—Revisited. In Proceedings of the 1st European Workshop on Security in Ad-hoc and Sensor Networks (ESAS'04). Lecture Notes in Computer Science, vol. 3313. Springer, 2--18.
[26]
Gaudry, P., Hess, F., and Smart, N. P. 2000. Constructive and destructive facets of Weil descent on elliptic curves. tech. rep. CSTR-00-016, Department of Computer Science, University of Bristol (Oct.).
[27]
Gay, D., Levis, P., von Behren, R., Welsh, M., Brewer, E., and Culler, D. 2003. The nesC language: a holistic approach to networked embedded systems. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. ACM, NY.
[28]
Gordon, D. M. 1993. Discrete logarithms in GF(P) using the number field sieve. SIAM J. Discret. Math. 6, 1, 124--138.
[29]
Gordon, D. M. 1998. A survey of fast exponentiation methods. J. Algori. 27, 1, 129--146.
[30]
Guajardo, J., Blümel, R., Krieger, U., and Paar, C. 2001. Efficient implementation of elliptic curve cryptosystems on the TI MSP430x33x family of microcontrollers. In Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography (PKC 2001). Springer, 365--382.
[31]
Gupta, V., Millard, M., Fung, S., Zhu, Y., Gura, N., Eberle, H., and Shantz, S. C. 2005. Sizzle: a standards-based end-to-end security architecture for the embedded Internet. In Proceedings of the 3rd IEEE International Conference on Pervasive Computing and Communications (PerCom). 247--256.
[32]
Gura, N., Patel, A., Wander, A., Eberle, H., and Shantz, S. C. 2004. Comparing elliptic curve cryptography and RSA on 8-bit CPUs. In Proceedings of the 6th International Workshop on Cryptographic Hardware and Embedded Systems, Boston, Massachusetts.
[33]
Handschuh, H. and Paillier, P. 2000. Smart card crypto-coprocessors for public-key cryptography. Lecture Notes in Computer Science, J.-J. Quisquater and B. Schneier, Eds. Springer-Verlag, 386--394.
[34]
Hankerson, D., Hernandez, J. L., and Menezes, A. 2001. Software implementation of elliptic curve cryptography over binary fields. Lecture Notes in Computer Science, vol. 1965.
[35]
Hasegawa, T., Nakajima, J., and Matsui, M. 1999. A small and fast software implementation of elliptic curve cryptosystems over GF(p) on a 16-Bit microcomputer. IEICE Trans. Fundamentals E82-A, 1, 98--106.
[36]
Hill, J., Szewczyk, R., Woo, A., Hollar, S., Culler, D. E., and Pister, K. S. J. 2000. System architecture directions for networked sensors. In Architectural Support for Programming Languages and Operating Systems. ACM SIGPLAN Notices, 35, 11(Nov.). 93--104.
[37]
IEEE Computer Society. 2000. IEEE P1363 Standard Specifications for Public-Key Cryptography.
[38]
Joye, M. and Yen, S.-M. 2000. Optimal left-to-right binary signed-digit recoding. IEEE Trans. Comput. 49, 7, 740--748.
[39]
Karlof, C., Sastry, N., and Wagner, D. 2004a. TinySec: A Link Layer Security Architecture for Wireless Sensor Networks. In Proceedings of the 2nd ACM Conference on Embedded Networked Sensor Systems, Baltimore, Maryland.
[40]
Karlof, C., Sastry, N., and Wagner, D. 2004b. TinySec: link layer security for tiny devices. http://www.cs.berkeley.edu/~nks/tinysec/.
[41]
Koblitz, N. 1987. Elliptic curve cryptosystems. Mathematics of Computation 48, 203--209.
[42]
Koblitz, N. 1992. CM-curves with good cryptographic properties. In Proceedings of Advances in Cryptology (CRYPTO'91). 279--287.
[43]
Kong, F. and Li, D. 2005. A note on signed binary window algorithm for elliptic curve cryptosystems. In Proceedings of the 4th International Conference on Cryptology and Network Security (CANS). 223--235.
[44]
Kottapalli, V. A., Kiremidjian, A. S., Lynch, J. P., Carryer, E., Kenny, T. W., Law, K. H., and Lei, Y. 2003. Two-tiered wireless sensor network architecture for structural health monitoring. Proceedings of the 10th Annual International Symposium on Smart Structures and Materials.
[45]
LaMacchia, B. A. and Odlyzko, A. M. 1991. Computation of discrete logarithms in prime fields. Lecture Notes in Computer Science, vol. 537, 616--618.
[46]
Lenstra, A. K. and Verheul, E. R. 1999. Selecting cryptographic key sizes. J. Cryptology.
[47]
López, J. and Dahab, R. 2000a. An overview of elliptic curve cryptography. Tech. rep., Institute of Computing, Sate University of Campinas, São Paulo, Brazil.
[48]
López, J. and Dahab, R. 2000b. High-speed software multiplication in F2m. Tech. rep., Institute of Computing, Sate University of Campinas, São Paulo, Brazil.
[49]
Malan, D. 2004. Crypto for tiny objects. Tech. rep. TR-04-04, Harvard University, Cambridge, MA. (Jan.).
[50]
Malan, D., Fulford-Jones, T., Welsh, M., and Moulton, S. 2004a. CodeBlue: an ad hoc sensor network infrastructure for emergency medical care. In Proceedings of the International Workshop on Wearable and Implantable Body Sensor Networks. London, United Kingdom.
[51]
Malan, D. J., Welsh, M., and Smith, M. D. 2004b. A public-key infrastructure for key distribution in TinyOS based on elliptic curve cryptography. In Proceedings of the 1st IEEE International Conference on Sensor and Ad Hoc Communications and Networks. Santa Clara, CA.
[52]
Marsaglia, G. 1994. The mother of all random generators. ftp://ftp.taygeta.com/pub/c/mother.c.
[53]
Menezes, A., Vanstone, S., and Okamoto, T. 1991. Reducing elliptic curve logarithms to logarithms in a finite field. In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing. ACM Press, 80--89.
[54]
Messerges, T. S., Cukier, J., Kevenaar, T. A. M., Puhl, L., Struik, R., and Callaway, E. 2003. A security design for a general purpose, self-organizing, multihop ad hoc wireless network. In Proceedings of the ACM Workshop on Security of Ad Hoc and Sensor Networks, George Mason University, Fairfax, VA.
[55]
Miller, V. 1986a. Uses of elliptic curves in cryptography. Lecture Notes in Computer Science. Springer-Verlag, Berlin, 417--426.
[56]
Miller, V. S. 1986b. Use of elliptic curves in cryptography. Lecture Notes in Computer Sciences. Springer-Verlag, New York, 417--426.
[57]
Möller, B. 2004. Fractional windows revisited: improved signed-digit representations for efficient exponentiation. In Information Security and Cryptology (ICISC), Springer, 137--153.
[58]
Montgomery, P. 1985. Modular multiplication without trial division. Math. Comput. 44, 170, 519--521.
[59]
National Institute of Standards and Technology. 1988. SKIPJACK and KEA Algorithm Specifications. Computer Security Division.
[60]
National Institute of Standards and Technology. 1994. Federal information processing standards publication 185. Escrowed Encryption Standard (EES).
[61]
National Institute of Standards and Technology. 1999. Recommended elliptic curves for federal government use. http://csrc.nist.gov/CryptoToolkit/dss/ecdsa/NISTReCur.pdf.
[62]
National Institute of Standards and Technology. 2003. Special publication 800-57: recommendation for key management.
[63]
NEST Challenge Architecture. 2002. http://www.tinyos.net/api.
[64]
Ning, P. and Liu, A. 2005. TinyECC: elliptic curve cryptography for sensor networks. http://discovery.csc.ncsu.edu/software/TinyECC/.
[65]
Okeya, K., Schmidt-Samoa, K., Spahn, C., and Takagi, T. 2004a. Lecture Notes in Computer Science, vol. 3152. Springer, Berlin, 123.
[66]
Okeya, K., Schmidt-Samoa, K., Spahn, C., and Takagi, T. 2004b. Signed binary representations revisited. Cryptology ePrint Archive, Report 2004/195. http://eprint.iacr.org/.
[67]
Paar, C. 1999. Implementation options for finite field arithmetic for elliptic curve cryptosystems. In Proceedings of the 3rd Workshop on Elliptic Curve Cryptography (ECC'99).
[68]
Perlman, R. 2003. Course Notes Computer Science 243, Harvard University.
[69]
Perrig, A., Stankovic, J., and Wagner, D. 2004. Security in wireless sensor networks. Comm. ACM 47, 6, 53--57.
[70]
Perrig, A., Szewczyk, R., Wen, V., Culler, D. E., and Tygar, J. D. 2001. SPINS: security protocols for sensor networks. In Mobile Computing and Networking. 189--199.
[71]
Rabin, M. 1979. Digitalized signatures and public-key functions as intractable as factorization. Tech. rep. MIT/LCS/TR-212, MIT.
[72]
Regehr, J. 2004. John Regehr's Stack Bounding Page. http://www.cs.utah.edu/~regehr/stacktool/.
[73]
Rochester Institute of Technology. 2005. CISCO University Research Program Project. http://www.ce.rit.edu/~fxheec/cisco_urp/docs/Main_ECC_Doc.htm.
[74]
Rosing, M. 1999. Implementing Elliptic Curve Cryptography. Manning Publications Co.
[75]
Schroeppel, R., Orman, H., O'Malley, S., and Spatscheck, O. 1995. Fast key exchange with elliptic curve systems. Lecture Notes in Computer Science, vol. 963.
[76]
Seo, S. C., Kim, H. C., and Ramakrishna, R. S. 2006. A new security protocol based on elliptic curve cryptosystems for security wireless sensor networks. In Proceedings of the 2nd International Workshop on Security in Ubiquitous Computing Systems (SECUBIQ 2006).
[77]
Shamus Software Ltd. 2004. Multiprecision integer and rational arithmetic C/C++ Library. http://indigo.ie/~mscott/#Elliptic.
[78]
Shnayder, V., Hempstead, M., Rong Chen, B., Allen, G. W., and Welsh, M. 2004. Simulating the power consumption of large-scale sensor network applications. In Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys'04). ACM Press, New York, 188--200.
[79]
Silverman, J. and Suzuki, J. 1998. Elliptic curve discrete logarithms and the index calculus. In Proceedings of the International Conference on the Theory and Application of Cryptology (ASIACRYPT).
[80]
Solinas, J. 1999. Generalized Mersenne numbers. Tech. Rep. CORR-39, University of Waterloo.
[81]
Solinas, J. A. 1997. An improved algorithm for arithmetic on a family of elliptic curves. In Proceedings of the Advances in Cryptology (CRYPTO'97). 357--371.
[82]
Texas Instruments. 2007. 2.4 GHz IEEE 802.15.4 / ZigBee-ready RF transceiver (Rev. B).
[83]
Wander, A. S., Gura, N., Eberle, H., Gupta, V., and Shantz, S. C. 2005. Energy analysis of public-key cryptography for wireless sensor networks. In Proceedings of the 3rd IEEE International Conference on Pervasive Computing and Communications (PERCOM'05). IEEE Computer Society, Washington, DC, 324--328.
[84]
Wang, H. and Li, Q. 2006. Elliptic curve cryptography based access control in sensor networks. Int. J. Secur. Net. 1.
[85]
Watro, R. 2003. Lightweight security for wireless networks of embedded systems. http://www.is.bbn.com/projects/lws-nest/bbn_nest_apr_03.ppt.
[86]
Watro, R., Kong, D., fen Cuti, S., Gardiner, C., Lynn, C., and Kruus, P. 2004. TinyPK: Securing sensor networks with public key technology. In Proceedings of the 2nd ACM Workshop on Security of Ad Hoc and Sensor Networks (SASN'04). ACM Press, New York, NY, 59--64.
[87]
Weimerskirch, A., Paar, C., and Shantz, S. C. 2001. Elliptic curve cryptography on a Palm OS device. In Proceedings of the 6th Australasian Conference on Information Security and Privacy. Sydney, Australia.
[88]
Wood, C. 2004. libecc. http://libecc.sourceforge.net/.
[89]
Woodbury, A. D. 2001. Efficient algorithms for elliptic curve cryptosystems on embedded systems. http://www.wpi.edu/Pubs/ETD/Available/etd-1001101-195321/unrestricted/woodbury.pdf.
[90]
Woodbury, A. D., Bailey, D. V., and Paar, C. 2000. Elliptic curve cryptography on smart cards without coprocessors. In Proceedings of the 4th Smart Card Research and Advanced Applications Conference (CARDIS 2000). Bristol, UK.
[91]
Zaroliagis, C. 2004. ECC-LIB: A library for elliptic curve cryptography. http://www.ceid.upatras.gr/faculty/zaro/software/ecc-lib/.
[92]
ZigBee Alliance. 2004. http://www.zigbee.org/.

Cited By

View all
  • (2024)Med-tech device security through advanced server cryptographyInternational Journal of Information Technology10.1007/s41870-024-02339-217:2(1015-1022)Online publication date: 20-Dec-2024
  • (2023)ECC-reliant secure authentication protocol for cloud server and smart devices in IoTThe Journal of Supercomputing10.1007/s11227-023-05135-079:11(12191-12218)Online publication date: 7-Mar-2023
  • (2022)A Novel Secure Authentication Protocol for IoT and Cloud ServersWireless Communications & Mobile Computing10.1155/2022/77075432022Online publication date: 1-Jan-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Sensor Networks
ACM Transactions on Sensor Networks  Volume 4, Issue 4
August 2008
295 pages
ISSN:1550-4859
EISSN:1550-4867
DOI:10.1145/1387663
Issue’s Table of Contents
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

Publication History

Published: 04 September 2008
Accepted: 01 November 2007
Revised: 01 July 2007
Received: 01 August 2006
Published in TOSN Volume 4, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. DLP
  2. Diffie-Hellman
  3. ECC
  4. ECDLP
  5. MICA2
  6. TinyOS
  7. TinySec
  8. elliptic curve cryptography
  9. motes
  10. sensor networks

Qualifiers

  • Research-article
  • Research
  • Refereed

Funding Sources

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)31
  • Downloads (Last 6 weeks)1
Reflects downloads up to 05 Mar 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Med-tech device security through advanced server cryptographyInternational Journal of Information Technology10.1007/s41870-024-02339-217:2(1015-1022)Online publication date: 20-Dec-2024
  • (2023)ECC-reliant secure authentication protocol for cloud server and smart devices in IoTThe Journal of Supercomputing10.1007/s11227-023-05135-079:11(12191-12218)Online publication date: 7-Mar-2023
  • (2022)A Novel Secure Authentication Protocol for IoT and Cloud ServersWireless Communications & Mobile Computing10.1155/2022/77075432022Online publication date: 1-Jan-2022
  • (2022)ECC-Based Authenticated Key Exchange Protocol for Fog-Based IoT NetworksSecurity and Communication Networks10.1155/2022/72648032022Online publication date: 1-Jan-2022
  • (2022)Secure and practical access control mechanism for WSN with node privacyJournal of King Saud University - Computer and Information Sciences10.1016/j.jksuci.2020.05.01034:6(3630-3646)Online publication date: Jun-2022
  • (2022)Robust encryption method based on AES-CBC using elliptic curves Diffie–Hellman to secure data in wireless sensor networksWireless Networks10.1007/s11276-022-02903-328:3(991-1001)Online publication date: 1-Apr-2022
  • (2020)Enhancing the Security and Efficiency of Resource Constraint Devices in IoT2020 International Conference on Industry 4.0 Technology (I4Tech)10.1109/I4Tech48345.2020.9102639(163-166)Online publication date: Feb-2020
  • (2020)FLAT: Federated Lightweight Authentication for the Internet of ThingsAd Hoc Networks10.1016/j.adhoc.2020.102253(102253)Online publication date: Jun-2020
  • (2020)Implementation of Public-Key Infrastructure for Smart Parking System Using MQTT ProtocolInventive Communication and Computational Technologies10.1007/978-981-15-0146-3_99(1029-1037)Online publication date: 30-Jan-2020
  • (2019)Scyther Validated Session Key Establishment in IoT2019 5th International Conference on Advanced Computing & Communication Systems (ICACCS)10.1109/ICACCS.2019.8728318(370-373)Online publication date: Mar-2019
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media