Subject: Re: [lisp] #8: Limits on "Gleaned" Map Entries Not Clear

From: "lisp issue tracker" <[email-masked]>
Date: Mon, 07 Sep 2009 23:18:50 -0000

#8: Limits on "Gleaned" Map Entries Not Clear
-------------------------------+--------------------------------------------
Reporter:  [email-masked]  |        Owner:  [email-masked]
    Type:  technical           |       Status:  assigned             
Priority:  major               |    Component:  draft-ietf-lisp      
Severity:  -                   |   Resolution:                       
Keywords:                      |  
-------------------------------+--------------------------------------------
Changes (by [email-masked]):

  * owner:  => [email-masked]
  * status:  new => assigned

Comment:

 In Dino's proposed 04 text  the following is added:

    o  A "gleaned" map-cache entry, one learned from the source RLOC of a
       received encapsulated packet, is only stored and used for a few
       seconds, pending verification.  Verification is performed by
       sending a Map-Request to the source EID (the inner header IP
       source address) of the received encapsulated packet.  A reply to
       this "verifying Map-Request" is used to fully populate the map-
       cache entry for the "gleaned" EID and is stored and used for the
       time indicated from the TTL field of a received Map-Reply.

 We're still waiting to hear back from the WG and Margaret on this text.

-- 
Ticket URL: <https://svn.tools.ietf.org/wg/lisp/trac/ticket/8#comment:1>
lisp <http://tools.ietf.org/lisp/>
LISP WG document issues

---

From: "lisp issue tracker" <[email-masked]>
Date: Mon, 07 Sep 2009 23:22:29 -0000

Comment(by [email-masked]):

 Actually Dino had an additional fix to his proposed text in the second
 round of 04 changes: themap request  needs to be sent to the eid not the
 rloc.

-- 
Ticket URL: <https://wiki.tools.ietf.org/wg/lisp/trac/ticket/8#comment:2>
lisp <http://tools.ietf.org/lisp/>
LISP WG document issues

---

From: Margaret Wasserman <[email-masked]>
Date: Mon, 7 Sep 2009 20:35:50 -0400

> We're still waiting to hear back from the WG and Margaret on this  

While this text is better than what was in the -03 draft, it isn't  
good enough, IMO.

On the list, we discussed an additional requirement that gleaned  
mappings will never overwrite mappings that were received in map  
replies.

Also, I am concerned about the implications of this behavior in the  
case of intentional spoofing.  If the attacker sends a message to  
create the gleaned mapping, he will also know that the host will soon  
send a request for that EID.  In that case, he _could_ send a large- 
enough number of map replies for that EID, all with difference nonce  
values, perhaps covering a non-trivial percentage of the 24-bit nonce  
space.

What is an ITR supposed to do if it receives two different responses  
to the map request for the gleaned address?

Margaret

---

From: Margaret Wasserman <[email-masked]>
Date: Mon, 7 Sep 2009 20:39:05 -0400

Margaret

---

From: Dino Farinacci <[email-masked]>
Date: Mon, 7 Sep 2009 19:14:00 -0700

> mappings will never overwrite mappings that were received in map  

Right, and the text above does not imply that. The verifying Map- 
Request is responded by a Map-Reply. It is the contents of the Map- 
Reply that is stored in the map-cache.

> create the gleaned mapping, he will also know that the host will  
> soon send a

You need to be clear about the case. Is the attacker spoofing the  
address of a real locator or is the attack spoofing the mapping data?

> request for that EID.

Yes, but the Map-Request will never be sent to the attacker when it is  
sent into the mapping database system.

> In that case, he _could_ send a large-enough number of map replies  
> for that EID, all with difference nonce values, perhaps covering a  
> non-trivial percentage of the 24-bit nonce space.

Who is he? The attacker? Nope, that won't happen, the attacker won't  
get the Map-Requests so it can't Map-Reply. And if it chooses to Map- 
Reply on its own, the ITR won't accept unsolicited Map-Replies.

> to the map request for the gleaned address?

What do you mean by different. In our implementation, if one is  
received with the wrong nonce, then the Map-Reply is rejected and a  
spoof-alert log message is issued. If the later comes in with the  
right nonce, it is accepted.

So not sure what you are asking.

Dino

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

---

From: Margaret Wasserman <[email-masked]>
Date: Tue, 8 Sep 2009 10:02:09 -0400

> Reply that is stored in the map-cache.

I think we should explicitly state that a "gleaned" map-cache entry  
will not be created if a map entry already exists for an EID prefix  
containing the EID in the received packet, even if the map-cache entry  
indicates that packets to that EID should be sent to a different ETR.
> address of a real locator or is the attack spoofing the mapping data?

The attacker is trying to get an ITR to use a bogus map cache entry,  
so that data will be sent to the attacker's ETR (and processed by the  
attacker's end-system) instead of to the actual ETR that serves the EID.

> Yes, but the Map-Request will never be sent to the attacker when it  
> is sent into the mapping database system.

True.

> Reply on its own, the ITR won't accept unsolicited Map-Replies.

There is nothing tying a map reply to the original map request except  
for the nonce.  So, if an attacker can reliably cause an ITR to send a  
map request for a particular EID, he can then send map replies for  
that EID, even though he didn't see the request.  If he sends a bunch  
(potentially thousands) of map replies over the next several seconds,  
perhaps one of them will match the nonce of the request that the ITR  
actually sent.  In that case the mapping information from the reply  
may be added to the cache instead of the mapping entry from the ETR  
that genuinely serves the indicated EID.  This is a percentages  
game...  While it might only work 1 in a ~10,000 times, there isn't  
any reason why the attacker couldn't try it 10,000 times, using  
different EIDs and/or targeting different ITRs until it works.  The  
spoofed entries could contain a long TTL and a short prefix, so that  
the attacker could cause an ITR to  use his ETR for a large number of  
EIDs  for a long time.  If the LISP ITR were run by an ISP, for  
example, this could cause all of the ISPs customers to connect to the  
attacker instead of to the real site(s) that are associated with those  
EIDs.

There are a couple ways to deal with this attack that I can think of:

(1) Make the nonce in the map request/reply larger (64-bits or more?),  
so that there is a much smaller chance that an attacker can hit upon a  
matching nonce.  This could probabilistically limit the case where  
attackers could create a bogus map cache entry using this mechanism to  
on-path attackers.  I don't have the security analysis skills to
know how long the nonce needs to be to make it large enough to thwart  
an off-path attacker, but we could probably get someone from the  
security area to help us figure
that out.

(2) Require that the reply be sent from the map resolver to whom the  
request was sent, perhaps with additional authentication to indicate  
that it was actually sent from that map resolver.  This would make it  
necessary for an attacker to gain control of a map resolver and/or to  
reconfigure the ITR in order to inject bogus map cache entries.

There are probably other ways to thwart this type of attack, so we  
might want to talk to security folks to see if there are other options.

>> What is an ITR supposed to do if it receives two different  
>> responses to the map request for the gleaned address?
>

What happens if you get two different replies that both have the right  
nonce?  Will you accept the first and then accept the second,  
overwriting the information received in the first?  Or will you accept  
the first, throw away the state related to that nonce, and reject the  
second because it doesn't match any open nonce?  Either way, if an  
attacker can send a reply with a matching nonce (regardless of how  
many replies he sends that don't match), you will end-up using his  
mapping about 50% of the time, instead of the mapping
from the real ETR that serves that EID prefix.

Margaret

---

From: Dino Farinacci <[email-masked]>
Date: Tue, 8 Sep 2009 17:19:05 -0700

> containing the EID in the received packet, even if the map-cache  
> entry indicates that packets to that EID should be sent to a  
> different ETR.

I will add that and send text in another email.

>>> Also, I am concerned about the implications of this behavior in  
>>> the case of intentional spoofing.  If the attacker sends a message  
>>> to create the gleaned mapping, he will also know that the host  
>>> will soon send a
>>
> so that data will be sent to the attacker's ETR (and processed by  
> the attacker's end-system) instead of to the actual ETR that serves  
> the EID.

That cannot happen. I think you may be convince of that now?

>> Who is he? The attacker? Nope, that won't happen, the attacker  
>> won't get the Map-Requests so it can't Map-Reply. And if it chooses  
>> to Map-Reply on its own, the ITR won't accept unsolicited Map- 
>> Replies.
>
> There is nothing tying a map reply to the original map request  
> except for the nonce.  So, if an attacker can reliably cause an ITR  
> to send a map request for a particular EID, he can then send map  
> replies for that EID, even though he didn't see the request.  If he  
> sends a bunch (potentially thousands) of map replies over the next  
> several seconds, perhaps one of them will match the nonce of the  
> request that the ITR actually sent.  In that case the mapping  
> information from the reply may be added to the cache instead of the  
> mapping entry from the ETR that genuinely serves the indicated EID.   
> This is a percentages game...  While it might only work 1 in a  
> ~10,000 times, there isn't any reason why the attacker couldn't try  
> it 10,000 times, using different EIDs and/or targeting different  
> ITRs until it works.  The spoofed entries could contain a long TTL  
> and a short prefix, so that the attacker could cause an ITR to  use  
> his ETR for a large number of EIDs  for a long time.  If the LISP  
> ITR were run by an ISP, for example, this could cause all of the  
> ISPs customers to connect to the attacker instead of to the real  
> site(s) that are associated with those EIDs.

No this isn't true. What ties the real ETRs and no one else to the EID  
in a Map-Request is the authenticated registration to the map-server.

All the attacker can do is send packets to the xTR which it drops. At  
the same rate, the xTR would get packets to decapsulated. All limited  
to the rate of the PE/CE link.

> (1) Make the nonce in the map request/reply larger (64-bits or  
> more?), so that there is a much smaller chance that an attacker can  
> hit upon a matching nonce.  This could probabilistically limit the  
> case where

The L2TP guys have said that 32-bit cookies work pretty well.

> attackers could create a bogus map cache entry using this mechanism  
> to on-path attackers.  I don't have the security analysis skills to
> know how long the nonce needs to be to make it large enough to  
> thwart an off-path attacker, but we could probably get someone from  
> the security area to help us figure
> that out.
>
> that it was actually sent from that map resolver.  This would make  
> it necessary for an attacker to gain control of a map resolver and/ 
> or to reconfigure the ITR in order to inject bogus map cache entries.

We don't need to do this. But to be honest I don't understand what you  
are proposing. But it sounds like a lot of machinery.

> What happens if you get two different replies that both have the  
> right nonce?  Will you accept the first

The second mapping data overrides the first.

> and then accept the second, overwriting the information received in  
> the first?  Or will you accept the first, throw away the state  
> related to that nonce, and reject the second because it doesn't  
> match any open nonce?  Either way, if an attacker can send a reply  
> with a matching nonce (regardless of how many replies he sends that  
> don't match), you will end-up using his mapping about 50% of the  
> time, instead of the mapping

We will accept both which are secure and from the authoritative source.

The same nonce would only happen if the ITR sent 2 Map-Requests with  
the same nonce and a different ETR at each site received it and  
replies. Which is a valid scenario.

And the attacker could only exist if it was man in the middle. But it  
would have to be in the middle of both the ALT and the Map-Reply  
return path. Which usually is an on-path device and rare.

Dino

---

From: Margaret Wasserman <[email-masked]>
Date: Tue, 8 Sep 2009 22:07:24 -0400

On Sep 8, 2009, at 8:19 PM, Dino Farinacci wrote:
>> The attacker is trying to get an ITR to use a bogus map cache  
>> entry, so that data will be sent to the attacker's ETR (and  
>> processed by the attacker's end-system) instead of to the actual  
>> ETR that serves the EID.
>

No, I don't see what would stop this from happening...

There are two steps here:

(1) The attacker manages to send a spoofed map reply that gets  
processed by the ITR.
(2) The ITR sends encapsulated data packets to the ETR in the spoofed  
map reply, instead of to the correct ETR for the destination EID.

The second step can certainly happen, if an attacker can cause the ITR  
to store a spoofed map-cache entry.

We all seem to agree that this can happen "for a few seconds" if an  
attacker sends a packet that will generate an incorrect "gleaned" entry.

The question is whether the attacker can parlay this into a longer- 
lived map cache entry by flooding the same ITR with map responses for  
the EID in the gleaned entry immediately after sending the packet that  
caused the gleaned entry in the first place.  The attacker knows that  
the ITR will send a request for that entry, so she can play a
numbers game and send replies with as many nonce values as possible,  
hoping to hit on the nonce that the ITR uses in its request.
>
> No this isn't true. What ties the real ETRs and no one else to the  
> EID in a Map-Request is the authenticated registration to the map- 
> server.

The ITR that sends the map request can't see the authenticated  
registration in the map server.

I am not saying that an attacker could get a spoofed entry into the  
mapping system.  We don't actually require map responses to come from  
the mapping system; they come directly from ETRs, at least some cases,  
and they don't contain any information that can be used to  
authenticate the data.  So, there is no reason that an attacker  
couldn't generate responses that, if they happen to hit the right  
nonce value, would look just as authentic to the requesting ITR as  
responses from the real ETR.
>
> All the attacker can do is send packets to the xTR which it drops.  
> At the same rate, the xTR would get packets to decapsulated. All  
> limited to the rate of the PE/CE link.

It will drop them unless the nonce matches.
> The L2TP guys have said that 32-bit cookies work pretty well.

What do they use the 32-bit cookies to protect?  It is possible that a  
32-bit nonce is sufficient to protect the map request/reply system,  
but given the level of danger if we are wrong, I think it would be  
wiser to move to a 64-bit nonce.  These are in control packets only,  
so moving to a longer nonce shouldn't effect forwarding performance or  
anything.  I agree that if we end-up moving to authenticating the  
individual mapping entries we won't need a 64-bit nonce, but isn't  
clear that we need a 32-bit nonce in that case, either.
>> (2) Require that the reply be sent from the map resolver to whom  
>> the request was sent, perhaps with additional authentication to  
>> indicate that it was actually sent from that map resolver.  This  
>> would make it necessary for an attacker to gain control of a map  
>> resolver and/or to reconfigure the ITR in order to inject bogus map  
>> cache entries.
>
> We don't need to do this. But to be honest I don't understand what  
> you are proposing. But it sounds like a lot of machinery.

A longer nonce wouldn't require any additional machiner.

> And the attacker could only exist if it was man in the middle. But  
> it would have to be in the middle of both the ALT and the Map-Reply  

The attack I am talking about is not an on-path attack.  It is  
performed by an off-path attacker who makes some guesses about how a  
particular LISP implementation will perform.  It becomes particularly  
dangerous if any of ship LISP implementations with (cryptographically)  
poor random number generators, which might allow an off-path attacker  
to optimize the specific nonce values that it will try in its spoofed  
responses.

Margaret

---

From: Dino Farinacci <[email-masked]>
Date: Tue, 8 Sep 2009 21:52:37 -0700

> (1) The attacker manages to send a spoofed map reply that gets  

And you say this will happen because the attacker guessed the 32-bit  
nonce, right? Because that is the only way it could happen.

> (2) The ITR sends encapsulated data packets to the ETR in the  
> spoofed map reply, instead of to the correct ETR for the destination  
> EID.
>
> The second step can certainly happen, if an attacker can cause the  
> ITR to store a spoofed map-cache entry.
>

Well, my implementation doesn't forward packets to a gleaned entry. It  
puts the entry in "tenative state" awaiting for the Map-Reply.

> lived map cache entry by flooding the same ITR with map responses  
> for the EID in the gleaned entry immediately after sending the  
> packet that caused the gleaned entry in the first place.  The  
> attacker knows that the ITR will send a request for that entry, so  
> she can play a

The attacker would have to guess each nonce. Unlikely.

> mapping system.  We don't actually require map responses to come  
> from the mapping system; they come directly from ETRs, at least some  
> cases, and they don't contain any information that can be used to  

Right, but it's a question of probability versus complex machinery to  
make it secure for those remote cases.

I'd like to remind you that the DNS has lived with this problem for a  
very long time.

>>> more?), so that there is a much smaller chance that an attacker  
>>> can hit upon a matching nonce.  This could probabilistically limit  
>>> the case where
>>
> What do they use the 32-bit cookies to protect?  It is possible that  
> a 32-bit nonce is sufficient to protect the map request/reply  
> system, but given the level of danger if we are wrong, I think it  
> would be wiser to move to a 64-bit nonce.  These are in control  
> packets only, so moving to a longer nonce shouldn't effect  
> forwarding performance or anything.  I agree that if we end-up  
> moving to authenticating the individual mapping entries we won't  
> need a 64-bit nonce, but isn't clear that we need a 32-bit nonce in  
> that case, either.

So what makes you think a ITR can process fast enough a blast of  
nonces where 32-bits won't be long enough?

>>> attackers could create a bogus map cache entry using this  
>>> mechanism to on-path attackers.  I don't have the security  
>>> analysis skills to
>>> thwart an off-path attacker, but we could probably get someone  
>>> from the security area to help us figure
>>> that out.
>>>
>>> resolver and/or to reconfigure the ITR in order to inject bogus  
>>> map cache entries.
>>

Let's see what the working group consensus is on this.

>>> and then accept the second, overwriting the information received  
>>> in the first?  Or will you accept the first, throw away the state  
>>> with a matching nonce (regardless of how many replies he sends  
>>> that don't match), you will end-up using his mapping about 50% of  
>>> the time, instead of the mapping
>> The same nonce would only happen if the ITR sent 2 Map-Requests  
>> with the same nonce and a different ETR at each site received it  
>> and replies. Which is a valid scenario.
>>
> particular LISP implementation will perform.  It becomes  
> particularly dangerous if any of ship LISP implementations with  
> (cryptographically) poor random number generators, which might allow  
> an off-path attacker to optimize the specific nonce values that it  
> will try in its spoofed responses.

By the way, the ETR would also have to guess the EID-prefix used by  
the site as well. So if the attacker replied with a mask-length that  
was not returned by the authoritative ETR, then the ITR knows there is  
a spoofer.

But I bet in practice, you won't be able to realize this attack.

Dino

---

From: Margaret Wasserman <[email-masked]>
Date: Wed, 9 Sep 2009 09:14:53 -0400

On Sep 9, 2009, at 12:52 AM, Dino Farinacci wrote:
> Well, my implementation doesn't forward packets to a gleaned entry.  
> It puts the entry in "tenative state" awaiting for the Map-Reply.

Shouldn't the specification say this, then?  If so, this would close a  
possible security concern.  I had assumed that when the specification  
said you could create a "gleaned" map cache entry that it meant that  
you could _store and use_ a "gleaned" map cache entry.  What is the  
point of creating the tentative entry at all if you won't use it?
>
> I'd like to remind you that the DNS has lived with this problem for  
> a very long time.

Not quite, because DNS requires that the response be returned by the  
server to which the request was sent.  LISP allows a response to come  
from anywhere.
>> performed by an off-path attacker who makes some guesses about how  
>> a particular LISP implementation will perform.  It becomes  
>> (cryptographically) poor random number generators, which might  
>> allow an off-path attacker to optimize the specific nonce values  
>> that it will try in its spoofed responses.
>
> was not returned by the authoritative ETR, then the ITR knows there  
> is a spoofer.

How does the ITR tell which response is coming from the authoritative  
ETR and which isn't?

Margaret

---

From: Margaret Wasserman <[email-masked]>
Date: Wed, 9 Sep 2009 09:21:58 -0400

Just to make my response a little clearer...

On Sep 9, 2009, at 9:14 AM, Margaret Wasserman wrote:
> server to which the request was sent.  LISP allows a response to  
> come from anywhere.

This is significant for two reasons:

(1) I can send the response from anywhere, using valid addresses for  
that location, so I don't need to worry about my packets being ingress  
filtered for having an invalid source address, and

(2) When I am flooding the ITR with responses trying to get a nonce  
hit, I can do so from many different systems.  In other words, this  
lends itself to a distributed attack.

Margaret

---

From: Sam Hartman <[email-masked]>
Date: Wed, 09 Sep 2009 11:58:12 -0400

>>>>> "Margaret" == Margaret Wasserman <[email-masked]> writes:

    >> I'd like to remind you that the DNS has lived with this problem
    >> for a very long time.

    Margaret> Not quite, because DNS requires that the response be
    Margaret> returned by the server to which the request was sent.

Also, I'll point out that we've spent the last year trying madly to
find ways of increasing DNS's nonce size exactly because of this sort
of attack.  And there, yes, we do have real-world proofs of the
problem.

---

From: "Darrel Lewis (darlewis)" <[email-masked]>
Date: Wed, 9 Sep 2009 09:25:05 -0700

> Subject: Re: [lisp] #8: Limits on "Gleaned" Map Entries Not Clear
> 
> 

I think we have a communication problem on this thread.  

Dino's comments seem to be about data-gleaning.  That is, placing map
entries in the cache by inspecting the data-plane traffic.  That is,
techniques described around 

Margaret and Noel (I think) seem to be talking about the map-data that
is piggybacked on a Map-Request packet.

So if this is the case (apologies if I mis-represented anyone's point of
view) hopefully by pointing this out this could help clear up the
discussion.  Speaking just for myself, Data Plane gleaning doesn't seem
useful in the capital I internet, but Map-Request map-data gleaning is
very useful, since it prevents packet loss/delay on return traffic of
session set up.  (several content providers emphasized this as an
important feature during LISP's presentations at NANOG).

-Darrel

---

From: Dino Farinacci <[email-masked]>
Date: Wed, 9 Sep 2009 09:43:08 -0700

>>> We all seem to agree that this can happen "for a few seconds" if  
>>> an attacker sends a packet that will generate an incorrect  
>>> "gleaned" entry.
>>
> Shouldn't the specification say this, then?  If so, this would close  
> a possible security concern.  I had assumed that when the  
> specification said you could create a "gleaned" map cache entry that  
> it meant that you could _store and use_ a "gleaned" map cache  
> entry.  What is the point of creating the tentative entry at all if  
> you won't use it?

Well, we wanted to leave it up to the implementation. Because in a  
trusted environment, to reduce delay, you could use the data-gleaned  
entry right away. Like I mentioned in a previous email.

> server to which the request was sent.  LISP allows a response to  

Well I could build a server that can return a request from anywhere.

I think both cases use solicitation to get a response.

>> the site as well. So if the attacker replied with a mask-length  
>> that was not returned by the authoritative ETR, then the ITR knows  
>> there is a spoofer.
>
> How does the ITR tell which response is coming from the  
> authoritative ETR and which isn't?

The 32-bit nonce.

Dino