Subject: Re: Removing the SERVFAIL response on hash collisions.

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

> On Thu, Aug 17, 2006 at 04:43:24PM +1000, Mark Andrews wrote:
> > 	No one has stated that my solution will not work.  If it won't
> > 	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.

	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):      }

> 	Bert
> 
> -- 
> http://www.PowerDNS.com      Open source, database driven DNS Software 
> http://netherlabs.nl              Open and Closed source services
--
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]

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