Subject: Closing issues 11 and 22: Nonce and timestamp management

From: Pekka Nikander <[email-masked]>
Date: Tue, 14 Oct 2003 13:01:38 +0300

I have now tried to edit in the results of the dicussions
on Issues 11 and 22.  It has resulted in a new combined
section for the Nonce and Timestamp options, and an
appendix discussing the issue somewhat longer.

I am including the new text below.  If there are no comments,
I will consider these issues closed.

--Pekka Nikander

5.4 Timestamp and Nonce options

5.4.1 Timestamp Option

  <structure same as before>

5.4.2 Nonce Option

  <structure same as before>

5.4.3 Processing rules for senders

    All solicitation messages MUST include a Nonce.  All solicited-for
    announcements MUST include a Nonce, copying the nonce value from the
    received solicitation.  When sending a solication, the sender MUST
    store the nonce internally so that it can recognize any replies
    containing that particular nonce.

    All NDP messages MUST include a Timestamp.  Senders SHOULD set the
    Timestamp field to the current time, according to their real time
    clock.

    If a message has both Nonce and a Timestamp options, the Nonce option
    MUST precede the Timestamp option in order.

5.4.4 Processing rules for receivers

    The processing of the Nonce and Timestamp options depends on whether
    a packet is a solicited-for advertisement or not. A system may
    implement the distinction in various means. Section 5.4.4.1 defines
    the processing rules for solicited-for advertisements.  Section
    5.4.4.2 defines the processing rules for all other messages.

    When there is a very large number of hosts on the same link, or when
    a cache filling attack is in progress, it is possible that the cache
    holding the most recent timestamp per sender becomes full.  In this
    case the node MUST remove some entries from the cache or refuse some
    new requested entries.  The specific policy as to which entries are
    preferred over the others is left as an implementation decision.
    However, typical policies may prefer existing entries over new ones,
    CGAs with a large Sec value over smaller Sec values, and so on.  The
    issue is briefly discussed in Appendix C.

5.4.4.1 Processing solicited-for advertisements

    The receiver MUST verify that it has recently send a matching
    solicitation, and that the received advertisement does contain a
    copy of the Nonce sent in the solicitation.

    If the message does not contain a Nonce option, it MAY be
    considered as a non-solicited-for announcement, and processed
    according to Section 5.4.4.2.

    If the message does contain a Nonce option, but the Nonce value is
    not recognized, the message MUST be silently dropped.

    If the message is accepted, the receiver SHOULD store the receive
    time of the message and the time stamp time in the message, as
    specified in Section 5.4.4.2

5.4.4.2 Processing all other messages

    Receivers SHOULD be configured with an allowed timestamp Delta value
    and an allowed clock drift parameter.  The recommended default value
    for the allowed Delta is 3,600 seconds (1 hour) and 1% for clock
    dritf.

    To facilitate timestamp checking, each node SHOULD store the
    following information per each peer:

       The receive time of the last received, acepted ND message.  This
       is called RDlast.

       The time stamp in the last received, accepted ND message.  This is
       called TSlast.

    Receivers SHOULD then check the Timestamp field as follows:

    o  When a message is received from a new peer, i.e., one that is not
       stored in the cache, the received timestamp, TSnew, is checked and
       the packet is accepted if the timestamp is recent enough with
       respect to the receival time of the packet, RDnew:

         -Delta < (RDnew - TSnew) < +Delta

        The RDnew and TSnew values SHOULD be stored into the cache as
       RDlast and TSlast.

    o  If the timestamp is NOT within the boundaries but the message is a
       Neighbor Solicitation message that should be responded to by the
       receiver, the receiver MAY respond to the message.  However, if it
       does respond to the message, it MUST NOT create a neighbor cache
       entry.  This allows hosts that have large difference in their
       clocks to still communicate with each other, by exchanging NS/NA
       pairs.

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

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

    o  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.  Otherwise TSlast SHOULD
       be updated.  RDlast MUST be updated in any case.

----------------------------

Appendix C. Cache Management

    In this section we outline a cache management algorithm that allows a
    host to remain partially functional even under a cache filling DoS
    attack.  This appendix is informational, and real implementations
    SHOULD use different algorithms in order to avoid he dangers of
    monocultural code.

    There are at least two distinct cache related attack scenarios:

    1.  There are a number of hosts on a link, and someone launches a
        cache filling attack.  The goal here is clearly make sure that
        the hosts can continue to communicate even if the attack is going
        on.

    2.  There is already a cache filling attack going on, and a new host
        arrives to the link.  The goal here is to make it possible for
        the new host to become attached to the network, inspite of the
        attack.

    From this point of view, it is clearly better to be very selective in
    how to throw out entries.  Reducing the timestamp Delta value is very
    discriminative against those hosts that have a large clock
    difference, while an attacker can reduce its clock difference into
    arbitrarily small.  Throwing out old entries just because their clock
    difference is large seems like a bad approach.

    A reasonable idea seems to be to have a separate cache space for new
    entries and old entries, and under an attack more eagerly drop new
    cache entries than old ones.  One could track traffic, and only allow
    those new entries that receive genuine traffic to be converted into
    old cache entries.  While such a scheme will make attacks harder, it
    will not fully prevent them. For example, an attacker could send a
    little traffic (i.e. a ping or TCP syn) after each NS to trick the
    victim into promoting its cache entry to the old cache.  Hence, the
    host may be more intelligent in keeping its cache entries, and not
    just have a black/white old/new boundary.

    It also looks like a good idea to consider the sec parameter when
    forcing cache entries out, and let those entries with a larger sec a
    higher chance of staying in.

--------------------------------------------------------------------
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: Jonathan Wood <[email-masked]>
Date: Tue, 14 Oct 2003 20:25:25 -0700

This looks good to me - one question, and one minor editorial
comment:

On Tuesday, October 14, 2003, at 03:01 AM, Pekka Nikander wrote:

<...>

>    MUST precede the Timestamp option in order.

Why require ordering? (Also note that RFC 2461 section 9 says
"Options in Neighbor Discovery packets can appear in any order;
receivers MUST be prepared to process them independantly of
their order")

>    issue is briefly discussed in Appendix C.

[Editorial]
This paragraph jumps right into a cache discussion with no context;
It may be clearer to start with something like "A implementation may 
utilize
some mechanism such as a timestamp cache to strengthen resistance to
replay attacks."

Jonathan

---

From: Pekka Nikander <[email-masked]>
Date: Wed, 15 Oct 2003 09:56:07 +0300

> receivers MUST be prepared to process them independantly of

Well, having the Nonce before the Timestamp would make processing
at the receiving end easier.  But if RFC 2461 says otherwise
(I was unaware of the clause), then apparently we shouldn't
mandate.  I changed the text to read as follows:

   If a message has both Nonce and Timestamp options, the
   Nonce option SHOULD precede the Timestamp option in order.
   The receiver MUST be prepared to receive them in any order,
   as per RFC 2461 Section 9.

Better?

>> 5.4.4 Processing rules for receivers
...
>>    a cache filling attack is in progress, it is possible that the cache
....
> some mechanism such as a timestamp cache to strengthen resistance to

Thanks, I added your suggested sentence (with s/^A/An/)

--Pekka

---

From: Jonathan Wood <[email-masked]>
Date: Wed, 15 Oct 2003 11:52:07 -0700

Looks good.