Full paper: Postscript, PS.GZ, PDF

$\mu$TESLA: Authenticated Broadcast

 

Current proposals for authenticated broadcast are impractical for sensor networks. First, most proposals rely on asymmetric digital signatures for the authentication, which are impractical for multiple reasons. They require long signatures with high communication overhead of 50-1000 bytes per packet, very high overhead to create and verify the signature. Even previously proposed one-time signature schemes that are based on symmetric cryptography (one-way functions without trapdoors) have a high overhead: Gennaro and Rohatgi's broadcast signature based on Lamport's one-time signature [20] requires over 1 Kbyte of authentication information per packet [11], and Rohatgi's improved $k$-time signature scheme requires over $300$ bytes per packet [36].

The recently proposed TESLA protocol provides efficient authenticated broadcast [31, 30]. However, TESLA is not designed for such limited computing environments as we encounter in sensor networks for three reasons.

First, TESLA authenticates the initial packet with a digital signature. Clearly, digital signatures are too expensive to compute on our sensor nodes, since even fitting the code into the memory is a major challenge. For the same reason as we mention above, one-time signatures are a challenge to use on our nodes.

Standard TESLA has an overhead of approximately $24$ bytes per packet. For networks connecting workstations this is usually not significant. Sensor nodes, however, send very small messages that are around $30$ bytes long. It is simply impractical to disclose the TESLA key for the previous intervals with every packet: with $64$ bit keys and MACs, the TESLA-related part of the packet would be constitute over $50\%$ of the packet.

Finally, the one-way key chain does not fit into the memory of our sensor node. So pure TESLA is not practical for a node to broadcast authenticated data.

We design $\mu$TESLAto solve the following inadequacies of TESLA in sensor networks:

• TESLA authenticates the initial packet with a digital signature, which is too expensive for our sensor nodes. $\mu$TESLAuses only symmetric mechanisms.
• Disclosing a key in each packet requires too much energy for sending and receiving. $\mu$TESLAdiscloses the key once per epoch.
• It is expensive to store a one-way key chain in a sensor node. $\mu$TESLA restricts the number of authenticated senders.