[RRG] Re: LISP gleaning looks insecure and therefore unusable

[Robin Whittle <rw@firstpr.com.au>]

Short version:   My understanding of Dino's response is that
                 my critique of "gleaning" is correct.  His
                 statements seem to be contrary to the
                 description of "gleaning" in the lisp-06 ID,
                 and look more realistic to me - so I suggest
                 the ID be rewritten.

                 "Gleaning" as I understand it from Dino's
                 message, involves two things:

                 1 - The ETR (assuming it is an ITR for the
                     destination host of the original packet)
                     speculatively initiating a mapping request
                     for the sending host of this packet, on
                     the basis this will enable mapping data
                     to be found sooner than if the ETR (now
                     acting as an ITR) waited for such a packet.
                     In most cases, I think the time saved would
                     be milliseconds, on average, and since the
                     lookup through the ALT network could take
                     one or more seconds, and since it is not
                     certain there would be such a return packet,
                     the technique is of extremely limited value.

                 2 - While the mapping lookup is occurring, the ETR
                     (R3 below) sends a probe packet to the ITR (R1)
                     with a nonce, to establish its reachability.
                     This is in anticipation of R3 soon being an ITR
                     for HostA's return packet to HostB, with R1 as
                     a likely, but not yet proven, ETR.

                     This would save time only to the extent that
                     it was faster to send the probe to the
                     R1 address immediately, rather than wait
                     a (typical) few milliseconds for HostA's
                     packet to be forwarded to R3.

                 Yet if LISP ITRs are generally, or sometimes
                 required to establish reachability of ETRs before
                 sending a traffic packet, this would seem to
                 introduce a new set of delays which we have not
                 yet contemplated.

                 L3 can't use a traffic packet as a probe to
                 L1, until it received mapping which shows that
                 L1 is an RLOC address for the EID prefix of
                 HostA.  So probing a gleaned R1 address can't
                 be done with a traffic packet.  Traffic packets
                 could not be tunnelled to R1 until R3 received
                 the mapping data, an acknowledgement from R1
                 and if R1 turned out to be a valid ETR in
                 the mapping data.  Still, this tells R3
                 nothing about the ability of R1 to send packets
                 to HostA . . . though perhaps such information
                 could be included in the LISP header with
                 which R1 tunnels the HostA->HostB packet.
                 That would extend the LISP header, making it
                 another 4 bytes or so longer.


                 Tired of all this complexity in ITRs and ETRs
                 and in the mapping data?  Don't want to wait
                 for a global query system to get mapping info??

                 Try http://www.firstpr.com.au/ip/ivip/ instead!

Example:

            ITR           ETR

  HostA-->--R1==>==R2==>==R3-->--HostB

                          R3 "gleans" the (HostA: R1) association
                          in preparation for it being an ITR for

                          HostB sending a packet to HostA.


Hi Dino,

You wrote:

>> Short version:    Gleaning seems to be completely insecure,
>>                  so I can't imagine how it could be useful.
> 
> You just don't use a glean until you complete a Map-Request/Map-Reply
> exchange.

So why bother with gleaning the ITR's address at all?

> That way you test the outer SA of the packet to echo a packet
> back to you with the nonce you provided.

   (BTW, last year when I used "SA" for source address, some
    folks thought I meant "security association".)

OK - that is why.

This makes me think that the ETR sends a LISP probe packet of some
kind with a nonce to the presumed ITR of the initial packet (outer
source address).

I don't recall anything in the LISP IDs which states that the ETR
probes the presumed ITR in this way.  (Presumed, because the ETR
can't know for sure the packet was generated by a legitimated ITR -
it could be the work of an attacker.)

This would make LISP ETRs a good method of sending packets to any
address an attacker chose, though presumably the ETR would only do
this for presumed ITR addresses it was not familiar with.

Your first sentence above seem reasonable to me.  I will discuss the
probing (second sentence) a little later.

Leaving aside the second sentence - and how this process does not
seem to be documented in a LISP ID - I want to focus on your first
sentence:

> You just don't use a glean until you complete a
> Map-Request/Map-Reply exchange.

This seems perfectly reasonable, but I think it contradicts the
lisp-06 ID:

     In order to eliminate the need for a mapping lookup in the
     reverse direction, an ETR MAY create a cache entry that maps
     the source EID (inner header source IP address) to the source
     RLOC (outer header source IP address) in a received LISP
     packet.

Yet your first sentence indicates that gleaning can never remove the
need for a mapping lookup.


     Such a cache entry is termed a "gleaned" mapping and only
     contains a single RLOC for the EID in question.  More complete
     information about additional RLOCs SHOULD be verified by
     sending a LISP Map-Request for that EID.

If the ID stated something like the following about "gleaning" then
I think it would be sensible, within certain limits, and would be in
agreement with your first sentence above:

     "Gleaning" involves the ETR receiving an encapsulated packet
     and recording the inner source address (that of the sending
     host) - and then performing a mapping lookup on this address.

     The purpose of this is to speed up the availability of mapping
     information for the likely event that the recipient of the
     first packet will send a packet back to the original sending
     host.

     Gleaning should only be performed under certain circumstances:

     1 - Where the original packet was in a valid format and was
         addressed to an EID which the ETR is configured to
         decapsulate packets for.

     2 - Where the ETR is also the ITR for any packet sent by the
         destination host of the initial packet.

     3 - Where the ETR does not already have mapping for the
         inner source address of this packet.

     4 - Where there is likely to be a significant time delay
         between this initial packet being decapsulated and the
         time at which the ETR, acting as an ITR, would likely
         receive a packet addressed to the initial sending host.

         "Significant" is relative to the likely delay in receiving
         the mapping reply.  For instance, if the average delay in
         receiving a mapping reply was 1.5 seconds and the
         destination host generally sends packets back to the
         hosts which send it a packet within 0.1 seconds, then
         there is only going to be a typically 0.1 second speed-up
         in the availability of mapping.  Since the ETR cannot
         reliably determine whether the receiving host will send
         a packet back to the original sending host, in this example
         it makes little sense to instigate a mapping request for
         only a slight overall improvement in mapping availability.


In practice, the average receiving host would typically send back a
packet in a few milliseconds.  This is a far smaller delay than that
inherent in any global query server system such as ALT.  So I can't
see much point in this "gleaning" speculative map request activity.

Also, you would need a configuration table in your ETR to tell it
which destination addresses it is decapsulating packets for which
are also hosts or networks for which this ETR is the ITR.

Furthermore, your new (first sentence above) approach to gleaning
makes for a good traffic generation and resource consumption attack:
just send to the ETR a bunch of short encapsulated packets with
random or widely varying inner source addresses, knowing the ETR
will dutifully send off a mapping request for each one, and cache
the results whenever a response arrives.


> Not only do you want to verify the locator, but you want to get the
> other locators associated with the EID-prefix.

Yes - but there is no reason to be sure the ITR of the initial
packet is the ETR for that sending host.  You may have LISP defined
in this way, or recommended to be used in this way, but this reduces
the flexibility of deployment.  (In Ivip, there is no necessary
connection between ITRs and ETRs, and the ITR function can be
performed in the sending host - not behind NAT - if desired.)

Also, if the ITR was a Proxy Tunnel Router (the same as Ivip's
"anycast ITRs in the core/DFZ"), it won't be the ETR of the original
sending host.

Not all sending hosts will have EID addresses, of course, but I
think my suggested text above copes with that, since after a while,
the map requests for various non EID addresses would come back with
answers to the effect that large areas of the address space are not
EID space at all.  The ETR/ITR will cache that, and so will not need
to generate a mapping request for any sending host's address which
matches one of these "not EID" prefixes.

I see that your new (as far as I know) suggestion that the ETR probe
reachability to the presumed ITR does give it a head-start in
testing reachability to at least one possible - or likely - ETR, in
anticipation of the possible or likely event that it will soon act
as an ITR for a packet going back to the original host.

That could happen in parallel with the mapping request.

So by the time the mapping reply arrives, if the list of RLOCs
includes the address of this presumed ITR/ETR (the original packet's
outer source address, R1 in this example) then by then, you may have
verified that it is reachable.

Yet ....  if the packet was legitimate, then R3 already knows R1
device is up, because it just got a packet encapsulated by it!  I
guess there is still the question of whether R1 is reachable by R3,
which cannot be assumed from the now known reachability of R1 to R3.
 But in fact, even this reachability isn't assured, since the
original encapsulated Host-A -> HostB packet may have come via the
ALT network, not as an encapsulated packet direct from R1.

In a typical situation, where the packet is legitimate, R3 is the
ITR for HostB, when HostB is about to send a packet to HostA, you do
in fact save some time *if* you insist on checking reachability to
an ETR before sending any packets to it.  I wasn't aware that this
was a requirement of LISP.  If it is, then this would seem to
introduce a whole new set of delays and possible failure modes.

If you insist that no packet be encapsulated by R3 to R1 until it is
shown by the mapping reply to be one viable ETR (I agree with this)
AND until you have already verified that R3 can reach R1, THEN, you
have saved some time.  This is because the reachability probe occurs
in parallel with the mapping request-response.

But as described above, R3 will always send a probe with a nonce to
R1 if R1 is a novel address in terms of R3's knowledge of
reachability of ETRs. - irrespective of whether it will actually be
called upon to act as an ITR for a packet addressed to HostA.

I think it would be more sensible for R3 to wait for an actual
traffic packet to HostA before sending such a reachabilty probe.
Generally, the packet to HostA will be sent by HostB really quickly,
within milliseconds.  You could have R3 launch the reachability
probe to R1 then, which would still save a lot of time compared to
sending it after you receive the map reply.

By only probing R1 after R3 receives a packet addressed to HostA,
you protect yourself against R3 being used as part of an attacker's
scheme to pepper unwanted probe packets to wherever they like.
There is very little cost to achieve this benefit: the probe is sent
and the response received X milliseconds later, where X will
generally be a small single-digit number - however long it takes
HostB to reply to HostA.


But do you really require every LISP ITR to probe reachability of an
ETR before encapsulating a packet to it?  I guess if the mapping
only returns one ETR, then there is no point - you might as well
send the encapsulated traffic packet there, since there is no
alternative.

But LISP mapping will generally include 2 or more ETR addresses.

Do you require the ITR to probe one, then the other if it gets no
response, before sending a traffic packet?  Why not just send the
packet with a flag in the LISP header telling the ETR to acknowledge
its correct receipt?  (You can only do this once you have the
mapping, since the gleaned address is insecure - you can't send a
traffic packet there until you know it is one of the ETRs specified
in the mapping.)

If there are two equal priority ETRs in the mapping, do you require
the ITR to probe both of them, before sending a traffic packet?

I don't recall any such requirement.  If there is no such
requirement for probing reachability of an ETR before sending an
encapsulated traffic packet, then I see no point in gleaning the
presumed ITR's address (outer source address = R1 in this example).


>> do not contain the word "glean".
>>
>> Here is my understanding of gleaning, by way of an example:
>>
>>   HostA-->--R1==>==R2==>==R3-->--HostB
>>
>> HostA sends a packet to HostB.  HostB's address is within a
>> LISP-mapped EID prefix.  R1 functions as an ITR and (after gaining
>> the mapping information for HostB's address) encapsulates the packet
>> and tunnels it "==" to R3 which acts as an ETR.  The decapsulated
>> packet is sent to HostB.  (Also, perhaps R1 had no mapping, but the
>> packet gets to R3 via the ALT network.)
>>
>> As I understand it, "gleaning" involves R3, as an ETR, taking the
>> outer source address of the packet it received (R1's address) as an
>> RLOC location, presuming it to be the address of an ETR, and the
>> inner packet's source address (HostA's address) and presuming this
>> to be an EID.
> 
> Yes, so the Map-Reply that responds to the Map-Request also provides the
> EID-prefix associated with the inner SA (the source EID) from the
> invoking packet.

OK, so as I noted above, unless you require or desire ITRs to probe
ETR reachability before tunnelling packets to them, why should the
ETR/ITR R3 take any interest in R1's address?


>> The purpose is to have at least this gleaned mapping information:
>>
>>  EID (HostA's address) mapped to RLOC (R1's address)
>>
>> ready, without any delay due to mapping lookups, for the likely
>> event that HostB will soon send a packet right to left to HostA.
> 
> Right, but you get an unvalidated partial mapping that one has to decide
> if it wants to use. In our prototype, we have gleaning turned off by
> default, but when enabled, we also allow you to verify the glean. So if
> you turn that off, you use the glean information right away, otherwise
> you drop packets until the Map-Reply comes back.

So my critique is valid.

The gleaned address of R1 in the above example is completely
insecure and may be completely misleading (in terms of sending a
packet to HostA), even if it is the address of HostA's ITR, since
this is not necessarily a valid ETR address for HostA.  So this ITR
address cannot reasonably be used to determine where any traffic
packet is tunnelled to.  You must wait for the mapping information.

The very most this presumed ITR address could be used for is as a
putative ETR address, the reachability of which could be tested
while the mapping lookup is in progress.  But if you require that
ETRs be proven to be reachable before you send them any tunnelled
packets, I think you will run into problems including:

1 - A probe packet and a response must successfully make the full
    ITR <-> ETR journey before the ETR can encapsulate a traffic
    packet.  This adds a potentially very large delay to initial
    packets, which I think has not been discussed before.

2 - The ITR has to store more traffic packets, and watch out for
    more incoming reachability acknowledgements.

3 - You or the operator need to decide how long to cache this
    reachability information.  Do you probe the ETR ever ten
    seconds, or every ten minutes?

    Do you define that as a constant time for the whole LISP
    system, or do you make it controllable by the operator
    of the ITR.  Alternatively, do you extend the mapping
    information for each ETR address (each RLOC), to include such
    things as:

     a - Test or don't test for reachability before
         sending traffic packets.

     b - Cache time for that reachability information.

    The two could be combined - zero means don't test.


Still, this probe for reachability doesn't tell you anything new
about the ITR/ETR (R1 in this example) being up - you already know
it is up since it just tunnelled a packet to R3.

All it is testing is that R3 can send a packet to R1.

This probe for reachability doesn't tell you anything about the
ability of R1 to send a packet to HostA.  You know HostA can send a
packet to R1, so that is encouraging.  However, unless your probe is
more specific, asking R1 whether it can reach HostA, then you
haven't really proven you can get traffic packets to HostA via R1.

If you make the probe more specific, it will take longer and have a
more complex result.

R1 could reply that yes it is reachable from R3, but that no, it
can't send a packet to HostA.

Now life gets even more complex for R3s ITR function: it has to
cache this information for some time, however determined, but if
there is another HostC which uses the same R1 as its ITR/ETR, this
reachability probe for HostA doesn't tell you anything about
reachability to HostC.

An attacker could get good mileage out of this, sending a bunch of
phoney packets to R3, causing R3 to pepper R1 with a series of
reachability probes for endless separate addresses it is purportedly
the ETR for.

>> The basic draft-farinacci-lisp-06 document can be hard to
>> understand, because it primarily (or solely?) applies to LISP
>> variants 1.0 and 1.5.  Where do LISP-NERD and LISP-ALT fit into
>> this?  The reader is trying to construct a concrete understanding of
>> how NERD and ALT would work while reading multiple documents which
>> reference each other in general, but perhaps not in sufficient detail.
> 
> There is a datagram based mechanism to send and receive Map-Replies from
> the main spec. But how and where Map-Requests or Data Probes are sent,
> depends on the mapping database.

I understand a Data Probe is a traffic packet, sent by some means
towards the destination by some other system than ordinary
encapsulation to a known good ETR.  That alternative system is not
suitable for the majority of traffic, due to costs, limited
capacity, poorer reliability and/or especially delay.  However, it
can get the traffic packet to the correct ETR and at the same time
have that packet act as a mapping request - with the response
typically being sent back directly to the ITR rather than back
through the circuitous paths of the ALT network.

> So Data Probes are used in:
> 
> 1) LISP 1.0.
> 2) LISP-ALT
> 
> And Map-Requests only are used in:
> 
> 1) LISP-CONS
> 2) Gleaning
> 
> And both Data Probes and Map-Requests are used in:
> 
> 1) LISP-ALT
> 
> And Nerd doesn't use any Data Probe or Map-Request because the mapping
> data comes to you via the push mechanism.

OK.  This confirms my understanding, though I am not taking any
interest in LISP 1.0 and I am not sure which variants of LISP would
use gleaning.

I guess gleaning could be used with ALT or CONS, as discussed above,
where you are waiting for the mapping to arrive, and you figure the
gleaned ITR address (R1) is probably an ETR address which will be
one of those ETRs specified by the mapping - so you might as well
check its reachability while waiting the mapping to arrive.  But if
you don't get a response, you must delay the traffic packet even
after the mapping arrives, I think.  You would either try again, or
send a probe to another ETR and wait for a reply from that.  This is
a whole bunch of delays which I didn't know were part of LISP.

Gleaning could work with NERD, but it makes little sense to me.  You
might as well wait for the actual HostA -> HostB packet to arrive at
R3, which will typically be only a few milliseconds, rather than
rushing ahead and sending the probe immediately.


I think it would be good to rewrite the ID in respect of "gleaning".
 According to the present definition, gleaning MAY occur, but if it
does, the ITR's address is cached.  Yet the ITR address cannot
reasonably be used for any purpose other than a pre-emptive
reachability probe.  On its own, it can't be used as an address to
tunnel packets to.

Once you get the mapping reply, you definitely don't need the ITR
address - unless you have used it to establish reachability and this
address is one of those in the mapping reply.


So unless you require ITRs to check reachability before sending
traffic packets, and unless you seek to accelerate this process by
probing the gleaned "R1" address immediately, rather than wait a few
milliseconds (typically) for HostB to send a packet to HostA, then
you really don't need to "glean" this R1 address.

In that case, all you are "gleaning" is the fact that the ETR
received an encapsulated packet containing an inner source address
which is presumed to be worth generating a map request for.

Yet I think the time this saves would typically be so small as to
make it not worth doing, especially since you are not certain there
ever will be a packet addressed to the inner source address.

  - Robin

--
to unsubscribe send a message to rrg-request@psg.com with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg