Subject: Re: Issue 22: Part I: Handling ND cache getting full

From: Jonathan Wood <[email-masked]>
Date: Fri, 19 Sep 2003 09:44:53 -0700

On Friday, September 19, 2003, at 03:03 AM, Pekka Nikander wrote:

>
> Now, while I agree that Francis' suggestion makes it clearer
> when to accept new packets, I don't immediately see how it
> helps with the cache getting full.  On the other hand, if
> we start dropping the cache entries with the oldest RDlast,
> and at the same time temporarily reduce Delta so much that
> the dropped entries would not be accepted again, that might
> help.
>

I agree that this would help in a non-attack case, where you have
a host talking with many other hosts with poorly sync'd clocks.
However...

Maybe I just need some coffee this morning, but I still don't see how
this would prevent an attack. Even if you reduce the delta to a pretty
small value, on many link layers an attacker should still be able to
flush a victim's cache in less than 1 second, (for example, by using
a large number of pre-computed CGAs and flooding the victim with
NS msgs) and then execute a replay attack.

What am I missing?

-Jon

--------------------------------------------------------------------
To unsubscribe from this list, send email with "UNSUBSCRIBE" in the
body to <[email-masked]>.
Archive: http://standards.ericsson.net/lists/ietf-send/maillist.html
--------------------------------------------------------------------

---

From: Jari Arkko <[email-masked]>
Date: Sat, 20 Sep 2003 16:24:00 +0300

Pekka Nikander wrote:

> new message.  However, the new message will not pass
> the check since apparently her clock has drifted more than
> what is allowed.  That is, (RDnew - RDlast) is small due
> to the replayed message from which RDlast was recorded,
> but TSnew - TSlast will be much larger, since TSlast was
> the timestamp in the replayed message.
> 
> Consequently, I propose that we remove the latter check
> from the second rule, allowing TSnew to be any much larger
> than TSlast.  I don't see this opening any new attacks,
> and it fixes the scenario above.

At first I thought it was more serious, but the rule
for new nodes limits the starting time to be within
Delta of the real time. If that had not been the case,
an attacker could have replayed any old message, and
made it impossible for the real node to communicate
using its current time value.

Still, even with the new node rule we have the possibility
that the Delta difference is larger than the Drift difference,
making the attack you mention possible.

I agree about the the fix that you propose.

--Jari

---

From: Pekka Nikander <[email-masked]>
Date: Fri, 19 Sep 2003 13:03:28 +0300

Issue 22 deals with timestamp validity period and avoiding a
cache filling DoS attack.  For background, see
http://www.arkko.com/publications/send/issues/issue22.txt

My (perhaps flawed) analysis of the issue boils down to
two points:

   1. The value for the timestamp delta

   2. What to do if the ND cache becomes full

I'll describe these separate messages, focusing on the
full cache situation here.
-----------------------------------------------------------------

The current specifications states the following

 > o If the cache becomes full, the receiver SHOULD temporarily reduce
 >   the Delta value for that source address so that all messages
 >   within that value can still be stored.

Francis Dupont has proposed an alternative method for handling the
situation.  Trying to rephrase his suggestion:

   o Per each peer, store the following information:
     * the receive time of the last received ND message (RDlast)
     * the time stamp in the last received ND message (TSlast)

   o When a message is received from a new peer, i.e. one
     that is not stored in the cache, the received timestamp
     is checked and the packet is accepted if the timestamp
     is recent enough:

         -Delta < RDnew - TSnew < +Delta

     where RDnew is the local time of the received packet
     delivery and TSnew is the timestamp in the new packet.

     A new cache entry is created if the other checks, including
     the signature check, are passed.

   o When a message is received from a known peer, i.e. one
     that has an entry in the cache, the time stamp is
     checked against the last received message:

        TSnew > TSlast + (RDnew - RDlast) x (1 - drift)
        TSnew < TSlast + (RDnew - RDlast) x (1 + drift)

     The suggested value for /drift/ is 10%, allowing clock skew
     of at most 10% between the hosts.

     If TSnew < TSlast, which is possible if packets arrive
     rapidly and out of order, TSlast MUST NOT be updated, i.e.,
     the stored TSlast for a given host MUST NOT ever decrease.

Opinions?

Any flaws in my analysis?

--Pekka Nikander

---

From: Pekka Nikander <[email-masked]>
Date: Fri, 19 Sep 2003 13:41:49 +0300

It is silly to reply to oneself, but I noticed a potential
problem after sending the initial message.

>         -Delta < RDnew - TSnew < +Delta
....
>        TSnew < TSlast + (RDnew - RDlast) x (1 + drift)

Doesn't this open a potential replay attack against a
new node that arrives to a link.

Let us assume that an attacker is on the link, and collects
ND messages.   Let us further assume that one node on the
link, say Alice, changes its link layer address.

Now a new node, say Bob arrives to the link, within the
Delta time from Alice changing her address.

If the attacker notices Bob arriving before Alice, it can
Alice's earlier recorded message that still uses the old
link layer address.  This causes Bob to record TSlast and
RDlast from the message, together with the old link layer
address

When Alice now notices Bob's arrival, she will send a

--Pekka Nikander