Mobile Ad Hoc Networking Working Group Manel Guerrero Zapata INTERNET DRAFT Technical University 15 September 2005 of Catalonia (UPC) Secure Ad hoc On-Demand Distance Vector (SAODV) Routing draft-guerrero-manet-saodv-04.txt Intellectual Property Rights Statement By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Status of this Memo 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 Copyright Copyright (C) The Internet Society 2005. All Rights Reserved. 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 15 March 2005 [Page 1] Internet DRAFT SAODV 15 September 2005 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.1.1. Encoding of Public Key and Signature . . . . . . . 20 14.1.2. Signature Method #1 (RSA) . . . . . . . . . . . . 21 14.1.3. Signature Method #2 (DSA) . . . . . . . . . . . . 22 14.1.4. Signature Method #3 (ElGamal) . . . . . . . . . . 23 14.2. SAODV Hash Chains . . . . . . . . . . . . . . . . . . . . 23 14.3. SAODV Delayed Verification of Signatures . . . . . . . . 24 14.4. SAODV Key Management . . . . . . . . . . . . . . . . . . 25 14.4.1. Duplicated IP Address Detection . . . . . . . . . 26 15. Adaptations of AODV that are needed . . . . . . . . . . . . . . 27 16. Security Considerations . . . . . . . . . . . . . . . . . . . . 27 17. Modifications of the draft . . . . . . . . . . . . . . . . . . . 28 18. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . 31 Guerrero Expires 15 March 2005 [Page 2] Internet DRAFT SAODV 15 September 2005 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 15 March 2005 [Page 3] Internet DRAFT SAODV 15 September 2005 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 break. 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 15 March 2005 [Page 4] Internet DRAFT SAODV 15 September 2005 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' and the 'Originator IP address' fields that work with that signature. If it has them, it generates the RREP, (adding the stored signature, lifetime and the originator IP address) signs the actual lifetime and the actual originator IP address and sends it. All the nodes that receive the RREP and that update the route store the signature the lifetime and the originator IP address with that route. If a node wants to be able to reply as an intermediate node for a route to a node that has been added due to a RREQ or to a RREP, it has to store the 'RREQ Destination' or 'RREP Originator' IP address, the lifetime and the signature. And use them as the 'Signature', 'Old Lifetime', and 'Old Originator IP address' fields in the RREP-DSE message. Hello messages are RREP messages, so they are signed in the same way. Hello Interval extensions are not signed. There is no attack from changing hello interval extension. Actually, if the hello interval extension would be added in the signature, the nodes that received a hello message from a node 'D' would not be able to reply as intermediate node when a node 'S' would issue a RREQ for 'D', because they wouldn't have a valid signature for the RREP without the hello interval extension. Extension messages that include a second signature also include the RREP fields (right now only the 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 15 March 2005 [Page 5] Internet DRAFT SAODV 15 September 2005 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 in bytes. 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 15 March 2005 [Page 6] Internet DRAFT SAODV 15 September 2005 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 15 March 2005 [Page 7] Internet DRAFT SAODV 15 September 2005 Length The length of the type-specific data, not including the Type and Length fields of the extension in bytes. 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 15 March 2005 [Page 8] Internet DRAFT SAODV 15 September 2005 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | Prefix Size | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Top Hash | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sign Method |H| Reserved | Padd Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Padding (optional) | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature for RREP | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hash | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 66 Length The length of the type-specific data, not including the Type and Length fields of the extension in bytes. 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. Reserved Sent as 0; ignored on reception. Prefix Size The prefix size field for the RREP (it is 7 bit long to allow IPv6 prefixes). Guerrero Expires 15 March 2005 [Page 9] Internet DRAFT SAODV 15 September 2005 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 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. 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. 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 15 March 2005 [Page 10] Internet DRAFT SAODV 15 September 2005 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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Old Originator IP address | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Sign Method 2 |H| Reserved | Padd Length 2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Public Key 2 | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Padding 2 (optional) | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Signature of the new Lifetime and Originator IP address | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hash | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Type 67 Length The length of the type-specific data, not including the Type and Length fields of the extension in bytes. Hash Function The hash function used to compute the Hash and Top Hash fields. Guerrero Expires 15 March 2005 [Page 11] Internet DRAFT SAODV 15 September 2005 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 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 originator of the RREQ-DSE). This field has variable length, but it must be 32-bits aligned. Old Lifetime The lifetime that was in the RREP generated by the originator of the RREQ-DSE). Old Originator IP address The Originator IP address that was in the RREP generated by the originator of the RREQ-DSE). Signature Method 2 ... Padding 2 The whole block of fields is repeated. This time for the 'Signature of the New Lifetime and Originator IP address' signature. Signature of the new Lifetime and Originator IP address The signature of the RREP with the actual lifetime (the lifetime of the route in the intermediate node) and with the actual Originator IP address. 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 15 March 2005 [Page 12] Internet DRAFT SAODV 15 September 2005 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 in bytes. 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 15 March 2005 [Page 13] Internet DRAFT SAODV 15 September 2005 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 in bytes. 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 15 March 2005 [Page 14] Internet DRAFT SAODV 15 September 2005 Type and Length fields of the message in bytes. 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 15 March 2005 [Page 15] Internet DRAFT SAODV 15 September 2005 Type and Length fields of the message in bytes. 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 15 March 2005 [Page 16] Internet DRAFT SAODV 15 September 2005 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 in bytes. 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 15 March 2005 [Page 17] Internet DRAFT SAODV 15 September 2005 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 the Prefix Size (the RREP field that is not derivable from the RREQ but not zeroed when computing the signature. In the case of RREPs, R and A flags are also zeroed. SAODV is not designed taking into account AODV multicast ('R' flag is used in multicast) and 'A' flag is mutable and, if an attacker alters it, it can only lead to some sort of denial of service. 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, the lifetime and the Destination IP address 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 the old lifetime and old originator IP address to put into the 'Signature', 'Old Lifetime' and 'Old Originator IP address' 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 Guerrero Expires 15 March 2005 [Page 18] Internet DRAFT SAODV 15 September 2005 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. 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 and the originator IP address 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 and Originator IP address' field in the RREQ-DSE message. This is the list of possible values of the Signature Method field: RESERVED 0 RSA 1 DSA 2 ElGamal 3 Reserved 4-127 Implementation dependent 128-255 All the implementations MUST support the RSA option. Guerrero Expires 15 March 2005 [Page 19] Internet DRAFT SAODV 15 September 2005 14.1.1. Encoding of Public Key and Signature Encoding of each of the components of Public Key will be done in the following manner unless stated otherwise: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Value | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Reserved Sent as 0; ignored on reception. Length The length of the Value field, (not including the Length and Reserved fields) in 32-bit units. Encoding of the Signature will be done in the following manner unless stated otherwise: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Hash F Sign | Reserved | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Value | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Hash F Sign The hash function used to compute the hash that will be signed. Because, typically you don't want to sign the whole message, you sign a hash of the message. The other fields work just like the ones of the encoding of the components of Public Key. Guerrero Expires 15 March 2005 [Page 20] Internet DRAFT SAODV 15 September 2005 This is the list of possible values of the 'Hash F Sign' field: Hash F Sign Hash length Value =========== =========== ===== RESERVED - 0 MD2 (128 bit) 1 MD5 (128 bit) 2 SHA1 (160 bit) 3 SHA256 (256 bit) 4 SHA384 (384 bit) 5 SHA512 (512 bit) 6 Reserved - 7-127 Implementation dependent - 128-255 All the implementations MUST support the SHA1 option. MD2 is a relatively slow hash function, but I decided to include it anyway. About SHA512 and SHA384, somebody might argue that nowadays they generate a much longer hash that what it is needed. But I believe they will be needed in the future. 14.1.2. Signature Method #1 (RSA) Public Key is composed of: - Modulus (n) - Exponent (e) Signature is composed of: - Signature Where all these components may be encoded in the standard way or in the following way: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |Exp| Reserved | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Modulus | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Reserved Sent as 0; ignored on reception. Length The length of the Modulus field, (not including the Length and Reserved fields) in 32-bit units. Guerrero Expires 15 March 2005 [Page 21] Internet DRAFT SAODV 15 September 2005 Exp The Exponent (e): 00 The components are encoded in the standard way. The Exponent (e) will be specified after the Modulus (n). 01 Specifies that Exponent (e) is 65537 (2^16+1). 10 Specifies that Exponent (e) is 17 (2^4+1). 11 Specifies that Exponent (e) is 3. A message that uses any of these 'smartly chosen' exponents MUST include random padding (in the Padding field). There is no security problem with everybody using the same exponent. 14.1.3. Signature Method #2 (DSA) Public Key is composed of: - Pub_key_y (y = g^x mod p) - Prime (p) - Group_order (q) - Group_generator (g) Signature is composed of: - Signature Where all these components may be encoded in the standard way or in the following way: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|Q|G| Reserved | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Pub_key_y | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Reserved Sent as 0; ignored on reception. Length The length of the Modulus field, (not including the Length and Reserved fields) in 32-bit units. P Shared Prime (p) flag. If it is set to '1' indicates that Prime (p) is shared among the nodes of the network. Q Shared Group_order (q) flag. G Shared Group_generator (g) flag. Guerrero Expires 15 March 2005 [Page 22] Internet DRAFT SAODV 15 September 2005 After this block, the non shared values will be included in the usual order. 14.1.4. Signature Method #3 (ElGamal) Public Key is composed of: - Pub_key_y (y = g^x mod p) - Prime (p) - Group_generator (g) Signature is composed of: - Signature Where all these components may be encoded in the standard way or in the following way: 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |P|G| Reserved | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Pub_key_y | ... ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Reserved Sent as 0; ignored on reception. Length The length of the Modulus field, (not including the Length and Reserved fields) in 32-bit units. P Shared Prime (p) flag. If it is set to '1' indicates that Prime (p) is shared among the nodes of the network. G Shared Group_generator (g) flag. After this block, the non shared values will be included in the usual order. 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 Guerrero Expires 15 March 2005 [Page 23] Internet DRAFT SAODV 15 September 2005 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. 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: Hash Funct. Hash length Value =========== =========== ===== RESERVED - 0 MD2 (128 bit) 1 MD5 (128 bit) 2 SHA1 (160 bit) 3 SHA256 (256 bit) 4 SHA384 (384 bit) 5 SHA512 (512 bit) 6 Reserved - 7-127 Implementation dependent - 128-255 All the implementations MUST support the SHA1 option. This table is, right now, exactly the same as the one for the hash functions used for the signature ('Hash F Sign'). But that could change in the future. 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. Guerrero Expires 15 March 2005 [Page 24] Internet DRAFT SAODV 15 September 2005 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 The first part of 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 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 hash the public key instead of an imprint): SAODV_HID = SHA1HMAC_64(PublicKey, PublicKey) SAODV_FID = SHA1HMAC_128(PublicKey, PublicKey) This is the list of what is used as PublicKey depending on which Signature Method is used: Signature Method PublicKey ================ ========= 1 (RSA) Modulus (n) 2 (DSA) Pub_key_y (y = g^x mod p) 3 (ElGamal) Pub_key_y (y = g^x mod p) 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 Guerrero Expires 15 March 2005 [Page 25] Internet DRAFT SAODV 15 September 2005 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). The length of an IPv4 address is probably too short to provide the statistically uniqueness that this scheme requires when the number of nodes is very big. Nevertheless, if the number of nodes is assumed to be low, (let's say, under 100 nodes) it is not very unrealistic to expect that the statistically uniqueness property will hold. The SAODV IPv4 address will have a network preffix of 8 bits and a SAODV_4ID (IPv4 Identifier). The network preffix can be any number between 1 and 126 (both included) with the exception of 14, 24 and 39 (see RFC3330). The network preffix 10 can only be used if it is granted that it will not be connected to any other network (RFC1918). The SAODV_4ID will be the first bits of the SAODV_HID and the 'H' flag will be set. 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 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 Guerrero Expires 15 March 2005 [Page 26] Internet DRAFT SAODV 15 September 2005 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. 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. Guerrero Expires 15 March 2005 [Page 27] Internet DRAFT SAODV 15 September 2005 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. What about the originator IP address (also in the case that intermediate nodes are allowed to reply RREQs)? If an intermediate node lies about it, the RREP will travel to the fake originator IP address but the routes that will be generated by the nodes that will propagate the routing message will be correct. So the attack is practically equivalent to the one in which the intermediate node ignores the RREQ. 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. 17. Modifications of the draft Version 4 - 'A' flag is not signed (as proposed by Francesco Dolcini). Neither is 'R' flag. - Section 14.4. SAODV Key Management: IPv4 addresses can now be generated in a similar fashion than IPv6 ones. - Section 7. RREQ Double Signature Extension: Prefix Size is now 7 bit long to be able to hold IPv6 Prefix Sizes. Version 3 - Clarification: Now, in section '3. Overview', it explicitly says that Hello Interval extension is not signed. - Adds sections: '14.1.1. Encoding of Public Key and Signature', Guerrero Expires 15 March 2005 [Page 28] Internet DRAFT SAODV 15 September 2005 '14.1.2. Signature Method #1 (RSA)', '14.1.3. Signature Method #2 (DSA)' and '14.1.4. Signature Method #3 (ElGamal)'. - Clarification: Now all lengths specify if we are talking about bytes or 32-bit words. - In section '14.4. SAODV Key Management', adds the list of what is used as PublicKey depending on which Signature Method is use. - In section '14.2. SAODV Hash Chains', the list of hash functions has changed, and now includes more hash functions. Note that the hash functions that already existed in the previous version now have a different value. Version 2 - Correction: In section '14.1. SAODV Signatures' instead of "and the lifetime (that is REV_ROUTE_LIFE) and the Originator IP address for the RREP in the route entry" now it says "the lifetime and the Destination IP address for the RREP in the route entry.". Thanks to Moritz Killat. - Adds a bit more of explanation of what a node has to do if it wants to be able to reply as an intermediate node for a route that has been added due to a RREQ or to a RREP in the section '3. Overview'. - Correction: When an intermediate node generates a RREP, the 'Originator IP Address' of the AODV message with a RREP-DSE might be different than the one that was in the RREQ with a RREQ-DSE (so we have to add a field in the RREP-DSE for the old Originator IP Address just in the same way as we do with the lifetime). Thanks to Moritz Killat for noticing it. - Correction: In RREQ-DSE 'Signature' should also sign the 'Signature for RREP' and, to make things clear the 'Signature for RREP' field goes before the 'Signature' field. I noticed this when discussing the DSE mechanism with Moritz Killat. - Correction: Hash functions must be MD5 and SHA1 (not HMACs). Thanks to Varaporn Pangboonyanon for noticing it. - Correction: In the HMACs used to get the SAODV_HID and the SAODV_FID, the data to which the HMACs are going to be applied was missing (now it is PublicKey). So it is an HMAC of the public key with the public key as a key. Version 1 Guerrero Expires 15 March 2005 [Page 29] Internet DRAFT SAODV 15 September 2005 - 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". - Other stuff I might be forgetting. Guerrero Expires 15 March 2005 [Page 30] Internet DRAFT SAODV 15 September 2005 18. Acknowledgments I want to thank all the people from the Nokia Research Center in Helsinki (where I worked for five years) that helped to make SAODV a reality. Special mention deserve my colleague N. Asokan and my bosses Jari Juopperi and Asko Vilavaara. 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. I also want to thank the following persons for their help and improvements to the draft: Sampo Sovio (from Nokia Research Center), Toni Barrera Arboix (while he was working for Nokia Research Center), Varaporn Pangboonyanon, Moritz Killat (from NEC Europe Ltd.) and Francesco Dolcini. 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, Guerrero Expires 15 March 2005 [Page 31] Internet DRAFT SAODV 15 September 2005 [9] R. Hinden and S. Deering: IP Version 6 Addressing Architecture. RFC 2373, July 1998. Author's Address: Questions about this memo can be directed to the author: Manel Guerrero Zapata Computer Architecture Department (DAC) Technical University of Catalonia (UPC) UPC-AC C6-123 Campus Nord C. Jordi Girona 1-3 08034 Barcelona SPAIN (+34) 93 4054044 guerrero@ac.upc.edu Appendix A. Full Copyright Statement Copyright (C) The Internet Society (2005). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. (See RFC 3667 sections 5.4 and 5.5.) Guerrero Expires 15 March 2005 [Page 32]