Context-free protocol for enforcing data forwarding in wireless ad hoc networks

• US 8,374,352 B2
• Filed: 04/13/2009
• Issued: 02/12/2013
• Est. Priority Date: 04/13/2009
• Status: Active Grant

• Current Assignee: Hong Kong University of Science and Technology
• Original Assignee: Hong Kong University of Science and Technology
• Inventors: Song, Chengqi, Zhang, Qian
• Primary Examiner(s): LEMMA, SAMSON B
• Application Number:
  US12/422,722
• Publication Number:
  US 20100260337A1
• Time in Patent Office: 1,401 Days
• Field of Search: 380/30, 380/33, 380/259, 380/270, 713/171, 713/160
• US Class Current: 380/270
• CPC Class Codes: H04L 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• CPC Class Codes: H04L 2463/062 applying encryption of the keys cryptographic mechanisms or cryptographic arrangements for key distribution using key encryption key H04L9/0822
• CPC Class Codes: H04L 63/062 for key distribution, e.g. centrally by trusted party cryptographic mechanisms or cryptographic arrangements for key distribution involving a central third party H04L9/0819
• CPC Class Codes: H04L 9/0827 involving distinctive intermediate devices or communication paths network architectures or network communication protocols using different networks H04L63/18
• CPC Class Codes: H04W 12/033 of the user plane, e.g. user's traffic
• CPC Class Codes: H04W 12/04 Key management, e.g. using generic bootstrapping architecture [GBA]

Abstract

Described herein is a context-free protocol (i.e., the COFFEE protocol) for stimulating cooperation among selfish nodes. Various embodiments have the ability to transmit a packet over the path successfully without the dependency on the information of other packets'"'"' transmissions. It is assumed that every node in the network is rational, and therefore during the packet forwarding stage, if the intermediate nodes can not clearly tell whether the packet is destined to them or not, they do not simply drop the packet. Thus, in the COFFEE protocol, by introducing several techniques, for a packet received by a node, the node thinks the packet could potentially be destined to itself and forwards the packet to find out the answer. Detailed analysis and performance evaluations have been conducted to demonstrate the effectiveness of the COFFEE protocol.

Claims

1. A method for enforcing data forwarding in a wireless ad hoc network, the method comprising:

encrypting, by a processor, data in a data packet based on a packet key;

encrypting the packet key based on a plurality of node keys, corresponding to a plurality of nodes;

transmitting the data packet with the encrypted packet key through a predetermined path to a destination node; and

making the packet key available to the destination node only after the destination node forwards the data packet to at least one neighboring node, so as to enable the destination node to decrypt the data in the data packet encrypted by the packet key.

2. The method of claim 1, wherein the predetermined path includes a plurality of intermediate nodes and the at least one neighboring node, and wherein the packet key is a symmetric key and the plurality of node keys are public keys.

3. The method of claim 2, wherein the data packet includes a first portion for carrying the encrypted data and a second portion for carrying the packet key encrypted based on the plurality of node keys.

4. The method of claim 1, wherein encrypting the packet key based on a plurality of node keys further comprises:

encrypting the packet key based on the plurality of node keys in an order opposite to the order through which the plurality of corresponding nodes are traversed during the transmission of the data packet through the predetermined path.

5. The method of claim 3, further comprising modifying the second portion of the data packet at each node in the predetermined path based on one of the plurality of node keys.

6. The method of claim 1, further comprising:

applying a node key to the encrypted packet key at the at least one neighboring node;

and

wherein making the packet key available comprises applying another node key to the encrypted packet key.

7. The method of claim 5, wherein the step of modifying the second portion of the data packet further comprises:

generating a decryption result by decrypting the second portion of the data packet based on one of the plurality of node keys; and

storing the decryption result in the second portion of the data packet.

8. The method of claim 7, wherein the data packet includes a third portion for carrying a pre-calculated hash value, and the method further comprises:

generating a hash value from the decryption result; and

determining that the hash value is not identical to the pre-calculated hash value.

9. The method of claim 3, wherein the data packet includes a third portion for carrying a pre-calculated hash value, and the method further comprises:

decrypting, at the destination node, the data packet using the packet key;

generating a hash value from the decrypted data packet; and

determining that the hash value is identical to the pre-calculated hash value.

10. A method for enforcing forwarding of a data packet in a wireless ad hoc network, wherein the data packet has a first portion encrypted based on a key and a second portion carrying the key, the method comprising:

receiving the data packet at a destination node at a first time;

modifying, by a processor, the second portion of the data packet;

transmitting the data packet to at least one of a plurality of intermediate nodes;

receiving the data packet at the destination node at a second time later than the first time; and

determining, at the destination node, the key from the second portion of the data packet so as to enable the destination node to decrypt the first portion of the data packet.

11. The method of claim 10, wherein before receiving the data packet at the destination node at the second time, the data packet has traversed a predetermined path including the plurality of intermediate nodes and the destination node, and wherein the key is encrypted based on a plurality of node keys, each of the plurality of node keys being associated with one of a plurality of intermediate nodes and the destination node.

12. The method of claim 11, wherein before the destination node transmits the data packet to at least one of the plurality of intermediate nodes, the method further comprises:

generating, by the destination node, a decryption result from the second portion of the data packet based on a node key associated with the destination node;

calculating, by the destination node, a hash value from the decryption result;

determining, by the destination node, that the hash value is not identical to a pre-calculated hash value stored in the data packet; and

storing, by the destination node, the decryption result in the second portion of the data packet.

13. The method of claim 11, wherein after the destination node receives the data packet at the second time, the method further comprises:

generating, by the destination node, a decryption result from the second portion of the data packet based on a node key associated with the destination node;

calculating, by the destination node, a hash value from the decryption result; and

determining, by the destination node, that the hash value is identical to a pre-calculated hash value stored in the data packet.

14. The method of claim 11, wherein the plurality of intermediate nodes and the destination node of the predetermined path are arranged in a predetermined order and wherein the key is encrypted based on the plurality of node keys in a reverse order with respect to the predetermined order.

15. A method for enforcing data forwarding in a wireless ad hoc network, the method comprising:

encrypting data in a data packet based on a key;

transmitting the data packet with the key from a source node to a destination node by way of a predetermined path including a plurality of intermediate nodes, wherein the predetermined path includes transmission of the data packet with the key from the destination node to at least one neighboring node and transmission of the data packet back to the destination node after the transmission of the data packet with the key from the destination node to the at least one neighboring node; and

decrypting the data in the data packet at the destination node based on the key after the data packet has been transmitted through the predetermined path.

16. The method of claim 15, further comprising encrypting the key in the data packet based on a plurality of node keys, wherein each of the plurality of node keys is associated with one of the plurality of intermediate nodes and the destination node.

17. The method of claim 16,

wherein the key is encrypted based on the plurality of node keys in a reverse order with respect to the predetermined path.