Subject: Re: [lisp] Anybody can participate in the IETF (Was: Why is IPv6 broken?)

From: Dino Farinacci <[email-masked]>
Date: Sun, 10 Jul 2011 15:42:48 -0700

> From: Jeff Wheeler <[email-masked]>
> Date: July 10, 2011 1:43:40 PM PDT
> To: NANOG <[email-masked]>
> Subject: Re: Anybody can participate in the IETF (Was: Why is IPv6  
> broken?)

I am not on the Nanog mailing list but a friend forwarded this to me.  
I would like to respond to your LISP comments Jeff. See responses  
inline.

I have copied the [email-masked] mailing list.

> On Sun, Jul 10, 2011 at 3:45 PM, Owen DeLong <[email-masked]> wrote:
>> Number two: While anyone can participate, approaching IETF as an
>> operator requires a rather thick skin, or, at least it did the last  
>> couple
>> of times I attempted to participate. I've watched a few times where
>
> I am subscribed to the IDR (BGP, etc.) and LISP lists.  These are
> populated with different people and cover entirely different topics.
> My opinion is the following:
>
> * The IDR list is welcoming of operators, but whether or not your
> opinion is listened to or included in the process, I do not know.
> Randy Bush, alone, posts more on this list than the sum of all
> operators who post in the time I've been reading.  I think Randy's
> influence is 100% negative, and it concerns me deeply that one
> individual has the potential to do so much damage to essential
> protocols like BGP.  Also, the priorities of this list are pretty
> fucked.  Inaction within this working group is the reason we still
> don't have expanded BGP communities for 32 bit ASNs.  The reason for
> this is operators aren't participating.  The people on the list or the
> current participants of the WG should not be blamed.  My gripe about
> Randy Bush having the potential to do huge damage would not exist if
> there were enough people on the list who understand what they're doing
> to offer counter-arguments.
>
>> operators were shouted down by purists and religion over basic
>> real-world operational concerns. It seems to be a relatively routine
>> practice and does not lead to operators wanting to come back to
>> an environment where they feel unwelcome.
>
> I have found my input on the LISP list completely ignored because, as
> you suggest, my concerns are real-world and don't have any impact on
> someone's pet project.  LISP as it stands today can never work on the

I bet your concerns are real-world but there are a lot of reasons why  
there is a lack of response on mailing lists. Maybe a lot is going on  
at the time or people are too busy to respond. But we, the LISP  
authors take input very seriously. I can speak for myself, we do not  
want to ignore the mailing list. It is the mailing list that has  
brought LISP to where it is today. And many are grateful of that.

If you could please restate on the list what your concerns are, we can  
have a discussion.

> Internet, and regardless of the fine reputations of the people at
> Cisco and other organizations who are working on it, they are either
> furthering it only because they would rather work on a pet project
> than something useful to customers, or because they truly cannot

Many of us have been working on the Internet for a very long time. We  
do so because we have passion to keep growing and scaling it. That is  
a basic fact. If you think that sounds cliche, then I am sorry for  
that. But, at least for me, it is simple as that.

> understand its deep, insurmountable design flaws at Internet-scale.
> You would generally hope that someone saying, "LISP can't work at
> Internet-scale because anyone will be able to trivially DoS any LISP
> ITR ('router' for simplicity),

Many have made this comment and that is why we have been working hard  
on cache management to see, if in practice, this is a real problem.  
The Internet has caches all over the place, some have proven to work  
extremely well and the Internet would not be at the scale it is today  
without them.

Many researchers have looked at ITR caching and there are papers  
published that discuss pros and cons.

> but here is a way you can improve it,"
> well, that remark, input, and person should be taken quite seriously,

What data do you have that it was not taken seriously?

> their input examined, and other assumptions about the way LISP is
> supposed to work ought to be questioned.  None of this has happened.

The main spec has gone through 29 revisions. LISP have been in review  
for 4 years both in the IRTF and the IETF. There is a pilot network  
with approximately 120 boxes in 25 countries. This is a very serious  
undertaking. There are real resources and real dollars going into this.

> LISP is a pet project to get some people their Ph.D.s and keep some

People will get their Ph.D's from all kinds of networking research.  
That is the nature of the beast and of course not specific to LISP.

> old guard vendor folks from jumping ship to another company.  It is a
> shame that the IETF is manipulated to legitimize that kind of thing.

Both points are hard to comment on without being negative. And I don't  
want to be negative. I want to take your comments as constructive and  
start a technical discussion on your concerns.

> Then again, I could be wrong.  Randy Bush could be a genius and LISP
> could revolutionize mobility.

We are all wrong and we are all right. Let's start the technical  
discussion.

Thanks,
Dino

> -- 
> Jeff S Wheeler <[email-masked]>
> Sr Network Operator  /  Innovative Network Concepts

---

From: Jeff Wheeler <[email-masked]>
Date: Sun, 10 Jul 2011 19:47:31 -0400

On Sun, Jul 10, 2011 at 6:42 PM, Dino Farinacci <[email-masked]> wrote:
> or people are too busy to respond. But we, the LISP authors take input very
> seriously. I can speak for myself, we do not want to ignore the mailing

I suggest you read my post, linked below, discussing cache management
vulnerabilities, and a way to improve upon them.  Darrel Lewis is the
only person who has showed any interest in this at all, and there has
been essentially zero public discussion of it.  I have also swapped
email with the authors of the lisp-threats draft, who believe this
problem warrants precisely one vague sentence.

http://www.ietf.org/mail-archive/web/lisp/current/msg02949.html

You can imagine how my view of LISP as a pet project, consuming vendor
personnel / resources on something which may have, at best, VPN
application, came about.  This is a very obvious problem with a great
deal of history -- many of the people I see working on LISP have been
around since flow-cache routing was popular, and unpopular, certainly
including yourself.  Some have not been and have yet to learn some of
the lessons from the 90s.

> Many researchers have looked at ITR caching and there are papers published
> that discuss pros and cons.

An academic paper examining 20k macro-flows toward ETRs is far from
Internet-scale, and is in my opinion not useful.  Perhaps I have not
read some more recent work on this topic; but all the LISP-specific
"research" I've seen in this area is nothing more than C.V. padding.

It can easily be shown that an ITR must have a huge FIB, compared to
FIB sizes today, in order to operate normally under a DDoS designed to
exploit the vulnerable negative mapping cache, which must be able to
install same mappings into FIB to guard the control-plane against
excessive punts, or avoid simply dropping punts which would cause
resolution of mappings for positive/good destination mappings.  Again,
see my mailing list post.

> We are all wrong and we are all right. Let's start the technical discussion.

I welcome such discussion.  LISP is very much designed from an
"eyeball" perspective, with the intent of delivering increased traffic
engineering capabilities, and multi-homed connectivity, to SOHO-type
networks with less expensive hardware.  The impact of this is, quite
simply, a shift of cost to the datacenter / content network, or a
shift of complexity to the actual content server, which may, and
probably should, become an ITR itself to avoid scaling problems with
ITRs in mixed-use datacenters.

Making it cheaper and easier to multi-home a SOHO network must
ultimately have the affect of dramatically increasing the number of
such networks which are multi-homed.  Not only is current LISP work
viewing the number of destination networks as substantially fewer than
those which already exist today -- it does not even attempt to account
for this growth.

It certainly does not account for the possibility of DoS designed to
exploit cache churn.  Even without any significant increase in the
number of destination networks today, and if you assumed each ASN had
only one ETR (obviously that will not be true), if LISP were really
deployed widely across the Internet, an ITR would need about 500k FIB
slots to manage just 50k destination networks, given current IPv6
addressing strategy.  An ETR intending to check the origin of traffic
before admitting it to the network will encounter a similar problem.

These problems are obvious.  Improvements can be made, but this has
not been done, and as far as I can tell, it has not been seriously
discussed.  A test network is certainly useful to discover emergent
problems and implementation issues, but from my perspective, feeling a
little proud about having a pilot network deployed while gaping
protocol design problems are not being addressed is a deeply misguided
waste of time and resources.  Scaling problems with ITR caches can be
shown with simple arithmetic -- they do not even require a working
router to discover.

---

From: Dino Farinacci <[email-masked]>
Date: Sun, 10 Jul 2011 21:29:17 -0700

> only person who has showed any interest in this at all, and there has

Oh so you did get a response. You gave the impression you were ignored.

> problem warrants precisely one vague sentence.

Have you looked at the latest draft. We have added more in this area.

> the lessons from the 90s.

An ITR does not maintain a flow-cache.

A LISP cache can get as large as a BGP cache if the site is sending to  
every destination in the Internet. Probabilistically that won't  
happen. But routers do have finite memory so even today the BGP cache  
can exceed the physical capacity of the device.

The problems of the 90s are much different that what is going on  
there. I was there.

With a on-demand cache you can limit who you talk to. With a BGP  
cache, you could do the same thing. There really is no different. Any  
implementor experienced in the art, will tell you the same resources  
are used and the same table management techniques would have to be used.

The size of the LISP cache will usually be less than or equal to a BGP  
cache. When comparing apples to apples it is the same. If you think  
the LISP will have more granular prefixes, say you put host routes in  
it, it will be as large as BGP with host routes.  The reason I am  
going this way is to indicate that any data structure can be abused.

> Internet-scale, and is in my opinion not useful.  Perhaps I have not

Okay, so put 350K in it. What is your point. Give me a technical point  
and not that we didn't make the test large enough.

> FIB sizes today, in order to operate normally under a DDoS designed to

It can be easily shown that it doesn't. And this week it will be  
publicly presented that the FIB cache can be over-subscribed when LISP  
is used.

> see my mailing list post.

Punting will always be a problem until data-planes can create state.  
But it is not a show-stopper.

> ITRs in mixed-use datacenters.

Right. It is time to experiment with state in a few places rather than  
everywhere.

> those which already exist today -- it does not even attempt to account

Yes, but that growth will not affect the core capacity.

> exploit cache churn.  Even without any significant increase in the

With the mapping database, we can push back attacks to the source.  
That has only been tried with source-quench for congestion control.

> slots to manage just 50k destination networks, given current IPv6

I don't know what you mean, but if your definition of a 'destination  
network' is either a single or multi-homed site, then the FIB would  
hold 50K entries.

> before admitting it to the network will encounter a similar problem.

Should a router today check origin before admitting traffic? If not,  
why not? Why does LISP require it where a CPE router today not? And by  
the way those routers as well as routers running LISP to run with uRPF  
configured.

> These problems are obvious.  Improvements can be made, but this has

They are problems but not the end of the world. Why you think they are  
serious I am not sure.

> discussed.  A test network is certainly useful to discover emergent

Have you been to the LISP working group meetings? This has been  
discussed many times.

> shown with simple arithmetic -- they do not even require a working

Then show me the simple arithmetic.

Dino

---

From: Jeff Wheeler <[email-masked]>
Date: Mon, 11 Jul 2011 00:57:19 -0400

On Mon, Jul 11, 2011 at 12:29 AM, Dino Farinacci <[email-masked]> wrote:
> network' is either a single or multi-homed site, then the FIB would hold 50K
> entries.

I am not responding to all of the points raised in your message,
because you are still missing the fundamental problem that negative
replies from the LISP Mapping Service, which should be cached in the
ITR, can cause the table to be inflated to a size that is, literally,
ten times the number of possible positive mapping entries.  Once
again, read my original LISP mailing list post on this subject.

If you read the part in the MS draft that dictates negative replies
must not overlap any possible positive mappings, and consider how RIRs
are currently allocating IPv6 address space to networks, you should
easily realize how this part of the MS protocol needs additional
flexibility.  Quite simply, a 50k entry IPv6 table would indeed
consume 500k entries when negative entries are included.

The simple arithmetic is in my original post, months ago.

---

From: Luigi Iannone <[email-masked]>
Date: Mon, 11 Jul 2011 11:52:21 +0200

> problem warrants precisely one vague sentence.

As co-author of that draft, let me say that we acknowledged the problem and proposed to you to add more wording on it, but you were still unhappy.

As we told you in our email exchange, the threat draft if is just an analysis. It is not the place where LISP specification should be changed. 
Indeed in your original email you refer to draft-ietf-lisp-ms-07, why should we modify the security analysis draft?

We suggested you that if you feel the problem so important to jeopardize any further LISP deployment just  come to  the IETF and discuss with us. What would be very helpful is to focus on the technical part and help in design a solution.

Let's avoid this continuos "LISP is a pet project", "LISP is broken", etc etc....  this is useless discussion. 

> application, came about.

IMHO, you fail to see the real potential of LISP.

>  This is a very obvious problem with a great
> Internet-scale, and is in my opinion not useful.

I am not sure which paper you refer to, but AFAIR there is no paper with 20K "macro-flows".

>  Perhaps I have not

This is just your personal opinion not the truth.  

Luigi

> _______________________________________________
> lisp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/lisp

---

From: Damien Saucez <[email-masked]>
Date: Tue, 12 Jul 2011 10:06:47 +0200

Hello Jeff,

Again thank you for your interest in LISP and please be sure that we are considering your comments
as they merit to be.

In our discussion last week, I proposed to add a discussion about the risk of cache poisoning
with negative replies. The draft with this discussion will be submitted with the other comments that
we will receive during the next IETF. So that, the draft should be presented publicly available
during mid of August. Otherwise, feel free to participate in the effort for securing the mappings (see
draft-saucez-lisp-mapping-security-00) where we are looking to see how to avoid someone to
cheat with the mappings it provides.

However, in our mail exchanges, I said that the cache management was more than a security problem
and was more important than just negative replies. You can inject a lot of entries with positive replies as
well, particularly in IPv6. You can have this by massively de aggregating the prefixes. Again, this is
not a security problem, this feature can lead to security but cache management is first a general problem
in LISP and in Map-and-Encap in general. It thus merit to be discussed in the main specs. However, 
researches have shown that the cache management was not as dramatic as we could expect. Of course
the first study in 2007 was with a mid-size campus network and I could understand that you considered
that the work was not relevant. Nevertheless, the study has been repeated this year with a traffic trace from
an operator (and not a pet-operator, a real one that has millions of customer today) and the conclusion is
the same. So if you still think that our research sucks and is not representative, I would be very happy to get
a traffic trace on your network and do the evaluation. The only limit we have is the time you are ready to wait
for the simulation to complete! Do not hesitate to provide us a 10-year  full packet trace from your network
and we will do all the work for you to see if LISP could be used in your network or if it would become a
catastrophe. 

> again, read my original LISP mailing list post on this subject.

As I am mentioning since a few days now, your are focusing on a small part of the problem. The
real problem is cache management in general. Negative replies are only a very very small part
of the problem.

> consume 500k entries when negative entries are included.

Could you provide more information about the numbers? From where is the 10 factor coming?

> The simple arithmetic is in my original post, months ago.

I think that the problem is more than just simple arithmetic so please provide more details about
how you obtained your results. Sorry I am just a researcher so I do need a lot of details to be able
to understand the things.

Thank you again and please ask for a slot at next IETF to make the discussion growing.

Cheers,

Damien Saucez

---

From: Jeff Wheeler <[email-masked]>
Date: Tue, 12 Jul 2011 04:45:55 -0400

> well, particularly in IPv6. You can have this by massively de aggregating the prefixes. Again, this is

As I have mentioned, a malicious person does not need access to any
LISP infrastructure.  They will not need to inject new prefixes.  All
an attacker must do is send packets in a systemic manner to exploit
the way LISP MS negative replies work -- by sending back
non-overlapping negative responses, which may be more numerous than
the possible number of positive mappings (especially for IPv6.)

> Could you provide more information about the numbers? From where is the 10 factor coming?

Again, you must read my original post on this subject.  An example may
be helpful.  Imagine I wish to attack your ITR, which can learn about
two routes, fc00:9000::/32 and fc00:9200::/32.  There is a large hole
between these two routes, due to RIR allocation strategy.  In order to
use up more MS cache entries on your ITR, I can send one packet each
within the following prefixes, all of which will cause an MS query,
negative response, and use up resources in the ITR:
fc00:9001::/32
fc00:9002::/31
fc00:9004::/30
fc00:9008::/29
fc00:9010::/28
fc00:9020::/27
fc00:9040::/26
fc00:9080::/25
fc00:9100::/24
So you can see that there are two (2) positive mapping entries and
nine (9) negative entries.  Now add a third positive mapping at
fc00:9400::/32 and you gain another nine negative entries.  That
continues to be the case for every possible /32 allocation aligned on
a /23 boundary, thus producing a hole which requires nine VLSM list
entries to be represented.

If you have 50k positive mappings in the system, you will have 450k
negatives making up those holes, requiring a 500k entry state database
on the ITR to avoid churn.  Obviously the goal of such a DoS will be
to exploit either bad behavior during excess churning, cripple the CPU
due to excess punts, or use up all the cache so the correct ETR
destination for legitimate traffic can't be learned.

The reason for this is the Mapping Server is not allowed to send a
negative response which overlaps a possible positive response.  The
hole can't be aggregated into "hole + one longer positive" even though
this would be easy for the router to understand, and indeed, to
install into FIB if necessary (to guard the CPU against punts.)

There will most likely be 50k actual IPv6 destination prefixes within
a few years, if each ASN active today receives about one IPv6
allocation.  If LISP were implemented widely on the Internet, it would
know about 50k mappings and be subject to learning about 450k holes
when abused.  This means the affect of caching is actually that a
bigger FIB is required when the router is subjected to this attack,
than if it wasn't able to cache at all, and simply learned all routes
from the mapping system.

If an ETR wants to be able to verify that ingress traffic is coming
from a legitimate ITR for the source, I believe ETRs will also have a
scaling problem here, which I think will be easier to exploit than the
ITR.

---

From: Darrel Lewis <[email-masked]>
Date: Tue, 12 Jul 2011 05:56:59 -0700

On Jul 12, 2011, at 1:45 AM, Jeff Wheeler wrote:

> non-overlapping negative responses,

Just so I can understand, are you saying that the attack may send unsolicited Map-Replies to an ITR?

Or are you suggesting you send, say, a syn packet with a spoofed source to a host within the site, expecting the resultant syn-ack to result in a map-request sent into the mapping system?

-Darrel

---

From: Jeff Wheeler <[email-masked]>
Date: Tue, 12 Jul 2011 13:42:25 -0400

> Or are you suggesting you send, say, a syn packet with a spoofed source to a host within the site, expecting the resultant syn-ack to result in a map-request sent into the mapping system?

I suggest the second case.  I assume here that the LISP MS
infrastructure itself is not accessible to a malicious attacker.

Whatever way the "bad packets" reach a host downstream of an ITR, if
they generate responses (SYN|ACK, etc.) then the ITR must try to
forward them.  Like you said above, if the ITR doesn't know what to do
with these packets, it is going to try to learn how by punting to the
CPU, initiating a MS query, and so on.

You might say that if LISP can be further developed and deployed, in
an ideal world, there might not be any spoofed traffic.  This would be
nice, except if a LISP ETR has to do a similar look-up when bringing
traffic into the network subject to attack, then the ETR may also
suffer from essentially the same problem as the ITR.

---

From: Ross Callon <[email-masked]>
Date: Wed, 13 Jul 2011 22:55:51 -0400

A comment on one particular point from your email...

> ... However, 
> the same. 

I have read a couple of papers on this issue, which I believe are probably the ones that you are referring to. The papers that I read both assume that the granularity of the EID-to-RLOC tables will be the same as the granularity of the current top level BGP routing table. If this assumption is wrong, then the results will be correspondingly inaccurate. 

To me it seems highly unlikely that this assumption is within an order of magnitude of being correct. 

Ross

---

From: Eliot Lear <[email-masked]>
Date: Thu, 14 Jul 2011 07:41:21 +0200

Ross,

> To me it seems highly unlikely that this assumption is within an order of magnitude of being correct. 

There are now two discussions intermixed in this thread:

1.  What is the projected cache growth rate based on legitimate use?

2.  What are the security considerations regarding cache attacks.

In the first instance, let me suggest that the whole point of LISP is to
disentangle memory consumption from number of reachable points on the
Internet, but rather bound it to the number of sites actually being
reached.  That is what induces the concern that Jeff has raised with the
2nd discussion.  What Jeff has described is a variation of the classic
reflection attack.  This is, IMHO, probably worth noting more
explicitly, as an area for future work.

I do not agree with Jeff that the only approach to solving this problem
is to allow for overlapping negative / positive responses.  That itself
can cause other problems.  For instance, it causes confusion as to when
in fact a query must be sent if a negative entry is already cached, but
there exists a positive entry somewhere in the world.  In any case, I
suggest we add a line that states the risk but not attempt to solve it
in this round of the experiment.

Eliot

---

From: Damien Saucez <[email-masked]>
Date: Thu, 14 Jul 2011 07:20:56 +0200

Hello Jeff,

I thought  about the problem and think that there is deployment solution that
could correct the problem. Here I am supposing that the mappings are
secured (which is a must for me as u can see from my drafts). Of course it
would work without secure mapping but then it would be dangerous (see
LISP-SEC Fabio's draft).

Currently, when a map-request is sent, you receive the mapping for the
longest-match prefix corresponding. So why not changing to receive a
Map-Reply that contains as today the reply to the request + the a
negative-mapping with the longest-match prefix of the RIR that contains
this. The RIR knows how it assigns the prefixes, so it is easy to provide this.
In your example, you just have to send fc00:9000::/32 positive mappings
and the corresponding negative /23 with a TTL lasting the time the
RIR is subject to assign a new sub-prefix of this /23. There is plenty of
solutions to ensure this mechanism (MS bases, mapping system bases,
ETR based), I will not propose them here, but I am open to start a draft
with you that present the issue and the solution. Or you can ask for a
slot @IETF81 to present the problem and I would also ask for a slot with
the solution.

Thank you,

Damien Saucez

---

From: Damien Saucez <[email-masked]>
Date: Thu, 14 Jul 2011 09:32:22 +0200

Eliot,

> in this round of the experiment.

You are right but I think this problem can be solved with the ACT bit with the
value 0x02 and overlapping mappings. Indeed, the assigned prefixes are
known for sure and the "holes" do not change too frequently. So the result of
a request in a hole could be the large "holed" prefix with a TTL that corresponds
to the time before which no hole will be assigned (depends on the policy of prefix
assignments but I think it should be not less than one day), this is a negative reply
with the ACT bits = 0x0. And all the aggregated prefixes that have been
assigned in this prefix in a negative reply form with the ACT bit = 0x2 meaning that
the ITR must send a map-request before trying to encapsulate the packets in such
sub-prefixes.

For example, if you have 192.0.2.0/24 and only 192.0.2.0/30 and 192.0.2.128/30
that are assigned, the reply for let say 192.0.2.13 could be

192.0.2.0/24, negative, ACT=0x0, TTL= 1day
192.0.2.0/30, negative, ACT=0x2, TTL=min lease time
192.0.2.128/30, negative, ACT=0x2, TTL=min lease time

where min lease time is the minimum time a prefix in the aggregate of sub-prefix
is assigned to the company. For example, if the prefix 192.0.2.0/30 is assigned on
a year basis, its TTL can safely be 1 year as it has the ACT=0x2 meaning that the
ITR will request for mappings corresponding to addresses in this prefix on demand.

Damien Saucez

---

From: Damien Saucez <[email-masked]>
Date: Thu, 14 Jul 2011 10:03:45 +0200

Ross,

> To me it seems highly unlikely that this assumption is within an order of magnitude of being correct. 

At a first glance, the assumption might look bad, but I believe it is not the case. Indeed, the evaluation are made
with real BGP feeds to determine the number of prefixes. However, this morning I look my FIB and saw 52% of /24,
the rest being less specific than that. So know imagine that the whole Internet become de-agregated, it means that
we would have 100% of /24 thus in the very worst case, we would double the number of required entries which
remains acceptable. Would you allow prefixes more specific than /24 in EID? In addition, many of the prefixes we
are seeing on the Internet are just there because of the incoming TE limitations of BGP (e..g, de-agregation,
aspath pre-pending, blah blah) but with mappings you do not need these artifacts and because you have the
list of locators and the weight you can even do less specific than /24 with the same result (with better end-to-end
control) and at the end one can expect to have the mapping churn lower than the current BGP churn.
Another point in favor of this decomposition is that people would probably not be happy to renumber their network
and then simply migrate their PI addresses into EIDs. Thus, the current prefix would appear as LISP EID prefixes.
So all-in-all, the numbers obtained in the different papers are not so dumb if we assume that LISP is deployed in
a smart way by people that know how it works (unfortunately it is not always the case with BGP and we can see
absurd announcements everyday), that no configuration mistake are performed (which can be enforced if we
ensure security in the mappings and appropriate mapping system, but this is another story) and if we limit the 
max-deaggregation into /24 for IPv4. In IPv6 I would not announce anything as it is still blurry how IPv6 BGP will
really look like (do we really conserve the aggregation we have today?).

Does it go in favor of these studies or not? If not, could you discuss with us off-list to design a worst case scenario
that we can study to see how the ITRs would behave?

Thank you for the feedback,

Damien Saucez

---

From: Jeff Wheeler <[email-masked]>
Date: Fri, 15 Jul 2011 18:11:48 -0400

> At a first glance, the assumption might look bad, but I believe it is not the case. Indeed, the evaluation are made

You forget that a feature of LISP is to make multi-homing SOHO sites
cheaper and easier, therefore increasing their number dramatically.
If I can multi-home using LISP with my cable modem and my DSL, I will.
 Many "power users" will at their homes, to say nothing of branch
offices and small businesses, which today do not warrant multiple,
expensive ISP connections that offer speed, economy, and the
capability for multi-homing.  To assume the number of multi-homed
end-sites won't grow by 10x is foolish.  I believe we would see more
than 100x growth, but even 10x, plus the cache problems identified,
make LISP very much impractical for content providers.

On Thu, Jul 14, 2011 at 1:55 AM, Damien Saucez
<[email-masked]> wrote:
> With "simple arithmetic", BGP cannot work, however, it works in practice because
> theory and practice are not the same. LISP is not perfect, and none of the protocols

360k prefixes, 360k FIB slots.  Yes, if you have a flow-based BGP
router in the DFZ, depending on its implementation, it may work poorly
(Foundry IronCore, for example) and it may be trivial to disable with
DoS traffic.

However, LISP proposes to create a situation where the ITR should
never know all mappings, must be able to hold negative replies from
the MS, and thus increases the amount of FIB required (in worst case,
which is real-world for content networks, they do receive DoS and have
to deal with it) beyond the maximum number of possible mappings.  As I
have shown, this is problematic even if the number of mappings
wouldn't explode due to SOHO multi-homing.

> this. The RIR knows how it assigns the prefixes, so it is easy to provide this.

Your idea is similar to my proposed fix and would reduce the "waste"
caused by negative mappings.  I don't agree that it is savvy to make
the reply necessarily based on RIR assignment strategy (one can
imagine many reasons where this may not be ideal) but think the router
should be able to request what portion of the possible routing table
it wants.  Flexibility in the protocol specification, so vendors can
implement what they choose, would be beneficial.

> explicitly, as an area for future work.

I encourage you to also keep in mind that, if an ETR should be able to
verify that an ITR is a legitimate origin point for traffic sourced
from a given address, ETRs will also be subject to the same cache
problems.  Except the ETR will be worse / more vulnerable, because you
don't need any packet reflection to exploit it.  I understand that the
ideas for possibly preventing spoofing of packets are not well evolved
yet, but they must take this into account.  You are not even able to
do loose uRPF checking on the inner-source-address of incoming packets
without exposing the ETR to trivial DoS.

On Thu, Jul 14, 2011 at 1:55 AM, Damien Saucez
<[email-masked]> wrote:
> LISP is definitely more than just a new way of doing VPNs. I am really sorry if
> you cannot see the fundamentals changes that a Map-and-Encap paradigm
> brings to the way networks are managed. LISP is just an instantiation of this

I simply see that a hard, underlying problem has not been addressed.
Touting the potential for LISP to bring new capabilities, on
Internet-scale, without having considered the implications of
Internet-scale DDoS, is either ignorant or irresponsible.

---

From: "Damien Saucez" <[email-masked]>
Date: Sat, 16 Jul 2011 16:17:10 +0200

Dear Jeff,

>> At a first glance, the assumption might look bad, but I believe it is
>> not the case. Indeed, the evaluation are made
>

Actually, the very nature of Internet traffic make this a non-problem.
Indeed, the heavy tail nature of the spacial locality distribution in the
Internet ensures that, in general, only the big networks will have to deal
with a huge number of client. And if your network is big, it is very
likely that it will have many entry points and that these entry point are
topologically close to the clients meaning that each entry point will
actually not have to deal with millions of clients. Don't forget that you
have to think in term of locality with LISP. If you don't you will kill
the paradigm. Not because it is bad but because your interepretation is
incorrect. LISP is not BGP! So if you don't believe me about how the
traffic is on the Internet, I think you can believe the harbor study (data
from hexabytes of traffic in real networks). What does the study show?
Simply that the traffic converges to a few buch of CDNs (actually the
study shows much more than that, but only this point is important for
now). So yes you will see a lot of SOHOs but only the big CDNs will have
to deal with an important amount of entries, not the other networks and
for the CDN, believe me or not, but the routers they are using will be
able to deal with even millions of mappings (which is unlikelly as the
load is spread over several routers). Actually, a SOHO has in general a
xTR (ITR and ETR merged) and the traffic is relativerly symetric in term
destinations/sources (not volume but we don't care for the cache) as
basically flows are bi-directional. In addition, the SOHO tend to
communicate with CDNs not with other SOHOs. Feel free to provide me data
that prove the opposite.

> (Foundry IronCore, for example) and it may be trivial to disable with

Pointless remark. It is trivial that if you are not doing a good
implementation your router will blow out. We are obviously considering
that state of the art techniques will be used by the guys in charge of
implementing LISP!

> to deal with it)

see above...

> beyond the maximum number of possible mappings.  As I

And I showed that it was not a so big problem if you are deploying the
system in a smart way.

> implement what they choose, would be beneficial.

RIR was an example, please be constructive in your remarks.
> without exposing the ETR to trivial DoS.

Jeff,  please, before shouting everywhere that we are dumb, read ALL the
documents related to LISP. In the draft about security threats we explain
that ETR should make sanity checks to protect against spoofing. We even
present different type of spoofing and ways to protect the routers. And in
a paper in Networking'11 the authors show that in a (real!) network,
activating such sanity check at the ETRs is not an issue and the caches do
not blow out.

Again if you have data to give us to proof your thoughts, feel free to
provide me them and I will work on them to see if we really are as stupid
as you pretend. I would be the first happy to show a negative result, my
work is not to provide positive of negative results but simply to provide
facts.

> Internet-scale DDoS, is either ignorant or irresponsible.

Since we never heard about you before a few weeks, I think that you just
discovered LISP. On my side, I started working on LISP in '07 and since
then I consider the security implications with LISP. We have internal
documents that explore the different ways to secure the mappings and to
avoid spoofing and we are still studying what is the best OPERATIONAL vs
REALISTIC solution. I am also the author and co-author of several IETF
drafts and scientific papers about the LISP security and the impact of
scans on LISP. You are probably not aware of that but a draft becomes a WG
document if and only if the majority of people in the WG consider that it
is worth working on it (many of my drafts have been dropped, this is the
life of an IETF draft). As several WG drafts are about security in the
LISP WG, it means that a majority of the people working in the LISP WG
consider that security is worth working on.

Could you please provide arguments and proofs of what you claim and try
also to know the LISP state of the art to be sure that it is not already
done? If you do not provide more argumented discussion, I will have to
stop answering your mails.

Thank you for you interest in LISP

Regards,

Damien Saucez

---

From: Robert Raszuk <[email-masked]>
Date: Sat, 16 Jul 2011 20:14:14 +0200

Hi Damien,

> now).

I am a bit puzzled by your above points. You seems to be making a future 
claims based on historical observations statistically averaged with 
time. I am afraid the point Jeff is making is not about any average .. 
it's about a peak.

I think any solution by design must consider that even if I am a very 
small home site my xTRs must be able to deal with millions of clients .. 
as this is not query, but replies which will go into millions of 
Internet destinations the moment google indexes some very popular 
content on my web server. Just consider the case where I am multi-homed 
and my web queries are coming over different ETR then my replies are 
taking ITR.

Many thx,
R.

---

From: Jeff Wheeler <[email-masked]>
Date: Sun, 17 Jul 2011 04:37:47 -0400

> Actually, the very nature of Internet traffic make this a non-problem.

This is incorrect, because *any* content network, and any subscriber
access platform, must be able to deal with the threat of DoS attacks.
If you re-design the Internet in such a way that it becomes trivial to
disable any service or any end-user with a relatively small DoS, and
that is the direct impact of LISP on a large scale, then every network
which wishes to avoid being subject to regular outages must build the
large xTR infrastructure you say a few CDNs will build.

DoS attacks > 10Gbps are so common today, they do not even attract
attention.  This can be handled by today's networks simply by having
enough capacity, but without xTR infrastructure able to support all
possible mappings in FIB without a need for cache, DoS attacks in a
scaled-out LISP future would be measured by flow-churn rate.

A router that can do > 15M FIB updates/second does not exist, and in
fact, FIB update rates would have to go up by three orders of
magnitude to handle a worst-case scenario where the cache hit rate is
near zero.  If you scale up the number of prefixes / end-sites from
360k to 36M, as I suggest is likely if SOHO multi-homing becomes
trivial for the end-sites, even routers with large FIB by today's
standards will have quite low cache hit rate when subject to DoS (or
simply a large amount of end-user traffic.)

The folks who often quip that vendors can easily increase the size of
FIB to deal with the increasing BGP DFZ generally mean vendors can
easily and inexpensively double the FIB.  They certainly cannot grow
it by 100x on today's IC fabrication processes.

If you assume most of the Internet is only having to deal with a few
tens of thousands of flows and a high cache hit rate, it is easy to
imagine that LISP is a wonderful idea.  These assumptions completely
break down when faced with the reality of DoS, and get far worse when
the number of end-sites scales up.  You continue to ignore both of
these problems, which are directly related to the fact that LISP has
not addressed the fundamental issue of an increasing number of
end-sites.

> that state of the art techniques will be used by the guys in charge of

LISP has not advanced the state of the art in flow cache management.
It has not produced a way of reducing the ultimate number of
end-sites, either; and in fact should increase them significantly if
LISP is successful.

> RIR was an example, please be constructive in your remarks.

If you don't think the above paragraph is constructive, then you have
closed yourself to feedback.  This exemplifies the problem operators
perceive with "the IETF."  Perhaps I should have said:
* more negative cache optimization is possible if not limiting that to
RIR assignment strategy
* RIR assignment strategy may chance and require implementation
updates (at worst) or configuration changes that may not be performed
by operators: see problems getting new RIR IP blocks "de-bogoned" over
the past few years
* not all platforms need these complexities, for example, the SOHO xTR
with a relatively low-speed connection that cannot be subject to a
high flow churn rate, or is implemented on a general-purpose computing
platform e.g. x86

> activating such sanity check at the ETRs is not an issue and the caches do

Yes, the caches do blow out, due to the same problem with DoS
reflecting out an ITR.  The difference here is the act of attempting
to verify source address (or even do loose uRPF) "blows out" the ETR
cache, and there is no possibility to defend against it.

Your analyses of "real" traffic are not based in reality without the
inclusion of Internet-scale DDoS.  In addition, they are further made
worse because your group has not envisioned the "worst case LISP DoS"
that specifically exploits cache vulnerabilities.  These types of
attack will not be represented by your analyses because of two
reasons:
* no LISP deployments yet and thus no real-world attacks against it
yet, but they will come in the future if LISP ever becomes
widely-deployed
* no huge increase in the number of end-sites due to SOHO
multi-homing, because that is not currently practical, but LISP
promises to make it practical

> Again if you have data to give us to proof your thoughts, feel free to

You need to stop relying on traffic captures.  Of course you won't see
DoS specifically designed to exploit a vulnerability that does not
exist in today's networks, but will with LISP deployed.  And if you
simply assume that only a few ultra-large CDNs will need to handle
millions of flows, and all other sites are trivial, you are assuming
that no other sites will ever see millions of flows due to DoS.  That
is wrong.

> discovered LISP. On my side, I started working on LISP in '07 and since

I have been aware of LISP development for many years.  I only took
more interest in it recently, when a colleague told me what great
progress had been made.  I examined the current work in more detail,
and found that the same fundamental problems which existed years ago
are still here.  The reason why is simple: your group has a great deal
of vision about how a future LISP-based Internet could function, but
you continually fail to consider the negative effects of DoS, and you
do not have a basic understanding of how the data-plane actually
works, which is necessary to envision how the xTR will perform when
subject to such DoS.

The reason I care is because IPv6 gave us an identical problem on a
more limited scope, by setting the expectation that LANs (or all
networks) should be /64.  Unfortunately, a parallel problem exists
with IPv6 ND cache exploits when deploying /64 networks in the real
world.  It is possible to fix this (SeND, more router/switch knobs,
etc.) and it is possible to simply deploy networks differently to
avoid the problem.  However, with LISP, the problem is of global scope
and it may not be possible to fix if LISP scales up.

> stop answering your mails.

How do you expect an ETR to validate the origin of packets when
subject to an attack designed to cause mapping churn?  Imagine that
you have an Internet-scale LISP network, with perhaps 3M or 30M
end-sites and possible mappings, and I am sending you 15Mpps of
packets which all appear to originate from different end-sites.  No
router today will be able to mange this in FIB, so cache churn will
result.

Now reduce the size of that attack from 15Mpps (trivial today) to an
even smaller 200Kpps.  This is still 10x faster than modern routers
can handle FIB churn, at a rate of around 20K updates/second.  How
will the ETR be able to validate source addresses under this tiny
assault, which may originate from literally one co-located server with
a GbE connection, without even fully utilizing such connection?  The
answer is it cannot.

Not only can the ETR not validate source addresses, it can't even
discard packets which originate from impossible source addresses
(loose uRPF check) because it is not able to determine whether or not
these source addresses are even present in the mapping system quickly
enough.

That is the state-of-the-art today.

---

From: Damien Saucez <[email-masked]>
Date: Mon, 18 Jul 2011 09:57:39 +0200

Robert,
On 16 Jul 2011, at 20:14, Robert Raszuk wrote:

> I am a bit puzzled by your above points. You seems to be making a future claims based on historical observations statistically averaged with time. I am afraid the point Jeff is making is not about any average .. it's about a peak.
> 

You are partially right as in the different studies, the cache load is considered
on average, in general 1 minute. However the averaging periods are shorter
than the TTL/timers used for the caches so the instantaneous size of the cache
would not change dramatically (probably a 1 or 2 % increase). What could
change more is the "churn" (i.e., the instantaneous cache size change) as we
are smoothing the curves thus lowering the derivative of the underlying cache
size function.

So for the studied networks, the cache sizes obtained are very close to the
reality (under our EID prefix attribution assumptions of course).

> I think any solution by design must consider that even if I am a very small home site my xTRs must be able to deal with millions of clients .. as this is not query, but replies which will go into millions of Internet destinations the moment google indexes some very popular content on my web server. Just consider the case where I am multi-homed and my web queries are coming over different ETR then my replies are taking ITR.

I am not sure I understand perfectly what you mean. Why should a small home
site would have millions of destinations? It would mean that you observe at least
millions of flows within your small network. Even in campus networks like our
university we do not observe millions of concurrent flows. In one day we have in
general 3 million different IP addresses in our network and there is no mechanism
to limit the traffic but more interestingly, during 5 minute periods, we observe
peaks at around 60K to 70K concurrent destination addresses and  peaks to 1.2M
L3 flows and interestingly, from 5min time slots to 5min time
slots, we can see big variations (having 60K destination then 20K then
40K ... is common) maning that actually the ground traffic that would stay in the
cache for what ever TTL is not so important. Indeed, a top few (~ thousands)
destinations are contacted all the time, while the rest could be seen as noise
with short period of time (from a few seconds to a few hours). So a good cache
eviction algorithm should solve most of the case. Regarding the cache size, I
think that the mistake is in the specs, where it is recommended to have a TTL
of one day.  From the temporal locality of Internet traffic, we can say that this
choice is meaningless. xTR should be able to fix themselves the TTL of the
mappings they install in their cache (TTL_cache <= TTL_Map-Reply).

Nevertheless, it is true that a site like google may have to deal with millions of
mappings while indexing. I do not know how google work for indexing, but I presume
that this million of pages are not indexed in one minute by a single machine. 
Probably that the indexing takes several hours (days?) and is from different machines
with load balancers. Probably that the indexing of a site takes at much a few tens of
minutes, the ITR could thus limit the TTL to that amount of time. In addition, if 
load balancers are actually used, one could imagine to use these LB directly as
xTRs.

Another case where you can observe peaks of destinations is with mails, if your
server is attacked and becomes a relay for spams, it can potentially have to
contact a huge number of destinations. It is a problem, but I think that the problem
is not LISP but the way the server is managed.

But you and Jeff are right that LISP has a big problem in case of sort of flash crowds.
The question is to know what will die first, the cache or the services that are
flash crowded. Such peaks can also be done with DDoS and this is why we are
working on techniques to avoid spoofing with LISP. And yes, we have to be
honest we do not have the perfect solution now for this problem.

Thank you,

Damien Saucez

---

From: Robert Raszuk <[email-masked]>
Date: Mon, 18 Jul 2011 10:12:43 +0200

Hi Damien,

Many thx for your reply.

Let me clarify ...

> millions of flows within your small network.

Yes. Imagine if you or me announce wiki-leaks-2 content on our IPv4/IPv6 
home web server. I think number of flows will explode. And imagine we 
are lucky users of FTTH so no bandwith issue :)

Moreover those may not be DOS or spoofing. Those may be legitimate 
addresses. And I do not think the server will die.

And I am not saying LISP will or will not be able to handle it. I am 
just asking how it will handle it ;) Maybe the answer is to in the 
moment of exceeding capacity threshold of any xTR push some of the 
traffic to few bigger proxies ... just a thought.

Cheers,
R.

Even in campus networks like our
> mappings they install in their cache (TTL_cache<= TTL_Map-Reply).
>

---

From: Luigi Iannone <[email-masked]>
Date: Mon, 18 Jul 2011 12:33:42 +0200

On Jul 17, 2011, at 10:37 , Jeff Wheeler wrote:

[snip]
> inclusion of Internet-scale DDoS.  

Simply because was out of the scope of that work. 
This does not reduce in any way the value of the work itself. 
The work makes clear assumptions that well define the scope of the results.

Luigi

---

From: Damien Saucez <[email-masked]>
Date: Mon, 18 Jul 2011 14:46:53 +0200

Hello,
On 18 Jul 2011, at 10:12, Robert Raszuk wrote:

> Yes. Imagine if you or me announce wiki-leaks-2 content on our IPv4/IPv6 home web server. I think number of flows will explode. And imagine we are lucky users of FTTH so no bandwith issue :)
> 
> Moreover those may not be DOS or spoofing. Those may be legitimate addresses. And I do not think the server will die.
> 
> And I am not saying LISP will or will not be able to handle it. I am just asking how it will handle it ;) Maybe the answer is to in the moment of exceeding capacity threshold of any xTR push some of the traffic to few bigger proxies ... just a thought.
> 

Thank you for the clarification, this is a nice example indeed!

You are right that for such legitimate traffic there is problem as it can be
assimilated to a flash crowd. In you particular example, I think
that it is the Map-Resolver or the control plane itself that will cause the
problems!

If we consider  the cache size it should be ok. If we have
one million client *simultaneously* and that the system is stupid and
stores the mapping records as-is, that all the requesters are IPv4 and
have two rlocs, then 40MB of storage is required. It is especially what
the small home routers have today, but it is not 1million times more
than the memory they provide now, so it would not be too hard.

But the control-plane in these routers would suffer and these boxes
are in general pure software and have slow processors so I don't know
if they will enjoy to update the cache at a rate higher than a few hundreds
entries per second. To be honest I don't know what could be achieved by
such devices. And even if they are able to deal with this speed, it will maybe
be complicated for the boxes to find a MR that will not rate limit the number
of requests.

So this goes in the direction of Jeff saying that the churn problem should
not be neglected.

Thank you,

Damien Saucez

---

From: Robert Raszuk <[email-masked]>
Date: Mon, 18 Jul 2011 15:03:56 +0200

Hi Damien,

 > So this goes in the direction of Jeff saying that the churn problem
 > should not be neglected.

Very much indeed.

And to save one more email from Luigi .. I do not buy the argument that 
this is simply "out of scope" as this would really mean "out of 
practical reality".

Cheers,
R.

---

From: Luigi Iannone <[email-masked]>
Date: Mon, 18 Jul 2011 15:16:47 +0200

On Jul 18, 2011, at 15:03 , Robert Raszuk wrote:

> And to save one more email from Luigi .. I do not buy the argument that this is simply "out of scope" as this would really mean "out of practical reality".

Too late..  ;-)

May be I was unclear. What I wanted to say is that this was out of scope of the papers that were cited in the thread. 

I was not saying that such kind of work is "out of scope" in a general way. 
Rather the contrary, I truly think that security issues need to be explored, understood, solved.

ciao

Luigi

---

From: Robert Raszuk <[email-masked]>
Date: Mon, 18 Jul 2011 15:20:54 +0200

Hi Luigi,

>>> So this goes in the direction of Jeff saying that the churn
>>> problem should not be neglected.
>>
>> Very much indeed.
>>
>> And to save one more email from Luigi .. I do not buy the argument
>> that this is simply "out of scope" as this would really mean "out
>> of practical reality".
>
> Too late..  ;-)

;-)

> May be I was unclear. What I wanted to say is that this was out of
> scope of the papers that were cited in the thread.

Ahh ok - it was not clear. Of course it makes sense to divide the work 
into chunks.

> I truly think that security issues need to be explored, understood,
 > solved.

But for me this is not really a security issue, but scaling issue of 
possible production legitimate use rather then any form of attack.

Cheers,
r.

---

From: Damien Saucez <[email-masked]>
Date: Mon, 18 Jul 2011 15:33:53 +0200

> And to save one more email from Luigi .. I do not buy the argument that this is simply "out of scope" as this would really mean "out of practical reality".

Definitely, the scalability problem is a major issue in LISP if we do not
do the things correctly. The first part of the scalability work was to see if
LISP data-plane could work in the current situation (cache papers). The
second  part was to see if the control-plane (mapping system) could work
in such situation (we started with LISP-Tree and are still working to see how
to ensure the control-plane scalability). As it seems that LISP could work
in the current Internet (with the assumption we made), we have to explore
the potential new deployment cases of LISP (i.e., corse vs fine grained
mapping decomposition, where to put the xTRs...). Then for the deployments,
see how to model the traffic to check if data-plane and control-plane can
resist. And finally consider that malicious people could attack LISP itself
to success attacks. We are still evaluating how to have "new LISP 
deployment pattern" and have started to lisp the intrinsic security flows
in LISP. So we will eventually be able to see how LISP would react to
new deployments with the presence of LISP based security threats. We are
still far from being able to answer, but at least we show that under certain
given assumptions LISP could be used and work. With baby steps we are
going to more complex cases, but I prefer to have a system that works but
must be optimized that an optimal system that does not work.

So definitely scalability and security are key points for LISP.

Thank you,

Damien Saucez

---

From: Damien Saucez <[email-masked]>
Date: Mon, 18 Jul 2011 15:36:20 +0200

Robert,
On 18 Jul 2011, at 15:20, Robert Raszuk wrote:

> Ahh ok - it was not clear. Of course it makes sense to divide the work into chunks.
> 
> But for me this is not really a security issue, but scaling issue of possible production legitimate use rather then any form of attack.
> 

definitely, this was our very first answer to Jeff when he raised us the problem. Jeff
said "DoS", we said "cache management". And your example is perfect to show
this where legitimate traffic has the same effect than an attack.

Thx,

Damien Saucez

---

From: Dino Farinacci <[email-masked]>
Date: Tue, 19 Jul 2011 01:13:48 -0700

> traffic to few bigger proxies ... just a thought.

Our LISP-MN implementation right now stores a single map-cache entry  
to a re-encapsulating LISP router. So just like you have a default  
route in a home router, you can have a default map-cache entry. And  
the data plane stretch can be the same if the re-encapsulating router  
is in the PE router provisioned with a product that has larger FIB  
capacity.

And if that PE router is a PITR connected to the ALT, it knows right  
away if the destination is a LISP site or a non-LISP site. When the  
destination is a non-LISP site, it forwards packet in hardware because  
it has a FIB route (via BGP), and when the destination is a LISP site,  
it can send a Map-Request and build the map-cache.

So the DOS attack on non-LISP sites is mitigated because BGP is in use  
and is no worse than today. A DOS attack on LISP sites can be bounded  
by the size of each EID-prefix. Not perfect, but that is what we have  
so far.

Dino