Xian-wei Zhou Shuai Du Ji-jian Meng Kun Shi Internet-Draft Guang Yang Intended status: Internet Draft Ling Zhou Expires: July 10, 2009 January 3, 2009 Secure and Scalable Location Routing Protocol (SSLRP) for Ad Hoc Networks draft-zhou-ustb-sslrp-00.txt Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html This Internet-Draft will expire on July 10, 2009. Copyright Notice Copyright (c) 2008 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Zhou et al. Expires July 10, 2009 [Page 1] Internet-Draft SSLRP 3 January 2009 Abstract The Secure and Scalable Location Routing Protocol (SSLRP) is a secure and distributed routing protocol designed for ad hoc networks of mobile nodes with location information. Commonly, each node acquires its own geographic position using a mechanism such as the Global Position System (GPS). The SSLRP addresses each node using the hybrid of its multi-level hierarchical address and unique identifier at the moment of network initialization. Certain measures were adopted to ensure security of the network. Zhou et al. Expires July 10, 2009 [Page 2] Internet-Draft SSLRP 3 January 2009 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3. Applicability Statement . . . . . . . . . . . . . . . . . . . . . 4 4. Message Formats . . . . . . . . . . . . . . . . . . . . . . . . . 5 4.1. Location Request (LREQ) Message Format . . . . . . . . . . 5 4.2. Location Reply (LREP) Message Format . . . . . . . . . . . 6 4.3. Location Error (LERR) Message Format . . . . . . . . . . . 7 4.4. Location Reply Acknowledgment (LREP-ACK) Message Format . 8 4.5. Home_location request (HREQ) Message Format . . . . . . . 9 4.6. Home_location reply (HREP) Message Format . . . . . . . . 10 4.7. Location Update (LUP) Message Format . . . . . . . . . . . 11 4.8. Location Update Broadcast (LUB) Message Format . . . . . . 12 4.9. Authentication Request (AREQ) Message Format . . . . . . . 13 4.10. Authentication Start (AST) Message Format . . . . . . . . 14 4.11. Authentication Reply (AREP) Message Format . . . . . . . 15 4.12. Authentication Execution (AEX) Message Format . . . . . . 16 4.13. Authentication Return (ARET) Message Format . . . . . . . 17 5. Protocol operation . . . . . . . . . . . . . . . . . . . . . . . 18 5.1. Network Initialization . . . . . . . . . . . . . . . . . . 18 5.1.1. Region-Code/Node-ID Hybrid Addressing (RIHA) . . . 18 5.1.2. Merkle Hash Tree . . . . . . . . . . . . . . . . . 19 5.2. Geographic Forwarding . . . . . . . . . . . . . . . . . . 19 5.3. Location Information Update . . . . . . . . . . . . . . . 20 5.3.1. Selecting Location Service . . . . . . . . . . . . 20 5.3.2. Entity Authentication . . . . . . . . . . . . . . 21 5.4. Location Service Maintenance . . . . . . . . . . . . . . . 22 5.5. Location Discovery . . . . . . . . . . . . . . . . . . . . 22 5.6. Empty Region . . . . . . . . . . . . . . . . . . . . . . . 23 5.7. Dead-end Operations . . . . . . . . . . . . . . . . . . . 23 6. Security Considerations . . . . . . . . . . . . . . . . . . . . . 23 7. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . 23 8. References . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 9. Author's Addess . . . . . . . . . . . . . . . . . . . . . . . . . 25 Zhou et al. Expires July 10, 2009 [Page 3] Internet-Draft SSLRP 3 January 2009 1. Introduction The Secure and Scalable Location Routing Protocol is a secure and distributed routing protocol designed for ad hoc networks of mobile nodes with location information. Commonly, each node acquires its own geographic position using a mechanism such as the Global Position System (GPS). The SSLRP addresses each node using the hybrid of its multi-level hierarchical address and unique identifier at the moment of network initialization. With this previous scheme, nodes use a simple mechanism to determine location update and query. The SSLRP adopts some security mechanisms including broadcast authentication protocol, entity authentication and key management scheme. The broadcast authentication protocol enables the receivers to verify that the broadcast packets they received were actually sent by the claimed sender. The entity authentication scheme using the concept of Merkle hash tree may obtain an effective safe authentication strategy, combining the network clustering technology. While the key management scheme does not rely on any center of the network, and solves the problem of single-point failure effectively. It also introduces the Diffie-Hellman algorithm and improves security of Ad Hoc networks effectively. 2. Terminology MFR The most forward within radius policy (MFR) selects the node with the minimum remaining distance to the destination's position. Location Server Location service is a cooperative service in which nodes are both clients and servers. As a node moves, it must update its location information. MAC A cryptographic message authentication code (MAC) is a short piece of information used to authenticate a message. A MAC algorithm accepts as input a secret key and an arbitrary-length message to be authenticated, and outputs a MAC. 3. Applicability Statement The SSLRP is designed for large scale mobile ad hoc networks with mobile nodes carrying positioning device.SSLRP addresses each node using the hybrid of its multilevel hierarchical address, in order to improve the performances of location update and query. SSLRP is secure because it adopts the broadcast authentication protocol, entity authentication and key management scheme. Zhou et al. Expires July 10, 2009 [Page 4] Internet-Draft SSLRP 3 January 2009 4. Message Formats Though there might be a little more control messages, they are all necessary. Some are for routing processing, others are to ensure high security. 4.1. Location Request (LREQ) Message Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | Time | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | LREQ Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Current Location | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Location Request message is illustrated above, and contains the following fields: Type 1 Reserved Sent as 0; ignored on reception. Time Timestamp of sending packets. Hop Count The number of hops from the originator IP address to the node handling the request. LREQ Sequence Number A sequence number uniquely identifying the particular LREQ when it's taken in conjunction with the originating node's RIHA. Destination HA Address The HA address of the destination combined region code with Node ID. It is the HA address of the destination for which a route is desired. Originator Current Location The current region number of the originator. Zhou et al. Expires July 10, 2009 [Page 5] Internet-Draft SSLRP 3 January 2009 Originator HA Address The HA address of the node which originated the Location Request. Signature The signature of all the fields in the SSLRP packet that are before this field but the Hop Count field. This field has variable length, but it must be 32-bits aligned. Public Key The public key of the originator of the message. This field has variable length, but it must be 32-bits aligned. 4.2. Location Reply (LREP) Message Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | Time | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination Current Location | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Current Location | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Lifetime | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Route Reply message is illustrated above, and contains the following fields: Type 2 Reserved Sent as 0; ignored on reception. Time Timestamp of sending packets. Hop Count The number of hops from the Originator IP Address to the node handling the request. Destination HA Address The HA address of the destination for which a route is supplied. Zhou et al. Expires July 10, 2009 [Page 6] Internet-Draft SSLRP 3 January 2009 Destination Current Location The current region number of the Destination. Originator HA Address The HA address of the node which originated the Location Reply. Originator Current Location The current region number of the Originator. Lifetime The time in milliseconds for which nodes receiving the LREP consider the route to be valid. Signature The signature of the all the fields in the SSLRP packet that are before this field but the Hop Count field. This field has variable length, but it must be 32-bits aligned. Public Key The public key of the originator of the message. This field has variable length, but it must be 32-bits aligned. 4.3. Location Error (LERR) Message Format 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | Time | DestCount | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Unreachable Destination HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Unreachable Destination Current location | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-| | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Route Error message is illustrated above, and contains the following fields: Type 3 Reserved Sent as 0; ignored on reception. Time Timestamp of sending packets. DestCount The number of unreachable destinations included in the message; MUST be at least 1. Zhou et al. Expires July 10, 2009 [Page 7] Internet-Draft SSLRP 3 January 2009 Unreachable Destination HA Address The HA address of the destination that has become unreachable due to a link break. Unreachable Destination Current Location The current region number in the route table entry for the destination listed in the previous Unreachable Destination HA Address field. Signature The signature of the all the fields in the SSLRP packet that are before this field but the DestCount field. This field has variable length, but it must be 32-bits aligned. Public Key The public key of the originator of the message. This field has variable length, but it must be 32-bits aligned. 4.4. Location Reply Acknowledgment (LREP-ACK) Message Format The Location Reply Acknowledgment (LREP-ACK) message will be sent in response to a LREP message. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Location Reply Acknowledgment message is illustrated above, and contains the following fields: Type 4 Reserved Sent as 0; ignored on reception. Signature The signature of all the fields in the SSLRP packet. This field has variable length, but it must be 32-bits aligned. Public Key The public key of the originator of the message. This field has variable length, but it must be 32-bits aligned. Zhou et al. Expires July 10, 2009 [Page 8] Internet-Draft SSLRP 3 January 2009 4.5. Home_location request(HREQ) Message Format The Home_location request(HREQ) message will be sent to its neighbors when a node moves into a new region. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type |S| Reserved | Time | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | HREQ Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Home_location Request Message is illustrated above, and contains the following fields: Type 5 S State flag; '1' indicates that the node enters into a new grid and '0' indicates that the node moves out of the previous grid. Reserved Sent as 0; ignored on reception. Time Timestamp of sending packets. Hop Count The Hop Count must be 1; others will be ignored. HREQ sequence number A sequence number uniquely identifying the particular HREQ when it's taken in conjunction with the originating node's HA address. Originator HA Address The HA address of the node which originated the Home_location Request. Signature The signature of all the fields in the SSLRP packet that are before this field but the Hop Count field. This field has variable length, but it must be 32-bits aligned. Public Key The public key of the originator of the message. This field has variable length, but it must be 32-bits aligned. Zhou et al. Expires July 10, 2009 [Page 9] Internet-Draft SSLRP 3 January 2009 4.6. Home_location reply(HREP) Message Format The Home_location request(HREP) message will be sent when a node receives the HREQ message. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | Time | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | HREP Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Home_location Reply Message is illustrated above, and contains the following fields: Type 6 Reserved Sent as 0; ignored on reception. Time Timestamp of sending packets. Hop Count The Hop Count must be 1; Others will be ignored. HREP sequence number A sequence number uniquely identifying the particular HREP when it's taken in conjunction with the originating node's HA address. Originator HA Address The HA address of the node which originated the Home_location Request. Signature The signature of all the fields in the SSLRP packet that are before this field but the Hop Count field. This field has variable length, but it must be 32-bits aligned. Public Key The public key of the originator of the message. This field has variable length, but it must be 32-bits aligned. Zhou et al. Expires July 10, 2009 [Page 10] Internet-Draft SSLRP 3 January 2009 4.7. Location Update (LUP) Message Format The Location Update Message will be sent to its location services when a node moves into a new region. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | Time | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator Current Location | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Update Destination region | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Update Timeout | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Location Update Message is illustrated above, and contains the following fields: Type 7 Reserved Sent as 0; ignored on reception. Time Timestamp of sending packets. Hop Count The Hop Count must be 1; Others will be ignored. Originator HA Address The HA address of the node which originated the Location Update Message. Originator Current Location The current region number of the Originator. Update Destination region The location service region number of the orginator. Update Timeout It is a value that corresponds to the periodic update interval. Zhou et al. Expires July 10, 2009 [Page 11] Internet-Draft SSLRP 3 January 2009 Signature The signature of all the fields in the SSLRP packet that are before this field but the Hop Count field. This field has variable length, but it must be 32-bits aligned. Public Key The public key of the originator of the message. This field has variable length, but it must be 32-bits aligned. 4.8. Location Update Broadcast(LUB) Message Format The Location Update Broadcast Message will be sent to its neighbors when a node receives the LUP message. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | Time | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sender HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sender Current Location | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Location Update Broadcast Message is illustrated above, and contains the following fields: Type 8 Reserved Sent as 0; ignored on reception. Time Timestamp of sending packets. Hop Count The Hop Count must be 1; Others will be ignored. Sender HA Address The HA address of the node which send the Location Update Message. Sender Current Location The current region number of the Sender. Zhou et al. Expires July 10, 2009 [Page 12] Internet-Draft SSLRP 3 January 2009 Destination HA Address The HA Addresses of all nodes in the home region. Signature The signature of all the fields in the SSLRP packet that are before this field but the Hop Count field. This field has variable length, but it must be 32-bits aligned. Public Key The public key of the originator of the message. This field has variable length, but it must be 32-bits aligned. 4.9. Authentication Request(AREQ) Message Format The Authentication Request Message will be sent when a node moves into a new region. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | Time | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | AREQ Sequence Number | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | MAC | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Location Update Broadcast Message is illustrated above, and contains the following fields: Type 9 Reserved Sent as 0; ignored on reception. Time Timestamp of sending packets. Hop Count The Hop Count must be 1; Others will be ignored. AREQ Sequence Number A sequence number uniquely identifying the particular AREQ when it's taken in conjunction with the originating node's HA address. Destination HA Address The HA Addresses of all nodes in the home region. Zhou et al. Expires July 10, 2009 [Page 13] Internet-Draft SSLRP 3 January 2009 Originator HA Address The HA address of the node which originated the Location Authentication Request Message. MAC Hash the Timestamp and the Originator HA Address along with K. 4.10. Authentication Start(AST) Message Format The Authentication Start Message will be sent to the members of the Merkle Hash Tree by the cluster head when the Timestamp matches with the MAC. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | Time | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | MAC | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Authentication Start Message is illustrated above, and contains the following fields: Type 10 Reserved Sent as 0; ignored on reception. Time Timestamp of sending packets. Hop Count The Hop Count must be 1; Others will be ignored. Destination HA Address The HA Addresses of Merkle Hash Tree members. Originator HA Address The HA Address of the cluster head. MAC Hash Type, Time and the Originator HA Address along with K1. Zhou et al. Expires July 10, 2009 [Page 14] Internet-Draft SSLRP 3 January 2009 Signature The signature of all the fields in the SSLRP packet that are before this field but the Hop Count field. This field has variable length, but it must be 32-bits aligned. Public Key The public key of the originator of the message. This field has variable length, but it must be 32-bits aligned. 4.11. Authentication Reply(AREP) Message Format The Authentication Reply Message will be sent to the new node by the cluster head when the Timestamp matches with the MAC. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | Time | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | MAC | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | m[1-m] | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Authentication Reply Message is illustrated above, and contains the following fields: Type 11 Reserved Sent as 0; ignored on reception. Time Timestamp of sending packets. Hop Count The Hop Count must be 1; Others will be ignored. Destination HA Address The HA Addresses of the new node. Originator HA Address The HA Address of the cluster head. Zhou et al. Expires July 10, 2009 [Page 15] Internet-Draft SSLRP 3 January 2009 MAC Hash m[1-m] and the Originator HA Address along with K. m[1-m] The root key of Merkle Hash Tree. Signature The signature of all the fields in the SSLRP packet that are before this field but the Hop Count field. This field has variable length, but it must be 32-bits aligned. Public Key The public key of the originator of the message. This field has variable length, but it must be 32-bits aligned. 4.12. Authentication Execution(AEX) Message Format The Authentication Execution Message will be sent to the new node by Merkle Hash Tree members when Merkle Tree members receive AST. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | Time | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | MAC | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | m[j] | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Authentication Execution Message is illustrated above, and contains the following fields: Type 12 Reserved Sent as 0; ignored on reception. Time Timestamp of sending packets. Hop Count The Hop Count must be 1; Others will be ignored. Destination HA Address The HA Addresses of the new node. Zhou et al. Expires July 10, 2009 [Page 16] Internet-Draft SSLRP 3 January 2009 Originator HA Address The HA Address of the cluster head. MAC Hash m[j] along with K. mj The key of originator. 4.13. Authentication Return(ARET) Message Format The Authentication Execution Message will be sent to Merkle Hash Tree members by the new node when it receives the AEX. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Reserved | Time | Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Destination HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Originator HA Address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | MAC | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Cipher Text | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ The format of the Authentication Execution Message is illustrated above, and contains the following fields: Type 13 Reserved Sent as 0; ignored on reception. Time Timestamp of sending packets. Hop Count The Hop Count must be 1; Others will be ignored. Destination HA Address The HA Addresses of Merkle Hash Tree members. Originator HA Address The HA Address of the new node. MAC Hash the authentication key Sj and M along with K. Cipher Text Encrypt the authentication key Sj and M with K. Zhou et al. Expires July 10, 2009 [Page 17] Internet-Draft SSLRP 3 January 2009 5.Protocol Operation This section describes how Location Service and Geographic Forwarding are performed in SSLRP. Authentication and key management are also used to protect the routing data. 5.1. Network Initialization In the network, each node can acquire its own position using the Positioning Device(e.g., GPS or other techniques). The mobile ad hoc network with N nodes can be considered as a square region with area of A for explicit explanation, yet it can be any shape. SSLRP divides the square into G unit regions, which are also called level-0 grids. In fact, the shape of level-0 grids are decided basing on the shape of the network. The size of the level-0 grid should be fully covered by a node's transmission range, that is to say, the side length of the level-0 grid should be (2^(1/2))/2 times of transmisson radius in maximum.It then combines k*k of the level-0 grids to form a level-1 grid, while k*k of the level-i grids form a level-(i+1) grid. (k=2,3,...) At the top level, the entire area is called level-H grid. According to this division method, the entire region is divided into k^2 level-0 grids. 5.1.1. Region-Code/Node-ID Hybrid Addressing (RIHA) First, a novel addressing scheme has been proposed. It combines region code which indicates its hierachical location with its node ID. They compose a new node address denoting node's identification instead of node ID. It is named RIHA (Region-code/node-ID Hybrid Addressing). RC is short for Region Code. By applying a Cartesian coordinate system to the network area, with the lower left point as the origin of the system, the level-i grid of a node A is formally defined as follows. Definition 1 (level-i grid): Let the current coordinates of a node A be (xA,yA), the level-i grid of A is a square area with lower left point (xA0,yA0) and side length of 2^(i)R, where xA0 = xA - (xA mod k^(i)R) yA0 = yA - (yA mod k^(i)R) Node's level-i region code can be defined by substitution of xA0,yA0 in a strong hash function. Node's integrity region code can be represented as (RC[H]|RC[H-1]|...|RC[1]|RC[0]). The address space of Region Code can be calculated as follows: decimal digit L can be expressed by m bit binary numbers, relationship of L and m is 2^(m-1) where MAC(Kdh(m)) (or MAC(K( m+MAC(Kdh(m))))) represents the MAC computed over message m ( or m+MAC(Kdh(m))) computed using key Kdh(or group key K). The sender discloses the key K at the end of the same packet. When the source node and destination node are not in the same cluster, the source node will first send the following message: < MAC(K(m+MAC(Kdh(m)))), MAC(Kdh(m)), m, K > to the cluster head, then the cluster head will verify that the key K at the end of the packet is authentic. After that, the cluster head sends the message which includes the MAC computed over message (m+MAC(Kdh(m))) using key Kc to the chosen cluster head and discloses the key Kc at the end of the packet. When the packet reaches the cluster-destination, the cluster head will send the following message: < MAC(K(m+MAC(Kdh(m)))), MAC(Kdh(m)), m, K > where the K represents the group key of the cluster-destination. 5.3. Location Information Update When a node moves out of the current grid, it sends a location update packet(LUP) to its location services. Then it will be authenticated by nodes in the new grid which it moves into. Upon authenticated a new node, the new grid will update its group keys. The details are as follows. 5.3.1. Selecting Location Service A node selects k*k level-0 grids which have the same region code of level-0 to level-(i-1) as its RIHA address located in the current level-(i+1) grid to be its level-i location service grids. All nodes in the grids are location services and maintain its level-i location cache. Especially, level-0 location service grid is the one which has the same region code of level-0 as its RIHA address located in the current level-1 grid. Nodes in that region maintain its accurate location cache. Zhou et al. Expires July 10, 2009 [Page 20] Internet-Draft SSLRP 3 January 2009 When a node moves out of the current level-i grid, it sends location update packet(LUP) to its level-i location service grids. Each node knows its location service grids and a location update packet(LUP) is sent towards the center of the level-i location service grid in the current level-(i+1) grid. Upon receiving LUP, nodes in that region forward the LUP to the other k*k-1 location service grids by constructing a BFS-tree. Any node receiving the LUP in the location service grids updates its cache and broadcasts a Location Update Broadcast packet(LUB) with the new location information to all nodes in the location service grids. 5.3.2. Entity Authentication When a node T enters a new grid, it will first apply for joining into the cluster C. CA gives the authentication dataset (group key K, authentication key Sj) to T. Then the authentication starts: 1) Node T generates an AREQ and broadcasts it to all cluster members. 2) When the cluster head receives the AREQ, it will first check the timestamp, then check MAC with k. If passed, the cluster head informs the cluster members to enter Merkle Hash Tree state by sending AST packets, and sends AREP packet to node T. If not, the cluster head drops the AREQ, and refuses to authenticate. 3) All the merkle hash tree members send AEX packets to node T except the node with authentication key. 4) Receiving all the AEX packets, node T gathers all the sub-keys of the merkle hash tree together with authentication key it received earlier. First, it calculates the root-key according to these sub-keys and compares with the m(1-m) received earlier. If they are not the same, the authentication will be terminated. Node T informs CA that there are compromised nodes in the cluster. If they are the same, node T calculates all the sub-keys in the merkle hash tree and sends ARET packets to the authentication nodes. 5) When the authentication node J receives ARET packet, it will decrypt the Cipher Text to get m and verify it. After that, it compares mj with its own sub-key. If they are the same, node J selects all the sub-keys except its own and calculates root-key. If the root-key is the same as m(1-m), node T passed the authentication by node J. 6) The cluster head calculates the number of members who admited node T. If the number is greater than X( m/2=