Subject: Removing the SERVFAIL response on hash collisions.

From: Mark Andrews <[email-masked]>
Date: Wed, 16 Aug 2006 12:30:28 +1000

draft-ietf-dnsext-nsec3-06.txt currently has:

6.2.9.  Server Response to a Run-time Collision

   If the hash of a non-existing QNAME collides with an existing NSEC3
   ownername, then the server will be unable to return a response that
   proves that QNAME does not exist.  In this case, the server MUST
   return a response with an RCODE of 2 (server failure).

   Note that with the hash algorithm specified in this document, SHA-1,
   such collisions are astronomically unlikely.

	We can disambiguate collisions by returning the original
	owner name used to generate the hash.

	I propose that NSEC3 wire format be extended to optionally
	include a the original owner name at the end of the existing
	wire format.  This is *only* returned in AXFR/IXFR and for this
	special case.  The RRSIG will be computed over NSEC3 records
	as if this extra name was not included.  You can verify the
	appended ownername as its hash will be the ownername of the
	NSEC3 record.

	To save space we could exclude the zone name with "."
	representing the zone if we do this.

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

--
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: Mark Andrews <[email-masked]>
Date: Wed, 16 Aug 2006 12:46:26 +1000

> 	appended ownername as its hash will be the ownername of the

	s/will be the ownername/will be in the ownername/

> 	NSEC3 record.

	Note we will need to include a length field for the bitmaps
	when we do this.

---

From: Mark Andrews <[email-masked]>
Date: Thu, 17 Aug 2006 09:07:49 +1000

> On Wed, 16 Aug 2006, Mark Andrews wrote:
> > 	wire format.
> I will support this change if you agree to carry around an oxygen tank
> for the rest of your life to avoid potential asphyxiation in case all
> the air molecules in whatever room you happen to be located in
> suddenly move to the other side.
> 
> Seriously, with SHA-1 the possibility of this collision is
> astronomically low.  More risk would be introduced by increasing code
> bloat to deal with this case than the possible damage if the case
> itself occurred.
> 
> Does SERVFAIL really need to be disambiguated?  I don't think so.  But
> if this really bothers anyone, let's burn an extended RCODE to signal
> this scenario.  But don't burden the NSEC3 wire format with it.
> 
> Matt

	The chance of collision is non zero.  It will happen.  We have
	to detect this anyway.  Applications behave badly to SERVFAIL.

	If we choose a new rcode then you need to work out how can it be
	abused.  It can't be just a plain RCODE.  It would need to be
	a RCODE with the entire proof.  Can one construct a response
	with the new RCODE which make a existing name disapear?

	If you have the NSEC3 which corresponds to verisign.com.  Is
	it possible to construct a response using that NSEC3 which makes
	verisign.com go away?  I suspect the answer to that would be
	yes.

	Has anyone done a test run against COM or the root to see if 
	the current NXDOMAIN responses would generate a collision with
	any NSEC3 hash.

	Mark

---

From: Matt Larson <[email-masked]>
Date: Wed, 16 Aug 2006 15:19:37 -0400

Matt

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 16 Aug 2006 16:56:10 -0700

> 	to detect this anyway.  Applications behave badly to SERVFAIL.

I hear this kind of thing a lot, but it's not true for any practical
value of "will happen". Given a population of n elements drawn from
a pool of d elements (with replacement) the probability that you
will have two values that are the same is approximately:
            
               -(n(n-1))/2d            -(n^2)/2d
p(n;d) ~= 1 - e                ~= 1 - e

[http://en.wikipedia.org/wiki/Birthday_paradox]

We can invert this to find out the number of elements we'd need
to have a probability of collision p. It's:

n(p) ~= sqrt(2 * d * ln(1/1-p))

[http://en.wikipedia.org/wiki/Birthday_attack]

So, let's say we're willing to accept a 10^-9 chance that the 
entire system will have a single collision. This would require
you to have about 2^64 separate names in the system, which is
rather unlikely.

> 	verisign.com go away?  I suspect the answer to that would be

Actually, this problem is much harder because you can't take
advantage of the birthday paradox. The cost of generating
an input which digests to a given hash value (a 2nd preimage
attack in this case) is approximately 2^160.

-Ekr

---

From: Mark Andrews <[email-masked]>
Date: Thu, 17 Aug 2006 10:46:53 +1000

> you to have about 2^64 separate names in the system, which is

	Which is all fine and dandy when you are looking at the
	names that exist and generating hashes from them.

> attack in this case) is approximately 2^160.

	I'm looking to find the existing hash.  Not to find a
	name which also has the same has value.
 
	To find a the hash of a name that I know to exist is just
	a matter of generating and testing enough sequential DS
	queries (to prevent referrals).  The hash function will
	randomise the NSEC3 selection.  There is only 200 and
	something million names in COM. A ~100 million queries and
	I have nearly a .5 probability of finding the hash I'm
	looking for.  400 million queries you get to several nines.

	This is the same problem of picking 1 ball out of 200 million
	replacing the ball after each pick if it is not the one you
	want and spinning the barrel.  Repeat.

	Something any bot army should produce a result on in a short
	period of time.

	Mark

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 16 Aug 2006 17:55:22 -0700

> 	names that exist and generating hashes from them.

No, the math I just gave you is the probability of having two
names generating the same hash.

> 	Something any bot army should produce a result on in a short

Hang on a second: what at a high level does this attack accomplish?

-Ekr

---

From: Mark Andrews <[email-masked]>
Date: Thu, 17 Aug 2006 11:23:18 +1000

> Hang on a second: what at a high level does this attack accomplish?

	At the moment there is a case where you detect a collision
	at runtime and are not able to send back a valid NXDOMAIN
	response.  i.e. the hash of the QNAME matches the hash of
	a existing name making it impossible to send back a NSEC3
	where the hash is inside the covered range.

	The current draft says, just send SERVFAIL.  I proposed
	that we make a response that contains just enough extra
	information to disprove the collision.

	Matt suggested a new RCODE.  Now for the new RCODE to work
	we need to be able to verify it by looking at the contents
	of the response.  I was looking to see how easy it would be
	to obtain the NSEC3 hashs we need.  For a non delegation
	you just pick some random types at the known name.  For
	a delegation you need to search if the DS record is there.

	Mark

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 16 Aug 2006 19:48:07 -0700

> 	information to disprove the collision.

Hmm... I think I'm still missing something.

Let's take a step back and walk through things again. We have a server
for zone example.com. It has a bunch of names N_1, N_2, ... N_n
registered so we have N_1.example.com, N_2.example.com,
... N_n.example.com. So far so good, right?  These correspond to a
series of hashes H_1, H_2, ... H_j.  For convenience, we order the
indices in hash order so that H_1 < H_2 < H_3 ... < H_n.

So, when someone asks for a name Q that isn't one of the registered
names, the name server computes H(Q) and then finds H_i and H_i+1
st. H_i < Q < H_i+1. He then returns the NSEC records for H_i and
H_i+1. Right?

Now, the collision problem occurs when H(Q) is equal to one of our
hashes H_j even though N_j != Q. At this point, even though Q doesn't
exist, the nameserver can't generate a valid negative response because
there is no pair of records which encloses H(Q). Do I have this right so
far?

Now, my assertion is that as a practical matter this case can't occur
because the number of names (n) in the domain would have to be well
outside of any plausible bounds (order 2^80) in order to have a 
reasonable chance of a collision. Now, it's true that an attacker
can mount an offline attack and try to generate a name that has
a hash that matches one of the known hashes, but the computational
cost of that is roughly 2^160/n, which is even more unreasonable.

Where have I gone wrong here?

-Ekr

---

From: Mark Andrews <[email-masked]>
Date: Thu, 17 Aug 2006 14:10:35 +1000

> cost of that is roughly 2^160/n, which is even more unreasonable.

	We are not talking about the number of names in a zone.
	We are talking about names in the namespace that are NOT
	in zone.
> Where have I gone wrong here?

	With SHA1 there are 1461501637330902918203684832716283019655932542976
	potential hashes.
	There are more than 111444219848545291112918149658401217019177846881717006276548100629318214534968256903948922840416256 (36^63) possible labels if you restrict
	yourself to a-z0-9.

	There 76253229556466706119897315261914748347145838923466 different
	labels, on average, that hash to a individual value.

	Mark
--
ISC Training!  October 16-20, 2006, in the San Francisco Bay Area,
covering topics from DNS to DHCP.  Email [email-masked].
-- 
Mark Andrews, ISC
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: [email-masked]

---

From: Eric Rescorla <[email-masked]>
Date: Wed, 16 Aug 2006 21:33:57 -0700

> 	We are talking about names in the namespace that are NOT

Well, we're talking about both. We're talking about the chance that
an arbitrary name *not* in the zone will have a hash that is the
same as the hash of one of the names in the zone.

> 	labels, on average, that hash to a individual value.

Sure, but so what? Actually finding a second preimage is computationally
intractable. 

How does this add up to an attack? What does the attacker do and what
advantage does it give them?

-Ekr

---

From: Rob Austein <[email-masked]>
Date: Thu, 17 Aug 2006 02:27:40 -0400

> advantage does it give them?

Sorry for jumping in, but I know both correspondants here pretty well
and can tell that they're talking past each other.

Mark, meet Eric.  Eric, meet Mark.  Eric is a protocol security guy.
Mark is a DNS implementation guy.

The attack that Mark is worried about is not the one that Eric thinks
Mark is worried about.

The draft says "this will never happen, but just in case it does, you
must check for it and send SERVFAIL when it does.  Which it won't."

Mark's reaction to this, based on twenty years before the mast as a
DNS implementor, is "Good grief, not another flipping event that sends
SERVFAIL.  Every time I follow a spec that tells me to send SERVFAIL,
my phone starts ringing off the hook with people whining about how
their DNS service doesn't work anymore and what have I broken now?"

The sad thing is that Mark is absolutely right about this.

Implementing a spec that says "just send SERVFAIL" leaves Mark's phone
open to a denial of service attack.  Since Eric assures us that Mark's
code will never send SERVFAIL in this particular case and that Mark's
phone will thus never ring, the obvious fix is to forward Mark's phone
to Eric.

All clear now?

---

From: Mark Andrews <[email-masked]>
Date: Thu, 17 Aug 2006 16:43:24 +1000

> same as the hash of one of the names in the zone.

	Which will happen, with SHA1, on average once every (2^160)/n
	NXDOMAIN responses.  n = the number of names in the zone.
	Yes I'm well away of how many years between collisions it is
	at current query rates.

	It most probably will never happen in our lifetimes.  But
	it still could.  A couple of extra lines of code will deal
	with the problem.  The code is testable using a truncated
	hash.  In fact it would be useful to specify a really short
	hash for test purposes only, 2^16 values would be fine as it
	would be useless for any zone of significant size.

	No one has stated that my solution will not work.  If it won't
	work please tell me and I'll shutup.

> > 	There are more than 111444219848545291112918149658401217019177846881717
> 006276548100629318214534968256903948922840416256 (36^63) possible labels if y
> ou restrict
> > 	yourself to a-z0-9.
> >

---

From: bert hubert <[email-masked]>
Date: Thu, 17 Aug 2006 09:53:21 +0200

> 	work please tell me and I'll shutup.

If I've followed the discussion above, the codepath to detect and handle
such a collision is unlikely to be taken once in the lifetime of the
universe. Hence it will bitrot with astounding rapidity.

	Bert

-- 
http://www.PowerDNS.com      Open source, database driven DNS Software 
http://netherlabs.nl              Open and Closed source services

---

From: Alex Bligh <[email-masked]>
Date: Thu, 17 Aug 2006 12:41:15 +0100

--On 17 August 2006 16:43 +1000 Mark Andrews <[email-masked]> wrote:

> 	NXDOMAIN responses.

And with SHA-256 still more infrequently (it's probably more likely
that a packet gets corrupted in transit to look like a SERVFAIL when
it didn't start out that way). Code to implement longer hashes is likely
to last better and be better tested than code to handle the extremely
unlikely event of a collision (of whichever variety).

> 	work please tell me and I'll shutup.

About 18 months ago (I think) we had a thread here where we concluded
under NSEC or NSEC3 it was still possible to spoof errors, such as
SERVFAIL. So it does seem a little bit like a bandaid covering a tiny
hole when there's a great gaping maw by the side. If we did this, I
would be concerned that the behaviour of the resolver receiving such
a SERVFAIL was also specified. If the QNAME is optional, I presume
in its absence, the resolver should assume it is associated with the QNAME
if the associated query. What if it's simply wrong? I presume ignore
the entire SERVFAIL as bogus (more interoperability testing to do there,
then).

Alex

---

From: Mark Andrews <[email-masked]>
Date: Thu, 17 Aug 2006 22:10:26 +1000

> universe. Hence it will bitrot with astounding rapidity.

	The vast majority of code once it has been written and
	tested never gets touched again.  Correct code stays correct.

	Below is the code to extract the proofs from BIND 9.  It
	hasn't been touched in two years.  I don't expect to have
	to touch it ever again.  Back in Jan 04 we added code to
	check for all the proof.

	Mark
	
1.135        (marka    03-Nov-05): /*%
1.115        (marka    14-Jan-04):  * Return ISC_R_SUCCESS if we can determine that the name doesn't exist
1.115        (marka    14-Jan-04):  * or we can determine whether there is data or not at the name.
1.115        (marka    14-Jan-04):  * If the name does not exist return the wildcard name.
1.135        (marka    03-Nov-05):  *
1.135        (marka    03-Nov-05):  * Return ISC_R_IGNORE when the NSEC is not the appropriate one.
1.115        (marka    14-Jan-04):  */
1.115        (marka    14-Jan-04): static isc_result_t
1.115        (marka    14-Jan-04): nsecnoexistnodata(dns_validator_t *val, dns_name_t* name, dns_name_t *nsecname,
1.115        (marka    14-Jan-04):                dns_rdataset_t *nsecset, isc_boolean_t *exists,
1.115        (marka    14-Jan-04):                isc_boolean_t *data, dns_name_t *wild)
1.57         (bwelling 26-May-00): {
1.57         (bwelling 26-May-00):      int order;
1.83         (marka    25-Oct-00):      dns_rdata_t rdata = DNS_RDATA_INIT;
1.57         (bwelling 26-May-00):      isc_result_t result;
1.111        (marka    18-Jan-03):      dns_namereln_t relation;
1.114        (jinmei   25-Oct-03):      unsigned int olabels, nlabels, labels;
1.115        (marka    14-Jan-04):      dns_rdata_nsec_t nsec;
1.115        (marka    14-Jan-04):      isc_boolean_t atparent;
1.57         (bwelling 26-May-00): 
1.115        (marka    14-Jan-04):      REQUIRE(exists != NULL);
1.115        (marka    14-Jan-04):      REQUIRE(data != NULL);
1.124        (marka    17-Nov-04):      REQUIRE(nsecset != NULL &&
1.124        (marka    17-Nov-04):              nsecset->type == dns_rdatatype_nsec);
1.104        (marka    29-Apr-02): 
1.113        (marka    30-Sep-03):      result = dns_rdataset_first(nsecset);
1.86         (bwelling 05-Dec-00):      if (result != ISC_R_SUCCESS) {
1.93         (gson     14-Sep-01):              validator_log(val, ISC_LOG_DEBUG(3),
1.113        (marka    30-Sep-03):                      "failure processing NSEC set");
1.115        (marka    14-Jan-04):              return (result);
1.86         (bwelling 05-Dec-00):      }
1.113        (marka    30-Sep-03):      dns_rdataset_current(nsecset, &rdata);
1.57         (bwelling 26-May-00): 
1.113        (marka    30-Sep-03):      validator_log(val, ISC_LOG_DEBUG(3), "looking for relevant nsec");
1.115        (marka    14-Jan-04):      relation = dns_name_fullcompare(name, nsecname, &order, &olabels);
1.115        (marka    14-Jan-04): 
1.115        (marka    14-Jan-04):      if (order < 0) {
1.57         (bwelling 26-May-00):              /*
1.115        (marka    14-Jan-04):               * The name is not within the NSEC range.
1.57         (bwelling 26-May-00):               */
1.115        (marka    14-Jan-04):              validator_log(val, ISC_LOG_DEBUG(3),
1.115        (marka    14-Jan-04):                            "NSEC does not cover name, before NSEC");
1.115        (marka    14-Jan-04):              return (ISC_R_IGNORE);
1.115        (marka    14-Jan-04):      }
1.82         (bwelling 07-Oct-00): 
1.115        (marka    14-Jan-04):      if (order == 0) {
1.57         (bwelling 26-May-00):              /*
1.115        (marka    14-Jan-04):               * The names are the same.
1.57         (bwelling 26-May-00):               */
1.115        (marka    14-Jan-04):              atparent = dns_rdatatype_atparent(val->event->type);
1.115        (marka    14-Jan-04):              if (dns_nsec_typepresent(&rdata, dns_rdatatype_ns) &&
1.115        (marka    14-Jan-04):                  !dns_nsec_typepresent(&rdata, dns_rdatatype_soa))
1.115        (marka    14-Jan-04):              {
1.115        (marka    14-Jan-04):                      if (!atparent) {
1.115        (marka    14-Jan-04):                              /*
1.115        (marka    14-Jan-04):                               * This NSEC record is from somewhere higher in
1.115        (marka    14-Jan-04):                               * the DNS, and at the parent of a delegation.
1.115        (marka    14-Jan-04):                               * It can not be legitimately used here.
1.115        (marka    14-Jan-04):                               */
1.111        (marka    18-Jan-03):                              validator_log(val, ISC_LOG_DEBUG(3),
1.115        (marka    14-Jan-04):                                            "ignoring parent nsec");
1.115        (marka    14-Jan-04):                              return (ISC_R_IGNORE);
1.111        (marka    18-Jan-03):                      }
1.115        (marka    14-Jan-04):              } else if (atparent) {
1.112        (marka    27-Feb-03):                      /*
1.115        (marka    14-Jan-04):                       * This NSEC record is from the child.
1.110        (marka    22-Jul-02):                       * It can not be legitimately used here.
1.110        (marka    22-Jul-02):                       */
1.110        (marka    22-Jul-02):                      validator_log(val, ISC_LOG_DEBUG(3),
1.115        (marka    14-Jan-04):                                    "ignoring child nsec");
1.115        (marka    14-Jan-04):                      return (ISC_R_IGNORE);
1.57         (bwelling 26-May-00):              }
1.115        (marka    14-Jan-04):              *exists = ISC_TRUE;
1.115        (marka    14-Jan-04):              *data = dns_nsec_typepresent(&rdata, val->event->type);
1.115        (marka    14-Jan-04):              validator_log(val, ISC_LOG_DEBUG(3),
1.115        (marka    14-Jan-04):                            "nsec proves name exists (owner) data=%d",
1.115        (marka    14-Jan-04):                            *data);
1.115        (marka    14-Jan-04):              return (ISC_R_SUCCESS);
1.132        (marka    05-Sep-05):      }
1.115        (marka    14-Jan-04): 
1.115        (marka    14-Jan-04):      if (relation == dns_namereln_subdomain &&
1.115        (marka    14-Jan-04):          dns_nsec_typepresent(&rdata, dns_rdatatype_ns) &&
1.115        (marka    14-Jan-04):          !dns_nsec_typepresent(&rdata, dns_rdatatype_soa))
1.115        (marka    14-Jan-04):      {
1.115        (marka    14-Jan-04):              /*
1.115        (marka    14-Jan-04):               * This NSEC record is from somewhere higher in
1.115        (marka    14-Jan-04):               * the DNS, and at the parent of a delegation.
1.115        (marka    14-Jan-04):               * It can not be legitimately used here.
1.115        (marka    14-Jan-04):               */
1.115        (marka    14-Jan-04):              validator_log(val, ISC_LOG_DEBUG(3), "ignoring parent nsec");
1.115        (marka    14-Jan-04):              return (ISC_R_IGNORE);
1.115        (marka    14-Jan-04):      }
1.115        (marka    14-Jan-04): 
1.115        (marka    14-Jan-04):      result = dns_rdata_tostruct(&rdata, &nsec, NULL);
1.115        (marka    14-Jan-04):      if (result != ISC_R_SUCCESS)
1.115        (marka    14-Jan-04):              return (result);
1.115        (marka    14-Jan-04):      relation = dns_name_fullcompare(&nsec.next, name, &order, &nlabels);
1.115        (marka    14-Jan-04):      if (order == 0) {
1.113        (marka    30-Sep-03):              dns_rdata_freestruct(&nsec);
1.93         (gson     14-Sep-01):              validator_log(val, ISC_LOG_DEBUG(3),
1.115        (marka    14-Jan-04):                            "ignoring nsec matches next name");
1.115        (marka    14-Jan-04):              return (ISC_R_IGNORE);
1.115        (marka    14-Jan-04):      }
1.115        (marka    14-Jan-04): 
1.115        (marka    14-Jan-04):      if (order < 0 && !dns_name_issubdomain(nsecname, &nsec.next)) {
1.57         (bwelling 26-May-00):              /*
1.115        (marka    14-Jan-04):               * The name is not within the NSEC range.
1.57         (bwelling 26-May-00):               */
1.115        (marka    14-Jan-04):              dns_rdata_freestruct(&nsec);
1.115        (marka    14-Jan-04):              validator_log(val, ISC_LOG_DEBUG(3),
1.115        (marka    14-Jan-04):                          "ignoring nsec because name is past end of range");
1.115        (marka    14-Jan-04):              return (ISC_R_IGNORE);
1.115        (marka    14-Jan-04):      }
1.115        (marka    14-Jan-04): 
1.115        (marka    14-Jan-04):      if (order > 0 && relation == dns_namereln_subdomain) {
1.115        (marka    14-Jan-04):              validator_log(val, ISC_LOG_DEBUG(3),
1.115        (marka    14-Jan-04):                            "nsec proves name exist (empty)");
1.115        (marka    14-Jan-04):              dns_rdata_freestruct(&nsec);
1.115        (marka    14-Jan-04):              *exists = ISC_TRUE;
1.115        (marka    14-Jan-04):              *data = ISC_FALSE;
1.115        (marka    14-Jan-04):              return (ISC_R_SUCCESS);
1.115        (marka    14-Jan-04):      }
1.115        (marka    14-Jan-04):      if (wild != NULL) {
1.115        (marka    14-Jan-04):              dns_name_t common;
1.115        (marka    14-Jan-04):              dns_name_init(&common, NULL);
1.115        (marka    14-Jan-04):              if (olabels > nlabels) {
1.115        (marka    14-Jan-04):                      labels = dns_name_countlabels(nsecname);
1.115        (marka    14-Jan-04):                      dns_name_getlabelsequence(nsecname, labels - olabels,
1.115        (marka    14-Jan-04):                                                olabels, &common);
1.115        (marka    14-Jan-04):              } else {
1.115        (marka    14-Jan-04):                      labels = dns_name_countlabels(&nsec.next);
1.115        (marka    14-Jan-04):                      dns_name_getlabelsequence(&nsec.next, labels - nlabels,
1.115        (marka    14-Jan-04):                                                nlabels, &common);
1.115        (marka    14-Jan-04):              }
1.115        (marka    14-Jan-04):              result = dns_name_concatenate(dns_wildcardname, &common,
1.115        (marka    14-Jan-04):                                             wild, NULL);
1.115        (marka    14-Jan-04):              if (result != ISC_R_SUCCESS) {
1.115        (marka    14-Jan-04):                      validator_log(val, ISC_LOG_DEBUG(3),
1.143        (marka    26-Feb-06):                                  "failure generating wildcard name");
1.115        (marka    14-Jan-04):                      return (result);
1.115        (marka    14-Jan-04):              }
1.57         (bwelling 26-May-00):      }

---

From: Roy Arends <[email-masked]>
Date: Thu, 17 Aug 2006 14:57:57 +0200

>       representing the zone if we do this.

Note that I'd like to see some kind of consensus on the need to document 
ANY text about 2nd pre-image resistance failover before actually 
documenting the following solution.

iff there is a collision, (enough has been said already about possibility) 
why not return the following:

H(X)=H(Y), X!=Y, X exists, Y does not exist.

rcode=3
QNAME=Y
empty answer section
authority section: 
H(Y) NSEC3 ... ... ...
H(Y) RRSIG NSEC3
X A 10.1.1.1
X RRSIG A ...

Since it is impossible to prove that Y does not exist 'the nsec3 way', we 
prove that X exist, by returning both X and H(X). Since collisions between 
existing names have been avoided during the generation of the NSEC3 
records, we can safely assert that Y does not exist.

This avoids (perceived) SERVFAIL allergy. This avoids fondling with RDATA. 
This is not spoofable, since the deletion of X,RRSIG(X) will leave the 
response broken.

Roy

---

From: Edward Lewis <[email-masked]>
Date: Thu, 17 Aug 2006 09:24:11 -0400

>SERVFAIL.  Every time I follow a spec that tells me to send SERVFAIL,

My reaction to the the first post on the thread is the same ("Good 
grief...").  But I haven't replied because I don't have a better 
suggestion.

So I'll just second that "yet another requirement to return 'service 
failure' is rather distasteful."  In a way it might be appropriate - 
but thinking more it isn't.

A service failure means (from 1035):
#                2               Server failure - The name server was
#                                unable to process this query due to a
#                                problem with the name server.

In this case, the failure is in the protocol and not the server. 
It's not like the server failed to load the (child) zone, or a 
recursive server could not get a response from another server.  It's 
not like a server only got a corrupted (as in failed DNSSEC 
validation) answer.  The problem here is that the protocol has no 
defined answer to give.

It's not like the server can't retrieve the record it needs for the 
answer, it's like there's no answer to give.

Of course, I'm basing this on a fairly narrow interpretation of "a 
problem with the name server."
-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Edward Lewis                                                +1-571-434-5468
NeuStar

Soccer/Futbol. IPv6.  Both have lots of 1's and 0's and have a hard time
catching on in North America.

---

From: David Blacka <[email-masked]>
Date: Thu, 17 Aug 2006 10:51:49 -0400

I feel a bit late, since there are already 20 more messages in response
to this thread, but Mark said some stuff that I would like to clarify.

> 	to detect this anyway.  Applications behave badly to SERVFAIL.

Please define "applications behave badly to SERVFAIL".  In what sense?
(I'm not arguing with the statement per se, but want to know what sort
of behavior you were thinking of.)

> 	with the new RCODE which make a existing name disapear?

Abused?  Why would a new rcode be any more abusable than other existing
rcodes?

> 	verisign.com go away?  I suspect the answer to that would be

The answer is no, you cannot.  I thought that was the problem you were
trying to solve?

-- 
David Blacka                      <[email-masked]>
Sr. Engineer    VeriSign Infrastructure Product Engineering

---

From: Edward Lewis <[email-masked]>
Date: Thu, 17 Aug 2006 11:11:07 -0400

>of behavior you were thinking of.)

I didn't write the original 'plaint - but I've seen apps that don't 
know to give up when they should.  NXDOMAIN - yeah, give up.  But 
SERVFAIL, they may try again.  And again.  And again.

Going out on a limb (meaning I'm speaking on hearsay), I think this 
is why ARIN passed a policy to trim lame delegations.  Resolvers of 
that era didn't stop retransmission when faced with a lame response. 
'Course, most resolvers of that era have been otherwise patched by 
now.

>Abused?  Why would a new rcode be any more abusable than other existing

Well, that's a good point.  If they don't understand "please stop" 
they aren't going to understand "please desist."

---

From: Mark Andrews <[email-masked]>
Date: Fri, 18 Aug 2006 01:15:31 +1000

> of behavior you were thinking of.)

	They tend to repeatedly ask the same question over and over and
	over and over and over and over and over and over and over and
	over in a vain hope that the SERVFAIL will go away.  The usually
	cope well with NXDOMAIN and SUCCESS.

	MTA's hold onto messages for several days before giving up on
	SERVFAIL.  The fail immediately on NXDOMAIN.  Lets hope you 
	don't want a quick response when the typo in the mail domain
	happens to trigger a NSEC3 has collision.
 
> The answer is no, you cannot.  I thought that was the problem you were

	I was playing out rcode solution space senarios.

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 17 Aug 2006 08:33:35 -0700

Mark Andrews <[email-masked]> wrote:
> 	it still could.

So, now we're circling back to the beginning again, where I said
that, no, it wouldn't happen for any practical value of the number
of queries. By which I mean that if every computer on the Internet
(order 2^32) did 1000 (2^10) queries per second for the
next million years (2^20) years, and if your zone has a billion
(2^30) names in it, the chance of even one of those queries 
generating a collision would be less than 2^(-60).

So, yes, in some sense it *could* happen, but it's far exceeded by the
chance of any number of other improbable things (for instance, values
spontaneously changing in program memory) that we don't bother to
do anything about.

> 	work please tell me and I'll shutup.

It's not a matter of won't work. It's a matter of it's extra
complexity that's not needed.

-Ekr

---

From: Mark Andrews <[email-masked]>
Date: Fri, 18 Aug 2006 00:16:10 +1000

> This is not spoofable, since the deletion of X,RRSIG(X) will leave the 

	This does not handle empty nodes.

---

From: bert hubert <[email-masked]>
Date: Thu, 17 Aug 2006 16:04:30 +0200

> 	tested never gets touched again.  Correct code stays correct.

Code itself may not bitrot (although given some things I've observed I'm
not too sure about that). But rest assured the 12 functions this code
interacts with will (subtly) change behaviour over time. The same goes for
the semantics of the host of structs and typedefs you interact with.

But all this aside, you are trying to detect an event that has been
described as extremely improbable to ever occur, perhaps never in the
remaining age of the universe, yet which will increase complexity of the
protocol yet further.

The protocol is already not simple, and everything has a cost. It is bad
business to pay the cost of an insurance that will never pay out.

	Bert

---

From: Roy Arends <[email-masked]>
Date: Thu, 17 Aug 2006 21:51:56 +0200

>    This does not handle empty nodes.

Return a node that is a sub of the empty node.

Roy

---

From: Mark Andrews <[email-masked]>
Date: Fri, 18 Aug 2006 08:52:31 +1000

> complexity that's not needed.

	SERVFAIL is a BAD response.

	SERVFAIL can mean I don't understand EDNS
	SERVFAIL can mean I don't understand CD
	SERVFAIL can mean I detected a error loading the zone
	SERVFAIL can mean I expired

	and thats just the list from auth servers.  Some of those SERVFAILs
	you can recover from.
	
	Returning SERVFAIL is just adding additional complexity to
	a already complex part of the answer analysis path.

	As a implementer I say that it is actually less complex to
	return the variable NSEC than to have to deal with the SERVFAIL.
	
	Yes, I'm written NSEC3 validator.  I'm well aware of how
	much more code I would need to be added to do this.

	SERVFAIL would cause you to requery with plain DNS (see the
	recovery comment above).  Once you got the plain DNS answer
	you would then attempt to prove that the answer was unsecure
	which would fail.  You would then try the next nameserver.
	Once you had tried all the nameservers for the zone that
	you could reach you would then return SERVFAIL.
	
	We already have to special case how we digest multiple records so
	this one is not really any different.

	This get a answer through to the validator that it can understand.

---

From: David Blacka <[email-masked]>
Date: Thu, 17 Aug 2006 19:51:54 -0400

> 	SERVFAIL is a BAD response.

So, what is the response that the server should generate if it has
loaded a zone with a broken NSEC/NSEC3 chain, gets a query for a
nonexistent QNAME, and fails to find the covering NSEC/NSEC3?  (Hint:
BIND 9.3.x returns SERVFAIL...).

So, I see this case as the same case: looks for covering NSEC3, can't
find it.  And a broken NSEC or NSEC3 chain is so mind-bogglingly more
likely than a SHA-1 hash collision.

> 	you could reach you would then return SERVFAIL.

So, what I like about this part of your argument is that your code must
already handle SERVFAIL.  And the behavior you describe sounds OK to me.

In short, using SERVFAIL for this case is (or should be) *zero* extra
code.  Which is about how much code we should devote to this case that
isn't going to happen.

---

From: Eric Rescorla <[email-masked]>
Date: Thu, 17 Aug 2006 15:59:13 -0700

> 	This get a answer through to the validator that it can understand.

But none of this matters because the case in question isn't
going to happen.

-Ekr

---

From: "The Purple Streak, Hilarie Orman" <[email-masked]>
Date: Thu, 17 Aug 2006 23:51:35 -0600

... one evening when she had gone down to check her email she happened
to look up at the ceiling, and there she saw a big wooden mallet stuck
in one of the beams, held by a relay that would release if her DNS
server had to deal with an NSEC3 collision.

It must have been there for ages and ages, for it was all covered with
cobwebs; but somehow or another she had never noticed it before, and
at once she began thinking how dangerous it was to have the mallet
just there.

"For," thought she, "supposing him and me was married, and supposing
we was to have a son, and supposing he were to grow up to be a man,
and supposing he were to come down to draw cider like as I'm doing,
and supposing there were a hash collision and the mallet were to fall
on his head and kill him, how dreadful it would be!"

Ormative reference:
http://www.mainlesson.com/display.php?author=steel&book=english&story=sillies

Hilarie

---

From: Edward Lewis <[email-masked]>
Date: Fri, 18 Aug 2006 09:28:07 -0400

Reading further...

And with that he closed his mail reader put down the laptop he was 
carrying and seating himself on a cask began to cry. And he cried and 
cried and cried - for all the time spent reading mail on a nice warm 
summer day.

But all ends happily:

So they deployed DNSSEC, and if they didn't live happy ever after, 
that has nothing to do with the story of the three sillies.

---

From: Eric Rescorla <[email-masked]>
Date: Mon, 21 Aug 2006 08:54:50 -0700

=?iso-8859-1?Q?=D3lafur?= =?iso-8859-1?Q?_Gu=F0mundsson?= /DNSEXT  wrote:
> Restart, I lost track of the discussion while reading all the messages
> in bulk this morning.
> 
> There are two cases of hash-to-name collision possibilities:
> 	Y    == H(x) (hashed name collides with an existing name)
> and 	H(z) == W    (New name collides with a hashed name)
> 
> The first one is random and has real low probability, the second is
> likely malicious.
> If the protocol handling of "collisions" causes "bad side effects"
> someone is going to do register new names that collide.

OK. I'm going to stop you right here:
This is what's known as a "2nd preimage attack" and in a secure
hash function of bit-length b has complexity 2^b. I.e., it's
completely impractical if your hash function is strong.

If your hash function is weak enough (i.e., someone has mounted
a successful analytic attack) that this is a practical attack
then you have a real serious problem because they can forge
new signatures based on a single valid signature. In this
case you need a new hash function.

The bottom line here is that if your hash function is secure
than collisions cannot happen. If it's not, then you need to 
change hash functions anyway. 

-Ekr

---

From: Ólafur Guðmundsson /DNSEXT co-chair <[email-masked]>
Date: Mon, 21 Aug 2006 11:01:31 -0400

To remove the collision(s) a zone can re-seed the hash parameters,
but in the case of large open registration zones (such as biz., co.uk.
com., de. and org.) someone can do a DOS on the zone.

Zones can protect them self by having a policy that blocks
registration of names that map to current Hash-names.

Alternative is to prefix the Hash-names like is done in IDN names with
an unique prefix and block registrations of that prefix.

What the WG need to determine
	Is current specification sufficient in dealing with
	name/hash-name collision?
	This includes that resolvers/applications are able to get
	the negative answer in a clear manner in ALL cases.

If not
	Should this be handled in-protocol or by-policy ?

If handle-in-protocol
	Propose a solution with suggested text.

	Olafur

---

From: Ólafur Guðmundsson<[email-masked]>
Date: Mon, 21 Aug 2006 12:39:43 -0400

>change hash functions anyway.

Eric,
This is not an attack on the hash function is only uses it to cause
confusion.

For sake of argument:
HASH("amazon.com.") == "abcdef01234567890abcdef"

There is nothing that prevents me from registering
abcdef01234567890abcdef.com as a domain.

Now at the same name we have NSEC3 RR for Amazon and Delegation for
my domain.
The question is what does a authorative server return in the case
someone asks for records at "abcdef01234567890abcdef.com".

A orthogonal issue (which you are discussing) is what to do TWO
valid names hash into the same  hashed-name.
I agree with you this the probability is so low we can "safely"
ignore that case, with a note in the security considerations section.

         Olafur

---

From: Roy Arends <[email-masked]>
Date: Mon, 21 Aug 2006 19:10:05 +0200

> ignore that case, with a note in the security considerations section.

Olafur, 

We closed this issue a while back: 

NSEC3 Issue 12: NSEC3 RR Owner Name Coincidence

http://www.nsec3.org/cgi-bin/trac.cgi/ticket/23

Regards,

Roy