Comparison of innovative signature algorithms for WSNs

ABSTRACT

For many foreseen applications of Wireless Sensor Networks (WSN) - for example monitoring the structural health of a bridge - message integrity is a crucial requirement. Usually, security services such as message integrity are realized by symmetric cryptography only, because asymmetric cryptography is often stated as impracticable for WSN. However, the proposed solutions for symmetric key establishment introduce a significant computation, storage, and - most important - communication overhead. Digital signatures and key-exchange based on asymmetric algorithms would be very valuable though. In the literature nearly only RSA and ECC are implemented and compared for sensor nodes, though there exist a variety of innovative asymmetric algorithms. To close this gap, we investigated the efficiency and suitability of digital signature algorithms based on innovative asymmetric primitives for WSN. We chose XTR-DSA and NTRUSign and implemented both (as well as ECDSA) for MICAz motes.

REFERENCES

• 1: Digital Signature Standard (DSS). Federal Information Processing Standards (FIPS) Publication 186, National Institute of Standards and Technology (NIST), May 1994.
• 2: A. A. Karatsuba and Y. Ofman. Multiplication of Many-Digital Numbers by Automatic Computers. Soviet Physics-Doklad, 7:595--596, 1963.
• 3: Haowen Chan , Adrian Perrig , Dawn Song, Random Key Predistribution Schemes for Sensor Networks, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.197, May 11-14, 2003
• 4: P. G. Comba, Exponentiation cryptosystems on the IBM PC, IBM Systems Journal, v.29 n.4, p.526-538, 1990
• 5: Atmel Corporation. AVR Studio, 4.12.490, Service Pack 3. http://www.atmel.com/dyn/products/tools_card.asp?tool_id=2725.
• 6: Crossbow Technology Inc. MPR-MIB Users Manual - Revision A. available via http://www.xbow.com/Support/Support_pdf_files/MPR-MIB_Series_Users_Manual.pdf, June 2007.
• 7: B. Driessen. Efficient Embedded Implementation of Security Solutions for ad-hoc Networks. Master's thesis, Ruhr-University Bochum, http://www.crypto.rub.de/theses.html, September 2007.
• 8: Craig Gentry , Jakob Jonsson , Jacques Stern , Michael Szydlo, Cryptanalysis of the NTRU Signature Scheme (NSS) from Eurocrypt 2001, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.1-20, December 09-13, 2001
• 9: N. Gura, A. Patel, A. Wander, H. Eberle, and S. C. Shantz. Elliptic curve cryptography and RSA on 8-bit CPUs. In Proceedings of Workshop on Crpytographic Hardware and Embedded Systems (CHES 2004), 6th International Workshop, pages 119 --132, 2004.
• 10: N. Gura, A. Patel, A. Wander, H. Eberle, and S. C. Shantz. Comparing Elliptic Curve Cryptography and RSA on 8-bit CPUs. Proceedings of Workshop on Cryptographic Hardware and Embedded Systems (CHES 2004), 6th International Workshop, pages 119--132, 2004.
• 11: Darrel Hankerson , Alfred J. Menezes , Scott Vanstone, Guide to Elliptic Curve Cryptography, Springer-Verlag New York, Inc., Secaucus, NJ, 2003
• 12: J. Hoffstein, N. Howgrave-Graham, J. Pipher, J. H. Silverman, and W. Whyte. NTRUSign: Digital signatures using the NTRU lattice. In Proceedings of the RSA conference, 2003.
• 13: Jeffrey Hoffstein , Jill Pipher , Joseph H. Silverman, NSS: An NTRU Lattice-Based Signature Scheme, Proceedings of the International Conference on the Theory and Application of Cryptographic Techniques: Advances in Cryptology, p.211-228, May 06-10, 2001
• 14: Joengmin Hwang , Yongdae Kim, Revisiting random key pre-distribution schemes for wireless sensor networks, 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.1029111]
• 15: J. Hoffstein and N. Howgrave-Graham and J. Pipher and J. H. Silverman and W. Whyte. Performance Improvements and a Baseline Parameter Generation Algorithm for NTRUSign, 2005.
• 16: D. Johnson and A. Menezes. The ellipcit curve digital signature algorithm (ECDSA), 1999.
• 17: Çetin Kaya Koç , Tolga Acar , Burton S. Kaliski, Jr., Analyzing and Comparing Montgomery Multiplication Algorithms, IEEE Micro, v.16 n.3, p.26-33, June 1996 [doi>10.1109/40.502403]
• 18: Arjen K. Lenstra , Eric R. Verheul, The XTR Public Key System, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.1-19, August 20-24, 2000
• 19: Arjen K. Lenstra , Eric R. Verheul, The XTR Public Key System, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.1-19, August 20-24, 2000
• 20: A. Liu and P. Ning. TinyECC: A Configurable Library for Elliptic Curve Cryptography in Wireless Sensor Networks. Technical Report TR-2007-36, North Carolina State University, Department of Computer Science, November 2007.
• 21: Donggang Liu , Peng Ning, Location-based pairwise key establishments for static sensor networks, Proceedings of the 1st ACM workshop on Security of ad hoc and sensor networks, October 31, 2003, Fairfax, Virginia [doi>10.1145/986858.986869]
• 22: Alfred J. Menezes , Scott A. Vanstone , Paul C. Van Oorschot, Handbook of Applied Cryptography, CRC Press, Inc., Boca Raton, FL, 1996
• 23: Victor S Miller, Use of elliptic curves in cryptography, Lecture notes in computer sciences; 218 on Advances in cryptology---CRYPTO 85, p.417-426, June 1986, Santa Barbara, California, United States
• 24: N/A. DSTU X9.98 Draft 9 - Lattice-Based Polynomial Public Key Establishment Algorithm for the Financial Services Industries. Technical report, Accredited Standards Commitee X9 Incorporated, 22. 2007.
• 25: Certicom Research. SEC 2: Recommended Elliptic Curve Domain Parameters. Standards for Efficient Cryptography Version 1.0, 2000.
• 26: R. L. Rivest , A. Shamir , L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, v.21 n.2, p.120-126, Feb. 1978 [doi>10.1145/359340.359342]
• 27: J. H. Silverman. High Speed Multiplication of (Truncated) Polynomials. Technical Report 10, NTRU, 1999.
• 28: Martijn Stam , Arjen K. Lenstra, Speeding Up XTR, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.125-143, December 09-13, 2001
• 29: L. Uhsadel. Comparison of Low-Power Public Key Cryptography on MICAz 8-bit Micro Controllers. Master's thesis, Ruhr-University Bochum, 2007.
• 30: Leif Uhsadel, Axel Poschmann, and Christof Paar. Enabling Full-Size Public-key Algorithms on 8-bit Sensor Nodes. In Proceedings of ESAS 2007, volume 4572 of LNCS, pages 73--86, 2007.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

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

General Terms:
Algorithms, Measurement, Performance, Security