Nark: Receiver-based Multicast Non-repudiation and Key Management

Bob Briscoe & Ian Fairman, Bob Briscoe & Ian Fairman, {rbriscoe|ifairman} BT Research, B54/74, BT Labs, Martlesham Heath, Ipswich, IP5 3RE, England
Abstract: The goal of this work is to separately control individual secure sessions between unlimited pairs of multicast receivers and senders while preserving the scalability of receiver initiated Internet multicast for the data transfer itself. Unlike other secure multicast solutions, there are absolutely no side-effects on other receivers when a single receiver joins or leaves a session. Each individual receiver can also reliably prove whether any fragment of the data hasn't been delivered or wasn't delivered on time (e.g. late video frames). Further, each receiver's data can be subject to an individual, watermarked audit trail. The cost per receiver-session is typically just one set-up message exchange with a key manager. Key managers can be replicated without limit because they are only loosely coupled to the senders who can remain oblivious to members being added or removed. The solution requires a tamper-resistant processor such as a smartcard at each receiver. However, generic cards supplied by a trusted third party are used rather than cards specific to each information provider. The technique can be applied to other bulk data distribution channels instead of multicast, such as DVD.

1. Introduction

This paper explores techniques to maintain an individual security relationship between multicast senders and each receiver without compromising the efficiency and scalability of IP multicast's data distribution. We focus on issues that are foremost if the multicast information is being sold commercially. Of prime concern is how to individually restrict each receiver to extract only the data for which it has paid. Secondly, commercial information delivery systems should preferably include the capability for individual proof of delivery. Where both non-repudiation and transport reliability aren't intrinsic to the delivery system, the cost of providing customer support to handle billing complaints is likely to overshadow all other costs. However, where streamed information is concerned, simple proof of reception is not enough. Timely reception must also be provable. Thirdly, of particular concern with multicast information products is prevention or at least detection of unlicensed re-distribution of received information.

We adopt an approach where the key used to encrypt sent data is systematically changed for each new unit of application data. The keys are taken from a pseudo-random sequence seeded with a value initially known only to the senders. When a receiver wishes to join, it requires a trusted third party smartcard. At the end of each receiver's set-up phase, its card is running a key generator seeded with the same value as that of the senders and it contains a policy defining which keys the receiver is entitled to. The smartcard does no decryption; it merely hands out a key whenever a request conforms to the policy. The smartcard can record a summary of which keys it has given out that can be used as a non-repudiable 'delivery note' in the case of delivery disputes.

Thus, whenever a receiver is added or removed, there is zero side-effect on other receivers. A special group key change doesn't have to be initiated because systematic changes occur all the time anyway. No keys need sending over the multicast, therefore reliable multicast isn't required. If key managers are delegated to handle requests to set-up receiver sessions, the senders can be completely oblivious of any receiver addition or removal. Thus, there is absolutely no coupling back to the senders. For stateless key manager scenarios (e.g. pre-payment with no credit) any amount of key manager replication can be introduced. The key managers just give out session seeds and policies in return for pre-payments. Thus performance is linear with key manager replication and system resilience is independent of key manager resilience.

Thus we focus on a pragmatic scenario where evictions from the multicast group are typically planned at session set-up, but still might occur at arbitrary times. Nonetheless, we do cater for the occasional unplanned eviction, although the scheme doesn't scale if the level of its use becomes high. Our thesis is that there are many applications that only rarely require premature eviction, e.g. pay-TV or pay-per-view. Consequently, our scheme typically requires just one set-up message per receiver session. All further security messaging proceeds between the receiver and its smartcard, which acts as a proxy of the key manager. If the receiver wishes to dispute delivery of certain parts of the stream, another message is required at the end of the session to present the 'delivery note'.

In section 2, we discuss requirements and describe related work on multicast key management, non-repudiable receipting and detection of re-multicast. In section 3 we describe the underlying composition of the systems we have implemented to meet all our requirements. Then, in section 4, we describe the design of specialisations we have implemented to achieve each requirement. Section 5 describes how secure sessions are set-up, torn down or modified (e.g. for an unplanned eviction). Section 6 briefly describes our implementation. Finally limitations of the approach are discussed followed by conclusions.

2. Background and requirements

When using Internet multicast, senders send to a multicast group address while receivers 'join' the multicast group through a message to their local router. For scalability, the designers of IP multicast deliberately ensured that any one router in a multicast tree would hide all downstream join and leave activity from all upstream routers and senders [Deering91]. Thus a multicast sender is oblivious to the identities of its receivers. Clearly any security relationship with individual receivers is impossible if they can't be uniquely distinguished. Conversely, if receivers have to be distinguished from each other, the scalability benefits start to be eroded.

2.1 Multicast key management

If a multicast sender wishes to restrict its data to a set of receivers, it will typically encrypt the data at the application level. End-to-end access is then controlled by limiting the circulation of the key. A new receiver could have been storing away the encrypted stream before it joined the secure session. Therefore, every time a receiver is allowed in, the key needs to be changed (termed backward security [McGrew98]). Similarly, after a receiver is thrown out or requests to leave, it will still be able to decrypt the stream unless the key is changed again (forward security). Most approaches work on the basis that when the key needs to be changed, every receiver will have to be given a new key. Continually changing keys clearly has messaging side-effects on other receivers than the one joining or leaving.

We define a 'secure multicast session' as the set of data that a receiver could understand, having passed one access control test. If one key is used for many related multicast groups, they all form one secure session. If a particular receiver leaves a multicast group then re-joins but she could have decrypted the information she missed, the whole transmission is still a single secure session. We envisage very large receiver communities, e.g. ten million viewers for a popular Internet pay-TV channel. Even if just 10% of the audience tuned in or out within a fifteen minute period, this would potentially cause thousands of secure joins or leaves per second.

We use the term 'application data unit' (ADU) as a more general term for the minimum useful atom of data from a security or commercial point of view (one second in the above example). ADU size is application dependent. It may be an initialisation frame and its set of associated 'P-frames' in a video sequence or it may be ten minutes of access to a network game. For performance, an ADU may be only partially encrypted with the remainder in the clear [Kunkel97]. ADU size can vary throughout the duration of a stream dependent on the content. ADU size is a primary determinant of system scalability. If a million receivers were to join within fifteen minutes, but the ADU size was also fifteen minutes, this would only require one re-key event.

However, reduction in re-keying requirements isn't the only scalability issue. In the above example, a system that can handle a million requests in fifteen minutes still has to be provided, even if its output is just one re-key request to the senders. With just such scalability problems in mind, many multicast key management architectures introduce a key manager role as a separate concern from the senders. This deals with policy concerns over membership and isolates the senders from much of the messaging traffic needed for access requests.

We now describe the most scalable of the group key management proposals. Ballardie suggested exploiting the same scalability technique used for the underlying multicast tree, by delegating key distribution along the chain of routers in a core based multicast routing tree [IETF_RFC1949]. However, this suffers from a lack of end-to-end security, requiring edge customers to entrust their keys to many intermediate network providers. The Iolus system [Mittra97] sets up a similar distribution hierarchy, but only involving trusted end-systems. However, gateway nodes in the hierarchy decrypt and re-encrypt the stream to isolate sub-group members from key-changes in other sub-groups. This increases latency and set-up complexity and reduces resilience.

An alternative class of approaches involves a single key for the multicast data, but a hierarchy of keys under which to send out a new key over the same multicast channel as the data. These approaches involve a degree of redundant re-keying traffic arriving at every receiver in order for the occasional message to arrive that is decipherable by that receiver. The logical key hierarchy (LKH) [Wallner97] gives each receiver its own key then creates the same number of extra keys, one for each node of a binary tree of keys with each member's key at the leaves. The root of the tree is the group key under which data is encrypted. When a member joins or leaves, all the keys on their branch to the root are replaced in one long message multicast to the whole tree. Perlman has suggested an improvement, termed LKH+, where a one way function could be used to compute the next key from the existing one [Perlman]. Only the new key would be revealed to the joining member. The one-way function tree (OFT) technique is in the same class of approaches [McGrew98]. Like LKH, all members have their own key, and a binary tree of keys is built over them with the root also being the group key. Because the keys at each intermediate node are a combination of the hashes of the two keys below, rather than being freely generated, Perlman's suggestion cannot be applied. LKH+ is therefore more efficient than OFT in most scenarios. The standardised approach to pay-TV key management also falls into this class [ITU-R.810]. A set of secondary keys is created and each receiver holds a sub-set of these in tamper-resistant storage. The group key is also unknown outside the tamper-resistant part of the receiver. In case the group key becomes compromised, a new one is regularly generated and broadcast multiple times under different secondary keys to ensure the appropriate receivers can re-key. All the key hierarchy approaches send new keys over the multicast itself. As 'reliable multicast' is still to some extent a contradiction in terms, either efficiency is reduced through adding redundant messaging or complexity is increased to cope with losses.

Dillon [Dillon97] falls into the same class of approaches to key management as the current work. Each broadcast document is encrypted using a different key rather than the key only being changed in synchrony with the addition or removal of receiver interest. In the interests of full disclosure, we note that the present work is the subject of a European patent filing [Briscoe97].

2.2 Multicast non-repudiation

The need for proof of delivery is recognised in two taxonomies of multicast security requirements [Bagnall99, Canetti98], but solutions are rarely discussed in the academic literature. Proof of delivery is a very different problem to acknowledgement of delivery. It has to be possible to prove the receiver did indeed receive data when they might deny reception. Pay-TV and pay-per-view systems invariably use the tamper-resistant processing and storage capabilities of the local receiver to record which products or programmes have been requested in order to form a bill at a later time (e.g. [ITU-R.810, Dillon97] as already cited).

The novel aspect of the present work is the ability to prove that individual fragments of an isochronous stream (e.g. video) not only arrived, but arrived in time to be played out, giving suitable perceived quality for a real-time application. Our approach is for the receiving system to only request a key to decrypt the stream if there is sufficient time remaining to decrypt it and still achieve smooth play-out. This is possible because the link between the receiving computer and the smartcard has predictable latency and minimal risk of packet drop unlike the Internet connection between sender and receiver.

2.3 Multicast audit trail

Re-multicast of received data requires very low resources on the part of any receiver. Even if the value of the information received is relatively low there is always a profit to be made by re-multicasting data and undercutting the original price, as proved in Herzog et al [Herzog95].

In general, prevention of information copying is considered infeasible; instead most attention focuses on the more tractable problem of copy detection. It is possible to 'watermark' different copies of a copyrighted digital work. If a watermarked copy is later discovered, it can be traced back to its source, thus deterring the holders of original copies from passing on further, illicit copies. Watermarks are typically applied to the least significant bits of a medium to avoid significantly degrading the quality. Such bits are in different locations with different regularity in different media, therefore there is never likely to be a generic approach [Schneier96]. The most generic scheme discussed to date is Chameleon [Anders97]. In Chameleon a stream is ciphered by combining a regular stream cipher with a large block of bits. Each receiver is given a long-term copy of the block to decipher the stream. In the concrete example given, four 64b words in the 512kB block are chosen by indexing the block with the output of the regular stream cipher. Then all four are XOR'd together with each 64b word of the stream. The block given to each receiver is watermarked in a way specific to the medium. For instance, the least significant bit of every 16b word of an audio stream might be the only place where a watermark can be stored without degrading the content significantly. Because the block is only used for the XOR operation, the position of any watermarked bits is preserved in the output.

Naor et al [Naor98] formalises a pragmatic approach to 'traitor tracing' by proposing a parameter that represents the minimum number of group members that need to collude to eliminate a watermark. The elimination criteria are that none of the conspirators are identifiable, and it is assumed that the copyright owner will want to avoid accusing innocent members. For instance, changing at least the square root of the total number of bits that could hold a watermark in the Chameleon scheme would protect against conspiracies of four or less members.

Watercasting [Brown99] is a novel, if rather convoluted way to embed an individual watermark in each receiver's copy of multicast data. Multicast forwarding is modified by including active networking elements at strategic branch points. These elements drop redundant data inserted into the original stream in order to produce a different drop pattern on each forwarded branch. A chain of trusted network providers is required for watercasting, each of which has to be willing to reveal their authenticated tree topology to each sender.

In this paper, for completeness, we report how it is possible to add an audit trail back to the copier of multicast information using watermarking. Our approach is not novel in this respect, simply re-using Chameleon. However, we include it to demonstrate our modular approach to the addition of mechanisms.

2.4 Other requirements

Beyond the three requirements we have focussed on so far, the taxonomies we have already cited include many other possible combinations of security requirements for multicast. We have placed sender authentication outside the scope of this paper, but its importance merits a brief survey of the literature. A sender may merely need to prove it is one of the group of valid receivers in which case use of the group encryption key suffices. If the group of valid senders is different from that of the receivers, a message authentication code (MAC) on all sent data based on a single key shared by the senders is sufficient and efficient. If receivers require each sender to authenticate their messages individually, public key signing leads to an unscalable solution because of the sheer volume of heavy asymmetric key operations required. Balenson et al [Balen99] and Canetti et al [Canetti98] both provide up to date reviews of more efficient approaches to this problem.

So far we have focussed on the scenario where the data is an ordered stream and access is given between some start and some later end point. A more random access approach might be required for non-sequential application name spaces [Fuchs98]. However, often we cannot generate a number at position n in the sequence if we have generated the number at position m where m > n, unless we store all numbers in the sequence up to the mth term or regenerate the sequence. Storing numbers in the sequence or regenerating the sequence is usually impractical for devices that are as limited as smartcards. For random access to any point in a sequence, in the longer version of this paper [Briscoed99] we present a fast algorithm to generate any key from a seed as an alternative to keyed hash algorithms.

2.5 Implementations

Many of the schemes discussed above are theoretical works. Known exceptions are Iolus and Chameleon. A report on implementation experience with LKH is provided by Boxall [Boxall98] and Shoup et al report on their implementation of session key distribution using smart cards [Shoup96].

3. Basic Scheme

In explaining the basic scheme we will firstly give a concrete example of how it would be used and then give a description of the core of the scheme upon which other features can be built.

3.1 A Concrete Example

Our example is of a content provider who wishes to multicast streamed video and charge viewers for watching it.

The content provider first divides the video stream into units that potential viewers can use to select what they want to see. The obvious unit here is a 'TV channel' or may-be a 'TV programme'. Each of these units is given an ID termed the session ID. Next the content-provider sets up a video server which has access to the video in a streamable form. As part of the set-up process a seed is generated and a formula chosen. This is used to generate symmetric encryption keys based on this seed for encrypting and decrypting the data. The content provider also sets up another key management server to hand out these seeds in return for payment. The sender passes on the programme information, including the seed and formula, to that server. The content provider then advertises the programmes on the channel, perhaps using a web site or email, with the session ID and the key management server being used to uniquely identify the channel to the system. When the broadcast time arrives the video server starts streaming. Each frame of video is given it's own ID within the channel and a corresponding key is generated from this ID, the seed key and the formula. This new key is used to encrypt each frame before it is sent.

Now we consider the receiver's side. The user has a computer that is connected to the network and a smartcard reader. They also have a smartcard which contains it's own public/private key pair and has been certified by a trusted third party. The private key is unavailable to the user. The user finds a programme they want to watch on a web site and clicks on the "set-up" link for that programme. The link URL downloads a file containing the information that is needed to join the session and the browser passes this on to the user's video player software (which has been configured as a browser helper application). The video player passes this information on to a socket factory, the internals of which are outside the scope of this paper - see Flexinet [Hayton98]. The essential point is that a communications stack is built containing a decrypter. When the decrypter is set up it in turn sets up a key generator in the smart card, which in turn needs a seed and a policy. The decrypter requests these from a key server in return for a payment. They arrive encrypted with the smartcard's public key and are passed to the key generator.

The socket factory then passes a socket reference back to the video application which need not be aware that decryption is taking place beneath it. The video application simply uses this socket to join the multicast. When the TV programme starts, the socket waits until it receives all the data for each frame, then asks the smartcard for the key for that particular frame, decrypts the frame and passes the frame on to the video player application for decompression and display. The smartcard can record the number of keys that were generated per programme and a summary of which keys were passed out.

After the programme finishes, there is no need to do anything further unless reception was poor or incomplete. The receiver can ask the smartcard to produce a 'delivery note' for the partially received programme which the smartcard signs with it's private key. This can be forwarded on to the payment server to prove the right to a refund.

3.2 Core Set-up

The core scheme involves a sender sending data via some distribution mechanism to zero or more receivers. The sender divides the data stream into a number of application data units (ADUs). Each ADU sent in a session has an ADU ID associated with it. These IDs are typically numeric. For the session there exists a mapping of IDs to keys and, before it is sent, the data in an ADU is encrypted using the key associated with the ADU's ID. Any receiver receiving data in the session must know the ID to key mapping used for that session and uses it to find the key for any ADUs it receives and wishes to decrypt.

Figure 1 - Sending Stage - Sender

The process of sending data is as follows:

  1. Sending application passes an unencrypted ADU on to the communications system.
  2. The communications system requests the next ID from the ID generator...
  3. ...which returns a new ID.
  4. The communications systems requests the key for that ID from the key generator...
  5. ...which returns the key.
  6. The communication system passes the ADU and the key on to the encrypter...
  7. ...which returns an encrypted ADU.
  8. The communications system passes the encrypted ADU and the ID on to the send point for distribution.
Note that the scheme is independent of the distribution mechanism. We use Internet multicast, but it could be DVD or other media.

Figure 2 - Sending Stage - Receiver

The process for receiving data is as follows (note that smartcard security is only added when we discuss the variations later):

  1. The receive point passes on an encrypted ADU and ID it has received from the distribution mechanism to the communications system.
  2. The communications system requests the key for that ID from the key generator...
  3. ...which returns the key.
  4. The communications system passes the encrypted ADU and the key on to the decrypter...
  5. ... which returns an unencrypted ADU…
  6. …which is passed on to the ADU to the application for processing.

4. Variations

4.1 Multicast Key Management

The scenario here is the situation where we have an ongoing multicast session and where receivers joining the session are only allowed to receive a portion of the data. An example of this might be where the multicast was a video broadcast and where a receiver might pay to receive an hour or a days worth of video.

Figure 3 - Multicast Key Management

In this case we add a key limiter that limits the production of keys, i.e. to a certain number or perhaps to a particular range of IDs. The key limiter and the key generator are placed within the tamper-proof processor. In Figure 3, a key is returned by the key generator only if the ADU ID passes the key limiter's test. The limiter will usually also be required to restrict its output to one response per key. This protects against the same card being shared around multiple receivers as a relatively convenient way to decrypt the same data multiple times rather than passing all the keys around. This would require internal receipting capabilities similar to those described in the next section.

4.2 Non-repudiation

In this scenario we are concerned with being able to confirm how much data an application received. Sending acknowledgements for each ADU is impractical, especially as the number of receivers grow large. Also, this does not prevent the receiver trying to fool the sender by not sending acknowledgements for ADUs it has received. What we do in this case is to produce a 'delivery note' of all the data received in a session. If, at the end of a session, we need to confirm how much data was received by an application in a particular session, we can query its secure processing environment and get the 'delivery note' for that session.

Figure 4 - Non-repudiation

In this case we can create receipts for every ADU decrypted by intercepting every return of a key and recording the ADU ID in a file. For ordered streams, the receipting storage format only needs to be a simple index to the last key given out, plus a list of any exceptions. If random access to any ADU is envisaged, a block of bits, one for each ADU, would be required to record which keys had already been given out. More efficient tree-based variants are possible to reduce storage requirements in most realistic scenarios.

If different types of ADUs in a stream require different treatment with respect to security it is simplest to create a separate secure session for them. For instance, high quality transmission costs for adverts might be refunded only if a delivery note is returned to prove they were at least decrypted if not watched (e.g. a hash of the decrypted frames might be required). These would form a sub-session with a different policy in the smartcard.

4.3 Audit Trails

The problem this variation helps to address is that of a receiver in the session colluding with other receivers that are not part of the session by sending them keys or decrypted data. There are two variants: on-card and off-card watermarking, the latter depicted in Figure 5. In the first variant only the plaintext data is watermarked therefore each ADU key is never revealed outside the smart card. In the second variant, the keys themselves are watermarked so both the keys and the data can be revealed outside the card.
If the watermarked keys or data are then sent on to other machines and detected later, it is possible to establish the identity of the source of the "leak" from the watermark. This variation assumes that the data is watermarkable, e.g. images.

Figure 5 Off-card Watermarking

On-card watermarking is only feasible with a fairly highly powered tamper-resistant cryptographic co-processor. It is impractical with smartcards due to processing and memory limitations. Off-card watermarking needs only light card resources. An approach such as Chameleon [Anders97] as described earlier is preferred as long as there is sufficient memory on the receiver to hold the whole watermarked key block (about 512kB in the concrete example). The following steps for off-card watermarking assume the sender encrypter unit produces its stream cipher by combining a standard cipher with an unwatermarked version of the long-term key-block, as in Chameleon.

  1. The receive point passes the encrypted ADU and ADU ID into the communications system.
  2. The communications system passes a) the ID into the key generator and b) the encrypted ADU into the decrypter.
  3. The generator passes the intermediate key for that ID into the decrypter.
  4. The decrypter passes the intermediate key to the watermarker
  5. The watermarker uses the intermediate key as an index into a long term watermarked key block to return the key to the decrypter
  6. The decrypter uses the key to decrypt the ADU and passes it to the communications system…
  7. …which passes the watermarked ADU on to the application.

4.4 Multiple Sender Systems

This variation addresses the issue of having many senders within a session. For simplicity’s sake we might want to use the same key generator for information sent from all senders, although this would require that the key generator would be able to generate keys for any order of IDs (which would be true in the general case of senders not being synchronised). If we wished to have key generators that required IDs in order or we wished to produce individual delivery notes for each sender (see Non-repudiation) then we need to maintain a number of key generators, one for each sender. To identify each sender we would have to generate a unique ID for each one, i.e. for information sent across the Internet we could use the IP address and port number which is sent as part of the packet. To seed the sequences we can then use a common seed for all senders within a session which is then combined with the unique ID in some way, i.e. XORed with the common seed, which is then used as the seed for that sender. The receiving stack now uses a switch to retrieve the correct key for the data unit. Of course, the sending stack need only maintain a single key generator for all data it sends to a session.

Figure 6 - Multiple Sender Systems - Receiver

5. Session Control

For any of the above schemes can be used it is necessary to have some auxiliary functions implemented.

In the follow sections this notation is used:

  1. sign(k,d) - d signed with key k (i.e. d and the signature of d with k)
  2. enca(k,d) - d encrypted asymmetrically with key k
  3. encs(k,d) - d encrypted symmetrically with key k

5.1 Tamper-proof Processor Confirmation

The object here is to confirm that the tamper-proof processor is one that the sender can trust. We assume that every secure processing environment leaves the factory with a securely stored private key and a public key that has been signed by a trusted third party (TTP) trusted by the sender.
  1. Sender generates a random string r (a nonce)
  2. Sender sends r to receiver
  3. Receiver sends r to secure space
  4. Secure space signs r with private key s to produce sign(s,r)
  5. Secure space returns sign(s,r) and public key p signed with the TTP's private key t (producing sign(t,p)) to receiver
  6. Receiver returns [sign(s,r), sign(t,p)] to sender
  7. Sender checks TTP is one it trusts
  8. Sender checks sign(t,p) with TTP (either by invoking TTP server or using cached TTP public key)
  9. Sender checks sign(s,r) with p.

5.2 Session Set-up

The sender needs to set-up the keying system so that it can generate a sequence of numbers for decoding each packet. This sequence will be some chaotic/pseudo-random sequence.
  1. Sender generates a seed value v.
  2. Sender generates a session key k.
  3. Sender encrypts v using secure space's public key p producing enca(p,v).
  4. Sender sends [k,enca(p,v)] to receiver.
  5. Receiver sends [k,enca(p,v)] to secure space.
  6. Keying system sets packet counter to zero.
  7. Keying system deciphers enca(p,v) using secret key s.
  8. Keying system initialises sequence generator with v.
For multicast key management the sender will also send some information to limit the production of keys, such as a limit on the maximum number of keys.

This describes a simple scenario where a single sequence generator can create an unlimited sequence of numbers and create a single delivery note type. More realistically the session information would include:

Sent in plain:

Sent encrypted: In this scenario there are a limited number of sequence generators and delivery note types that can be used as it is identifiers that are being sent over as part of the session information. Alternatively a secure class loader could be implemented that would allow new sequence generators and delivery note types to be uploaded into the encryption system. This would offer the most future-proofing.

Another aspect of session set-up is session amendment. The user may pay to receive a certain amount of data and then later on pay for some more. This would ideally be handled by updating the session information (probably just increasing the maximum number of keys to be generated) while the session is active.

5.3 Session Tear-down

Sessions simply end when the sender stops sending data or the key generator stops generating keys. In the case of non-repudiation though there is a need to retrieve the delivery note from the secure environment. The following steps allow this.
  1. Receiver requests delivery note for session key k from keying system.
  2. Keying system generates delivery note for session key k, ck.
  3. Keying system signs ck with private key s giving sign(s,ck).
  4. Keying system returns sign(s, ck) to receiver.
  5. Receiver sends sign(s, ck) to sender.
  6. Sender checks sign(s, ck) against public key p of keying system known to be used by the receiver (database lookup).
  7. Sender refunds if necessary.

5.4 Access Revocation - Poison Pill

It may be desirable for a session controller to be able to modify or revoke a receiver’s membership of a session. The solution detailed below assumes that each member of the session has an ID (or several IDs) within the session, although this ID does not have to be unique to the member (if it is not unique then the ID obviously represents a group). It also requires that the smartcard will not co-operate if the required control data is not passed to it with each key request.

This is a probabilistic approach. Every time an ADU is sent it contains an encrypted control message and secure space ID which must be passed into the secure space along with the key ID to obtain the key. If the secure space ID(s) contained in the encrypted block refer to this particular space then it checks the flags. If the stop flag is set then the card 'commits suicide' - no more keys are passed out. If the contact sender flag is set then the secure space does a remote procedure call to the sender (or the sender's representative) and will not give out more keys until it has a new key generation policy. Alternatively more general control messages might take the place of these two flags.

If several users need to be thrown out of the session then their secure space IDs will be rotated through different packets.

ADU format:

  1. Signature of Hash (2)
  2. Hash of 3, 4, 5, 6
  3. ADU  ID
  4. Stop flag (y/n) (encrypted)
  5. Contact sender flag (y/n) (encrypted)
  6. secure space IDs (encrypted)
  7. ADU data (encrypted)
The stack passes 1, 2, 3, 4, 5 and 6 into the secure space to receive the key for 7.

If the length of the control message and number of secure space IDs is variable then there needs to be an unencrypted field before the flags stating the total length of the control message and secure space IDs.

6. Implementation

An implementation of this system was created for demonstration purposes. It was written in Java 1.1 and used the Cryptix 3.0.3 [Cryptix] library for cryptography. Aspects of the system can easily be changed: the formula used to generate keys (one based on the logistic mapping [Gleick87] has been implemented); the policy for limiting keys (policies for producing fixed numbers of keys and keys for a range of IDs have been implemented); the cryptographic system (DES was implemented); the receipt type (one simple receipt was implemented). The prototype did not use any smartcards but those aspects of the design are cleanly separated from the rest of the system. Simple graphical applications were written to demonstrate the sender and receiver roles.

7. Limitations and further work

Our  approach relies on the tamper-resistance of smartcards. Products are continually being produced with improved tamper-resistance features, but there will always be attrition between the designers of tampering techniques [Anders96] and the designers of resistance to them. The need to regularly replace the smartcard is therefore an inherent weakness in our scheme. Indeed, the fact that a smartcard is needed at all, is in itself a major impediment to take up of the scheme. We have tried to mitigate this barrier by designing for a generic trusted third party card (e.g. a Java card), rather than one tailored to a specific service provider.

The non-repudiation aspect of this work is only useful in a commercial model where there is an incentive for the receiver to volunteer the delivery note to the information provider. Such scenarios are easy to imagine, but this means the capability is not universally useful. For instance, it would not be possible to give away the stream of information then ask each receiver to volunteer their delivery note to calculate how much they should pay. The beneficial corollary is that it is difficult to get the smartcard to give out thousands of keys off-line in order to break the seed. The smart card won't give out any keys if it doesn't have a key limiter policy and if it does have a policy, it will only give out keys the user has paid for.

This paper contains no formal security analysis of the strength of the schemes employed. A number of questions are left unanswered, such as whether the seed of a pseudo-random sequence becomes easier to predict, the more values from the sequence are revealed.

We must also admit to the standard limitations that apply to most other work on copyright protection. A watermark-based audit trail is only proof against small numbers in collusion and it only helps detection not prevention. Also, traitor tracing relies on finding the watermarked data in the first place; a problem that this paper and others on the subject invariably leave unresolved.

Regarding further work, we claimed in the abstract that this approach could be applied to other means of bulk data distribution than multicast, such as DVD (digital video/versatile disk). We envisage a scenario where data on the DVD would be encrypted with a stream cipher such that it would be indistinguishable from a multicast stream once it was read from the disk. As long as the initial set up with the smartcard had occurred on-line, the rest of the DVD could be played off-line, only requiring interaction with the smartcard, not the network. Any final 'delivery note' of exactly what had been accessed would then be available to present to the provider of the DVD. In a similar vein, policies and seeds to load into the smart card could be supplied on various media other than over the Internet. All these scenarios and more are introduced in [Briscoe97], but we have done no specific design or implementation work on them.

8. Conclusion

We have presented a number of modular mechanisms to enable secure sessions tailored to each individual multicast receiver while at the same time not compromising the inherent scalability of Internet multicast, achieved through loose coupling between senders and receivers. Unlike other schemes, we typically require absolutely no coupling at all from receivers back to senders but still create a security relationship between each receiver and a key manager replica. The key managers can be highly replicated as they require no coupling back to the sender. As long as a stateless commercial model is required (e.g. pre-payment rather than credit), key manager replication is limitless. Further, as members join and leave, there are absolutely no side-effects on other receivers, unlike traditional multicast key management schemes.

All this loose coupling is made possible by a simple technique where multicast senders systematically change the group encryption key rather than only changing it whenever there is a change to the group membership. This innovation is driven by the insight that there will always be a minimum application data unit (ADU) granularity, within which there is no commercial advantage to changing the group key. The traditional approach has been to group together membership change events within the timespan of an ADU and then drive key changes dependent on whether none or some events have occurred within each timeslot. Instead, by systematically changing group keys whether or not it is necessary, the whole system can rely on the key changes and not require tight coupling back to the senders. A further advantage of this approach is that there is no need to send control messages over the multicast channel itself. Thus no reliable multicast mechanism is assumed or required and no complexity is involved when messages are dropped. The only exception is the rare need to send a 'poison pill', which merely requires statistical delivery.

In order to distribute the load of key management further, we require each receiver to operate a smartcard, into which the information provider can install a key generator capable of mirroring the systematic key generation of the senders. We prefer generic smartcards certified by trusted third parties, so that any key generator can be installed at session set-up. This mitigates the barrier created by the need for each receiver to obtain a card, as it can be re-used for multiple services. A policy is installed into the smart card at session set up to control which keys it will give out to its receiver. The details depend on the specifics of the wider application.

Further, we have shown by implementation that it is even possible to prove timely reception of real-time data units using this arrangement. The smart card records which keys it has been asked for and if a packet arrives late, the receiver simply refrains from asking for the key. Thus, the smartcard generates a delivery note that can later be used by the receiver to prove that only a certain number of data units were usefully decrypted.

We have also described how it would be possible to combine the above approach with a key watermarking scheme such as 'Chameleon'. This provides a small but significant deterrent against a receiver giving away or re-selling either the keys or the decrypted data, because both are watermarked in such a way as to trace that receiver.

We believe these mechanisms (combined with sender authentication approaches described elsewhere) provide a soundly engineered basis for a number of very large scale commercial applications built over Internet multicast. We have also briefly described how the same techniques could usefully be applied to other bulk data distribution mechanisms, such as DVDs. The techniques also have application where protection of information security rather than value is required.

9. References

[Anders96] Ross Anderson and MG Kuhn, ""Tamper Resistance - A Cautionary Note", in proceedings of the second USENIX Electronic Commerce Workshop (Nov 96) pp 1-21 <URL:>

[Anders97] Ross Anderson & Charalampos Manifavas (Cambridge Uni), "Chameleon - A New Kind of Stream Cipher" Encryption in Haifa (Jan 1997), <URL:>

[Bagnall99] Pete Bagnall, Bob Briscoe & Alan Poppitt, (BT), "Taxonomy of Communication Requirements for Large-scale Multicast Applications", Internet Draft (work in progress), Internet Engineering Task Force (17 May 1999) <draft-ietf-lsma-requirements-03.txt>

[Balen99] D. Balenson, D. McGrew & A. Sherman (TIS Labs at Network Associates), "Key Management for Large Dynamic Groups:  One-Way Function Trees and Amortized Initialization", February 26, 1999, <draft-balenson-groupkeymgmt-oft-00.txt>

[Ballard95]  Tony Ballardie and Jon Crowcroft (UCL), "Multicast-specific threats and counter-measures," Proceedings of the Internet Society 1995 Symposium on Network and Distributed System Security 16-17 Feb 1995, San Diego, California, IEEE Computer Society (1995), 2-14. <URL:>

[Boxall98] Sarah Boxall (Cambridge Uni), Report on industrial placement (Sep 1998).

[Briscoe97] Bob Briscoe and Ian Fairman (BT), "Multicast Key Management", European patent publication no. EP98304429.8 (Mar 97).

[Briscoed99] Bob Briscoe and Ian Fairman (BT), "Nark: Receiver-based Multicast Key Management and Non-repudiation", BT Technical Report (Jun 1999), <URL:>

[Brown99] Ian Brown, Colin Perkins & Jon Crowcroft (UCL), "Watercasting: Distributed Watermarking of Multicast Media", submitted to Globecom '99, Rio de Janeiro, (December 1999),  <URL:>

[Canetti98] Canetti, R. & B. Pinkas, "A taxonomy of multicast security issues," Internet Draft (work in progress), Internet Engineering Task Force (May 1998), <URL:draft-canetti-secure-multicast-taxonomy-00.txt>

[Cryptix] Cryptix library, <URL:>

[Deering91] S. Deering, "Multicast Routing in a Datagram Network," PhD thesis, Dept. of Computer Science, Stanford University,

[Dillon97] Douglas M Dillon (Hughes), "Deferred Billing, Broadcast, Electronic Document Distribution System and Method", International patent publication no. WO 97/26611 (24 July 1997).

[Fuchs98] M. Fuchs, C. Diot, T. Turletti, M. Hoffman, "A Naming Approach for ALF Design", in proceedings of HIPPARCH workshop, London, (June 1998) <URL:>

[Hayton98] Richard Hayton, Andrew Herbert & Douglas Donaldson, (APM), "FlexiNet - A flexible component oriented middleware system", in proceedings of SIGOPS'98 (1998), <URL:>

[Herzog95] Shai Herzog (IBM), Scott Shenker (Xerox PARC), Deborah Estrin (USC/ISI), "Sharing the cost of Multicast Trees: An Axiomatic Analysis", in Proceedings of ACM/SIGCOMM '95, Cambridge, MA, Aug. 1995, <URL:>

[Gleick87] James Gleick, "Chaos", 1987, ISBN: 0749386061

[IETF_RFC1949] Tony Ballardie, "Scalable multicast key distribution", Request for Comments (RFC) 1949, Internet Engineering Task Force (May 1996) <URL:rfc1949.txt>

[ITU-R.810] ITU-R Rec. 810, "Conditional-Access Broadcasting Systems", (1992) <URL:>

[Kunkel97] Thomas Kunkelmann, Rolf Reinema & Ralf Steinmetz (Darmstadt Tech Uni), "Evaluation of Different Video Encryption Methods for a Secure Multimedia Conferencing Gateway", 4th COST 237 Workshop, Lisboa, Portugal, Springer Verlag LNCS 1356, ISBN 3-540-63935-7 (Dec 1997), <URL:>

[McGrew98]  McGrew, David A., & Alan T. Sherman, "Key establishment in large dynamic groups using one-way function trees," TIS Report No. 0755, TIS Labs at Network Associates, Inc., Glenwood, MD (May 1998).  13 pages.

[Mittra97] Suvo Mittra, "Iolus: A framework for scalable secure multicasting," Proceedings of the ACM SIGCOMM '97, 14-18 Sep 1997 Cannes, France.

[Naor98] Moni Naor & Benny Pinkas (Weizmann Inst of Sci, Rehovot), ''Threshold Traitor Tracing'', CRYPTO '98. <URL:>

[Perlman] Radia Perlman, observation concerning LKH [McGrew98] from the conference floor - termed "LKH+"

[Schneier96] Schneier B, "Applied cryptography", 2nd Edition, John Wiley & Sons (1996).

[Shoup96] V. Shoup and A.D. Rubin, "Session Key Distribution Using Smart Cards", in Proc. of Eurocrypt'96 (1996), <URL:>

[Wallner97] Wallner, Debby M., Eric J. Harder, and Ryan C. Agee, "Key management for multicast: Issues and architectures,"  IETF Internet Draft (work in progress) (15 Sep 1998) draft-wallner-key-arch-01.txt