Encryption overhead in embedded systems and sensor network nodes: modeling and analysis

ABSTRACT

Recent research in sensor networks has raised issues of security for small embedded devices. Security concerns are motivated by the deployment of a large number of sensory devices in the field. Limitations in processing power, battery life, communication bandwidth and memory constrain the applicability of existing cryptography standards for small embedded devices. A mismatch between wide arithmetic for security (32 bit word operations) and embedded data bus widths (often only 8 or 16 bits) combined with lack of certain operations (e.g., multiply) in the ISA present other challenges.This paper offers two contributions. First, a survey investigating the computational requirements for e a number of common cryptographic algorithms and embedded architectures is presented. The objective of this work is to cover a wide class of commonly used encryption algorithms and to determine the impact of embedded architectures on their performance. This will help designers predict a system's performance for cryptographic tasks. Second, methods to derive the computational overhead of embedded architectures in general for encryption algorithms are developed. This allows one to project computational limitations and determine the threshold of feasible encryption schemes under a set of the constraints for an embedded architecture.Experimental measurements indicate uniform cryptographic cost for each encryption class and each architecture class and negligible impact of caches. RC4 is shown to outperform RC5 for the Atmega platform. But when message authentication is required in addition to encryption, hash or block ciphers, such as RC5, have the advantage of providing support for both authentication and encryption. The analytical model allows to assess the impact of arbitrary embedded architectures as a multi-variant function for each encryption scheme. Overall, our results are not only valuable to assess the feasibility of encryption schemes for existing embedded architectures, they also extend to assess the feasibility of encryption methods for new algorithms and architectures for sensor systems.

REFERENCES

• 1: R. Rivest, "The RC5 encryption algorithm", in Proceedings of the 1994 Leuven Workshop on Fast Software Encryption, pages 86--96, Springer-Verlag, 1995, http://citeseer.nj.nec.com/rivest95rc.html
• 2: B. Schneier, "Applied Cryptography", Second edition, John Wiley & Sons, 1996.
• 3: R. . Rivest, "The MD5 Message-Digest Algorithm", IETF RFC 1321, April 1992. ftp://ftp.rfc-editor.org/in-notes/rfc1321.txt
• 4: D. Eastlake and P. Jones. "US Secure Hash Algorithm 1 (SHA1)",IETF RFC 3174, Sept. 2001. ftp://ftp.rfc-editor.org/in-notes/rfc3174.txt
• 5: Sun microsystems, "UltraSPARCTM II Microprocessor", http://www.sun.com/processors/UltraSPARC-II/PBN-0140.pdf
• 6: M. Brown, D. Cheung, D. Hankerson, J. Hernandez, M. Kirkup, A. Menezes, "PGP in Constrained Wireless Devices", in Proceedings of the 9th USENIX Security Symposium, Denver Colorado, pp. 247--261, Aug. 2000.
• 7: D. Carman, P. Kruus, B. Matt, "Constraints and approaches for distributed sensor network security", NAI Labs technical report #00-010, Sept 2000, http://download.nai.com/products/media/nai/zip/nailabs-report-00-010-final.zip.
• 8: W. Dai, "Crypto++ 4.0 Benchmarks", http://www.eskimo.com/~weidai/benchmarks.html
• 9: C. Madson, "The Use of HMAC-SHA-1-96 within ESP and AH", IETF RFC 2404, Nov. 1998, http://www.ietf.org/rfc/rfc2404.txt
• 10: S. Kent and R. Atkinson, "Security Architecture for the Internet Protocol", IETF RFC 2401, Nov. 1998, ftp://ftp.rfc-editor.org/in-notes/rfc2401.txt
• 11: The International PGP Home Page, http://www.pgpi.org
• 12: Adrian Perrig , Robert Szewczyk , Victor Wen , David Culler , J. D. Tygar, SPINS: security protocols for sensor netowrks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.189-199, July 2001, Rome, Italy [doi>10.1145/381677.381696]
• 13: "LAN MAN Standards of the IEEE Computer Society. Wireless LAN medium access control (MAC) and physical layer(PHY) specification IEEE Standaard 802.11, 1997 Edition," 1997.
• 14: O. S. Elkeelany, M. M. Matalgah, K. P. Sheikh, M. Thaker, G. Chaudhry, D. Medhi, and J. Qaddour, "Performance Analysis of IPSec Protocol: Encryption and Authentication", IEEE Communications Conference (ICC 2002), pp. 1164--1168, 2002.
• 15: C. Schnorr, Efficient signature generation by smart cards, Journal of Cryptology, vol. 4, pages 161--174, 1991.
• 16: J. Burke, J. McDonald, T. Austin, "Architectural support for fast symmetric-key cryptography", ASPLOS-IX, 2000, pp. 178--189.
• 17: Phillip Rogaway , Don Coppersmith, A Software-Optimised Encryption Algorithm, Fast Software Encryption, Cambridge Security Workshop, p.56-63, December 09-11, 1993
• 18: D. Wheeler, M. Needham, "TEA, a Tiny Encryption Algorithm", Fast Software Encryption: Second International Workshop", Springer LNCS, Vol. 1008, 1994, pp. 14--16.
• 19: Gideon Yuval, Reinventing the Travois: Encryption/MAC in 30 ROM Bytes, Proceedings of the 4th International Workshop on Fast Software Encryption, p.205-209, January 20-22, 1997
• 20: Chenghuai Lu , Andre L. M. dos Santos , Francisco R. Pimentel, Implementation of fast RSA key generation on smart cards, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain [doi>10.1145/508791.508837]
• 21: Joseph D. Touch, Performance analysis of MD5, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.77-86, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 22: William Freeman , Ethan Miller, An Experimental Analysis of Cryptographic Overhead in Performance-Critical Systems, Proceedings of the 7th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, p.348, March 24-28, 1999

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Standards (e.g., DES, PGP, RSA)

General Terms:
Measurement

Keywords:
embedded systems, encryption, security, sensor networks