Subject: [RAM] Fwd: I-D ACTION:draft-bagnulo-lisp-threat-01.txt

From: marcelo bagnulo braun <[email-masked]>
Date: Wed, 11 Jul 2007 16:49:07 +0200

Hi,

I have updated the threat analysis for LISP to the new 01 version of  
LISP.

Regards, marcelo

Inicio del mensaje reenviado:

> De: [email-masked]
> Fecha: 9 de julio de 2007 21:15:02 GMT+02:00
> Para: [email-masked]
> Asunto: I-D ACTION:draft-bagnulo-lisp-threat-01.txt
> Responder a: [email-masked]
>
> A New Internet-Draft is available from the on-line Internet-Drafts
> directories.
>
>
> 	Title		: Preliminary LISP Threat Analysis
> 	Author(s)	: M. Bagnulo
> 	Filename	: draft-bagnulo-lisp-threat-01.txt
> 	Pages		: 16
> 	Date		: 2007-7-9
> 	
> This document performs a preliminary threat analysis on the
>    Locator/ID Separation Protocol (LISP) as defined in
>    draft-farinacci-lisp-01.txt.
>
> A URL for this Internet-Draft is:
> http://www.ietf.org/internet-drafts/draft-bagnulo-lisp-threat-01.txt
>
> To remove yourself from the I-D Announcement list, send a message to
> [email-masked] with the word unsubscribe in the body of
> the message.
> You can also visit https://www1.ietf.org/mailman/listinfo/I-D-announce
> to change your subscription settings.
>
> Internet-Drafts are also available by anonymous FTP. Login with the
> username "anonymous" and a password of your e-mail address. After
> logging in, type "cd internet-drafts" and then
> "get draft-bagnulo-lisp-threat-01.txt".
>
> A list of Internet-Drafts directories can be found in
> http://www.ietf.org/shadow.html
> or ftp://ftp.ietf.org/ietf/1shadow-sites.txt
>
> Internet-Drafts can also be obtained by e-mail.
>
> Send a message to:
> 	[email-masked].
> In the body type:
> 	"FILE /internet-drafts/draft-bagnulo-lisp-threat-01.txt".
> 	
> NOTE:	The mail server at ietf.org can return the document in
> 	MIME-encoded form by using the "mpack" utility.  To use this
> 	feature, insert the command "ENCODING mime" before the "FILE"
> 	command.  To decode the response(s), you will need "munpack" or
> 	a MIME-compliant mail reader.  Different MIME-compliant mail readers
> 	exhibit different behavior, especially when dealing with
> 	"multipart" MIME messages (i.e. documents which have been split
> 	up into multiple messages), so check your local documentation on
> 	how to manipulate these messages.
>
> Below is the data which will enable a MIME compliant mail reader
> implementation to automatically retrieve the ASCII version of the
> Internet-Draft.
> Content-Type: text/plain
> Content-ID: <[email-masked]>
>
> _______________________________________________
> I-D-Announce mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/i-d-announce

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

---

From: Robin Whittle <[email-masked]>
Date: Thu, 12 Jul 2007 14:39:02 +1000

My understanding of:

  http://tools.ietf.org/html/draft-bagnulo-lisp-threat-01

is that 3.1 to 3.1.1.3 involves sending an encapsulated packet to
a combined ETR-ITR which convinces that router that the RLOC to
use when encapsulating packets with EID=V is the the attacker's
address.  So subsequent packets with EID=V will wind up at the
attacker's host.

This is for "LISP 1" (1.5?) where there is no central database.

In LISP 2.x, 3.x or 4.x:

http://www1.ietf.org/mail-archive/web/ram/current/msg01289.html

is it true to say that the ETR-ITR wouldn't learn any such false
information simply by receiving a packet, because its mapping is
controlled by a database instead?

Ivip's ITRs are always controlled by one or more databases - there
are no messages and ETRs don't "learn" anything from the
encapsulated packet.  So this vulnerability doesn't apply to Ivip.

Likewise, Ivip has no "Map-Reply" message and the ITRs don't learn
their mapping from anything other than their own copy of the
database(s) or from responses resulting from queries to a query
server which has a copy.  So the rest of section 3.1, 3.2.1, 3.2.2
and 3.2.3 doesn't apply to Ivip.

In LISP 2 to 4 does the ITR learn mapping information from
Map-Reply messages or from an associated ETR learning an RLOC from
the outer header of an encapsulated packet it receives?

3.2.4 concerns the cache of ETRs or ITRs overflowing - but the
sentence:

  An attacker could massively generate either tunnelled data
  packets so that the router cache is overflowed.

looks incomplete.

I think that in all LISP variants the ITR is not intended to carry
a copy of the entire database, so in principle its cache could be
overflowed by either making it learn mapping information from the
headers of encapsulated packets or perhaps by some use of the Map
Reply message.

I think the ITR's cache could also be made to overflow by simply
sending packets to it which are addressed to a wide variety of
LISP EIDs, each with different mappings.  This would force the ITR
to query and cache the mapping for each EID, or for whatever
prefix each EID is within which has the same mapping information.

Ivip has ITRDs with a full copy of "the database" - actually
multiple arrays of mapping information, one for each Ivip Mapped
Address Block (IMAB, previously "master-subnet").  So an ITRD
can't be overloaded by any pattern of destination addresses in the
packets it encapsulates.  This is practical, at least for IPv4,
using a server with a 64 bit CPU, rather than a conventional
router (though in principle some routers could do it) because the
Ivip mapping is simply a 4 byte IP address for every address in
the IMABs.  (LISP's data per EID IP address or prefix is more
extensive.)  2 billion Ivip-mapped addresses therefore require 8
gigabytes of RAM, plus some extra RAM for indexing into this set
of arrays for each IMAB and for decoding the incoming database
dumps (boot time) and real-time updates.

Ivip ITRCs (caching ITRs) and ITFHs (caching ITR functions in
sending hosts) are subject to some cache size limit and so would
be subject to a DoS attack (or simply non-malicious traffic) which
consisted of a sufficiently fast and diverse range of data packets
to addressed to Ivip-mapped addresses.  However, the response of
an ITFH or ITRC to this would probably be to not try to retain the
mapping for every address of every packet - which is the same as
their normal way of working, which is to only seek mapping
information for addresses for which multiple packets are received.

If an ITFH lets through a packet without tunneling it, then the
packet will be forwarded to some ITRC or ITRD (or maybe explicitly
tunneled by the ITFH to an ITRD).  Likewise, if things are
properly organised, an ITRC doesn't have to encapsulate and tunnel
every packet with an Ivip-mapped DA.  It can either tunnel these
packets to some other ITRC, or ideally to an ITRD, which will
handle them - or if the local routing system is suitably
organised, the packets will flow through one or more ITRCs or
ITRDs anyway.

I will add something like this to the I-D:

  The idea is that any ITFH or ITRC can let a packet addressed
  to an IMAB pass on to another ITRC or an ITRD which will handle
  it.

  This will happen naturally with an ITFH, since any still
  unencapsulated packets it emits will ultimately be forwarded
  to some router which advertises the Ivip-Mapped Address Blocks
  (IMABs) and so can presumably definitely encapsulate the packet.

  To achieve this, any ITRC which advertises the Ivip IMABs must
  have a way of tunneling the packets it can't handle to some
  other ITR which definitely can encapsulate them.  This could be
  another such ITRC, provided any chain or tree of these always
  forwards packets which still need to be encapsulated towards
  either an ITRD which will do it, or to the Internet, where
  the packets should find such an ITRD (which hopefully won't
  be overloaded.)

  ITRC functions could be installed on internal routers in
  a network, so they look out for all packets with DA matching
  any IMAB and either encapsulate them, or leave them
  unencapsulated.  However, forwarding some or all of these
  packets without encapsulation will only work if this ITRC
  does not actually advertise itself as the destination for
  packets addressed to these IMABs.  If it did, the packets
  it forwards which still need to be encapsulated will probably
  not progress to any other router.  So an ITRC which is simply
  in the path of packets in general, without advertising itself
  as the destination for the Ivip IMABs, doesn't need to
  explicitly tunnel packets it can't handle to some other ITR.

So the impact of the DoS attack on any one ITRC or ITFH in a
network which was correctly configured for Ivip (according to the
new text above) would be to cause some packets to go on longer
paths before an ITR encapsulated them.  This would cause extra
load on the network, and on these other ITRs, but unless the
packet wound up at a core ITR or some other ITR which advertised
the IMAB prefixes and was overloaded with traffic, then the packet
would always be encapsulated and find its way to the destination.

  - Robin     http://www.firstpr.com.au/ip/ivip/

---

From: marcelo bagnulo braun <[email-masked]>
Date: Thu, 12 Jul 2007 12:22:52 +0200

Hi Robin,

> address.  So subsequent packets with EID=V will wind up at the

right

> This is for "LISP 1" (1.5?) where there is no central database.

this applies to LISP as defined in draft-farinacci-lisp-01 which states:

    This document will focus on LISP 1 and LISP 1.5, both of which rely
    on a router-based distributed cache and database for EID-to-RLOC
    mappings.  The LISP 2 and LISP 3 mechanisms, which require separate
    EID-to-RLOC infrastructure, will be documented in additional drafts.

So, it is not clear to me whether this threats apply only to LISP1  
and 1,5, it depends on whether the other (yet to be documeted)  
versions of LISP will learn using data and MapReply packets or they  
will striclty learn mapping infromation from the database interface

which is clear that an additional threat analysis is needed to  
understand the threats to the database, how to introduce and  
propagate mapping information in it.

> controlled by a database instead?

i don't know, there is no ID describing LISP v2,3,4 afaik

> encapsulated packet.  So this vulnerability doesn't apply to Ivip.

haven't read the ivip draft yet, sorry,

> and 3.2.3 doesn't apply to Ivip.

the tradeoff here, is that the receiving host needs to query the  
database to learn that information, introducing additional latency  
when the first packet is received i guess.

> the outer header of an encapsulated packet it receives?

don't know, as i said i am not aware of any ID that documents lisp 2,3,4

>   packets so that the router cache is overflowed.

?

> headers of encapsulated packets or perhaps by some use of the Map

exactly

> prefix each EID is within which has the same mapping information.

right

> information for addresses for which multiple packets are received.

so, they would seeks for the maping information, forward the packet  
and discard the mapping information? So, when the second packet  
arrives, do they rememeber that they have queried for the same  
mapping before? (If yes, then they store some state, hence a DoS  
vector is possible)

In any case, i guess that:
- if you have a mapping database, the effect of the DoS attack is  
less than when you don't since you can recover the mapping  
information, so you don't have to discard the packets for which you  
have discarded the cache information (which is the case of LISP 1, 1,5)
- the DoS attack will also affect the mapping database, which will  
receive all the requests from all the routers it is serving,

regards, marcelo

---

From: Robin Whittle <[email-masked]>
Date: Thu, 12 Jul 2007 21:34:55 +1000

Hi Marcelo,

I was just stating how I believe Ivip differs from LISP and asking
questions about LISP, for Dino and others to answer rather than you.

>>   packets so that the router cache is overflowed.

it was because I couldn't make full sense of this sentence in the
context.  I thought maybe it should be "either tunneled data
packets or ICMP packets" or similar - I think this is just a typo
or expression glitch.

> so, they would seeks for the maping information, forward the packet and
> discard the mapping information? So, when the second packet arrives, do
> they rememeber that they have queried for the same mapping before? (If
> yes, then they store some state, hence a DoS vector is possible)

OK - this is my bad expression.

What I meant to write is that with Ivip, the ITRC's job is to find
and tunnel as many packets as it can.  It doesn't necessarily have
to tunnel each one, because (ideally, one way or another) the
untunneled packets will get to to another ITRD - perhaps via one
or more ITRCs.  Unless it is too busy, that ITRD which will tunnel
it immediately, because its FIB is set up to do every mapping in
the system.  I described what needs to happen in order that
packets will be handled like this later in my message in the text
following "I will add something like this to the I-D:".

So an ITRC which is running out of cache memory could either dump
some of its cached mapping and use the space for a recently
received response, or it could keep the current cache contents.
Either way, it is probably going to get packets it doesn't have
mapping data for, so it doesn't tunnel them.

> - if you have a mapping database, the effect of the DoS attack is less
> than when you don't since you can recover the mapping information, 

The idea with Ivip is that nearby, there will be a QSD which has a
copy of the database and can answer queries quickly.  Maybe the
ITRC doesn't send the query to that directly, but to a closer (and
less expensive) QSC caching query server.  This way, one QSD with
one feed of update data can handle a bunch of QSCs which can
collectively handle more ITRCs than just the QSD alone.  Ideally,
it would only take a fraction of a second for any of these ITRCs
to get a response to its query, so it might be OK for the ITRC to
hold a packet for a moment while it waits for the response - but
then if the response doesn't come, it is left with a highly
delayed packet.  My idea is that the ITRCs would not hold onto
packets at all, but would let those it doesn't have mapping pass
through untunneled.

> so
> you don't have to discard the packets for which you have discarded the
> cache information (which is the case of LISP 1, 1,5)

LISP doesn't have any alternative as exists (or at least can and
generally will exist) for Ivip, so any ITR which can't get mapping
data will effectively drop the packet - and all LISP ITRs need to
get the mapping information from somewhere else, since the whole
database is too big to store.

> receive all the requests from all the routers it is serving,

The QSD and any QSCs (which also have limited caches) would
certainly get a hammering.  The result would be that other ITRCs
nearby which are not subject to the attack would not be able to
get so many responses to its requests.  So those ITRCs will be
passing more untunneled packets.  Further along in the path taken
by the packets, other ITRCs or an ITRD will get a lot more packets
to handle than usual, which ultimately means that beyond some
level, the DoS attack will succeed - including by stopping the
tunneling of some packets from other parts of the network which
rely on the one ITRD as the last way of tunneling packets.

I plan to finalise the ivip-arch-00 I-D on Sunday.  There isn't
enough detail in it regarding how the database updates get to the
ITRD and QSD for a security critique to be made.  There is a lot
of stuff to think about regarding getting updates to hundreds of
thousands of ITRDs and QSCs all over the world.

I am thinking it that unless some really snappy techniques can be
developed, it would be difficult to absolutely protect against
spoofed packets being sent to the ITRDs and QSCs - but I think
there will be ways of detecting any problems within a few seconds.

These are really interesting problems.

 - Robin

---

From: marcelo bagnulo braun <[email-masked]>
Date: Thu, 12 Jul 2007 16:24:22 +0200

Hi Robin,

> questions about LISP, for Dino and others to answer rather than you.

I am relieved then :-)

> packets or ICMP packets" or similar - I think this is just a typo

right, i think the either should be removed and it should then make  
more sense...

> or more ITRCs.

so this basically means that the attack is propagated to other  
ITRC's, right? I mean, if oneITRC is receiving too many packets and  
it decides to forward them without tunnelling them to the next ITRC,  
then the the next ITRC will start receiving a huge amount of  
untunnelled packets, hence the attack is now not only affecting the  
initial router under attack but also to other routers that were used  
as fall back.

My point is that this is a two edged sword. On one hand, you have  
more processing power, becuase you can get the help of other routers,  
but otoh, a single attack can have a domino effect and affect  
multiple routers... makes sense?

>   Unless it is too busy, that ITRD which will tunnel

so other routers will need to tunnel them, hence the effect of the  
attack will affect the other routers as well, right?

>> less

so, bascally the effect of the dos based on overflowing the cache  
would be that the system is slower, because for every new address,   
query to the database is needed. (this seems better than not being  
able to communicate :-)

> database is too big to store.

yes, this is what i meant in the threat analysis and this seems an  
grave vulnerability imho

> rely on the one ITRD as the last way of tunneling packets.

yes, i think this is what i expressed above...

> These are really interesting problems.

i would expect that certificates similar to those being proposed in  
sidr for bgp could be used for protecting this database. It would be  
nice to have cheaper techniques though

Regards, marcelo

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 12 Jul 2007 23:08:46 -0700

> i don't know, there is no ID describing LISP v2,3,4 afaik

There will probably never be a LISP 2 because many people have  
sounded off about the circular dependency even though DNS gives the  
best low latency for a request based mapping lookup (that is, it  
shares the DNS lookup latency with the map lookup).

The LISP authors have never mentioned or defined a variant numbered 4.

And for LISP 3, there is currently 3 examples of LISP 3, that is  
CONS, NERD, and APT.

Dino

---

From: marcelo bagnulo braun <[email-masked]>
Date: Fri, 13 Jul 2007 10:49:32 +0200

> And for LISP 3, there is currently 3 examples of LISP 3, that is  

from a security analysis perspective, i guess an important question  
would be if in LISP 3, TR also learn through tunneled data packets  
and MAP-Reply packets as described in the draft-farinacci-lisp-01. If  
yes, then we need to see if the threats identified in the threat  
analysis draft also apply (but it is likely to be the case, if no  
additional measures are taken to prevent them)

regards, marcelo

---

From: Robin Whittle <[email-masked]>
Date: Fri, 13 Jul 2007 20:12:29 +1000

Hi Dino,

You wrote of Marcelo's comment:

> There will probably never be a LISP 2 because many people have sounded
> off about the circular dependency even though DNS gives the best low
> latency for a request based mapping lookup (that is, it shares the DNS
> lookup latency with the map lookup).
> 
> And for LISP 3, there is currently 3 examples of LISP 3, that is CONS,
> NERD, and APT.

I mentioned LISP 2.x, 3.x and 4.x, which are listed in your
message on 16 April:

including several 4.x variants.  I don't recall any other mentions
of 4.x.

I don't think there is a problem with circular dependencies with
LISP using DNS provided the LISP-mapped address space comes with a
caution or something to say it shouldn't be used for some DNS
functions, including root nameservers and a few other things, and
any nameserver on which LISP depends.  Brian Carpenter made the
original circularity critique, I think, but on 28 June:

  http://www1.ietf.org/mail-archive/web/ram/current/msg01588.html

I think he agreed to a certain extent with the limitations I
suggested which would prevent circularity problems.  His remaining
critique is that the list of constraints is "operationally error
prone", but I think a lot of things we have to rely on are
"operationally error-prone".

  - Robin

---

From: Dino Farinacci <[email-masked]>
Date: Fri, 13 Jul 2007 16:21:17 -0700

> and MAP-Reply packets as described in the draft-farinacci-lisp-01.  
> If yes, then we need to see if the threats identified in the threat  

Yes, I agree. We are assuming at this point that CONS and NERD are  
control plane based and do not have data-triggered Map-Replies. Using  
APT, it depends. Because the design indicates that you send packet  
along the mapping service topology. That is a bit different where  
there isn't data plane triggered mappings but the data is sent over a  
control-plane. Much different than a LISP 1 and 1.5 approach.

Dino

---

From: Dino Farinacci <[email-masked]>
Date: Fri, 13 Jul 2007 18:34:32 -0700

> including several 4.x variants.  I don't recall any other mentions

You shouldn't take an email reference verbatim. I said in that email  
"for instance" and it was never documented in an ID so we were  
brainstorming.

Dino