Subject: Re: dictionary attack on nameservers

From: "Olaf M. Kolkman" <[email-masked]>
Date: Wed, 1 Sep 2004 11:14:52 +0200

Dear Colleagues,

I returned from vacation and saw that this thread, and the related
"What I mumbled at the mike today" had developed during my absense. I
started reading it with the intention to make an abstract of the
discussion. The shear amount of side tracks and circles in arguments
make this virtually impossilbe. I counted 191 messages with a total of
15127 lines (including headers).

I want to close this thread by giving every participant the
opportunity to state their concluding argument in not more than 20
lines of text.

Please make an abstract of your own concluding arguments (some people
may have changed their opinions) please do not start discussing these
arguments again. If you can phrase your arguments as a set of
(measurable) requirements for further protocol development that would
be fab.

Note that we are trying to take the work on preventing zone
enumeration seriously and that we are trying to get the requirements
done. At least one of the messages burried in the thread was relevant to
that and didn't get any followup.

Also read:
http://ops.ietf.org/lists/namedroppers/namedroppers.2004/msg01237.html

I am trying to get something sensible out of this that will allow us to
go forward or, if needed, conclude, in a decent fashion.

-- Olaf 
   DNSEXT Co-Chair.

---------------------------------| 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: Paul Vixie <[email-masked]>
Date: 02 Sep 2004 17:25:39 +0000

"Olaf M. Kolkman" <[email-masked]> writes:

> ...

 1: my observations are:
 2:
 3:     - non-registry (SLD, et al) zone administrators are already
 4:       hiding their sensitive DNS data, if any, behind split views
 5:
 6:     - registry (mostly TLD) zone administrators have a competitive
 7:       interest in name secrecy not shared by registrars/registrants
 8:
 9:     - load increases due to more difficult enumeration will be felt
10:       by enumeration victims and third parties, not just attackers
11:
12: my recommendations are:
13:
14:     + ensure that NSEC is capable of covering a single name, so that
15:       a zone can use precomputed positive signatures and on-the-fly
16:       negative signatures, and let motivated/interested zone
17:       administrators add name secrecy by provisioning extra hardware.
18:
19:     + consider other, more compact encodings for nonexistence-proof,
20:       which are easier to generate on-the-fly than single-name NSEC.
-- 
Paul Vixie

---

From: Ben Laurie <[email-masked]>
Date: Mon, 06 Sep 2004 10:35:22 +0100

>  7:       interest in name secrecy not shared by registrars/registrants

I don't believe "competitive" is a correct characterisitaion for all 
registries, though it may be for some, and I'm not sure I agree that 
registrants do not share this interest, either. Certainly registrants 
register domains in order that a particular audience can see those 
domains, but that does not mean that all registrants want their domains 
to be visible to absolutely everyone.

For example, I have just registered a domain in order to get email - if 
I want to receive email from you, then I'll tell you what it is. If I 
don't, I won't. Having it published doesn't help me achieve that.

> 20:       which are easier to generate on-the-fly than single-name NSEC.

Why are you only interested in on-the-fly proofs? If its to avoid 
(major) changes to the protocol, then there's at least one problem with 
this type of solution, which is that outsourced DNS servers would have 
to have a signing key capable of signing anything.

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: "Olaf M. Kolkman" <[email-masked]>
Date: Mon, 6 Sep 2004 12:10:40 +0200

I would like to conclude this thread. Please send your (about) 20
lines closing argument and try to refrain from discussing other
persons summaries.

-- Olaf

---

From: Danny Mayer <[email-masked]>
Date: Mon, 06 Sep 2004 13:16:34 -0400

At 05:35 AM 9/6/2004, Ben Laurie wrote:

>domains, but that does not mean that all registrants want their domains to 
>be visible to absolutely everyone.

I'm curious. Why would they register a domain if they didn't want
everyone to know about it? After all registering a domain means publish,
make it public and provide a means to get there. There are other ways
to provide directions to a site without registering it.

>For example, I have just registered a domain in order to get email - if I 
>want to receive email from you, then I'll tell you what it is. If I don't, 
>I won't. Having it published doesn't help me achieve that.

So don't register the domain. You can always just provide an IP address.
Mail servers only use the domain name to find out where to deliver the
mail.

Danny

---

From: Alex Bligh <[email-masked]>
Date: Mon, 06 Sep 2004 18:44:02 +0100

--On 06 September 2004 13:16 -0400 Danny Mayer <[email-masked]> wrote:

> everyone to know about it?

I have to agree with Olaf's comment that this discussion is becoming
circular - this in particular has been covered at great length (from both
directions) before. Whilst I'm always happy to discuss Nominet's policies
etc. Olaf has made the point this is not / no longer the place to discuss
the rationale behind it. Can I suggest we either take this off-list, or go
dig up things from the archive, and provide closing statements/arguments as
requested?

Alex

---

From: Paul Vixie <[email-masked]>
Date: Mon, 06 Sep 2004 21:37:34 +0000

i said:

> > 20: ...

someone else said:

> [whatever]

but i'm not debating these topics.  olaf asked me to state my concluding
argument in 20 lines or less, which i've done.  anyone who has a different
view, whether outright opposed to what i said or completely independent,
ought to give olaf 20 lines (or fewer) of text.  as tempting as it is to
stand my ground and fight for what i believe in, that time, for nsec++, is
over.

---

From: Alex Bligh <[email-masked]>
Date: Tue, 07 Sep 2004 14:42:03 +0100

> opportunity to state their concluding argument in not more than 20

[ This is a response from me personally and not from Nominet/Geoff/Ben;
  apologies for it being 21 lines ]

=====

Defense against Zone Enumeration is desirable for reasons including:

1. Principle of least surprise - Current DNS implementations allow it

2. Many users require it, e.g: certain registries who for honestly held 
policy reasons (expounded at length, but outside IETF's remit to debate); 
enterprise uses where split DNS is not feasible (e.g. web services).

3. For both, there is a qualitative difference between publishing a node & 
associated RRs, and publishing an index of all nodes. For the former, and 
possibly the latter, discovery of a significant number of RR's is less 
undesirable than discovery of a complete or near complete zone.

4. Those registries that publish data normally do so under specific Ts&Cs, 
and would chose mechanisms more efficient than DNSSEC enumeration.

5. The argument that the data is freely available "anyway", through 
(for-instance) dictionary attacks, web-server logs etc. has not been 
supported by empirical evidence; what empirical evidence has been put 
forward suggests that not all zones are significantly susceptible to 
dictionary attack, and those that are, are far from wholly susceptible.

I recommend that there should be an optional server side alternative 
mechanism for authenticated denial that does not expose an index to the 
zone contents, but retains protection against replay attack, and without 
online signing of denials (impractical, computationally expensive, DoS 
vector). This should be based upon NSEC, and making as few changes as 
possible.

=====

Alex

---

From: Ben Laurie <[email-masked]>
Date: Thu, 09 Sep 2004 16:03:30 +0100

> opportunity to state their concluding argument in not more than 20

The central idea is that people should not be worse off by deploying 
DNSSEC than they are by deploying DNS, So, zone file enumeration should 
be no easier in DNSSEC than it is in DNS.

That said, DNSSEC introduces other considerations, in particular the 
potential exposure of private keys, so a solution should not require 
private keys to be kept online.

And then there are "ordinary" DNS requirements: the solution should be 
compact and minimise change to existing protocols. If it introduces 
extra processing, storage or bandwidth requirements, it should also be 
optional.

Cheers,

Ben.

---

From: Peter Koch <[email-masked]>
Date: Thu, 09 Sep 2004 19:50:35 +0200

> opportunity to state their concluding argument in not more than 20

Zone file enumeration is a deployment obstacle for DNSSEC and it should be
made no easier than it is without DNSSEC. I'd also like to steal from
Ed Lewis' excellent set of items to avoid (sorted kind of top down):

	o Exposition of any existing names (regardless of data owned)
	o Breaking namespace invariants ("muddying up the name space")
	  or namespace consistency
	o Opening attacks against positive answers or against authenticated
	  denial of RRSet existence
	o Exposition of more than a very limited number of not existing names
	o Protocol incompatibilities other than TCR
	o Enforcing major operational efforts by those satisfied with NSEC
	o Enabling replay attacks for authenticated denial

As long as complexity allows, zone enumeration avoidance may be optional
since not only the structured {IN-ADDR,IP6,E164}.ARPA zones but also the
majority of zones containing no more than @, "www" and maybe "mail" won't
probably need it.  Defining a set of reasonable prerequisites (e.g. "no
wildcards", "delegation only", etc) is acceptable.

-Peter

---

From: Mark Andrews <[email-masked]>
Date: Fri, 10 Sep 2004 07:58:10 +1000

I doubt there is a perfect solution that will solve everyones
	problems.  There may need to be a suite of solutions that
	the zone administrator can choose between.

	DNSSEC and DNS itself is a set of engineering tradeoffs.
	DNSSECbis just changes the the current set of tradeoffs.
	Spoofing (DNS) vs enumeration (DNSSEC/DNSSECbis)

	I dislike the hashing solutions as it introduces namespace
	pollution and doesn't allow all existing DNS zones to be signed.

	I can live with online signing though I don't believe that
	NSEC white lies is the best way to do this.  If we have to
	have online signing then we should look for a better way
	to do this than NSEC white lies.  I believe we can introduce
	a new type of zone signing and have no impact on DNSSECbis
	servers.  The zones would be treated as unsigned by DNSSECbis.

	This would give the zone operator the choice of spoofable
	results, enumeration or online signing.  I don't believe
	that the other tradeoffs are the way to go.  We already
	have online signing for secure updatable zones.

	Mark
--
Mark Andrews, ISC
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: [email-masked]

---

From: Alex Bligh <[email-masked]>
Date: Fri, 10 Sep 2004 11:17:54 +0100

> 	pollution and doesn't allow all existing DNS zones to be signed.
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

At the risk of annoying Olaf, but for the purposes of getting a common
understanding of all our position, could you elaborate on the bit
underlined by carrets? (i.e. either it's a new point or I've completely
missed something).

Alex

---

From: Marcos Sanz/Denic <[email-masked]>
Date: Fri, 10 Sep 2004 13:22:56 +0200

> opportunity to state their concluding argument in not more than 20

Overcoming my original reluctance to give a summary of my position, 
because the chairs did not privately contact me to do so *lol*, here it 
goes:

The current list of requirements (
http://www.links.org/dnssec/requirements.txt) reflects my expectations for 
a signed proof of non-existence (modulo my remarks sent privately to the 
authors 3 weeks ago: ICMP_ECHO_REQUEST), so I won't list the requirements 
here again. IMHO some of them are less and some are more relevant, but it 
has repeatedly been said that we are still in the phase of outspeaking 
requirements, and we all know that a solution will probably imply a 
trade-off among them.

Best,
Marcos

---

From: Mark Andrews <[email-masked]>
Date: Fri, 10 Sep 2004 23:25:42 +1000

> > 	pollution and doesn't allow all existing DNS zones to be signed.

	If I have a zone with domainnames/zonename that are almost
	maximal length the addition of the hash causes the resulting
	domainnames to exceed maximimal length.

---

From: Jim Reid <[email-masked]>
Date: Fri, 10 Sep 2004 14:59:36 +0100

>>>>> "Mark" == Mark Andrews <[email-masked]> writes:

    Mark> 	If I have a zone with domainnames/zonename that are
    Mark> almost maximal length the addition of the hash causes the
    Mark> resulting domainnames to exceed maximimal length.

Another potential problem with the current hashing proposals is that a
hash could collide with a label for an existing name. ie Suppose the
hash of the A record for jim.foo is alex.jim.foo but alex.jim.foo
already exists as a delegation point or CNAME.

---

From: Alex Bligh <[email-masked]>
Date: Fri, 10 Sep 2004 15:59:40 +0100

> already exists as a delegation point or CNAME.

Let's append ".*" to each hash label to ensure it doesn't collide then.
(joke).

Alex

---

From: Simon Josefsson <[email-masked]>
Date: Fri, 10 Sep 2004 20:50:58 +0200

> already exists as a delegation point or CNAME.

There are at least two solutions to that problem.

The first is to use salting to make sure there are no collisions.

The second one is to place the NSECbis record in a separate name
space.  For example:

jim.foo IN A
alex.jim.foo IN CNAME ...
alex._no.foo IN NSECbis ....

The second solution introduce new issues, like decreasing the length
of the owner name by 3 bytes compared to naive hash based NSECbis.

However, the second solution also has additional advantages.  You can
delegate the ._no. zone, to serve all NSECbis records from separate
machines, which can be useful for dynamic NSECbis signing.

Thanks,
Simon

PS.  All of this has been mentioned before.  It seems like a process
failure that we keep repeating these discussions.

---

From: Robert Elz <[email-masked]>
Date: Sat, 11 Sep 2004 03:59:33 +0700

Date:        Fri, 10 Sep 2004 20:50:58 +0200
    From:        Simon Josefsson <[email-masked]>
    Message-ID:  <[email-masked]>

  | There are at least two solutions to that problem.

no, there are no solutions for this problem in any proposal that requires
adding new names (attempts to steal some of the namespace) for any existing
RR type (the _tcp stuff in SRV records is annoying, but not fatal, as they're
relevant only to SRV lookups and don't prevent _tcp being used as a label
for any other RR types).

  | The first is to use salting to make sure there are no collisions.

That doesn't work, you just collide with a different name.   For any
name that you propose adding, I simply add the same name with whatever
RR types cause your proposal to have problems.

  | The second one is to place the NSECbis record in a separate name
  | space.

In this case the "separate name space" is the name that is the problem.

  | PS.  All of this has been mentioned before.  It seems like a process
  | failure that we keep repeating these discussions.

Perhaps, but if people keep not understanding, there's little choice but
to keep on repeating.   Eventually the message might get through.

kre

---

From: Alex Bligh <[email-masked]>
Date: Fri, 10 Sep 2004 22:39:33 +0100

> RR types cause your proposal to have problems.

[ I hope Olaf's going to forgive me on this one, but I think we are
  now talking about something quite different from the circular
  discussion on whether or not non-enumerability is needed and
  what the requirements are so I have changed the subject appropriately ]

I'm lost. Let me do some CS/Math and then see if I have applied it
without missing the point:

If you have a set of labels X, and a set of labels Y where
  Y(i) = HASH ( X(i) , S, H)

i.e. a hash of X(i) using salt S (the same for all values of i) and H bit
hash, then, providing n(X) << 2^H, it's trivially easy (and computationally
efficient) to find a value S such that there are NO values i, j such that
Y(i) = X(j) - I'll call that finding a non-colliding salt value S such that
there are no collisions between the range and domain of the hash function.

One possible mechanism is simply to iterate through values of S chosen
according to any cyclic algorithm with a cycle length >> n(X) (let's say of
length 2^H or similar) - let's call the values S(1), S(2), S(3) etc. - you
can show that you will find a first non-colliding value S(c) in a
computationally small number of iterations (the expected number of
iterations c is in essence 1, assuming n(X)<<2^H).

I don't *think* I'm wrong on that bit of CS / math.

Assuming I'm not wrong, and assuming some NSEC2/NSEC+-esque proposal,
whatever routine is used to generate the NSEC2/NSEC+ etc. records you don't
want to collide (let's say, to be really safe, with ANY record, no matter
WHAT the RRTYPE) you just first create them with S(1), if there is a
collision (irrespective of RRTYPE) try S(2), etc. etc., and again the
expected number of iterations is in essence 1, assuming n(X)<<2^H.

Now if you add another name, you do the same. Is there a collision now? No
- then no problem. Yes - then time to resalt. There's no external DoS risk
as it's only the zone owner who can add the names - if they are
deliberately (for some reason) chosing to add names that collide with
existing hashed records, then "don't do that".

So I think they CAN be avoided algorithmically - in a similar sort
of way to the creation of Bloom filters, but with far less computational
complexity.

For the record, for the reasons Ben mentioned a good while ago, I am not
sure why collisions are actually a problem at all - i.e. if we have
  $ORIGIN example.com
  alex IN TXT "1"
  jim  IN TXT "2"
why is it a problem if HASH("alex")="jim" and so we also have
  jim  IN NSECBLAH whatever

I'm quite prepared to believe it is a problem, and my understanding
of the protocol is flawed, but I'd like to be educated :-)

Alex

---

From: Robert Elz <[email-masked]>
Date: Sat, 11 Sep 2004 06:24:19 +0700

Date:        Fri, 10 Sep 2004 22:39:33 +0100
    From:        Alex Bligh <[email-masked]>
    Message-ID:  <6D2BC836CD949E7C4EB3762D@[192.168.100.25]>

  | [ I hope Olaf's going to forgive me on this one, but I think we are
  |   now talking about something quite different from the circular
  |   discussion on whether or not non-enumerability is needed and
  |   what the requirements are so I have changed the subject appropriately ]

Yes, I have been avoiding that discussion, I believe my views are already
well known (and that I haven't been wasting space restating them doesn't
mean they've changed).

  | I'm lost. Let me do some CS/Math and then see if I have applied it
  | without missing the point:
  | 
  | If you have a set of labels X, and a set of labels Y where
  |   Y(i) = HASH ( X(i) , S, H)
  | 
  | i.e. a hash of X(i) using salt S (the same for all values of i) and H bit
  | hash, then, providing n(X) << 2^H,

Well, you've already lost the "any zone" requirement with that
assumption, but it gets worse than that.

  | it's trivially easy (and computationally
  | efficient) to find a value S such that there are NO values i, j such that
  | Y(i) = X(j) - I'll call that finding a non-colliding salt value S such that
  | there are no collisions between the range and domain of the hash function.

I think you're relying upon probabilities, which doesn't work in a situation
like this.

  | One possible mechanism is simply to iterate through values of S chosen
  | according to any cyclic algorithm with a cycle length >> n(X) (let's say of
  | length 2^H or similar) - let's call the values S(1), S(2), S(3) etc. - you
  | can show that you will find a first non-colliding value S(c) in a
  | computationally small number of iterations (the expected number of
  | iterations c is in essence 1, assuming n(X)<<2^H).

All I need to do, is pick a name, any name, N, that exists in my zone,
and then for each potential S calculate HASH(N, S[i], H) and add that
name to my zone file.   Now for name N, there's no possible S which doesn't
generate a conflict.

How practical this is depends upon how big the range of possible salts is,
but practical or not, it is clearly possible.  The number of bits in the
hash function is immaterial here (though as it gets bigger, the number of
possible salts must get less, as the total label length is limited).

  | For the record, for the reasons Ben mentioned a good while ago, I am not
  | sure why collisions are actually a problem at all

This one is a different issue, and isn't one I was addressing (just the
theory that it is possible to go about stealing names from the namespace
without ever doing any harm).

The usual problems (if the RRtype of the clashing name is NS or CNAME)
might not apply to NSEC because of the weird rules that (I think) apply
to this new record type (or then again they may, I'm no expert on the
DNSSEC RR types).

But I'd want to know just how they effect wildcards.   If I have a
	* IN MX 10 foobar.
record in my zone file (for the example. zone), I expect that anyone looking
up any-random-hash.example. is going to get the foobar MX record, just like
anyone looking up any other name that doesn't exist will get.   If the
NSEC records existing mean that the the wildcard doesn't get found, then
things are badly broken.  To fix that I'd have to add explicit MX records
for every hash label (and a *.hash-label as well) which would alter the
set of NSEC records that has to exist (clearly adding more), which means more 
MX records required, and ... (so it isn't really fixable).  That is, unless
NSEC records are to be treated as "special" for wildcard purposes.

kre

---

From: Mark Andrews <[email-masked]>
Date: Sat, 11 Sep 2004 10:12:04 +1000

> NSEC records are to be treated as "special" for wildcard purposes.

Please don't go there as finding the answer to that is not as simple as
just inoring the NSEC records.  It would require examining the tree
rooted at the hashname to see if there was anything valid beneath it.

---

From: Alex Bligh <[email-masked]>
Date: Sat, 11 Sep 2004 08:40:48 +0100

Robert,

I think we have a seriously different understanding of how the
hash things work

--On 11 September 2004 06:24 +0700 Robert Elz <[email-masked]> wrote:

>   | i.e. a hash of X(i) using salt S (the same for all values of i) and H
> bit   | hash, then, providing n(X) << 2^H,
>

I am saying for ANY given set X(i) (i.e. for any zone) you can (trivially)
find a value S that produces a non-collinding Y(i).

Yes, this non colliding S may be different depending on X(i) - i.e.
depending on the zone. That just means there is a potential requirement
for a different salt per zone if one wants to ensure non-colliding.

>   | efficient) to find a value S such that there are NO values i, j such
> that   | Y(i) = X(j) - I'll call that finding a non-colliding salt value
> S such that   | there are no collisions between the range and domain of
> the hash function.
>
> I think you're relying upon probabilities, which doesn't work in a
> situation like this.

It does work. You just iterate. You can show that there is a binomial
process and the expected number of iterations is

                1
	------------
                   2
               n(X)
         ( 1 - ----- )
               2^H

IE if n(X)< 2^(H-1) the expected number of iterations is less than two.

Probabilities *do* work here as mathematically there is no finite chance of
a loop (the Bloom filter stuff is clearly close enough here). Plenty of
algorithms work this way. Remember this is done pre-signing - finding a
non-colliding salt is far less computationally intensive than signing. It's
only O(n) - (I wrote the case of that O correctly).

>   | according to any cyclic algorithm with a cycle length >> n(X) (let's
> say of   | length 2^H or similar) - let's call the values S(1), S(2),
> S(3) etc. - you   | can show that you will find a first non-colliding
> value S(c) in a   | computationally small number of iterations (the
> expected number of   | iterations c is in essence 1, assuming n(X)<<2^H).
>
> name to my zone file.   Now for name N, there's no possible S which
> doesn't generate a conflict.
>

The number of potential S values is the size of the hash space. So
whilst you are technically correct, all you are showing is that
the assumption fails where n(X) is *not* considerably smaller than
the zone. I think you can be even more critical than that, as from
some brief calcs I did half asleep in bed last night, I think things
start to go wrong when the (n(X) ^2) > 2^H (i.e. where the number
of names is greater than the square root of half the size of the
hash space).

But we already know we need a large hash space if the thing is going to be
resistant to attack. For a 32 bit hash, we can support zones of size 2^16.
For a 64 bit hash, we can support zones of size 2^32. For a 128 bit hash,
zones of size 2^64. For a 160 bit hash, zones of size 2^80. Assuming 5 bits
per character (yes I know labels are really 8 bit but I am assuming caches
on the way might incorrectly not be 8 bit clean), that's 4 characters, 13
characters, 26 characters and 32 characters respectively in the hash symbol.

Given the choice of available hash lengths, I don't think we are losing
much functionality by insisting the hash bits are at least
2 x log2(zonesize).

A much MORE significant collision problem it seems to me is where
two labels X(i), X(j) for which i!=j have the same hash value
(i.e. Y(i)=Y(j) ). That too is going to call for another salt.
I think that's going to be a greater driver to longer hash labels
but I haven't yet worked the maths behind it out. I think it's
probably the same.

--
Alex

---

From: Simon Josefsson <[email-masked]>
Date: Sat, 11 Sep 2004 14:25:41 +0200

> relevant only to SRV lookups and don't prevent _tcp being used as a label

Here's an idea to add another level of indirection to handle this:

jim.foo. IN A
alex.jim.foo. IN CNAME ...
foo. IN NSECBISZONE _nix
alex._nix.foo. IN NSECbis ....

In other words, the part of the namespace that is stolen for NSECbis
records can be chosen to avoid existing names.

I'd agree with anyone who thinks this is complex.  I don't believe
stealing a part of the namespace for technical reasons, much like SRV
does, is a problem.

> RR types cause your proposal to have problems.

Then I'll change the salt, to get another non-colliding name.  I agree
with Alex Bligh's discussion.  Remember, you don't get to add new
names after NSECbis records have been added.  The NSECbis tool have
the entire zone content, and can chose salt values to make sure there
are no collisions.

However, I have not been convinced that salting is necessary in the
first place, since I don't consider colliding names a realistic
problem.  Same for offline dictionary attacks against the hash
function.

> In this case the "separate name space" is the name that is the problem.

I want to understand why.  Please explain.  What is the problem?

Thanks,
Simon

---

From: Edward Lewis <[email-masked]>
Date: Mon, 13 Sep 2004 16:28:34 -0400

>to keep on repeating.   Eventually the message might get through.

Or maybe trying to explain in a different manner.  Perhaps one's 
words are being read within the same context that they are being 
written. ;)
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                            +1-703-227-9854
ARIN Research Engineer

"I can't go to Miami.  I'm expecting calls from telemarketers." -
Grandpa Simpson.

---

From: Edward Lewis <[email-masked]>
Date: Mon, 13 Sep 2004 16:47:27 -0400

I'm lost on the issue of "avoiding" collisions.

I've been trying not to jump into this as we haven't set up the 
requirements (in a draft yet) for the problem, but:

1) What if authenticated denial was different for sets at an existing 
name than for name errors?  I mean, in RFC 1034 returns "no error" if 
a name exists but data doesn't, and a "name error" if the name 
doesn't exist.

2) So, what if we take care of "no error, no data" by just using NSEC's like:
      owner NSEC owner <types it has>

3) For name errors, just return:
      H(owner1) NXD H(owner2) for any H(owner1) < H(query) < H (owner2)?

The implications - the zone data no longer needs to be sorted (no 
lexical ordering of names).  The table of hash records need not sully 
the data space, so who cares about collisions?

Okay - maybe H(missing name) = H (owner3)...like I've said, I have 
been trying not to think about this until the time has come for the 
discussion on solutions.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                            +1-703-227-9854
ARIN Research Engineer

---

From: Ben Laurie <[email-masked]>
Date: Tue, 14 Sep 2004 13:37:56 +0100

Edward Lewis wrote:
> name than for name errors?  I mean, in RFC 1034 returns "no error" if a 
> name exists but data doesn't, and a "name error" if the name doesn't exist.
> 

Precisely my point!

> Okay - maybe H(missing name) = H (owner3)...like I've said, I have been 
> trying not to think about this until the time has come for the 
> discussion on solutions.

Hash collisions are fantastically unlikely. With salt you can make them 
never occur, anyway. Plus, if they were a problem, then you would have 
the same issue with signatures, but I don't see anyone bringing that one up.

Cheers,

Ben.

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

---

From: Ben Laurie <[email-masked]>
Date: Tue, 14 Sep 2004 13:45:42 +0100

> I think you're relying upon probabilities, which doesn't work in a situation

DNSSEC already relies on the probability that two strings don't have the 
same hash - if they did, then a signature could be used to prove fake data.

Cheers,

Ben.

---

From: Ben Laurie <[email-masked]>
Date: Tue, 14 Sep 2004 13:48:32 +0100

> possible salts must get less, as the total label length is limited).

The salt is not included in the label (at least in my proposal). 
However, I still contend that colliding with another name is irrelevant, 
since the hashed name will only appear in an NSECbis record, and an 
unhashed name will never appear in an NSECbis record.

> NSEC records are to be treated as "special" for wildcard purposes.

I agree, NSECbis records need to be treated as special.

---

From: Mark Andrews <[email-masked]>
Date: Wed, 15 Sep 2004 08:04:26 +1000

> > the data space, so who cares about collisions?

	The data doesn't have to be sorted but the hashes do.  "6 of 1,
	half a dozen of the other" as far as I am concerned.

> the same issue with signatures, but I don't see anyone bringing that one up.

	You are incorrect.  All the current schemes have a hash of less than
	64 octets.  There will ALWAYS be a possibility of collision even
	after trying every salt as it is impossible to make the hash space
	larger than the pre-hash space.

---

From: Mark Andrews <[email-masked]>
Date: Wed, 15 Sep 2004 08:10:36 +1000

> same hash - if they did, then a signature could be used to prove fake data.

	But collisions over the rdata do not impact on the lookup
	algorithm.  Collisions in the namespace do impact on the
	lookup algorithm.

---

From: Alex Bligh <[email-masked]>
Date: Wed, 15 Sep 2004 10:52:16 +0100

> 	larger than the pre-hash space.

But the pre-hash space is sparse, and we only care about collisions of
ACTUAL values in the pre-hash space, not potential values. IE (assuming all
octet values are OK and 64 byte labels for the sake of argument) there are
the pre-hash space is size 256^64 and the hash space is smaller (let's say
we represent them as alphanumerics so 36^64) - which is presumably your
complaint. Note 256^64 is approximately 10^153, and there are about 10^79
atoms in the universe, so I predict in applications the pre-hash space will
be sparse as even if we could represent one RR in just one atom, we are way
off filling the zone :-) So this doesn't matter provided there is a
limitation on the number of RR's in a zone - the limitation doesn't have to
be impactful - If it was 10^76 (number of atoms in the universe over 1000),
we'd still have 10^79 possible salt values to work through, i.e. about 263
bits of salt. And as I pointed out earlier, as 76*2<153, the expected
number of iterations to find a salt that works is less than 2.

I do not think limiting a zone file to 10^79 RRs is going to have
a significant deployment impact.

Alex

---

From: Mark Andrews <[email-masked]>
Date: Wed, 15 Sep 2004 21:48:09 +1000

> a significant deployment impact.

	You can't write a draft assuming that there won't be collisions.
	There will ALWAYS be the possibility of collisions (salts only
	reduce the probability) and you have to take those into account.

	You have to describe what to do when you have a collision.  Don't
	say they won't occur because they will.

	For RRSIG the impact of collisions is that there are two (or more)
	RRsets that you cryptographically prove they are different.

	For name hashes you end up with different names with possible
	different sets of types that you some how have to merge.  If the
	sets are identical I don't think there is a issue but it would need
	to be discussed.

	You will also have occasional false matches (names that you
	can't prove that don't exist).  There MUST be names for which
	this will occur.

	Mark

---

From: Robert Elz <[email-masked]>
Date: Wed, 15 Sep 2004 19:11:42 +0700

Date:        Tue, 14 Sep 2004 13:48:32 +0100
    From:        Ben Laurie <[email-masked]>
    Message-ID:  <[email-masked]>

  | The salt is not included in the label (at least in my proposal).

It needs to be included somewhere, right?   Otherwise the resolver can't
verify the hash is correct, and thus has no idea if the NSECbis record
is actually one that was supposed to apply to this query.   If the salt is 
something very huge, that's a lot of extra data to include (somewhere)
in each record (and the salt itself needs to be verified to be correct).

This is why I have been assuming that the size of the salt (number of
bits) would be limited to a (somewhat) smallish value.

  | However, I still contend that colliding with another name is irrelevant, 
  | since the hashed name will only appear in an NSECbis record, and an 
  | unhashed name will never appear in an NSECbis record.

That's OK as far as it goes, except that the mere existence of a RR
(of any type) alters the lookup algorithm - particularly as it relates
to wildcards.   And ...

  | I agree, NSECbis records need to be treated as special.

I think that would be a terrible idea, more "special" records are the
very last thing that the DNS needs.

kre

---

From: Roy Arends <[email-masked]>
Date: Wed, 15 Sep 2004 15:06:59 +0200 (CEST)

> 	reduce the probability) and you have to take those into account.

At hash generation time, in case of collision with an existing name, alter
salt.

At name inclusion time, in case of collision with an existing hash, alter
salt.

At serving time, in case of collision, be famous:

Oh, if anyone can give an example of an actual collision of two different
inputs for say SHA-1 (full rounds please), please speak up.

> 	say they won't occur because they will.

In case of an actual collision at serve time (birthday paradox does not
apply here, all pre-images were chosen for you), you treat this as a false
positive. A false positive implies that a non-existent name and type is
now proven to exist. I can't even imagine how one can abuse that fact.

Oh, if anyone can give an example of an actual abuse of false positives,
please speak up.

> 	can't prove that don't exist).  There MUST be names for which

If _ever_ such a name can be uncovered, register it with some type.

Roy

---

From: Edward Lewis <[email-masked]>
Date: Wed, 15 Sep 2004 09:31:42 -0400

>	sets are identical I don't think there is a issue but it would need

Why not just include both records as an RRset?

I think this is why I'm thinking we should have split the problem 
into solving "name error" proofs and "no data" proofs.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                            +1-703-227-9854
ARIN Research Engineer

---

From: Edward Lewis <[email-masked]>
Date: Wed, 15 Sep 2004 09:29:13 -0400

>	half a dozen of the other" as far as I am concerned.

For a lookup resulting in an answer, you don't need to access the 
hashes.  So, for all positive hits, you can go back to the old means 
of storing a zone's contents in memory.

Only for lookups resulting in negative answers do you have to have a 
sorted list of things to respond with.

>	larger than the pre-hash space.

Well, I believe that.  Still I don't understand why collisions are a 
problem.  Perhaps because I am assuming that you'd only need to give 
out hash answers in name errors, so the list of RRSETs doesn't matter.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                            +1-703-227-9854
ARIN Research Engineer

---

From: Mark Andrews <[email-masked]>
Date: Wed, 15 Sep 2004 23:44:53 +1000

> now proven to exist. I can't even imagine how one can abuse that fact.

	The problem is that you cannot supply a secure answer to the
	question asked.  For every hash there is a enormous set of
	qnames which all has to the same value.

---

From: Mark Andrews <[email-masked]>
Date: Wed, 15 Sep 2004 23:53:21 +1000

> sorted list of things to respond with.

	The same is true of NSEC.

> out hash answers in name errors, so the list of RRSETs doesn't matter.

	The problem is that by using hashes there you are creating
	sets of QNAMES for which you cannot return NXDOMAIN securely.
	One set for each hash in use.
	
	If you have collisions with hashes of names with data you cannot
	hand out NODATA responses securely.  Yes, Roy you can exhaust
	salt space.

---

From: Mark Andrews <[email-masked]>
Date: Thu, 16 Sep 2004 00:04:13 +1000

> Why not just include both records as an RRset?

	Because you can now spoof away data that exist.

---

From: Edward Lewis <[email-masked]>
Date: Wed, 15 Sep 2004 10:15:31 -0400

>	One set for each hash in use.

?  I'm probably not on the same wavelength about hashes.  I think the 
hash space needn't be considered part of the DNS data tree, just a 
transformation of existing names into an obscured representation. 
I.e., in a response message with a name error in the return code, the 
verifier ought to realize that the negative answer proof records are 
using transformed names, not plain text names.

>	hand out NODATA responses securely.  Yes, Roy you can exhaust

Let's say the labels in a zone are {chamberlin erving julius wilt} 
and the corresponding hash values are { 6  9  13 } with a collision.

Let's say I ask for ( robertson, IN, TXT ) and the hash of robertson is 9.

Hmmm, I picked out 9 by randomly hitting a key and seeing that I 
managed to pick a collision between the qname and one or more members 
of the zone.  Will this still work out?

So, I get back a "name error" with "9 NSEC7 13" in the authority 
section.  After verifying the record (via the RRSIG), what next?  I 
suppose it's then possible to a victim of an insertion attack - an 
interloper passes back this collision with there being a genuine 
robertson in the zone.

What if there the qname's hash was 10?  In that case, I don't see a 
problem in the collision amongst zone members.

But - it's the collision between qname and zone content - which isn't 
possible to know at signing or serving time - that might be a problem.
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                            +1-703-227-9854
ARIN Research Engineer

---

From: Chris Thompson <[email-masked]>
Date: Wed, 15 Sep 2004 15:27:06 +0100 (BST)

Mark Andrews writes: 

[...snip...]
> 	One set for each hash in use.

Maybe a different mechanism for securely returning NXDOMAIN is needed
in these cases? If a name being looked up hashes to something different 
from every extant name, return the signed NSEC' record to prove it by
showing an interval of hash values free of extant ones. But if the hash
matches that of one or more extant names, but the name isn't any of them, 
then return a signed NSEC'' record that lists all the extant names that 
hash to that value (proving that the caller's wasn't one of them). That 
gives away one or more names in the zone, of course, but the caller had 
to be pretty damn lucky to get a hash match in the first place.

This idea is somewhat half-baked, in that representing a list of names 
of potentially unlimited length in a signed answer could pose problems.
(Although now you really could play "change the salt, Walt" to finesse 
that.)

Chris Thompson
Email: [email-masked]

---

From: Alex Bligh <[email-masked]>
Date: Wed, 15 Sep 2004 15:28:32 +0100

> 	say they won't occur because they will.

Well we seem to be disagreeing on a point of mathematics not protocol
here. I am saying that it is always going to be possible, in time
no worse than O(n) (correct case for "O") where n is the zone size,
to find a salt such that there are no hash collisions, provided that
the size of the zone is less than the square root of the size of the
hash space.

I agree a collision MAY occur, and my description for dealing with it
is to chose subsequent salts using a cyclic function of order at least
the hash length, until a collision doesn't occur. Such a cyclic function
might be "add one modulo max hash value".

I believe I've demonstrated that this process finds a salt providing
a non-colliding set (incidentally both non-colliding in the sense that
no hashed name collides with a name prior to hashing, an also that
no hashed name collides with any other hashed name), that the expected
number of iterations is less than 2, and that each iteration is o(n),
provided the requirements on maximum zone size are adhered to (as
per another email, they have no practical impact).

The foregoing is maths rather than protocol design (or at least
my attempt at maths), so it should be something objectively verifiable.
It's a fair while since I did this stuff academically, so perhaps
with more recent experience might like to chime in.

In a nutshell, I assert:

Given a set of n integers, p(i), where 0<=p(i)<K, and a hash function
H (satisfying all the normal properties) such that 0<=H(p(i),S)<J, and
K > n^2, and J<=K, it is possible to find a salt value S for the hash
such that:
  there is no (i, j) such that H(p(i),S)=p(j)
  and there is no (i, j) where i!=j such that H(p(i),S)=H(p(j),S)
by the algorithm of selecting a value S at random from the interval
O<=S<J, and, if the condition is not satisfied modifying S according
to a cyclic function of length J (such as adding 1), until the condition
is satisfied. I further assert that assuming hashing the set p(i) is
o(n), then finding a non-colliding S (i.e. an S satisfying the above
conditions) is no worse than O(n).

If that's a fair statement of the problem, we've reduced it to
a mathematical argument, yes? IE if my assertion is right, collisions
are not a problem?

> 	can't prove that don't exist).  There MUST be names for which

There must be such names for a given salt value (though such names
are computationally very hard to find). I am pretty sure one can
prove that there are not such names for ALL salt values. I am sure
one cannot prove that there ARE such names for all salt values.

Alex

---

From: Alex Bligh <[email-masked]>
Date: Wed, 15 Sep 2004 15:31:44 +0100

> At serving time, in case of collision, be famous:

I'm confused Roy - if you do the first two, how can the third ever
occur (even if you COULD find an SHA-1 collision). Or more accurately
you can avoid it by defining collision (in the first two) as either
H(i)=j OR H(i)=H(j) (i.e. regenerate the hash if you find two labels
hash to the same value - so you become potentially famous at hash
generation or name inclusion time, not at serving time)

Alex

---

From: Roy Arends <[email-masked]>
Date: Wed, 15 Sep 2004 16:40:03 +0200 (CEST)

On Wed, 15 Sep 2004, Alex Bligh wrote:

> occur (even if you COULD find an SHA-1 collision).
>
> Or more accurately

At generation/inclusion/serving time, it is virtually impossible to assert
the content of a future query. A hash over this future -yet-unknown- query
may collide with a hash over an existing name. You'll be famous at serving
time.

Roy

---

From: Ben Laurie <[email-masked]>
Date: Wed, 15 Sep 2004 16:37:48 +0100

> 	larger than the pre-hash space.

I agree, in theory. However, in practice, there's no way to have a zone 
with size 2^512, or even 2^160, so this is not a problem in real life. 
Even a zone large enough to have a 1 in 2 chance of a hash collision 
(2^80) is mind-bogglingly unlikely. If I'd started at the beginning of 
the Universe[1], I'd have to have generated 30 million domains a second 
to have a zone that large today.

Cheers,

Ben.

[1] 12,000,000,000 years ago, says me.

---

From: Ben Laurie <[email-masked]>
Date: Wed, 15 Sep 2004 16:40:01 +0100

> generation or name inclusion time, not at serving time)

The collision would be between the name requested and one of the 
existing names in the zone. And the reason you'd be famous is you'd have 
broken second preimage resistance for SHA-1.

Cheers,

Ben.

---

From: Ben Laurie <[email-masked]>
Date: Wed, 15 Sep 2004 16:48:35 +0100

> bits) would be limited to a (somewhat) smallish value.

In my proposal, the salt is a separate piece of data in the NSEC2 
record. I don't know how critical it is that it is small, given that the 
response includes signatures, which are huge.

> very last thing that the DNS needs.

I agree that this would be a good thing to avoid. I am less sure that it 
is avoidable if the problem is to be solved.

Cheers,

Ben.

---

From: Jim Reid <[email-masked]>
Date: Wed, 15 Sep 2004 17:19:46 +0100

>>>>> "Ben" == Ben Laurie <[email-masked]> writes:

    Ben> I agree, in theory. However, in practice, there's no way to
    Ben> have a zone with size 2^512, or even 2^160, so this is not a
    Ben> problem in real life.

Once upon a time people said that about MD5. There was supposedly no
realistic chance of two different input strings yielding the same hash.

---

From: Roy Arends <[email-masked]>
Date: Wed, 15 Sep 2004 20:34:42 +0200 (CEST)

> realistic chance of two different input strings yielding the same hash.

And thats it, there's the crux.

If a collision would be found we're en-masse shifting to a different hash
algorithm, instead of desperately trying to avoid collisions.

Roy

---

From: Simon Josefsson <[email-masked]>
Date: Wed, 15 Sep 2004 21:59:04 +0200

> realistic chance of two different input strings yielding the same hash.

In what way do you believe that is relevant?

If it is possible to find two (useful) inputs that have the same hash,
then the signature schemes in DNSSEC are dead.

Whether the hash function is collision resistant isn't critical for
the NSECbis idea.  One necessary property is that the output space is
large enough, so that with salting it is possible to find unique
output hashes for all owner names in existence.

This isn't something you have to trust some hash function designer on,
you can show this empirically yourself.  Compute hashes H(i) for
i=0...2^40 and count the number of distinct hash outputs you get.  If
that number is close to 2^40, the hash function is good enough to
avoid collisions by repeated salting, since DNS zone doesn't contain
more than 2^40 owner names.  Replace by 2^41 if you think 2^40 is too
small...

You can base the NSECbis idea on CRC-128 plus salting, and I think it
would still work.  As you know, it is trivial to find two inputs that
have the same CRC-128 output.  I think your argument is simply flawed.

I believe the hash function property that is needed for the NSECbis
idea is a large enough output space and non-reversibility.

Thanks,
Simon

---

From: Robert Elz <[email-masked]>
Date: Thu, 16 Sep 2004 04:53:11 +0700

Date:        Wed, 15 Sep 2004 16:40:01 +0100
    From:        Ben Laurie <[email-masked]>
    Message-ID:  <[email-masked]>

  | The collision would be between the name requested and one of the 
  | existing names in the zone. And the reason you'd be famous is you'd have 
  | broken second preimage resistance for SHA-1.

No, that's not true.

Or at least, it would be, but only if you're deliberately setting out
to find a name that hashes to a particular value - that's what's hard.

Merely getting an accidental collision with some unexpected name isn't
enough to make anyone famous.

Yet, the algorithms absolutely have to work when such things happen
(and they will happen - if rarely) - and not only the algorithms, but
the implementations as well.   Getting these "you'll never see it in
your or anyone else's lifetime" things wrong is the cause of the most
frustrating things to diagnose in any system, as the errors happen so
rarely - but they do happen.

kre

ps: all this noiose to attempt to achieve a totally worthless objective!

---

From: Mark Andrews <[email-masked]>
Date: Thu, 16 Sep 2004 08:09:03 +1000

> using transformed names, not plain text names.

And the transformed QNAMEs WILL collide on occasions with the transformed
names of the existing names in the zone.

> interloper passes back this collision with there being a genuine 

	The problem is that you can't return 9 NSEC7 13 + NXDOMAIN.
	The NSEC7 says that robertson exists.  The RCODE says that
	it doesn't.  IT DOES NOT WORK.

	To make HASHES works you need to make the HASH longer than the
	namespace and also guarantee that the hashes are unique for
	all possible inputs.  One could then take the hash use the first
	n octets as the name and store the remainder in the record to
	deal with collisions.  This will however make NSEC7s large.

	Instead of hashing into 16 octets you need to hash into 512 octets.
	Something larger than the input space (63 or 255 octets) .

---

From: Roy Badami <[email-masked]>
Date: Wed, 15 Sep 2004 23:32:13 +0100

>>>>> "Robert" == Robert Elz <[email-masked]> writes:

    Robert> Or at least, it would be, but only if you're deliberately
    Robert> setting out to find a name that hashes to a particular
    Robert> value - that's what's hard.

That's one of the things that's hard.  In crypto circles it's called
preimage resistance, and it's true that it's the weakest of the three
properties that a cryptographic hash function is expected to satisfy
(ie breaking it is the hardest).

The strongest of the three properties is collision resistance, and it
means that it's computationally infeasable to find two names that hash
to the same value.

It's bad cryptographic design to rely on stronger properties of an
underlying algorithm than you need to; but if the collision resistance
of SHA-1 was broken, that would be headline news...

	   -roy

---

From: Jim Reid <[email-masked]>
Date: Wed, 15 Sep 2004 23:56:58 +0100

>>>>> "Simon" == Simon Josefsson <[email-masked]> writes:

    >>  Once upon a time people said that about MD5. There was
    >> supposedly no realistic chance of two different input strings
    >> yielding the same hash.

    Simon> In what way do you believe that is relevant?

Because some people here seem to be saying that the chance of a hash
collision is so remote, it's not worth considering. That's been said
about previous crypto hash algorithms and later been shown to be a
false premise.

If things like ENUM and RFID tags take off, the DNS name space could
increase by one or two orders of magnitude, maybe more: ~4bn E.164
phone numbers and how many billion Coke cans, each name with how many
RRtypes? Once we're in the realm of billions of names the probability
a hash collision is much more likely. Too bad if they're in the same
(enormous) zone.
 
    Simon> If it is possible to find two (useful) inputs that have the
    Simon> same hash, then the signature schemes in DNSSEC are dead.

Not so. In DNSSECbis, the RRSIG is what matters. That depends on the
secrecy of the private key that signed some hash value. How that hash
is computed doesn't really matter. Though it makes sense to use
something strong like SHA to get a hash string that's long and random
enough to protect against cryptanalytic attacks on the key. [For some
definition of "strong", "long" and "random".] Besides, the original
input to the hash function is known so that a validator can recompute
the hash value and compare that to what was found in the signature.

    Simon> Whether the hash function is collision resistant isn't
    Simon> critical for the NSECbis idea.  One necessary property is
    Simon> that the output space is large enough, so that with salting
    Simon> it is possible to find unique output hashes for all owner
    Simon> names in existence.

This looks like hand-waving to me. Sorry.

And won't "all owner names in existence" include the RRs containing
the generated hash strings? Suppose I have a client that does an ANY
query for foo.bar. This name didn't exist in the unsigned zone. But
foo is the label resulting from hashing the bar zone's SOA
record. What response does my client get back? How is that signed?

Just put the hash string in the RDATA for some RRtype and the whole
issue about collisions goes away. So does the prospect of having to
deal with hashes that collide with existing CNAME, DNAME and
delegation points as yet more corner cases that need special
treatment.

---

From: Ben Laurie <[email-masked]>
Date: Thu, 16 Sep 2004 00:30:40 +0100

> (Although now you really could play "change the salt, Walt" to finesse 

The way to fix this is to show an NSEC record when NSEC' fails because 
of a hash collision.

Since a good fraction of the world thinks that NSEC' is pointless, 
there's no chance that NSEC is going away, making this solution cheap, 
as well as (of course) 100% effective.

People actually bothering to sign NSECs in case this happens before the 
Sun burns out will spend twice as much on hardware, but the edge case 
has been handled totally.

Excellent suggestion. Superb. Thankyou.

Cheers,

Ben.

---

From: Ben Laurie <[email-masked]>
Date: Thu, 16 Sep 2004 00:35:56 +0100

> realistic chance of two different input strings yielding the same hash.

People said it was practical to have a zone of size 2^128?

The unrelated fact that there exist broken hashes is by no means a 
disproof of the general concept that there are an awful lot of possible 
outputs from cryptographic hash functions.

Cheers,

Ben.

---

From: Mark Andrews <[email-masked]>
Date: Thu, 16 Sep 2004 09:57:38 +1000

> outputs from cryptographic hash functions.

	The zone size is irrelevent.

	If the number of QNAMES > number of hash function outputs
	(true of all the proposals todate).

	You will have collisions.  They CANNOT be prevented.

	The only way to prevent this is to change the hash function
	so that the number of QNAMES <= number of hash outputs *and*
	that for all QNAMES the output is unique.  You then have
	the problem of how to store the resultant hash.

	For NSEC the hash function returns its input.  It also meets
	all the required properties above.

	Now we know the QNAME space.  You need to pick a hash
	function that has the properties above.  So far I have
	yet to see anyone propose one.

	Mark

---

From: Alex Bligh <[email-masked]>
Date: Thu, 16 Sep 2004 10:01:22 +0100

--On 15 September 2004 23:56 +0100 Jim Reid <[email-masked]> wrote:

> collision is so remote, it's not worth considering.

No, people (well me) are not saying that. People are saying that the chance
of hash collision is very remote, but you DO have to worry about it (if
it's necessary to avoid collisions at all - which I am not sure of, but
there are people who know more than me on that one), but the statistics
tell you that iteratively changing the salt is a sufficient solution to the
problem.

Alex

---

From: Simon Josefsson <[email-masked]>
Date: Thu, 16 Sep 2004 13:35:32 +0200

> about previous crypto hash algorithms and later been shown to be a

I don't know about "people", but I'm not saying that.  I'm saying that
the problem of hash collisions isn't relevant to the NSECbis idea,
especially if salting is part of the solution.

Whether or not some hash function is collision resistant can be a fun
discussion, but if you want to show that it is relevant to the NSECbis
discussion I think you'll have to show in what way it is relevant.  So
here's the exercise: Show that NSECbis based on CRC-128 is worse than
NSECbis based on SHA-1.  CRC-128 is trivially breakable, SHA-1 is
currently presumed not to be.

> a hash collision is much more likely. Too bad if they're in the same

Could you do the math to show us how likely?  That would be useful
input.

> This looks like hand-waving to me. Sorry.

Did you read my next paragraph?  What part of it didn't convince you
of the above?

  This isn't something you have to trust some hash function designer
  on, you can show this empirically yourself.  Compute hashes H(i) for
  i=0...2^40 and count the number of distinct hash outputs you get.
  If that number is close to 2^40, the hash function is good enough to
  avoid collisions by repeated salting, since DNS zone doesn't contain
  more than 2^40 owner names.  Replace by 2^41 if you think 2^40 is
  too small...

> record. What response does my client get back? How is that signed?

You get back the NSECbis RR for the SOA, since it is stored at
foo.bar:

foo.bar IN NSECbis baz SOA
foo.bar IN RRSIG ...

You can prove that there are no other types at foo.bar than NSECbis
and RRSIG by including the NSECbis with the owner name H(foo.bar).

> delegation points as yet more corner cases that need special

That sounds good, but I don't follow.  What would the owner name be,
and what would the hash string be computed on?  How would it be used?

Thanks,
Simon

---

From: Alex Bligh <[email-masked]>
Date: Thu, 16 Sep 2004 15:03:49 +0100

> 	You will have collisions.  They CANNOT be prevented.

Aaahhhhhhh - you are talking about a different type of hash collision.

I have previously been talking about collisions either between the hashed
values of two RR labels, or between the hashed value of one label and the
unhashed value of the other. These are avoidable [1] because the number of
labels (and thus the number of hashed labels) in the zone is limited.

You are (here), I think, talking about potential collisions between the
hashed value of a QNAME, and hashed values of RR labels in the zone file,
where the unhashed QNAME does not correspond to the RR label.

I now understand the comment "if you find one of these you get to be famous
on serving the record".

However, I don't think it necessarily breaks anything.

Let's assume you agree with [1] above (that you can create a zone without
collisions with "itself") which I'm pretty sure is correct.

Now the problem to be solved is that there is a very large number of
possible QNAMEs and it is possible (albeit unlikely) that a query is made
with a QNAME which has the same hash with something already in the zone
file.

So let's assume that there are a set of labels P(1)..P(n) in the zone which
are ordered by hashed order, and that they we have a non-colliding salt,
meaning there is a value S such that:
* For no i,j, H( P(i), S ) = P(j)
* For no i,j, i!=j, H( P(i), S ) = H ( P(j), S)

And let's further assume we have a colliding Query Q, such that
for some k,

  H(Q, S) = H( P(k), S ), but P(k) != Q

Now, if someone makes a query for Q, BY ASSUMPTION the zone is non-self
colliding, so RR Q does not exist (else RR Q would have the same hash as
P(k) and we'd have chosen a different salt - as we could detect this at
zone preparation time).

So if we return an NSEC-x record that says "there are no RR's in the [open]
interval H(P(k), S) ... H(P(k+1), S)", that also implies that there ARE
RR's at P(k), and P(k+1), and thus BECAUSE the zone is non-colliding with
itself (see [1]), that OTHER than the exact label names P(k), P(k+1), there
are no other RR's with the same hash and thus "there are no RR's in the
[closed] interval H(P(k), S) ... H(P(k+1), S)) other than P(k) and P(k+1)".
Provided the reply contains the QNAME whose existence is being denied,
the "other than" cases can be distinguished.

Thus I think that provided we have (as described in a previous email)
prevented the zone from colliding with itself, we can still effectively
do an authenticated denial of existence for a QNAME whose hash collides
with an RR which is present, and for that RR.

Alex

---

From: Roy Badami <[email-masked]>
Date: Thu, 16 Sep 2004 15:38:58 +0100

Alex> Now the problem to be solved is that there is a very large
    Alex> number of possible QNAMEs and it is possible (albeit
    Alex> unlikely) that a query is made with a QNAME which has the
    Alex> same hash with something already in the zone file.

I think even that will make you famous, assuming you're using
full-length SHA-1.

Someone needs to do that maths and estimate an upper bound on the
probability of this ever happening.

ie assume that:

   * the distribution of the output of SHA-1 is uniformly distributed
   * we have the largest zone we can ever imagine
   * we have the largest number authorative namesservers we can imagine
   * these nameservers are the fastest we can imagine
   * they are speding all their time answering queries for random non-existent
     names

And then work out the probability of *ever* seeing a collision
assuming 160 bit hashes.

Let's choose some figures for the above, and then work out whether
this is worth worrying about.

     -roy

---

From: Robert Elz <[email-masked]>
Date: Fri, 17 Sep 2004 01:39:26 +0700

Date:        Thu, 16 Sep 2004 15:38:58 +0100
    From:        Roy Badami <[email-masked]>
    Message-ID:  <[email-masked]>

  | 
  |     Alex> Now the problem to be solved is that there is a very large
  |     Alex> number of possible QNAMEs and it is possible (albeit
  |     Alex> unlikely) that a query is made with a QNAME which has the
  |     Alex> same hash with something already in the zone file.
  | 
  | I think even that will make you famous, assuming you're using
  | full-length SHA-1.

Perhaps.

But that isn't really the one that is interesting.   Assuming the hashes
are in the zone as owner names (if they're not, then I don't care in the
slightest about clashes - others might - but that's just the security
algorithms, etc, which are outside my field of interest) then the clash
that matters (in this area) is when the QNAME clashes with a NSEC' hash.

And that isn't even slightly hard to imagine - I simply query for any
random nonsense, get back the NXDOMAIN/NODATA, along with the NSEC' record,
take the hash value from it, and do a query on that as a QNAME.

So, let's assume that in the example.com. zone I have

	* IN MX 10 target.
	www IN A 10.11.12.13

(along with the NS and SOA records for the zone itself of course, but they're
not adding any new names).   That's it.

Now, I query for foo.example.com (type A), get back NODATA and a NSEC' record
that demonstrates that "foo" doesn't exist (along with whatever else is
required to generate the right answer proof, which I don't care about here).
For the purposes here, let a hash value in the NSEC' be H.

Now I query for H.example.com. (MX).

What do I get here?    If I get NODATA, then you have just broken my
wildcard MX.   If I get "IN MX 10 target." then you have just broken the
DNS lookup algorithm.

Neither is acceptable.

More than that, I assert that my domain (as example.com. in the above)
is mine - I registered it, and I decide what names go in it.   You (being the
IETF or any other standards body) have no business whatever creating names
in my zone - no names whatever.   That's my ballpark to play in.   And this
is a much more fundamental principle than having non-enumerable zones.

kre

---

From: Alex Bligh <[email-masked]>
Date: Fri, 17 Sep 2004 10:42:42 +0100

--On 17 September 2004 01:39 +0700 Robert Elz <[email-masked]> wrote:

> (along with the NS and SOA records for the zone itself of course, but
> they're not adding any new names).   That's it.
>
> Now, I query for foo.example.com (type A), get back NODATA and a NSEC'
> record that demonstrates that "foo" doesn't exist (along with whatever
> else is required to generate the right answer proof, which I don't care
> about here). For the purposes here, let a hash value in the NSEC' be H.
>

You get "IN MX 10 target.". The zone is generated to be non-SELF-colliding
so the only record at H is an NSEC' record. Returning an NSEC' record
for ANY type of query other than NSEC' is ALWAYS a bad idea.

The situation is no different from the zone
    * IN MX 10 target.
    www IN A 10.11.12.13
    H IN TXT "foobar"

If you do a query of type MX for H, you would not expect the TXT record
to be returned, you'd expect the wildcard MX to be returned. And just
the same happens with the example you have above with
   * IN MX 10 target.
   www IN A 10.11.12.13
   H IN NSEC' blah

Alex

---

From: Peter Koch <[email-masked]>
Date: Fri, 17 Sep 2004 12:02:08 +0200

> for ANY type of query other than NSEC' is ALWAYS a bad idea.

but that interferes with how wildcards work. The name H exists (per the NSEC
RR), so the wildcard doesn't apply - regardless of QTYPE.

> to be returned, you'd expect the wildcard MX to be returned. And just

One might expect that, but it again isn't how wildcards work (see parallel
thread).

The basic problem is that hashes, if they use the same namespace (and currently
there is no alternative) will introduce new names into the zone. The not so
trivial question is whether this is an academic problem or whether it can
lead to problems or be abused. Look, for example, at those NSEC' RRs which
deny their own existence.

-Peter

---

From: Alex Bligh <[email-masked]>
Date: Fri, 17 Sep 2004 11:12:13 +0100

(Replying to myself).

> with an RR which is present, and for that RR.

Hmmm... I've been thinking about this a bit more.

Here is a demonstrable potential problem with hash collision:

Let us assume you have a non-self-colliding zone with salt S - which
I allege one can generate:

; exampel.com presented out of order for clarity

	xxx	IN	MX	1.1.1.1 ; Hash is 1000
	foo	IN	MX	2.2.2.2 ; Hash is 2000
	bar	IN	MX	3.3.3.3 ; Hash is 3000

	...	IN	NSEC'	1000
	1000	IN	NSEC'	2000
	2000	IN	NSEC'	3000
	3000	IN	NSEC'	...

As the hash space is smaller than the QNAME space (assuming we don't want
to use all 8 bits to represent hashes that's always the case), then there
WILL always be a finite number of QNAMEs having the same hash values as
some of the labels in the zone (though they will be stupendously difficult
to find).

Let's assume, however, that we have one, for instance baz.example.com which
ALSO has hash value 2000.

I do an MX query for baz.example.com. I get back a proof (manner
irrelevant) that says hash values 2000 - 3000 (exclusive) don't exist. Now
according to my previous posting, I could infer from getting that back that
baz.example.com does not exist, as I know there is a label with hash value
2000 that does exist, and the record with hash value 2000 WAS
baz.example.com, then I'd have got back an MX record (not a denial of
existence).

But a (potential) problem arises here: If I do an MX query for
foo.example.com, and some interloper captures the response and substitutes
it for the same denial of existence as above (i.e. the same one I'd have
got asking for foo.example.com), then by my own logic, I'd have to conclude
that foo.example.com didn't exist (or I'd have received an MX record back).

What I think this means is that any NSEC' proof of the sort above can only
disprove the existence of hash values 2001-2999 (etc.) and the existence of
a single (unspecified) record with hash value 2000 (and similarly with
3000). One cannot draw an implication as to whether that record is, or is
not, the QNAME (if one worries about hash collisions with QNAMEs).

Now clearly the label could always be returned in the NSEC' reply, but that
would get us back to enumerability.

I think the way to fix this is as follows: if the QNAME does not
have the same hash as any record (i.e. falls into the open interval
between NSEC' records), then simply return then NSEC' record. So
if the QNAME has hash 1001, the resolver, seeing there are no records
between (open interval) 1000 and 2000, can assume the QNAME does not
exist.

In the circumstance where there *IS* a hash match, in the response,
return the original label that generated that hash. So in the case
above of a query for baz.example.com (hash 2000), return foo.example.com,
as well as the normal NSEC' proof. Now this could either be done
by returning additional records (though I'm not sure those always
get passed through the system enough) which would be cleaner, or
failing that by having two presigned NSEC' proofs for the
interval 1000,2000, one with foo.example.com (to be returned to
deny existence of QNAMES with hashes of 1000 exactly), and one without
(to be returned to deny existence of QNAMES with hashes of 1001-1999
inclusive) - (NB QNAMES with hash exactly 2000 go into the next pair
of NSEC' records). This doesn't enable enumerability for a strong
hash as in order to get the record back with foo.example.com in,
you'd either have to already know foo (which is hard), or to be
able to break the hash (i.e. generate an arbitrary QNAME with hash
1000). The latter as we know is computationally extremely difficult.

The unlikelihood of the second form NSEC' records ever occurring might
make interoperability testing difficult. This could be resolved by
making a deliberately weak hashing mechanism mandatory for interoperability
testing.

Alex

---

From: Alex Bligh <[email-masked]>
Date: Fri, 17 Sep 2004 11:27:18 +0100

> One might expect that, but it again isn't how wildcards work (see parallel

OK - I wondered if Robert might mean that, so I set up a test before
posting. Try
  dig MX H.example.alex.org.uk

I get:

;; ANSWER SECTION:
H.example.alex.org.uk.  494     IN      MX      10 target.example.com.

No mention of:
;; ANSWER SECTION:
H.example.alex.org.uk.  360     IN      TXT     "HASH"

Or are you saying that's changed in DNSSEC?

Alex

---

From: Peter Koch <[email-masked]>
Date: Fri, 17 Sep 2004 13:31:06 +0200

> Or are you saying that's changed in DNSSEC?

No, I'm saying that these observations suggest the nameserver implementation
used to serve the zone is not protocol conformant (with or without wcard-
clarify). They also stumble over a QNAME like 'foo.*.example.alex.org.uk'.

-Peter

---

From: Alex Bligh <[email-masked]>
Date: Fri, 17 Sep 2004 12:51:42 +0100

Peter,

--On 17 September 2004 13:31 +0200 Peter Koch <[email-masked]> 
wrote:

> No, I'm saying that these observations suggest the nameserver
> implementation used to serve the zone is not protocol conformant (with or
> without wcard- clarify). They also stumble over a QNAME like
> 'foo.*.example.alex.org.uk'.

Robert pointed that out off list - I used UltraDNS as the sandbox is behind
a firewall. So I tried on the sandbox on Bind 9, and it returns NOERROR,
but no data.

So my question is, if the zone is
     * IN MX 10 target.
   www IN A 10.11.12.13
   H IN NSEC' blah

And the hash of www is H, what breaks if, on a query of type MX for H,
it returns:
   H IN MX 10 target
(i.e. ignores the NSEC' record).

Alex

---

From: Robert Elz <[email-masked]>
Date: Fri, 17 Sep 2004 19:31:53 +0700

Date:        Fri, 17 Sep 2004 12:51:42 +0100
    From:        Alex Bligh <[email-masked]>
    Message-ID:  <864823E63085C47CEEC82009@[192.168.100.25]>

  | And the hash of www is H, what breaks if, on a query of type MX for H,
  | it returns:
  |    H IN MX 10 target
  | (i.e. ignores the NSEC' record).

The "ignores the NSEC' record" is not nearly as easy as it seems like
it might be (as a message from Mark Andrews pointed out a few days ago).

But even if it is easy, explaining how wildcards work now is difficult,
and than's when it is all simple, and clean, and consistent (difficult
because it sometimes isn't what people are hoping for, or are expecting
based upon the assumption that wildcards do pattern matching).

Expecting anyone to ever understand the things if we start adding special
cases to the algorithm is beyond hope.

kre

---

From: "Olaf M. Kolkman" <[email-masked]>
Date: Fri, 17 Sep 2004 14:47:50 +0200

On Fri, 17 Sep 2004 12:51:42 +0100

>  (i.e. ignores the NSEC' record).

In other words you would propose that the searching algorithm would be
modified based on the qtype queried? 

If so ...auucchhh.... :-) 

NB it is not that one cannot propose a change to the full standard,
wildcard carify proposes (will propose) a change on how wildcard owned
CNAMEs are dealth with.

A Little Side Track (I am not sure if these scenarios have been
scetched, apologies if I am duplicating arguments)

EBS1 (Evil Bastard Scenario 0ne):

I own secret-wg.org.

Tomorrow I am going to register 
 HASH(salt=0x00, secret-wg.org).org
 HASH(salt=0x01, secret-wg.org).org
 ...
 HASH(salt=0xff, secret-wg.org).org

Just to make the changes on a hash collission in secret-wg.org 2^24
instead of 2^32. The hash colission being an anoyance during signing
because you have to regenerate all NSEC2s with a different salt not
because you happen to hit a "real" name.

This can be distributed over mulitple registrants can do this each carying 
their part of the registration costs:

 HASH(salt=0x00, secret-wg.org).org
 HASH(salt=0x01, kolkman.org).org
 ...
 HASH(salt=0xff, marnick.org).org
 ...
 HASH(salt=0xffff, geerthe.org).org

you could actually do a DDOS attack on the zone signing process if the
salt space is to small. Practically I think 32bits of salt is
sufficient to mitigate this, so is registration policy.

EBS 2:

Today the .org registry generates their NSEC2s with salt(0x4e8aeb32).
I register
HASH(salt=0x4e8aeb32, secret-wg.org).org
That forces the .org registry to roll their salt to e.g. salt(0x23a5883d)
at which point I register
HASH(salt=0x23a5883d, secret-wg.org).org

Problematic? Maybe.. I force them to sign all NSEC2 RRs for all owner
names in their zone while otherwise they could have used incremental
signing.

The underlying assumption for this is that one version of the zone
would have the same salt for all the NSEC2 RRs. This would not occur
if the NSEC RRs would have owner names in a different namespace in
wich you would not be able (or allowed) to register names (a policy
and not a protocol issue).

--Olaf
  as namedropper.

---

From: Alex Bligh <[email-masked]>
Date: Fri, 17 Sep 2004 14:27:36 +0100

Olaf,

> wildcard carify proposes (will propose) a change on how wildcard owned

I'm not so much proposing it as trying to work out what it would break.

Incidentally, is the searching algorithm based on the QCLASS queried?
It seemed peculiar to me that NSEC records were of QCLASS "IN"
given I suppose they should be equally applicable to HS records etc.
If the searching algorithm is indeed currently based on QCLASS (or
if changing that doesn't break much given lack of other classes),
then perhaps having NSEC' as a CLASS rather than a TYPE would fix
both the above, and the colliding namespace problem.

...
> sufficient to mitigate this, so is registration policy.

This is perhaps not as stretched a scenario as you might think even with
LONG salts if one is dumb about the cyclic algorithm used (that's why I
said "cyclic function of cycle-length N"). The reason is because whilst one
can show that the expected number of recalculations is less than 2, if an
attacker KNOWS the cyclic algorithm used to produce subseqeuent salts, they
could in theory generate names that would collide with a large number of
subsequent salts. This suggests that the salts themselves should be
produced using a cyclic algorithm known only to the signer, for instance:
 S(i) = H( i, private value)

[pointless aside: perhaps the registry concerned won't mind the extra
CPU cycles with all that extra income flowing in]

> names in their zone while otherwise they could have used incremental

Indeed - you can speed up roll of the salt.

To the extent this is a problem, it could be resolved/mitigated either by
a) Ensuring the NSEC' records are in a separate namespace completely
   (see other thread) [resolution] (evil grin: perhaps we should chose
   the currently maldefined "salt.*.example.com IN NSEC ..."); or
b) Ensuring that NSEC' records representation is unlikely to clash
   with incrementally added namespace; for instance, ensure all
   NSEC records are of the form "_23a4883d NSEC..." (etc.) - that's only
   going to be susceptible when you can add NSEC records beginning
   with "_" (evil grin: perhaps we should chose "*23a4883d NSEC ...").

> and not a protocol issue).

Yep I think that's (a) above.

Another way of mitigating this might be to have multiple NSEC' chains,
each with a different salt. Then you only have to roll one complete
chain.

Alex

---

From: Edward Lewis <[email-masked]>
Date: Fri, 17 Sep 2004 09:29:24 -0400

...
>	it doesn't.  IT DOES NOT WORK.

You can - if it's defined to be allowed.  Name error means that the 
name desired is not found - not that the hash of the name is not 
found.  (We've never defined any semantics for hashes of names.)

OTOH, even if you define a hash mess to avoid collisions at signing 
time, you can't guarantee against a query name's hash clash.

And OTOH - I agree with KRE, this is a lot of noise about a non-issue.

---

From: Mark Andrews <[email-masked]>
Date: Sat, 18 Sep 2004 08:04:20 +1000

> time, you can't guarantee against a query name's hash clash.

	Thank you Ed.  You at least are repeating (if not hearing)
	what I have been saying.
 
	robertson was the QNAME the has was 9.

---

From: Edward Lewis <[email-masked]>
Date: Fri, 17 Sep 2004 20:10:39 -0400

>	Thank you Ed.  You at least are repeating (if not hearing)

Well I think a lot of us are coming around to that reality now.  I 
realized it when I wrote the example - by accident.  I'm not saying I 
was the first to realize it - but that's when I realized it.

BTW - I have never been a fan of hash approaches, not even then they 
were first discussed in 99 or so.  To me there's a siren's call 
associated with them.  I guess I have been brainwashed into thinking 
zone enumeration is a given, but really I can understand why it's 
undesirable (to say the least).

So far just about all of the "complaining" (for lack of a better 
word) about zone enumeration seems to have come from large 
registries.  Question: is zone enumeration a more general "problem?"

I ask this because if zone enumeration is only a problem for large 
registries, can it be assumed that a solution that is heavy-handed be 
acceptable?  Saying "large" carries the assumption of well-funded, 
attendant operating staff, and with (machine) resources under one 
control.  "Heavy-handed" in the sense that it would take a 
considerable out-of-band effort to maintain.

Digging further, if the assumption can be made that the only 
organizations that will need to "defend" against zone enumeration are 
well-funded to do so, an approach like on-line signing appears to be 
a start to a solution.  (I'd call it heavy handed in the sense that 
key management is needed.)  A "start" - I want to emphasize that.

This is all premature still, I don't know if we've come to an 
understanding of the problem (requirements).  But all this talk about 
hashing and salt...
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                            +1-703-227-9854
ARIN Research Engineer

---

From: Paul Vixie <[email-masked]>
Date: Sun, 19 Sep 2004 03:54:32 +0000

ed lewis wrote, as his way of demonstrating that he has me in his KILL
file and hasn't read a thing i've posted to namedroppers this year:

> ...
> 
> So far just about all of the "complaining" (for lack of a better word)
> about zone enumeration seems to have come from large registries.
> Question: is zone enumeration a more general "problem?"

no.

> acceptable?

yes.

> well-funded to do so, an approach like on-line signing appears to be a
> start to a solution.

exactly right.

if one principle of good engineering is to minimize cost in the average case,
then dnssec-bis is nearly complete as-is, and the only thing that's needed
is to ensure that online signing isn't a "white lie" but rather signalled
unambiguously in the protocol.  people who fear enumeration will use "views"
if they are a registrant (which they are already doing, according to me),
or online signing if they are a registry.  people who don't fear enumeration
will run vanilla dnssec-bis with no special stuff.  everybody will be happy
except the registry operators who didn't want to pay extra megabucks for the
online signing capability, and nobody will sympathize because we all know
they will just pass these costs on to the registrants, or reduce their
operating margins, or both.

---

From: Simon Josefsson <[email-masked]>
Date: Sun, 19 Sep 2004 12:57:01 +0200

> registries.  Question: is zone enumeration a more general "problem?"

Yes.  The risks in smaller zones further down in the domain tree are
different from the risks in zones higher up in the tree, but they do
exist.  The citation I like to give, on risks in smaller zones, is:

  Steven M. Bellovin, "Using the Domain Name System for System Break-Ins", in
  Proceedings of the Fifth Usenix UNIX Security Symposium, Salt Lake City, UT,
  June, 1995. http://www.research.att.com/~smb/papers/dnshack.pdf

> considerable out-of-band effort to maintain.

Without any details of what you are thinking of, it is difficult to
say.  Even todays DNSSEC require various out-of-band efforts to
maintain; for key exchanges, root key configuration, key rollover etc.
If it was on that magnitude, it isn't a problem, but if this is more
heavy-handed than that, I'm not so sure.

Thanks,
Simon

---

From: Paul Vixie <[email-masked]>
Date: Sun, 19 Sep 2004 15:25:07 +0000

>   Steven M. Bellovin, "Using the Domain Name System for System
>   Break-Ins", in Proceedings of the Fifth Usenix UNIX Security
>   Symposium, Salt Lake City, UT, June, 1995.
>   http://www.research.att.com/~smb/papers/dnshack.pdf

i say no.  smaller zones further down in the domain tree who fear
enumeration are already using views, because turning off AXFR isn't
good enough for them.  note that the bellovin paper and presentation
were better than mine at the same conference:

    Vixie, Paul A., "DNS and BIND Security Issues", Proceedings of the
    Fifth Usenix UNIX Security Symposium, Salt Lake City, UT, June, 1995.
    http://sa.vix.com/~vixie/bindsec.psf

but i stand by what i wrote -- most dns-related breakins up to that time
were due to poor dns implementations rather than to data exposure.

---

From: Alex Bligh <[email-masked]>
Date: Sun, 19 Sep 2004 16:59:31 +0100

--On 19 September 2004 15:25 +0000 Paul Vixie <[email-masked]> wrote:

>> Yes
...
> i say no.

Guys - aren't we back to discussing what our chairs suggested
we shouldn't discuss (hence the 20 line statements of position).

Alex

---

From: Simon Josefsson <[email-masked]>
Date: Sun, 19 Sep 2004 18:17:13 +0200

Paul Vixie <[email-masked]> writes:

> good enough for them.

Aren't views only useful if you can control, or find out, from where
the DNS information will be accessed?

If owners of a small zone want to be able to go into an Internet cafe
(in other words, an "unknown" IP address), and be able to look up
their server's hostname in DNS, views doesn't seem to be a solution.

My claim is that it is useful for the small zone owner to prevent
trivial enumeration via NSEC, but still permit public access to the
data.  As described in Bellovin's paper, trivial enumeration allow
attackers to easily find out names of all targets of an attack.

Gathering the same information without trivial NSEC enumeration is
more difficult, and may be enough to hold off some percentage of
attackers.  Since there is no absolute security, fending of some
percentage of attackers is what various security measures can hope to
achieve.  We can discuss the actual percentage figure, but my view is
that it is significant.  Think "script kiddies" that exploit the
latest flaw in Sendmail/OpenSSH/BIND against every server in your
domain.

The situation is comparable to other databases with public but
sensitive information.  Like WHOIS.  Full access can be restricted,
but still queries are allowed.  I good discussion of the social
aspects is given in <http://www.cs.uwyo.edu/~rex/privacy.html>.

In any case, if "views" would be the suggested remedy for this problem
for small zones, the idea should be adopted and described by the WG.

Thanks,
Simon

---

From: Paul Vixie <[email-masked]>
Date: 19 Sep 2004 17:45:41 +0000

> the DNS information will be accessed?

"views" is a BIND9 thing.  a view can be selected based on the ip address
of a requestor, or on other criteria (like signing with a certain TSIG key).

> their server's hostname in DNS, views doesn't seem to be a solution.

that's kind of what the TSIG key does for you.

> attackers to easily find out names of all targets of an attack.

my counterclaim is that if the public has access to the data, then even a
moderately determined attacker can find enough hostnames (from Received:
headers in e-mail archives, from web crawling, from traceroute, from doing
a dictionary attack) that a small zone owner who is worried about
enumeration is going to have to use views to prevent queries from 
succeeding.  turning off axfr, or changing dnssec to prevent nsec-walking,
isn't going to be enough for these people.  the problem they're having is
already in their lives, and allowing nsec-walking doesn't make it worse,
and preventing nsec-walking would not make it better.

it's worth noting that small zone owners are the primary audience for BIND,
and their needs (as revealed by consulting, support, software development,
and other contacts made by myself and others at ISC over the last 25 years)
are the driving force behind BIND9 having "views" in the first place.  i
possess direct knowledge, in other words, of who wants this feature, who
uses this feature, and why.

> latest flaw in Sendmail/OpenSSH/BIND against every server in your

this opens a new category of victim -- the hapless kind.  you're assuming
that folks who would be hurt by enumeration cannot self-identify.  this is
not my experience -- for instance, BIND4 was the first dns implementation
to allow the protocol breakage known as "prohibiting or limiting axfr", and
as with views, i know who this was added to please, and why they wanted it.

if we're going to specify DNS in such a way that implementations are all
required to lock down the set of features that "hapless zone owners" would
be injured by if the defaults weren't restrictive, then that's a new topic.
presumably such a regime would include restricting zone transfers (which is
not described in the protocol), using TSIG to enable views of sensitive
data (which is not described in the protocol), and things like strong root
passwords, non-world-readable zone files, and so on.  that's a big project
and it may belong in a different ietf area than the one namedroppers is in.

> for small zones, the idea should be adopted and described by the WG.

that's at best premature.  the requirements document isn't done yet.  this
thread is part of a debate as to whether confidentiality should be listed
as a requirement.
-- 
Paul Vixie

---

From: Mark Andrews <[email-masked]>
Date: Mon, 20 Sep 2004 08:20:22 +1000

>   June, 1995. http://www.research.att.com/~smb/papers/dnshack.pdf

	This is no so much zone enumeration but lack of security in
	the answers being returned.

	AXFR was in both the solution and problem spaces.  It gave you
	the names but it also allowed the caches to be protected from
	spoofing of replies.  The problem was and still is that AXFR
	doesn't scale and you couldn't know in advance all the names
	that would be added to .rhosts files.

	As with most things enumeration was not just bad or just good
	but a mixture.

	Mark

---

From: Simon Josefsson <[email-masked]>
Date: Mon, 20 Sep 2004 01:14:12 +0200

Paul Vixie <[email-masked]> writes:

> succeeding.

I don't see how these claims are in conflict.  Preventing zone
enumeration, like disabling AXFR, prevent some problems.  They don't
prevent all problems, and may even introduce new ones.

I agree that an attacker who spend more time to break in will
eventually find Received: headers etc.  But that was sort of my point.
To secure something, you remove the simple attack vectors first.  That
is, in this case, zone enumeration.  If eventually the total time
required for the break in become too costly, you have succeeded.

> turning off axfr, or changing dnssec to prevent nsec-walking,

We disagree here.  I believe preventing nsec-walking may make things
better.  It is difficult to quantify by how much objectively.

> uses this feature, and why.

Excellent, let's build on that.  What are the motivations for using
"views"?  What risks do your customers perceive with publishing all
their information in public, that presumably made them consider using
"views"?

> be injured by if the defaults weren't restrictive, then that's a new topic.

I'm not saying that.  Instead, and naturally, implementors that don't
perceive that their users fear zone enumeration should not implement
proposals like NSECbis.

> and it may belong in a different ietf area than the one namedroppers is in.

Right.  It seems, at best, something for DNSOP.

> thread is part of a debate as to whether confidentiality should be listed

I don't think the term "confidentiality" properly describe what the
requirement should be here.  The word's negative connotations are
heavy, from the vanilla DNS point of view, which suggest that
"confidentiality" shouldn't be a requirement.  Perhaps you get another
thought process if you ask whether permitting new vulnerabilities to
DNSSEC should be a requirement or not.  Neither spin is useful,
though.

Thanks,
Simon

---

From: Samuel Weiler <[email-masked]>
Date: Wed, 22 Sep 2004 09:15:32 -0400 (EDT)

> already exists as a delegation point or CNAME.

Apologies if this has been mentioned before[1], but I couldn't find it
in this thread, and it came up in a discussion yesterday...

The way I understand the proposals on the table, this sort of
collision is fine and dandy.  No "real" name should "naturally" have
an NSEC++.  If another "real" name happens to hash to another existing
name, you insert the NSEC++ there as normal.  The pre-existing "real"
name has it's corresponding NSEC at some (presumably different) name.

Example:

"real" names:
	example.com SOA/DNSKEY/etc.  (the apex)
	a.example.com A 127.0.0.1
	overly-long-name.example.com A 10.1.1.1

Hash all three:
	hash(apex) ---> qwertyuiop\034\011zyxw
	hash(a) ---> overly-long-name
	hash(overly-long-name) ---> acbdefghijklmnoz\000\009

And add these three NSEC++ RR's when signing [1]:
	acbdefghijklmnoz\000\009 NSEC++ qwertyuiop\034\011zyxw A
	qwertyuiop\034\011zyxw  NSEC++ overly-long-name SOA DNSKEY NS
	overly-long-name NSEC++ acbdefghijklmnoz\000\009 A

If anyone every queries for (overly-long-name,IN,MX), they get the
acbdefghijklmnoz\000\009 NSEC++ record.

So there's no conflict between having "real" RRsets and generated
NSEC++'s at the same name.

-- Sam

[1] The type bitmaps in these aren't quite right; they omit RRSIG and
NSEC++.

---

From: Ben Laurie <[email-masked]>
Date: Wed, 22 Sep 2004 15:22:59 +0100

> because you happen to hit a "real" name.

Eh? This makes the chances 2^104, not 2^24, surely?

> HASH(salt=0x23a5883d, secret-wg.org).org

No, if you want to force them to change their salt, you must find a hash 
collision with the current salt, work factor 2^80.

> names in their zone while otherwise they could have used incremental

Now you've lost me.

> would have the same salt for all the NSEC2 RRs.

It has to, or the proof doesn't work.

> This would not occur

Hmm. In that case, I have not understood your examples. :-(

---

From: Ben Laurie <[email-masked]>
Date: Wed, 22 Sep 2004 15:22:34 +0100

> cases to the algorithm is beyond hope.

I don't really buy that adding "ignore NSEC' records" is really going to 
confuse people to any noticable extent.

Cheers,

Ben.