Subject: Re: Requirements Matrix

From: Alex Bligh <[email-masked]>
Date: Wed, 06 Oct 2004 20:10:37 +0100

--On 06 October 2004 14:01 +0100 Ben Laurie <[email-masked]> wrote:

> I have uploaded my first cut at a compatibility matrix for NSEC++
> requirements. It is available as both a spreadsheet and a web page:
>
> http://www.links.org/dnssec/requirements-matrix.htm
> http://www.links.org/dnssec/requirements-matrix.xls
>
> I'm sure I've got some of them wrong, so please take a look.

OK some comments mainly on the red & yellow areas:

[ I may have misunderstood (27) but I took it to mean "I can sign some
intervals as non-existing without revealing ANYTHING about other names -
not only what they are, but not (necessarily) whether they exist or not" -
IE a combination of non-enumerability and support for intervals which did
not deny existence at all (a la 26). ]

Inconsistencies within the Matrix
=================================

I did a matrix transpose and found out what happened:

17 is marked as incompatible with 7, but 7 is marked as compatible with
17. I don't think they are incompatible.

7 is marked compatible with 10, but 10 is marked incompatible with 7.
I don't think they are incompatible.

9 is marked compatible with 10, but 10 is marked incompatible with 9.
I don't think they are per-se incompatible but I'm not sure.

Compatibility
=============

Requirements 20 & 21 which say: "NSEC++ should not introduce changes
incompatible with NSEC." & "NSEC++ should differ from NSEC in a way that is
transparent to the resolver or validator." are marked as incompatible with
(in essence) the zone non-enumeration requirements and the 27 (called
protocol design but essentially about partially signed zones or at least
zones only partially signed for non-existence which I think is the same
thing or very nearly). I think there is a possible interpretation problem
here, to do with mandatory and option support.

It is possible to read the zone enumeration requirements as mandatorily
applying to all zones, AND to read "incompatible" (in 26) as meaning "if
any resolver implementing DNSSECbis NSEC only - not NSEC++ - cannot
interpret the responses then it's failed the test" THEN clearly we have a
problem. If that's what the red square means, I understand it, but it's not
particularly useful.

However, I do not think it is necessarily impossible to have (for instance)
* NSEC / NSEC++ / unsigned zones as alternatives on the server side *
NSEC++ designed such that it looks like an unsigned zone to resolvers
  supporting NSEC but not NSEC++ If that's what you meant by the red square
Ben, I'd ask why.

It /might/ be possible (in essence through permitting responses currently
prohibited by DNSSEC-bis in a manner which cannot harm any compliant
DNSSEC-bis resolver) to have a zone constructed for NSEC++ signing still
return authenticated records other than NSEC records for resolvers
supporting DNSSEC-bis (& NSEC) but not NSEC++. I am not saying it *is*
possible, I just don't think anyone's conclusively demonstrated that it's
not.

Requirement 19 - Replay Attacks
===============================

I am going to stick my neck out and say I think the problem of replay
attacks IS soluble even in the theoretical case less likely than meteor
destroying the earth (etc.). I think I've said this before and haven't been
contradicted. You can solve this by two measures, each of which solves
separate issues. Firstly, prior to signing, choose a hash such that no
LABEL's hash collides with any other LABEL's hash, and such that no LABEL's
hash collides with any other LABEL. As I think I've shown, this can be done
with minimum computational effort. Next you have the problem that a QNAME's
hash may still collide with a LABEL's hash (i.e. the server is asked to
deny the existence of a LABEL with the same hash as a label that does
exist) - in the conventional analyses submitted thusfar you either can't do
that, or leave yourself vulnerable to a replay attack (depending on whether
you return an error or an NSEC++ record respectively). If you wanted to
solve the problem completely (i.e. introduce support for SHA-256 hash
collisions!), you can solve the second issue by allowing multiple TYPES of
hash in the NSEC++ record, and insist that support of the identity hash
(i.e. the output of the hash is the same as the input) is mandatory. This
will enable a server worried about denying the existence of colliding
QNAMES to return an NSEC++ record using the identity hash (which can never
collide, being a bijective function - or apply common sense :-) ) IF AND
ONLY IF the QNAME they get ACTUALLY collides with an existing hash for a
LABEL that does not correspond to that QNAME. This would allow zone
enumerability at as fast a rate as you can produce SHA-256 hashes (i.e.
never for most definitions of never, or extremely slowly for those worried
about such things).

This mechanism has the additional advantage that it relies on no more
than support for multiple hash mechanisms which are probably a good
thing for the following other mechanism:
(a) if one hash turns out to be flawed, we have alternatives
(b) people may be interested in different hash lengths to minimize
    bandwidth or because necessary hash length might vary
    according to zone size.
(c) it allows the concept of deliberately short weak hashes which
    might "inevitably" produce the odd collision - in case there are
    those who want to make zone enumeration slightly harder than
    it is with NSEC, but nowhere near impossible if they are very
    concerned about zone-size (I have no idea if this constituency
    exists). This would also let us test collision handling.

Requirement 7 - Zone Size
=========================

This becomes slightly less difficult to reconcile with zone enumberability
requirements in zones which are only partially signed for non-existence
(i.e. with requirement 26) as there is no way of telling how many
entries there are in an interval where which is signed but does
not specify nonexistence (assuming the way this is done is two types
of NSEC++ - denying existence in the interval, and being silent
as to existence in the interval). An attacker might estimate that the
density of labels in a hash interval is constant, and this will be
true with a good hash, but quite possibly untrue with the identity
hash or NSEC. So what I'm saying is that non-obvious zone size estimates
could possibly live with NSEC++ if you were using NSEC++ only for
partially signed zones, so I'm not sure the clash marked with (say) 27
is correct.

Somewhat trivially, those building zone files at the server end can
introduce as many NULL records as they like (and thus cause any estimate to
be an overestimate) where the zone does not contain wildcards. It might be
possible to allow abutting NSEC++ records (without an intervening real
label) to perform the same task without the wildcard problem.

Requirement 18 - Purity
=======================

"The name space should not be muddied with fake names or data sets."

This can mean two things:
a) There should not be fake names in the sense of synthesized names,
   (IE deny existence between name N and name N+1 - the next possible
   name only) - in which case I think your analysis is correct, or
b) The above, but also count hash labels as "fake names or data sets"
   in which case I think it may be possible to keep these out of
   the normal name-space, but (i) they'll be in there somewhere, and
   (ii) it requires mucking around with wildcard queries and QTYPE=ANY
   queries to exclude NSEC++ records if you are going to do it properly.

Alex

--
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, 07 Oct 2004 13:41:56 +0100

> not deny existence at all (a la 26). ]

Good point. Taken literally, that would seem a correct interpretation.

> Inconsistencies within the Matrix

I think they are, in the sense that no proposal that I've seen satisfies 
both (hmmm, possibly Bellovin's Bloom filters do, I'm not sure), and I 
can't think of one that does. Note that synthesized "point" denials 
probably do, but they are currently illegal.

I also had marked 17/9 as incompatible, in error.

> I don't think they are incompatible.

Again, I think they are.

> I don't think they are per-se incompatible but I'm not sure.

Again, in the sense that no proposal reconciles them, they are.

> Compatibility

It is what it means, IMO.

>  supporting NSEC but not NSEC++ If that's what you meant by the red square

It is not what I meant.

The essence here is that these points are meant to convey the idea that 
it would be nice if we could do NSEC++ without having to change the 
world. I do not believe that is (currently) possible.

> possible, I just don't think anyone's conclusively demonstrated that it's

This point I don't understand. I have a version of BIND running that 
does exactly this - i.e. returns NSEC2 records. An "old" resolver will 
not understand the responses, and so will treat NXDOMAIN/NODATA as 
unauthenticated denials.

> Requirement 19 - Replay Attacks

I think you are missing an essential point. The server does not get to 
choose what is returned in a replay attack, the attacker does. So, the 
logical consequence of your argument is that the server would always 
have to use the "identity" hash (since it cannot know what the QNAME 
is), i.e. NSEC, and that makes it incompatible, as stated.

> Requirement 7 - Zone Size

Then the size of the signed zone would be apparent, which I believe is 
in the spirit of the requirement.

> label) to perform the same task without the wildcard problem.

This would be incompatible with 18 :-)

> Requirement 18 - Purity

Indeed, if one is prepared to change the rules for searching, then one 
can exclude hashes from the namespace, and this fixes the problem.

"Not changing the search algorithm" was not included as a requirement, 
but I have heard the sentiment expressed, and so it probably should have 
been.

Another issue is that sometimes incompatibilities only exist when more 
than two requirements are grouped, this being a good example - "Purity 
of namespace" and "don't change searches" are incompatible with "zone 
enumeration", but only when paired (modulo meteor-strike probabilities).

I can fix this by introducing new lines for such pairings, I guess. But 
only ones specifically requested, I don't think a 650x650 matrix is what 
people want!

Cheers,

Ben.

-- 
ApacheCon! 13-17 November! http://www.apachecon.com/

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: Alex Bligh <[email-masked]>
Date: Thu, 07 Oct 2004 15:00:49 +0100

Ben,

>> I did a matrix transpose and found out what happened:

OK you disagreed with my three guesses as to what the correct states
were here, but that still means you have to fix the transpose entry.
EG if 17 is indeed incompatible with 7, 7 should be marked as
incompatible with 17 (it isn't), ditto for 7/10 and 9/10 (i.e.
they should be resolved the same way whichevever is on the H&V axes).

> Again, in the sense that no proposal reconciles them, they are.

OK I had read "No proposal exists to reconcile these two, nor is it obvious
they can be" to mean "No proposal exists to reconcile these two, nor is it
obvious that any route exists unknown or otherwise to reconcile them" (i.e.
that whilst we haven't proved they are incompatible, it seems pretty
unlikely they will be). Perhaps I misread. It might be clearer if you
said "Reconciliation is non-obvious and currently unknown, but may
be possible" - i.e. you mean "these are work items" not "don't bother
to dig here".

>> problem. If that's what the red square means, I understand it, but it's
>> not particularly useful.
>

OK - from my "zone enumeration requirement" (and I thought from
Nominet's) I did NOT mean "no zones should be enumerable", I meant
"the server operator should have the option of preventing given
zones being enumerable). This then is not incompatible with (say)
20 (NSEC compatibility) as it can be achieved by making use of NSEC++
optional, and mandating that resolvers that support NSEC++ also
support NSEC.

> world. I do not believe that is (currently) possible.

OK, that's "compatibility with NSEC only resolvers" not "compatibility
with NSEC only servers".

> This point I don't understand. I have a version of BIND running that does
> exactly this - i.e. returns NSEC2 records. An "old" resolver will not
> understand the responses, and so will treat NXDOMAIN/NODATA as
> unauthenticated denials.

That's because of how you implemented it!

In a handwaving way (deliberately to avoid details :-) ) if it were
the case that an NSEC++ supporting resolver made queries in a different
way to servers in such a way as to flag their support for NSEC++,
then an NSEC++ supporting server could return
a) NSEC++ records for NSEC++ supporting resolverd
b) for non-supporting resolvers, either:
   i) NSEC records (if people don't care about zone enumeration) or
   ii) pretend to be a non-DNSSEC-bis server (if people do care
       about zone enumeration).

What I'm saying /might/ be possible (under b(ii)) is to pretend to
have a split personality - as a dreadful hack, for instance, return
the correct records for records that exist, and return SERVFAIL
instead of NSEC where things don't exist (yuck!). As an NSEC (not
NSEC++) resolver has to cope with SERVFAIL anyway, it's not going
to break any compliant resolver. I know SERVFAIL isn't the way to do
it, but what I'm saying is I don't think it's been shown there is
NO way to do b(ii).

> logical consequence of your argument is that the server would always have
> to use the "identity" hash (since it cannot know what the QNAME is), i.e.
> NSEC, and that makes it incompatible, as stated.

Why can the server not know what the QNAME is, if you so design the
protocol? You are assuming the server is ONLY passed the hashed value,
and not (hashedvalue,QNAME). I am not making that assumption. That
may be undesirable for other reasons (granted), but my point is that
solving the problem is not impossible.

>> So
>> what I'm saying is that non-obvious zone size estimates could possibly
>> live with NSEC++ if you were using NSEC++ only for partially signed
>> zones, so I'm not sure the clash marked with (say) 27 is correct.
>
> Then the size of the signed zone would be apparent, which I believe is in
> the spirit of the requirement.

I'm missing something: why would the size of the zone be apparent (or
rather any more apparent) if you were using NSEC++ only to implement
partially signed zones (i.e. used identity hashes)? You get no more
information than out of NSEC records - in fact you get rather less
as the zone is only partially signed.

You assertion is only correct if the ONLY usage of NSEC++ is
non-enumerability, which the reqs doc clearly says it isn't!

Alex

---

From: Ben Laurie <[email-masked]>
Date: Fri, 22 Oct 2004 15:20:54 +0100

Apologies for the delay. I am now updating the requirements I-D and matrix.

> they should be resolved the same way whichevever is on the H&V axes).

Indeed, I have updated the matrix.

> be possible" - i.e. you mean "these are work items" not "don't bother

No, I meant what you said.

> optional, and mandating that resolvers that support NSEC++ also

That would be a "change incompatible with NSEC" (i.e. 20).

> OK, that's "compatibility with NSEC only resolvers" not "compatibility

Well, since the requirement was "compatability with NSEC", I think we 
can take that to mean both clients and servers.

> it, but what I'm saying is I don't think it's been shown there is

Then you still have old resolvers getting unauthenticated denials.

> solving the problem is not impossible.

The point is that you are attempting to protect against a replay attack. 
In a replay attack, the attacker chooses the response, so the server is 
not at liberty to formulate a response based on the QNAME in the query.

> as the zone is only partially signed.

The size of the _signed_ part of the zone would be apparent.

Cheers,

Ben.