next up previous
Next: Bootstrapping a new Receiver Up: An Overview of TESLA Previous: An Overview of TESLA

Sender Setup

 

In our model, a sender distributes a stream of data composed of message chunks {Mi}. Generally, the sender sends each message chunk Mi in one network packet Pi. Many multicast distribution protocols do not retransmit lost packets. The goal is therefore that the receiver can authenticate each message chunk Mi separately.

For the purpose of TESLA, the sender splits the time into even intervals Ii. We denote the duration of each time interval with Tint, and the starting time of the interval Ii is Ti. Trivially, we have Ti = T0 + i * Tint. 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 KN 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 Ki = F(Ki+1). Each key can be derived from KN as Ki = FN-i(KN), where Fj(k) = Fj-1(F(k)) and F0(k) = k. Each key of the key chain corresponds to one interval, i.e., Kj is active in interval Ij.

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, K'i = F'(Ki). 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: F(x) = HMAC( x, 0 ) and F'(x) = HMAC( x, 1 ), where 0 and 1 are 8-bit integers. Note that the first argument of the MAC function is the key and the second argument is the data.


next up previous
Next: Bootstrapping a new Receiver Up: An Overview of TESLA Previous: An Overview of TESLA

Adrian Perrig
Sun Nov 5 19:29:44 PST 2000