next up previous
Next: Combining with multicast group Up: TESLA: Timed Efficient Stream Previous: Scheme V: Accommodate a

Initial Synchronization - Further Discussion

 

Our stream authentication scheme relies on a loose time synchronization between the sender and all the recipients. We call this synchronization loose, because the synchronization error can be large. The only requirement we have is that the client knows an upper bound δt on the maximum synchronization error.

Any time synchronization protocol can be used for our scheme, as long as it is robust against an active adversary.

As a proof-of-concept, we present a simple time synchronization protocol which suffices the requirements. The basic protocol is as follows:

The receivergif uses a nonce in its first packet to prevent an attack which replays a previously signed synchronization reply. Besides the current time tS at the sender, the sender also sends all information necessary to define the intervals and a commitment to the active key chain. The disclosure lag defines the difference in intervals on when the key values are disclosed. Finally, the packet is signed with a regular signature scheme.

For the purposes of our stream authentication scheme, the receiver is only interested in the maximum possible time value at the sender. This simplifies the computation. Figure 5 shows a timing diagram of the synchronization. The receiver sets Δt = tS - tR and computes the latest possible sender's time t'S as follows: t'S = t'R + Δt, where t'R is the current receiver's time, and t'S is the estimated sender time. In the ideal case, the receiver's initial packet arrives at the sender without delay, denoted as time t1 in the figure. The maximum time discrepancy δt = RTT (round-trip time).

t1t1 t2t2 t3t3 tStS tRtR

 figure408
Figure 5: The receiver synchronizes its time with the sender. 

Scalability is a major concern for a widely deployed system. If every receiver needs to synchronize its time with the sender, the sender could be a bottleneck. A better solution would use distributed and secure time servers. Initially, the sender synchronizes its time with the time server and computes the maximum synchronization error δt(S). The sender would periodically broadcast the interval information, along with its δt(S) and the current timestamp, digitally signed to ensure authenticity. The receivers can independently synchronize their time to the synchronization server, and individually compute their maximum synchronization error δt. Finally, the receivers add up all the δt values to verify the security condition. Taking this scheme one step further, we could have a hierarchy of synchronization servers (only the maximum errors need to propagate). We could also imagine synchronizing all the synchronization servers with a satellite signal, for example GPS.




next up previous
Next: Combining with multicast group Up: TESLA: Timed Efficient Stream Previous: Scheme V: Accommodate a

Adrian Perrig
Sat Sep 2 17:01:14 PDT 2000