Immediate Authentication

 

A drawback of the original TESLA protocol is that the receiver needs to buffer packets during one disclosure delay before it can authenticate them. This might not be practical for certain applications if the receivers cannot afford much buffer space and bursty traffic might cause the receivers to drop packets due to insufficient buffer space. Moreover, as we show later in section 4.2, the requirement of receiver buffering introduces a vulnerability to a denial-of-service attack. To solve these problems caused by receiver-buffering, we propose a new method to support immediate authentication, which allows the receiver to authenticate packets as soon as they arrive.

The basic observation of this method is that we can replace receiver buffering with sender buffering. If the sender can buffer packets during one disclosure delay, then it could store the hash value of the data of a later packet in an earlier packet and hence as soon as the earlier packet is authenticated, the data in the later packet is authenticated through the hash value as well.

In the new scheme, the sender buffers packets for the duration of one disclosure delay. For simplicity of illustration, we assume that the sender sends out a constant number $v$ of packets per time interval. To construct the packet for the message chunk $M$_j in time interval $T$_i, the sender appends the hash value of the message chunk $M$_j+vd to $M$_j and then computes the MAC value also over $H(M$_j+vd) with the key $K$_i. Figure 2 illustrates how the packet $P$_j is constructed by appending $H(M$_j+vd), $MAC(K$_i, M_j | H(M_j+vd)), along with the disclosed key $K$_i-d. (Note that the $|$ stands for message concatenation). When the packet $P$_j+vd arrives at the receiver which discloses the key $K$_i it allows authentication of packet $P$_j sent in interval $I$_i. $P$_j carries a hash of the data $M$_j+vd in $P$_j+vd. If $P$_j is authentic, $H(M$_j+vd) is also authentic and therefore the data $M$_j+vd is immediately authenticated. Also note that if $P$_j is lost or dropped due to violation of the security condition, $P$_j+vd will not be immediately authenticated and can still be authenticated later using the MAC value.

HMjpkd$H(M$_j+vd) MACKiHMj$MAC(K\text{'}$_i,D_j) Kimd$K$_i-d Dj$D$_j Djpkd$D$_j+vd Mjpkd$M$_j+vd HMjp2kd$H(M$_j+2vd) MACKipdHMj$MAC(K\text{'}$_i+d,D_j+vd)

 
Figure 2: Immediate authentication packet example. $D$_j = H(M_j+vd) | M_j and $D$_j+vd = H(M_j+2vd) | M_j+vd. 

Iip3$I$_i+3 Pjp7$P$_j+7 Pjp8$P$_j+8

If each packet can only carry the hash of one other packet, it is clear that the sending rate needs to remain constant. Also it is clear that if a packet is lost, the corresponding packet cannot be immediately authenticated. To achieve flexibility for dynamic sending rate and robustness to packet loss, the sender can add the hash values of multiple future packets to a packet, similar to the EMSS scheme [25].