Subject: Re: NSEC2 on existing records

From: Don Stokes <[email-masked]>
Date: Thu, 03 Jun 2004 12:02:29 +1200

I wrote:
>"baz A ?" would return:
>
>	hash(foo) NSEC2	hash(bar)
>
>providing authenticated denial of the name, requiring a hash computation.

That's:

	hash(foo) NSEC2 hash(bar)
		  RRSIG NSEC2 <sig hash(foo) NSEC2>

of course.

-- 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: Thu, 03 Jun 2004 12:17:23 +0100

Don Stokes wrote:

> Having just got my head around NSEC2, I wonder if the hash lookup of
> NSEC2 records is really required for names that do actually exist.
> 
> That is, can we move the "this name exists but we don't have the RRset
> you asked for" function into the EXISTS function, rather than the NSEC2
> function, and remove the type bitmap from the NSEC2 record?
> 
> That is, given:
> 
> @		...
> foo		A	10.0.0.1
> 		RRSIG	A <sig foo A>
> 		EXISTS	A RRSIG EXISTS
> 		RRSIG 	EXISTS <sig foo EXISTS>
> bar		A	abc
> 		RRSIG	A <sig bar A>
> 		MX	0 xyz
> 		RRSIG	MX <sig bar MX>
> 		EXISTS	A MX RRSIG EXISTS
> 		RRSIG 	EXISTS <sig bar MX>
> 
> hash(@)		NSEC2	hash(foo)
> 		SIG	NSEC2 <sig hash(@) NSEC2>
> 		SIG	NSEC2 <sig hash(foo) NSEC2>
> hash(bar)	NSEC2	hash(@)
> 		SIG	NSEC2 <sig hash(bar) NSEC2>
> 
> The cases would be:
> 
> Query "foo A" would return:
> 
> 	foo	A 	10.0.0.1
> 		RRSIG 	A <sig foo A>
> 
> providing authenticated data;
> 
> "foo MX ?" would return:
> 
> 	foo	EXISTS	A RRSIG EXISTS
> 		RRSIG	EXISTS <sig foo EXISTS>
> 
> providing authenticated denial of the specific RRset, but without
> requiring a hash computation;
> 
> "baz A ?" would return:
> 
> This approach is most useful to zones containing large numbers of
> unsecured delegations, as queries to such delegations don't incur a hash
> lookup to authenticate the lack of DS record.
> 
> I also think this cuts down on the needed data in the two types of
> authenticated denial -- in the "name exists" case, you don't actually
> need the next domain pointer, and in the "no name" case, you don't need
> a types bitmap for a name you didn't actually query.
> 
> Have I missed something important?

The downside of this proposal is that currently EXISTS records are only 
needed to prove closest enclosers that otherwise don't exist. You'd be 
introducing them for every name in the zone - and you'd still have to 
have NSEC2 records. The upside, if I understand, is that for the case of 
proving existence you'd save the size of the hash of the next domain 
name in the response. Not sure the upside is worth the downside.

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: [email-masked]
Date: Thu, 3 Jun 2004 13:29:03 +0200 (CEST)

> name in the response. Not sure the upside is worth the downside.

There has been an alternative proposed for the closest encloser issue.
That was to add NSEC2s (instead of EXIST) for every emtpty non-terminal.

Another alternative would be the hashing of individual labels, and
truncate hashes to accomodate size.

Roy

---

From: Ben Laurie <[email-masked]>
Date: Thu, 03 Jun 2004 13:11:49 +0100

> That was to add NSEC2s (instead of EXIST) for every emtpty non-terminal.

I don't really understand the advantage of this proposal.

> truncate hashes to accomodate size.

Hash truncation is fine, so long as it is done carefully.

Cheers,

Ben.

---

From: [email-masked]
Date: Thu, 3 Jun 2004 14:20:46 +0200 (CEST)

> I don't really understand the advantage of this proposal.

With EXIST you'll have an NSEC2 record associated anyway. Why do both for
the price of one.

For instance:

 a.b.c  A
#a.b.c  NSEC2 #... A NSEC2 RRSIG
   b.c  EXIST
  #b.c  NSEC2 #... EXIST NSEC2 RRSIG
     c  EXIST
    #c  NSEC2 #... EXIST NSEC2 RRSIG

Could simply be:

 a.b.c  A
#a.b.c  NSEC2  #... A NSEC2 RRSIG
  #b.c  NSEC2  #... NSEC2 RRSIG
    #c  NSEC2  #... NSEC2 RRSIG

Your proposal introduces 4 records at every empty non-terminal
(EXIST/SIG/NSEC2/SIG), while the other proposal introduces 2 records.

> Hash truncation is fine, so long as it is done carefully.

To compare, my proposal is:

#a.#b.#c  NSEC2 #.#.#. A NSEC2 RRSIG

That saves space no ?

Roy

---

From: Ben Laurie <[email-masked]>
Date: Thu, 03 Jun 2004 17:19:31 +0100

> #a.#b.#c  NSEC2 #.#.#. A NSEC2 RRSIG

Its actually:

#a.b.c NSEC2 #d.e.c A NSEC2 RRSIG

for the avoidance of doubt.

> That saves space no ?

There is an open question: is it OK to optimise away NSEC2 records for 
EXIST (since EXIST is _only_ produced as a proof of a closest encloser, 
and MUST NOT [hmmm, bet the I-D doesn't say this] be used to answer a 
query for the owner name). Your proposal does have the advantage of 
avoiding the question, at the cost of quite a bit of overhead, sizewise, 
if the question turns out to have answer "yes".

Cheers,

Ben.

---

From: [email-masked]
Date: Thu, 3 Jun 2004 18:37:42 +0200 (CEST)

> for the avoidance of doubt.

You can't really tell what you put in the next domain name field though.

I ment hash(a).hash(b).hash(c) instead of hash(a.b.c) or hash(a).b.c,
unless you know my proposal better then I do ;-)

> if the question turns out to have answer "yes".

The problem with EXIST is that it turns empty-non-terminals into
non-empty-terminals, only to be able to list the empty-non-terminals for
closest-encloser purposes. (now read this backwards :-)

EXIST is a hack. With NSEC, the empty-non-terminals simply appear in the
owner name of an existing NSEC record, giving proof that such a
non-terminal exists.

With NSEC2 the problem of a single hash for multiple labels is that
ownernames become flat.

With my proposal the NSEC ownername is simply projected into a hashed
ownername by hashing individual labels. Therefor the empty-non-terminal
still exist (in hash-space so to say).

Roy

---

From: Don Stokes <[email-masked]>
Date: Fri, 04 Jun 2004 13:59:58 +1200

>name in the response. Not sure the upside is worth the downside.

The point of the proposal is (a) to cut the amount of work required 
for authenticated denial of RRsets in existing names using NSEC2, and
(b) to cut the traffic on the wire in both authenticated denial cases.  

The expense, as you say, is to add an additional RR and its signature to
the zone, making zone signing harder. 

Where I'm coming from with regard to (a) is that TLD zones would contain
vast numbers of insecure delegations, especially early in the game, and
every one of those insecure delegations would need to generate hashed
NSEC2 records for security-aware resolvers.  While authoritative name
servers could internally link each name with its NSEC2 hash at zone load
time, that link has to be computed on the fly by security-aware
resolvers every time a query is made via those delegations.

If the NSECINFO iteration count is high to deter offline dictionary
attacks, those hash computations could get expensive for smaller
resolvers.

-- don

---

From: Ben Laurie <[email-masked]>
Date: Fri, 04 Jun 2004 15:05:28 +0100

[going backwards for a moment, coz I have seen the light]

>     #c  NSEC2 #... EXIST NSEC2 RRSIG

This is incorrect in general. EXIST records are only required for empty 
non-terminals that are associated with wildcards.

> (EXIST/SIG/NSEC2/SIG), while the other proposal introduces 2 records.

Yes, you are right, I managed to persuade myself that EXISTS were 
required because you couldn't know what the record was that created the 
closest encloser - that is, using NSEC, to deny a.b.c you might exhibit 
an RR for d.b.c and prove nonexistence of *.b.c. But since the EXISTS 
record would only be for b.c, you could indeed use an NSEC2 record. My 
counterargument would be that since EXISTS is only used in negative 
proofs, it can be treated as special, and so what you'd actually have is:

  a.b.c  A
    b.c  EXISTS
      c  EXISTS

(though really at least c would be shown by some other RR, like SOA).

> #a.#b.#c  NSEC2 #.#.#. A NSEC2 RRSIG

Compared to your example, yes - compared to mine? Probably not, since #b 
is much bigger, generally, than b, and #c is almost certainly redundant 
most of the time.

Neat idea, though. Worth further thought.

Cheers,

Ben.

---

From: [email-masked]
Date: Fri, 4 Jun 2004 16:16:41 +0200 (CEST)

> non-terminals that are associated with wildcards.

Then how do I give proof that there exist no wildcard between a
non-empty-terminal and an empty-non-terminal ?

Roy

---

From: Ben Laurie <[email-masked]>
Date: Fri, 04 Jun 2004 15:35:19 +0100

> non-empty-terminal and an empty-non-terminal ?

These wildcards make my head spin. You are correct - we need each of the 
records (modulo my other points), but only need to _return_ one for any 
particular query. Apologies.

Cheers,

Ben.