Analyzing and Modeling Encryption Overhead for Sensor Network Nodes Prasanth Ganesan, Ramnath Venugopalan, Pushkin Peddabachagari, Alexander Dean, Frank Mueller, Mihail Sichitiu Center for Embedded Systems Research Departments of Electrical and Computer Engineering / Computer Science North Carolina State University, Raleigh, NC 27695 phone: (919) 515-7889, fax: -7925 {pganesa, rvenugo, ppeddab, agdean, mlsichit, mueller}@ncsu.edu ABSTRACT Recent research in sensor networks has raised security issues 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 a number of popular 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 Motes Atmega platform contrary to the choice of RC5 for the Motes project, a choice driven in large by memory constraints. 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. Categories and Subject Descriptors C.2.1 [Computer-Communication Networks] Network Architecture and Design - Wireless communication C.3 Special-Purpose and Application-Based Systems - Real-time and embedded systems C.4 Performance of Systems - Modeling techniques D.2.8 [Software Engineering] Metrics – Performance measures E.3 Data Encryption General Terms Security, Performance, Measurement Keywords Sensor networks, encryption overhead, analysis, model, embedded systems. 1. INTRODUCTION Security is a well-established field for general-purpose computing. Security mechanisms address computing services, such as authentication for user admission, intrusion detection and prevention as well as counter-measures for other forms of attacks (e.g., denial of service) and data protection in storage, in e-mails or to provide secure transactions. This paper focuses on the last aspect, namely, data protection mechanisms provided by encryption techniques. The objective of this paper is to study the impact of a variety of encryption techniques for embedded architectures instead of general-purpose processors. Embedded systems have a long history in the context of transaction processing, for example, cash transactions at teller machines. However, security measures have typically focused on physical access restrictions as well as software measures to disable a device if attempts to tamper with it are suspected. Recent developments have changed this focus. On the one side, embedded architectures provide a wider range of processing power, which allows more sophisticated security responses, in particular for high-end embedded systems. On the other side, new application areas in embedded systems require secure communication. For example, recent work in sensor networks includes data encryption considerations [12]. Sensor networks allow the collection of data from low-end sensor nodes in the field. This data is communicated over non-secure channels, such as radio frequencies, through routers (in the latest design) and, ultimately, to a base station for further processing and decision making. Applications range from battlefield surveillance over data collection to study environmental impacts to medical observation. Beyond sensor networks, embedded processors are increasingly deployed with network connections, such as in PDAs with wireless communication (802.11b), e.g., for the Ipaq Pocket PCs used in this study [23]. The objective of data encryption in 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. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. WSNA’03, September 19, 2003, San Diego, California, USA. Copyright 2003 ACM 1-58113-764-8/03/0009…$5.00. 151such settings is to ensure that data can only be interpreted by authorized recipients. In this paper, we assess the feasibility of different encryption schemes for a range of embedded architectures. We determine architectural impacts on the performance of encryption as well as algorithmic properties of the selected encryption schemes. The particular embedded platforms were chosen to cover a wide range of embedded devices. Measurements were obtained for six different architectures, ranging in word size from 8 (Atmel AVR) over 16 (Mitsubishi M16C) to 32-bit width (StrongARM, XScale) to cover low-end, medium and high-end embedded processors, respectively. As a baseline for comparison, one general-purpose architecture (SPARC) was also included as a reference point. Future encryption schemes need only be evaluated on reference architectures to derive the overhead for other architectures. Other reference architectures are those with differing ISA support for encryption, as detailed in the evaluation. The analysis takes