Method and apparatus for negotiating Diffie-Hellman keys among multiple parties using a distributed recursion approach
View Patent ↗A method and apparatus for negotiating a shared secret among members of a multicast group are disclosed. A tree that represents the group is created and stored in a memory. Each node of the tree is associated with a group member. The shared secret is generated by traversing the tree in post-order, and at each node of the tree, recursively generating a partial key value for use in the shared secret and a base value for use in subsequent recursive partial key value generation. At each node, a partial key value is computed by accumulating the exponent portion of the Diffie-Hellman key equation and computing a new base value for use in subsequent computations. If a particular node has a left or right child sub-tree, each sub-tree is also recursively traversed in post-order fashion. When traversal of the entire tree is complete, all nodes have the shared secret key.
1. A method of generating a shared secret for a plurality of members of a multicast group to use in a secure communication session, the method comprising the computer-implemented steps of:
creating and storing a tree that represents the group, wherein each node of the tree is associated with a group member; and
generating the shared secret by traversing the tree in post-order, and at each node of the tree, recursively generating a partial key value for use in the shared secret and a base value for use in subsequent recursive partial key value generation;
wherein the base value is accumulated and computed by performing at least one exponential operation with an exponent that is a local random number that is associated with a specific node of a specific subtree that is rooted at that node of the tree.
2. A method as recited in claim 1 , further comprising the steps of:
receiving information identifying a number of members of the multicast group;
creating and storing the tree as a balanced binary tree having a root node and a plurality of other nodes equal in number to the number of members of the multicast group.
3. A method as recited in claim 1 , wherein the step of generating the shared secret comprises the steps of:
receiving a request to generate a portion of the shared secret at a particular node of the tree;
recursively requesting each sub-tree of the particular node to generate other portions of the shared secret for such sub-trees.
4. A method as recited in claim 1 , wherein the step of generating the shared secret comprises the steps of:
receiving a request to generate the partial key value at a particular node of the tree;
recursively requesting each sub-tree of the particular node to generate other portions of the shared secret for such sub-trees;
computing the partial key value based on the other portions of the shared secret of the sub-trees.
5. The method as recited in claim 1 , wherein the step of generating the shared secret comprises the steps of:
receiving a request to generate the partial key value at a particular node of the tree;
recursively requesting each sub-tree of the particular node to generate other portions of the shared secret for such sub-trees;
computing and storing the partial key value based on the other portions of the shared secret of the sub-trees;
computing and storing a new base value for use in subsequent computations of partial key values; and
sending the partial key value and the new base value from the particular node to its parent node.
6. The method as recited in claim 1 , further comprising the steps of:
storing, in association with each node of the tree, values identifying a left child of such node in the tree, a right child of such node in the tree, a parent node of such node in the tree, a next node after such node in a post-order traversal of the tree, and the first node in a post-order traversal of a subtree rooted at such node; and
using the values to guide post-order traversal of the tree.
7. The method as recited in claim 1 , further comprising the steps of:
designating one member in the group as a control member;
wherein the control member carries out the creating and storing step; and
at the control member, storing, in association with each node of the tree, values identifying a left child of such node in the tree, a right child of such node in the tree, a parent node of such node in the tree, a next node after such node in a post-order traversal of the tree, and the first node in a post-order traversal of a subtree rooted at such node.
8. A method as recited in claim 1 , further comprising the steps of automatically establishing a secure multicast session among the group members using the shared secret.
9. A method as recited in claim 1 , wherein the step of generating the shared secret comprises the steps of sending an initialization message from a root node of the tree to a first node of a first subtree rooted at the first node, wherein the initialization message includes a base value and a prime number value.
10. A method as recited in claim 9 , wherein the step of generating the shared secret further comprises the steps of responding to the initialization message by performing the steps of:
sending a key computation message to traverse the first subtree using post-order traversal until the first node is reached;
as each node of the subtree is visited in the traversal, requesting each node to generate a partial shared secret;
computing the shared secret at the first node.
11. A method as recited in claim 10 , wherein the step of generating the shared secret comprises the steps of:
computing a new left subtree base value and a new right subtree base value;
sending the new left subtree base value and the prime number value to a left child node of the first node;
sending the new right subtree base value and the prime number value to a right child node of the first node.
12. A method as recited in claim 11 , further comprising the steps of recursively performing the steps of traversing, requesting and computing at each node of a left subtree that is rooted at the left child node and at each node of a right subtree that is rooted at the right child node.
13. A method as recited in claim 10 , wherein sending the key computation message includes sending a key computation message that comprises an identifier of the node that is sending the key computation message, a base value, and a prime number value.
14. A method as recited in claim 11 , wherein the step of computing a new left subtree base value and a new right subtree base value is performed in response to receiving a base computation message that comprises a base value and a prime number value.
15. A method as recited in claim 11 , wherein each of the steps of sending includes the step of sending a base reply message that includes the base value.
16. A method as recited in claim 12 , wherein the step of recursively performing includes the steps of sending an initialization message that includes a partial shared secret value and the prime number value.
17. A method as recited in claim 16 , further comprising the steps of:
setting a flag value that indicates whether the key computation message has been generated as a result of receiving a base computation message or receiving an initialization message;
upon returning to the root node of a subtree after post-order traversal of such subtree, determining whether the flag value is null, and when the flag value is not null, sending the base value to a further node as identified in the flag value.
18. A method as recited in claim 16 , further comprising the step of initiating generation of the shared secret by sending the initialization message to the root node of the tree.
19. A method as recited in claim 9 , further comprising the step of determining that all nodes of the tree have the shared secret when no message is in transit among any of the nodes.
20. A method as recited in claim 1 , further comprising the steps of sending a confirmation message from any node that has computed the shared secret to its parent node.
21. A method as recited in claim 1 , further comprising the steps of:
when a child node has computed the shared secret, sending a confirmation message to its parent node;
when a child node that is a leaf node has computed the shared secret, sending a confirmation message to its parent node;
when a non-leaf node has computed the shared secret and received a confirmation message from each of its child nodes, sending a confirmation message to its parent node;
when the root node has computed the shared secret and received a confirmation message from each of its child nodes, determining that all nodes have the shared secret.
22. A method as recited in claim 20 , further comprising the steps of:
determining that a node has failed based upon failure to receive a confirmation message therefrom;
removing the failed node from the multicast group
creating and storing a new tree that represents a new set of nodes without the failed node;
sending an initiation message to a new root node of the new tree to cause the new root node to initiate key generation.
23. A method as recited in claim 22 , further comprising the steps of sending a failure warning message from one node to the control node, and in response thereto, polling all nodes in the multicast group to check the status of each node.
24. A method as recited in claim 1 , further comprising the steps of:
sending a departure message from a first node that is leaving the multicast group to the control node;
in response to receiving the departure message, creating and storing a new tree that represents a new set of nodes without the departed node;
sending an initiation message to a new root node of the new tree to cause the new root node to initiate key generation.
25. A method as recited in claim 1 , further comprising the steps of:
sending a joining message from a first node that is joining the multicast group to the control node;
in response to receiving the joining message, creating and storing a new tree that represents a new set of nodes that includes the joining node;
sending an initiation message to a new root node of the new tree to cause the new root node to initiate key generation.
26. A method of generating a shared secret for a plurality of members of a multicast group to use in a secure communication session, the method comprising the computer-implemented steps of:
creating and storing a tree that represents the group, wherein each node of the tree is associated with a group member; and
generating the shared secret by traversing the tree in post-order, and at each node of the tree, recursively generating a partial key value for use in the shared secret and a base value for use in subsequent recursive partial key generation, wherein the base value is accumulated and computed by performing at least one exponential operation with an exponent that is a local random number that is associated with a specific node of a specific subtree that is rooted at that node of the tree, by the steps of:
selecting an initial base value g and prime number value p;
sending a key computation message that includes the initial base value g and the prime number value p to a first node of a left subtree L that is rooted at the root node;
forwarding the key computation message to each successor nodes in post-order traversal of the subtree, collecting an accumulated exponent value x j , jεM;
repeating the sending step and forwarding step for a right subtree R that is rooted at the root node;
upon completion of the post-order traversal, receiving at the root node a value
X
L
+
R
=
(
g
∏
j
∈
L
+
R
x
j
)
mod
p
computing the shared secret value as
X
M
=
(
X
l
+
R
)
x
i
mod
p
=
g
∏
j
∈
M
x
j
mod
p
=
K
;
27. A method as recited in claim 26 , further comprising the steps of:
requesting a first child node of the root node and a second child node of the root node to respectively compute a first new base value and a second new base value X R+{t} and X L+{t} ;
for the first child node, recursively issuing a key computation message to traverse its subtree, to result in computing a first base value
X
R
=
g
∏
j
∈
R
x
j
mod
p
;
sending the first base value X R to the root node;
computing a first new root base value at the root node as
X
R
+
{
t
}
=
(
X
R
)
x
t
mod
p
=
g
∏
j
∈
R
+
{
t
}
x
j
mod
p
;
performing the steps of requesting, issuing, sending and computing for the second child node, to result in computing a second new root base value X L+{t} .
28. A method as recited in claim 27 , further comprising the steps of:
sending the first new root base value X R+{t} and the second new root base value X L+{t} to the left child node and right child node, respectively, of the root node;
recursively computing subsequent shared secret values and new base values for the left child node using the new root base value of X R+{t} ;
recursively computing subsequent shared secret values and new base values for the left child node using the new root base value of X L+{t} .
29. A computer-readable medium carrying one or more sequences of instructions for generating a shared secret for a plurality of members of a multicast group to use in a secure communication session, which instructions, when executed by one or more processors, cause the one or more processors to carry out the steps of:
creating and storing a tree that represents the group, wherein each node of the tree is associated with a group member; and
generating the shared secret by traversing the tree in post-order, and at each node of the tree, recursively generating a partial key value for use in the shared secret and a base value for use in subsequent recursive partial key value generation;
wherein the base value is accumulated and computed by performing at least one exponential operation with an exponent that is a local random number that is associated with a specific node of a specific subtree that is rooted at that node of the tree.
30. An apparatus for generating a shared secret for a plurality of members of a multicast group to use in a secure communication session, comprising:
means for creating and storing a tree that represents the group, wherein each node of the tree is associated with a group member; and
means for generating the shared secret by traversing the tree in post-order, and at each node of the tree, recursively generating a partial key value for use in the shared secret and a base value for use in subsequent recursive partial key value generation;
wherein the base value is accumulated and computed by performing at least one exponential operation with an exponent that is a local random number that is associated with a specific node of a specific subtree that is rooted at that node of the tree.
31. An apparatus for generating a shared secret for a plurality of members of a multicast group to use in a secure communication session, comprising:
a network interface that is coupled to the data network for receiving one or more packet flows therefrom;
a processor;
one or more stored sequences of instructions which, when executed by the processor, cause the processor to carry out the steps of:
creating and storing a tree that represents the group, wherein each node of the tree is associated with a group member; and
generating the shared secret by traversing the tree in post-order, and at each node of the tree, recursively generating a partial key value for use in the shared secret and a base value for use in subsequent recursive partial key value generation;
wherein the base value is accumulated and computed by performing at least one exponential operation with an exponent that is a local random number that is associated with a specific node of a specific subtree that is rooted at that node of the tree.