Mobile Ad Hoc Networking Working Group Manel Guerrero Zapata INTERNET DRAFT Universitat Pompeu Fabra 11 August 2004 Secure Ad hoc On-Demand Distance Vector (SAODV) Routing draft-guerrero-manet-saodv-01.txt Status of this Memo This document is an Internet-Draft and is subject to all provisions of Section 10 of RFC2026. 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 Abstract The Secure Ad hoc On-Demand Distance Vector (SAODV) is an extension of the AODV routing protocol that can be used to protect the route discovery mechanism providing security features like integrity, authentication and non-repudiation. Guerrero Expires 11 February 2005 [Page 1] Internet DRAFT SAODV 11 August 2004 Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Preliminary notes . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1. Security Features . . . . . . . . . . . . . . . . . . . . 3 2.2. Interaction with IPSec . . . . . . . . . . . . . . . . . . 4 3. Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 5. RREQ (Single) Signature Extension . . . . . . . . . . . . . . . . 6 6. RREP (Single) Signature Extension . . . . . . . . . . . . . . . . 7 7. RREQ Double Signature Extension . . . . . . . . . . . . . . . . . 9 8. RREP Double Signature Extension . . . . . . . . . . . . . . . . . 11 9. RERR Signature Extension . . . . . . . . . . . . . . . . . . . . 13 10. RREP-ACK Signature Extension . . . . . . . . . . . . . . . . . . 14 11. Duplicated Address (DADD) Detected Message . . . . . . . . . . . 14 12. New Address (NADD) Notification Message . . . . . . . . . . . . 15 13. New Address Acknowledgment (NADD-ACK) Message . . . . . . . . . 17 14. SAODV Operation . . . . . . . . . . . . . . . . . . . . . . . . 18 14.1. SAODV Signatures . . . . . . . . . . . . . . . . . . . . 18 14.2. SAODV Hash Chains . . . . . . . . . . . . . . . . . . . . 19 14.3. SAODV Delayed Verification of Signatures . . . . . . . . 20 14.4. SAODV Key Management . . . . . . . . . . . . . . . . . . 20 14.4.1. Duplicated IP Address Detection . . . . . . . . . 21 15. Adaptations of AODV that are needed . . . . . . . . . . . . . . 22 16. Security Considerations . . . . . . . . . . . . . . . . . . . . 23 17. Modifications of the draft . . . . . . . . . . . . . . . . . . . 24 18. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . 25 Guerrero Expires 11 February 2005 [Page 2] Internet DRAFT SAODV 11 August 2004 1. Introduction Manet protocols are being designed without having security in mind. In most of their specifications it is assumed that all the nodes in the network are friendly. The security issue has been postponed and there is the common feeling that it is going to be possible to make those routing protocols secure by retrofitting pre-existing cryptosystems. Nevertheless, securing network transmissions without securing the routing protocols is not sufficient. Moreover, by retrofitting cryptosystems (like IPSec) security is not necessarily achieved. Therefore, in manet networks with security needs, there must be two security systems: one to protect the data transmission and one to make the routing protocol secure. There are already well studied peer to peer security systems that can be used for protecting network transmissions. But there is no much work about how make manet routing protocols discover routes in a secure manner [6] [7]. In this memo the reader will find a way to add security to AODV[1] via a protocol extension. It would be interesting to see if the solution proposed in this paper could be adapted to other manet protocols. 2. Preliminary notes It is important to have in mind that this paper is describing how to protect the routing messages, not the data messages. This section contains some preliminary notes about which security features SAODV provides, and IPSec interacting with SAODV. 2.1. Security Features Before designing a protocol extension that provides security to AODV it is required to think what are the security needs and what issues just cannot be solved. The main thing that cannot be avoid is that there might be malicious nodes that do not respect protocols (they will forge AODV packets, listen to the others, reply packets in their own interests, report errors where there are none, etc). It is needed to have integrity, authentication and non-repudiation. It is also desired to have a way to avoid tampering attacks, like delaying or reusing packets (in AODV this can be solved by using the sequence numbers). But what about confidentiality? Well, maybe it is needed for scenarios with a very high security needs, but it does not make sense if the scenario is a public ad hoc network that everybody can joint at any moment. Therefore, it is not taken into account in Guerrero Expires 11 February 2005 [Page 3] Internet DRAFT SAODV 11 August 2004 the proposed protocol extension. Concerning availability, of course it is desired, but prevent denial- of-service attacks in a network that uses wireless technology is quite impossible when an attacker can just focus in the physical layer instead of attacking the routing protocol. Of course military scenarios are the most likely to suffer such kind of attacks. Anyway, being in a less security demanding scenario, and although denial-of- service attacks in general are not easy to stop, it is desirable to have some measures that make availability more difficult to broke. 2.2. Interaction with IPSec When trying to use IPSec to secure network transmissions in a manet network, it is needed that the IPSec implementation can use as a selector the TCP or UDP port number. Sadly, there are quite many implementations that cannot do that. The importance of that is because it is needed that the IPSec policy will be able to apply certain security mechanisms to the data packets and just bypass the routing packets. 3. Overview The solution presented in this paper is an extension of the AODV protocol mainly by using new extension messages. In these extension messages there is a signature created by digesting the AODV packet using the private key of the original sender of the Routing message (not of the intermediate nodes that just forward it). Concerning to RREQ and RREP messages there are two alternatives: The first one in which only final destinations are allowed to reply a RREQ, and the second in which there is no such limitation. In the first one, when a RREQ is sent, the sender signs the message. Intermediate nodes verify the signature before creating or updating a reverse route to that host. And only if the signature is fine they store the reverse route. The final destination node signs the RREP with its private key. Intermediate and final nodes, again verify the signature before creating or updating a route to that host, also storing the signature with the route entry. In the second one, when a RREQ is sent, the sender signs the message. Intermediate nodes verify the signature before creating or updating a reverse route to that host. And, again, only if the signature is fine they store the reverse route. But the difference is that the RREQ message has also a second signature that is always stored with the reverse route. This second signature is needed to be added in the gratuitous RREPs of that RREQ and in regular RREPs to future RREQs Guerrero Expires 11 February 2005 [Page 4] Internet DRAFT SAODV 11 August 2004 that the node might reply as an intermediate nodes. An intermediate node that wants to reply a RREQ needs not only the correct route, but also the signature corresponding to that route to add it in the RREP and the lifetime that came in the same message tha the signature. When this happens, it generates the RREP, (adding the stored signature and lifetime) signs the actual lifetime and sends it. All the nodes that receive the RREP and that update the route store the signature and lifetime with that route. Hello messages are RREP messages, so they are signed in the same way. Extension messages that include a second signature also include the RREP fields (flags and prefix size) that are not derivable from the RREQ but not zeroed when computing the signature. RREP-ACK messages may be authentified by using a digital signature, that might be verified by any one that receives them. Every node, generating or forwarding a RERR message, uses digital signatures to sign the whole message and any neigbour that receives verifies the signature. The hop count of all these messages is authentified by using a hash chain. 4. Terminology This memo uses the conventional meanings [2] for the capitalized words MUST, SHOULD and MAY. It also uses terminology taken from the specifications of AODV [1] and IPSec [3]. Guerrero Expires 11 February 2005 [Page 5] Internet DRAFT SAODV 11 August 2004 5. RREQ (Single) Signature Extension 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 | Length | Hash Function | Max Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Top Hash | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sign Method |H| Reserved | Padd Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Padding (optional) | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hash | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 64 Length The length of the type-specific data, not including the Type and Length fields of the extension. Hash Function The hash function used to compute the Hash and Top Hash fields. Max Hop Count The Maximum Hop Count supported by the hop count authentication. Top Hash The top hash for the hop count authentication. This field has variable length, but it must be 32-bits aligned. Signature Method The signature method used to compute the signatures. H Half Identifier flag. If it is set to '1' indicates the use of HID and if it is set to '0' the use of FID. Reserved Sent as 0; ignored on reception. Guerrero Expires 11 February 2005 [Page 6] Internet DRAFT SAODV 11 August 2004 Padding Length Specifies the length of the padding field in 32-bit units. If the padding length field is set to zero, there will be no padding. Public Key The public key of the originator of the message. This field has variable length, but it must be 32-bits aligned. Padding Random padding. The size of this field is set in the Padding Length field. Signature The signature of the all the fields in the AODV packet that are before this field but the Hop Count field. This field has variable length, but it must be 32-bits aligned. Hash The hash corresponding to the actual hop count. This field has variable length, but it must be 32-bits aligned. 6. RREP (Single) Signature Extension 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 | Length | Hash Function | Max Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Top Hash | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sign Method |H| Reserved | Padd Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Padding (optional) | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hash | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 65 Guerrero Expires 11 February 2005 [Page 7] Internet DRAFT SAODV 11 August 2004 Length The length of the type-specific data, not including the Type and Length fields of the extension. Hash Function The hash function used to compute the Hash and Top Hash fields. Max Hop Count The Maximum Hop Count supported by the hop count authentication. Top Hash The top hash for the hop count authentication. This field has variable length, but it must be 32-bits aligned. Signature Method ... Padding The same than in RREQ (Single) Signature Extension. Signature The signature of the all the fields in the AODV packet that are before this field but the Hop Count field. This field has variable length, but it must be 32-bits aligned. Hash The hash corresponding to the actual hop count. This field has variable length, but it must be 32-bits aligned. Guerrero Expires 11 February 2005 [Page 8] Internet DRAFT SAODV 11 August 2004 7. RREQ Double Signature Extension 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 | Length | Hash Function | Max Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |R|A| Reserved |Prefix Sz| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Top Hash | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sign Method |H| Reserved | Padd Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Padding (optional) | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature for RREP | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hash | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 66 Length The length of the type-specific data, not including the Type and Length fields of the extension. Hash Function The hash function used to compute the Hash and Top Hash fields. Max Hop Count The Maximum Hop Count supported by the hop count authentication. R Repair flag for the RREP. A Acknowledgment required flag for the RREP. Reserved Sent as 0; ignored on reception. Guerrero Expires 11 February 2005 [Page 9] Internet DRAFT SAODV 11 August 2004 Prefix Size The prefix size field for the RREP. Top Hash The top hash for the hop count authentication. This field has variable length, but it must be 32-bits aligned. Signature Method ... Padding The same than in RREQ (Single) Signature Extension. Signature The signature of the all the fields in the AODV packet that are before this field but the Hop Count field. This field has variable length, but it must be 32-bits aligned. Signature for RREP The signature that should be put into the Signature field of the RREP Double Signature Extension when an intermediate node (that has previously received this RREQ and created a reverse route) wants to generate a RREP for a route to the source of this RREQ. This field has variable length, but it must be 32-bits aligned. Both signatures are generated by the requesting node. Hash The hash corresponding to the actual hop count. This field has variable length, but it must be 32-bits aligned. Guerrero Expires 11 February 2005 [Page 10] Internet DRAFT SAODV 11 August 2004 8. RREP Double Signature Extension 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 | Length | Hash Function | Max Hop Count | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Top Hash | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sign Method |H| Reserved | Padd Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Padding (optional) | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Old Lifetime | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sign Method 2 |H| Reserved | Padd Length 2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key 2 | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Padding 2 (optional) | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature of the new Lifetime | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hash | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 67 Length The length of the type-specific data, not including the Type and Length fields of the extension. Hash Function The hash function used to compute the Hash and Top Hash fields. Max Hop Count Guerrero Expires 11 February 2005 [Page 11] Internet DRAFT SAODV 11 August 2004 The Maximum Hop Count supported by the hop count authentication. Top Hash The top hash for the hop count authentication. This field has variable length, but it must be 32-bits aligned. Signature Method ... Padding The same than in RREQ (Single) Signature Extension. Signature The signature of all the fields of the AODV packet that are before this field but the Hop Count field, and with the Old Lifetime value instead of the Lifetime. This signature is the one that was generated by the final destination. This field has variable length, but it must be 32-bits aligned. Old Lifetime The lifetime that was in the RREP generated by the final destination. Signature Method 2 ... Padding 2 The whole block of fields is repeated. This time for the 'Signature of the New Lifetime' signature. Signature of the new Lifetime The signature of the RREP with the actual lifetime (the lifetime of the route in the intermediate node). This signature is generated by the intermediate node. This field has variable length, but it must be 32-bits aligned. Hash The hash corresponding to the actual hop count. This field has variable length, but it must be 32-bits aligned. Guerrero Expires 11 February 2005 [Page 12] Internet DRAFT SAODV 11 August 2004 9. RERR Signature Extension 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 | Length | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sign Method |H| Reserved | Padd Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Padding (optional) | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 68 Length The length of the type-specific data, not including the Type and Length fields of the extension. Reserved Sent as 0; ignored on reception. Signature Method ... Padding The same than in RREQ (Single) Signature Extension. Signature The signature of the all the fields in the AODV packet that are before this field. This field has variable length, but it must be 32-bits aligned. Guerrero Expires 11 February 2005 [Page 13] Internet DRAFT SAODV 11 August 2004 10. RREP-ACK Signature Extension 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 | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sign Method |H| Reserved | Padd Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Padding (optional) | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 69 Length The length of the type-specific data, not including the Type and Length fields of the extension. Signature Method ... Padding The same than in RREQ (Single) Signature Extension. Signature The signature of the all the fields in the AODV packet that are before this field. This field has variable length, but it must be 32-bits aligned. 11. Duplicated Address (DADD) Detected 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 | Length |H| Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Duplicated Node's IP Address | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Duplicated Node's Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 64 Length The length of the type-specific data, not including the Guerrero Expires 11 February 2005 [Page 14] Internet DRAFT SAODV 11 August 2004 Type and Length fields of the message. H Half Identifier flag. If it is set to '1' indicates the use of HID and if it is set to '0' the use of FID. Reserved Sent as 0; ignored on reception. Duplicated Node's IP Address The IP Address of the node that uses a Duplicated IP Address. Duplicated Node's Public Key The Public Key of the node that uses a Duplicated IP Address. 12. New Address (NADD) Notification 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 | Length | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sign Method |H| Reserved | Padd Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Old Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Padding (optional) | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sign Method 2 |H| Reserved | Padd Length 2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | New Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Padding 2 (optional) | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature with Old Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature with New Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 65 Length The length of the type-specific data, not including the Guerrero Expires 11 February 2005 [Page 15] Internet DRAFT SAODV 11 August 2004 Type and Length fields of the message. Reserved Sent as 0; ignored on reception. Signature Method ... Padding The same than in RREQ (Single) Signature Extension. Corresponds to the 'Signature with Old Public Key' signature. Signature Method 2 ... Padding 2 The whole block of fields is repeated. Corresponds to the 'Signature of the New Public Key' signature. Signature with Old Key The signature (with the old key) of the all the fields in the AODV packet that are before this field. This field has variable length, but it must be 32-bits aligned. Signature with New Key The signature (with the new key) of the all the fields in the AODV packet that are before this field. This field has variable length, but it must be 32-bits aligned. Guerrero Expires 11 February 2005 [Page 16] Internet DRAFT SAODV 11 August 2004 13. New Address Acknowledgment (NADD-ACK) 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 | Length | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Old IP Address | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | New IP Address | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sign Method |H| Reserved | Padd Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Padding (optional) | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 66 Length The length of the type-specific data, not including the Type and Length fields of the message. Reserved Sent as 0; ignored on reception. Old IP Address The old IP address. New IP Address The new IP address. Signature Method ... Padding The same than in RREQ (Single) Signature Extension. Signature The signature of the all the fields in the AODV packet that are before this field. This field has variable length, but it must be 32-bits aligned. Guerrero Expires 11 February 2005 [Page 17] Internet DRAFT SAODV 11 August 2004 14. SAODV Operation This section describes how SAODV allows to authenticate the AODV routing data. Two mechanisms are used to achieve this: hash chains and signatures. 14.1. SAODV Signatures When calculating signatures, Hop Count field is always zeroed, because it is a mutable field. In the case of the Signature for RREP field of the RREQ Double Signature Extension, what is signed is the future RREP message that nodes might send back in response to the RREQ. To construct this message it uses the values of the RREQ and its Prefix Size. It also decides which are going to be the values of the R and A flags. Every time a node generates a RREQ it decides if it should be signed with a Single Signature Extension or with a Double Signature Extension. All implementations MUST support RREQ Single Signature Extension, and SHOULD support RREQ Double Signature Extension. A node that generates a RREQ with the gratuitous RREP flag set SHOULD sign the RREQ with a Double Signature Extension. A node SHOULD never generate a RREQ without adding a Signature Extension. When a node receives a RREQ, first verify the signature before creating or updating a reverse route to that host. Only if the signature is verified, it will store the route. If the RREQ was received with a Double Signature Extension, then the node will also store the signature and the lifetime (that is REV_ROUTE_LIFE) for the RREP in the route entry. If a node receives a RREQ without a Signature Extension it SHOULD drop it. An intermediate node will reply a RREQ with a RREP only if fulfills the AODV requirements to do so, and the node has the corresponding signature and old lifetime to put into the Signature and Old Lifetime fields of the RREP Double Signature Extension. Otherwise, it will rebroadcast the RREQ. When a RREQ is received by the destination itself, it will reply with a RREP only if fulfills the AODV requirements to do so. This RREP will be sent with a RREP Single Signature Extension. All implementations MUST support RREP Single Signature Extension, and SHOULD support RREP Double Signature Extension. A node SHOULD never generate a RREP without adding a Signature Extension. This also applies to gratuitous RREPs. Guerrero Expires 11 February 2005 [Page 18] Internet DRAFT SAODV 11 August 2004 When a node receives a RREP, first verifies the signature before creating or updating a route to that host. Only if the signature is verified, it will store the route with the signature and the lifetime of the RREP. If a node receives a RREP without a Signature Extension it SHOULD drop it. Every node, generating or forwarding a RERR message, uses digital signatures to sign the whole message and any neigbour that receives verifies the signature. In this way it can verify that the sender of the RERR message is really the one that claims to be. And, since destination sequence numbers are not singed by the corresponding node, a node SHOULD never update any destination sequence number of its routing table based on a RRER message. Although nodes will not trust destination sequence numbers in a RERR message, they will use them to decide whether they should invalidate a route or not. RREP-ACK messages MAY be authentified by using the RREP-ACK Signature Extension. The block 'Signature Method ... Padding' is included before the 'Signature' field in all the extension messages, and before the 'Signature of the new Lifetime' field in the RREQ-DSE message. This is the list of possible values of the Signature Method field: RESERVED 0 RSA 1 Elliptic Curve 2 Reserved 3-127 Implementation dependent 128-255 All the implementations MUST support the RSA option. 14.2. SAODV Hash Chains Hash chains are used in SAODV to authenticate the hop count of the AODV routing messages (not only by the end points, but by any node that receives one of those messages. Every time a node wants to send a RREQ or a RREP it generates a random number (seed). Selects a Maximum Hop Count. Maximum Hop Count SHOULD be set to the TTL value in the IP header, and it SHOULD never exceed its configuration parameter NET_DIAMETER. The Hash field in the Signature Extension is set to the seed. The Top Hash field is set to the seed hashed Max Hop Count times. Guerrero Expires 11 February 2005 [Page 19] Internet DRAFT SAODV 11 August 2004 Every time a node receives a RREQ or a RREP it verifies the hop count by hashing Max Hop Count - Hop Count times the Hash field, and checking that the resultant value is the same than the Top Hash. If the check fails, the node SHOULD drop the packet. Before rebroadcasting a RREQ or forwarding a RREP, a node hashes one time the Hash field in the Signature Extension. The function used to compute the hash is set in the Hash Function field. Since this field is signed, a forwarding node will only be able to use the same hash function that the originator of the routing message has selected. If an node cannot verify or forward a routing message because it does not support the hash function that has been used, then it drops the packet. This is the list of possible values of the Hash Function field: RESERVED 0 MD5HMAC96 1 SHA1HMAC96 2 Reserved 3-127 Implementation dependent 128-255 All the implementations MUST support the HMAC-SHA-1-96 option. 14.3. SAODV Delayed Verification of Signatures The signatures in route requests and route replies will be verified after the node has forwarded the route reply. In this way transmissions of the route requests and replies occur without any kind of delay due to the verification of the signatures. Following the same idea, the signature of route error messages will also be verified after forwarding them. Routes pending of verification will not be used to forward any packet. If a packet arrives for a node for which there is a route pending of verification. The node will have to verify it before using that route. If the verification fails, it will delete the route and request a new one. 14.4. SAODV Key Management This section describes a key management scheme that MAY be used with SAODV and AODVv6. SAODV can generate the IP addresses is very similar to the generation Guerrero Expires 11 February 2005 [Page 20] Internet DRAFT SAODV 11 August 2004 of SUCV (Statistically Unique and Cryptographically Verifiable) addresses [8]. SUCV addresses where designed to protect Binding Updates in Mobile IPv6. The main difference between SUCV and the method proposed in here is that SUCV addresses are generated by hashing an "imprint" in addition to the public key. That imprint (that can be a random value) is used to limit certain attacks related to Mobile IP. In SAODV, the address can be a network prefix of 64 bits with a 64 bit SAODV_HID (Half IDentifier) or a 128 bit SAODV_FID (Identifier). These two identifiers are generated almost in the same way than the sucvHID and the sucvID in SUCV (with the difference that they do not include an imprint): SAODV_HID = SHA1HMAC_64(PublicKey) SAODV_FID = SHA1HMAC_128(PublicKey) There will be a flag in the SAODV routing message extensions (the 'H' flag) that will be set to '1' if the IP address is a HID and to '0' if it is a FID. Finally, if it has to be a real IPv6 address, there is a couple of things that should be done [9]. If HID is used, then the HID behaves as an interface identifier and, therefore, its sixth bit (the universal/local bit) should be set to zero (0) to indicate local scope (because the IP address is not guaranteed to be globally unique). And, if FID is used, then a format prefix corresponding to the manet network should be overwritten to the FID. Format prefixes '010' through '110' are unassigned and would take only three bits of the FID. Format prefixes '1110' through '1111 1110 0' are also unassigned and they would take between 4 and 9 bits of the FID. All of these format prefixes required to have to have 64-bit interface identifiers in EUI-64 format, so universal/local bit should be set to zero (0). This section does not propose a scheme for IPv4 since the length of an IPv4 address would be too short to provide the statistical uniqueness that this scheme requires. 14.4.1. Duplicated IP Address Detection If a node 'A' receives a routing message that is signed by a node 'B' that has the same IP address than one of the nodes for which 'A' has a route entry (node 'C'), it will not process normally that routing message. Instead, it will inform 'B' (sending to it a Duplicated Guerrero Expires 11 February 2005 [Page 21] Internet DRAFT SAODV 11 August 2004 Address (DADD) Detected message) that it is using a duplicated IP and it will prove it by adding the public key of 'C' (so 'B' can verify the truthfulness of the claim). When the node 'B' receives a DADD message that indicates that somebody else has the same IP address than itself (or it realizes about it by itself), it will have to generate a new pair of public/private keys. After that, it will derive its IP address from its public key and it MIGHT inform to all the nodes it finds relevant (through a broadcast) of which is its new IP address with an special message (New Address (NADD) Notification message) that contains: the two IP addresses (the old and the new ones) and the two public signatures (old and new) signed with the old private key and, all this, signed with the new private key. This unicast MIGHT be answered with the New Address Acknowledgment (NADD-ACK) Message by the receiver if it verifies that everything is in order. After this, the node will generate a route error message for his old IP address. Its propagation will delete the route entries for the old IP address and, therefore, eliminate the duplicated addresses. This route error message may have a message extension that tells which is the new address. In this way, the nodes that receive the routing message can already create the route to the new IP address. 15. Adaptations of AODV that are needed According to the AODV RFC [1], the originator of a RREQ can put (on purpose) a much more bigger destination sequence number than the real one. This allows a very easy attack that consists in setting the destination sequence number to 0xFFFFFFFF (the maximum value that fits in the 32-bits field). Then, the originator of the RREP and all the intermediate nodes will have that as sequence number for the route. The next time the node increments the sequence number, its sequence number counter will overflow. This might cause completely unexpected results, none of them good. The fact that the originator of the RREQ can set the sequence number of the destination is because it is going to be needed if the destination node has rebooted (see section 6.13. 'Actions After Reboot' in the AODV RFC [1]). After rebooting, a node does not remember its sequence number anymore and trusts anybody that sends to it a RREQ with the number. But this just cannot be allowed. Therefore, all the AODV-enabled nodes SHOULD have a way to keep their destination sequence number even after rebooting. In addition, in the case that the destination sequence number in the RREQ is bigger than the destination sequence number of the destination node, the destination node SHOULD NOT take into account the value in the RREQ. Guerrero Expires 11 February 2005 [Page 22] Internet DRAFT SAODV 11 August 2004 Instead, it will realize that the originator of the RREQ is misbehaving and will send the RREP with the right sequence number. Finally, and concerning to the AODV port (the UDP port used to send AODV messages), AODV nodes SHOULD never accept AODV messages sent from a different port than the standard one. 16. Security Considerations The goal of the protocol extension described here, is to achieve that a node that plans to build an attack by not behaving according to the AODV routing protocol, will be only able to selectively don't reply to certain routing messages and to lie about information about itself. Nevertheless, It does not much to avoid denial-of-service attacks. If a malicious node receives a packet and resends it after a while, it will not alter the network topology because of the sequence number system. It might seem that lifetime is not very strongly authentificated in the case that intermediate nodes are allowed to reply RREQs, because they could lie about the lifetime. Anyway, the goal of the protocol extension is achieved, because the node would be only lying about itself. Using hash chains for authentifying hop counter has a problem: A malicious node forwarding a route might not increment the hop counter by using the same hash value. If it does so, the subsequent nodes will think that this route is one hop shorter (having more chances to be chosen as the route to use). This is not really a big threat, because to launch an attack, a group of malicious nodes should be close to the shortest path (each of the malicious nodes forwarding the routing messages would not increment the hop counter), and the less malicious nodes are, the more close they have to be to the shortest path. A path that is changing with the time. There are still the following open issues: 1. Is it correct that the RREQ Double Signature Extension fixes the values for the R and A flags in the RREP issued by an intermediate node? Is there any attacks that could be performed if those flags are considered as 'not predictable' ones and, therefore, zeroed for the signature computation? 2. It is not clear yet if a mixture between nodes using SAODV and nodes using plain AODV in the same network is possible or desirable. Guerrero Expires 11 February 2005 [Page 23] Internet DRAFT SAODV 11 August 2004 17. Modifications of the draft Version 1 - Adds this section. ;) - Adds the following fields just before the 'Signature' field in all the extension messages: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sign Method |H| Reserved | Padd Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Padding (optional) | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - And adds these other fields just before the 'Signature of the new Lifetime' field in the RREQ-DSE extension message: +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sign Method 2 |H| Reserved | Padd Length 2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key 2 | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Padding 2 (optional) | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ - Adds the section "11. Duplicated Address (DADD) Detected Message". - Adds the section "12. New Address (NADD) Notification Message". - Adds the section "13. New Address Acknowledgment (NADD-ACK) Message". - Adds some text at the end of the section "14.1. SAODV Signatures" to explain the new fields of the extension messages. - Adds the section "14.3. SAODV Delayed Verification of Signatures". - Adds the section "14.4. SAODV Key Management". - Removes the section "2.3. Key distribution". Guerrero Expires 11 February 2005 [Page 24] Internet DRAFT SAODV 11 August 2004 - Other stuff I might be forgetting. 18. Acknowledgments N. Asokan (from Nokia Research Center) has contributed to this draft with several improvements and corrections. He suggested the use of hash chains for authenticate the hop count and, that intermediate nodes should sign the lifetime of the RREPs. Sampo Sovio (also from Nokia Research Center) discussed with me several ways of how to use hashing techniques for SAODV. Toni Barrera Arboix gave very valuable orientations about certificates. References [1] Charles E. Perkins, Elizabeth M. Belding Royer, Samir R. Das: Ad hoc On-Demand Distance Vector (AODV) Routing. RFC 3561, November 2003. [2] S. Bradner: Key words for use in RFCs to Indicate Requirement Levels. RFC 2119, March 1997. [3] S. Kent, R. Atkinson: Security Architecture for the Internet Protocol. RFC 2402, November 1998. [4] NIST: "Secure Hash Standard", FIPS 180-1, National Institute of Standards and Technology, U.S. Department of Commerce, May 1994 [5] R. Rivest, A. Shamir, and L. Adleman: "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM, v. 21, n. 2, February 1978. [6] S. Jacobs, M. S. Corson: "MANET Authentication Architecture", Internet Draft (draft-jacobs-imep-auth-arch-01.txt), February 1999. [7] L. Zhou, Z. J. Haas: "Securing Ad Hoc Networks", IEEE Network Magazine, vol. 13, no.6, November/December 1999. [8] Gabriel Montenegro, Claude Castelluccia: Statistically Unique and Cryptographically Verifiable (SUCV) Identifiers and Addresses. Network and Distributed System Security Symposium (NDSS '02). February 2002, [9] R. Hinden and S. Deering: IP Version 6 Addressing Architecture. RFC 2373, July 1998. Guerrero Expires 11 February 2005 [Page 25] Internet DRAFT SAODV 11 August 2004 Author's Address: Questions about this memo can be directed to the author: Manel Guerrero Zapata Technology Department Universitat Pompeu Fabra Passeig de Circumval.lacio 8, 08003 Barcelona (Spain) +34 935421498 manel.guerrero@upf.edu Guerrero Expires 11 February 2005 [Page 26]