Subject: [Ila] Securing pull-based ID/LOC caches

From: Albert Cabellos <[email-masked]>
Date: Thu, 22 Mar 2018 16:13:57 +0000

Hi all

I am attaching a short paper describing a solution for control-plane
denial-of-service & overflowing attacks against pull-based ID/LOC caches.
The solution is based on implementing a per-source rate-limiter at the xTR
using an efficient Count-Min Sketch structure.

Albert

---

From: Tom Herbert <[email-masked]>
Date: Fri, 23 Mar 2018 04:46:27 -0700

> using an efficient Count-Min Sketch structure.
Hi Albert,

Thank you for forwarding the paper. It is an interesting read!

I have a few comments:

>From the paper: "In LISP the mapping from the overlay namespaces can
be done using two mechanisms."

I believe a third mechanism is exists in secure redirects. This is
akin to ICMP redirects where a network router informs a sender that
there is a better path. This is sort of a hybrid of the pull and push
models.

>From the paper: "It is worth noting that this solution assumes that
spoofing source addresses is not possible inside the LISP site". That
is a big assumption and I'm not sure it will be generally true.

Even if if spoofing is enabled, trying to identify bad guys by source
address is still precarious. Consider that there could be complex
downstream networks of LISP that are possibly behind NAT, delegated
prefixes, VMs sharing common server IP address, etc.

You might also want to consider the possibility of a distributed
denial of service attack where the attacker uses many system to attack
a cache where no individual systems sends a high enough rate of
packets to trip the rate limiting threshold. I imagine the code for an
attack on cache is pretty trivial-- little more than a simple loop
sending UDP packets to random destinations. This could very easily be
hidden in some downloaded app.

>From the paper: "Attackers generate (randomly) between 2 and 3 orders
of magnitude more control-plane messages than legitimate users.
Specifically, attackers generate a uniform random number in the range
of 1k-10k, legitimate users a range in 1-10 and the threshold T is set
to 1k"

The job of an attacker is blend in so that their traffic is
indistinguishable from users. If they know they know what the
thresholds are that raise suspicion then they'll adjust their attack
to avoid hitting the thresholds! In this case, for instance, they
could try a DDOS to avoid detection.

Caches also have other attack vectors. For instance, if an attacker
knows they hash algorithm and the cache scheme, they might be able to
launch and attack to prevent service to specific destinations by
targeting the hash buckets of the destination. This sort of attack
comes up a lot in traffic steering which is why all those schemes
requiring randomizing the hash key and occasionally rekeying.

>From the paper: "The main design rationale behind the proposed
solution is to detect and push-back attackers by rate-limiting them in
aggregating points"

Unless the identification of attackers is perfect (which again is what
attackers are working to prevent), at some point legitimate users will
get swept up in this and they will be subject to the same rate
limiting. In that case, what is the effect on them? For instance, are
they completely blocked sending packets for some period of time? How
would this situation be resolved?

Thanks,
Tom

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

---

From: Dino Farinacci <[email-masked]>
Date: Fri, 23 Mar 2018 13:01:47 +0000

I believe we have to spec out how CMS could work in more detail and try different fields of the IP header for input to  different hash functions to see if the needle (good actors) can get through the haystack (bad actors). 

But agree if bad actors are spoofing good actors there is no way to tell. 

Many of us have been thinking about how to use Proof of Work mechanisms so if a bad actor had to do more work to send a packet it could slow down the DoS attack. But just early thoughts. 

Dino

> On Mar 23, 2018, at 11:46 AM, Tom Herbert <[email-masked]> wrote:
>

---

From: Albert Cabellos <[email-masked]>
Date: Fri, 23 Mar 2018 15:06:13 +0100

Hi Tom

Thank you very much for your feedback, please see inline:

> there is a better path. This is sort of a hybrid of the pull and push

Agreed, as we point in the short paper alternative LISP deployment models
are possible [draft-rodrigueznatal-ila-lisp-00] if the assumptions
described in the paper do not hold.

> is a big assumption and I'm not sure it will be generally true.
We consider it a reasonable assumption, particularly for data-center and 5G
scenarios.

> prefixes, VMs sharing common server IP address, etc.
The paper focuses on source IP addresses but it can be trivially adapted to
identify users using any information in the packet headers or from the
network infrastructure.

> hidden in some downloaded app.

The threshold determines what is and what is not an attacker, if they are
below T then this means that they are not overflowing the control-plane
channel. In other words, T is related to the maximum throughput of this
channel.

> could try a DDOS to avoid detection.
In my view this is orthogonal. You pick T (the threshold) so that it
determines the maximum throughput of your control-plane channel. If they
are below T then you have enough resources to accommodate all control-plane
messages.

> requiring randomizing the hash key and occasionally rekeying.

Yes, but LFU-A or ARC mechanisms require attackers to generate as much
traffic to unpopular destinations as the popular destinations are
receiving. If this happens in your network this roughly means that you have
more traffic from attackers than from legitimate users. Then what is the
'legitimate traffic'? Either you fix your network or you serve what your
users want.

We have seen over and over that traffic is a long-tail distribution, some
destinations are very popular while many other destinations are not
popular. The same applies to the pages accessed by a computer program, etc.
This is the underlying reason why caches are so prevalent in computer
science. With long-tail distributions they are very efficient in terms of
resource consumption.

> would this situation be resolved?

If anti-spoofing mechanisms are not in place then the solution proposed in
the paper does not work.

The rate-limiter allows you to send T messages per period of time p. After
p seconds you can send T additional control-plane messages. The
rate-limiter is T/p control-plane messages per second.

Thanks!

Albert

---

From: Tom Herbert <[email-masked]>
Date: Sat, 24 Mar 2018 11:56:35 +0000

On Fri, Mar 23, 2018, 1:01 PM Dino Farinacci <[email-masked]> wrote:

> I believe we have to spec out how CMS could work in more detail and try
> different fields of the IP header for input to  different hash functions to
> see if the needle (good actors) can get through the haystack (bad actors).
>

Dino,

I'm not sure what else in IP header could help, attackers can spoof any
field. If you are saying that users need to authenticate with the LISP
sub-system that will have a lot of pushback.

> Many of us have been thinking about how to use Proof of Work mechanisms so
> if a bad actor had to do more work to send a packet it could slow down the
> DoS attack. But just early thoughts.

The other possibility is to accept the fact that we can't prevent DoS
attacks on public networks, however we can limit the effects of the DoS
attack so that it's not worth it to an attacker. The limit of interest is
the worst case effect of the DoS attack. The worse case we are targeting
for attacks on a mapping cache is that packets for good guys might take a
suboptimal route. This should be much better than good users having packets
dropped or blocked.

Tom

---

From: Dino Farinacci <[email-masked]>
Date: Sat, 24 Mar 2018 05:14:09 -0700

> I'm not sure what else in IP header could help, attackers can spoof any field. If you are saying that users 

Destination address and possibly QoS. That is, popular destinations or EF QoS could have more strict rate-limters.

> need to authenticate with the LISP sub-system that will have a lot of pushback.

I am not saying that.

> The other possibility is to accept the fact that we can't prevent DoS attacks on public networks, however we can limit the effects of the DoS attack so that it's not worth it to an attacker. The limit of interest is 

Well if the mapping system doesn’t allow high-rate senders to get RLOCs, that helps a lot more than what we have today. Especially when xTRs/ILA-N nodes are close to the source.

By the way, if you call your ILA-N nodes xTRs, you’d be compatible with LISP. That is, “T” in LISP means “Tunnel” and “T” in ILA means “Transformation”. So when we speak we can say that an xTR is on the edge of the overlay that can “tunnel” or “transform”. 

And this follows nicely with RTRs/ILA-R nodes (“Re-encapsulating Tunnel Routers and “Re-transforming Transforming Routers).  

> the worst case effect of the DoS attack. The worse case we are targeting for attacks on a mapping cache is that packets for good guys might take a suboptimal route. This should be much better than good users having packets dropped or blocked. 

Well I think you can do this once the map-cache entry is populated. That is if you see high-rate sources that are not legit, then one of the RLOCs in the RLOC-set could be a honey-pot or third-party that has sufficient bandwidth and capacity to drop packets. Where other sources that are within the rate-limiters can get their packets sent to good RLOCs.

But then you have to absorb the low-rate bad actors. But if they are low-rate, one would argue you can classify them as good actors (i.e. they get the same service as low-rate good-actors). The other thing you can do is lower the QoS value for bad actors. With encapsulation you can retain the original QoS value in the inner header and the downgraded value in the outer header. 

Dino

---

From: Tom Herbert <[email-masked]>
Date: Sat, 24 Mar 2018 23:37:14 +0000

On Sat, Mar 24, 2018, 12:14 PM Dino Farinacci <[email-masked]> wrote:

> field. If you are saying that users
>
> Well if the mapping system doesn’t allow high-rate senders to get RLOCs,
> that helps a lot more than what we have today. Especially when xTRs/ILA-N
> nodes are close to the source.
>
> By the way, if you call your ILA-N nodes xTRs, you’d be compatible with
> LISP. That is, “T” in LISP means “Tunnel” and “T” in ILA means
> “Transformation”. So when we speak we can say that an xTR is on the edge of
> the overlay that can “tunnel” or “transform”.
>
> And this follows nicely with RTRs/ILA-R nodes (“Re-encapsulating Tunnel
> Routers and “Re-transforming Transforming Routers).
>
> Well I think you can do this once the map-cache entry is populated. That
> is if you see high-rate sources that are not legit, then one of the RLOCs
> in the RLOC-set could be a honey-pot or third-party that has sufficient
> bandwidth and capacity to drop packets. Where other sources that are within
> the rate-limiters can get their packets sent to good RLOCs.
>
> But then you have to absorb the low-rate bad actors. But if they are
> low-rate, one would argue you can classify them as good actors (i.e. they
> get the same service as low-rate good-actors). The other thing you can do
> is lower the QoS value for bad actors. With encapsulation you can retain
> the original QoS value in the inner header and the downgraded value in the
> outer header.
>

Dino,

That's still contingent on be able to distinguish bad actors from good
ones, I claim there is no general method that can do that reliably.

Tom