Scheme IV: Dealing with Dynamic Packet Rates

 

Our previous schemes used a fixed or predictable sender schedule, with each recipient knowing the exact sending time of each packet. Since this severely restricts the flexibility of senders, we design a scheme which allows senders to send at dynamic transmission rates, without the requirement that every receiver needs to know about the exact sending schedule of each packet. The solution to this problem is to pick the MAC key and the disclosed key in each packet only on a time interval basis instead of on a packet index basis. The sender uses the same key $K$_i to compute the MAC for all packets which are sent in the same interval $i$. All packets sent in interval $i$ disclose the key $K$_i-d.

At session set-up the sender announces values $T$₀ and $T$_Δ, where the former is the starting time of the first interval and the latter is the duration of each interval. In addition the delay parameter $d$ is announced. These announcements are signed by the sender. The interval index at any time period $t$ is determined as $i\; =\; \{t-T$₀T_Δ}. A key $K$_i is associated with each interval $i$. The keys are chained in the same way as in Scheme II. The sender uses the same key $K$_i' = F'(K_i) to compute the MAC for each packet which is sent in interval $i$. Every packet also carries the interval index $i$ and discloses the key of a previous interval $K$_i-d. We refer to $d$ as disclosure lag. The format of packet $P$_j is $P$_j = M_j, i, K_i-d, MAC(K_i',M_j). Figure 3 shows an example of this scheme, where $d=4$.

pj$P$_j pjp1$P$_j+1 pjp2$P$_j+2 pjp3$P$_j+3 pjp4$P$_j+4 pjp5$P$_j+5 pjp6$P$_j+6 kip2$K$_i+2 kip3$K$_i+3 kip4$K$_i+4 kip5$K$_i+5 kip6$K$_i+6 kip7$K$_i+7

 


Figure 3: Scheme IV. The MAC key and disclosed key are only dependent on the time interval. The authentication key of $P$_j is $K$_i which is disclosed by packets sent during interval $i+4$. In this case, packet $P$_j+4 discloses key $K$_i+1 which allows the receiver to compute $K$_i and to authenticate packet $P$_j. We would like to point out that packets $P$_j+2 and $P$_j+3 are both authenticated with the same MAC key $K$_i+3', because they were sent in the same time interval. 

In this scheme, the receiver verifies the security condition as follows. Each receiver knows the values of $T$₀, $T$_Δ, and $\delta$_t. ($\delta$_t is the value obtained from the initial synchronization protocol.) Assume that the receiver gets packet $P$_j at its local time $t$_j, and the packet was apparently sent in interval $i$. The sender can be at most in interval $i\text{'}\; =\; \{t$_j + δ_t - T₀T_Δ}. The security condition in this case is simply $i\; +\; d\; >\; i\text{'}$, which ensures that no packet which discloses the value of the key could have been sent yet. Figure 4 illustrates the verification of the security condition.

It remains to describe how the values $T$_Δ and $d$ are picked. (We stress that the choice of these values does not affect the security of the scheme, only its usability.) Before the sender can pick values for $T$_Δ and $d$, it needs to determine the maximum tolerable synchronization uncertainty $\delta$_tMax, and the maximum tolerable network delay $d$_NMax. The sender defines $\Delta$_Max&thicksp; def =&thicksp;δ_tMax + d_NMax

The sender's choice for $T$_Δ and $\Delta$_Max both present a tradeoff. First, a large value for $\Delta$_Max will allow slow receivers to verify the security condition correctly, but requires a long delay for packet authentication. Conversely, a short $\Delta$_Max will cause slow receivers to drop packets because the security condition is not satisfied. The second tradeoff is that a long interval duration $T$_Δ saves on the computation and storage overhead of the key chain, but a short $T$_Δ more closely achieves the desired $\Delta$_Max.

After determining $\delta$_tMax, $d$_NMax, and $T$_Δ, the disclosure lag is $d\; =\; \{\delta$_tMax + d_NMaxT_Δ}.

This scheme provides numerous advantages. First, the sender can predict how long a pre-computed key chain lasts, since the number of necessary keys is only time dependent and not on the number of packets sent. Second, the receiver can conveniently verify the security condition and the sender does not need to send its packets at specific intervals (we will discuss the details of this in Section 2.9). Another advantage is that new receivers can easily join the group at any moment. A new group member only needs to synchronize its time with the sender and receive the interval parameters and a commitment to the key chain.

mdt$-\delta$_t pdt$+\delta$_t

 


Figure 4: The security condition visualized. The packet $P$_j is sent in the interval where key $K$_i+1 is active. The receiver receives the packet when the sender is in interval $i+3$, but due to the $\delta$_t the sender might already be in interval $i+4$, which discloses key $K$_i. This is not a problem for the current packet, so key $K$_i+1 was not disclosed yet, hence the security condition is satisfied and the packet is safe.