In our model, a sender distributes a stream of data composed of message chunks . Generally, the sender sends each message chunk in one network packet . Many multicast distribution protocols do not retransmit lost packets. The goal is therefore that the receiver can authenticate each message chunk separately.
For the purpose of TESLA, the sender splits the time into even intervals . We denote the duration of each time interval with , and the starting time of the interval is . Trivially, we have . In each interval, the sender may send zero or multiple packets.
Before sending the first message, the sender determines the sending duration (possibly infinite), the interval duration, and the number N of keys of the key chain. This key chain is analogous to the one-way chain introduced by Lamport [18], and the S/KEY authentication scheme [15]. The sender picks the last key of the key chain randomly and pre-computes the entire key chain using a pseudo-random function F, which is by definition a one-way function. Each element of the chain is defined as . Each key can be derived from as , where and . Each key of the key chain corresponds to one interval, i.e., is active in interval .
Since we do not want to use the same key multiple times in different cryptographic operations, we use a second pseudo-random function F' to derive the key which is used to compute the MAC of messages in each interval (we will explain the algorithm in detail later). Hence, . Figure 1 depicts this key derivation. We propose to use HMAC in conjunction with a cryptographically secure hash function for the pseudo-random function [2]. For example, a possibility is to use the following: and , where and are 8-bit integers. Note that the first argument of the MAC function is the key and the second argument is the data.