Authenticating Digital Streams


Dan Boneh, Philippe Golle, Nagendra Modadugu


Data files may easily be associated to an author by simply appending a digital signature to the file. However, in the case of streaming real-time data a recipient may need to continually authenticate the stream while receiving the stream.

Some work has previously been done in the area. But the approaches taken have either ignored the fact that some packets in the stream may get lost, or have introduced a fair amount of overhead into the stream. We are looking into novel ideas for minimizing the overhead while taking into consideration that networks are lossy.



We have implemented plugins that are capable of authenticating data streamed over the RealAudio system. We have implemented two structures, one is a simple hash chain authentication mechanism and the other is the mechanism described in Golle's paper. Go to the distribution page to download.

Technical Summary

The simplest solution for authenticating a stream would be to sign each and every packet. This is however not a feasible solution in general as computing say an RSA signature turns out to be computationally too expensive to do on a packet by packet basis. One of our implementations is based on the simple hash chain shown below. In this implementation, the hash of each packet is placed sent with the next packet in the stream (packets are sent in order from left to right). One of the packets in the chain, say every 100th , is signed.

In this scheme, the loss of a packet implies that all the packets prior to it in the chain cannot be authenticated. This scheme works well if the network is very reliable, as the overhead is minimal -- both client the server need only buffer the hash of the previous packet.


The second implementation is based on Golle's paper. The basic structure (shown below) consists of an outer hash chain and an inner tree like structure. This structure can withstand burst packet loss of length approximately three times the number of packets in the inner chain. The main features of the  structure are that the hash of each packet is sent is set with two other packets. As a result, a packet will be un-authenticable only is both the packets that carry its hash are lost. All the packets are not of equal size, the packets on the outer chain contain 6 hashes each and the inner chain packets contain between 0 and 3 hashes each. 

nagendra at
Last modified: Sat Nov 13 15:29:45 PST 1999