Re: zone walking and random generated names

[Samuel Weiler <weiler@tislabs.com>]

After spending some more time on this, it's starting to sink in (or,
at least, something is sinking in -- I hope it's what Gustavo
intended).  This is a very interesting idea.  Thank you very much for
sharing it with us.

I'm going to try to explain this in different words.  Please tell me
if I get it wrong.  For the moment, I'm only going to look at how to
prove that a name doesn't exist at all, and I'm going to ignore how to
prove what RR types exist at a given name.  I'm also going to ignore
what happens at the beginning and end of zones.  I think the propsoal
is:

   Insert a new name between all existing names in the zone, thereby
   breaking the zone up into spans that each contain EXACTLY one name,
   no more, no less.

   At these new names, build an NSEC (or RNXD) chain containing JUST
   the random names.  (Original names don't get NSECs.)  These new
   NSECs (RNXDs) prove that there is exactly one name between the
   endpoints of the NSEC.  Add to the NSEC (RNXD) RR the hash of the
   ONE original name contained in that span.

Looking at an example used earlier in this thread (and stealing some
text from the draft):

> The zone example.com. has the following data:
>
> b.example.com.            A         10.10.10.10
> e.example.com.            A         10.10.10.11
...
> Using random NSEC you will create random names between each existing
> domain: a.example.com. and d.example.com. for example.

This leaves a zone of:

   a.example (random generated)
   b.example (original)
   c.example (random generated)
   e.example (original)
   f.example (random generated)

Or, more specifically:

   a.example NSEC c.example hashof(b.example)
   b.example A 10.10.10.10
   c.example NSEC f.example hashof(e.example)
   e.example A 10.10.10.11
   f.example NSEC something hashof(something)

Along with appropriate RRSIGs and zone apex RRs and such.

When faced with a query for (the non-existant) d.example.com, the
server returns the c.example NSEC (or RNXD).  What does the resolver
do?

   The resolver sees that the returned NSEC proves that only one name
   exists between c and f.  It then hashes the QNAME and compares the
   hash to the hash in the NSEC.  They don't match, so this QNAME must
   not be the one name in this span.  Thus, the QNAME does not exist.

   If hash(QNAME) had matched the hash in the NSEC, then this NSEC
   would prove that the QNAME does exist.

   And if the plaintext QNAME had, perchance, matched either of the
   endpoints of the NSEC RR, then the name would (ironically) have
   been proven to not exist, since NSEC RRs are only inserted where
   there are not already existing names.

The proposal suggests a second RR type at each existing name to list
the RR types at that name.  I think that the NSEC/RNXD RR could still
do that -- it just lists the types present at the hashed name.
Presumably the NSEC/RNXD would also need to list the hash parameters
used (just like the NSEC2/3/++ proposals).  This would lead to really
long NSEC RR's, but no extra RRs.  For example:

   a.example NSEC c.example hashof(b.example) ( A RRSIG ) hash-param
   b.example A 10.10.10.10
   c.example NSEC f.example hashof(e.example) ( A RRSIG ) hash-param
   e.example A 10.10.10.11
   f.example NSEC something hashof(something) ( types )

This proposal, if I've understood it correctly, seems to have some
interesting potential.  It trivially allows for different hash
parameters at each span, facilitating hash algorithm and parameter
changes.  We'd need to work out the beginning- and end-of-zone
details, but that seems easy.  It's not clear how it would work with
wildcard proofs (empty non-terminals, anyone?) -- that could be
harder.  It avoids the potential "recursion" problem in the NSEC++
proposals, where one NSEC++ proves that another one doesn't exist.

This proposal exposes more about the zone than the NSEC++ proposals:
they only allow counting of the zone and relative numbers of RR types
present, whereas this exposes some information about the lexical
distribution of names.  One could limit the exposure of information by
inserting extra random names in the NSEC/RNXD chain -- in the newly
created spans where no real name exists, use the hash of some name
outside of that span and a synthesized type bitmap.

I'm assuming that, other than for some wildcard proofs, a resolver
always knows or can easily infer which names it needs to prove the
non-existence of, so it knows what value to look for in the hash, but
I'm not sure if that's actually true or not.

In any case, thanks again to Gustavo for sharing this idea.

-- Sam

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