Full paper: Postscript, PS.GZ, PDF

$\mu$TESLAOverview

We give a brief overview of $\mu$TESLA, followed by a detailed description.

As we discussed in Section 3, authenticated broadcast requires an asymmetric mechanism, otherwise any compromised receiver could forge messages from the sender. Unfortunately, asymmetric cryptographic mechanisms have high computation, communication, and storage overhead, which makes their usage on resource-constrained devices impractical. $\mu$TESLAovercomes this problem by introducing asymmetry through a delayed disclosure of symmetric keys, which results in an efficient broadcast authentication scheme.

For simplicity, we explain $\mu$TESLAfor the case where the base station broadcasts authenticated information to the nodes, and we discuss the case where the nodes are the sender at the end of this section.

$\mu$TESLArequires that the base station and nodes are loosely time synchronized, and each node knows an upper bound on the maximum synchronization error. To send an authenticated packet, the base station simply computes a MAC on the packet with a key that is secret at that point in time. When a node gets a packet, it can verify that the corresponding MAC key was not yet disclosed by the base station (based on its loosely synchronized clock, its maximum synchronization error, and the time schedule at which keys are disclosed). Since a receiving node is assured that the MAC key is known only by the base station, the receiving node is assured that no adversary could have altered the packet in transit. The node stores the packet in a buffer. At the time of key disclosure, the base station broadcasts the verification key to all receivers. When a node receives the disclosed key, it can easily verify the correctness of the key (which we explain below). If the key is correct, the node can now use it to authenticate the packet stored in its buffer.

Each MAC key is a key of a key chain, generated by a public one-way function $F$. To generate the one-way key chain, the sender chooses the last key $K$_n of the chain randomly, and repeatedly applies $F$ to compute all other keys: $K$_i = F(K_i+1). Each node can easily perform time synchronization and retrieve an authenticated key of the key chain for the commitment in a secure and authenticated manner, using the SNEPbuilding block. (We explain more details in the next subsection).

Example
Figure 2 shows an example of $\mu$TESLA. Each key of the key chain corresponds to a time interval and all packets sent within one time interval are authenticated with the same key. The time until keys of a particular interval are disclosed is $2$ time intervals in this example. We assume that the receiver node is loosely time synchronized and knows $K$₀ (a commitment to the key chain) in an authenticated way. Packets $P$₁ and $P$₂ sent in interval $1$ contain a MAC with key $K$₁. Packet $P$₃ has a MAC using key $K$₂. So far, the receiver cannot authenticate any packets yet. Let us assume that packets $P$₄, $P$₅, and $P$₆ are all lost, as well as the packet that discloses key $K$₁, so the receiver can still not authenticate $P$₁, $P$₂, or $P$₃. In interval $4$ the base station broadcasts key $K$₂, which the node authenticates by verifying $K$₀ = F(F(K₂)), and hence knows also $K$₁ = F(K₂), so it can authenticate packets $P$₁, $P$₂ with $K$₁, and $P$₃ with $K$₂.

  
Figure 2: Using a time-released key chain for source authentication.

Instead of adding a disclosed key to each data packet, the key disclosure is independent from the packets broadcast, and is tied to time intervals. Within the context of $\mu$TESLA, the sender broadcasts the current key periodically in a special packet.