Internet DRAFT - draft-liu-ustb-srp
draft-liu-ustb-srp
Internet Engineering Task Force Tao Liu
INTERNET-DRAFT Xian-wei Zhou
<draft-liu-ustb-srp-00.txt> Shuai Du
Intended status: Internet Draft U. S. T. B
Expires: June 10, 2013 December 7, 2012
Secure Routing Protocol for Delay and Tolerant Networks
draft-liu-ustb-srp-00.txt
Status of this Memo
This Internet-Draft is submitted 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 June 10, 2013.
Copyright Notice
Copyright (c) 2012 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. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License.
Liu et al. Expires June 10, 2013 [Page 1]
Internet-Draft SRP 7 December 2012
Abstract
The Secure Routing Protocol (SRP) is a secure and distributed
routing protocol designed for Delay and Tolerant Networks 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 SRP 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.
Liu et al. Expires June 10, 2013 [Page 2]
Internet-Draft SRP 7 December 2012
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
Liu et al. Expires June 10, 2013 [Page 3]
Internet-Draft SRP 7 December 2012
1. Introduction
The Secure Routing Protocol is a secure and distributed routing
protocol designed for Delay and Tolerant 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 SRP 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 SRP 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 SRP is designed for large scale mobile ad hoc networks with
mobile nodes carrying positioning device.SRP addresses each node
using the hybrid of its multilevel hierarchical address, in order to
improve the performances of location update and query. SRP is
secure because it adopts the broadcast authentication protocol,
entity authentication and key management scheme.
Liu et al. Expires June 10, 2013 [Page 4]
Internet-Draft SRP 7 December 2012
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.
Liu et al. Expires June 10, 2013 [Page 5]
Internet-Draft SRP 7 December 2012
Originator HA Address
The HA address of the node which originated the
Location Request.
Signature The signature of all the fields in the SRP 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.
Liu et al. Expires June 10, 2013 [Page 6]
Internet-Draft SRP 7 December 2012
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 SRP 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.
Liu et al. Expires June 10, 2013 [Page 7]
Internet-Draft SRP 7 December 2012
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 SRP 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 SRP 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.
Liu et al. Expires June 10, 2013 [Page 8]
Internet-Draft SRP 7 December 2012
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 SRP 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.
Liu et al. Expires June 10, 2013 [Page 9]
Internet-Draft SRP 7 December 2012
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 SRP 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.
Liu et al. Expires June 10, 2013 [Page 10]
Internet-Draft SRP 7 December 2012
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.
Liu et al. Expires June 10, 2013 [Page 11]
Internet-Draft SRP 7 December 2012
Signature The signature of all the fields in the SRP 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.
Liu et al. Expires June 10, 2013 [Page 12]
Internet-Draft SRP 7 December 2012
Destination HA Address
The HA Addresses of all nodes in the home region.
Signature The signature of all the fields in the SRP 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.
Liu et al. Expires June 10, 2013 [Page 13]
Internet-Draft SRP 7 December 2012
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.
Liu et al. Expires June 10, 2013 [Page 14]
Internet-Draft SRP 7 December 2012
Signature The signature of all the fields in the SRP
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.
Liu et al. Expires June 10, 2013 [Page 15]
Internet-Draft SRP 7 December 2012
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 SRP 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.
Liu et al. Expires June 10, 2013 [Page 16]
Internet-Draft SRP 7 December 2012
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.
Liu et al. Expires June 10, 2013 [Page 17]
Internet-Draft SRP 7 December 2012
5.Protocol Operation
This section describes how Location Service and Geographic
Forwarding are performed in SRP. 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. SRP
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)<L<=2^m
Liu et al. Expires June 10, 2013 [Page 18]
Internet-Draft SRP 7 December 2012
The address space of a single region code is p, which can be
calculated by
2^(p-1)<k*k<=2^p
There are H+1 levels in all, the address space can be calculated by
2^(q-1)<H+1<=2^q
Multiplying p by q is the total address space of region code.
Each node has an unique and constant ID which is substitution of
node's MAC address or IP address in a strong hash function. Define
node's RIHA address as the combination of region code and node's ID.
The integrity RIHA adress of a node is defined as:
RC(H-1)|RC(H-2)|...|RC1|RC0
RIHA address is defined according to the location of the node while
the network is initializing. After that, RIHA address is unique and
permanent. It represents node's identity in the network.
5.1.2. Merkle Hash Tree
Nodes in a level-0 grid are considered to be a cluster with a random
chosen cluster head. All cluster members generate two group keys
K1&K. K1 is used to send control message in cluster, while K is used
for authentication request. New node can only get K but not K1. After
that, every cluster generates and maintains a Merkle Hash Tree.
Each cluster chooses m nodes randomly as current authentication nodes
with corresponding sequence number. Authentication nodes calculate
sub-key seperately and root-key together. Each node only knows its
own sub-key and root-key. One is chosen from the subkeys as
authentication key, which is secret to others. Then it will be sent
to CA(Certificate Authority) safely with K. CA maintains a
certification database, with format {Vi|Vi = (Ci,K,Sj),i = 1,...,n}.
Ci is the ID of cluster i, K is group key, Sj is authentication key.
5.2. Geographic Forwarding
When node needs to forward a packet towards location P, the node
consults its neighbor table and chooses the cluster head closest to
P. It then forwards the packet to that node, which itself applies the
same forwarding algorithm. When the packet reaches the
cluster-destination, it will be sent to the destination by the
cluster head.
SRP uses DH(Diffie-Hellman Algorithm) to generate a private key
Kdh, which only belongs to the source node and the destination node.
kDH will be used for the first encryption when the packet is
transmitted.
Liu et al. Expires June 10, 2013 [Page 19]
Internet-Draft SRP 7 December 2012
Since the intermediate nodes have not shared any secret key with the
source, they can not verify the packet. However, each intermediate
node needs to authenticate the previous node to avoid message
tampering and replay attacks. So the TIK protocol is used for
hop-by-hop authentication.
When the source node and destination node are in the same cluster,
the source node will send the following message:
< MAC(K(m+MAC(Kdh(m)))), MAC(Kdh(m)), m, K >
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.
Liu et al. Expires June 10, 2013 [Page 20]
Internet-Draft SRP 7 December 2012
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=<X<=m ), the cluster will
admits node T.
7) The cluster head updates the group key and sends it to all the
members.
Liu et al. Expires June 10, 2013 [Page 21]
Internet-Draft SRP 7 December 2012
5.4. Location Service Maintenance
Nodes in a Location Service Grid are also mobile, and thus the set of
nodes in a region changes over time. In SRP, all the nodes of a
Location Service Grid are responsible for keeping location
information for nodes registered in that region. All nodes keep a
list, node_list, of other nodes located within the same region as
themselves. This list is updated as new nodes arrive or leave.
When a node moves into a new grid, it sends a HREQ packet to its
neighbor requering location information of the nodes registered
there. Any neighbor which has such location entries generates a
HREP packet to the node.
When the node detect that it left the previous grid, it broadcasts
HREQ packets in its previous grid informing all nodes of its
departure. All nodes in that grid then modify their node_lists. When
a node_list has just one entry, that entry represents the last node
present in the grid. When this node leaves the grid, the grid will be
empty. It will be discussed in section 5.6.
After the node leaves the grid, the cluster head will generate a new
group key and broadcast to all cluster members.
5.5. Location Discovery
Say some node S wants to send a data packet to D, it needs first to
find the current location of D. Therefore it generates LREQ packet
and sends to Location Service of D.
First, node S inquires the region code of level-(h-1) grid which node
D located in from the level-(h-1) location services of node D in the
current level-(h-1) grid.
Second, these location services forward the LREQ packet to the
level-(h-2) location services of node D in the level-(h-1) grid
acquired before. There are k*k level-(h-2) location services in that
grid, the one with the same region code as the level-(h-1) region
code of node S is chosen to be the forward destination.
By parity of reasoning, the LREQ packet is forwarding to level-0
location service of node D to inquire the region code of level-0 grid
which node D located in.
Receiving LREQ packet, node D generates a LREP packet and forwards it
back to node S using MFR route scheme.
Finally, the two nodes can communicate with each other.
A node SHOULD NOT originate more than RREQ_RATELIMIT RREQ messages in
certain interval. If a route is not received in NET_TRAVERSAL_TIME
the node MAY try again to send another LREQ with a limit of
LREQ_RETRIES.
Liu et al. Expires June 10, 2013 [Page 22]
Internet-Draft SRP 7 December 2012
5.6. Empty Region
When a node list has just one entry, that entry represents the last
node present in the grid. When this node leaves the grid, the grid is
to be empty. The node generates broadcast message in the level-0 grid
which has the least Region Code greater than the previous grid. This
broadcast message contains the location information for all nodes
that regard the, now empty, grid as their location service grid. If
this grid is still empty, the messages will be forwarded to the next
greater one. If there is no greater one, the message will forward to
the grid with the smallest RC code. If the whole level-1 grid is
empty, the message will be forwarded to the level-0 grid with the
smallest RC located in the level-1 grid which has the least RC code
greater than the previous level-1 grid.
When a node moves into an empty grid, according to the rule above, it
collects the location information for nodes register in that region
by sending HREQ packet to the grid with the least RC greater than the
empty grid.
5.7. Dead-end operations
Using MFR Geographic Forwarding scheme, a packet may reach a node
that does not know about any nodes closer than itself to the ultimate
destination. This dead-end indicates that there is a "hole" in the
geographic distribution of nodes.
SRP uses GPSR to solve the dead-end problem. It is possible using
the same neighbour position table used in geographic forwarding. GPSR
demonstrates a loop-free method for routing packets around holes
using only information local to each node.
6. Security Considerations
This protocol considers network security as a key factor, an entity
authenticatoin scheme based on Merkle Hash Tree which was published
as a paper has been adopted.
7. Acknowledgments
I want to thank my team members Doctor Du Shuai, Doctor Wu Xiao-bo,
Master Jin Jin, Master Yang Guang and Master Wang Yao who dug into
the draft for so long time to help me get it done.
Liu et al. Expires June 10, 2013 [Page 23]
Internet-Draft SRP 7 December 2012
8. References
[1] M. Mauve, J. Widmer, H. Hartenstein: A survey on position-based
routing in mobile ad hoc networks. [J]. IEEE Network Magazine,
p30-39, November 2001.
[2] Azzedine Boukerche: Handbook of Algorithms for Wireless
Networking and Mobile Computing. [M]. London: Chapman & Hall/CRC,
2006. 328-329.
[3] Wang Li-na, Shi De-jun, Qin Bo-ping, Zhou Xian-wei:
Cluster-Based Merkle Hash Tree Entity Authentication Scheme for
Wireless SenSor Network. [C]. Chinese Journal of Sensors and
Actuators, Vol.20, No.6, June 2007.
Liu et al. Expires June 10, 2013 [Page 24]
Internet-Draft SRP 7 December 2012
Author's Addresses
Tao Liu
Communication engineering Department
University of Science and Technology Beijing(USTB)
St.Xue Yuan, No.30
100083 Beijing
P.R.CHINA
Email: ustbliutao@gmail.com
Liu et al. Expires June 10, 2013 [Page 25]
