Subject: Could MLD announced solicited node memberships be used validate off-link, router originated Neighbor Solicitations?

From: Mark Smith <[email-masked]>
Date: Wed, 27 Jan 2010 18:14:47 +1030

Hi,

There have been a few discussions on a few operational mailing lists in
the last few weeks about the use of longer than /64s on point-to-point
links.

One valid reason to do so is to mitigate a Neighbor Discovery DoS,
initiated by off-link sources sending traffic to incrementing
destinations, causing the on-link router to issue large numbers of
Neighbor Solicitations towards Solicited-Node multicast destinations
for nodes that don't exist. 

RFC3756 described this vulnerability in section 4.3.2, "Neighbor
Discovery DoS Attack".

This issue isn't specific to point-to-point links. Any /64 is
vulnerable. People who're advocating longer than /64s for
point-to-point links as a mitigation for this issue can also advocate
using prefix lengths longer than /64 for all IPv6 subnets.

As I'm an advocate for the simplicity of using /64s for all links, I've
been thinking how this issue could be avoided, without having to resort
to longer than /64s, or other manual methods such as traffic filtering
ACLs or static neighbor discovery entries.

At the end of the description of the issue, RFC3756 mentions

"This attack does not directly involve the trust models presented.
However, if access to the link is restricted to registered nodes, and
the access router keeps track of nodes that have registered for access
on the link, the attack may be trivially plugged.  However, no such
mechanisms are currently standardized."

I think Multicast Listener Discovery announcements for hosts'
memberships of the Solicited Node multicast addresses could be used as
this "membership registration" mechanism. When a router is asked
to issue a neighbor solicitation for a downstream host, after it
converts the destination address into a Solicited Node multicast
address, is could then validate that multicast address against a list
of known Solicited Node multicast addresses it has learned from the
hosts via their MLD announcements. Neighbor Solications for Solicited
Node multicast addresses that aren't known would be dropped, preventing
off-link nodes from exhausting the router's neighbor discovery
resources. 

Do people think using MLD announcements in this way would be suitable
way to mitigate this DoS while preserving the simplicity of
universal /64s?

Regards,
Mark.

---

From: Shane Amante <[email-masked]>
Date: Wed, 27 Jan 2010 08:03:48 -0700

Mark,

> way to mitigate this DoS while preserving the simplicity of

Why not have routers just look at the IPv6 "Hop Limit" (TTL) field, and discard if hop limit < 255?  (Of course, you'd still want to apply an "infrastructure" ACL with GTSM so NMS systems still have visibility to your p2p interfaces, but that shouldn't be terribly difficult).

Have a look at RFC 5082: <http://tools.ietf.org/html/rfc5082> for GTSM.

-shane

> 
> Regards,
> Mark.
> 
> --------------------------------------------------------------------
> IETF IPv6 working group mailing list
> [email-masked]
> Administrative Requests: https://www.ietf.org/mailman/listinfo/ipv6
> --------------------------------------------------------------------

---

From: Mark Smith <[email-masked]>
Date: Thu, 28 Jan 2010 20:59:12 +1030

Hi Shane,

On Wed, 27 Jan 2010 08:03:48 -0700

> Have a look at RFC 5082: <http://tools.ietf.org/html/rfc5082> for GTSM.

Are you talking about protecting against neighbor solicitations
that are originated off link? If that is that case, that's not the
problem I talking about. I've realised the subject line might not have
made that quite clear - I've changed it to hopefully make it so.

Here's the steps to cause it:

1. target prefix is a globally routable /64

2. off-link located (e.g. Internet) attacker sends a high rate of
packets (any type) towards incrementing or random addresses within
that /64 e.g. ::1, ::2, ::3, etc. etc.

3. the router attached to the target /64 will generate neighbor
solicitations for those non-existant destinations, towards it's
directly attached target /64. According to RFC2461, the default total
timeout for these NSes is 3 seconds. As the router keeps state for the
outstanding neighbor solicitations, if the rate the attacker is sending
traffic with changing host addresses is high enough, the
state tables in the router may be exhausted, resulting in a denial of
service.

The router might appear to need to hold 2^64 outstanding
Neighbor Solicitation table entries to survive this attack, however, as
destinations for Neighbor Solicitations are mapped to Solicited Node
multicast addresses, using the lower 24 bits, the router would have to
"only" hold 2^24 outstanding Neighbor Solicitation entries, which still
16 million+. Admittedly with 64 byte packets, to go through all 2^24
Solicited Node multicast addresses the attacker would have to send
around 2.8 Gpbs of traffic - receiving that much traffic might be a
bigger problem. To create 65 535 neighbor solicitation table entries,
which a router could still struggle with (e.g. low-end residential CPE)
would only require around 11 Mbps of traffic, which is much more
commonly achievable.

I think the fundamental issue is that a remote attacker can use traffic
to create remote network device state. That is also the case with
IPv4 with ARP tables, however because the subnets in IPv4 are commonly
small, IPv4 has been protected from this type of attack.

Ideally, the local router should only issue neighbor solicitations onto
the attached /64 for Solicited Node multicast addresses that exist,
avoiding unnecessary traffic, and avoiding creating unnecessary router
state for Neighbor Soliciations that will never be answered.

My Linux box issues MLD announcements for these Solicited Node multicast
addresses when an interface comes up, and it responds to MLD General
Queries for those multicast addresses. The IPv6 Node Requirements RFC
says MLD is a required feature, so I think it can be relied on that
most if not all IPv6 implementations will make MLD announcements for
Solicited Node addresses. I think those MLD announcements could be used
by routers to build a Solicited Node validation list, allowing them to
filter out Neighbor Solicitations, protecting against this type of
attack.

Regards,
Mark.

---

From: Erik Nordmark <[email-masked]>
Date: Thu, 28 Jan 2010 02:39:06 -0800

> way to mitigate this DoS while preserving the simplicity of

The "join delay" for MLD is unpredictable since the reliability of the 
MLD reports is based on a few initial ones (which could all be lost) 
plus router-triggered slow rate MLD queries. That join delay doesn't 
seem to cause a problem for today's multicast applications, but I would 
be quite concerned if the host couldn't communicate at all during this 
delay, which would be the effect of your proposal.

I think the correct thing architecturally is to actually introduce a 
reliable "registration" mechanism for hosts. There are other good 
reasons for it such as avoiding low-power devices being woken up by 
multicast NS messages especially when the L2 uses broadcast to deliver 
multicast packets. (Work in 6lowpan has explored this space, but I don't 
think draft-ietf-6lowpan-nd is quite what we need.)

If this is construed as a security issue one can probably come up with 
combinations of MLD and also the routers hearing the hosts (which they 
do if the hosts send RSs as they power on) that could minimize the 
probability of hosts being unreachable during the MLD join delay even if 
the MLD reports are lost. But I view that as a short-term approach which 
needs to be replaced by a registration mechanism.

Note that the RSs don't list all the hosts' IP addresses - the source is 
a link-local address. Thus the logic in the router needs to be able to 
compare just N low order bits. If a RS has been send from link local 
fe80::0:1:2:3 then the router needs to be able to send NSs for anything 
in Prefix::0:1:2:3. Listening to the MLD has a similar property since 
the solicited-node multicast address is just a match on the bottom 32 
bits of the IPv6 address.

    Erik

---

From: Mark Smith <[email-masked]>
Date: Thu, 28 Jan 2010 22:19:35 +1030

Hi Erik,

On Thu, 28 Jan 2010 02:39:06 -0800

> delay, which would be the effect of your proposal.

Just to ensure we're on the same page, this checking of known Solicited
Node addresses would only be performed for Neighbor Solicitations
tiggered by traffic with off-link sources. Hosts within the subnet
would still be able to communicate with each other, even if the MLD
reports were lost.

> needs to be replaced by a registration mechanism.

A registration mechanism would definitely address this issue.

I think it is security issue unfortunately. All that is needed to
exploit it is a short script with a looping integer, standard IPv6
ping utility and low numbers of megabits of bandwidth to create
unanswered NSes in the 1000s.

Are there any creative ways we can make the existing MLD mechanisms a
bit more robust, without having to change the protocols, and avoiding
changing the hosts (only having to change router code would be much
easier at this point in time I think)? Maybe something like when a
router responds to a RS, or issues it's periodic RAs, it also issues an
MLD general query to ensure it's Solicited Multicast address list is
kept accurate? Or possibly when a Router Solicitation is received, in
addition to responding with an RA, it also issues a Multicast Address
Specific query for the Solicited Node Address calculated from the
link-local address source of the RS?

> bits of the IPv6 address.

That's true. What we're fundamentally trying to do here is to supress
Neighbor Solicitations for Solicited Node groups that don't have any
members, avoiding the corresponding neighbor discovery state. With 2^24
Solicited node groups*, but practical limits of only a few 1000 hosts
on a link, there potentially will be a very large number of Solicited
Node groups that don't have any members.

* My understanding is that the Solicited Node address is created from
  the bottom 24 bits of the IPv6 address, and then the lower 32 bits of
  that Solicited Node address is copied into the Ethernet 33:33:
  address. 

Regards,
Mark.

---

From: Erik Nordmark <[email-masked]>
Date: Thu, 28 Jan 2010 04:34:11 -0800

> would still be able to communicate with each other, even if the MLD

Sure. But practically all hosts want to communicate off-link e.g. to 
reach google.com.

> unanswered NSes in the 1000s.

But presumably a router would have some resource limits that can avoid 
using up too much memory for incomplete neighbor cache entries. (If they 
don't, perhaps the routers need a real OS ;-)

> link-local address source of the RS?

If the router is actually aware of how much memory it is using for the 
incomplete NCEs then it can have an adaptive mechanism based on a 
threshold. Below the threshold nothing changes. If the number exceeds 
the threshold it would look for the low order bits using 24 bit matches 
against recorded MLD reports and 64 bit matches against existing NCEs. 
If it is there no match, then just drop the packet. If there was a 
temporary spike in the number of inactive NCEs pushing it above the 
threshold, then the number will drop once those inactive NCEs time out, 
at which point one can get through even to a host which didn't do the 
MLD report.

Note that this requires the routers to remember the MLD state for the 
link-local groups; currently routers don't need to do that. The MLD (and 
IGMP) reports for link-local groups exist for the sole purpose of making 
it easy to have MLD (and IGMP) snooping L2 devices.

>    that Solicited Node address is copied into the Ethernet 33:33:

Yes, I misremembered it as 32 bits.

Hmm - seems like there is still a 2^40 (or 2^39 if we discount the group 
bit) of attack possibility with the MLD check.

If the attacker knows that there is a host with a particular address on 
a subnet, then it can construct 2^40 other IPv6 address that map to the 
same solicited-node multicast group. A ping to those addresses would, 
even with all the above mechanisms, mean that the router would send the 
NSes. Thus you still need a real OS in the router that can limit the 
number of (incomplete) NCEs.

    Erik

---

From: Erik Nordmark <[email-masked]>
Date: Thu, 28 Jan 2010 04:35:52 -0800

On 01/28/10 04:16 AM, Joakim Aronius wrote:
> * Erik Nordmark ([email-masked]) wrote:
>> Note that the RSs don't list all the hosts' IP addresses - the
>> source is a link-local address. Thus the logic in the router needs
>> to be able to compare just N low order bits. If a RS has been send
>> from link local fe80::0:1:2:3 then the router needs to be able to
>> send NSs for anything in Prefix::0:1:2:3.
>
> You don't allways have that relation between link local and unicast address, i.e. if the unicast address has been manually configured or assigned via DHCPv6.

And also for SeND and temporary addresses.

I was merely trying to make the mechanism slightly more robust by not 
relying solely on MLD reports. But given the residual 2^40 attack 
possibility I now think the right answer is careful management in the 
router in the amount of memory used for incomplete NCEs.

    Erik

---

From: Mark Smith <[email-masked]>
Date: Thu, 28 Jan 2010 23:23:40 +1030

A quick thought on one of your points, before I go to bed :-)

On Thu, 28 Jan 2010 04:34:11 -0800

> don't, perhaps the routers need a real OS ;-)

True. It seems most of the residential CPE has or is moving to Linux
these days, so they're ending up with one.

Setting maximums for the incomplete neighbor cache entry was my
first thought. The drawback I'd be concerned about is that if that
limit is e.g. 1000, and an an attacker fills it up, then subsequent
legitimate requests get dropped. I'm hoping we can come up with a
simple and smart way, using existing mechansims as much as possible, to
discriminate between legitimate and illegitimate NSes, based on
something that the downstream hosts can provide, that doesn't
involve basically setting a lower point where a NS DoS can be triggered.

---

From: Joakim Aronius <[email-masked]>
Date: Thu, 28 Jan 2010 13:16:14 +0100

BR
/Joakim

---

From: Erik Nordmark <[email-masked]>
Date: Thu, 28 Jan 2010 05:46:20 -0800

> involve basically setting a lower point where a NS DoS can be triggered.

To do this you need to be able to tell the difference between a good and 
a bad (unresolvable) address. But you have no a-priori knowledge to tell 
them apart.

Instead of a simple threshold the effect of having too many incomplete 
NCEs could be to effectively reduce the time until the incomplete NCEs 
time out. Thus instead of blocking the creation of new NCEs, discard the 
oldest incomplete NCE. That will favor the good ones as long as the load 
doesn't get so high that the lifetime of an incomplete NCE drops below 
the RTT of the LAN; in that case not even the good ones will see a NA 
before they are thrown away.

But one could also potentially create the NCE when a NA is received even 
if there is no longer an incomplete NCE around. I haven't looked into 
this in detail.

    Erik

---

From: Wassim Haddad <[email-masked]>
Date: Thu, 28 Jan 2010 08:47:57 -0700

Hi Mark,

Just a quick note. If I understand your problem correctly, I'd suggest reading the 
following paper as it decsribes a mechanism to mitigate the ND DoS attack 
launched from outside:

http://planete.inrialpes.fr/%7Eccastel/PAPERS/infocom05.pdf

Regards,

Wassim H.

Regards,

Wassim H.

---

From: Fernando Gont <[email-masked]>
Date: Sun, 31 Jan 2010 04:06:39 -0300

Mark Smith wrote:

> 16 million+. 

This is my take: Have a rather small table for ND entries in the
INCOMPLETE state. Those are the entris for which there has never been a
reachability confirmation.

ND entries that correspond to real nodes that have already sent packets
through the attacked router (or that have received traffic through the
attacked router) would be in other states.

Once the table of ND entries in the INCOMPLETE state gets full, drop
randomly.

Thoughts?

Kind regards,
-- 
Fernando Gont
e-mail: [email-masked] || [email-masked]
PGP Fingerprint: 7809 84F5 322E 45C7 F1C9 3945 96EE A9EF D076 FFF1

---

From: Fernando Gont <[email-masked]>
Date: Sun, 31 Jan 2010 04:14:30 -0300

Erik Nordmark wrote:

> in Prefix::0:1:2:3. 

What about privacy addresses?

Thanks,