Full paper: Postscript, PS.GZ, PDF

Implementation

 

Due to the stringent resource constraints of the sensor nodes, the implementation of the cryptographic primitives is a major challenge. Usually for the sake of feasibility and efficiency, security is sacrificed. Our belief, however, is that strong cryptography is necessary for trustworthy devices. Hence, one of our main goals is to provide strong cryptography despite the severe hardware restrictions.

A hard constraint is the memory size: Our sensor nodes have 8 KBytes of read-only program memory, and 512 bytes of RAM. The program memory is used for TinyOS, our security infrastructure, and the actual sensor net application. To save program memory we implement all cryptographic primitives from one single block cipher [22, 38].

Block cipher We evaluated several algorithms for use as a block cipher. An initial choice was the AES algorithm Rijndael [6]; however, after closer inspection, we sought alternatives with smaller code size and higher speed. The baseline version of Rijndael uses over 800 bytes of lookup tables which is too large for our memory-deprived nodes. An optimized version of that algorithm which runs about a 100 times faster, uses over 10 Kbytes of lookup tables. Similarly, we rejected the DES block cipher which requires a 512-entry SBox table, and a 256-entry table for various permutations [42]. We defer using other small encryption algorithms such as TEA [43] or TREYFER [44] until they matured after thorough scrutiny of cryptanalysts. We chose to use RC5 [33] because of its small code size and high efficiency. RC5 does not rely on multiplication, and does not require large tables. However, RC5 does use 32-bit data-dependent rotates, and our Atmel processor only has an 8-bit single bit rotate, which makes this operation expensive.

Even though the RC5 algorithm can be expressed very succinctly, the common RC5 libraries are too large to fit on our platform. With a judicious selection of functionality, we were able to use a subset of RC5 from OpenSSL, and after further tuning of the code we achieve an additional 40% reduction in code size.

Encryption function To save code space, we use the same function both for encryption and decryption. The counter (CTR) mode of block ciphers, shown in Figure 3 has this property. Another property of the CTR mode is that it is a stream cipher in nature. Therefore the size of the ciphertext is exactly the size of the plaintext and not a multiple of the block size. This property is particularly desirable in our environment. Message sending and receiving is very expensive in terms of energy. Also, longer messages have a higher probability of data corruption. Therefore, message expansion by the block cipher is undesirable. CTR mode requires a counter for proper operation. Reusing a counter value severely degrades security. In addition, CTR-mode offers semantic security, since the same plaintext sent at different times is encrypted into different ciphertext because the encryption pads are generated from different counters. To an adversary who does not know the key, these messages will appear as two different, unrelated, random strings. Since the sender and the receiver share the counter, we do not need to include it in the message. If the two nodes lose the synchronization of the counter, they can simply transmit the counter explicitly to resynchronize using SNEP with strong freshness.

  
Figure 3: Counter mode encryption and decryption. The encryption function is applied to a monotonically increasing counter to generate a one time pad. This pad is then XORed with the plaintext. The decryption operation is identical.

Freshness Weak freshness is automatically provided by the CTR encryption. Since the sender increments the counter after each message, the receiver verifies weak freshness by verifying that received messages have a monotonically increasing counter. For applications that require strong freshness, the node creates a random nonce $N$_M (a 64-bit value that is unpredictable) and sends in the request message to the receiver. The receiver generates the response message and includes the nonce in the MAC computation (see Section 5). If the MAC of the response verifies successfully, the node knows that the response was generated after it sent out the request message and hence achieves strong freshness.

Random-number generation Although the node has its own sensors, radio receiver, and scheduling process, from which we could derive random digits, we choose to minimize power requirements and select the most efficient random number generation. We use a MAC function as our pseudo-random number generator (PRG), with the secret pseudo-random number generator key $K$_rand. We also keep a counter $C$ that we increment after each pseudo-random block we generate. We compute the $C$-th pseudo-random output block as $MAC(K$_rand,C). If $C$ wraps around (which should never happen because the node will exhaust its energy before then), we derive a new PRG key from the master secret key and the current PRG key using our MAC as a pseudo-random function (PRF): $K$_rand' = MAC(K, K_rand).

Message authentication We also need a secure message authentication code. Because we intend to re-use our block cipher, we use the well-known CBC-MAC [41]. A block diagram for computing CBC MAC is shown in Figure 4.

To achieve authentication and message integrity we use the following standard approach. Assuming a message $M$, an encryption key $K$_encr, and a MAC key $K$_mac, we use the following construction: $\{M\}$ K_encr, MAC(K_mac,{M}₄₅₆K_E). This construction prevents the nodes from decrypting erroneous ciphertext, which is a potential security risk.

In our implementation, we decided to compute a MAC per packet. This approach fits well with the lossy nature of communications within this environment. Furthermore, at this granularity, MAC is used to check both authentication and integrity of messages, eliminating the need for mechanisms like CRC.

  
Figure 4: CBC MAC. The output of the last stage serves as the authentication code.

Key setup Recall that our key setup depends on a secret master key, initially shared by the base station and the node. We denote that key with $K$_i for node $M$_i. All keys subsequently needed are bootstrapped from the initial master secret key. Figure 5 shows our key derivation procedure. We use the pseudo-random function (PRF) $F$ to derive the keys, which we implement as $F$_K(x) = MAC(K,x). Again, this allows for more code reuse. Since MAC has strong one-way properties, all keys derived in this manner are computationally independent. Even if the attacker could break one of the keys, the knowledge of that key would not help it to determine the master secret or any other key. Additionally, if we detect that a key has been compromised, both parties can derive a new key without transmitting any confidential information.

  
Figure 5: Deriving internal keys from the master secret key