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 $\delta$_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 receiver uses a nonce in its first packet to prevent an attack which replays a previously signed synchronization reply. Besides the current time $t$_S 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 $\Delta$_t = t_S - t_R and computes the latest possible sender's time $t\text{'}$_S as follows: $t\text{'}$_S = t'_R + Δ_t, where $t\text{'}$_R is the current receiver's time, and $t\text{'}$_S is the estimated sender time. In the ideal case, the receiver's initial packet arrives at the sender without delay, denoted as time $t$₁ in the figure. The maximum time discrepancy $\delta$_t = RTT (round-trip time).

t1$t$₁ t2$t$₂ t3$t$₃ tS$t$_S tR$t$_R

 
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 $\delta$_t(S). The sender would periodically broadcast the interval information, along with its $\delta$_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 $\delta$_t. Finally, the receivers add up all the $\delta$_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.

 
• Combining with multicast group control centers.
• Dealing with clock drift.