Subject: zone walking and random generated names

From: Gustavo Lozano Ibarra <[email-masked]>
Date: Mon, 28 Mar 2005 18:56:50 -0600

On 12/14/2004, I sent a draft about using random generated names to do 
authenticated denial of existence in DNSSEC. I received some replies about 
a possible MTM attack. I still believe that using random generated names 
can solve the problem of non zone walking offline generated authenticated 
denial of existence. I updated the idea of random generated names to stop 
the MTM attack mentioned on the list and I want to know the list opinion 
about it in order to not waste resources on bad ideas. Maybe I am missing 
something said in the last 10 years about random generated names.

The zone example.com. has the following data:

b.example.com.            A         10.10.10.10
e.example.com.            A         10.10.10.11

In DNSSECbis a NSEC RR will be created to proof non existence of 
c.example.com. and non existence of RR AAAA for b.example.com.

b.example.com. NSEC e.example.com. (A RRSIG)

Using random NSEC you will create random names between each existing 
domain: a.example.com. and d.example.com. for example.

Two new RRs are introduced in random NSEC: rnxd (random non exising domain 
proof) and rnxrr (random non existing resource record proof):

rnxd is used to proof the non existence of a name between two following 
random generated names. A hash of the FQDN of the non random generated name 
between the two following random generated names is sent in the response to 
prevent MTM attacks.

rnxrr is used to proof the non existence of a RR for a non random generated 
name.

The following record is sent to the client to proof the non existence of 
c.example.com. The resolver do a verification procedure as in DNSSECbis and 
also verifies that b.example.com. is not the hash value in the rnxd RR to 
prevent MTM attacks.

a.example.com.                                                rnxd 
d.example.com.            f96a6ec2fb6efbe43002f4cbf124f90879424d79

The following record is sent to the client to proof the non existence of RR 
AAAA for b.example.com.

b.example.com.                                                rnxrr     (A 
RRSIG)

The following records will be also generated.
d.example.com.                                                rnxd 
a.example.com.    eb391a1462ef3dda8fdba242cf55cdab843422bb
e.example.com.                                                rnxrr (A RRSIG)

The idea is to use the same utility that generated the signed zones to also 
generate the random names, rnxd and rnxrr records.

Using this idea, an attacker will then enumerate the random-generated names 
and will obtain the hash values of the non-random generated names.

Thanks.

--
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: Samuel Weiler <[email-masked]>
Date: Mon, 28 Mar 2005 22:57:06 -0500 (EST)

I'm having an extraordinarily hard time following these examples[1].
You might try reformatting the examples to clearly show the bounds of
RRs (for example, it was not immediately obvious to me that the quoted
text below was one RR wrapped across two lines).  Feel free to
truncate hashes in these examples.

> d.example.com.            f96a6ec2fb6efbe43002f4cbf124f90879424d79

I'm going to take at guess about waht you mean and try to respond
anyway.

How does the resolver know it needs to check that b.example.com does
not hash to this value?  Why would it know the name "b" at all?  And
wouldn't telling the resolver that "b" exists enable enumeration?

-- Sam

[1]  Actually, I think I understand the RNXRR (it's like NSEC, only
without the 'next name' field -- it just lists what RR types are at a
name).

---

From: Samuel Weiler <[email-masked]>
Date: Tue, 29 Mar 2005 00:56:52 -0500 (EST)

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

> e.example.com.            A         10.10.10.11
...
> 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

---

From: Alex Bligh <[email-masked]>
Date: Tue, 29 Mar 2005 12:42:44 +0100

> Maybe
> I am missing something said in the last 10 years about random generated
> names.

I *think* what you are trying to say, is at signature time generate
a number of RR's with random labels within the zone, and use these
as boundary points for non-existence proofs. I may have misunderstood.

I am taking it that the rnxd needs to have the next (random) domain
in the record, so it is signed (and you cannot have a man in the middle
attack). In this case, there is a walkable chain of random names which
would seem to give nothing away. Each says merely "there is nothing
between R1 and R2 except the label with the hash which comes along
with the record".

That's all fine and dandy until you realize that you need to put
at least one "random" name between each existent name, as only one
name can be carried in the hash. (Of course you can put more than
one, and the intervals that contain no existing normal names can
have a hash of something outside the interval itself).

But I think this is not going to hide much of the zone.

For instance, let's assume the zone has
  secret-sausage.co.uk
  secret-squirrel.co.uk
  secret-squirrel-incorporated.co.uk
  secret-squirrel-industries.co.uk
  secret-swizzle.co.uk

then we'd have to generate something like:
  secret-sausage.co.uk
  secret-smsadg24g34gdsaf.co.uk		rnxd
  secret-squirrel.co.uk
  secret-squirrel-a1423252fb.co.uk		rnxd
  secret-squirrel-incorporated.co.uk
  secret-squirrel-incu41jhgah.co.uk	rnxd
  secret-squirrel-industries.co.uk
  secret-srweadfaskdhjasd.co.uk		rnxd
  secret-swizzle.co.uk

All the records with rnxd are visible. So the attacker gets:
  secret-smsadg24g34gdsaf.co.uk		rnxd
  secret-squirrel-a1423252fb.co.uk		rnxd
  secret-squirrel-incu41jhgah.co.uk	rnxd
  secret-srweadfaskdhjasd.co.uk		rnxd

Now I grant you we haven't got an exact enumeration there. However
a little bit of analysis based on the distance between records will
tell you how many letters you've got right.

So if I've understood this correctly, I think it would work, but
I don't see it as less disruption than NSEC3, but gives less
"hiding".

Alex

---

From: Gustavo Lozano Ibarra <[email-masked]>
Date: Tue, 29 Mar 2005 15:34:32 -0600

>    breaking the zone up into spans that each contain EXACTLY one name,

Yes. An updated a draft will need to work the case when you have a name or 
more with immediate successors in a zone.

>    would prove that the QNAME does exist.

If hash(QNAME) had matched the hash in the NSEC and the server sent this 
NSEC as response, this will indicate a problem with the DNS implementation 
or a MTM.

>    f.example NSEC something hashof(something) ( types )

The problem with using only one RR for denial of names and RR is when you 
think about the case when you have a name or more with immediate successors 
in a zone. I was thinking of having one or more RNXDs per span for this case.

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

Thank you. I will write an updated draft to better explore this idea.

---

From: Gustavo Lozano Ibarra <[email-masked]>
Date: Tue, 29 Mar 2005 15:52:29 -0600

>between R1 and R2 except the label with the hash which comes along

Correct.

>tell you how many letters you've got right.

Correct. In the actual DNS your minimum universe of search is a tree of 64 
levels with [a-z],[0-9],- possibilities per level. Random generated names 
can cut the universe to subtrees per span and citing the secret-squirrel 
example you will be able to prone the subtree. You can also use a 
dictionary, yellow pages...  in the actual DNS and obtain a great amount of 
the names in a zone. I think random generated names have a good level of 
security and a resolver is able to do a double check for the integrity of 
the response: the name that was denied is between the boundaries of the 
span and the signature of the RNXD RR itself.

>I don't see it as less disruption than NSEC3, but gives less

I will write an updated draft taking in consideration your feedback. I 
think we need to have more choices for the zone enumeration problem.

Thank you.