Subject: [dnsext] NSEC4

From: Miek Gieben <[email-masked]>
Date: Wed, 4 Jan 2012 10:29:46 +0100

Dear dnsext,

We have written down a little experiment that we have performed, called NSEC4.
The goal of the experiment was to optimize denial of existence records.
It is not our intention to standardize this, as we are aware of the backwards
compatibility issues this has with the current DNSSEC family RFCs, and we do
not want to discomfort the ongoing DNSSEC deployment.

However, we do want to document this to archive the insights we have gained
by doing this experiment. Therefor, we have submitted the following draft:

    http://www.ietf.org/id/draft-gieben-nsec4-00.txt

This experiment resolves two things:
* Reduces the size of the denial of existence response;
* Adds Opt-Out to un-hashed names.

We would be grateful if you would like to read this.

Our question is what is the best place to archive this? Re-reading RFC 2026,
we are considering to put this on the experimental non-standards track.

Thoughts?

Best regards,

Miek Gieben,
Matthijs Mekking
_______________________________________________
dnsext mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/dnsext

---

From: Roy Arends <[email-masked]>
Date: Wed, 4 Jan 2012 10:24:11 +0000

> we are considering to put this on the experimental non-standards track.

Nice!

During the development of NSEC3 we (nsec3 editors) discussed both optimizations (no hash, and wildcard bit). We called "no hash" an identity function [1], and figured out we could always define it as an NSEC3 hash function later. We called the wildcard bit an asterisk flag, but figured that wildcard expansions are per record type, not per full name, and that the proof would be even more different from nsec than before (and the group seemed to be suffering from NSEC3 fatigue at the time). Again, we thought we could always define an additional flag later. However, both additions would break backwards compatibility if you want to optimize for response size.

Great stuff, thanks for documenting the effort. Do you have code, and any comparative analysis on response size? As for a proper place, I'd suggest 

The added functionality of NSEC4 (smaller responses, unhashed names, opt-out) looks like the original opt-in specification: NSEC plus opt-in :-)

[1] http://en.wikipedia.org/wiki/Identity_function

Warm regards,

Roy

---

From: Matthijs Mekking <[email-masked]>
Date: Wed, 04 Jan 2012 12:06:02 +0100

Hi Roy,

Thanks for your kind reaction.

First of all, you mentioned that the "no hash" (or "zero hashing") was
also discussed during the development of NSEC3. Unfortunately, it is
hard (if not impossible) to define it as a new NSEC3 hash function: For
"zero hashing" the Next (Hashed) Owner Name field cannot be base32
encoded. Therefore, with our experiment we made the field a Domain Name.

Second, I cannot deny that adding unhashed named to NSEC3 looks a lot
like adding Opt-In to NSEC. I also think that document writes down a
very clever idea:).

We have code, adaptations of ldns and NSD on the authoritative side,
godns on the resolver side. An analysis on response size is difficult,
because it is zone and query specific. In general, all NXDOMAIN and
Wildcard NODATA responses will be reduced by one NSECx record and its
corresponding signatures.

Kind regards,
  Matthijs

On 01/04/2012 11:24 AM, Roy Arends wrote:
>> We have written down a little experiment that we have performed,
>> called NSEC4. The goal of the experiment was to optimize denial of
>> existence records. It is not our intention to standardize this, as
>> we are aware of the backwards compatibility issues this has with
>> the current DNSSEC family RFCs, and we do not want to discomfort
>> the ongoing DNSSEC deployment.
>> 
>> However, we do want to document this to archive the insights we
>> have gained by doing this experiment. Therefor, we have submitted
>> the following draft:
>> 
>> This experiment resolves two things: * Reduces the size of the
>> denial of existence response; * Adds Opt-Out to un-hashed names.
>> 
>> Our question is what is the best place to archive this? Re-reading
>> RFC 2026, we are considering to put this on the experimental
>> non-standards track.
>> 
>> Thoughts?
> 
> Nice!
> 
> During the development of NSEC3 we (nsec3 editors) discussed both
> optimizations (no hash, and wildcard bit). We called "no hash" an
> identity function [1], and figured out we could always define it as
> an NSEC3 hash function later. We called the wildcard bit an asterisk
> flag, but figured that wildcard expansions are per record type, not
> per full name, and that the proof would be even more different from
> nsec than before (and the group seemed to be suffering from NSEC3
> fatigue at the time). Again, we thought we could always define an
> additional flag later. However, both additions would break backwards
> compatibility if you want to optimize for response size.
> 
> Great stuff, thanks for documenting the effort. Do you have code, and
> any comparative analysis on response size? As for a proper place, I'd
> suggest
> 
> The added functionality of NSEC4 (smaller responses, unhashed names,
> opt-out) looks like the original opt-in specification: NSEC plus
> opt-in :-)
> 
>> Miek Gieben, Matthijs Mekking 
>> _______________________________________________ dnsext mailing
>> list [email-masked] https://www.ietf.org/mailman/listinfo/dnsext
> 
> _______________________________________________ dnsext mailing list 
> [email-masked] https://www.ietf.org/mailman/listinfo/dnsext

---

From: Ben Laurie <[email-masked]>
Date: Wed, 4 Jan 2012 11:26:22 +0000

> we are considering to put this on the experimental non-standards track.

Cute. One minor quibble: in 3.2 you say that if the hash algorithm is
0, then Salt Length MUST be ignored. Strictly speaking, if it is
ignored, then the Salt field cannot be ignored (since you don't know
how long it is). :-)

On that note, you could save 4 bytes by omitting those fields in this case.

A more major observation: when the hash alg is 0 you specify that
domain names are sorted in canonical order (6.1. step 7 and presumably
elsewhere). Clearly this cannot be required to make the algorithm
work, or it would fail when hashing was used. So, either this is
suspicious, in that it suggests a weakness in the protocol, or you
could make the protocol simpler by always sorting in byte order.

Note that the canonical sort is vital to NSEC: it is what keeps the
proof down to 2 records instead of 3 (hence the reason this might be
suspicious).
_______________________________________________
dnsext mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/dnsext

---

From: Andrew Sullivan <[email-masked]>
Date: Wed, 4 Jan 2012 06:58:51 -0500

> we are considering to put this on the experimental non-standards track.

Given that it's an experiment, that seems like a reasonable thing to
do, unless you think the experiment is over.  In the latter case, just
write an informational document and be done with it.

Best,

A

-- 
Andrew Sullivan
[email-masked]

---

From: Matthijs Mekking <[email-masked]>
Date: Wed, 04 Jan 2012 13:33:23 +0100

Hi Ben,

Thanks for your response.

> ignored, then the Salt field cannot be ignored (since you don't know

A quibble, but indeed.

> could make the protocol simpler by always sorting in byte order.

My apologies, I fail to see what the problem is. If "no hash" is used,
we can order the NSEC4s in canonical order, just like NSEC. If hashing
is used, we order them in hash order, like NSEC3. In both cases you make
a usable linked-list. I guess my confusion is about:

     ... when the hash alg is 0 you ...
     work, or it would fail when hashing was used.

But when hash alg is 0, that implies that hashing cannot be used.

Step 7 of the sign algorithm in Section 6.1 says:

 7.   Sort the set of NSEC4 RRs into hash order or canonical order,
        depending on the value of the hash algorithm;

Maybe we have to clarify that canonical order is only for algorithm
number is 0?

> proof down to 2 records instead of 3 (hence the reason this might be

Yes, because you can always the closest encloser from the NSEC RRs. With
hashing that is not possible.

Best regards,
  Matthijs

---

From: Ben Laurie <[email-masked]>
Date: Wed, 4 Jan 2012 12:36:33 +0000

On Wed, Jan 4, 2012 at 12:33 PM, Matthijs Mekking <[email-masked]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> Hi Ben,
>

Sure. But my point is that the order is arbitrary, therefore you can
use the same ordering regardless of whether hashing is used or not.

> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.11 (GNU/Linux)
> Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/
>
> iQEcBAEBAgAGBQJPBEcTAAoJEA8yVCPsQCW5+T4H/jRGxj456YibwPfBQL5gsr/F
> Ty+cP1Xsq2XhfCsshAEm3q8lB1ezSkW53/6XkuXAWXcjy6If854bCkbMx0qepNoV
> FYhnS8DWgkHQZH/d3SeWkg9fko9e7JLjM74Joa8is3MpJb07J8lmuMNPFzT2eFqQ
> um1jJIo2JJgDcBv39dS/mIlzDO6gCE0RwkhyQDOYmjL37JaNd+QH1vPBC37/UOzU
> MmsY2l1IWwWpsgTgxO0elRTlavvHu0xYncn5M/vvsEeC9YvD6pEhJyTZlpp2DFN/
> SfITazW1ZrlqZlVozoEBJDAbgfXss6iYdzM05smgoR+KGfJndRRJAlO/toB67mU=
> =sxGe
> -----END PGP SIGNATURE-----

---

From: "Blacka, David" <[email-masked]>
Date: Wed, 4 Jan 2012 15:14:50 +0000

> we are considering to put this on the experimental non-standards track.

Interesting!  As Roy points out, we did consider these ideas while working on NSEC3, but decided that adding them would make the analysis of NSEC3 even harder for the working group, so decided to leave them out.

I note that with zero hashing, NSEC4 doesn't look exactly like NSEC, as you will have NSEC4 records at empty non-terminals.  This is the reason (that is, the ability to find a record for every possible closest encloser) that the order doesn't have to be DNSSEC canonical name order, and thus could be byte order as Ben suggests.

Since this is an experiment, why not also experiment with a different type map encoding?  I've generally thought that the current encoding isn't typically space or computationally optimal.

--
David Blacka                          <[email-masked]> 
Principal Engineer      Verisign Infrastructure Engineering

---

From: Miek Gieben <[email-masked]>
Date: Wed, 4 Jan 2012 18:22:48 +0100

[ Quoting <[email-masked]> at 15:14 on Jan  4 in "Re: [dnsext] NSEC4..." ]
> Interesting!  As Roy points out, we did consider these ideas while working on
> NSEC3, but decided that adding them would make the analysis of NSEC3 even
> harder for the working group, so decided to leave them out.
> 
> I note that with zero hashing, NSEC4 doesn't look exactly like NSEC, as you
> will have NSEC4 records at empty non-terminals.  This is the reason (that is,
> the ability to find a record for every possible closest encloser) that the
> order doesn't have to be DNSSEC canonical name order, and thus could be byte
> order as Ben suggests.

Ah, I see. Because you eliminate empty non-terminals, the depth of the zone
doesn't matter anymore. This would make the algorithm(s) even simpler as
you don't have to switch between hash == 0 and hash == 1.

> Since this is an experiment, why not also experiment with a different type map
> encoding?  I've generally thought that the current encoding isn't typically
> space or computationally optimal.

What are you thinking about?

Other (wild) ideas:

* eliminate the salt
* use a fixed nr of iterations (100 for instance)

Together that would remove the need for an NSEC4PARAM record.

 grtz,

-- 
    Miek

---

From: Alex Bligh <[email-masked]>
Date: Wed, 04 Jan 2012 19:43:39 +0000

Matthijs,

--On 4 January 2012 12:06:02 +0100 Matthijs Mekking <[email-masked]> 
wrote:

> hard (if not impossible) to define it as a new NSEC3 hash function:

Uggghh. If true, that is a shame.

> For

I /think/ your explanation could be clarified a little. If I understand
things correctly, the issue is not that the Next (Hashed) Owner Name cannot
be base32 encoded (it isn't - it's in binary - see 3.1.6, 3.1.7 and the
last para of 3.2 of the RFC), but that the owner name of the NSEC3 RR needs
to be equal to the base32 encoded value of the previous Next (Hashed) Owner
Name, and as such cannot be guaranteed to fit in the Owner Name.

What we should have done is defined that mapping (base32 encoding here) as
part of the hash algorithm. What we also should have done is specified the
identity mapping as part of the standard. NSEC3 fatigue as someone said.

Unless I'm missing something, the Next (Hashed) Owner Name it seems to me
could be base32 encoded, provided that the encoded value does not exceed
255 bytes. I think that allows representation of up to 159 characters,
which might be useful to someone.

But I seem to remember that hash algorithm support signaling is a minefield
anyway.

-- 
Alex Bligh

---

From: Miek Gieben <[email-masked]>
Date: Fri, 6 Jan 2012 13:51:58 +0100

[ Quoting <[email-masked]> at 19:43 on Jan  4 in "Re: [dnsext] NSEC4..." ]
> identity mapping as part of the standard. NSEC3 fatigue as someone said.

Yes and yes.

Wrt hash algorithm rollovers in the nsec3 record, we *might* make a rule
that if the algorithm of the DNSKEYs supports the hashing algorithm
you can also use that in the nsec3 record.

But of course there are some issues...

 grtz,