Processing method for key exchange among broadcast or multicast groups that provides a more efficient substitute for Diffie-Hellman key exchange

• US 7,181,014 B1
• Filed: 11/17/2003
• Issued: 02/20/2007
• Est. Priority Date: 09/10/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Srivastava, Sunil K.
• Primary Examiner(s): Sheikh; Ayaz
• Assistant Examiner(s): LAFORGIA, CHRISTIAN A
• Application Number:
  US10/715,721
• Time in Patent Office: 1,191 Days
• Field of Search: 380/28, 380/30, 380/278, 380/277, 713/162, 713/163, 713/201, 713/168
• US Class Current: 380/278
• CPC Class Codes: H04L 2209/601 Broadcast encryption
• CPC Class Codes: H04L 9/0833 involving conference or group key network architectures or network communication protocols for key management in group communication in a packet data network H04L63/065
• CPC Class Codes: H04L 9/0841 involving Diffie-Hellman or related key agreement protocols

Abstract

An approach for arriving at a shared secret key in a multicast or broadcast group environment is disclosed. The key exchange protocol permits nodes within a multicast or broadcast group to compute a shared secret key in a binary fashion, whereby a shared secret key is generated for a pair of nodes at a time. Once the shared secret key is computed by the pair, the nodes within the pair is viewed as a single entity by a node that is to be joined. This process is iteratively performed until all the nodes within the multicast group attain a common shared secret key. Under this approach, the number of messages exchanged between the nodes for establishing the secured channel is significantly reduced.

Claims

1. A method for establishing a secure communication session among a first node of a network and one or more other nodes using a group shared secret key, each of the nodes having a private key value associated therewith, the method comprising the computer-implemented steps of:

communicating a first public key value of the first node to a second node;

creating and storing an initial shared secret key for the first node and second node based on a first private key value and a second public key value that is received from the second node;

creating and storing information at the first node that associates the first node with a first network communication entity by generating a collective public key value that is shared by the first node and a second node and based on the first private key value and a second private key value that is derived by the first node from the second public key value;

receiving a third public key value from a third node that seeks to join the first network communication entity;

creating a second shared secret key value based on the collective public key value and the third public key value; and

joining the first node to a second network communication entity that includes the first network communication entity and the third node and that uses secure communication with messages that are encrypted using the second shared secret key value;

wherein the first node, second node, and third node are separate nodes.

2. A method as recited in claim 1, wherein joining the first node to a second network communication entity includes the step of communicating the first private key value to the second node and to the third node using messages encrypted using the second shared secret key value.

3. A method as recited in claim 1, wherein creating the second shared secret key value further comprises creating and storing the second shared secret key based upon how many times each node of the second network communication entity has participated in formation of any such entity and based upon each private number of each node in the second network communication entity.

4. A method as recited in claim 1, further comprising the step of creating and storing a subsequent shared secret key for use by the first network communication entity and the third node to enable the third node to independently compute the group shared secret key.

5. A method as recited in claim 4, wherein creating and storing the subsequent shared secret key comprises creating and storing the subsequent shared secret key, k, according to the relation

k=p^(a*^x)(b*^y)(c*^z) mod (q)

where p=a random number, q=a prime number, a=the first private key value, b=the second private key value, c=a private key value of the third node, x=a number of times the first node has participated in entity formation, y=a number of times the second node has participated in entity formation, and z=a number of times the third node has participated in entity formation.

6. A method as recited in claim 5, further comprising the step of storing and distributing the first public value and the second public value using a key distribution center.

7. A method as recited in claim 5, wherein the step of joining the first node to a second network communication entity further comprises:

creating and storing a collective public key based upon the first private key value, the second private key value, and the third private key value;

communicating a collective public key of the second network communication entity to the third node.

8. A method as recited in claim 7, wherein the step of joining the first node to a second network communication entity further comprises determining which one of the nodes of the first network communication entity is designated to transfer the collective public key based upon order of entry into the formed entity.

9. A method as recited in claim 7, wherein the step of joining the first node to a second network communication entity further comprises determining which one of the nodes of the first network communication entity is designated to transfer the collective public key based upon a predetermined metric.

10. A method as recited in claim 1, wherein creating and storing an initial shared secret key for the first node and second node comprises creating and storing an initial shared public key “

AB”

according to the relation

AB=k_ab^ab mod (q)=p^(ab)(ab) mod (q)

wherein k=the initial shared secret key value, a=the first private key value, b=the second private key value, p is a base value, and q is a randomly generated prime number value.

11. A method as recited in claim 1, wherein creating and storing the second shared secret key value further comprises creating and storing the second shared secret key according to the relation

k_abc=(AB)^c mod (q)=p^(ab)(ab)c mod (q)=p^(ab**^2)c mod (q)

where p=a random number, q=a prime number, a=the first private key value, b=the second private key value, c=a private key value of the third node, AB=the collective public key value.

12. A computer-readable storage medium carrying one or more sequences of one or more instructions for establishing a secure communication session among a first node of a network and one or more other nodes using a group shared secret key, each of the nodes having a private key value associated therewith, the one or more sequences of one or more instructions including instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of:

communicating a first public key value of the first node to a second node;

creating and storing an initial shared secret key for the first node and second node based on a first private key value and a second public key value that is received from the second node;

creating and storing information at the first node that associates the first node with a first network communication entity by generating a collective public key value that is shared by the first node and a second node and based on the first private key value and a second private key value that is derived by the first node from the second public key value;

receiving a third public key value from a third node that seeks to join the first network communication entity;

creating a second shared secret key value based on the collective public key value and the third public key value; and

joining the first node to a second network communication entity that includes the first network communication entity and the third node and that uses secure communication with messages that are encrypted using the second shared secret key value;

wherein the first node, second node, and third node are separate nodes.

13. A multicast communication server for establishing a secure communication session among a first node of a network and one or more other nodes using a group shared secret key, each of the nodes having a private key value associated therewith, comprising:

means for communicating a first public key value of the first node to a second node;

means for creating and storing an initial shared secret key for the first node and second node based on a first private key value and a second public key value that is received from the second node;

means for creating and storing information at the first node that associates the first node with a first network communication entity by generating a collective public key value that is shared by the first node and a second node and based on the first private key value and a second private key value that is derived by the first node from the second public key value;

means for receiving a third public key value from a third node that seeks to join the first network communication entity;

means for creating a second shared secret key value based on the collective public key value and the third public key value;

means for joining the first node to a second network communication entity that includes the first network communication entity and the third node and that uses secure communication with messages that are encrypted using the second shared secret key value;

wherein the first node, second node, and third node are separate nodes.

14. The multicast communication server in claim 13, wherein the means for joining the first node to a second network communication entity includes means for communicating the first private key value to the second node and to the third node using messages encrypted using the second shared secret key value.

15. The multicast communication server in claim 13, wherein the means for creating the second shared secret key value further comprises means for creating and storing the second shared secret key based upon how many times each node of the second network communication entity has participated in formation of any such entity and based upon each private number of each node in the second network communication entity.

16. The multicast communication server in claim 13, further comprising means for creating and storing a subsequent shared secret key for use by the first network communication entity and the third node to enable the third node to independently compute the group shared secret key.

17. The multicast communication server in claim 16, wherein the means for creating and storing the subsequent shared secret key comprises means for creating and storing the subsequent shared secret key, k, according to the relation

k=p^(a*^x)(b*^y)(c*^z) mod (q)

where p=a random number, q=a prime number, a=the first private key value, b=the second private key value, c=a private key value of the third node, x=a number of times the first node has participated in entity formation, y=a number of times the second node has participated in entity formation, and z=a number of times the third node has participated in entity formation.

18. The multicast communication server in claim 17, further comprising means for storing and distributing the first public value and the second public value using a key distribution center.

19. The multicast communication server in claim 17, wherein the means for joining the first node to a second network communication entity further comprises:

means for creating and storing a collective public key based upon the first private key value, the second private key value, and the third private key value;

means for communicating a collective public key of the second network communication entity to the third node.

20. The multicast communication server in claim 19, wherein the means for joining the first node to a second network communication entity further comprises means for determining which one of the nodes of the first network communication entity is designated to transfer the collective public key based upon order of entry into the formed entity.

21. The multicast communication server in claim 19, wherein the means for joining the first node to a second network communication entity further comprises means for determining which one of the nodes of the first network communication entity is designated to transfer the collective public key based upon a predetermined metric.

22. The multicast communication server in claim 13, wherein the means for creating and storing an initial shared secret key for the first node and second node comprises means for creating and storing an initial shared public key “

AB”

according to the relation

AB=k_ab^ab mod (q)=p^(ab)(ab) mod (q)

wherein k=the initial shared secret key value, a=the first private key value, b=the second private key value, p is a base value, and q is a randomly generated prime number value.

23. The multicast communication server in claim 13, wherein the means for creating and storing the second shared secret key value further comprises means for creating and storing the second shared secret key according to the relation

k_abc=(AB)^c mod (q)=p^(ab)(ab)c mod (q)=p^(ab**^2)c mod (q)

where p=a random number, q=a prime number, a=the first private key value, b=the second private key value, c=a private key value of the third node, AB=the collective public key value.

24. An apparatus for establishing a secure communication session among a first node of a network and one or more other nodes using a group shared secret key, each of the nodes having a private key value associated therewith, comprising:

one or more processors;

a computer-readable storage medium carrying one or more sequences of one or more instructions, the one or more sequences of one or more instructions including instructions which, when executed by the one or more processors, cause the one or more processors to perform the steps of;

communicating a first public key value of the first node to a second node;

creating and storing an initial shared secret key for the first node and second node based on a first private key value and a second public key value that is received from the second node;

creating and storing information at the first node that associates the first node with a first network communication entity by generating a collective public key value that is shared by the first node and a second node and based on the first private key value and a second private key value that is derived by the first node from the second public key value;

receiving a third public key value from a third node that seeks to join the first network communication entity;

creating a second shared secret key value based on the collective public key value and the third public key value;

joining the first node to a second network communication entity that includes the first network communication entity and the third node and that uses secure communication with messages that are encrypted using the second shared secret key value;

wherein the first node, second node, and third node are separate nodes.

25. An apparatus as recited in claim 24, wherein the step of joining the first node to a second network communication entity includes the step of communicating the first private key value to the second node and to the third node using messages encrypted using the second shared secret key value.

26. An apparatus as recited in claim 24, wherein the step of creating the second shared secret key value further comprises creating and storing the second shared secret key based upon how many times each node of the second network communication entity has participated in formation of any such entity and based upon each private number of each node in the second network communication entity.

27. An apparatus as recited in claim 24, the one or more sequences of one or more instructions including instructions which, when executed by the one or more processors, cause the one or more processors to further perform the step of creating and storing a subsequent shared secret key for use by the first network communication entity and the third node to enable the third node to independently compute the group shared secret key.

28. An apparatus as recited in claim 27, wherein creating and storing the subsequent shared secret key comprises creating and storing the subsequent shared secret key, k, according to the relation

k=p^(a*^x)(b*^y)(c*^z) mod (q)

where p=a random number, q=a prime number, a=the first private key value, b=the second private key value, c=a private key value of the third node, x=a number of times the first node has participated in entity formation, y=a number of times the second node has participated in entity formation, and z=a number of times the third node has participated in entity formation.

29. An apparatus as recited in claim 28, the one or more sequences of one or more instructions including instructions which, when executed by the one or more processors, cause the one or more processors to further perform the step of storing and distributing the first public value and the second public value using a key distribution center.

30. An apparatus as recited in claim 28, wherein the step of joining the first node to a second network communication entity further comprises:

creating and storing a collective public key based upon the first private key value, the second private key value, and the third private key value;

communicating a collective public key of the second network communication entity to the third node.

31. An apparatus as recited in claim 30, wherein the step of joining the first node to a second network communication entity further comprises determining which one of the nodes of the first network communication entity is designated to transfer the collective public key based upon order of entry into the formed entity.

32. An apparatus as recited in claim 30, wherein the step of joining the first node to a second network communication entity further comprises determining which one of the nodes of the first network communication entity is designated to transfer the collective public key based upon a predetermined metric.

33. An apparatus as recited in claim 24, wherein creating and storing an initial shared secret key for the first node and second node comprises creating and storing an initial shared public key “

AB”

according to the relation

AB=k_ab^ab mod (q)=p^(ab)(ab) mod (q)

wherein k=the initial shared secret key value, a=the first private key value, b=the second private key value, p is a base value, and q is a randomly generated prime number value.

34. An apparatus as recited in claim 24, wherein creating and storing the second shared secret key value further comprises creating and storing the second shared secret key according to the relation

k_abc=(AB)^c mod (q)=p^(ab)(ab)c mod (q)=p^(ab**^2)c mod (q)

where p=a random number, q=a prime number, a=the first private key value, b=the second private key value, c=a private key value of the third node, AB=the collective public key value.