Full paper: Postscript, PS.GZ, PDF

Evaluation

 

We evaluate the implementation of our protocols in terms of code size, RAM size, and processor and communication overheads.

 

Version Total Size MAC Encrypt Key Setup

Smallest 1594 480 392 622

Fastest 1826 596 508 622

Original 2674 1210 802 686

 

Code size Table 2 shows the code size of three implementations of crypto routines in TinyOS. The smallest version of the crypto routines occupies about 20% of the available code space. Additionally, the implementation of $\mu$TESLAprotocol uses another 574 bytes. Together, the crypto library and the protocol implementation consume about 2 KBytes of program memory, which is quite acceptable in most applications.

While optimizing the crypto library, it became apparent that at this scale it is important to identify reusable routines to minimize the call setup costs. For example, OpenSSL implements the RC5 encryption routine as a function. In the case of a sensor network it became clear that the costs of call setup and return outweigh the costs of the RC5 itself. Thus, we made the decision to implement RC5 encryption as a macro, and only expose interfaces to the MAC and CTR-ENCRYPT functions.

Performance The performance of the cryptographic primitives is adequate for the bandwidth supported by the current generation of network sensors. The RC5 key setup requires $8000$ instruction cycles ($4$ ms, the time required to send $40$ bits). Encryption of a $8$-byte block $120$ instruction cycles. Our sensors currently support a maximum throughput of twenty 30-byte messages per second, with the microcontroller being idle for about 50% of the time [16]. Assuming a single key setup, one MAC operation, and one encryption operation, our code is still able to encrypt and sign every message.

We infer the time required for $\mu$TESLAbased on static analysis of the protocol. As stated in the previous section, $\mu$TESLAhas a disclosure interval of 2. The stringent buffering requirements also dictate that the we cannot drop more that one key disclosure beacon. Thus, we require a maximum of two key setup operations and two CTR encryptions to check the validity of a disclosed TESLA key. Additionally, we perform up to two key setup operations, two CTR encryptions, and up to four MAC operation to check an integrity of a TESLA message. That gives an upper bound of 17,800 $\mu$s for checking the buffered messages. This amount of work is easily performed on our processor. In fact, the limiting factor on the bandwidth of authenticated broadcast traffic is the amount of buffering we can dedicate on individual sensor nodes. Table 3 shows the amount of RAM that the security modules require. We configure the $\mu$TESLAprotocol with 4 messages: the disclosure interval dictates a buffer space of 3 messages just for key disclosure, and we need an additional buffer to use this primitive in a more flexible way. Despite allocating minimal amounts of memory to $\mu$TESLA, the protocols we implement consume nearly half of the available RAM, and we do not feel that we can afford to dedicate any more RAM to security related tasks.

 

Module RAM size (bytes)

RC5 80

TESLA 120

Encrypt/MAC 20

 

Energy costs Finally we examine the energy costs of security mechanisms. Most of the energy costs will come from extra transmissions required by the protocols. Since we use a stream cipher for encryption, the size of encrypted message is the same as the size of the plaintext. The MAC uses 8 bytes of every 30 byte message, however, the MAC also achieves integrity so we do not need to use other message integrity mechanisms (e.g. a 16-bit CRC). Thus, encrypting and signing messages imposes an overhead of 6 bytes per message over an unencrypted message with integrity checking, or about 20 %. Figure 6 expresses the costs of computation and communication in terms of energy required for the SNEPprotocol.

The messages broadcast using $\mu$TESLAhave the same costs of authentication per message. Additionally, $\mu$TESLArequires a periodic key disclosure, but these messages are grafted onto routing updates (see Section 8). We can take two different views regarding the costs of these messages. If we accept that the routing beacons are necessary, then $\mu$TESLAkey disclosure is nearly free, because energy of transmitting or receiving dominate the computational costs of our protocols. On the other hand, one might claim that the routing beacons are not necessary and that it is possible to construct an ad hoc multihop network implicitly. In that case the overhead of key disclosure would be one message per time interval, regardless of the traffic pattern within the network. We believe that the benefit of authenticated routing justifies the costs of explicit beacons.

  
Figure 6: Energy costs of adding security protocols to the sensor network. Most of the overhead arises from the transmission of extra data rather than from any computational costs.

Remaining security issues Although this protocol suite does address many security related problems, there remain many additional issues. First, we do not address the problem of information leakage through covert channels. Second, we do not deal completely with compromised sensors, we merely ensure that compromising a single sensor does not reveal the keys of all the sensors in the network. It is an interesting research problem on how to design efficient protocols that scale down to sensor networks which are robust to compromised sensors. Third, we do not deal with denial-of-service (DoS) attacks in this work. Since we operate on a wireless network, an adversary can always perform a DoS attack by jamming the radio channel with a strong signal. Finally, due to our hardware limitations, we cannot provide Diffie-Hellman style key agreement or use digital signatures to achieve non-repudiation. We believe that for the majority of sensor network applications, authentication is sufficient.