We review related work that deals with security issues in a ubiquitous computing environment. We also review work on cryptographic protocols for low-end devices.
Fox and Gribble present a security protocol that provides secure access to application-level proxy services [10]. Their protocol is designed to interact with a proxy to Kerberos and to facilitate porting services that rely on Kerberos to wireless devices. The work of Patel and Crowcroft focuses on security solutions for mobile user devices [27]. Unfortunately, their work uses asymmetric cryptography and is hence too expensive for the environments we envision. The work of Czerwinski et al.also relies on asymmetric cryptography for authentication [4]. Stajano and Anderson discuss the issues of bootstrapping security devices [39]. Their solution requires physical contact of the new device with a master device to imprint the trusted and secret information. Zhou and Hass propose to secure ad-hoc networks using asymmetric cryptography [45]. Carman, Kruus, and Matt analyze a wide variety of approaches for key agreement and key distribution in sensor networks [3]. They analyze the overhead of these protocols on a variety of hardware platforms.
A number of researchers investigate the problem to provide cryptographic services in low-end devices. We first discuss the hardware efforts, followed by the algorithmic work on cryptography. Several systems integrate cryptographic primitives with low cost microcontrollers. Examples of such systems are secure AVR controllers [1], the Fortezza government standard, and the Dallas iButton [7]. These systems support primitives for public key encryption, with instructions for modular exponentiation, and attempt to zeroize their memory if tampering is detected. However, these devices were designed for different applications, and are not meant as low-power devices.
On the cryptographic algorithm front for low-end devices the majority of research focuses on symmetric cryptography. A notable exception is the work of Modadugu, Boneh, and Kim which offload the heavy computation for finding an RSA key pair to untrusted servers [24].
Symmetric encryption algorithms seem to be inherently well suited for low-end devices, due to their relatively low overhead. In practice, however, low-end microprocessors are only 4-bit or 8-bit, and do not provide (efficient) multiplication or variable rotate/shift instructions. Hence many symmetric ciphers are too expensive to implement on our target platform. Even though one of the goals for the Advanced Encryption Standard (AES) [25] was efficiency and small code size on low-end processors, the chosen Rijndael block cipher [6] is nevertheless too expensive for our platform. Depending on the implementation, AES was either too big or too slow for our application. Due to our severely limited code size, we chose to use RC5 by Ron Rivest [33]. Algorithms such as TEA by Wheeler and Needham [43] or TREYFER by Yuval [44] would be smaller alternatives, but we still choose RC5 to attain high security because the security of these other ciphers is not yet thoroughly analyzed.