Subject: Re: [manet] Re Security considerations in MANET

From: "Claude Castelluccia" <[email-masked]>
Date: Wed, 24 Apr 2002 09:45:27 +0200

Hello Panos,

-----Message d'origine-----
De : Panos Papadimitratos <[email-masked]>
À : [email-masked] <[email-masked]>
Cc : [email-masked] <[email-masked]>; Phil Neumiller
<[email-masked]>; Manel Guerrero Zapata
<[email-masked]>; ext Casey Carter <[email-masked]>; ext
Claude Castelluccia <[email-masked]>; Seung Yi
<[email-masked]>; Charles E. Perkins <[email-masked]>; Pekka
Savola <[email-masked]>
Date : mardi 23 avril 2002 19:05
Objet : Re: [manet] Re Security considerations in MANET

>Dear fellow “security enthusiasts”, (:-)
>
>a few things I would like to contribute to your interesting discussion:
>
>First, it is important to realize that not all security solutions can be
>applied in all ad hoc networking environments. At one extreme, the
>conference room resources can use location authentication, i.e., no access
>constraint other than the mobile device location (e.g., short range IR of

i am not convinced that this is enough...sometimes you don't want everbody
in the
conference room being able to play with your presentation ;-)

>RF connectivity). At the other extreme, a MANET of trusted military
>devices, can be capable to perform expensive cryptographic operations and
>have all the infrastructure support we can imagine. In short, the
>interaction between nodes is the one that dictates how to do the trust
>management.
>

>Second, the point of crucial importance for the securing MANET, at least as
>far as I am concerned, is to make clear distinction between:
>-Security of the MANET-based application.
>-Security of the basic networking services.

I do not quite agree with this distinction: the security of the MANET-based
application *depends*
on the security of the basic networking services as least as DoS attacks are
concerned...
If the networking services can not protect you from DoS attacks there is not
much you can do at the
application level...isn't it?

>The challenge is exactly to achieve the latter. And, it has to be done for
>the wide range of network instances between the two above-mentioned
>extremes. And, it has to be done in a way that “understands” the MANET
>paradigm, and does not transplant secure Internet routing solutions.

i agree.

>This is what seems to be happening with most of the secure routing
>solutions for MANET, as we explain in:
>
>P.Papadimitratos and Z.J. Haas, "Secure Routing for Mobile Ad Hoc
>Networks," SCS Communication Networks and Distributed Systems Modeling and
>Simulation Conference (CNDS 2002), San Antonio, TX, January 27-31, 2002.
>
>The rationale behind the Secure Routing Protocol (SRP) in a few lines is:
>
>Even if you have the appropriate distributed CA instantiation (which you
>can have  - see Zhou & Haas), it is not feasible to cryptographically
>validate every single in-transit control packet, even with the upcoming
>commercial mobile devices.
>

this might be true but i am not convinced about that statement yet
especially
if you consider new low-cost authentication schemes such as Biba, Tesla and
others...
probably some more work is required in this area ....

>Even if you have a service- or group- based distribution of credentials,
>the basic network functionality will not be supported only by your trusted
>peers.
>
>Even if you have a heavy-weight crypto-based solution, how do you deal with
>a node that does not comply with a protocol? That is, correct operation
>equals correct connectivity information. And SRP does exactly this,
>avoiding the pitfall of ‘correct is whatever is cryptographically ok’.
>(BTW, that’s the main issue in Internet secure routing s well…)

that's right : crypto is not enough but helps...

>For clarifications, or if you want to hear some possible attacks on the
>discussed protocols (:-), please, don’t hesitate…

i'd like very much to hear about those attacks...

thanks,
regards,
Claude.

>Cheers,
>
>Panos
>
>
>_______________________________________________
>manet mailing list
>[email-masked]
>https://www1.ietf.org/mailman/listinfo/manet
>

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: "Claude Castelluccia" <[email-masked]>
Date: Wed, 24 Apr 2002 09:45:27 +0200

Hello Panos,

-----Message d'origine-----
De : Panos Papadimitratos <[email-masked]>
À : [email-masked] <[email-masked]>
Cc : [email-masked] <[email-masked]>; Phil Neumiller

i agree.

thanks,
regards,
Claude.

---

From: "Claude Castelluccia" <[email-masked]>
Date: Wed, 24 Apr 2002 14:38:33 +0200

-----Message d'origine-----
>D).  In the case that the network has no fixed infrastructure, i.e. a pure
ad hoc network
>       a good solution for key management does not yet exist.  Please find
one.

Hello Phil,

We've actually found one;-)

Our proposal focuses on AODV but
actually could be used with any other MANET protocol. It is
basically a scheme to establish an authenticated secret key between two
hosts that does not have access to an infrastructure (PKI, or others...).

Protecting AODV against Impersonation attacks (or how
to establish a secure tunnel between 2 hosts on a MANET)
=============================================
Claude Castelluccia and Gabriel Montenegro.
April 2002.

1 *Problem statement:
--------------------
- How to protect AODV from impersonation attack: i.e.
how can host H1 that is communicating with H2 over an
insecure Adhoc network that uses AODV have the assurance that when
they receive packets from H2 they actually come from H2 and not for
an impersonator even if the routing insfracture/protocol is insecure...

In current AODV, H1 establishes a route to H2 by sending a RREQ to H2 that
will then replies with a RREP. But actually anyone (a malicious host
on the path or not) can reply to the RREQ and
redirect the packets addressed to H2 to him (eventhough H1 thinks it is
communicating with H2). Furthermore if H1 receives several RREP, how can it
select the right one?

The basic solution is:
- the node uses a CGA (Crypto Generated Addresses) or CGI
(Crypto. Generated Identifiers) [SUCV,CAM]  as address (a CGI is
a identifier is defined as a hash of a public key).
- whenever a host H2 sends packets to H1, it must disclosed its public key
and
 it musts signed its packets (by setting
the mutable field ie hop counts to zero or as specified in sAODV) with its
CGA private key...

As a result, the destination, H1, can verified that the packets have
actually been sent by H2 . This is achieved by verifying that the CGA ou CGI
was generated from the public key and that the signatures are valid.

This solution is not very efficient and requires one signature generation/
verification per packets. This is definetly not acceptable.

A Better solution is:
- H1 and H2 established a secure channel (tunnel) and then encrypt or
authenticated (with a HMAC) their packets with the symetric key that
was generated.

Therefore the problem can now be stated as follows:
- how can two hosts H1 and H2, identified by their address,
 establish a secure (IPSec) tunnel over an insecure adhoc network
that uses AODV.

2 * Proposal description:
---------------------------------
2.1 + requirements:

- H1 and H2 uses CGA or CGI (CGI_H1 and CGI_H2)
 i.e  CGI_H1 =  hashx(PublicKey_H1, counter_H1) x=64 (for CGA) or 128 (for
CGI).
 and CGI_H2 =  hashx(PublicKey_H2, counter_H2)

Note: it is not clear today if a IPv6 address is really needed in MANET.
If this is the case then CGA must be used otherwise CGI (128 bit identifier)
is better since they are cryptographically stronger.

2.2 + protocol description:

- H1 initiates a RREQ, includes in it its PublicKey_H1, counter_H1,
g^x.modp (i.e. a DH value) and an nonce N1 (RREQ id could be used instead)
, and signs the whole message with its PrivateKey_H1.
The RREQ must have the newly defined D flag (see Section 2.3).
set. This flag specifies that only H2  is allowed to reply to this RREQ
with a RREP.

- When H2 receives the RREQ,  it verifies that H1 owns its address and
replies with
  a RREP that contains PublicKey_H2, counter_H2,  g^y. modp, N1 (i.e. RREQ
id), and
signs the whole message with its PrivateKey_H2. H2 also derives the secret
key, Ke that would
be used to establish a secure channel between CGI_H1 and CGI_H2.
For example, Ke  could be defined as follows:
 Ke = hash_x(g^xy mod p)  (where x is the size of the generated key).

- When H2 receives RREP, it verifies that H2 owns its address and
derives the secret Key, Ke.

From then on, the "standard" AODV protocol is used until the SA needs to be
refreshed.

As a result of this exchange, CGI_H1 (resp. CGI_2) has the assurance that it
is talking to CGI_H2 (resp. CGI_H1) and a secure tunnel (i.e. an
authenticated
symetric key) is established between
CGI_H1 and CGI_H2 that can be use to secure (authenticate + encrypt) control
or
data traffic.

2.3 + the "D" flag

-The D (Destination) flag has been added in the RREQ because in the above
protocol,
when H1 sends a RREQ, it wants to make sure that it gets a reply from H2
itself
and not from an intermediate host that has an active route to H2 (as this is
possible in current AODV draft). In fact, RREQ and RREP
carries information (DH exponentiation value) that is used to establish a
symetric key between H1 and H2.
If an intermediate node replies, H2 won't be able to derive the symetric key
and the
protocol will fail.

             Route Request (RREQ) Message Format
    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Type      |J|R|G|D|     Reserved          |   Hop Count   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                   32-bit Flooded Packet ID                    |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |              32-bit Destination Sequence Number               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                 32-bit Source Sequence Number                 |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   :                128-bit Destination IP Address                 :
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                                                               |
   :                   128-bit Source IP Address                   :
   |                                                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

3 + Conclusion
--------------
We propose a protocol that allows two hosts H1 and H2 to establish a secure
tunnel
over an insecure Adhoc network that uses AODV.  Our solution relies on CGI
and the
definition of a new flag (the D flag) in the RREQ packet format.

Our proposal does not use any certificate (and therefore PKI) and does not
require
any TTP support. It is therefore well adapted to adhoc environment and very
scalable.

Note that since the routing infrascture is insecure, our proposol does not
protect H1 and
H2 against DoS attacks. In fact, in our proposal, as in AODV, an attacker
 can easily redirect/hijacked the packets from H1 or H2. Protecting from
these DoS attacks  is a different (or very complex) issue that can
potentially solved by
securing the routing infrastructure or by using schemes that use redundancy
(i.e several paths).
However, even under DoS attacks,  when H1 (and resp. H2) receives a packet
from H2 (resp. H1) it has the assurance that it was not sent by an
impersonator.
That was the goal of our work.

---

From: "Claude Castelluccia" <[email-masked]>
Date: Wed, 24 Apr 2002 14:38:33 +0200

-----Message d'origine-----
ad hoc network
one.

Hello Phil,

1 *Problem statement:
--------------------

The basic solution is:

A Better solution is:

2.3 + the "D" flag

3 + Conclusion
--------------

---

From: "Claude Castelluccia" <[email-masked]>
Date: Wed, 24 Apr 2002 16:08:26 +0200

-----Message d'origine-----
De : Claude Castelluccia <[email-masked]>
À : Phil Neumiller <[email-masked]>; Manel Guerrero Zapata
<[email-masked]>; ext Casey Carter <[email-masked]>
Cc : [email-masked] <[email-masked]>; Seung Yi <[email-masked]>
Date : mercredi 24 avril 2002 14:38
Objet : [manet] Re: Re Security considerations in MANET

>to establish a secure tunnel between 2 hosts on a MANET)

oups, i have just realized that i've sent an old (very drafty)
version of the draft.
Please ignore my previous email and consider the draft attached to
this email...sorry about that...
regards,
Claude.

PS: FYI i'll be travelling for the next 10 days and not sure whether i'll
have an Internet access...but Gabriel (my co-author) will reply to
your comments (or  i'll reply when i'll be back...)

PS: BTW we plan to submit this draft to the AODV workshop in Lausanne
(after MobiHoc)
the submission deadline is April 30th...it would be great to have your
comments
before this deadline to possibly integrate them in the draft...thanks in
advance.

Claude.

----------8><---------------------------8><--------------------------------

Protecting AODV against Impersonation attacks (or how
to establish a secure tunnel between 2 hosts on a MANET)
======================================================
Claude Castelluccia and Gabriel Montenegro.
April 2002.

1 *Problem statement:
--------------------
- How to protect AODV from the impersonation attack: i.e.
how can a host H1 that is communicating with a host H2 over an
insecure Adhoc network that uses AODV has the assurance that when
it receives packets from H2 they actually come from H2 and not from
an impersonator even if the routing insfracture/protocol is insecure...

In current AODV [AODV,AODV6], H1 establishes a route to H2 by sending
a RREQ message to H2 that will then replies with a RREP. But actually anyone
(ecen a malicious host, on the path or not) can reply to the RREQ and
redirect the packets addressed to H2 to him (eventhough H1 thinks
it is communicating with H2). Furthermore if H1 receives several RREP,
how can it select the right one?

The basic solution is:
- the node H2 uses a CGA (Crypto Generated Address) or CGI
(Crypto. Generated Identifier) [SUCV,CAM]  as address (a CGI is
an identifier that is defined as the hash of a public key).
- whenever a H2 sends packets to H1, it must disclosed its public key
and sign its packets (by setting
the mutable fields (ie hop counts) to zero or as specified in sAODV [SAODV])
with its CGA private key...

As a result, the destination, H1, can verify that the packets have
actually been sent by H2 . This is achieved by verifying that the CGA
or CGI was generated from the public key and that the signatures
are valid.

This solution solves the problem but is not very efficient because
it requires one signature generation/verification per packets.
This is not acceptable.

A Better solution is:
- H1 and H2 establish a secure channel (tunnel) and then encrypt or
authenticate (with a HMAC) their packets with the symetric key that
was generated.

Both H1 and H2 define a CGA or CGI, respectively CGI_H1 and
CGI_H2 as follows:
 -CGI_H1 =  hashx(PublicKey_H1, counter_H1) x=64 (for CGA)
or 128 (for CGI).
 -CGI_H2 =  hashx(PublicKey_H2, counter_H2)

where PublicKey_H1 (resp. PublicKey_H2) is a public key
associated with H1 (resp. H2).

Note: it is not clear today if a IPv6 address is really needed in
MANET.
If this is the case then CGA must be used otherwise CGI
(128 bit identifier) is better since they are cryptographically
 stronger.

- H1 initiates a RREQ, includes in it its PublicKey_H1, counter_H1,
g^x.modp (i.e. a DH exponentiation value) and an nonce N1 (RREQ id
could be used instead), and signs the whole message with its
PrivateKey_H1.
The RREQ must have the newly defined D flag (see Section 2.3).
set. This flag specifies that only H2  is allowed to reply to this
RREQ.

- When H2 receives the RREQ,  it verifies that H1 owns its address
(i.e. CGI_H2 was generated from PublicKey_H2 and the signature is valid).
It then replies with a RREP that contains PublicKey_H2, counter_H2,
g^y. modp, N1 (i.e. RREQid), and signs the whole message with its
PrivateKey_H2. H2 also derives the secret key, Ke that would
be used to establish a secure channel between CGI_H1 and CGI_H2.
For example, Ke  could be defined as follows:
Ke = hash_x(g^xy mod p)  (where x is the size of the generated key).

- When H1 receives RREP, it verifies that H2 owns its address and
derives the secret Key, Ke.

From then on, the "standard" AODV protocol is used until the SA
needs to be refreshed.

As a result of this exchange, CGI_H1 (resp. CGI_2) has the assurance
that it is talking to CGI_H2 (resp. CGI_H1) and a secure tunnel
(i.e. an authenticated symetric key) is established between
CGI_H1 and CGI_H2 that can be used to secure (authenticate + encrypt)
control or data traffic.

2.3 + the "D" flag

-The D (Destination) flag has been added to the RREQ packet format
because in our proposal, when H1 sends a RREQ it wants to make sure
that it gets a reply from H2 itself and not from an intermediate host
that may have an active route to H2 (as this is possible in current
AODV draft). In fact, RREQ and RREP carry information (DH
exponentiation value) that are used to establish the symetric key
between H1 and H2. If an intermediate node replies, H2 won't be able
to derive the symetric key and the protocol will fail.

3 + Conclusion
--------------
We propose a protocol that allows two random hosts H1 and H2 to
establish a secure tunnel over an insecure Adhoc network that uses
AODV.  Our solution relies on CGI and the definition of a new flag
(the D flag) in the RREQ packet format.

Our proposal does not use any certificate (and therefore PKI) and
does not require any TTP support. It is therefore well adapted to
adhoc environments and very scalable.

Note that since the routing infrasstructure is insecure, our proposol
does not protect H1 and H2 against DoS attacks. In fact, in our
proposal, as in AODV, an attacker can easily redirect/hijacked the
packets from H1 or H2. Protecting from these DoS attacks  is a
different (or very complex) issue that can potentially solved by
securing the routing infrastructure or by using schemes that use
redundancy (i.e several paths).
However, even under DoS attacks,  whenever H1 (and resp. H2)
receives a packet from H2 (resp. H1) it has the assurance that it
was not sent by an impersonator. That is the goal of our proposal.

References:
----------

[AODV] Charles Perkins, Elisabeth Belding-Royer and Samir Das, Ad Hoc
On Demand Distance Vector (AODV) Routing, draft-ietf-manet-aodv-10.txt,
March 2002.

[AODV6] Charles Perkins, Elisabeth Belding-Royer and Samir Das, Ad Hoc
On Demand Distance Vector (AODV) Routing for IPv6,
draft-ietf-manet-aodv6-01.txt, March 2002.

[CAM] Greg O'Shea and Michael Roe, "Child-proof Authentication for MIPv6
(CAM)", ACM Computer Communication Review, April 2001.

[SAODV] Manel Zapata, Secure Ad hoc On-Demand Vector (SAODV) Routing,
draft-guerrero-manet-saodv-00.txt, August 2001.

[SUCV] Gabriel Montenegro and Claude Castelluccia, "Statistical Unique and
Cryptographically Verifiable (SUCV) Identifiers and Addresses", in NDSS02,
February 2002.

---

From: "Claude Castelluccia" <[email-masked]>
Date: Thu, 25 Apr 2002 09:29:54 +0200

Salut Philippe,

There are at least two good reasons for combining it with the routing
protocol:
1- It might help to solve  some DoS attacks....
For exemple, let's say H1 sends a RREQ for H2 and receives
10 RREPs (9 malicious one and on legitimate one)...how can
he select the right one?? With our approach H1 will be able to
identify the right RREP because it is signed by H2...and will therefore
be able to perform the route discovery correctly...

(note that possibly the intermediate may also verify the RREP validity
before updatin their routing table...)
2- It is more efficient is term of bandwidth utilization...We use 2 messages
instead
of 4 messages....

voila,
Regards,
Claude.

-----Message d'origine-----
De : Philippe Jacquet <[email-masked]>
À : Claude Castelluccia <[email-masked]>; [email-masked]
<[email-masked]>
Date : mercredi 24 avril 2002 17:54
Objet : Re: [manet] Re: Re Security considerations in MANET

>Claude,
>
>Nice stuff. I am relatively new in security considerations, sorry if I ask
>naive questions. Why H1 and H2 must exchange their public keys and
>signatures in RREQ and RREP messages. It cannot be done in simple data
>packets after route discovery? I don't see the plus of involving the
routing
>protocol.
>
>Philippe
>----- Original Message -----
>From: Claude Castelluccia <[email-masked]>
>To: Claude Castelluccia <[email-masked]>; Phil Neumiller
>Cc: <[email-masked]>; Seung Yi <[email-masked]>
>Sent: Wednesday, April 24, 2002 4:08 PM
>Subject: Re: [manet] Re: Re Security considerations in MANET
>
>
>>
>> ----------8><---------------------------8><------------------------------
-
>-