Subject: Re: NSEC3 chain walking

From: Ben Laurie <[email-masked]>
Date: Tue, 01 Nov 2005 12:01:39 +0000

Marcus Better wrote:
> Hello,
> 
> I have a comment concerning the problem of chain walking mentioned in
> section 11 of draft-ietf-dnsext-nsec3-03:
> 
>    "Walking the NSEC3 RRs will reveal the total number of records in the
>    zone, and also what types they are.  This could be mitigated by
>    adding dummy entries, but certainly an upper limit can always be
>    found."
> 
> It seems that this little nuisance can be eliminated quite easily.
> 
> (Disclaimer: I am not a DNS expert, so if this is really dumb or has
> already been discussed, I apologize for wasting your time.)
> 
> The following changes are made to the draft:
> 
> 1. The Next Hash Ownername field is modified so that it contains a
> _double_ hash of the next hashed ownername, i.e. H2(H1(name)) where H1
> and H2 are hash algorithms. (One could possibly take H1=H2.)
> 
> 2. The hash order is now determined according to the double hash.
> 
> Note that the ownername of the NSEC3 RR is still the single hash of the
> owner name. So the record would look in principle like
>   H1(foo.example.)	NSEC3	H2(H1(bar.example.))
> 
> This record would prove the non-existence of original ownernames
> name.example such that
>   H2(H1(foo.example.)) < H2(H1(name.example.)) < H2(H1(bar.example.))
> 
> Since the RR only contains the double hash of the next name, which is
> not used as an ownername in the zone, this information cannot be used to
> make further queries. So it becomes impossible to walk the NSEC3 chain.
> 
> An obvious drawback is that the verifier must do extra work to compute
> the additional hashes.

I don't think this works fantastically well. Whether the hash is single
or double an attacker has to guess names that produce hashes in the
intervals it has not yet explored. The difficulty of doing this is
proportional to the zone size (i.e. not very hard even for very large
zones) regardless of whether the hash is single or double.

Assuming, that is, that we ban direct lookup of NSEC3 records.

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

--
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: Simon Josefsson <[email-masked]>
Date: Tue, 01 Nov 2005 13:26:07 +0100

> Assuming, that is, that we ban direct lookup of NSEC3 records.

Baning direct lookup of NSEC3 records doesn't work well.  You can make
queries for random names until you got all NSEC3 records.

Further, because hash output has a rectangular distribution, you know
how large the zone is only after a few queries, so you know how many
queries you will have to send, after seeing the response to a few
queries.

Regards,
Simon

---

From: Alex Bligh <[email-masked]>
Date: Tue, 01 Nov 2005 12:41:39 +0000

> Assuming, that is, that we ban direct lookup of NSEC3 records.

Does that gain us much, other than a debugging nightmare and more
special-case coding? All I can see it does is prevent one from making an
exact enumeration of the NSEC3 records (as opposed to the other RRs) which
is then equal in size to the zone, though one can (by virtue of the
principle that good hash functions distribute values evenly amongst their
range) make a very good guess with a minimum number of non-NSEC queries
(make 1,000 queries and look at distribution of hash values). Given you
only get an upper bound on the "true" content of the zone (as it's quite
feasible to stuff it with NULL records if you want to make your TLD look
bigger :-) ) through the NSEC query method, what in practice is the
difference between getting an upper bound, and a very good estimate of an
upper bound (I think you'd need to make something like K.log2 the number of
size queries to get within a few percent with small K - given this,
it's probably worth publishing an NSEC3 intelligent zone size estimator
to prevent people guessing it by walking!)

Alex

---

From: Roy Arends <[email-masked]>
Date: Tue, 1 Nov 2005 14:01:25 +0100 (CET)

> queries for random names until you got all NSEC3 records.

We're not banning nsec3 to avoid enumeration.

From the current draft:

7.  Responding to NSEC3 Queries

    Since NSEC3 records do not correspond to names that exist within the
    zone, there is the potential for confusion when responding to queries
    that have the QTYPE set to NSEC3 (or ANY).  In order to avoid
    creating an infinite recursion, there is only one consistent way to
    respond to NSEC3 queries, and that is to act as if the NSEC3 record
    did not exist.

    So, if presented with a query where QTYPE is NSEC3 and QNAME is a
    name that exists in the zone with an RRTYPE other than NSEC3, then
    the responder should deny the existence of the NSEC3 RRSet and prove
    it with an NSEC3 record corresponding to the hash of the QNAME (which
    will, of course, exist), as usual.

    If the QTYPE is NSEC3 and QNAME is a name that only exists by virtue
    of an NSEC3 record at that name, then the response should be an
    NXDOMAIN with appropriate NSEC3 records as proof.

Regards,

Roy

---

From: Ben Laurie <[email-masked]>
Date: Tue, 01 Nov 2005 13:03:49 +0000

Alex Bligh wrote:
> special-case coding?

No :-)

> All I can see it does is prevent one from making an

I can't get excited about zone size estimation.

---

From: Ben Laurie <[email-masked]>
Date: Tue, 01 Nov 2005 13:02:16 +0000

> queries for random names until you got all NSEC3 records.

It works as well as I stated above :-)

> queries you will have to send, after seeing the response to a few

True.

---

From: Simon Josefsson <[email-masked]>
Date: Tue, 01 Nov 2005 14:15:35 +0100

> We're not banning nsec3 to avoid enumeration.

I see, I had missed that section.

>    NXDOMAIN with appropriate NSEC3 records as proof.

I don't see why this is the only way to handle the problem.  This text
create a special case, that will require special care in
implementation.

What's wrong with returning the NSEC3 a client asks for?  Assuming the
NSEC3 the client asked for exist, that is.

If it does not exist, the client get the usual NSEC3 records that deny
existence.

The only problem I can see is that an attack can replace the reply
with the real NSEC3 with another NSEC3 record that deny the first
NSEC3's existence.  But you could simply document that this is not
protected against.  The attacker doesn't gain anything by this, as far
as I can tell.  I don't see how this would cause infinite recursion.

With this approach, there is no additional code complexity, that I can
see.

Thanks,
Simon

---

From: Ben Laurie <[email-masked]>
Date: Tue, 01 Nov 2005 13:18:49 +0000

>> Does that gain us much, other than a debugging nightmare and more

BTW, when I say "no" I mean in respect of zone walking or size
estimation. As Roy says we ban them for other reasons.

---

From: Alex Bligh <[email-masked]>
Date: Tue, 01 Nov 2005 13:43:39 +0000

> estimation. As Roy says we ban them for other reasons.

I see.

Alex

---

From: Paul Vixie <[email-masked]>
Date: Tue, 01 Nov 2005 14:49:16 +0000

# I can't get excited about zone size estimation.

me neither.

but i can't get excited about zone content enumeration, either, and yet here
we are trying to solve it, and more or less proposing an N+1'th flag day for
DNSSEC before deployment has begun on #N, all because this risk does matter
to some folks.

can we find out if this is a serious problem or showstopper for somebody 
BEFORE we make decisions about addressing it?  (for a pleasant change of pace?)

---

From: Ben Laurie <[email-masked]>
Date: Tue, 01 Nov 2005 15:32:55 +0000

> BEFORE we make decisions about addressing it?  (for a pleasant change of pace?)

We decided in
http://www.ietf.org/internet-drafts/draft-ietf-dnsext-signed-nonexistence-requirements-02.txt
that it was "nice to have" and not an actual requirement.

---

From: Peter Koch <[email-masked]>
Date: Tue, 01 Nov 2005 16:45:31 +0100

> that it was "nice to have" and not an actual requirement.

not to question your assessment in this case, but the message should
probably be that "we" (be that the editors or the WG) should be careful
about other people's requirements, especially if they are crucial for a
deployment success.

It might be quite easy to get feedback from TLD registries, but there are
other DNS operators who may not have made their mind and, if they do, might
disagree with the above categorization (as "nice to have").

When it comes to "zone size" and "zone enumeration", it's also important
to view the first order differential, i.e. dies NSEC++ make it easier (than
pre-DNSSEC DNS) to find the [number of] changes applied to zone?
(This is not to introduce new hurdles, just completeness of the requirements
list).

-Peter

---

From: Thierry Moreau <[email-masked]>
Date: Tue, 01 Nov 2005 11:24:45 -0500

Paul Vixie wrote:
> [...]

Here is a totally un-informed guess (as the adage says, "those wo know 
don't speak, those who speak don't know").

The concealed organization behind org-AB7C7F580FF653D4648C.example.com 
might be concerned, yet would be reluctant to reply to your post.

There are perhaps other legitimate arguments for domain name privacy 
protection. That's the nature of the privacy concern that it covers a 
wide rance of motives, ...

Enough of minding someone else's business ... good luck all for 
resolving this issue!

-- 

- Thierry Moreau

CONNOTECH Experts-conseils inc.
9130 Place de Montgolfier
Montreal, Qc
Canada   H2M 2A1

Tel.: (514)385-5691
Fax:  (514)385-5900

web site: http://www.connotech.com
e-mail: [email-masked]

---

From: Ben Laurie <[email-masked]>
Date: Tue, 01 Nov 2005 16:35:44 +0000

> about other people's requirements, especially if they are crucial for a

This was on the basis that no-one said it was their requirement.

> disagree with the above categorization (as "nice to have").

True. However, given that we have established the impossibility of
satisfying all plausible requirements we are obliged to choose amongst
them, are we not?

I'd also note that it is not generally required of WGs that they should
attempt to achieve consensus with non-participants!

> (This is not to introduce new hurdles, just completeness of the requirements

Surely the appropriate differential is against NSEC in this case, since
NSEC3 is not designed to solve this particular problem, so the
requirement is surely to not make it worse than NSEC, if possible, and
if anyone cares at all.

Cheers,

Ben.

---

From: Alex Bligh <[email-masked]>
Date: Tue, 01 Nov 2005 18:09:50 +0000

--On 01 November 2005 14:49 +0000 Paul Vixie <[email-masked]> wrote:

> BEFORE we make decisions about addressing it?  (for a pleasant change of
> pace?

Didn't we do this with the requirements doc? And I thought noone in
particular much cared.

Alex

---

From: Alex Bligh <[email-masked]>
Date: Tue, 01 Nov 2005 18:20:30 +0000

--On 01 November 2005 16:45 +0100 Peter Koch <[email-masked]> wrote:

> to view the first order differential, i.e. dies NSEC++ make it easier
> (than pre-DNSSEC DNS) to find the [number of] changes applied to zone?

I'm pretty sure that a bit of relatively trivial maths based on NSEC
results from a relatively small number of random queries
(O(log(zonesize))will give you a relatively accurate zone size estimate,
and from there to a first differential is merely a case of repeating the
process several times.

That said, I think /any/ NSEC variant with a finite number of possible
denials (or at least a finite number of denials that is in some manner
linked to the number of zone entries) will suffer the same 'problem'
to a greater or lesser extent. Including double hashes, etc.

The only way of completely solving this that I'm aware of would be the
white-lies method plus epsilons which in essence means online signing.

An advantage to supporting multiple hash types is that it would be
possible to introduce a certain amount of bogosity into the hash
space (deliberately giving non-rectangularly distributed hash functions
which are still unique, e.g. by truncating the hash then duplicating
a random number of bits). This would make evaluation of zone size
mildly less trivial, though not (I fear) much less trivial if you
are looking for broad estimates over time. I think it would be waste
of time & effort to do this (interesting mathematically as it might be)

With my ccTLD hat on, I can't see many TLD operators caring too much given
most of them publish this information anyhow. The ones that don't tend to
have very small zones where artificially increasing the number of zone
entries by inserting random NULL records is going to be a trivial thing to
do in resource terms. Those that want to pretend claim zones are smaller
can always claim they HAVE stuffed the zone with NULL records when they
haven't. Given the zones can't be walked, this would seem not to be
disprovable :-)

Alex

---

From: Paul Vixie <[email-masked]>
Date: Tue, 01 Nov 2005 19:25:54 +0000

# not to question your assessment in this case, but the message should
# probably be that "we" (be that the editors or the WG) should be careful
# about other people's requirements, especially if they are crucial for a
# deployment success.

indeed, everyone who came forward when DNSSEC and DNSSEC-bis were planned
said that enumeration was an evil they could live with.  then things changed.
apparently, the people who would later on care very much, were not asked.
(that's the loop i'm hoping we find a way to break out of.)

---

From: Paul Vixie <[email-masked]>
Date: Tue, 01 Nov 2005 19:37:29 +0000

# Didn't we do this with the requirements doc? And I thought noone in
# particular much cared.

had we done a requirements doc ten years ago that nominet and others would
not have read because they might not have noticed that it would intersect
their national privacy laws or business requirements, we might still have
run into the NSEC3 juggernaut and be just as far off the rails now as we
actually are now.

perhaps something more should be done then write a draft and hope that the
right people read it and understand its implications on their businesses?

something like, oh, let's say, a market requirements survey?

---

From: [email-masked]
Date: Tue, 1 Nov 2005 20:04:28 +0000

> their national privacy laws or business requirements, we might still have

	a decade ago, the EU privacy laws were not anywhere near 
	the state they are in now... 

> something like, oh, let's say, a market requirements survey?

	might as well also include potential shifts in the political
	climate as well...  It is -possible- that a new McCarthy could
	arise and change the US landscape, or that the UN opts for the
	reestablishment of aparthide...  (it is scary to me that the
	EU political process moves faster than the IETF...:)  
	Seriously, if the IETF starts in on marketing requirements surveys,
	then i'm ready to espouse friend Bushs'  rebranding as the IVTF.

--bill