Subject: NSEC synthesis and the NSEC Next Domain Name field

From: Don Stokes <[email-masked]>
Date: Fri, 11 Jun 2004 11:32:43 +1200

Folks,

If one is to synthesise NSEC records, either online, or staticly in
"NSEC white lies" the recent draft put it, what should one place in the
Next Domain Name field of the NSEC record?

As things stand, it appears that given a name "x.example.", then the
very next name that could be created in given the canonical ordering
rules would be "\001.x.example.".

However, that doesn't sit nicely (although this might not be a problem)
when x.example is a delegation; one doesn't really want "fake" NSEC
records pointing at subdomains that don't exist, e.g.

	x.example.	NS	ns1.example.com.
			NS	ns2.example.com.
			NSEC	\001.x.example. NS RRSIG NSEC

as \001.x.example is out of bailiwick.  The "next" name at the same
level as x.example would be "x\001.example.".

What happens if you get:

	x.example. 	NSEC 	x.example. ...

Could replaying that NSEC record be used to (e.g.) forge a denial of
y.example.?

What I'm looking for is a standard, canonical way of saying, "this name,
and only this name, does not exist", preferably without reference to
other data.

Is this a special case for the NSEC Next Domain Name field, or can it
reliably be fudged?  Could the field be given a value that meant "there
is no next domain name field; this NSEC only refers to the name
queried"?

-- don

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>

---

From: Don Stokes <[email-masked]>
Date: Sat, 12 Jun 2004 17:32:10 +1200

Paul Vixie <[email-masked]> wrote:
>> Or would just:
>> 
>> example. NSEC example.
>> 
>> suffice?
>
>this is my preference, but i admit i don't know whether the current -bis
>spec requires that either an NSEC owner or target name, or both, actually
>does exist.  certainly the expectation is that the owner name exists, which
>is why there's a list of RRtypes in the NSEC rdata.  but as to whether the
>validation model actually requires such existence, i don't know.  would an
>NSEC asserting that no RRtypes were present at its owner name be valid?

I don't understand.  Is this in response to a query for "x.example." or
"example."?  If the former, then that could be used in a replay attack.

I can't see anything in the current drafts that says what one should do
when the Next Domain Name field is the same as the Name, other than at
the zone apex.  The latter situation can turn up, e.g.

	foo.example.	SOA	...
			NS	...
			A	...
			NSEC	foo.example. SOA NS A NSEC ...

In this case, the NSEC record says, "There are these RRsets for
foo.example, but there is nothing else in or below this zone."  By
extension, and I think some explicit wording in the -protocol doc would
be required for this, one could interpret "foo.example. NSEC foo.example
NSEC RRSIG" as meaning that there are no RRSETS for foo.example, *nor
anything below it* other than the NSEC & RRSIG.

Note that -protocol, section 2.3 states:

   An NSEC record (and its associated RRSIG RRset) MUST NOT be the only
   RRset at any particular owner name.  

That rule would have to be relaxed for this interpretation, or indeed to
allow NSEC records to be dynamically generated at all.

Note too that this approach doesn't cater for the situation where
bar.foo.example. exists; the "foo.example. NSEC foo.example. NSEC RRSIG"
response could be replayed to deny the existence of bar.foo.example. 
You'd need to respond with something like "foo.example. NSEC
\001.foo.example. NSEC RRSIG" to say "just foo.example, and not anything
below that".

So, if one were going to generate signed NSEC records on the fly, one
would have to do something like the following:

For any name in the zone that exists, at zone build time, generate either:

	<name> NSEC <name> <existing-rrsets> NSEC RRSIG
or
	<name> NSEC \001.<name) <existing-rrsets> NSEC RRSIG

The latter case is required if there are any names below <name>, but
should (must?) not be used if <name> is a delegation point.

When asked for a name that does not exist, generate (on the fly), sign
and return:

	<name> NSEC \001.<name> NSEC RRSIG

unless one knows that there are no names below <name, in which case you
could use <name> instead of \001.<name>.

Alternatively, one could generate in all cases:

	<name> NSEC <null> NSEC RRSIG

where <null> is an as yet undefined magic value that says, "there is no
next domain name field", possibly even using one of the reserved values
of the label type field, e.g a byte value of 0xA0.

Is this what others are thinking for dynamic synthesis?  Or have I got
it all wrong?

-- don

---

From: Don Stokes <[email-masked]>
Date: Sat, 12 Jun 2004 23:44:19 +1200

Paul Vixie <[email-masked]> wrote:
>geoff sisson proposes that servers who care deeply about zone walking and
>who can't afford the crypto hardware nec'y for NSEC synthesis just keep a
>general purpose NSEC sitting around, like one at the first non-apex domain
>name with a target of the apex, and just use this on all NXDOMAIN responses.
>this clearly "proves" that all names do not exist, even if they do, but
>since the only valid use for such an NSEC is to validate an NXDOMAIN or
>NOERROR response, nobody is actually allowed to care whether the names
>that NSEC "proves" do not exist, actually don't exist.  the danger is
>replay, but geoff says he's willing to trade that risk off against others.

I'm thinking about that.  It gives me the shivers, because I'm not sure
about all the corner cases.  For example, if a TLD has (excluding
RRSIGs):

	example.	SOA ... 
			...
	\001.example.	NSEC	example. NSEC RRSIG  ; For denials
			...
	foo.example.	NS	ns1.example.com.
			DS	...
			NSEC	\001.foo.example. NS DS NSEC RRSIG
			...

and an attacker forges:

	foo.example.	NS	hostile.example.net.

in response to a query for name.foo.example, a security aware resolver
might ask <foo.example. DS ?> and be met with the "denial" NSEC:

	\001.example.	NSEC	example. NSEC RRSIG

"proving" the DS doesn't exist.  Now, that should also be taken as
proving that the NS doesn't exist as well, invalidating the cached NS
records, however, I can see buggy implementations forced by an attacker
into doing this in two phases missing that and interpreting the
"missing" DS as an unsecured delegation to hostile.example.net. 

Maybe I'm just too pessimistic. 

>the reason i mention all of this is, an NSEC says nothing about zone content,
>it's only a way to prove the nonexistence of a qname or <qname,qtype>.
>there can be other existing and populated names within the range given,
>and that's not a problem.  as long as the range given "covers" the qname,
>then the NSEC is a valid response.

I take the point about caching of NSEC records, and agree that at least
in the short term, nothing more than the status of the query should be
inferred from them.  However, the presence of a cached NSEC record
indicates the non-existence of the intervening names, and I'd like to
see the door kept open to using that information in the future. 

Consider: if the root has a valid NSEC chain, then a forwarder faced
with lots of queries for <something>.localdomain" will soon get:

	lk.	NSEC lr. ...

from the root servers and could answer all "localdomain" queries with
that.  Once all the corner cases are worked out, I think this could be
quite valuable.

Allowing NSECs to cover existing records would close the door on using
cached NSECs in this way, and I think such NSECs should be disallowed
from the outset.

Personally, I think that DoS avoidance in NSEC synthesis, even if one
doesn't have crypto gear aboard, can be achieved to a large degree
by queueing all requests for records that don't exist to a low-priority
NSEC synthesis process via a fixed-length queue.  If the queue is full,
just drop new queries on the floor.  They'll get retried, probably to other
servers, and the worst case is that legitimate lookups for things that
don't exist anyway will time out.  One would still have static NSECs for
things that do exist, which are a lot more important, and appropriate
caching of synthesised NSECs could also mitigate such attacks.  (I'm
figuring that in real life, most legitimate denials will be for a small
number of domains, so a usage-weighted cache would mean that queries to
common non-existent domains would get cached synthesised NSECs even if
the crypto process was totally swamped.)

>> By extension, and I think some explicit wording in the -protocol doc
>> would be required for this, one could interpret "foo.example. NSEC
>> foo.example NSEC RRSIG" as meaning that there are no RRSETS for
>> foo.example, *nor anything below it* other than the NSEC & RRSIG.
>
>i would not interpret it that way at all.  "empty nonterminals" and all.

By "below" I meant below it in the tree, not in the (ordered) zone.

>by the resolution and validation rules as i understand them at this moment,
>the zone cut would trump the NSEC.  in other words you'd get a delegation
>rather than an NXDOMAIN, and the content of the "latter case" NSEC target
>would never be relevant.  and as before, if you can't enforce it, don't
>make it a rule.

Fair enough.  Might pay to make "delegation trumps NSEC" an actual rule
tho.

>that's most intriguing.

It would make synthesis, or just plain lying, a lot tidier.  

Using the reserved label code points (01 or 10) would set a precedent,
so should be thought through carefully, but if they are introduced as
part of the definition of NSEC, shouldn't pose a problem.  I think the
effect of using 0xA0 would be to make code point 10 effectively mean
"arbitrary values"; future developments might find uses for 0xA1 and
so-on through to 0xBF.  That still leaves code point 01 reserved.

Other possibilities for <null> include:

- a "magic" name, eg "NULL."  Yuck.

- The root.  Nice and small, but might complicate things with the real
root.

- A compression pointer with an offset of 0, i.e. 0xC000.  This "can't
happen" even if compression is allowed (which it isn't in an NSEC),
because the offset is relative to the start of the message, which will
be the message header.  Therefore 0xC000 will never turn up in a real
compressed name.

I think I prefer the reserved code point approach myself.

-- don

---

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Sat, 12 Jun 2004 07:41:50 -0700

This thread on dynamic signing of NSEC records is pointless.

If you tool up to do this you might as well just sign every response. That
would allow the entire protocol stack to be dramatically simplified.

You could even go one stage further and do ephemeral key exchange then
authenticate the responses via MACs.

> -----Original Message-----
> From: [email-masked]
> [mailto:[email-masked]]On Behalf Of Don Stokes
> Sent: Saturday, June 12, 2004 7:44 AM
> To: [email-masked]
> Subject: Re: NSEC synthesis and the NSEC Next Domain Name field 
> 
> 
>

---

From: Ólafur Gudmundsson/DNSEXT co-chair <[email-masked]>
Date: Sat, 12 Jun 2004 17:18:43 -0400

At 11:57 12/06/2004, Paul Vixie wrote:

>i honestly cannot figure out whether this thread belongs on namedroppers
>or dnssac@cafax.  apologies to our chairs if i'm getting it wrong -- no
>disrespect is intended.

[email-masked] please.

         Olafur