Method and apparatus for key management in distributed sensor networks

• US 7,486,795 B2
• Filed: 09/18/2003
• Issued: 02/03/2009
• Est. Priority Date: 09/20/2002
• Status: Active Grant

• Current Assignee: University of Maryland
• Original Assignee: University of Maryland
• Inventors: Eschenauer, Laurent, Gligor, Virgil D.
• Primary Examiner(s): Vu; Kimyen
• Assistant Examiner(s): PATEL, NIRAV B
• Application Number:
  US10/666,207
• Publication Number:
  US 20050140964A1
• Time in Patent Office: 1,965 Days
• Field of Search: 380277-280, 380/283, 380285-286, 380/44, 380/45, 380/255, 380/270, 380/269, 380/259, 713/163, 713/150, 713/168, 713/169, 455/410, 455/411
• US Class Current: 380/277
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 63/1408 by monitoring network traffic monitoring network traffic per se H04L43/00
• CPC Class Codes: H04L 9/0838 Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or associated with, each of these network architectures or network communication protocols for key exchange in a packet data network H04L63/061
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04W 12/041 Key generation or derivation
• CPC Class Codes: H04W 12/0433 Key management protocols
• CPC Class Codes: H04W 76/10 Connection setup
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

In a distributed sensor network, a method of key management is carried out in several phases, particularly key pre-distribution phase, shared key discovery phase, and as needed, a path key establishment phase. In the key pre-distribution phase, prior to DSN deployment, a ring of keys is distributed to each sensor node, each key ring consisting of randomly chosen keys from a large pool of keys which is generated off-line. A shared key exists between each two key rings with a predetermined probability. In the shared key discovery phase, which takes place upon deployment of the DSN, every sensor node discovers its neighbors in wireless communication range with which it shares keys, and the topology of the sensor array is established by forming secure communication links between respective sensor nodes. The path key establishment phase assigns a path key to selected pairs of sensor nodes in wireless communication range that do not share a key but are connected by two or more links at the end of the shared key discovery phase. The key management scheme also assumes a revocation phase for removal of the key ring of the compromised sensor node from the network. Also, re-keying phase is assumed for removal of those keys with the expired lifetime.

Claims

1. A method of key-management in Distributed Sensor Networks, comprising the steps of:

prior to deployment of a plurality of sensor nodes of the Distributed Sensor Network, storing a respective key ring including a plurality of individually selectable private keys in each sensor node of the Distributed Sensor Network, said private keys being randomly chosen from a common pool, said key rings of at least a pair of said sensor nodes having a pre-defined probability of having at least one private key in common;

wherein the step of storing a respective key ring further includes the steps of;

generating a key space having a multiplicity of keys,

randomly selecting a pool of keys from said key space,

assigning a specific key identifier for each key in said pool of keys,

randomly selecting a number of the keys from said pool of keys to form said respective key ring for each sensor node, said number of keys being probabilistically determined to provide said pre-defined probability of said pair of sensor nodes having at least one shared private key, and

storing said specific key identifier with said respective key ring in each said sensor node;

deploying said plurality of the sensor nodes of the Distributed Sensor Network;

actuating at least one sensor node to discover at least another sensor node sharing said at least one private key to establish a secure communication link between said one sensor node and another of said sensor nodes; and

using said at least one shared private key for subsequent secure communication between said at least one sensor node and said other sensor node.

2. The method of claim 1, wherein the step of deploying is preceded by the step of:

assigning to each said sensor node a specific sensor identifier.

3. The method of claim 2, where the step of actuating includes the step of:

broadcasting said key identifiers with said specific sensor identifier associated with said at least one sensor node to discover said at least another sensor node and establish a link therewith.

4. The method of claim 2, wherein the step of deploying is preceded by the steps of:

providing a controller node to securely communicate with a plurality of said sensor nodes for collecting data therefrom;

storing said key identifiers of the keys in said respective key ring of each said sensor node along with said sensor identifier of said each sensor node on said controller node.

5. The method of claim 3 wherein said key identifiers are broadcast in a clear text.

6. The method of claim 3, wherein said key identifiers are broadcast in a hidden pattern.

7. The method of claim 4, further comprising the steps of:

computing a plurality of sensor-controller keys respectively shared by said plurality of sensor nodes with said controller node, and loading said controller node and each of said sensor nodes with an associated one of said sensor-controller keys.

8. The method of claim 4, further comprising the steps of:

upon compromising of at least one sensor node, revoking said at least one compromised sensor node by broadcasting from said controller node a revocation message containing a signed list of the key identifiers of the key ring of said compromised sensor node to be revoked.

9. The method of claim 8, further comprising the steps of:

generating a signature key for said list and unicasting the same to each said sensor node.

10. The method of claim 9, further comprising the steps of:

upon obtaining of said signature key by an uncompromised sensor node, verifying said signature key of said signed list of the key identifiers of the key ring of said compromised sensor node, locating said key identifiers in said key ring of said uncompromised sensor node, and removing keys corresponding to the key identifiers of the compromised keys from said key ring of said uncompromised sensor node.

11. The method of claim 8, further comprising the steps of:

reconfiguring the communication links of the sensor nodes affected by revocation of said compromised sensor node.

12. The method of claim 1, further comprising the steps of:

upon expiration of at least one key shared by said at least one and the other sensor node, removal of said expired at least one key from said key rings of said at least one and the other sensor nodes, and searching for another key common for said at least one and the other sensor nodes to establish a new communication link therebetween.

13. The method of claim 1, further comprising the steps of:

generating a connectivity random graph for said Distributed Sensor Network, and computing the number of the sensor nodes, the number of keys in said pool of keys and the size of each said key ring, sufficient to provide for a connected Distributed Sensor Network.

14. The method of claim 1, further comprising the step of:

assigning a path-key to a selected pair of sensor nodes connected by at least two communication links.

15. A Distributed Sensor Network system, comprising:

at least two sensor nodes, each said sensor node being pre-loaded prior to deployment thereof with a respective key ring including a plurality of individually selectable private keys randomly chosen from a common pool, the key rings of at least a pair of said sensor nodes having a pre-defined probability of having at least one private key in common, each of said private keys of said key ring having an associated key identifier stored in a corresponding sensor node;

each of said sensor nodes having means for searching for another sensor node where a plurality of said key identifiers are broadcast to search for other sensor nodes with a matching of at least one of the key identifiers, said matching key identifier indicating the other sensor node has a private key in common therewith to establish a secure communication link therebetween;

means for generating a key space having a multiplicity of keys, means for randomly selecting a pool of keys from said key space, means for assigning a specific key identifier for each key of said pool of keys, and means for randomly selecting a distinct set of private keys from said pool of keys for each said sensor node to thereby form said respective key rings for said sensor nodes.

16. The Distributed Sensor Network system of claim 15, further comprising:

at least one controller node for secure communication with at least one of sensor nodes, said at least one controller node having said key identifiers of said key ring of said at least one sensor node and a specific sensor identifier of said at least one sensor node saved therein, and a sensor-controller key stored therein and respectively stored in a corresponding sensor node.

17. The Distributed Sensor Network system of claim 16, further comprising means for generating a revocation message and broadcasting the same for revocation of a compromised at least one of said two sensor nodes, said revocation message containing a signed list of said key identifiers of said key ring of said compromised sensor node.

18. The Distributed Sensor Network system of claim 17, further comprising means for reconfiguring communication links of said at least another sensor node affected by revocation of said compromised sensor node.

19. The Distributed Sensor Network system of claim 15, further comprising means for assigning a path-key to a selected pair of sensor nodes connected by at least two communication links.