Implementing public-key infrastructure for sensor networks

ABSTRACT

We present a critical evaluation of the first known implementation of elliptic curve cryptography over F_2p 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: Leonard Adleman, A subexponential algorithm for the discrete logarithm problem with applications to cryptography, Proceedings of the 20th Annual Symposium on Foundations of Computer Science (sfcs 1979), p.55-60, October 29-31, 1979
• 2: Ortal Araz , Hairong Qi, Load-balanced key establishment methodologies in wireless sensor networks, International Journal of Security and Networks, v.1 n.3/4, p.158-166, December 2006 [doi>10.1504/IJSN.2006.011775]
• 3: Paul Barrett, Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor, Proceedings on Advances in cryptology---CRYPTO '86, p.311-323, January 1987, Santa Barbara, California, United States
• 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: Ian F. Blake , G. Seroussi , N. P. Smart, Elliptic curves in cryptography, Cambridge University Press, New York, NY, 1999
• 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: Michael Brown , Donny Cheung , Darrel Hankerson , Julio Lopez Hernandez , Michael Kirkup , Alfred Menezes, PGP in constrained wireless devices, Proceedings of the 9th conference on USENIX Security Symposium, p.19-19, August 14-17, 2000, Denver, Colorado
• 11: Alberto Cerpa , Jeremy Elson , Deborah Estrin , Lewis Girod , Michael Hamilton , Jerry Zhao, Habitat monitoring: application driver for wireless communications technology, ACM SIGCOMM Computer Communication Review, v.31 n.2 supplement, April 2001 [doi>10.1145/844193.844196]
• 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: Henri Cohen , Atsuko Miyaji , Takatoshi Ono, Efficient Elliptic Curve Exponentiation Using Mixed Coordinates, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.51-65, October 18-22, 1998
• 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: Jing Deng , Richard Han , Shivakant Mishra, Secure code distribution in dynamically programmable wireless sensor networks, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127822]
• 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: Whitfield Diffie , Paul C. Van Oorschot , Michael J. Wiener, Authentication and authenticated key exchanges, Designs, Codes and Cryptography, v.2 n.2, p.107-125, June 1992 [doi>10.1007/BF00124891]
• 20: Dragongate Technologies Limited. 2003. jBorZoi 0.9. http://dragongate-technologies.com/products.html.
• 21: Wenliang Du , Ronghua Wang , Peng Ning, An efficient scheme for authenticating public keys in sensor networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062698]
• 22: M. Ernst , M. Jung , F. Madlener , S. Huss , Rainer Blümel, A Reconfigurable System on Chip Implementation for Elliptic Curve Cryptography over GF(2n), Revised Papers from the 4th International Workshop on Cryptographic Hardware and Embedded Systems, p.381-399, August 13-15, 2002
• 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: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 28: Daniel M. Gordon, Discrete logarithms in GF(P) using the number field sieve, SIAM Journal on Discrete Mathematics, v.6 n.1, p.124-138, Feb. 1993 [doi>10.1137/0406010]
• 29: Daniel M. Gordon, A survey of fast exponentiation methods, Journal of Algorithms, v.27 n.1, p.129-146, April 1998 [doi>10.1006/jagm.1997.0913]
• 30: Jorge Guajardo , Rainer Blümel , Uwe Krieger , Christof Paar, Efficient Implementation of Elliptic Curve Cryptosystems on the TI MSP 430x33x Family of Microcontrollers, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.365-382, February 13-15, 2001
• 31: Vipul Gupta , Matthew Millard , Stephen Fung , Yu Zhu , Nils Gura , Hans Eberle , Sheueling Chang Shantz, Sizzle: A Standards-Based End-to-End Security Architecture for the Embedded Internet (Best Paper), Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications, p.247-256, March 08-12, 2005 [doi>10.1109/PERCOM.2005.41]
• 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: Helena Handschuh , Pascal Paillier, Smart Card Crypto-Coprocessors for Public-Key Cryptography, Proceedings of the The International Conference on Smart Card Research and Applications, p.372-379, September 14-16, 1998
• 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: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, ACM SIGPLAN Notices, v.35 n.11, p.93-104, Nov. 2000 [doi>10.1145/356989.356998]
• 37: IEEE Computer Society. 2000. IEEE P1363 Standard Specifications for Public-Key Cryptography.
• 38: Marc Joye , Sung-Ming Yen, Optimal Left-to-Right Binary Signed-Digit Recoding, IEEE Transactions on Computers, v.49 n.7, p.740-748, July 2000 [doi>10.1109/12.863044]
• 39: Chris Karlof , Naveen Sastry , David Wagner, TinySec: a link layer security architecture for wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031515]
• 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: Neal Koblitz, CM-Curves with Good Cryptographic Properties, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.279-287, August 11-15, 1991
• 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 F_2^m. 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: Alfred Menezes , Scott Vanstone , Tatsuaki Okamoto, Reducing elliptic curve logarithms to logarithms in a finite field, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.80-89, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103434]
• 54: Thomas S. Messerges , Johnas Cukier , Tom A. M. Kevenaar , Larry Puhl , René Struik , Ed Callaway, A security design for a general purpose, self-organizing, multihop ad hoc wireless network, Proceedings of the 1st ACM workshop on Security of ad hoc and sensor networks, October 31, 2003, Fairfax, Virginia [doi>10.1145/986858.986860]
• 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: Adrian Perrig , John Stankovic , David Wagner, Security in wireless sensor networks, Communications of the ACM, v.47 n.6, June 2004 [doi>10.1145/990680.990707]
• 70: Adrian Perrig , Robert Szewczyk , Victor Wen , David Culler , J. D. Tygar, SPINS: security protocols for sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.189-199, July 2001, Rome, Italy [doi>10.1145/381677.381696]
• 71: M. O. Rabin, DIGITALIZED SIGNATURES AND PUBLIC-KEY FUNCTIONS AS INTRACTABLE AS FACTORIZATION, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 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: Michael Rosing, Implementing elliptic curve cryptography, Manning Publications Co., Greenwich, CT, 1999
• 75: Richard Schroeppel , Hilarie Orman , Sean W. O'Malley , Oliver Spatscheck, Fast Key Exchange with Elliptic Curve Systems, Proceedings of the 15th Annual International Cryptology Conference on Advances in Cryptology, p.43-56, August 27-31, 1995
• 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: Victor Shnayder , Mark Hempstead , Bor-rong Chen , Geoff Werner Allen , Matt Welsh, Simulating the power consumption of large-scale sensor network applications, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031518]
• 79: Joseph H. Silverman , Joe Suzuki, Elliptic Curve Discrete Logarithms and the Index Calculus, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.110-125, October 18-22, 1998
• 80: Solinas, J. 1999. Generalized Mersenne numbers. Tech. Rep. CORR-39, University of Waterloo.
• 81: Jerome A. Solinas, An Improved Algorithm for Arithmetic on a Family of Elliptic Curves, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.357-371, August 17-21, 1997
• 82: Texas Instruments. 2007. 2.4 GHz IEEE 802.15.4 / ZigBee-ready RF transceiver (Rev. B).
• 83: Arvinderpal S. Wander , Nils Gura , Hans Eberle , Vipul Gupta , Sheueling Chang Shantz, Energy Analysis of Public-Key Cryptography for Wireless Sensor Networks, Proceedings of the Third IEEE International Conference on Pervasive Computing and Communications, p.324-328, March 08-12, 2005 [doi>10.1109/PERCOM.2005.18]
• 84: Haodong Wang , Bo Sheng , Qun Li, Elliptic curve cryptography-based access control in sensor networks, International Journal of Security and Networks, v.1 n.3/4, p.127-137, December 2006 [doi>10.1504/IJSN.2006.011772]
• 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: Ronald Watro , Derrick Kong , Sue-fen Cuti , Charles Gardiner , Charles Lynn , Peter Kruus, TinyPK: securing sensor networks with public key technology, Proceedings of the 2nd ACM workshop on Security of ad hoc and sensor networks, October 25-25, 2004, Washington DC, USA [doi>10.1145/1029102.1029113]
• 87: André Weimerskirch , Christof Paar , Sheueling Chang Shantz, Elliptic Curve Cryptography on a Palm OS Device, Proceedings of the 6th Australasian Conference on Information Security and Privacy, p.502-513, July 11-13, 2001
• 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: Adam D. Woodbury , Daniel V. Bailey , Christof Paar, Elliptic curve cryptography on smart cards without coprocessors, Proceedings of the fourth working conference on smart card research and advanced applications on Smart card research and advanced applications, p.71-92, February 2001, Bristol, United Kingdom
• 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/.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Network operating systems
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Security

Keywords:
DLP, Diffie-Hellman, ECC, ECDLP, MICA2, TinyOS, TinySec, elliptic curve cryptography, motes, sensor networks