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

From: Luigi Iannone <[email-masked]>
Date: Mon, 11 Jul 2011 12:01:22 +0200

Jeff,

from your original post.

On Apr 28, 2011, at 07:31 , Jeff Wheeler wrote:

> Dear List,
> 
> I've had several off-list discussions with some vendor folks, and
> otherwise, working hard on LISP.  I see that the issue of cache
> thrashing is currently left entirely up to the implementor to handle.
> I may be unaware of some body of work on this topic, however, I
> believe the current language in draft-ietf-lisp-ms-07, below,
> eliminates a needed means of reducing negative mapping cache size on
> an ITR.
> 
> From section 4.4 Map-Resolver Processing:
> To minimize the number of negative cache entries needed by an ITR, the
> Map-Resolver should return the least-specific prefix which both
> matches the original query and does not match any EID-prefix known to
> exist in the LISP-capable infrastructure.
> 
> This is a good approach in most circumstances, where there are few
> packets to unknown destinations (few "punts" to the control-plane.)
> It breaks down, however, in the event the ITR needs to process a large
> amount of packets to unknown destinations, such as:
> * a deliberate DoS attack on the ITR from within
> * reply packets to an external DoS attack with false, random source addresses
> * a malicious worm searching for hosts to infect
> * etc.
> 
> All of the above contribute to FIB churn.  They may also cause a large
> number of negative mapping cache entries to be populated on the ITR.
> To demonstrate how the mechanism in draft-ietf-lisp-ms-07 is not ideal
> in this situation, all you must do is emulate the existing IPv6
> routing table, which contains numerous, costly-to-express holes.  For
> example, current ARIN IPv6 allocations to ISPs are /32 in size but are
> aligned on /23 boundaries.  These holes between "adjacent" (minus
> holes) /32 ISP allocations allow a malicious person to cause an ITR to
> learn nine (9) negative mapping cache entries between each two /32
> allocations, if one was utilizing LISP on Internet-scale, and LISP
> were widely-deployed.
> 

Can you provide real numbers instead of just example? Have you ever counted the holes?

Isn't possible to avoid this by filtering? The ITR can avoid sending any request for IPv6 unallocated space. 

Luigi

> The draft language does not leave room for alternatives, but it
> probably should.  A different mechanism works better in this
> situation, allowing the ITR to learn about all feasible prefix
> mappings within a given supernet.  This may allow the ITR to reduce
> its number of negative cache entries dramatically by installing a far
> smaller number of positive mappings (to control-plane cache for
> possible use, or to FIB.)
> 
> This is of more importance than is immediately obvious, because one
> must consider the cost of "punts" to the control-plane in order to
> drive the learning process.  These punts must be policed somehow, and
> surely, they will be by vendor implementations with a "hardware FIB"
> and a "software negative cache."  However, when faced with a large
> volume of punts (packets to unknown destinations, causing a negative
> cache hit or a new Mapping Service inquiry), an implementation might
> choose to actually install negative mappings into his FIB, preventing
> these known-bad punts from reaching the control-plane *and* preventing
> them from contenting for policer conformance with other punts which
> are needed to learn new mappings for legitimate traffic.  This means
> the cost of pushing some negative cache entries into the FIB should be
> considered, and the cost of doing so should be able to be minimized by
> the implementation.
> 
> I suggest the Mapping Service specification leave room for an ITR that
> wishes to request all mappings within a given subset of the feasible
> routing table.  This gives the implementor additional options for
> dealing with malicious traffic which may drive its negative mapping
> cache to a large size, and perhaps consume precious FIB resources as
> well.
> 
> Darrel Lewis tells me there was a similar capability in a router with
> "on-demand FIB compression."  While the application differs in this
> case, the principle is the same.
> 
> -- 
> Jeff S Wheeler <[email-masked]>
> Sr Network Operator  /  Innovative Network Concepts
> _______________________________________________
> lisp mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/lisp

---

From: Jeff Wheeler <[email-masked]>
Date: Mon, 11 Jul 2011 15:25:27 -0400

> Can you provide real numbers instead of just example? Have you ever counted the holes?

Luigi, the holes in the IPv6 space are there due to RIR allocation
strategy.  If I am an ISP and request a /32 for my customers, they
will give me a /32 aligned to a /23 boundary, and not allocate any
other blocks out of that /23 (at least not yet) in case I need to grow
my address space.  This is what produces the holes that are guaranteed
to allow attacking the vulnerable negative mapping cache, if LISP were
widely-deployed on the Internet.  So you can see that it is not just a
hypothetical "what if the address space had lots of holes..." problem,
but a practical "there are lots of holes and LISP will perform badly
due to this as it scales up."

> Isn't possible to avoid this by filtering? The ITR can avoid sending any request for IPv6 unallocated space.

You must understand how routers work to see why this is possible, but
requires 10x more FIB space than the number of possible positive
mapping entries (for the case of IPv6, given current allocation
strategy.)

How does the ITR learn about a mapping for a newly-arrived
packet/flow?  Packets bound for a yet-unknown destination must be
punted from the data-plane to the control-plane, where the router's
CPU can check its potentially larger mapping cache (if control-plane
cache is larger than FIB.)  This punting is itself the problem.  In
order to filter punts for unallocated space, you must install
something into the data-plane / FIB to match them -- this means you
can either install all positive mappings, or you can load negative
mappings on-demand, or you can not filter them at all and punt garbage
look-ups to the CPU.

There is no easy way to "avoid sending any request for unallocated
space" at a granular level that would protect the CPU in an
Internet-scale LISP deployment.  Simply increasing the size of the
control-plane cache, and not turning the punts into MS queries, is not
enough.  The MS will be able to service a very high rate of requests
and is fairly easy and inexpensive to scale up.  The problem is the
router CPU cannot receive an infinite number of punts before failing,
and the data-plane cannot churn its FIB at an infinite rate either.
On modern routers, the limit of these functions is on the order of
20,000 punts or FIB updates per second.

This is why it would be trivial to disable an ITR, because the
filtering you suggest is not possible without a huge FIB, defeating
the purpose of using a cache at all.

I believe the only way for LISP to scale up in a dense, mixed-use
data-center environment, where the hosts may be untrustworthy, is for
the hosts themselves to be their own ITR.  However, modifying the
mapping service spec to allow for a different way of handling negative
responses can significantly improve the situation, to the point where
the ITR only needs enough FIB to hold approximately the whole possible
routing table, not 10x more entries due to negative "filter" entries
as you suggest.

If you do not consider how the ITR actually works, and this seems to
be the case with a lot of the work on LISP today, it is easy to focus
your efforts on interactions within the LISP signalling infrastructure
without ever realizing that the data-plane has vulnerabilities.

---

From: Luigi Iannone <[email-masked]>
Date: Tue, 12 Jul 2011 09:45:00 +0200

Jeff,

what you are describing is nothing new and is not limited to LISP. Hence I do not understand the alarmist tone of your emails.

If you want to propose text describing the issue for the next version of the threats draft, I will be happy to include it. (please do not include any solution since it is not the place to document it. Please be concise.)

Thanks

Luigi