Efficient, secure multicasting with minimal knowledge

Background of the invention

1. Connected registrations

This application is related to U.S. Application No. 09 / 009,475 filed January 20, 1998, issued under No. US-A-6,049,878, entitled "Efficient, Secure Multicasting with Global Knowledge," by the inventors of the same Application was invented and assigned to the assignee of the present invention.

Second Field of the invention

The present invention relates to general group data communications, and more particularly to protecting multi-destination communications over a non-secure communication channel.

Third Relevant background

Distributed applications such as multimedia conferencing, computer-aided collaboration, distributed processing, remote inquiry, and diagnostic systems for medical applications depend on efficient information sharing among multiple participants. Multi-destination communication and data exchange over a public network are essential for such applications. This type of communication will hereinafter generally be referred to as "multiple transmission" or Be referred to as "multicast". Some applications, which are referred to hereafter generally as "broadcasting applications", are characterized by a small number of sending subscribers and a large, dynamically changing group of receiving subscribers. Other applications, referred to hereinafter as "conferencing applications", include a large number of sending and receiving participants.

When a group of people wants to communicate through a public network, such as the Internet, in a conference, each message sent out by one of the participants is received by all other participants. The mechanism used to perform this communication is called multicast. Any Internet user or user with access to a public network can join a multicast communication group and will then receive all messages sent to that group. In addition, every Internet user will be able to send messages to the whole group.

Multicast is fast becoming an important communication mode and an effective platform for building group-oriented services. To be used for secure or reliable communication, existing multicast techniques must be supplemented with tools to protect (ie, encrypt and authenticate) the traffic, control participation, and restrict access by unauthorized users.

An example of a known multicast coordination system is that described in European Patent EP-A-0 776 107 of Xerox Corporation. This describes a multimedia coordination system that provides secure multimedia communication channels in a collaborative network environment. The infrastructure of the system includes a plurality of client workstations connected to a central server using point-to-point network connections. The central server contains a steady virtual world of network locations in which objects are located. The client workstations multicast their audio and video data over the network to defined recipients after receiving a multi-class address and an encryption key for a particular multicast channel. To protect the confidentiality of any communication and the integrity of the coordinate system, each client workstation retains significant control over distribution and reception of audio and video data because multicast transmission is associated with particular user interface elements.

The need for secure electronic information exchange over an unsecured public network is becoming increasingly apparent. Compared to traditional unicast (ie point-to-point), multicast is probably more vulnerable. Multicast transmissions, due to the fact that the message may be propagated over much of the network, present much more possibilities for intercepting the traffic. When an attack occurs, a large number of multicast participants are affected.

Further, because multicast addresses are often known, it becomes easier for an attacker to attack. Further, multicasting typically involves a large number of authorized users, making it easier for a group of covert members (or a single attacker posing as a group of legitimate users) to attempt attacks in parallel. While secure unicast communications are well understood, previous attempts at secure multicast communication have encountered difficulty in standardizing on large groups and handling groups with highly dynamic membership.

To assist in obtaining secure electronic information exchange, each network security protocol should allow authorized subscribers to securely communicate over an insecure network under conditions where it is suspected that an attacker is capable of reading, inserting, modifying, and deleting unprocessed communications. Typically, this protocol is achieved by providing a security association between the authorized participants through authentication and key exchange. The security association defines a set of encrypting material shared only by the authorized participants and used for a variety of security tasks, such as authentication, data secrecy, and integrity verification.

In a multicast scenario, the security association between subscribers must be dynamic to support subscriber changes. A secure multicast communication group must ensure that subscribers are allowed to participate only during periods during which they are authorized. A subscriber may be authorized to participate in secure multicast for some time periods and may not be authorized for other periods of time. For example, for a paid program access, a receiver is only authorized for the time periods for which payment was made. The security association and the group-encrypted material that defines it must be changed each time a subscriber joins or leaves the multicast group. This change is necessary to ensure that an incoming subscriber is unable to understand data that has been previously multicast and that the leaving entity is unable to continue to read the miscast data after its authorization expires. The management and distribution of dynamic security associations and encrypting material is a fundamental difficulty with a secure multicast protocol.

Applied communication systems need to create a reasonable economy of the network. By economics, it is meant that the steps taken to ensure secure communication do not add an unordered amount of extra traffic consuming a bandwidth without transferring "payload" information (e.g., application level data) between subscribers. For the foreseeable future, all communications networks will have a bandwidth cap that will provide a premium to efficient communication systems. Thus, it is desirable that the security procedures require minimal communication between subscribers to perform key management. In fact, in some scenarios, such as television or radio broadcasting, only a one-way channel will be available in case the need for minimal subscriber communication is at the top.

Efficiency also means that the steps taken to ensure secure communication do not impose an unacceptable computational and data structure burden on subscribers. Key management and encryption / decryption processes require participants to perform some additional calculations to obtain secure communications. These processes also require subscribers to implement data structures (ie Tables, key storage areas, and the like) which may be of considerable size. It often happens that the number, size, and / or complexity of these computations and data structures increases as the number of subscribers in the multicast communication group increases. In many cases, the complexity increases much faster than the number of participants, which makes the security process unscalable, as these calculations and data structures are costly. Increasing complexity results in lower performance and / or higher hardware and software costs for each participating entity.

In order to achieve efficient private communications over the network, all subscribers in the group must share secret information (ie, key information). The manner in which this secret information is shared and maintained throughout the life of the group is a major feature of the present invention. Earlier applications can continuously establish unicast connections between a sender and all recipients to update security associations and exchange key information. Such continuously required unicast connections are not suitable for large groups. To change a key, many messages must be generated or a message must be handled by intermediate skips, which is not efficient. Taking a large group, where subscribers can continually go and leave, and where the actual key for each issue or access needs to be changed to maintain confidentiality, the computational resources may be inadequate if an extensive calculation (such as one with a public key cryptography) is needed.

An example of a key management system that focuses on unicast communications is simple key management for Internet protocols (SunScreen ™ SKIP, SunScreen is a trademark of Sun Microsystems, Inc.). SKIP is a certification-based key management scheme with a public key that provides group key management for Internet protocols. Earlier multicast implementations of SKIP create a single multicast group and do not automatically handle key changes as subscribers join or leave the group. SKIP, which is designed to be application-independent, can be incorporated into the IP Security Protocol (IPSP) of the IPV6. Using certified Diffie / Hellman keys, SKIP avoids the need for real session setup by keeping "soft" session state information, which can be discarded and reproduced if necessary, and avoids the need for pre-communication between two participating ends to obtain traffic keys and to update. This is an advantage of SKIP, which is particularly suitable for connectionless datagram protocols, such as the Internet Protocol. In the SKIP system, each participant has the ability to construct a shared secret based solely on knowledge of the other participants' public keys combined with their own private key (ie, information needed for symmetric encryption).

Multicast security logs exclude various types of scaling errors. A first type of error occurs when the protocol allows the action of a single member that affects the entire group. The second type of error occurs when the protocol can not handle the group as a whole and instead needs to consider the conflicting needs of each member on an individual basis. This requires point-to-point or unicast communication with each subscriber, which rapidly reduces efficiency as more subscribers join. There is a need for a multicast system that solves these and other scaling problems that exist in the prior art.

A secure multicast framework called Iolus has been proposed that addresses some of these scaling problems by discarding the idea of ​​a single planar secure multicast group. Iolus instead replaces the notion of a secure distribution tree. The secure distribution tree includes a number of smaller secure multicast subgroups hierarchically arranged to provide a single virtual secure multicast group. Since each subgroup is managed relatively independently, the Iolus system is scalable. Each subgroup in the secure distribution tree has its own multicast group and can be created and managed using a suitable multicast routing protocol. A feature of the Iolus system is that there is no global group key or secret information shared by all subgroups. So it is necessary for Iolus to trust third parties such as routers or other network components. Thus, only its local subgroup is affected when a member joins or leaves. However, since no global secure information is shared among all the participants, re-encryption is not optimal. Furthermore, data sent in the system must be re-encrypted each time they move to a different subgroup, thereby increasing the overall computation of the system.

Extensions to the conventional Diffie-Hellman key exchange have been proposed, in which participants collaboratively compute a common session key. In a first example, the subscribers are logically arranged in a ring, and all subscribers in a multicast group connect at the same time. Participants participate in n-1 key exchange rounds (where n is the number of group members). In a given round, each participant increases the previously received intermediate key value to the order of its own exponent and forwards the result to the next participant. After n-1 rounds, each participant holds the same key. This protocol involves high latency, is computationally annoying for large groups, and is primarily suitable for static key distribution.

A more efficient protocol uses point-to-multipoint broadcast messages and performs in only three rounds. In the first round each participant chooses a random exponent ri, calculates a value zi = ari (mod p) and sends zi. Secondly, each participant calculates and sends Xi = (zi + 1 / zi-1) ri (mod p). In the last round, each party can compute the conference key Ki = (zi-1) nri * Xin-1 * Xi + 1n-2 * ... X'-2)) (mod p). This key is the same for all participants.

Although this protocol is about as fast as RSA and as secure as the Diffie-Hellman problem, it is difficult to use in a dynamic group. All members must keep transitional states for possible changes in group membership, otherwise each addition or leaving must be considered a new group, and all three rounds must be redone. Collaboration among all participants, including n reliable point-to-multipoint messages, is also required.

Yet another example provides the ability to distribute session keys in dynamic groups, where a "group manager" entity has to perform O (n) pots for each group change. While this protocol provides a way to distribute a session key in highly dynamic groups, the solution does not scale well with large groups, and messages tend to grow in a forbidden manner.

The need remains for a group data communication method and apparatus that provides secure multi-destination communications over a non-secure communication channel in an efficient manner.

Summary of the invention

In short, the present invention includes a secure multicast system that includes a plurality of subscribers that can send and / or receive multicast messages. A traffic distribution component is coupled to the participating entities, the traffic distribution component supporting recipients at multiple destinations. A group key management component uses a first key shared with all other participants and a number of second keys, each of which is shared with a set of subgroups, the first and second keys being stored and maintained in a group key database. The group key database is implemented in a non-hierarchical, flat manner.

In a first implementation, the group key management component is implemented in a distributed fashion among a plurality of subscribers such that the group key database is implemented in a distributed data structure. In a second implementation, the group key management component is centralized so that the group key management component has global knowledge of shared key information without knowing which subscribers share that key information.

Brief description of the drawings

Figures 1a and 1b illustrate in block diagram form exemplary embodiments of a secure multicast mechanism according to the present invention;

Fig. 2 shows in block diagram form exemplary component parts of a secure multicast system according to the present invention;

Fig. 3 shows a key database according to the present invention;

Fig. 4 shows a detailed example entry from the database of Fig. 3;

Figures 5 to 7 show in the form of block diagrams a key blending feature according to the present invention; and

Fig. 8 illustrates an exemplary data packet used to communicate information in accordance with the present invention.

Detailed Description of the Preferred Embodiments

Proposals for multicast security released to date are complex, often require trust in network components or are inefficient. The present invention includes a number of approaches to achieving scalable security at e.g. An Internet Protocol (IP) multicast, and to provide group-wide confidentiality and authentication. The present invention is usefully applied to multi-subscriber applications in an efficient manner, allowing members of highly dynamic groups of any size to participate.

The present invention will be described in terms of a secure multicast system and protocol, but is more generally considered a group communication security protocol. The system and method of the present invention provide several useful features including: confidentiality of far-transmitted messages, the ability to use untrusted third-party network components, and full utilization of the multicast features. In accordance with the present invention, key management is provided with minimal computation and reduced memory requirements among the subscribers in a multicast communication group. The present invention logically organizes subscribers in a multicast communication group to a plurality of smaller virtual subgroups defined by the encrypting material that they share with other subscribers. The present invention does not require explicit assignment of subscriber identifications, which facilitates synchronization (ie, ensuring that each sending entity uses a consistent group-wide reference for each subscriber) in an environment with different sending subscribers. In addition, a global and implicit way of defining subscriber IDs allows a group of members to initiate a leave operation without worrying about an ID under which other members know the leaving party. Similarly, the system according to the present invention prevents subscribers from reading future or past traffic that is outside the authorized scope.

A conference or group collaboration scenario is characterized by a large dynamically changing group of participant entities, where each participant can be both a sender and a recipient. US Patent Application No. 09 / 009,475 is directed to solutions that are particularly useful in a point-to-multipoint scenario in which only some of the subscribers are senders and each subscriber has global knowledge in the form of key information. In the sister application, each participant is aware of a group membership, and so each participant includes a memory space for holding key information shared with group members. For example, in a situation with a number N of subscribers, where each subscriber is identified by a W-bit long network address, the parent application uses a hierarchical data structure storing a total of (2 * N) -1 entries in the group key manager. In contrast, the present invention uses a flat data structure that reduces memory requirements to only W + 1 entries stored in each subscriber in a first embodiment and to 2 * W + 1 entries in a centralized database in a second embodiment. Using a flat key data structure, the data structure size is logarithmically proportional to the number of participants compared to hierarchical key data structures having a size that is linearly proportional to the number of participants.

A first implementation of the present invention, referred to hereinafter as a "distributed flat" implementation, is particularly useful in a conference or group collaboration scenario. In this first implementation is the flat. Data structure distributed over many participants. This implementation is immune to an installation implosion because admission control responsibilities are distributed across the multicast group. For example, an installation implosion occurs when a centralized access control entity must manage access and exit information for each subscriber. As the number of subscribers increases, the likelihood of receiving more messages than the centralized access control entity can handle (ie, an implosion) increases. Access control and key management according to the present invention are performed by the participants independently of each other.

In addition, the distributed system is more flexible against interference. The loss of some members or network connections does not automatically result in a total group failure. In hierarchical approaches, the loss of the entity that implements the group key manager function is fatal. In the distributed flat implementation according to the present invention, switching or changing the control of information stored by a missing subscriber is automatically performed. In a centralized flat implementation of the present invention, described below, a new participant may be selected to implement the group key manager function at the expense of additional complexity.

A second implementation, hereinafter referred to as "centralized flat", is particularly useful in the point-to-multipoint scenario, where data traffic is essentially unidirectional. The second implementation uses a centralized entity to implement the flat data structure. The centralized flat implementation reduces the data structure size to 2W + 1 entries held in a centralized entity and reduces or eliminates any need for the participants to exchange key control information with each other. While the centralized approach results in a central point of failure and is not immune to installation implosion, it provides many advantages and functionalities of the first implementation described above.

While each implementation of the present invention is described in terms of a scenario in which it is most useful, it is to be understood that any implementation may be useful, although it may not be optimal for use in either point-to-multipoint or Conference scenarios are adapted with appropriate modifications. Although the implementations are described in terms of a W-bit long network address for each subscriber, it should also be remembered that each subscriber can be identified with a W-symbol-wide ID, with each symbol having multiple bits. This implementation is desirable in many applications since it is possible for each symbol to accept multiple (versus two) values.

The secure multicast architecture according to the present invention is usefully described as a plurality of cooperating components as shown in Figs. 1a and 1b. The components in Figure 1a illustrate the distributed flat implementation in a group conference scenario, whereas Figure 1b illustrates the centralized planar implementation. Equal numbered components in FIGS. 1a and 1b are for essentially equivalent purposes and provide essentially equivalent functionality.

FIG. 1a illustrates a scenario in which each subscriber 101 may be a sender and / or a receiver by communicating data packets over a multicast data connection 102 to a data multicast group 103. In a group conference scenario, sender and recipient can not be distinguished. Each subscriber 101 may send data freely over a multicast data connection 102, the data being encrypted using secret information shared by all subscribers 101. For example, in an environment of a cooperating group, each participant 101 simultaneously assumes both the role of a sender and a recipient.

In the collaborative group scenario illustrated in FIG. 1, an admission control component 110 is contacted via a one-shot control link 104 from each of the group 101 new subscribers. For example, a control connection 104 may be implemented using a secure unicast connection or an out-of-band channel if there is no return channel.

In the implementation shown in FIG. 1a, the admission control component 110 is replicated multiple times at multiple subscribers 101. In practice, each subscriber 101 is likely to include an admission control component 110, although in some circumstances some admission control components 110 will be activated and others will be idled if they are not needed.

A group key management component 108 accepts subscribers 101 admitted by an admission control component 110 and receives their encrypting material. Optionally, each admission control component 110 may initiate a forced exit of each participant 110 one-way, without being contacted.

Control link 104 includes, for example, a conventional unicast connection that is established and terminated as needed during admission control operations. This unicast connection exists only once for each participant 101 and can be resolved after the participant 101 receives its installation information. In this way, the relatively significant overhead provided by installing a new user 102 is performed only when necessary, which greatly improves the efficiency of the system according to the present invention. The unicast connection can also be handled using out-of-band methods.

The admission control component 110 communicates with the group key management component 108 and informs them of additions and departures. The group key management component 108 manages inbound and outbound operations and establishes and generates messages for the key manager components 109 to perform necessary key changes (described below).

A key control group 107 is a virtual subset of the subscribers defined by shared encrypting information and connected by a multicast, point-to-multipoint, or any cast channel that receives packets from the group management components 108 at key locations. Manager components 109, at least the intended subscriber 101, provides. Traffic in the key control group 107 includes packets containing new encrypting material that must be distributed to the key management components 109. The encrypting information defining key control groups 107 is held in the flat data structure or key database according to the present invention. In the in Fig. 1a, the physical instance of this key database is distributed among a plurality of subscribers 101.

In the implementation shown in Fig. 1b, an admission control component 120 is implemented in a centralized entity. Optionally, an admission controller 110 and a group key manager 118 in a single entity may be associated with a sending participant 121 to establish the single sender for a group. Alternatively, these components may be implemented in separate entities. In this implementation, the centralized admission control component 120 may perform an access control and communicate with a key management component 118 to inform them of additions and departures. A group management component 118 manages inbound and outbound operations and establishes and generates messages for a key manager component 109 to perform necessary key changes (described below).

A key control group 117 is a virtual subset of subscribers (related to a key control group 107) defined by shared encrypted information and connected by any multicast, multicast, or any cast channel containing packets of group management Supplies components 118 to at least the desired receivers 111. The encrypting information defining the key control group 117 is held in the flat data structure or key database according to the centralized flat implementation of the present invention. For example, in the implementation shown in Figure 1b, the physical instance of this key database is centralized in the sender or in components that are physically separate but associated with a sender 121. Traffic in key control group 117 has packets that include new encrypting material that needs to be distributed to key management components 119.

In Figures 1a and 1b, transmissions must be received via the key control group 107 and, 117 from each subscriber 101 (or receiver 111), which can be accomplished by (1) implementing components of any reliable multicast mechanism, or (2) Retransmission is performed on a regular basis with a limited history of key transitions, resulting in a soft state approach. The latter approach is desirable for scenarios without a return channel and is particularly useful if the loss rate is known (eg, through a bandwidth reservation) or through known, good or reliable transmission channels. Periodic retransmissions allow a subscriber to catch up with key changes after he has not been in contact with the key control group 107 for a certain period of time. Less reliable channels require a higher retransmission rate or longer retransmission times to clarify expired information.

If, for some reason, a recipient 111 or a received subscriber 101 were unable to receive a packet in a reasonable amount of time, the subscriber 101 or the recipient 111 has a retraction option to contact the group manager 108 or 118 again. This can also be done using a secure unicast connection or an out-of-band channel, which is related to a control link 104 if there is no return channel.

FIG. 2 illustrates in block diagram form traffic distribution components within each subscriber 111 including a network interface 201, a network driver 202 and a physical communication network 207. These components are conventionally implemented using available hardware and software solutions to meet the needs of a particular network environment.

The traffic encryption component 203 is the component that is actually transmitting data. A traffic encryption component 203 holds a symmetric traffic encryption key (TEK) generated by the group key management component 108 and received and encoded by a key manager component 109 shown in FIG. The traffic encryption component 203 uses the TEK to encrypt data to be transmitted and decrypts data received. In the example of Figure 2, traffic encryption component 203 receives network packets (e.g. IP packets) from the transport layer 204 (which in turn comprises data messages generated by a subscriber multicast application 206) encrypts the entire network packet and adds new header information (unencrypted) to route the packet. The traffic encryption component 203 also receives encrypted payload network packets from a network driver component 202, encrypts the packets using the stored TEK, and transmits the encrypted packet to a transport layer 204 for use by a subscriber application 206. This encryption / decryption may be performed using any available encryption algorithm or combination of algorithms comprising DES, RCA4 or other block stream encryption or the like. The encryption can also take place at any other suitable level.

An example network 207 includes a virtual transport mechanism with a multicast backbone (MBONE) operating at the top of a conventional internet protocol (IP) network. However, it is contemplated that the present invention may be usefully applied to any physical network including global networks, local area networks, and the like.

In accordance with the distributed flat implementation of the present invention, an admission control component 110 is implemented in each participant 101. In this way, each subscriber 101 can perform access control operations. Each participant 101 also includes a group manager component 108. More particularly, each participant 101 may implement a portion of a group manager component 108 so that multiple participants working together implement the functionality of a group manager 108. In this way, none of the participants 101 are burdened with the large resource requirements of a centralized group manager 108. However, because any participant can initiate access and exit operations, trust in all participants is important.

The main concern with centralized approaches, such as that shown in Figure 1b, is the danger of implosion and the existence of a single point of disturbance. Thus, the implementation shown in Figure 1a offers an attractive distributed solution to the key management problem. According to the present invention, the key database of the group key manager 108 is completely distributed so that all the users 101 are created equal and no individual user 101 has complete knowledge. Each participant 101 only holds keys that match its own ID, and the collaboration of multiple participants 101 is intended to relay changes to the entire group. There is not a single identity dedicated to an implemented group manager 108, instead each participant 101 can (but does not always have to) do admission control operations.

The distributed flat implementation is flexible against network or node interference because of its inherent self-healing capability. However, it is more vulnerable to internal attacks because key management is distributed. So, appropriate precautions should be taken to control the risk of such attacks. The present invention offers the high resistance to interference, it can be considered to be stronger against "denial-of-service" attacks from the outside than the centralized flat solution shown in Figure 1b.

The present invention is to be understood in terms of five different stages or states in the operation of the components described below. The states include "group generation", "group access", "data transfer", "group exit" and "group destruction". These operational states will be described in more detail after describing the data structures of the main components according to the present invention.

Each subscriber 101 or recipient 111 is identified by a single ID. In every implementation, there is not a single dedicated entity with global knowledge of the participant IDs used, where each participant ID should be uniquely generated in a distributed fashion. In accordance with the present invention, the subscriber's network address (e.g., the concatenation of his IP address and a port number) is used directly or in combination with a collision-free hash function to provide unique subscriber IDs. Alternatively, an asynchronous transfer mode (ATM) address or any network identification type or information derived from the network identification may be used as the subscriber ID as long as the ID generation does not cause collisions.

FIG. 3 illustrates a simplified example of a group key manager database 300 useful for implementing a key control group 107 or 117 shown in FIGS. 1a and 1b.

For ease of understanding, this database is represented as a unified entity, however, it should be understood that according to the distributed flat implementation of the present invention, the database 300 is actually distributed over a plurality of users 101. The example of Fig. 3 is simplified in that, assuming each W symbol width subscriber ID has only four binary symbols (ie, W = 4).

The database 300 includes a number of 2 * W + 1 entries 400 stored, for example, in a simple table data structure. One entry 401 holds the current TEK and the other 2 * W entries 400 hold "key encryption keys" KEKs.

If individual bits of the subscriber ID are used to designate the keys, there are two available keys corresponding to the two values ​​(0 and 1) that the bit can occupy, in total 2 * W KEKs and 1 TEK. On the left side of Fig. 3 there are keys KEK1 to KEK4 which correspond to ID address bits which are zero. On the right side of Fig. 3 there are keys KEK5 to KEK8 corresponding to ID address bits equal to one.

More generally, if multi-bit symbols are used, each of these symbols will take any of the V possible values. Thus, each entry 400 is uniquely identified by a symbol value pair, which denotes a rule of how to extract the symbol from the ID and the value of that symbol, in total V · W-KEKs. In a typical application, the address of the subscriber is much longer and not only individual bits can be used to differentiate between the keys, but any number of bits can be used (e.g., groups of three to four bits). For ease of understanding, the examples use symbols consisting of a single bit only.

Each participant 101 or recipient 111 is "aware" of or "knows" the key from database 300 and uses these keys to encrypt and / or decrypt messages. By "aware of" and "knowing" as used herein, it is meant that the software implementing the key manager 109 and 119 includes variable declarations to construct variables that hold the specified information. The selection of what W keys are known to the particular subscribers 101 is conventionally based on the bit patterns in the particular ID of the subscriber. For example, a subscriber 101 with a decimal subscriber ID = "10" (ie, a binary bit pattern <1010>) knows the TEK and KEK1, KEK6, KEK3 and KEK8. In this way, since each subscriber 101 holds a unique ID, he also holds a unique combination of keys.

4 shows the contents of an entry 400 in the database 300. In both implementations, the centralized flat and the distributed flat, the keys (ie, the TEK and the KEKs) have merged version and revision numbers. The revision and revision numbers are used during operation to maintain safety conditions, as described below. In the centralized flat implementation of the version and revision numbers, maintenance is performed by the centralized group key management component 120, and so this component is deemed to be "owning" the keys.

In the distributed flat implementation, each entry 400 also includes an owner field holding the subscriber ID of a single subscriber 101, referred to as the "key holder" for that key. The owner field is not needed in the centralized flat implementation because the centralized sender entity is the owner of all keys. In the distributed flat implementation, not a single subscriber 101 can be the key holder or owner of more than W of the KEKs, so the key database in each subscriber 101 or receiver 111 has a flat data structure with W + 1 entries 400. A significant difference between these alternative implementations is that in the distributed flat implementation some subscribers 101 may be designated as owners of one or more of the W + 1 keys, whereas in the centralized flat implementation a centralized entity is the owner of the whole key set (ie V * W + 1 key), of which separate subsets having W + 1 keys are known to each receiver 111.

The participants 101, who are distinguished as "key holders," perform some authoritative function. This function is a) only used to improve the performance of version changes, b) is naturally attributed to the producer of the latest version of the key, and c) can be taken over at any time by any other subscriber 101 who receives a key update message from the key holder if this node should fail. In other words, no special trust is needed to transfer the ownership of a key. The duties of a key holder are to generate a heartbeat message that distributes the key and perform a key translation. These functions are described in more detail below.

During access operations, revision numbers of the keys to be given to the new subscriber 101 or receiver 101 are incremented by the active group key management components 108 or centralized group key managers 118. Checked keys are given by a simple directed function implemented by a group key management component 108 or 118 and subscriber key management component 109 or 119. This system defines a single-purpose function that is identical and known among the group key manager 108 (or the key manager 118) and each subscriber key manager component 109 (or 119), causing the generation of new encrypting material without interfering with the communication of the new encrypting agent Material is needed. All that has to be communicated is the increased revision number. The transmission of the revision number of the KEKs can be deferred until the updated keys are actually used. This occurs during a retirement operation (described below). An example of a simple-directed function is the MD5 algorithm, the secure hash algorithm (SHA), or an equivalent.

During outbound operations, each key known to the outbound subscriber 101 or recipient 111 is changed, including the TEK per se. The changed keys must be communicated by the active group managers 108 (or a group manager 118) to each of the subscribers 101 (or receivers 111) who know one of the changed keys. Likewise, the version numbers of these keys are increased. By periodically changing encrypting material and changing the revision numbers, even in the absence of accesses or outflows, the likelihood that an attacker has previously perfectly secreted a secret is really small.

In the centralized flat approach, a key control group is created when a key manager 118 allocates a group by generating the TEK and the KEKs to fill entries 400 in a data structure 300. A group key manager 118 publishes its public key parameter and access control contact address in a heartbeat message.

In the distributed flat implementation, key control group generation is obtained on an ad hoc basis because there is no single group management component 108. The first participant 101 in the group observes the traffic and will find that there is no "heartbeat" and begins to generate its own keys (ie the TEK and W of the 2W KEKs, or more generally V * W KEKs). Thus, the initial participant generates the keys that he would have received from the group manager 118 in the centralized flat approach. The initial subscriber 101 himself begins a heartbeat and announces the fact that he is a key holder for the keys he has just generated. Each participant 101, who is a key holder, performs a regular heartbeat, sending a message including his view of the latest keys. Optionally, the heartbeat includes a brief history of the previous keys rather than an automatic retransmission in case some messages were lost. Each participant who has recently generated a key will regard himself as a key holder of the generated key as long as he holds the latest version of that key. When a participant receives a heartbeat that displaces his (ie a heartbeat comprising a newer version of a key that he himself considers a key holder) that subscriber will stop viewing himself as a key holder of that key. Over time, the distributed flat implementation achieves a stable state in which heartbeat messages generated by different key holders are equal. This results in a small number of messages sent out in a regular manner, in addition to the disreputable messages. The novice must also verify that the appreciative node is trustworthy if he does not want to risk a "man-in-the-middle" (or other fraud) attack ("man-in-the-middle" attack ) to risk.

The heartbeat for each key includes the ID of the key (eg, a bit-value pair describing the location of the key in the database 300), version information, and revision information. In the distributed flat implementation, the heartbeat message also includes the ID of the owner for each key. In early stages of grouping, in the distributed flat implementation there is no previous shared key, multiple generations of the same key are re-resolved, as described below with respect to the outbound operation, except that a unicast connection between the keyholders is opened to an earlier key build.

Each new subscriber 101 or receiver 111 intending to join the multicast group is generated after the heartbeat message generated by the initial subscriber 101 (distributed flat) or the group key control component 1119 of the transmitter (centralized flat). A new receiver 111 receives the address of the multicast group via a session directory and receives the heartbeat message sent by the group key manager 118. The new receiver 111 establishes a confidential unauthenticated connection with an admission control component 120 and, in the event of success, receives a set of KEKs associated with their network address and the TEK encrypted using the KEKs. The TEK is decrypted and the new receiver 111 may begin to decrypt the traffic using the received keys and the connection to the admission control component 120 will be closed.

In the distributed watch implementation, new participants 101 will encounter one or more heartbeat messages. In a stable state, up to 2 W (or generally VW) have different sources of heartbeat messages in the distributed flat implementation, since several former subscribers can act as key holders. Before the stable state is reached, there may be more than 2 W (or generally VW) heartbeat sources. The prospective new subscriber is only interested in most W's heartbeat messages and collects a table of key users that he needs and that are owned by different participants. All of these key bits that a new subscriber 101 needs but has not been assigned are generated by the attendant subscriber.

The incoming subscriber then contacts one or more (a small number) of the current participants 101 and asks for permission from the group, at the same time publishing their public key parameters, recommendations, etc. Any participant who shares bits in the network address with the newbie can choose an admission check and, if necessary, provide the newbie with the current TEK and the KEKs that they share. Subscribers who miss the admission check are desirably notified so that they can take appropriate action. The keys are sent encrypted using the envisaged encrypted information. For any key bits that the new subscriber can not receive in this way, he creates a unicast connection to the authoritative source of a key for a bit (the owner or key holder) and asks that subscriber 101 for permission and suitable encrypting material.

The former subscribers 101, keyring the incoming subscriber in the distributed flat implementation, increment the revision number of the keys that are creating and announce this change of group in a key control message via a key control group 107 (shown in Fig. 1a). The subscriber key manager 109 may begin to process traffic from the existing subscribers using the received keys. Once the connection is established, the unicast connection (s) will be closed.

It should be appreciated that the system may be implemented so that only former participants acting as key holders will answer inquiries from new subscribers 101 to reduce synchronization problems. During access, the incoming subscriber will first multicast a message to the "owner multicast group" without raising rings. If no response is received, the subscriber begins to ring around the "Subscriber Multicast Group". Alternatively, the incoming subscriber must passively await a heartbeat that includes the necessary information, or listen for any sender with a partial network ID match and contact them for admission information. This would be followed by a possible selection or choice of an owner adding an automatic liveness test.

If the novice had to generate some of his own keys, using symbol-value pairs that are not yet used within that group, he becomes a key holder for those new keys, and so begins the heartbeat of his key-table. The key table of the subscriber is a subset of the key table 300 (shown in Fig. 3) having at most W + 1 of the (2 x W) + 1 keys (or more generally (2 x W) + 1 key). Each entry 400 in the subscriber's key table includes addresses of the owner and version / revision numbers of the keys. If the other key owners allow the new subscriber 101, they will customize their own key tables to display the new subscriber as the owner of the newly assigned key bits. In this way, all group participants 101 will eventually be aware of the new ownership.

Since a subscriber 101 includes an admission control component 110 in the distributed flat embodiment, each may choose to perform a local admission control and ignore ownership of unauthorized parity. Each new subscriber 101 may also use its own admission control component 120 to allow the current subscribers. This action avoids the possibility of misleading the newly arriving participant by a man-in-the-middle style attack.

In the distributed implementation, the TEK is owned by a first group member (ie, the participant who created the TEK) until the ownership is transferred to a successor. If a key holder should terminate the announcement of his function, any other subscriber 101 may be aware of that key. An ownership transfer occurs automatically when the current TEK owner leaves the group, is forced by the group, becomes unreachable, or otherwise fails to send his heartbeat message. After a system-specific time without receiving the heartbeat, one or more of the participants 101 will claim to be the new owner. If there are several claimants, (ie Participants 101 who are willing to take over) should use a non-elusive voting scheme to decide which participant will become the new owner. For example, the subscriber 101 wins with a higher priority (eg higher network address). Any criterion may be used to select the new owner, but the selection may be made by basing the selection criteria on the IP address of the subscribers, the network ID or the subscriber ID with minimal communication between the subscribers. Additionally, the replacement key holder may desire to perform a retirement operation, discussed below, for the old key holder.

The new owner starts his own heartbeat and holds the ownership of the TEK. If the missing subscriber 101 comes back later and resumes his heartbeat, the one with the lower address will win again. Although this process is described in terms of transferring the ownership of the TEK, a similar procedure is also used to transfer the ownership of any CEC. However, in the case of a CEC transfer, the new owner must be a subscriber 101 who knows the KEK being transferred.

A normal data transfer according to the present invention is sent in packets 800 having a format such as shown in FIG. Each packet 800 includes a merge ID field indicating the ID of the subscriber 101 from which the data packet 800 originates. Each package 800 also includes a key version field and a key revision field. The KEK revision number may be a single bit set by access operations (ie is set to a one level) and after a retirement operation that caused that key to be replaced with a new version. Additional headers having one or more header fields used in the traffic distribution component are also provided. The encrypted payload information typically has an encrypted ID packet (e.g. a SKIP packet) Since each packet is received by a received subscriber 101, subscribers 101 can capture key revision changes and use the single-directional function to generate the same verified key. Each package may also display version changes that include new keys, but the new key is provided in a separate update or reek message, described below. Subscriber 101 may also request retransmission of a message if a version update was missed due to corrupted or expired packets typical of an Internet application.

Traffic encryption / decryption is obtained in the subscribers 101 by the traffic encryption component 203. Participants 101 detect an increase in the key revision number and pass the verified key through the simple-directed function to generate the new key and begin encrypting / decrypting data with the new key. Subscribers 101 pass their stored traffic encryption key through the simply directed function. This creates the new TEK '(where the apostrophe indicates a new version) in each database of the participants. Once the new key update occurs, normal operation continues. In this way, subscribers 101 merely need to communicate that a key has been checked to update their keys for all subscribers 101 to the new key. It is desirable for the subscribers 101 to hold earlier (ie repeated) keys for a short system-defined time (eg, 1 to 3 minutes) to handle cases where the sending subscriber 101 has not yet received the version update message.

During an outbound operation, the access control component 110 in one or more subscribers 101 informs the group key management component in other subscribers 101 that one or more subscribers 101 are composing the group so that they are no longer authorized to receive group multicast messages. The access control component 110 may initiate or eject these participants 101, or may simply have detected that the participants have left by themselves.

If a participant 101 (an "excluder") decides to discard another participant 101, the excluder selects a TEK 'and encrypts it with each KEK encryption key that he knows he does not share with the participants 101, to be thrown out. The KEKs known to the outgoing subscriber are thrown out, leaving a set of remaining KEKs known only to the remaining subscribers 101. The excluder assigns new CECs for each KEK in the set of remaining CECs that are encrypted using the corresponding old CEC and the new CEC. The outlaw then becomes the new key owner for the newly assigned CECs. The outgoing participant populates a table with this information and sends it to the group. Alternatively, the function of assigning new KEKs may be left to another key owner entity. Any participant who is able to understand the new TEK decrypts it, starts using it, complements the table with KEKs it holds but not yet in the table, and redistributes the table.

If two subscribers 101 attempt to allocate a new KEK during a same timeslot (both use the same new incremented version number), the two KEKs are combined in one by mixing schemas, which will be explained in greater detail with reference to Figs. 5-6 which illustrate this feature of the present invention in more detail. Table 1 shows an example table prepared by an excluder, where a party with the ID = 9 (binary 1001) wants to evict a party with an ID = 10 (binary 1010): Table 1

Where the locations marked "unusable" are known to the subscriber 101 with the ID = 10, therefore, the KEKs stored in these locations can not be used to encrypt the new TEK (indicated as TEK ') and have to be replaced. The places marked "unknown" are not known to the participant with the ID = 9. Sites that are neither usable nor unknown can be used to carry the new TEK 'encrypted with the old KEK of the site. These places, which are marked as unusable only, are filled with new KEKs that are encrypted with the new TEK 'and the old KEK. The table sent by the excluder looks like this. Table 2

Subscribers 101 having an ID = "xx10", where "x" represents a nonspecified value (ie, subscribers 2, 6, 10, 14), can not understand this message and must wait for a fuller table or have one of the other subscribers 101 if they do not receive the update message in time (e.g., the sender of that message, key bit owner, or a recent contributor to traffic in the group). The subscriber 101 with the ID = 10 will never be able to understand the message and, assuming a consistent admission control mechanism, will also be unable to receive the new TEK from other subscribers 101. He will remain excluded, which is the goal of the departure process.

It is best that changes to the admission control be synchronized with the key update message. Otherwise, an excluded participant might attempt to return to the multicast group until the admission control component is updated. It is possible to do this in conjunction with the key change so that there are no exploitable inconsistencies. Also, anyone who joins in later needs a blacklist that is up-to-date and displays foreclosed participants (or a white list that shows the currently enrolled participants).

For example, a participant 101 with an ID = 1 (ie binary 0001) receives the message in Table 2 and completes it as much as possible to create a table 3, shown below, before sending it out. Table 3

Next, a participant 101 with an ID = 6 can fill its deletions. If a subscriber ID = 2 were assigned a new KEK1 and KEK6 at the same time, the new KEK6 would win the subscriber ID = 2, since 2 is the lower network address. The resulting Table 4 is complete. Table 4

If two new subscribers create common and separate CECs at the same time (eg, a Subscriber ID = 2 generates KEK1, KEK6 and KEK3 and a Subscriber ID = 14 generates KEK1, KEK6 and KEK8), others using keys would separated by the lower network address for each key (ie selected on a key-by-key basis). In this particular example, this would result in KEK1, KEK6 and KEK3 from subscriber 2 and KEK8 from subscriber 14. Participants 101 who still can not find a TEK encrypted in a KEK they can read build a secure unicast to one of the participants, obtain the TEK ', expand the table and then distribute the extended table. Thus, one considers the situation where two different groups of subscribers 101 can not communicate over a multicast because they do not share a key encryption key that they do not share with the subscriber who is to be thrown out.

Groups are destroyed when all participants cease to exist, with all secrets (the TEK and all CECs) being abandoned by each participant 101.

It will be useful to understand a number of concepts that help explain how the system according to the present invention operates without centralized control with a number of subscribers 101 performing simultaneous operations. These concepts are picked up in turn below:

Key Merging: Since several subscribers can generate new keys at the same time, each must have its own creator ID to insure uniqueness. In addition, each key holder must include information indicating which key (version, revision, version generator) the new key is based on, as this is also the key with which it is encrypted. This allows the participants implicitly (ie without sending additional messages) to agree on a common key and also to be able to understand any traffic that has been encrypted using both the individual and mixed keys. Three typical mixing scenarios are shown in FIGS. 5 to 7 and explained below. In Figures 5-7, the message is indicated in parentheses by components (Version #, Revision #, Version Creator ID).

A first case in which several new revisions are received by a subscriber is shown in FIG. 5, where a key holder 501 generates a key with a revision increment to subscribers 502 and 503. A subscriber 504 receives the key verification message from both the subscriber 502 and the subscriber 503, and can readily determine that there is no conflict since the key is the same in each message. In this case, no action is needed to get the new key, since a revision raise is well specified (ie not ambiguous) and repeatable.

A second case where several new versions are received by a subscriber is shown in FIG. In this case, a key holder 602 and a key holder 603 have produced version increases of the key of a key holder 601. Subscriber 604 can see that the same version has been generated by multiple key holders and can combine these keys into a single new key that can be readily calculated from the base keys (e.g. using Exclusive-OR). The version generator ID of the mixed key will be the set of ID pairs. Any key holder of a base key should consider itself as a key holder of the mixed key in a first step until it is set down (as described below).

In a third case, shown in Fig. 7, a new version is generated by a key holder 702, while a key holder 703 creates a new revision. Any participant 704 who has experienced a revision of a key abandoned by a version upgrade should increase the revision of the new mixed key accordingly to ensure perfect forward secrecy. The key holder for this new key can re-encrypt the new key with the new revision of its base key to simplify operation for the novice causing the revision.

A key holder stops carrying a heartbeat if his message is abandoned. A message with a key K is considered abandoned if any of the following keys are disclosed: (a) a new revision, (b) a new version based on K or any key giving it up, (c) a mixed key, the K comprises, or (d) K is a mixed key and it is communicated by a party to this key having a higher priority (e.g., a higher network address).

While the invention has been particularly described and illustrated to some extent, it is to be understood that the present disclosure has been made by way of example only and that those skilled in the art will appreciate numerous changes in the combination and arrangement of parts as claimed below , In particular, it should be noted that 48 symbols, each symbol having a 2-bit value, could be used that directly match an application's IP address and port number, thereby uniquely identifying the application on the network. In this case, the second part of the table (eg, 64 symbols of 16 values ​​each) may encode keys that may be used to counter covert participants. Normal access and exit operations can be performed on the 48 symbols, which have high connectivity in the participating network, and if ever covert enemies have to be thrown out, the other 64 symbols are available for use. Encompassing enemies would then be at least 2W (e.g., 2¹ & in the specific example) to wipe out all participants. One can combine different tables with different symbol spaces to obtain a number of properties of the resulting distributed system. These and other modifications are promptly implemented in accordance with the teachings of the present invention and are considered equivalents.