Subject: NSEC+-epsilon (whitelies server) proof of concept.

From: "Olaf M. Kolkman" <[email-masked]>
Date: Mon, 29 Nov 2004 12:29:15 +0100

Dear Colleagues,

<hat chair=off geek=on>

I have implemented a "proof-of-concept" server for the "white lies" scheme. 

Although there are a number of optimizations one can do I have found
this server to interoperate with a bind verifying nameserver.

Rough outline.

The sever itself is a proxy implemented in perl. After applying some
local policy it will forward all its queries to a BIND nameserver that
serves a specially prepared zone. Based on the answer being a wildcard
match, a NOERROR/empty answer match or an NXDOMAIN match the proxy
will cook up the appropriate NSEC white lies that "surround" the query.

The nearest successor and predecessor are determined as in
draft-sisson-dnsext-dns-name-p-s (with specification bugs corrected
and reported to the author) without any possible optimizations.

In more detail.
 
The zone preparations is done as follows.

An input zone is stripped from all its security related RRs (RRSIG,
NSEC, and DNSKEY). For each domain name "dname" in the zone that is
not a delegation a "dname+epsilon TXT " RR is created.

To this zone the keyset needs to be appended an then the zone is
signed through the regular BIND dnssec-signzone signer.

After the signing process all RRs with owner name "dname+epsilon" are
stripped. The result is a signed zone with NSEC RRs pointing to
"dname+epsilon" instead of the next dname.

This zone is loaded on a BIND nameserver running on a private address.

When the proxy receives a query it will return a "REFUSE" if the query
name contains "\000" or "\255" in one of its labels. This policy is
not strictly needed but it is to address the issue that the the NSEC
next name should be part of the zone.  By refusing queries for the
names that contain the "maximum and minimum sort values" that have
been inserted in the +-epsilon process, we "weasel" our way out of the
question if these names are or are not in the zone, the client will
just never be able to know because of our policy.

The proxy will forward its question to the BIND nameserver.

If the answer returned from the authoritative BIND server is a "No
Data" error:

  - the server take the packet coming from the BIND backend server
    and strip all NSECs and their RRs if the owner name is not the
    same as the qname and which are not owned by wildcard names (this
    preservers the NSEC RRs generated in the preprocessing phase and
    that are relevant for the proof).

  - It will then assess if the query was terminated in a wildcard
    match and add proof for non-existence of the direct match against
    the qname (it generates a name error) and return the answer to the
    client.

  - If the no data error was due because of a match against an empty
    non-terminal then a qname-epsilon NSEC qname+epsilon RR will be
    added to the proof to the client.

If the answer returned from the authoritative BIND server is a "name
error" (NXDOMAIN). 

  - A proof qname+epsilon NSEC qname+delta NULL proof will be supplied.
    the delta is somewhat bigger than the epsilon, that is qname+delta
    is the first successor of qname that does not prepend a label.

More detail you can find in the source which is available at
http://www.kolkman.org/NSECepsilon/

The proxy runs at 193.0.3.29. It is authoritative for eg.secret-wg.org. There
exists a secure delegation from secret-wg.org. 

Some of the zone content (not all, the challenge is to enumerate it and
provide me with the zone content :-) )

 *.foo                   10      TXT     "Wildcard match *.foo"

 bla.foo                 10      TXT     "direct match bla.foo"

 *.bla.foo               10      TXT     "direct match *.bla.foo"

 hidden.foo              10      TXT     "direct match hidden.foo"

 foo                     10      TXT     "direct match foo"

 ifeelso.empty   10      A       10.0.0.1

Please let me know if you think I overlooked an important protocol
feature or you find incorrect proofs. The whole point of this
exercise is to proof this can be done.

TODO:

There are a number of optimizations one can do based on the zone content
and structure. This has not been done yet.

</hat>

-- Olaf

---------------------------------| Olaf M. Kolkman
---------------------------------| RIPE NCC

--
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: Alex Bligh <[email-masked]>
Date: Mon, 29 Nov 2004 12:43:58 +0000

Olaf,

Apologies for replying without reading the perl first, but I am
trying to understand your thinking here

--On 29 November 2004 12:29 +0100 "Olaf M. Kolkman" <[email-masked]> wrote:

> name contains "\000" or "\255" in one of its labels.

I am presuming you *do* in fact mean "\000" or "\255" *in* any one
of its labels, not "\000" or "\255" *as* any one of its labels.

If so, then this is a pragmatic rather than a purist approach (that isn't a
criticism, that's an observation), as it effectively prevents any existing
labels with "\000" or "\255" in from working (obviously). But if that's the
case, i.e. if one is prepared to consider certain octet values as reserved
(and thus unavailable for the raw zone file), then I think it's possible to
construct far more simple successor and predecessor functions than those in
draft-sisson-dnsext-dns-name-p-s, (especially if one enforces one octet
stricter length restrictions) which are much simpler to code, understand
and debug. For instance, in terms of successor functions, if one limits the
function's domain[*] to labels not containing \000 and \255, less than 63
(not 64) octets, and with a similar change to the total name length
restriction, then one could define the successor function as simply
concatenating "\000" to the label. The result of the successor function is
not going to need a successor itself, as you'll be returning REFUSE as the
QNAME had a \000 in a label.

All the complexity in draft-sisson-dnsext-dns-name-p-s is because it needs
to support all possible values in the "original" zonefile (i.e. all legal
domain[*].

[* = 'domain' in the mathematical sense, i.e. set of legal input values
to a function - terminological overload - arrrgghh ]

> This policy is

Yes-ish. I think you can generalize that concept as follows:

If it is permissible to place further restrictions on valid label names by
a set of rules (X), then by defining the successor/predecessor functions
S', P' as ones which for any input value compliant with rules (X) generate
a near successor/predecessor which are not compliant with rule (X), and
refusing queries for QNAMEs breaching rule (X), we avoid the wildcard /
existence problem.

I am not ENTIRELY sure your approach conforms to the above for all
cases (I am thinking of maximal DNS length) in that I think the
successor might under certain circumstances not have a \000 or \255 in
it. From the draft:

   DNS name is the maximum DNS name length:

      y  = fooooooooooooooooooooooooooooooooooooooooooooooooo.ooooooooo\
           oooooooooooooooooooooooooooooooooooooooooooooooooooooo.ooooo\
           oooooooooooooooooooooooooooooooooooooooooooooooooooooooooo.o\
           oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo\
           oo.example.com.

      y' = foooooooooooooooooooooooooooooooooooooooooooooooop.ooooooooo\
           oooooooooooooooooooooooooooooooooooooooooooooooooooooo.ooooo\
           oooooooooooooooooooooooooooooooooooooooooooooooooooooooooo.o\
           oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo\
           oo.example.com.

which does not have a \000 or a \255 in it. You can solve that trivially
by putting a one lower limit of maximum DNS name length in the input
zone.

I note that for the purists, names with \000 and \255 in labels,
and (I think) labels between epsilon and delta, are restricted in
their use (i.e. either must not exist or it cannot be shown securely
either that they do or don't exist). I do not think that is a practical
issue for most users.

Alex

---

From: "Olaf M. Kolkman" <[email-masked]>
Date: Mon, 29 Nov 2004 14:58:33 +0100

Alex,

I think we agree, comments in-line

--Olaf

On Mon, 29 Nov 2004 12:43:58 +0000

> of its labels, not "\000" or "\255" *as* any one of its labels.

Acknowledged.

> labels with "\000" or "\255" in from working (obviously)

I have taken the "REFUSE" approach more to proof that one can never
"proof" that the generated owner names are not in the zone, which is
AFAIK the only objection against this scheme. I honestly think that
the client side does not care about that language in the specs. 

> But if that's the
> stricter length restrictions) which are much simpler to code,

Well.. eh this code is pretty simple :-) ....

> understand
> and debug. 

Absolutely correct !!!! I am not saying this is the final product. I think
we can do a lot on optimization.

> For instance, in terms of successor functions, if one limits the

Correct, Geoffry has documented this in his next version.

> by putting a one lower limit of maximum DNS name length in the input

Ack.. that may be a cornercase.

> either that they do or don't exist). I do not think that is a practical

I think they can exist, they are just not obfuscated (and my
"stripper" script would need a patch too :-) ).

If we were to drop the refuse on the "\255" and the "\000" match I think 
I would still refuse on queries for the "NULL" RRs itself, as these do 
simply not exist, while we have NSEC RRs that can "proof" their existence.

There is still some corner case for direct NSEC queries for owner
names dname+epsilon, but have not been able to word that.

On the other hand I can not think of a query that would result in an
NSEC RR that can be used to deny existing data.

--Olaf

PS. I will remove the "REFUSE" on '\000' and '\255' in a day or two. Please
remind me if you found this "not-done".

---

From: [email-masked] (Geoffrey Sisson)
Date: Mon, 29 Nov 2004 14:04:55 +0000 (GMT)

> QNAME had a \000 in a label.

I've added a comparable optimisation to sisson-dnsext-dns-name-p-s-01.
A copy of the `draft' draft is available at:

    http://www.panix.com/~geoff/draft-sisson-dnsext-dns-name-p-s-01pre2.txt

However in a delegation-only domain, the owner names of glue RRs may
still be 255 octets in length.  Any optimisation involving restriction
of maximum length would require ensuring that no owner name of any
glue RR exceeded the restriction.  However I don't believe such a
restriction would be unpopular with registrants: at the moment there
are only two glue RRs in the co.uk zone which are longer than the
maximum label size alone.

> by putting a one lower limit of maximum DNS name length in the input

Note that you will always be able to devise a QNAME which will result
in a predecessor or successor which not only doesn't contain \255 or
\000, but is also a valid owner name in the zone.  These are unlikely
to occur in normal practice, though.

Regards

Geoff

---

From: "Olaf M. Kolkman" <[email-masked]>
Date: Mon, 29 Nov 2004 18:14:12 +0100

>  maximum label size alone.

Glue is just glue and since it is not part of your zone it will not be
signed and there will not be NSEC RRs generated for the glue ownernames.

In any of the optimization you perform you do not have to do any magic
that takes into acount the glue RRs.

I think :-) ....

-- Olaf

---

From: [email-masked] (Geoffrey Sisson)
Date: Tue, 30 Nov 2004 10:49:25 +0000 (GMT)

> that takes into acount the glue RRs.

Yes, of course.

Hmm, then if all the owner names in a zone are one label longer than
the owner name of the zone apex, then another possible optimisation is
the omission of the last step of the derivation of DNS name
predecessor, i.e. prepending labels.

Regards

Geoff