Full paper: Postscript, PS.GZ, PDF

$\mu$TESLADetailed Description

$\mu$TESLAhas multiple phases: Sender setup, sending authenticated packets, bootstrapping new receivers, and authenticating packets. For simplicity, we explain $\mu$TESLAfor the case where the base station broadcasts authenticated information, and we discuss the case where nodes send authenticated broadcasts at the end of this section.

Sender setup The sender first generates a sequence of secret keys (or key chain). To generate the one-way key chain of length $n$, the sender chooses the last key $K$_n randomly, and generates the remaining values by successively applying a one-way function $F$ (e.g.a cryptographic hash function such as MD5 [34]): $K$_j = F(K_j+1). Because $F$ is a one-way function, anybody can compute forward, e.g.compute $K$₀,&ldots;,K_j given $K$_j+1, but nobody can compute backward, e.g.compute $K$_j+1 given only $K$₀,&ldots;,K_j, due to the one-way generator function. This is similar to the S/Key one-time password system [14].

Broadcasting authenticated packets Time is divided into time intervals and the sender associates each key of the one-way key chain with one time interval. In time interval $t$, the sender uses the key of the current interval, $K$_t, to compute the message authentication code (MAC) of packets in that interval. The sender will then reveal the key $K$_t after a delay of $\delta$ intervals after the end of the time interval $t$. The key disclosure time delay $\delta$ is on the order of a few time intervals, as long as it is greater than any reasonable round trip time between the sender and the receivers.

Bootstrapping a new receiver The important property of the one-way key chain is that once the receiver has an authenticated key of the chain, subsequent keys of the chain are self-authenticating, which means that the receiver can easily and efficiently authenticate subsequent keys of the one-way key chain using the one authenticated key. For example, if a receiver has an authenticated value $K$_i of the key chain, it can easily authenticate $K$_i+1, by verifying $K$_i = F(K_i+1). Therefore to bootstrap $\mu$TESLA, each receiver needs to have one authentic key of the one-way key chain as a commitment to the entire chain. Another requirement of $\mu$TESLAis that the sender and receiver are loosely time synchronized, and that the receiver knows the key disclosure schedule of the keys of the one-way key chain. Both the loose time synchronization as well as the authenticated key chain commitment can be established with a mechanism that provides strong freshness and point-to-point authentication. A receiver sends a nonce in the request message to the sender. The sender replies with a message containing its current time $T$_S (for time synchronization), a key $K$_i of the one-way key chain used in a past interval $i$ (the commitment to the key chain), and the starting time $T$_i of interval $i$, the duration $T$_int of a time interval, and the disclosure delay $\delta$ (the last three values describe the key disclosure schedule).

Since we do not need confidentiality, the sender does not need to encrypt the data. The MAC uses the secret key shared by the node and base station to authenticate the data, the nonce $N$_M allows the node to verify freshness. Instead of using a digital signature scheme as in TESLA, we use the node-to-base-station authenticated channel to bootstrap the authenticated broadcast.

Authenticating broadcast packets When a receiver receives the packets with the MAC, it needs to ensure that the packet could not have been spoofed by an adversary. The threat is that the adversary already knows the disclosed key of a time interval and so it could forge the packet since it knows the key used to compute the MAC. Hence the receiver needs to be sure that the sender did not disclose the key yet which corresponds to an incoming packet, which implies that no adversary could have forged the contents. This is called the security condition, which receivers check for all incoming packets. Therefore the sender and receivers need to be loosely time synchronized and the receivers need to know the key disclosure schedule. If the incoming packet satisfies the security condition, the receiver stores the packet (it can verify it only once the corresponding key is disclosed). If the security condition is violated (the packet had an unusually long delay), the receiver needs to drop the packet, since an adversary might have altered it.

As soon as the node receives a key $K$_j of a previous time interval, it authenticates the key by checking that it matches the last authentic key it knows $K$_i, using a small number of applications of the one-way function $F$: $K$_i = F^j-i(K_j). If the check is successful, the new key $K$_j is authentic and the receiver can authenticate all packets that were sent within the time intervals $i$ to $j$. The receiver also replaces the stored $K$_i with $K$_j.

Nodes broadcast authenticated data New challenges arise if a node broadcasts authenticated data. Since the node is severely memory limited, it cannot store the keys of a one-way key chain. Moreover, re-computing each key from the initial generating key $K$_n is computationally expensive. Another issue is that the node might not share a key with each receiver, hence sending out the authenticated commitment to the key chain would involve an expensive node-to-node key agreement, as we describe in Section 8. Finally, broadcasting the disclosed keys to all receivers can also be expensive for the node and drain precious battery energy.

Here are two viable approaches to deal with this problem:

• The node broadcasts the data through the base station. It uses SNEPto send the data in an authenticated way to the base station, which subsequently broadcasts it.
• The node broadcasts the data. However, the base station keeps the one-way key chain and sends keys to the broadcasting node as needed. To conserve energy for the broadcasting node, the base station can also broadcast the disclosed keys, and/or perform the initial bootstrapping procedure for new receivers.