Secure routing protocol for an ad hoc network using one-way/one-time hash functions

• US 7,401,217 B2
• Filed: 08/12/2003
• Issued: 07/15/2008
• Est. Priority Date: 08/12/2003
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Electric Information Technology Center America, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Cukier, Johnas I., Huang, Qiang
• Primary Examiner(s): Barron, Jr.; Gilberto
• Assistant Examiner(s): Kim; Jung
• Application Number:
  US10/639,575
• Publication Number:
  US 20050036616A1
• Time in Patent Office: 1,799 Days
• Field of Search: 380/270
• US Class Current: 713/153
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 63/0838 using one-time-passwords
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

A method authenticates packets that are transmitted serially in a network. A current password is selected for a current packet to be transmitted. The current packet includes current data. A one-way/one-time hash function is applied to the current password to form a current tag. A next password is selected for a next packet that includes next data, and the one-way/one-time hash function is applied to the next password to form a next tag. The one-way/one-time hash function is then applied to the next data, the next tag, and the current password to obtain a hashed value. The current packet is then transmitted to include the hash value, the current data, the current tag, and a previous password of a previous transmitted packet to authenticate the current data.

Claims

1. A method for authenticating packets transmitted serially in an ad hoc network, comprising:

selecting a current password P_i for a current packet to be transmitted, the current packet including current data M_i;

applying a one-way/one-time hash function h to the current password P_i to form a current tag Y_i of the current packet as Y_i=h(P_i);

selecting a next password P_i+1 for a next packet to be transmitted, the next packet including next data M_i+1;

applying the one-way/one-time hash function h to the next password P_i+1 to form a next tag Y_i+1 of the next packet as Y_i+1=h(P_i+1);

applying the one-way/one-time hash function h to the next data M_i+1 the next tag Y_i+1, and the current password P_i of the current packet to obtain Z_i+1=h(M_i+1, Y_i+1, P_i); and

transmitting, in an ad hoc network, the current packet from a source node to a destination node via intermediate nodes along a route including multiple hops, the current packet including Z_i+1, the current data M_i, the current tag Y_i, and a previous password P<sub>i−

1</sub> of a previously transmitted packet to authenticate the current data M_i, in which the transmitting further comprises;

maintaining, in a route cache in each node along the route, a node list describing the route through the ad hoc network; and

applying the one-way/one-time hash function h on a per hop basis along the route to verify that no intermediate hop is omitted in a node list.

2. The method of claim 1, in which a first password of a first packet is authenticated with a digital signature at the source node and the intermediate nodes.

3. The method of claim 1, in which the plurality of packets include control packets and the data are route requests for discovering a route in the ad hoc network.

4. The method of claim 3, in which the data include a source address and a destination address of the route.

5. The method of claim 1, in which the passwords are selected randomly by the source node and the intermediate nodes.

6. The method of claim 1, in which the plurality of packets include control packets and the data are route replies for a discovered route in the ad hoc network.