Subject: Re: dictionary attack on nameservers

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.

--
to unsubscribe send a message to [email-masked] with
the word 'unsubscribe' in a single line as the message text body.
archive: <http://ops.ietf.org/lists/namedroppers/>

---

From: Alex Bligh <[email-masked]>
Date: 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.
 
--
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: 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/

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: 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: 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: 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: 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++.