Subject: Re: NSEC synthesis and the NSEC Next Domain Name field

From: Paul Vixie <[email-masked]>
Date: Sat, 12 Jun 2004 06:21:57 +0000

> >> example. NSEC example.
> >
> >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.

it would only be for the latter, since it wouldn't cover the former's name.

> 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."

i know it seems that way, but actually that's not what it says at all.  an
nsec in a zone file says nothing.  an nsec in a response says that the qname
or <qname,qtype> doesn't exist and proves this by signing an NSEC RR that
has an owner<--->target range which includes the qname, and an rrtype list
that possibly includes the qtype.  it is valid for the zone to contain:

	$ORIGIN foo.example.
	@	SOA	...
		NSEC	A
	A	NSEC	D
	B	A	...
	D	NSEC	@

if you ask for <qname=A,qtype#NSEC> you'll get <A NSEC D>.
if you ask for <qname=B,qtype=A> you'll get <B A ...>.
if you ask for <qname=B,qtype#A> you'll get <A NSEC D> again.
if you ask for <qname=C> you'll get <A NSEC D> again.

i guess i was just being silly earlier.  of course the owner name exists,
even if it's synthetic.  after all, there's an NSEC there.  the target name
need not exist, it just has to not be below the owner name in "DNSSEC sort
ordering" unless it's wrapping back around to the apex.  and it really ought
to be an in-baliwick name (at or below the same zone apex as the owner name).

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.

(geoff, i'm not clear on how this proposal applies to NOERROR responses.)

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 guess the single NSEC RR needed for this is just <@ NSEC @>, right?
if so then it's a strange case.  <A NSEC A> talks only about a single
name "A", but "<@ NSEC @>" talks about all possible names below this
apex.  that seems like a strange exception case.  perhaps <A NSEC A>
should also refer to the entire zone, and your <A NSEC \001.A> example
(given below) should be used to refer only to "A".

> 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.

> 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.

that rule should be relaxed in any case, since it's unenforceable.  to show
you what i mean, consider that a synthetic NSEC RR doesn't actually exist
(and indeed, due to the salting nec'y to prevent key attacks, you might not
ever see the same synthesized RRSIG(NSEC) twice, even for same-qname's).
if it doesn't exist, then it's not really "at any particular owner name"
and so the rule is satisfied even though, between you and me and the lamp
post, it's actually not.  but if you can't enforce it, it's not a "rule."

> 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".

ouch.  you're right.

> 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.

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.

> When asked for a name that does not exist, generate (on the fly), sign
> and return:
> 
> 	<name> NSEC \001.<name> NSEC RRSIG

right.

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

maybe.  it's possible that "name NSEC name" refers to the entire zone, due
to the kind of wrapping that would normally only be done around the apex.

> 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.

that's most intriguing.

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

other than as noted above, i found your analysis very insightful.

--
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: Paul Vixie <[email-masked]>
Date: Sat, 12 Jun 2004 15:57:41 +0000

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.

> From: Don Stokes <[email-masked]>
>
> >...
> 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.

yes.  that's part of what i meant by "replay attacks that geoff says he's
willing to live with."  like asimov's rules of robotics, everything depends
on everything else, and if you take out something that appears innocuous,
it'll probably have many unforeseen consequences, some of which are Deep.

(i think it's becoming clear to me that the -trans doco won't be amended to
include geoff's "one or two precomputed NSECs used for everything" scenario
as one of its alternatives.)

>                                 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. 

pessimism in the pursuit of dns protocol change, or any security protocol,
or in any of the former involving the latter, is a wonderful virtue.

> 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,

no, it doesn't.  in the as-yet-undocumented DLV we use NSEC that way but
only in a specific part of the domain name tree where it's known to be true.
but generally in dnssec-bis, it is not the case that names in the range from
an NSEC's owner to an nsec's target are being asserted as nonexistent.  all
an NSEC is doing is proving that the qname or <qname,qtype> is nonexistent.

>                                                       and I'd like to
> see the door kept open to using that information in the future. 

many of us would.  but -bis isn't written that way, and i don't expect that
we'll see a bit added to the NSEC RR saying "by the way, it's not just the
<qname> or <qname,qtype> that doesn't exist, but all names after the owner
and up to but not including the target also don't exist".  like many good
ideas, this one comes too late in the process.  a half dozen times now, we
have stopped the presses and rewritten this newspaper to add recent events;
the result is that something that should have taken 3 years has taken 10
(and counting).

> 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.

again, i agree, but there are dozens of corner cases that would have to be
discovered and illuminated and documented before it could be used that way,
and as good as this idea is, i want to start deploying dnssec-bis in 2004.
so, like many other good ideas, it'll have to wait for dnssec-ter or dns-bis.

> 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.

apart from all other reasons to the contrary, the fact that this is not
enforceable, or even detectable as an invalid condition, means that it's not
a useful protocol rule.  right now a cached NSEC is usable for sending out
an nxdomain from cache only if the <qname> or <qname,qtype> being answered
is the same as the one that caused the NSEC to become cached in the first
place, and that's all we can do and still begin -bis deployment in 2004.

> 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.

this represents "modality" and it means that an attacker who wants some
victim (who is not your name server) to be unable to prove the nonexistence
of some name the attacker cares about, has to launch a separate early-stage
attack on your zone's name servers in order to put them into "congestion
mode" where queries about nonexistent names are dropped, before they launch
their real attack which depends on their real victim not being able to find
out that some name of the attacker's does not exist.

now, while this is true of ddos in general, and a congestion attack on the
upstream network links of your zone's name servers would have a similar
effect, there are two important differences.  one is, your zone's name
server operators would not be certain that they'd been attacked.  two is,
normal positive questions asked during this "congestion mode" attack would
still be answered.  i can think of a couple of scenarios where a bad guy
could benefit from this modality.  we can't institutionalize it.

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

that's not how this works.  if the "rule" is implicit or emergent based on
other rules, then it's a "note" not a "rule".  just to make sure people can
reason their way to the side effects and have successfully done so.

> 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.

if done, this would use one of the EDNS extended label types (see RFC2671).
and note that the "0 1" nonextended label type is allocated to EDNS0 now.

> ...
> I think I prefer the reserved code point approach myself.

i think that this is definitely the part of the thread that belongs on the
other mailing list (dnssec@cafax) since it has nothing to do with -bis.