Subject: [DNSOP] draft-fujiwara-dnsop-nsec-aggressiveuse-01.txt

From: [email-masked]
Date: Tue, 07 Jul 2015 18:20:43 +0900 (JST)

Akira Kato and I submitted draft-fujiwara-dnsop-nsec-aggressiveuse-01.

  https://datatracker.ietf.org/doc/draft-fujiwara-dnsop-nsec-aggressiveuse/

* Added reference to DLV {{RFC5074}} and imported some sentences.
* Added Aggressive Negative Caching Flag idea.
* Added detailed algorithms in Appendix.

Please check and comment.

I made a mistake at detailed algorithm part in -01.
I added updated version in this mail and I will update the draft.
NSEC3 validation is difficult for me.
Please check this algorithm.

And where is the pseudo code writing guide ?

~~~~~~~~~~~
QNAME = the query name;
if (QNAME name entry exists in the cache) {
    resolve the query as usual;
    // if RRSet (query name and query type) exists in the cache,
    //     the resolver responds the RRSet from the cache
    // Otherwise, the resolver needs to iterate the query.
}

// Find closest enclosing NS RRset in the cache.
// The owner of this NS RRset will be a suffix of the QNAME
//    - the longest suffix of any NS RRset in the cache.
SIGNER = closest enclosing NS RRSet of QNAME in the cache;

if (SIGNER zone does not have a special NSEC/NSEC3 data structure) {
    Resolve the query as usual;
}

if (SIGNER zone is not signed or not validated) {
   Resolve the query as usual;
}

if (SIGNER zone is signed with NSEC) {
    // NSEC mode
    if (covering NSEC RR of QNAME at SIGNER zone
       doesn't exist in the cache) {
        Resolve the query as usual.
    }

    TEST = Find the longest existing domain name of QNAME
           from the covering NSEC RR;

    if (*.TEST name entry exists in the cache) {
        the resolver can generate positive response
        or resolve the query as usual;
    }
    if covering NSEC RR of "*.TEST" at SIGNER zone exists
         in the cache {
        the resolver can generate negative response;
    }
    // Lack of information, need to resolve the query as usual
} else
if (SIGNER zone is signed with NSEC3 and does not use Opt-Out) {
    // NSEC3 mode

    TEST = SIGNER;
    while (TEST != QNAME) {
        // if any error happens in this loop, break this loop
        UPPER = TEST;
        add a label from the QNAME to the start of TEST;
          // TEST = label.UPPER
        if (TEST name entry exist in the cache) {
            continue; // need to check rest of QNAME
        }
        if (covering NSEC3 of TEST exist in the cache) {
            // (non-)terminal name TEST does not exist
            if (*.UPPER name entry exist in the cache) {
                // TEST does not exist and *.UPPER exist
                the resolver can generate positive response;
            } else
            if (covering NSEC3 of *.UPPER exist in the cache) {
                // TEST does not exist and *.UPPER does not exist
                the resolver can generate negative response;
            }
            break; // Lack of information
        } else
        if (NSEC3 of TEST does not exist in the cache) {
            break; // Lack of information
        }
        // TEST label exist, then need to check rest of QNAME
    }
    // Lack of information, need to resolve the query as usual
}
Resolve the query as usual
~~~~~~~~~~~
--
Kazunori Fujiwara, JPRS <[email-masked]>

---

From: Bob Harold <[email-masked]>
Date: Tue, 7 Jul 2015 12:09:35 -0400

On Tue, Jul 7, 2015 at 5:20 AM, <[email-masked]> wrote:

> ...

> I am concerned that the "AN" flag allows for easy zone walking, defeating
the purpose of minimal range NSEC records.  So I don't think authoritative
servers would want to respect it.

I am also concerned that random subdomain queries will set the CD bit, if
that avoids aggressive negative caching.  So I would think that the CD bit
should not be allowed to stop aggressive negative caching.

-- 
Bob Harold

---

From: [email-masked]
Date: Wed, 08 Jul 2015 18:19:12 +0900 (JST)

> From: Bob Harold <[email-masked]>

It's the problem.
However, authoritative DNS servers can detect random subdomain attacks.
They can generate NSEC resource records with wider range
under random subdomain attacks.

> should not be allowed to stop aggressive negative caching.

Thanks.
I will add.

Regards,

---

From: 神明達哉 <[email-masked]>
Date: Fri, 10 Jul 2015 11:53:30 -0700

> Please check and comment.

The primarily intended benefit of this approach seems to mitigate a
DoS attack on a resolver (e.g., according to Section 3).  But I'm
skeptical about the effectiveness in that context: for this mitigation
to work the zone in question needs to be DNSSEC-signed.  But an
attacker would be easily able to find unsigned zone to use for the
attack, and they could even set up an unsigned zone they can control.
Also, an equally effective attack is possible without relying
non-existent names: an attacker would only find some wildcard name and
send random queries that match the wildcard.  So, if the proposed
approach is really effective to "random (non-existent) sub-domain
attacks", attackers would simply move to a variant of it that would
still work.  So, in the end, a resolver would still employ counter
measures like rate limiting (which will work for both types of random
name attacks, and will work for unsigned zones), and, if it's
reasonably effective, the defense using "nsec-aggressiveuse" won't be
that promising.

That said, I wouldn't necessarily be opposed to the idea itself.  It
might still be some nice-to-have optimization for resolver
performance, and if so, it's probably worth pursing.

In Introduction it states:

   While negative (non-existence) information of DNS caching mechanism
   has been known as DNS negative cache [RFC2308], it requires exact
   matching in most cases.  [...]
   This was because the NXDOMAIN response just says
   there is no such name "a.example.com" and it doesn't tell anything
   for "b.example.com".

While I see what it tries to say and don't disagree with it, I think
this is not very accurate.  In fact, NXDOMAIN for "a.example.com" says
there is no such name *or any subdomain of it*.  So it would still be
usable to suppress unnecessary external query for, e.g.,
foo.a.example.com.

Regarding Section 5 (possible side effect on root servers), I wonder
about the implication of qname-minimization (which I expect will be
deployed much sooner than this proposal).  A resolver that supports
qname-minimization would first send a query to "local." to the root
server upon receiving a "foo.local" query, and cache the result of
NXDOMAIN for "local.".  It will suppress subsequent external queries
for any subdomain of it.

--
JINMEI, Tatuya

---

From: Shumon Huque <[email-masked]>
Date: Mon, 13 Jul 2015 22:01:29 -0400

On Fri, Jul 10, 2015 at 2:53 PM, 神明達哉 <[email-masked]> wrote:

> [...]

That's indeed the literal meaning of NXDOMAIN, but it turns out most
current resolver implementations don't treat it that way. The wording in
RFC2308, Section 5 is not entirely precise, but it seems to say that
negative answers should be cached only for the exact qname, and not
(necessarily) for anything below it.

Section 3 of http://tools.ietf.org/html/draft-vixie-dnsext-resimprove-00
("Stopping Downward Cache Search on NXDOMAIN") proposed to fix this
resolver behavior. It would be great if this was standardized and adopted.

> NXDOMAIN for "local.".  It will suppress subsequent external queries

Yes, this will certainly be a very beneficial result of qname minimization.

Shumon.

---

From: Mark Andrews <[email-masked]>
Date: Tue, 14 Jul 2015 13:03:18 +1000

In message <CAHPuVdU-1e_7KPH9JdSvbPn-tYptaXbHrQvQz=[email-masked]>
, Shumon Huque writes:
> 
> On Fri, Jul 10, 2015 at 2:53 PM, =E7=A5=9E=E6=98=8E=E9=81=94=E5=93=89 <jinm=
> [email-masked]> wrote:
>

Because the consensus at the time was not to support nxdomain
synthesis from signed zone (speaketh the author of RFC 2308).

Extreme care needs to be taken with nxdomain synthesis. You need
to choose the correct NSEC records especially for qnames which are
the subdomain of the NSEC owner name.  The NS bit MUST NOT be set
in this case as the presence of the NS bit indicates a delegation.

NSEC3 is even more complicted.

DLV is only defined to use NSEC signed zones as I wasn't interested
in having to working out all the rules for NSEC3.

-- 
Mark Andrews, ISC
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: [email-masked]

---

From: 神明達哉 <[email-masked]>
Date: Tue, 14 Jul 2015 10:00:49 -0700

At Mon, 13 Jul 2015 22:01:29 -0400,

> (necessarily) for anything below it.

Ah, yes, thanks for pointing it out.  I don't know or didn't check
other resolver implementations, but BIND 9 certainly behaves that way.
I should have known this, but I guess I was confused about the
"meaning of NXDOMAIN", the behavior of authoritative server
implementations and the behavior of recursive server implementations.

> Yes, this will certainly be a very beneficial result of qname minimization.

And the same remark should apply here, too.  We'd need "Stopping
Downward Cache Search on NXDOMAIN" in addition to qname minimization
for this to work.

--
JINMEI, Tatuya

---

From: Shumon Huque <[email-masked]>
Date: Tue, 14 Jul 2015 13:13:23 -0400

> Downward Cache Search on NXDOMAIN" in addition to qname minimization

I think we can distinguish the negative caching algorithm and the iterative
resolution algorithm.

The current iterative resolution algorithm already interprets NXDOMAIN
literally (unlike negative caching), so I don't think we need to explicitly
say this for the qname minimization variant of iterative resolution either.
However, I suppose there's no harm in adding explicit text around this
point.

Shumon Huque

---

From: [email-masked]
Date: Wed, 15 Jul 2015 20:02:07 +0900 (JST)

Thanks to Jinmei, Shumon and Mark.

> From: 神明達哉 <[email-masked]>

I will add some text in next revision.

> From: Shumon Huque <[email-masked]>

> From: Mark Andrews <[email-masked]>

I will add texts to update RFC 2308.

> NSEC3 is even more complicted.

YES.

> in having to working out all the rules for NSEC3.

I think the procedure is the same as NSEC3 validation.

# and qname minimization discussion is interesting.
# It may be listed in draft-ietf-dnsop-root-loopback 
# as a different approach.

---

From: Casey Deccio <[email-masked]>
Date: Wed, 15 Jul 2015 16:25:01 -0400

Hi,

Some thoughts below, strictly on the NSEC/NSEC3 algorithm.  They're quite
rough, but hopefully they're useful.

Cheers,
Casey

> Please check this algorithm.

Several times, the phrase "query as usual" is used.  However, something
might need to be said about the resolver modifying "query as usual" to save
NSEC/NSEC3 records associated with wildcard and negative responses in a way
that they can be used by the algorithm.

For example, the following indexes could be maintained:

Indexes:
NSEC_TABLE = a canonically ordered mapping of NSEC owner names to NSEC
records, grouped by corresponding SOA name
NSEC3_TABLE = a canonically ordered mapping of NSEC3 owner names to NSEC3
records, grouped by corresponding SOA name and NSEC3 parameters
NSEC3_NAMES = a canonically ordered mapping of names to their corresponding
NSEC3-hashed names (or records)

QNAME = the query name;
> SIGNER = closest enclosing NS RRSet of QNAME in the cache;

You should now find the SOA record corresponding to SIGNER.  If there is no
SOA record in cache, then there are no previously cached negative
responses, so you can resolve the query as usual.

>     Resolve the query as usual;

I'm not sure what this means.

>    Resolve the query as usual;

You mean here: if the SOA record is not validated (signed is implied by
validated).

While colloquially we talk about zones being signed, in this case, you want
an actual RRset--one that matters at that.  The SOA record fits the bill
here because of its role with negative responses.

> if (SIGNER zone is signed with NSEC) {

While in theory a zone is signed with either NSEC or NSEC3, in practice all
that matters is the NSEC or NSEC3 proofs provided in individual responses.
While not necessarily desirable, it is entirely possible that subsequent
responses could different NSEC/NSEC3 results.  Therefore, for algorithm
robustness, checking whether a zone is signed with NSEC or NSEC3 is less
useful than simply looking at both NSEC and NSEC3 records in the cache.

I would eliminate "if SIGNER zone is signed with NSEC" and its
corresponding "else"/"else if" altogether.  You should really check both
NSEC and NSEC3.

BEGIN NSEC SECTION

>         Resolve the query as usual.

s/Resolve the query as usual/Go to NSEC3 SECTION/

>            from the covering NSEC RR;

You could use the term "closest encloser"/CLOSEST_ENCLOSER instead of
"longest existing domain name"/TEST.

>         or resolve the query as usual;

s/resolve the query as usual/Go to the NSEC3 SECTION

It could be a NODATA response (which is a negative response), if the type
doesn't exist.  Although, I think that's what you mean by "positive
response or resolve the query as usual".

>         the resolver can generate negative response;

s/resolver can generate negative response/Return synthesized negative
response/

>     // Lack of information, need to resolve the query as usual

No. move on to NSEC3 now.

Eliminate this "else if SIGNER zone is signed with NSEC3 and does not use
Opt-out" check too.

BEGIN NSEC3 SECTION

    TEST = SIGNER;

Again, I would look for closest encloser (CLOSEST_ENCLOSER) here (e.g.,
using the NSEC3_NAMES table).  There might be multiple NSEC3 records for a
single closest encloser if multiple sets of NSEC3 parameters are used
across different responses, but really all you need is one.  In this case,
you would need to iterate through the different sets of NSEC3 parameters.

Once you have the closest encloser, the algorithm looks more (but not
entirely) like the NSEC portion above, but with NSEC3 instead.  I'm not
sure I follow the logic in the previously written NSEC3 section.  I've made
some modifications below.

   if (no CLOSEST_ENCLOSER is found) {
        Go to FALLBACK SECTION
    }

NEXT_CLOSEST_ENCLOSER_PROOF_FOUND = False
 for each set of parameters corresponding to NSEC3 names in the appropriate
zone {
    if (there is a NSEC3 RR covering the next closest encloser (i.e.,
CLOSEST_ENCLOSER + one label)) {
      NEXT_CLOSEST_ENCLOSER_PROOF_FOUND = True
    }
  }
  if ! NEXT_CLOSEST_ENCLOSER_PROOF_FOUND {
    Go to FALLBACK SECTION
  }

 WILDCARD_PROOF_FOUND = False
 for each set of parameters corresponding to NSEC3 names in the appropriate
zone {
    if (*.CLOSEST _ENCLOSER name entry exists in the cache) {
        the resolver can generate positive response
        or Go to FALLBACK SECTION;
    }

    if covering NSEC3 RR of "*.NEXT_CLOSEST_ENCLOSER" exists
         in the cache {
        WILDCARD_PROOF_FOUND = True
    }
   }

  If WILDCARD_PROOF_FOUND {
    Return synthesized negative response
  }

BEGIN FALLBACK SECTION