Scheme I: The Basic Scheme

 

Here is a summary of scheme I: The sender issues a signed commitment to a key which is only known to itself. The sender then uses that key to compute a MAC on a packet $P$_i, and later discloses the key in packet $P$_i+1, which enables the receiver to verify the commitment and the MAC of packet $P$_i. If both verifications are successful, packet $P$_i is authenticated and trusted. The commitment is realized via a pseudorandom function with collision resistance. More details on the requirements on the pseudo-random functions are in appendix A. This protocol is similar to the Guy Fawkes protocol [1].

pim1$P$_i-1 pi$P$_i pip1$P$_i+1 mim1$M$_i-1 mi$M$_i mip1$M$_i+1 fki$F(K$_i) fkip1$F(K$_i+1) fkip2$F(K$_i+2) dim1$D$_i-1 di$D$_i dip1$D$_i+1 kim2$K$_i-2 kim1$K$_i-1 ki$K$_i kip1$K$_i+1 ma1MAC$(K\text{'}$_i-1,D_i-1) ma2MAC$(K\text{'}$_i,D_i) ma3MAC$(K\text{'}$_i+1,D_i+1)

 
Figure 1: Basic stream authentication scheme. $M$_i stands for message $i$, $P$_i is packet $i$, $K$_i denotes the secret key $i$, $F,F\text{'}$ are pseudo-random functions, and $MAC(K$_i',D_i) computes the MAC of packet $i$ using the secret key $K$_i' = F'(K_i). 

We now describe the basic scheme in more detail. The scheme is depicted in Figure 1. We assume that the receiver has an authenticated packet $P$_i-1 = D_i-1, MAC(K_i-1',D_i-1) to start with (where $D$_i-1 = M_i-1, F(K_i), K_i-2). The fields have the following meanings. $M$_i-1 is the message contained by the packet, $K\text{'}$_i = F'(K_i) is the secret key used to compute the MAC of the next packet, and $F(K$_i) commits to the key $K$_i without revealing it. The functions $F$ and $F\text{'}$ are two different pseudo-random functions. Commitment value $F(K$_i) is important for the authentication of the subsequent packet $P$_i. To bootstrap this scheme, the first packet needs to be authenticated with a regular digital signature scheme, for example RSA [27].

To send the message $M$_i, the sender picks a fresh random key $K$_i+1 and constructs the following packet $P$_i = D_i, MAC(K_i',D_i), where $D$_i = M_i, F(K_i+1), K_i-1 and the $MAC(K$_i',D_i) computes a message authenticating code of $D$_i under key $K$_i'.

When the receiver receives packet $P$_i, it cannot verify the MAC instantly, since it does not know $K$_i and cannot reconstruct $K$_i'. Packet $P$_i+1 = D_i+1, MAC(K_i+1', D_i+1) (where $D$_i+1 = M_i+1, F(K_i+2), K_i) discloses $K$_i and allows the receiver first to verify that $K$_i is correct ($F(K$_i) equals the commitment which was sent in packet $P$_i-1); and second to compute $K$_i' = F'(K_i) and check the authenticity of packet $P$_i by verifying the MAC of packet $P$_i.

After the receiver has authenticated $P$_i, the commitment $F(K$_i+1) is also authenticated and the receiver repeats this scheme to authenticate $P$_i+1 after $P$_i+2 is received.

This scheme can be subverted if an attacker gets packet $P$_i+1 before the receiver gets $P$_i, since the attacker would then know the secret key $K$_i which is used to compute the MAC of $P$_i, which allows it to change the message and the commitment in $P$_i and forge all subsequent traffic. To prevent this attack, the receiver checks the following security condition on each packet it receives, and drops the packet if the condition does not hold.

Security condition: A data packet $P$_i arrived safely, if the receiver can unambiguously decide, based on its synchronized time and $\delta$_t, that the sender did not yet send out the corresponding key disclosure packet $P$_j.

This stream authentication scheme is secure as long as the security condition holds. We would like to emphasize that the security of this scheme does not rely on any assumptions on network latency.

In order for the receiver to verify the security condition, the receiver needs to know the precise sending schedule of packets. The easiest way to solve this problem is by using a constant packet rate. The sending time of packet $P$_i is hence $T$_i = T₀ + i/r where $T$_i is the time on the sender's clock and $r$ is the packet rate (number of packets per second). In that case, the security condition which the receiver checks has the following form: $ArrT$_i + δ_t < T_i+1, where $ArrT$_i stands for the arrival time (on the synchronized receiver's clock) of packet $P$_i. The main problem with this scheme is that, in order to satisfy the security condition, the sending rate must be slower than the network delay from the sender to the receiver. This is a severe limitation on the throughput of the transmission. In addition, the basic scheme cannot tolerate packet loss. In particular, once a packet is dropped no further packets can be authenticated. We now gradually extend the basic scheme to eliminate these deficiencies.