Subject: Re: Avoiding collisions - desirability & possibility thereof

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

>>>>> "Simon" == Simon Josefsson <[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.

    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. 

--
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: 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: Paul Vixie <[email-masked]>
Date: Sun, 19 Sep 2004 15:25:07 +0000

> > 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?"
> 
> 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

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:

>>>  Question: is zone enumeration a more general "problem?"
>>
>> 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: 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