/*

 * validator/val_nsec.c - validator NSEC denial of existence functions.

 *

 * Copyright (c) 2007, NLnet Labs. All rights reserved.

 *

 * This software is open source.

 * 

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 * 

 * Redistributions of source code must retain the above copyright notice,

 * this list of conditions and the following disclaimer.

 * 

 * Redistributions in binary form must reproduce the above copyright notice,

 * this list of conditions and the following disclaimer in the documentation

 * and/or other materials provided with the distribution.

 * 

 * Neither the name of the NLNET LABS nor the names of its contributors may

 * be used to endorse or promote products derived from this software without

 * specific prior written permission.

 * 

 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED

 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR

 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF

 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING

 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS

 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 */

/**

 * \file

 *

 * This file contains helper functions for the validator module.

 * The functions help with NSEC checking, the different NSEC proofs

 * for denial of existence, and proofs for presence of types.

 */

#include "config.h"

#include "validator/val_nsec.h"

#include "validator/val_utils.h"

#include "util/data/msgreply.h"

#include "util/data/dname.h"

#include "util/net_help.h"

#include "util/module.h"

#include "services/cache/rrset.h"

/** get ttl of rrset */

static uint32_t 

rrset_get_ttl(struct ub_packed_rrset_key* k)

{

  struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data;

  return d->ttl;

}

int

nsecbitmap_has_type_rdata(uint8_t* bitmap, size_t len, uint16_t type)

{

  /* Check type present in NSEC typemap with bitmap arg */

  /* bitmasks for determining type-lowerbits presence */

  uint8_t masks[8] = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01};

  uint8_t type_window = type>>8;

  uint8_t type_low = type&0xff;

  uint8_t win, winlen;

  /* read each of the type bitmap windows and see if the searched

   * type is amongst it */

  while(len > 0) {

    if(len < 3) /* bad window, at least window# winlen bitmap */

      return 0;

    win = *bitmap++;

    winlen = *bitmap++;

    len -= 2;

    if(len < winlen || winlen < 1 || winlen > 32) 

      return 0; /* bad window length */

    if(win == type_window) {

      /* search window bitmap for the correct byte */

      /* mybyte is 0 if we need the first byte */

      size_t mybyte = type_low>>3;

      if(winlen <= mybyte)

        return 0; /* window too short */

      return (int)(bitmap[mybyte] & masks[type_low&0x7]);

    } else {

      /* not the window we are looking for */

      bitmap += winlen;

      len -= winlen;

    }

  }

  /* end of bitmap reached, no type found */

  return 0;

}

int

nsec_has_type(struct ub_packed_rrset_key* nsec, uint16_t type)

{

  struct packed_rrset_data* d = (struct packed_rrset_data*)nsec->

    entry.data;

  size_t len;

  if(!d || d->count == 0 || d->rr_len[0] < 2+1)

    return 0;

  len = dname_valid(d->rr_data[0]+2, d->rr_len[0]-2);

  if(!len)

    return 0;

  return nsecbitmap_has_type_rdata(d->rr_data[0]+2+len, 

    d->rr_len[0]-2-len, type);

}

/**

 * Get next owner name from nsec record

 * @param nsec: the nsec RRset.

 *  If there are multiple RRs, then this will only return one of them.

 * @param nm: the next name is returned.

 * @param ln: length of nm is returned.

 * @return false on a bad NSEC RR (too short, malformed dname).

 */

static int 

nsec_get_next(struct ub_packed_rrset_key* nsec, uint8_t** nm, size_t* ln)

{

  struct packed_rrset_data* d = (struct packed_rrset_data*)nsec->

    entry.data;

  if(!d || d->count == 0 || d->rr_len[0] < 2+1) {

    *nm = 0;

    *ln = 0;

    return 0;

  }

  *nm = d->rr_data[0]+2;

  *ln = dname_valid(*nm, d->rr_len[0]-2);

  if(!*ln) {

    *nm = 0;

    *ln = 0;

    return 0;

  }

  return 1;

}

/**

 * For an NSEC that matches the DS queried for, check absence of DS type.

 *

 * @param nsec: NSEC for proof, must be trusted.

 * @param qinfo: what is queried for.

 * @return if secure the nsec proves that no DS is present, or 

 *  insecure if it proves it is not a delegation point.

 *  or bogus if something was wrong.

 */

static enum sec_status 

val_nsec_proves_no_ds(struct ub_packed_rrset_key* nsec, 

  struct query_info* qinfo)

{

  log_assert(qinfo->qtype == LDNS_RR_TYPE_DS);

  log_assert(ntohs(nsec->rk.type) == LDNS_RR_TYPE_NSEC);

  if(nsec_has_type(nsec, LDNS_RR_TYPE_SOA) && qinfo->qname_len != 1) {

    /* SOA present means that this is the NSEC from the child, 

     * not the parent (so it is the wrong one). */

    return sec_status_bogus;

  }

  if(nsec_has_type(nsec, LDNS_RR_TYPE_DS)) {

    /* DS present means that there should have been a positive 

     * response to the DS query, so there is something wrong. */

    return sec_status_bogus;

  }

  if(!nsec_has_type(nsec, LDNS_RR_TYPE_NS)) {

    /* If there is no NS at this point at all, then this 

     * doesn't prove anything one way or the other. */

    return sec_status_insecure;

  }

  /* Otherwise, this proves no DS. */

  return sec_status_secure;

}

/** check security status from cache or verify rrset, returns true if secure */

static int

nsec_verify_rrset(struct module_env* env, struct val_env* ve, 

  struct ub_packed_rrset_key* nsec, struct key_entry_key* kkey, 

  char** reason, struct module_qstate* qstate)

{

  struct packed_rrset_data* d = (struct packed_rrset_data*)

    nsec->entry.data;

  if(!d) return 0;

  if(d->security == sec_status_secure)

    return 1;

  rrset_check_sec_status(env->rrset_cache, nsec, *env->now);

  if(d->security == sec_status_secure)

    return 1;

  d->security = val_verify_rrset_entry(env, ve, nsec, kkey, reason,

    NULL, LDNS_SECTION_AUTHORITY, qstate);

  if(d->security == sec_status_secure) {

    rrset_update_sec_status(env->rrset_cache, nsec, *env->now);

    return 1;

  }

  return 0;

}

enum sec_status 

val_nsec_prove_nodata_dsreply(struct module_env* env, struct val_env* ve, 

  struct query_info* qinfo, struct reply_info* rep, 

  struct key_entry_key* kkey, time_t* proof_ttl, char** reason,

  struct module_qstate* qstate)

{

  struct ub_packed_rrset_key* nsec = reply_find_rrset_section_ns(

    rep, qinfo->qname, qinfo->qname_len, LDNS_RR_TYPE_NSEC, 

    qinfo->qclass);

  enum sec_status sec;

  size_t i;

  uint8_t* wc = NULL, *ce = NULL;

  int valid_nsec = 0;

  struct ub_packed_rrset_key* wc_nsec = NULL;

  /* If we have a NSEC at the same name, it must prove one 

   * of two things

   * --

   * 1) this is a delegation point and there is no DS

   * 2) this is not a delegation point */

  if(nsec) {

    if(!nsec_verify_rrset(env, ve, nsec, kkey, reason, qstate)) {

      verbose(VERB_ALGO, "NSEC RRset for the "

        "referral did not verify.");

      return sec_status_bogus;

    }

    sec = val_nsec_proves_no_ds(nsec, qinfo);

    if(sec == sec_status_bogus) {

      /* something was wrong. */

      *reason = "NSEC does not prove absence of DS";

      return sec;

    } else if(sec == sec_status_insecure) {

      /* this wasn't a delegation point. */

      return sec;

    } else if(sec == sec_status_secure) {

      /* this proved no DS. */

      *proof_ttl = ub_packed_rrset_ttl(nsec);

      return sec;

    }

    /* if unchecked, fall through to next proof */

  }

  /* Otherwise, there is no NSEC at qname. This could be an ENT. 

   * (ENT=empty non terminal). If not, this is broken. */

  /* verify NSEC rrsets in auth section */

  for(i=rep->an_numrrsets; i < rep->an_numrrsets+rep->ns_numrrsets; 

    i++) {

    if(rep->rrsets[i]->rk.type != htons(LDNS_RR_TYPE_NSEC))

      continue;

    if(!nsec_verify_rrset(env, ve, rep->rrsets[i], kkey, reason,

      qstate)) {

      verbose(VERB_ALGO, "NSEC for empty non-terminal "

        "did not verify.");

      return sec_status_bogus;

    }

    if(nsec_proves_nodata(rep->rrsets[i], qinfo, &wc)) {

      verbose(VERB_ALGO, "NSEC for empty non-terminal "

        "proved no DS.");

      *proof_ttl = rrset_get_ttl(rep->rrsets[i]);

      if(wc && dname_is_wild(rep->rrsets[i]->rk.dname)) 

        wc_nsec = rep->rrsets[i];

      valid_nsec = 1;

    }

    if(val_nsec_proves_name_error(rep->rrsets[i], qinfo->qname)) {

      ce = nsec_closest_encloser(qinfo->qname, 

        rep->rrsets[i]);

    }

  }

  if(wc && !ce)

    valid_nsec = 0;

  else if(wc && ce) {

    /* ce and wc must match */

    if(query_dname_compare(wc, ce) != 0) 

      valid_nsec = 0;

    else if(!wc_nsec)

      valid_nsec = 0;

  }

  if(valid_nsec) {

    if(wc) {

      /* check if this is a delegation */

      *reason = "NSEC for wildcard does not prove absence of DS";

      return val_nsec_proves_no_ds(wc_nsec, qinfo);

    }

    /* valid nsec proves empty nonterminal */

    return sec_status_insecure;

  }

  /* NSEC proof did not conclusively point to DS or no DS */

  return sec_status_unchecked;

}

int nsec_proves_nodata(struct ub_packed_rrset_key* nsec, 

  struct query_info* qinfo, uint8_t** wc)

{

  log_assert(wc);

  if(query_dname_compare(nsec->rk.dname, qinfo->qname) != 0) {

    uint8_t* nm;

    size_t ln;

    /* empty-non-terminal checking. 

     * Done before wildcard, because this is an exact match,

     * and would prevent a wildcard from matching. */

    /* If the nsec is proving that qname is an ENT, the nsec owner 

     * will be less than qname, and the next name will be a child 

     * domain of the qname. */

    if(!nsec_get_next(nsec, &nm, &ln))

      return 0; /* bad nsec */

    if(dname_strict_subdomain_c(nm, qinfo->qname) &&

      dname_canonical_compare(nsec->rk.dname, 

        qinfo->qname) < 0) {

      return 1; /* proves ENT */

    }

    /* wildcard checking. */

    /* If this is a wildcard NSEC, make sure that a) it was 

     * possible to have generated qname from the wildcard and 

     * b) the type map does not contain qtype. Note that this 

     * does NOT prove that this wildcard was the applicable 

     * wildcard. */

    if(dname_is_wild(nsec->rk.dname)) {

      /* the purported closest encloser. */

      uint8_t* ce = nsec->rk.dname;

      size_t ce_len = nsec->rk.dname_len;

      dname_remove_label(&ce, &ce_len);

      /* The qname must be a strict subdomain of the 

       * closest encloser, for the wildcard to apply 

       */

      if(dname_strict_subdomain_c(qinfo->qname, ce)) {

        /* here we have a matching NSEC for the qname,

         * perform matching NSEC checks */

        if(nsec_has_type(nsec, LDNS_RR_TYPE_CNAME)) {

           /* should have gotten the wildcard CNAME */

          return 0;

        }

        if(nsec_has_type(nsec, LDNS_RR_TYPE_NS) && 

           !nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) {

           /* wrong parentside (wildcard) NSEC used */

          return 0;

        }

        if(nsec_has_type(nsec, qinfo->qtype)) {

          return 0;

        }

        *wc = ce;

        return 1;

      }

    } else {

      /* See if the next owner name covers a wildcard

       * empty non-terminal. */

      while (dname_canonical_compare(nsec->rk.dname, nm) < 0) {

        /* wildcard does not apply if qname below

         * the name that exists under the '*' */

        if (dname_subdomain_c(qinfo->qname, nm))

          break;

        /* but if it is a wildcard and qname is below

         * it, then the wildcard applies. The wildcard

         * is an empty nonterminal. nodata proven. */

        if (dname_is_wild(nm)) {

          size_t ce_len = ln;

          uint8_t* ce = nm;

          dname_remove_label(&ce, &ce_len);

          if(dname_strict_subdomain_c(qinfo->qname, ce)) {

            *wc = ce;

            return 1;

          }

        }

        dname_remove_label(&nm, &ln);

      }

    }

    /* Otherwise, this NSEC does not prove ENT and is not a 

     * wildcard, so it does not prove NODATA. */

    return 0;

  }

  /* If the qtype exists, then we should have gotten it. */

  if(nsec_has_type(nsec, qinfo->qtype)) {

    return 0;

  }

  /* if the name is a CNAME node, then we should have gotten the CNAME*/

  if(nsec_has_type(nsec, LDNS_RR_TYPE_CNAME)) {

    return 0;

  }

  /* If an NS set exists at this name, and NOT a SOA (so this is a 

   * zone cut, not a zone apex), then we should have gotten a 

   * referral (or we just got the wrong NSEC). 

   * The reverse of this check is used when qtype is DS, since that

   * must use the NSEC from above the zone cut. */

  if(qinfo->qtype != LDNS_RR_TYPE_DS &&

    nsec_has_type(nsec, LDNS_RR_TYPE_NS) && 

    !nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) {

    return 0;

  } else if(qinfo->qtype == LDNS_RR_TYPE_DS &&

    nsec_has_type(nsec, LDNS_RR_TYPE_SOA) &&

    !dname_is_root(qinfo->qname)) {

    return 0;

  }

  return 1;

}

int 

val_nsec_proves_name_error(struct ub_packed_rrset_key* nsec, uint8_t* qname)

{

  uint8_t* owner = nsec->rk.dname;

  uint8_t* next;

  size_t nlen;

  if(!nsec_get_next(nsec, &next, &nlen))

    return 0;

  /* If NSEC owner == qname, then this NSEC proves that qname exists. */

  if(query_dname_compare(qname, owner) == 0) {

    return 0;

  }

  /* If NSEC is a parent of qname, we need to check the type map

   * If the parent name has a DNAME or is a delegation point, then 

   * this NSEC is being misused. */

  if(dname_subdomain_c(qname, owner) && 

    (nsec_has_type(nsec, LDNS_RR_TYPE_DNAME) ||

    (nsec_has_type(nsec, LDNS_RR_TYPE_NS) 

      && !nsec_has_type(nsec, LDNS_RR_TYPE_SOA))

    )) {

    return 0;

  }

  if(query_dname_compare(owner, next) == 0) {

    /* this nsec is the only nsec */

    /* zone.name NSEC zone.name, disproves everything else */

    /* but only for subdomains of that zone */

    if(dname_strict_subdomain_c(qname, next))

      return 1;

  }

  else if(dname_canonical_compare(owner, next) > 0) {

    /* this is the last nsec, ....(bigger) NSEC zonename(smaller) */

    /* the names after the last (owner) name do not exist 

     * there are no names before the zone name in the zone 

     * but the qname must be a subdomain of the zone name(next). */

    if(dname_canonical_compare(owner, qname) < 0 &&

      dname_strict_subdomain_c(qname, next))

      return 1;

  } else {

    /* regular NSEC, (smaller) NSEC (larger) */

    if(dname_canonical_compare(owner, qname) < 0 &&

       dname_canonical_compare(qname, next) < 0) {

      return 1;

    }

  }

  return 0;

}

int val_nsec_proves_insecuredelegation(struct ub_packed_rrset_key* nsec, 

  struct query_info* qinfo)

{

  if(nsec_has_type(nsec, LDNS_RR_TYPE_NS) &&

    !nsec_has_type(nsec, LDNS_RR_TYPE_DS) &&

    !nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) {

    /* see if nsec signals an insecure delegation */

    if(qinfo->qtype == LDNS_RR_TYPE_DS) {

      /* if type is DS and qname is equal to nsec, then it

       * is an exact match nsec, result not insecure */

      if(dname_strict_subdomain_c(qinfo->qname,

        nsec->rk.dname))

        return 1;

    } else {

      if(dname_subdomain_c(qinfo->qname, nsec->rk.dname))

        return 1;

    }

  }

  return 0;

}

uint8_t* 

nsec_closest_encloser(uint8_t* qname, struct ub_packed_rrset_key* nsec)

{

  uint8_t* next;

  size_t nlen;

  uint8_t* common1, *common2;

  if(!nsec_get_next(nsec, &next, &nlen))

    return NULL;

  /* longest common with owner or next name */

  common1 = dname_get_shared_topdomain(nsec->rk.dname, qname);

  common2 = dname_get_shared_topdomain(next, qname);

  if(dname_count_labels(common1) > dname_count_labels(common2))

    return common1;

  return common2;

}

int val_nsec_proves_positive_wildcard(struct ub_packed_rrset_key* nsec, 

  struct query_info* qinf, uint8_t* wc)

{

  uint8_t* ce;

  /*  1) prove that qname doesn't exist and 

   *  2) that the correct wildcard was used

   *  nsec has been verified already. */

  if(!val_nsec_proves_name_error(nsec, qinf->qname))

    return 0;

  /* check wildcard name */

  ce = nsec_closest_encloser(qinf->qname, nsec);

  if(!ce)

    return 0;

  if(query_dname_compare(wc, ce) != 0) {

    return 0;

  }

  return 1;

}

int 

val_nsec_proves_no_wc(struct ub_packed_rrset_key* nsec, uint8_t* qname, 

  size_t qnamelen)

{

  /* Determine if a NSEC record proves the non-existence of a 

   * wildcard that could have produced qname. */

  int labs;

  uint8_t* ce = nsec_closest_encloser(qname, nsec);

  uint8_t* strip;

  size_t striplen;

  uint8_t buf[LDNS_MAX_DOMAINLEN+3];

  if(!ce)

    return 0;

  /* we can subtract the closest encloser count - since that is the

   * largest shared topdomain with owner and next NSEC name,

   * because the NSEC is no proof for names shorter than the owner 

   * and next names. */

  labs = dname_count_labels(qname) - dname_count_labels(ce);

  if(labs > 0) {

    /* i is number of labels to strip off qname, prepend * wild */

    strip = qname;

    striplen = qnamelen;

    dname_remove_labels(&strip, &striplen, labs);

    if(striplen > LDNS_MAX_DOMAINLEN-2)

      return 0; /* too long to prepend wildcard */

    buf[0] = 1;

    buf[1] = (uint8_t)'*';

    memmove(buf+2, strip, striplen);

    if(val_nsec_proves_name_error(nsec, buf)) {

      return 1;

    }

  }

  return 0;

}