Subject: Re: NSEC3 Issue 10: Potential DoS on Servers,

From: "David A. Wheeler" <[email-masked]>
Date: Wed, 21 Jun 2006 19:32:19 -0400 (EDT)

Earlier an "NSEC3 issue 10" was noted, saying:
>Significantly more work is required for a name server to
>respond to queries which require negative proofs using NSEC3
>than is required for a client to compose and send them.

I don't understand this as an issue, and I'm concerned that I may be
misunderstanding NSEC3.  It seems to me that the whole point
of the NSEC3 design is that all the hashes and signatures can
be precomputed, offline.  You don't want the signing key to BE on-line,
and you cannot assert that hash ranges don't exist until you've
computed ALL the valid hash values anyway. And the hash already includes
the salt, iterations, etc.  So I'd expect the entire chain of hash
calculations and signing to be done off-line, where DoS is irrelevant.

Thus, when a client sends a request, the server should be able to
trivially determine the non-match, find the relevant NSEC3 key
(a trivial binary search would be fine), and send the appropriate canned response.
The computation in view is very trivial; I wouldn't expect any complex computations
to be done for an NSEC3 response by a sensible name server (at run time).

Do I misunderstand things?  If so, please enlighten me!

--- David A. Wheeler 

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

---

From: Ben Laurie <[email-masked]>
Date: Thu, 22 Jun 2006 00:52:49 +0100

> Do I misunderstand things?  If so, please enlighten me!

The problem is that the server has to calculate iterated hashes to find
the right NSEC3 records.

-- 
http://www.apache-ssl.org/ben.html           http://www.links.org/

"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: "David A. Wheeler" <[email-masked]>
Date: Wed, 21 Jun 2006 20:55:00 -0400

Ben Laurie wrote:
> The problem is that the server has to calculate iterated hashes to find the right NSEC3 records.
>   
Ah!  Of course!   Perhaps that note, as well as noting that a server
could use NSEC if this was the primary concern, could be put in the next 
version.

I don't see any reasonable way to resolve this 100%.  Even if you had 
requestors
sending the iterated hash with the request (a MAJOR protocol change), you'd
still have to redo the recalculation at the server end (without the trusted
check, NSEC3 dissolves into NSEC).  An attacker can just send
random names and ruin any cache.

There is a PARTIAL solution, though, that I suspect would be worth
including as a suggestion in the spec.  Something like this:
"It is RECOMMENDED that DNS servers designed
to withstand determined denial-of-service attacks selectively drop
processing NSEC3 responses if necessary to be able to reasonably
respond to queries where there is a valid name."  Don't make this a "SHALL".
In servers that do this, resolvers who DO request a valid name can
get responses, while those who request an invalid name will get a 
"not-found"
response unless the server is overloaded... but then, only the invalid names
are dropped.   There are lots of ways to do this, including separate queues,
dropping if you've seen more than X not-found packets in a period, whatever.

You might also recommend caching at the master server level some 
not-found values.
That won't help against intentional attack, but there's always a few
screwed-up or old values; servers that cache a few of them will have better
performance, and that might help encourage deployment.  (This isn't 
necessary
at a master if the master isn't visible, and only negative-caching 
slaves are visible
and used for queries, but I don't think that is ALWAYS the case.) E.G.,
"It is RECOMMENDED that master servers cache a few recent queries that
resulted in not-found results, so that they need not recalculate the hash."

Finally, no matter what, any hashing approach can be attacked through a
dictionary.  The salt and iterations are very helpful, but I think the 
following
should be added: "Any hashing system can be attacked using a dictionary
attack.  The salt and iteration values make such attacks much more 
difficult,
but those who are especially concerned about revealing names can make such
attacks even more difficult by using longer, more difficult-to-guess 
names that
are not obviously related to each other."

--- David A. Wheeler

---

From: "David A. Wheeler" <[email-masked]>
Date: Thu, 22 Jun 2006 10:37:53 -0400 (EDT)

Thanks for the clarification.  I view DNSSEC as critically important to Internet security,
but I've been concerned about the zone enumeration issue.
Thus, I view NSEC3 as critically important as well, and I'm glad it's getting done.
I'm just reviewing it in the hopes that I can help in some way.

There are two possible alternatives to NSEC3 (and NSEC) that I don't see
noted, for those where zone confidentiality is especially critical;
are there non-obvious horrors to these alternatives?:
1. What about permitting a name server to simply drop requests for names
     it doesn't have when it has a zone's data, e.g, no reply at all?
    Clearly that is NOT how things currently work, and that screws
    up caching for those without the complete zone, but it WOULD be a possibility.
2. What about having a separate signing key used ONLY for signing
    denial of existence?  The risk is that when then server is subverted, you
    can forge denial-of-existence as a DoS attack, but if it's limited to that use,
    the attacker can't forge anything else... so for some that might be acceptable.
    That way, you can sign "that name doesn't exist" without giving away
     any other information.

NSEC3 seems to me to strike a good balance between confidentiality and
availability.  I.E., it provides some confidentiality of zone names (now you have
to mount a dictionary/guessing attack, since you have only the hashes),
while not requiring online signing keys (risking signed DoS's if broken into)
and not just dropping requests for non-names.  Option #1 screws up caching,
and option #2 risks DoS.  But I can imagine that for a small subset, perhaps
those problems might be okay.

Would it be reasonable to permit ("MAY") option #1, perhaps even just "slipped in"
as part of NSEC3, and then consider option #2 as a potential future work item?

Forgive me if this has been discussed before.

--- David A. Wheeler

---

From: Paul Vixie <[email-masked]>
Date: Thu, 22 Jun 2006 16:56:06 +0000

> I'm just reviewing it in the hopes that I can help in some way.

welcome.

> noted, for those where zone confidentiality is especially critical; are
> there non-obvious horrors to these alternatives?:

yes.

> 1. What about permitting a name server to simply drop requests for names it
> doesn't have when it has a zone's data, e.g, no reply at all?  Clearly that
> is NOT how things currently work, and that screws up caching for those
> without the complete zone, but it WOULD be a possibility.

this blurs the necessary and important distinction between packet loss due
to network overcommit/outage, packet loss due to intentional targetted attack,
and assertion-of-nonexistence.  without a bright line separating those three
conditions from a requestor's point of view, the inevitable results will be
(a) excessive useless retransmissions and (b) effective lack of authenticated
denial of existence.

> 2. What about having a separate signing key used ONLY for signing denial of
> existence?  The risk is that when then server is subverted, you can forge
> denial-of-existence as a DoS attack, but if it's limited to that use, the
> attacker can't forge anything else... so for some that might be acceptable.
> That way, you can sign "that name doesn't exist" without giving away any
> other information.

this creates a new vector for authority server CPU attacks, and leads back to
the same blurred distinction as above.  it's expected that signature
generation will almost always be more expensive than signature verification
(in fact, that's a desireable feature and guided the choice of crypto alg)
and if it takes more authority server CPU to generate an authentic NXDOMAIN
than an authentic NOERROR, an attacker can target an attack so as to prevent
authentic NXDOMAIN from being available during their real attack elsewhere,
which effectively removes authenticated NXDOMAIN as a DNSSEC-bis feature.

> Forgive me if this has been discussed before.

you are forgiven; the archives are in complete disarray on this topic.

---

From: "David A. Wheeler" <[email-masked]>
Date: Fri, 23 Jun 2006 11:24:28 -0400 (EDT)

I know you're trying to meet a Monday deadline for NSEC3.
Here are a few proposed _specific_ changes to the spec, which I've
tried to make as easy as possible for you; they're basically line-in/line-outs;
I hope they help:

* Nit - section numbering is wrong - in May draft, 11 precedes 10..
need to renumber in order..!

* Under "Security Considerations":
- Change "DNSSEC already relies on SHA-1 to not collide" to
"DNSSEC already relies on the presumption that the
cryptographic hash function (such as SHA-1) will not collide."
(other hash functions besides SHA-1 are possible, in the long term likely,
and the sentence structure was a little odd anyway.)

- After the 1st two paragraphs (discussing iterations and salt), add:
"Domains can also make discovery of many names much more difficult,
if ithey wish, by choosing longer names that are not in any dictionary
and do not follow any discernable pattern.
They can also insert 'dummy' names that should never be queried,
possibly including some easier-to-find names, and then alert an administrator
when unexpected queries are performed on those names."

* Under "Rationale", insert before last paragraph:
"Some alternatives to this specification have undesirable side-effects.
An unsigned reply denial of existence can be trivially spoofed.
Ignoring requests for non-existant names blurs the important distinction
between packet loss due to network overcommit/outage,
packet loss due to intentional targetted attack,
and assertion-of-nonexistence, resulting in
excessive useless retransmissions and effective lack of authenticated
denial of existence.
Signing a denial of existance for each specific name requires that the name server
have a private key for denial of existence; its subversion
could then result in large-scale denial of service. Some may find this
last result an acceptable tradeoff, but many others will not.
This specification provides protection against trivial zone enumeration while
(1) providing signed denial of existence and (2) not requiring private keys in the
name servers."
(elsewhere is fine too, of course.  But I think this is important background
information that needs to go SOMEWHERE in the document.  If you don't briefly
document WHY this specification is designed the way it is, the
reader will wonder why you did NOT do these "obvious" things.
Paul Vixie noted that "the archives are in complete disarray on this topic." :-) ).

* Add "It is RECOMMENDED that master servers cache a few recent queries that
resulted in not-found results, to save processing time"
(I reworded the last part).

Here is the proposed changed I noted earlier:
* section 10, in the phrase "cannot by cryptographically proven",
replace "by" with "be".

To address NSEC3 issue 10, in the security section note the issue and specifically
tell the implementors it's okay to drop requests for nonexistent names if they
have to, to serve existing names (it's a DoS, but it at least limits the damage
and is better for most people, so it should be explicitly permitted).
Here's some sample text, more or less lifted from the earlier emails
(I just don't want this lost, you probably already have this in the draft):
"Significantly more work is required for a name server to respond to
queries which require negative proofs using NSEC3 than is required for
a client to compose and send them.  For each such query, the name
server must repeat the hash function for the number of iterations
specified in the NSEC3 RRs.  Consequently, name servers with NSEC3
zones are susceptible to asymmetric DoS attacks.
Implementations MAY provide a reduced
quality of service for queries which require negative proofs, so that
resolution and validation of existing names will not be compromised."
(In earlier text I said RECOMMENDED... I think that might be a good idea
to recommend, but that's very debatable so I leave it up to you.  But telling
implementors they at least MAY drop them if necessary is, I think, important).

I look forward to seeing the new NSEC3 spec.  I agree with adding the
hash length field, though that will obviously require a (small) change in
implementations... best to find that out NOW than after it's an RFC...! :-).

--- David A. Wheeler

---

From: Roy Arends <[email-masked]>
Date: Sun, 25 Jun 2006 04:44:15 +0200

"David A. Wheeler" <[email-masked]> wrote on 06/23/2006 05:24:28 

> need to renumber in order..!

We've done a total rewrite since then, so this was already fixed.

> and the sentence structure was a little odd anyway.)

This is changed to:

                                 Note that DNSSEC already relies on the
   presumption that a cryptographic hash function is second pre-image
   resistant, since these hash functions are used for generating and
   validating signatures and DS records.

> when unexpected queries are performed on those names."

This document describes the workings of the DNSSEC/NSEC3 protocol, and was 
not ment to be an exhaustive list of all possible defenses against 
enumeration.

> Paul Vixie noted that "the archives are in complete disarray on this

We can now refer to:

   http://ops.ietf.org/lists/namedroppers/namedroppers.2006/msg00794.html

:-)

Anyway, the validity or limitations of other proposals (i.e. not specified 
in any draft) should not be listed in this document. It is distracting, 
and basically not relevant for NSEC3. It is fine to have this in a 
seperate 'road map' draft or something similar. We have limitted ourselfs 
to solely list the limitations of NSEC3.

> * section 10, in the phrase "cannot by cryptographically proven",

Fixed.
 
> have to, to serve existing names (it's a DoS, but it at least limitsthe 
damage
> implementors they at least MAY drop them if necessary is, I think, 
important).

Will chew on this. 
 
> implementations... best to find that out NOW than after it's an RFC...! 
:-).

Thanks for reading the draft !

Regards,

Roy