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: Ben Laurie <[email-masked]>
Date: Fri, 11 Jun 2004 10:00:52 +0100

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

That proves that x.example. does exist and doesn't prove that anything 
doesn't exist.

Cheers,

Ben.

-- 
http://www.apache-ssl.org/ben.html       http://www.thebunker.net/

"There is no limit to what a man can do or how far he can go if he
doesn't mind who gets the credit." - Robert Woodruff

---

From: Roy Badami <[email-masked]>
Date: Fri, 11 Jun 2004 11:15:21 +0100

>>>>> "Ben" == Ben Laurie <[email-masked]> writes:

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

    Ben> That proves that x.example. does exist and doesn't prove that
    Ben> anything doesn't exist.

I thought it proves that nothing else in the zone exists.  The
canonical ordering is circular, so if the next RR is yourself, it
means there are no other RRs...

      -roy

---

From: Ben Laurie <[email-masked]>
Date: Fri, 11 Jun 2004 11:34:49 +0100

> means there are no other RRs...

You may be right.

---

From: Don Stokes <[email-masked]>
Date: Fri, 11 Jun 2004 22:41:29 +1200

Ben writes:
>    >> x.example.  NSEC x.example. ...>

>means there are no other RRs...

but if there's nothing (else) there, the current drafts say there
shouldn't be an NSEC record.  NSEC records should show up only when
there's something to talk about...

I wasn't being very clear, and was conflating two separate issues.  So
I'll have another go.  Assume that one wishes to generate static NSEC
records for all names that do exist, but without a traversable NSEC
chain.  Assume too that we want to do authenticated denial on the fly
for those that don't.

Firstly, for the names that DO exist, what should I put in the Next
Domain Name field of the NSEC record to say, "this is the NSEC record
for the name you asked for, but this NSEC does not cover any other
possible record"?

Secondly, if I am to generate signed negative responses on the fly to
cover names that DO NOT exist, what would those records look like?  Can
we fudge NSEC in some way to provide on-the-fly authenticated denial,
(and allow for that capability within DNSSEC-bis), or do we need some
kind of "signed NXDOMAIN" response in DNSSEC-ter?

-- don

---

From: "Scott Rose" <[email-masked]>
Date: Thu, 10 Jun 2004 21:21:37 -0400

I would suggest the next domain name be the apex - indicating it is the last
canonical name in the zone.

Yes, it isn't true, but caches should be fabricating non-existance responses
for non-authoritative data anyway.

Scott

---

From: Ben Laurie <[email-masked]>
Date: Fri, 11 Jun 2004 15:34:17 +0100

> for non-authoritative data anyway.

"shouldn't", surely?

I was also coming to the conclusion that a pair of records of the form:

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

could be used to deny anything (except example. or x.example.), without 
causing other problems - apart, of course, from giving an attacker a 
method of denying any name's existence.

Or would just:

example. NSEC example.

suffice?

Cheers,

Ben.

---

From: Derek Atkins <[email-masked]>
Date: Fri, 11 Jun 2004 10:34:58 -0400

> for non-authoritative data anyway.

That unfortunately enables replay attacks if a "bad cache" gets
in your path or an attacker can guess your query txn id.

> Scott

-derek

-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: Paul Vixie <[email-masked]>
Date: Fri, 11 Jun 2004 17:42:13 +0000

> > I would suggest the next domain name be the apex - indicating it is
> > the last canonical name in the zone.  Yes, it isn't true, but caches
> > should be fabricating non-existance responses for non-authoritative
> > data anyway.

there's a replay attack possible if the range of domain names between the
owner and target of an NSEC is not actually known to be empty.

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

---

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

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

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

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

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

> \001.foo.example. NSEC RRSIG" to say "just foo.example, and not anything

ouch.  you're right.

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

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

right.

> unless one knows that there are no names below <name>, in which case you

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.

> 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

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

---

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

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

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

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

>would never be relevant.  and as before, if you can't enforce it, don't

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

>> of the label type field, e.g a byte value of 0xA0.

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

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.

> 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

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

> that.  Once all the corner cases are worked out, I think this could be

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.

> cached NSECs in this way, and I think such NSECs should be disallowed

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.

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

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

---

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

>or dnssac@cafax.  apologies to our chairs if i'm getting it wrong -- no

[email-masked] please.

         Olafur

---

From: Robert Elz <[email-masked]>
Date: Wed, 30 Jun 2004 15:20:02 +0700

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

I haven't been reading the list for the past few weeks, and am attempting
to catch up.

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

This is a minor point, but I saw this, and didn't see it corrected (though
I have not yet read all of the messages since this one), and I'd like to
try and avoid one more piece of DNS folklore being developed, that everyone
"simply knows" but which is incorrect...

The "next" name in this sense from x.example would be \000.x.example
not \001.x.example - or if you prefer, \000.x.example sorts between
x.example and \001.x.example.

The same is true for x\000.example (wrt x.example and x\001.example
of course).

There's nothing in the DNS spec that prohibits the use of the nul
character in labels, and 0 is clearly < 1 (but greater than absent).

kre

---

From: Don Stokes <[email-masked]>
Date: Thu, 01 Jul 2004 11:46:03 +1200

>x.example and \001.x.example.

True -- and I was aware of that.  However, I'm also fully aware of the
fact that a heck of a lot of software out there is not as eight-bit
clean as one might imagine, especially as far as nuls are concerned. 
After all, nuls are so rare and library routines that deal with
nul-terminated strings so common that someone's eventually going to get
bitten where it hurts by that.

But yes, if one was codifying NSEC lies, one could use \000 and tell
everyone writing DNS software that has to deal with NSEC that this is
going to happen and they need to worry about it.

-- don