Time Synchronization

 

TESLA does not need the strong time synchronization properties that sophisticated time synchronization protocols provide [22, 24, 37], but only requires loose time synchronization, and that the receiver knows an upper bound on the sender's local time. We now outline a simple and secure time synchronization protocol that achieves this requirement. For simplicity, we assume the clock drift of both sender and receiver is negligible (otherwise the receiver can periodically resynchronize the time with the sender). We denote the real difference between the sender and the receiver's time with $\delta$. In loose time synchronization, the receiver does not need to know the exact $\delta$ but only an upper bound on it, $\Delta$, which we also refer to as the maximum time synchronization error. We now describe a simple protocol for time synchronization, where each receiver performs explicit time synchronization with the sender. This approach does not require any extra infrastructure to perform time synchronization. We present a simple two-round time synchronization protocol that satisfies the requirement for TESLA, which is that the receiver knows an upper bound on the sender's clock. Reiter previously describes this protocol [31, 32].

  
Figure 2: Direct time synchronization between the sender and the receiver. The receiver issues a time synchronization request at time $t$_R, at which time the sender's clock is at time $t$₁. The sender responds to the request at its local time $t$_S. In TESLA, the receiver is only interested in an upper bound on the sender's time. When the receiver has its current time $t$_r, it computes the upper bound on the current sender's time as $t$_s ≤t_r - t_R + t_S. The real synchronization error after this protocol is $\delta$. The receiver, however, does not know the propagation delay of the time synchronization request packet, so it must assume that the time synchronization error is $\Delta$ (or the full round-trip time (RTT)).

Figure 2 shows a sample time synchronization between the receiver and the sender. In the protocol, the receiver first records its local time $t$_R and sends a time synchronization request containing a nonce to the sender. Upon receiving the time synchronization request, the sender records its local time $t$_S and replies with a signed response packet containing $t$_S and the nonce.

1. Setup. The sender $S$ has a digital signature key pair, with the private key $K$_S^-1 and the public key $K$_S. We assume a mechanism that allows a receiver $R$ to learn the authenticated public key $K$_S. The receiver chooses a random and unpredictable nonce.
2. Protocol steps. Before sending the first message, the receiver records its local time $t$_R.
   
   To verify the return message, the receiver verifies the digital signature and checks that the nonce in the packet equals the nonce it randomly generated. If the message is authentic, the receiver stores $t$_R and $t$_S. To compute the upper bound on the sender's clock at local time $t$, the receiver computes $t-t$_R+t_S.

Upon receiving the signed response, the receiver checks the validity of the signature and verifies that the nonce in the response packet equals the nonce in the request packet. If all verifications are successful, the receiver uses $t$_R and $t$_S to compute the upper bound of the sender's time: when the receiver has the current time $t$_r, it computes the upper bound on the current sender's time as $t$_s ≤t_r - t_R + t_S. The real synchronization error after this protocol is $\delta$, as Figure 2 shows. The receiver, however, does not know the propagation delay of the time synchronization request packet, so it must assume that the time synchronization error is $\Delta$ (or the full round-trip time (RTT)).

A digital signature operation is computationally expensive, and we need to be careful about denial-of-service attacks in which an attacker floods the sender with time synchronization requests. Another problem is request implosion: the sender is overwhelmed with time synchronization requests from receivers. We address these issues in our earlier paper [27].