Our Basic Signature Scheme

To achieve non-repudiation, we rely on a conventional signature scheme, for example RSA [27] or Rohatgi's k-times signature scheme [28]. Unfortunately, the computation and communication overhead of current signature schemes is too high to sign every packet individually. To reduce the overhead, one signature needs to be amortized over multiple packets.

Our basic solution bases on the following scheme to achieve non-repudiation of a sequence of packets. Packet $P$_i includes a hash $H(P$_i-1) of the previous packet $P$_i-1. By sending a signature packet at the end of the stream, which contains the hash of the final packet along with a signature, we achieve non-repudiation for all packets. To achieve robustness against packet loss, each packet contains multiple hashes of previous packets, and furthermore, the final signature packet signs the hash of multiple packets. Figure 6 shows an example, where each packet contains the hash of the two previous packets, and where the signature packet contains the hash of the last two packet and the signature.

Pi$P$_i Pip1$P$_i+1 Pip2$P$_i+2 Mi$M$_i Mip1$M$_i+1 Mip2$M$_i+2 hpim2$H(P$_i-2) hpim1$H(P$_i-1) hpi$H(P$_i) hpip1$H(P$_i+1) hpip2$H(P$_i+2)

 
Figure 6: We achieve non-repudiation through periodic signature packets, which contain the hash of several data packets, and the inclusion of the hash of the current packet within future packets. The inclusion of multiple hashes achieves robustness against packet loss. 

In order for the sender to continuously verify the signature of the stream, the sender sends periodic signature packets. Since the receiver can only verify the signature of a packet after it receives the next signature packet, it is clear that the receiver experiences a delay until packet verification.

To simplify the following discussion, we describe this scheme as a graph problem and use the corresponding terminology. Namely, we use the term node instead of packet, and edge instead of hash link. We define the length of an edge as $L(E$_ij) = |i-j|, where $i$ and $j$ are the id's of the corresponding nodes. If packet $P$_j contains the hash of packet $P$_i, we draw a directed edge starting at $P$_i to $P$_j. We call $P$_j a supporting packet of $P$_i. Similarly, an edge points from a packet $P$_k to a signature packet $S$_l, if $S$_l contains the hash of $P$_k. We assume that some of the packets are dropped between the sender and the receiver. All nodes which correspond to dropped packets are removed from the graph. A packet $P$_i is verifiable, if there exists a path from $P$_i to any signature packet $S$_j.

This stream signature scheme has the following parameters:

• Number of edges per node
• Length and distribution of edges
• Frequency of signature nodes
• Number and distribution of incoming edges in signature nodes

These parameters influence the computation and communication overhead, the delay until verification, and the robustness against packet loss. We want to achieve low overhead while retaining high robustness against packet loss and a low verification delay.

To simplify the problem of optimizing all parameters simultaneously, we first focus on the interplay between the number and distribution of edges to achieve high robustness against packet loss. We first consider static edges, which means that all the outgoing and incoming edges of each node have predefined lengths. For example, in a ``1-3-7'' scheme, the node $P$_i has outgoing edges to $P$_i+1, P_i+3, P_i+7, and incoming edges from $P$_i-1, P_i-3, P_i-7.

To simplify the problem even further, we initially assume independent packet loss, i.e. each packet has an equal loss probability.

Instead of computing the probability precisely for each node, we wrote a program to perform simulations. We checked the accuracy of the simulation program on the cases for which we computed an analytical solution: $$ 1-2-4$and$ 1-2-3-4$.\; Our\; simulation\; (with$ 2500$samples\; simulating\; up\; to$ 1000$packets\; before\; the\; signature\; packet)\; had\; an\; absolute\; error\; of\; less\; than$ \pm 2\%$of\; the\; verification\; probability\; for\; these\; two\; cases.$

We ran extensive simulations to find a good distribution of edges withstanding high amounts of dropped nodes. In our largest simulation, we searched through all combinations of six edges per node, where the maximum length of any edge was $51$, and the probability of dropping a node was $60\%$. In our simulation, we assumed that the final seven nodes all existed and that they all contained an edge to the signature node.

The simulation results were illuminating. The most important finding from the simulation study is that the majority of combinations are robust. Figure 8 illustrates this point. The x-axis ranges over the average probability of verification $p$. The figure shows how many combinations had that average verification probability $p$, measured over $400$ nodes preceding the signature packet. The figure demonstrates that most of the combinations have high robustness. In fact, $99\%$ of all combinations give an average verification probability over $90\%$. This finding motivates the use of random edges instead of static edges.

Another interesting result is that the continuous case $1-2-3-4-5-6$ is the weakest combination, and that exponentially increasing edge lengths $1-2-4-8-16-32$ had poor robustness. One of the strongest combinations is $5-11-17-24-36-39$. We show the performance of these three combinations in figure 7. The continuous case has the lowest verification probability, the exponential chain is already much better, and the last case does not seem to weaken as the distance from the signature packet increases.

 
Figure 7: The verification probability for three static cases: Top line: 5-11-17-24-36-39. Middle line: 1-2-4-8-16-32. Bottom line: 1-2-3-4-5-6.  

 
Figure 8: Number of combinations of six hashes that resulted in a given average verification probability. Note that we assume a 60% packet loss probability. 

 
Figure 9: The verification probability for random vs a static case. Top line is random link distribution. Bottom line is 5-11-17-24-36-39. 

The assumption of independent packet loss does not hold in the Internet. Many studies show that packet loss is correlated, which means that the probability of loss is much higher if the previous packet is lost. Paxson shows in one of his recent studies that packet loss is correlated and that the length of losses exhibit infinite variance [24]. Borella et al.draw similar conclusions, furthermore they find that the average length of loss bursts is about $7$ packets [6].

Yajnik et al.show that a $k$-state Markov model can model Internet packet loss patterns [32]. For our simulation purposes, the two-state model is sufficient, since it can model simple patterns of bursty loss well [16, 32]. The main advantage of randomizing the edges, however, is visible when we consider correlated packet loss. Figure 9 shows a simulation with $60\%$ packet loss and where the average length of a burst loss is $10$ packets. We can clearly see in the figure that the verification probability of the static edge scheme drops exponentially, whereas the random edges still provide a high verification probability.