Subject: Secure AODV draft

From: Manel Guerrero Zapata <[email-masked]>
Date: Mon, 08 Oct 2001 13:09:05 +0300

Hi everybody,

I'm attaching in this e-mail a draft that I've been writting myself
(with a lot of help from Asokan and some others).

It 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.
It does so by using certificates and hash chains. And it is not
oriented for only-military scenarios.

While still might need to be polished a little, I thing it is ready
to be published in this list.

Your comments are, of course, more than wellcome.

Best regards,

	Manel Guerrero

P.D.: Yi, Naldurg and Kravets just presented in this MobiHoc a panel
with another aproach that also tries to solve the problem of how
to make AODV secure. Their aproache uses symmetric cryptography
and it is clearly oriented for military scenarios.

Mobile Ad Hoc Networking Working Group             Manel Guerrero Zapata
INTERNET DRAFT                                     Nokia Research Center
12 August 2001

        Secure Ad hoc On-Demand Distance Vector (SAODV) Routing
                   draft-guerrero-manet-saodv-00.txt

Status of this Memo

   This document is _not_yet_ a submission by the Mobile Ad-hoc Networks
   (manet) Working Group of the Internet Engineering Task Force (IETF).

   Distribution of this memo is unlimited.

   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 12 February 2002                [Page 1]

Internet DRAFT            CONFIDENTIAL - SAODV            12 August 2001

                             Table of Contents

1. Introduction  . . . . . . . . . . . . . . . . . . . . . . . . . .   3
2. Preliminary notes . . . . . . . . . . . . . . . . . . . . . . . .   3
     2.1. Security Features  . . . . . . . . . . . . . . . . . . . .   3
     2.2. Interaction with IPSec . . . . . . . . . . . . . . . . . .   4
     2.3. Key distribution . . . . . . . . . . . . . . . . . . . . .   4
3. Overview  . . . . . . . . . . . . . . . . . . . . . . . . . . . .   5
4. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . .   6
5. RREQ (Single) Signature Extension . . . . . . . . . . . . . . . .   6
6. RREP (Single) Signature Extension . . . . . . . . . . . . . . . .   7
7. RREQ Double Signature Extension . . . . . . . . . . . . . . . . .   8
8. RREP Double Signature Extension . . . . . . . . . . . . . . . . .   9
9. RERR Signature Extension  . . . . . . . . . . . . . . . . . . . .  10
10. RREP-ACK Signature Extension . . . . . . . . . . . . . . . . . .  11
11. SAODV Operation  . . . . . . . . . . . . . . . . . . . . . . . .  11
     11.1 SAODV Signatures . . . . . . . . . . . . . . . . . . . . .  11
     11.2 SAODV Hash Chains  . . . . . . . . . . . . . . . . . . . .  12
12. Adaptations of AODV that are needed  . . . . . . . . . . . . . .  13
13. Security Considerations  . . . . . . . . . . . . . . . . . . . .  14
14. Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . .  15

Guerrero                Expires 12 February 2002                [Page 2]

Internet DRAFT            CONFIDENTIAL - SAODV            12 August 2001

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, IPSec interacting with SAODV, and the key distribution
   system.

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

Guerrero                Expires 12 February 2002                [Page 3]

Internet DRAFT            CONFIDENTIAL - SAODV            12 August 2001

   can joint at any moment. Therefore, it is not taken into account in
   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.

2.3. Key distribution

   This paper does not discuss how all the different nodes get to know
   the public key of the other nodes. There are some preliminary works
   about how to build a key distribution system for manet networks.
   Besides, if the nodes connect periodically to a fixed network (like
   Internet) where a certification authority can be reached, they could
   get the public keys of different manet nodes, plus the public key of
   the certification authority. This would avoid the need of having a
   manet key distribution system.

   Anyway, there is one issue that has to be taken into account when
   using such systems for AODV networks:

   When distributing a public key, with the public key it also should
   come the IP address of the node (of course) and the netmask (in the
   case the node is a network leader). This would avoid the attack in
   which a malicious node becomes a black hole for a whole subnet by
   claiming that it is their network leader.

   If no certificates are used (only private and public keys) it will be
   assumed that the hash algorithm is SHA [4] and the encryption method
   is RSA [5]. If certificates are used they already include which
   algorithms should be used.

Guerrero                Expires 12 February 2002                [Page 4]

Internet DRAFT            CONFIDENTIAL - SAODV            12 August 2001

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
   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 use the same authentication extension that
   RREPs. RERR messages do not have any security extension messages.

   The hop count of all these messages is authentified by using a hash
   chain.

Guerrero                Expires 12 February 2002                [Page 5]

Internet DRAFT            CONFIDENTIAL - SAODV            12 August 2001

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].

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                            |
    ...                                                         ...
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                           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 funtion 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    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 12 February 2002                [Page 6]

Internet DRAFT            CONFIDENTIAL - SAODV            12 August 2001

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                            |
    ...                                                         ...
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                           Signature                           |
    ...                                                         ...
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                             Hash                              |
    ...                                                         ...
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Type         65

   Length       The length of the type-specific data, not including the
                Type and Length fields of the extension.

   Hash Function The hash funtion 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    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 12 February 2002                [Page 7]

Internet DRAFT            CONFIDENTIAL - SAODV            12 August 2001

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                            |
    ...                                                         ...
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                           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 funtion 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.

   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    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

Guerrero                Expires 12 February 2002                [Page 8]

Internet DRAFT            CONFIDENTIAL - SAODV            12 August 2001

                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.

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                            |
    ...                                                         ...
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                           Signature                           |
    ...                                                         ...
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                          Old Lifetime                         |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                 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 funtion used to compute the Hash and Top Hash
                fields.

   Max Hop Count The Maximum Hop Count supported by the hop count
                authentication.

Guerrero                Expires 12 February 2002                [Page 9]

Internet DRAFT            CONFIDENTIAL - SAODV            12 August 2001

   Top Hash     The top hash for the hop count authentication. This
                field has variable length, but it must be 32-bits
                aligned.

   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 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.

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            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                           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    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 12 February 2002               [Page 10]

Internet DRAFT            CONFIDENTIAL - SAODV            12 August 2001

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     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                           Signature                           |
    ...                                                         ...
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Type         69

   Length       The length of the type-specific data, not including the
                Type and Length fields of the 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. 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.

11.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

Guerrero                Expires 12 February 2002               [Page 11]

Internet DRAFT            CONFIDENTIAL - SAODV            12 August 2001

   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 Doble 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.

   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.

11.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.

Guerrero                Expires 12 February 2002               [Page 12]

Internet DRAFT            CONFIDENTIAL - SAODV            12 August 2001

   Every time a node wants to send a RREQ or a RREP it generates a
   secret random number. 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 secret number hashed one time.
   The Top Hash field is set to the secret number 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. This avoids forwarding nodes to pick up weeker
   hash algorithms than what the originator of the RREQ considers
   required. 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-MD5-96 and HMAC-
   SHA-1-96 options.

12. Adaptations of AODV that are needed

   According to the AODV draft [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.

Guerrero                Expires 12 February 2002               [Page 13]

Internet DRAFT            CONFIDENTIAL - SAODV            12 August 2001

   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 8.11. 'Actions After
   Reboot' in the AODV draft [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.

13. 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 choosen 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.

Guerrero                Expires 12 February 2002               [Page 14]

Internet DRAFT            CONFIDENTIAL - SAODV            12 August 2001

   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.

14. Acknowledgments

   N. Asokan 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 discused with me several ways of how to use hashing
   techniques for SAODV.

   Toni Barrera Arboix gave very valuable orientations about
   certificates.

   All of them (Asokan, Sampo and Toni) are from Nokia Research Center.

References

   [1] Charles E. Perkins, Elizabeth M. Royer, Samir R. Das: Ad hoc On-
   Demand Distance Vector (AODV) Routing (work in progress). draft-ietf-
   manet-aodv-08.txt, March 2001.

   [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.

Guerrero                Expires 12 February 2002               [Page 15]

Internet DRAFT            CONFIDENTIAL - SAODV            12 August 2001

   [7] L. Zhou, Z. J. Haas: "Securing Ad Hoc Networks", IEEE Network
   Magazine, vol. 13, no.6, November/December 1999.

Author's Address:

   Questions about this memo can be directed to the author:

       Manel Guerrero Zapata
       Mobile Networks Laboratory
       Nokia Research Center
       Itamerenkatu 11 - 13
       FIN-00180 Helsinki
       +358 718037368
       [email-masked]

Guerrero                Expires 12 February 2002               [Page 16]

---

From: "Seung Yi" <[email-masked]>
Date: Fri, 12 Oct 2001 10:20:39 -0500

At the end of his post of the SAODV draft, Mr. Manel Guerrero added some
comments on our research project 'Security-aware Routing for Ad-hoc
Networks'. We feel some of his comments are not exactly correct and would
like to provide our opinions.

The goal of our security-aware ad hoc routing (SAR) project is two-fold,
exposing security to the application and securing the routing protocol.
Our first goal is to characterize and explicitly represent the trust values
and trust relationships associated with ad hoc nodes and use these values to
make routing decisions.  Our second goal is to secure the information in the
routing messages against alteration that can change routing behavior.
Introducing security into the routing protocol has an associated performance
penalty. Rather than propose a specific solution, we develop a generalized
framework with open feedback and explicit representation of attributes and
choices. This allows users to change the security attributes dynamically and
renegotiate for alternative routes, based on (but not limited to) the
cost-benefit analysis of the performance penalties versus the protection
offered in the given situation.

Although the experimental results presented in our paper use AODV as a base
protocol (hence the similar name SAODV), our solution presents a framework
for security-aware routing that can be integrated in many ad hoc routing
protocols, and so are not limited to use with only AODV .

Mr. Manel Guerrero described SAR as yet another approach to solve the same
problem he tries to solve, namely 'how to make AODV secure'. This is a clear
understatement. Also, he mentioned that our approach is using symmetric
cryptography and clearly coming out of military contexts. That's also not
exactly true.

First of all, SAR is not yet another approach trying to secure the routing
protocols. In SAR, we use security attributes as metrics in the routing
protocols, so security levels and mechanisms can be considered when making
routing decisions.  As a result, the security concerns become a property of
the paths that can enable better informed operations at the application
layer. With SAR, applications can request quantifiably secure routes rather
than just asking for the shortest path toward the destination.

Another aspect of the SAR is the problem Mr. Manel Guerrero is also trying
to solve. We also try to secure our routing protocols so that the malicious
nodes can not disrupt routing behavior. For this, we are not confining
ourselves to just symmetric cryptography and military scenarios as he
described.  Indeed, we used symmetric cryptography in our initial
implementation of SAR. But that was just for proof-of-concept and we have no
intention to limit SAR to only using symmetric cryptography. One of the
ongoing research in SAR project is the introduction of public key
cryptography into SAR and we're investigating the issue of providing the
Certificate Authority functionality within the ad-hoc networks. Compared to
our approach, Mr. Manel Guerrero's draft assumed some kind of CA
functionality in section 2.3 of his draft, rather than providing a solution.

About the military orientation comments, our approach is to use the existing
structure of the organization that deploy ad hoc networks in the routing
decisions. It can be a military unit, a corporation, or even a school. Any
organizational structure would suffice. Any scenario where the nodes can be
differentiated by some criteria can be used in SAR. So, it's unfair to
describe SAR as designed for the military contexts only.

For any further details of SAR, we would like to invite you to read our
technical report. It is available online at
http://www.cs.uiuc.edu/Dienst/UI/2.0/Describe/ncstrl.uiuc_cs/UIUCDCS-R-2001-2241.

Please feel free to direct any questions to any of authors.
Seung Yi,           [email-masked]
Prasad Naldurg,     [email-masked]
Dr. Robin Kravets,  [email-masked]

Thanks.