contrib/unbound/validator/val_nsec.c

   1 /*
   2  * validator/val_nsec.c - validator NSEC denial of existence functions.
   3  *
   4  * Copyright (c) 2007, NLnet Labs. All rights reserved.
   5  *
   6  * This software is open source.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * Redistributions of source code must retain the above copyright notice,
  13  * this list of conditions and the following disclaimer.
  14  *
  15  * Redistributions in binary form must reproduce the above copyright notice,
  16  * this list of conditions and the following disclaimer in the documentation
  17  * and/or other materials provided with the distribution.
  18  *
  19  * Neither the name of the NLNET LABS nor the names of its contributors may
  20  * be used to endorse or promote products derived from this software without
  21  * specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  27  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  29  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  30  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  31  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  32  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  33  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  34  */
  35
  36 /**
  37  * \file
  38  *
  39  * This file contains helper functions for the validator module.
  40  * The functions help with NSEC checking, the different NSEC proofs
  41  * for denial of existence, and proofs for presence of types.
  42  */
  43 #include "config.h"
  44 #include "validator/val_nsec.h"
  45 #include "validator/val_utils.h"
  46 #include "util/data/msgreply.h"
  47 #include "util/data/dname.h"
  48 #include "util/net_help.h"
  49 #include "util/module.h"
  50 #include "services/cache/rrset.h"
  51
  52 /** get ttl of rrset */
  53 static uint32_t
  54 rrset_get_ttl(struct ub_packed_rrset_key* k)
  55 {
  56         struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data;
  57         return d->ttl;
  58 }
  59
  60 int
  61 nsecbitmap_has_type_rdata(uint8_t* bitmap, size_t len, uint16_t type)
  62 {
  63         /* Check type present in NSEC typemap with bitmap arg */
  64         /* bitmasks for determining type-lowerbits presence */
  65         uint8_t masks[8] = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01};
  66         uint8_t type_window = type>>8;
  67         uint8_t type_low = type&0xff;
  68         uint8_t win, winlen;
  69         /* read each of the type bitmap windows and see if the searched
  70          * type is amongst it */
  71         while(len > 0) {
  72                 if(len < 3) /* bad window, at least window# winlen bitmap */
  73                         return 0;
  74                 win = *bitmap++;
  75                 winlen = *bitmap++;
  76                 len -= 2;
  77                 if(len < winlen || winlen < 1 || winlen > 32)
  78                         return 0;       /* bad window length */
  79                 if(win == type_window) {
  80                         /* search window bitmap for the correct byte */
  81                         /* mybyte is 0 if we need the first byte */
  82                         size_t mybyte = type_low>>3;
  83                         if(winlen <= mybyte)
  84                                 return 0; /* window too short */
  85                         return (int)(bitmap[mybyte] & masks[type_low&0x7]);
  86                 } else {
  87                         /* not the window we are looking for */
  88                         bitmap += winlen;
  89                         len -= winlen;
  90                 }
  91         }
  92         /* end of bitmap reached, no type found */
  93         return 0;
  94 }
  95
  96 int
  97 nsec_has_type(struct ub_packed_rrset_key* nsec, uint16_t type)
  98 {
  99         struct packed_rrset_data* d = (struct packed_rrset_data*)nsec->
 100                 entry.data;
 101         size_t len;
 102         if(!d || d->count == 0 || d->rr_len[0] < 2+1)
 103                 return 0;
 104         len = dname_valid(d->rr_data[0]+2, d->rr_len[0]-2);
 105         if(!len)
 106                 return 0;
 107         return nsecbitmap_has_type_rdata(d->rr_data[0]+2+len,
 108                 d->rr_len[0]-2-len, type);
 109 }
 110
 111 /**
 112  * Get next owner name from nsec record
 113  * @param nsec: the nsec RRset.
 114  *      If there are multiple RRs, then this will only return one of them.
 115  * @param nm: the next name is returned.
 116  * @param ln: length of nm is returned.
 117  * @return false on a bad NSEC RR (too short, malformed dname).
 118  */
 119 static int
 120 nsec_get_next(struct ub_packed_rrset_key* nsec, uint8_t** nm, size_t* ln)
 121 {
 122         struct packed_rrset_data* d = (struct packed_rrset_data*)nsec->
 123                 entry.data;
 124         if(!d || d->count == 0 || d->rr_len[0] < 2+1) {
 125                 *nm = 0;
 126                 *ln = 0;
 127                 return 0;
 128         }
 129         *nm = d->rr_data[0]+2;
 130         *ln = dname_valid(*nm, d->rr_len[0]-2);
 131         if(!*ln) {
 132                 *nm = 0;
 133                 *ln = 0;
 134                 return 0;
 135         }
 136         return 1;
 137 }
 138
 139 /**
 140  * For an NSEC that matches the DS queried for, check absence of DS type.
 141  *
 142  * @param nsec: NSEC for proof, must be trusted.
 143  * @param qinfo: what is queried for.
 144  * @return if secure the nsec proves that no DS is present, or
 145  *      insecure if it proves it is not a delegation point.
 146  *      or bogus if something was wrong.
 147  */
 148 static enum sec_status
 149 val_nsec_proves_no_ds(struct ub_packed_rrset_key* nsec,
 150         struct query_info* qinfo)
 151 {
 152         log_assert(qinfo->qtype == LDNS_RR_TYPE_DS);
 153         log_assert(ntohs(nsec->rk.type) == LDNS_RR_TYPE_NSEC);
 154
 155         if(nsec_has_type(nsec, LDNS_RR_TYPE_SOA) && qinfo->qname_len != 1) {
 156                 /* SOA present means that this is the NSEC from the child,
 157                  * not the parent (so it is the wrong one). */
 158                 return sec_status_bogus;
 159         }
 160         if(nsec_has_type(nsec, LDNS_RR_TYPE_DS)) {
 161                 /* DS present means that there should have been a positive
 162                  * response to the DS query, so there is something wrong. */
 163                 return sec_status_bogus;
 164         }
 165
 166         if(!nsec_has_type(nsec, LDNS_RR_TYPE_NS)) {
 167                 /* If there is no NS at this point at all, then this
 168                  * doesn't prove anything one way or the other. */
 169                 return sec_status_insecure;
 170         }
 171         /* Otherwise, this proves no DS. */
 172         return sec_status_secure;
 173 }
 174
 175 /** check security status from cache or verify rrset, returns true if secure */
 176 static int
 177 nsec_verify_rrset(struct module_env* env, struct val_env* ve,
 178         struct ub_packed_rrset_key* nsec, struct key_entry_key* kkey,
 179         char** reason, sldns_ede_code* reason_bogus,
 180         struct module_qstate* qstate)
 181 {
 182         struct packed_rrset_data* d = (struct packed_rrset_data*)
 183                 nsec->entry.data;
 184         int verified = 0;
 185         if(!d) return 0;
 186         if(d->security == sec_status_secure)
 187                 return 1;
 188         rrset_check_sec_status(env->rrset_cache, nsec, *env->now);
 189         if(d->security == sec_status_secure)
 190                 return 1;
 191         d->security = val_verify_rrset_entry(env, ve, nsec, kkey, reason,
 192                 reason_bogus, LDNS_SECTION_AUTHORITY, qstate, &verified);
 193         if(d->security == sec_status_secure) {
 194                 rrset_update_sec_status(env->rrset_cache, nsec, *env->now);
 195                 return 1;
 196         }
 197         return 0;
 198 }
 199
 200 enum sec_status
 201 val_nsec_prove_nodata_dsreply(struct module_env* env, struct val_env* ve,
 202         struct query_info* qinfo, struct reply_info* rep,
 203         struct key_entry_key* kkey, time_t* proof_ttl, char** reason,
 204         sldns_ede_code* reason_bogus, struct module_qstate* qstate)
 205 {
 206         struct ub_packed_rrset_key* nsec = reply_find_rrset_section_ns(
 207                 rep, qinfo->qname, qinfo->qname_len, LDNS_RR_TYPE_NSEC,
 208                 qinfo->qclass);
 209         enum sec_status sec;
 210         size_t i;
 211         uint8_t* wc = NULL, *ce = NULL;
 212         int valid_nsec = 0;
 213         struct ub_packed_rrset_key* wc_nsec = NULL;
 214
 215         /* If we have a NSEC at the same name, it must prove one
 216          * of two things
 217          * --
 218          * 1) this is a delegation point and there is no DS
 219          * 2) this is not a delegation point */
 220         if(nsec) {
 221                 if(!nsec_verify_rrset(env, ve, nsec, kkey, reason,
 222                         reason_bogus, qstate)) {
 223                         verbose(VERB_ALGO, "NSEC RRset for the "
 224                                 "referral did not verify.");
 225                         return sec_status_bogus;
 226                 }
 227                 sec = val_nsec_proves_no_ds(nsec, qinfo);
 228                 if(sec == sec_status_bogus) {
 229                         /* something was wrong. */
 230                         *reason = "NSEC does not prove absence of DS";
 231                         *reason_bogus = LDNS_EDE_DNSSEC_BOGUS;
 232                         return sec;
 233                 } else if(sec == sec_status_insecure) {
 234                         /* this wasn't a delegation point. */
 235                         return sec;
 236                 } else if(sec == sec_status_secure) {
 237                         /* this proved no DS. */
 238                         *proof_ttl = ub_packed_rrset_ttl(nsec);
 239                         return sec;
 240                 }
 241                 /* if unchecked, fall through to next proof */
 242         }
 243
 244         /* Otherwise, there is no NSEC at qname. This could be an ENT.
 245          * (ENT=empty non terminal). If not, this is broken. */
 246
 247         /* verify NSEC rrsets in auth section */
 248         for(i=rep->an_numrrsets; i < rep->an_numrrsets+rep->ns_numrrsets;
 249                 i++) {
 250                 if(rep->rrsets[i]->rk.type != htons(LDNS_RR_TYPE_NSEC))
 251                         continue;
 252                 if(!nsec_verify_rrset(env, ve, rep->rrsets[i], kkey, reason,
 253                         reason_bogus, qstate)) {
 254                         verbose(VERB_ALGO, "NSEC for empty non-terminal "
 255                                 "did not verify.");
 256                         *reason = "NSEC for empty non-terminal "
 257                                 "did not verify.";
 258                         return sec_status_bogus;
 259                 }
 260                 if(nsec_proves_nodata(rep->rrsets[i], qinfo, &wc)) {
 261                         verbose(VERB_ALGO, "NSEC for empty non-terminal "
 262                                 "proved no DS.");
 263                         *proof_ttl = rrset_get_ttl(rep->rrsets[i]);
 264                         if(wc && dname_is_wild(rep->rrsets[i]->rk.dname))
 265                                 wc_nsec = rep->rrsets[i];
 266                         valid_nsec = 1;
 267                 }
 268                 if(val_nsec_proves_name_error(rep->rrsets[i], qinfo->qname)) {
 269                         ce = nsec_closest_encloser(qinfo->qname,
 270                                 rep->rrsets[i]);
 271                 }
 272         }
 273         if(wc && !ce)
 274                 valid_nsec = 0;
 275         else if(wc && ce) {
 276                 /* ce and wc must match */
 277                 if(query_dname_compare(wc, ce) != 0)
 278                         valid_nsec = 0;
 279                 else if(!wc_nsec)
 280                         valid_nsec = 0;
 281         }
 282         if(valid_nsec) {
 283                 if(wc) {
 284                         /* check if this is a delegation */
 285                         *reason = "NSEC for wildcard does not prove absence of DS";
 286                         return val_nsec_proves_no_ds(wc_nsec, qinfo);
 287                 }
 288                 /* valid nsec proves empty nonterminal */
 289                 return sec_status_insecure;
 290         }
 291
 292         /* NSEC proof did not conclusively point to DS or no DS */
 293         return sec_status_unchecked;
 294 }
 295
 296 int nsec_proves_nodata(struct ub_packed_rrset_key* nsec,
 297         struct query_info* qinfo, uint8_t** wc)
 298 {
 299         log_assert(wc);
 300         if(query_dname_compare(nsec->rk.dname, qinfo->qname) != 0) {
 301                 uint8_t* nm;
 302                 size_t ln;
 303
 304                 /* empty-non-terminal checking.
 305                  * Done before wildcard, because this is an exact match,
 306                  * and would prevent a wildcard from matching. */
 307
 308                 /* If the nsec is proving that qname is an ENT, the nsec owner
 309                  * will be less than qname, and the next name will be a child
 310                  * domain of the qname. */
 311                 if(!nsec_get_next(nsec, &nm, &ln))
 312                         return 0; /* bad nsec */
 313                 if(dname_strict_subdomain_c(nm, qinfo->qname) &&
 314                         dname_canonical_compare(nsec->rk.dname,
 315                                 qinfo->qname) < 0) {
 316                         return 1; /* proves ENT */
 317                 }
 318
 319                 /* wildcard checking. */
 320
 321                 /* If this is a wildcard NSEC, make sure that a) it was
 322                  * possible to have generated qname from the wildcard and
 323                  * b) the type map does not contain qtype. Note that this
 324                  * does NOT prove that this wildcard was the applicable
 325                  * wildcard. */
 326                 if(dname_is_wild(nsec->rk.dname)) {
 327                         /* the purported closest encloser. */
 328                         uint8_t* ce = nsec->rk.dname;
 329                         size_t ce_len = nsec->rk.dname_len;
 330                         dname_remove_label(&ce, &ce_len);
 331
 332                         /* The qname must be a strict subdomain of the
 333                          * closest encloser, for the wildcard to apply
 334                          */
 335                         if(dname_strict_subdomain_c(qinfo->qname, ce)) {
 336                                 /* here we have a matching NSEC for the qname,
 337                                  * perform matching NSEC checks */
 338                                 if(nsec_has_type(nsec, LDNS_RR_TYPE_CNAME)) {
 339                                    /* should have gotten the wildcard CNAME */
 340                                         return 0;
 341                                 }
 342                                 if(nsec_has_type(nsec, LDNS_RR_TYPE_NS) &&
 343                                    !nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) {
 344                                    /* wrong parentside (wildcard) NSEC used */
 345                                         return 0;
 346                                 }
 347                                 if(nsec_has_type(nsec, qinfo->qtype)) {
 348                                         return 0;
 349                                 }
 350                                 *wc = ce;
 351                                 return 1;
 352                         }
 353                 } else {
 354                         /* See if the next owner name covers a wildcard
 355                          * empty non-terminal. */
 356                         while (dname_canonical_compare(nsec->rk.dname, nm) < 0) {
 357                                 /* wildcard does not apply if qname below
 358                                  * the name that exists under the '*' */
 359                                 if (dname_subdomain_c(qinfo->qname, nm))
 360                                         break;
 361                                 /* but if it is a wildcard and qname is below
 362                                  * it, then the wildcard applies. The wildcard
 363                                  * is an empty nonterminal. nodata proven. */
 364                                 if (dname_is_wild(nm)) {
 365                                         size_t ce_len = ln;
 366                                         uint8_t* ce = nm;
 367                                         dname_remove_label(&ce, &ce_len);
 368                                         if(dname_strict_subdomain_c(qinfo->qname, ce)) {
 369                                                 *wc = ce;
 370                                                 return 1;
 371                                         }
 372                                 }
 373                                 dname_remove_label(&nm, &ln);
 374                         }
 375                 }
 376
 377                 /* Otherwise, this NSEC does not prove ENT and is not a
 378                  * wildcard, so it does not prove NODATA. */
 379                 return 0;
 380         }
 381
 382         /* If the qtype exists, then we should have gotten it. */
 383         if(nsec_has_type(nsec, qinfo->qtype)) {
 384                 return 0;
 385         }
 386
 387         /* if the name is a CNAME node, then we should have gotten the CNAME*/
 388         if(nsec_has_type(nsec, LDNS_RR_TYPE_CNAME)) {
 389                 return 0;
 390         }
 391
 392         /* If an NS set exists at this name, and NOT a SOA (so this is a
 393          * zone cut, not a zone apex), then we should have gotten a
 394          * referral (or we just got the wrong NSEC).
 395          * The reverse of this check is used when qtype is DS, since that
 396          * must use the NSEC from above the zone cut. */
 397         if(qinfo->qtype != LDNS_RR_TYPE_DS &&
 398                 nsec_has_type(nsec, LDNS_RR_TYPE_NS) &&
 399                 !nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) {
 400                 return 0;
 401         } else if(qinfo->qtype == LDNS_RR_TYPE_DS &&
 402                 nsec_has_type(nsec, LDNS_RR_TYPE_SOA) &&
 403                 !dname_is_root(qinfo->qname)) {
 404                 return 0;
 405         }
 406
 407         return 1;
 408 }
 409
 410 int
 411 val_nsec_proves_name_error(struct ub_packed_rrset_key* nsec, uint8_t* qname)
 412 {
 413         uint8_t* owner = nsec->rk.dname;
 414         uint8_t* next;
 415         size_t nlen;
 416         if(!nsec_get_next(nsec, &next, &nlen))
 417                 return 0;
 418
 419         /* If NSEC owner == qname, then this NSEC proves that qname exists. */
 420         if(query_dname_compare(qname, owner) == 0) {
 421                 return 0;
 422         }
 423
 424         /* If NSEC is a parent of qname, we need to check the type map
 425          * If the parent name has a DNAME or is a delegation point, then
 426          * this NSEC is being misused. */
 427         if(dname_subdomain_c(qname, owner) &&
 428                 (nsec_has_type(nsec, LDNS_RR_TYPE_DNAME) ||
 429                 (nsec_has_type(nsec, LDNS_RR_TYPE_NS)
 430                         && !nsec_has_type(nsec, LDNS_RR_TYPE_SOA))
 431                 )) {
 432                 return 0;
 433         }
 434
 435         if(query_dname_compare(owner, next) == 0) {
 436                 /* this nsec is the only nsec */
 437                 /* zone.name NSEC zone.name, disproves everything else */
 438                 /* but only for subdomains of that zone */
 439                 if(dname_strict_subdomain_c(qname, next))
 440                         return 1;
 441         }
 442         else if(dname_canonical_compare(owner, next) > 0) {
 443                 /* this is the last nsec, ....(bigger) NSEC zonename(smaller) */
 444                 /* the names after the last (owner) name do not exist
 445                  * there are no names before the zone name in the zone
 446                  * but the qname must be a subdomain of the zone name(next). */
 447                 if(dname_canonical_compare(owner, qname) < 0 &&
 448                         dname_strict_subdomain_c(qname, next))
 449                         return 1;
 450         } else {
 451                 /* regular NSEC, (smaller) NSEC (larger) */
 452                 if(dname_canonical_compare(owner, qname) < 0 &&
 453                    dname_canonical_compare(qname, next) < 0) {
 454                         return 1;
 455                 }
 456         }
 457         return 0;
 458 }
 459
 460 int val_nsec_proves_insecuredelegation(struct ub_packed_rrset_key* nsec,
 461         struct query_info* qinfo)
 462 {
 463         if(nsec_has_type(nsec, LDNS_RR_TYPE_NS) &&
 464                 !nsec_has_type(nsec, LDNS_RR_TYPE_DS) &&
 465                 !nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) {
 466                 /* see if nsec signals an insecure delegation */
 467                 if(qinfo->qtype == LDNS_RR_TYPE_DS) {
 468                         /* if type is DS and qname is equal to nsec, then it
 469                          * is an exact match nsec, result not insecure */
 470                         if(dname_strict_subdomain_c(qinfo->qname,
 471                                 nsec->rk.dname))
 472                                 return 1;
 473                 } else {
 474                         if(dname_subdomain_c(qinfo->qname, nsec->rk.dname))
 475                                 return 1;
 476                 }
 477         }
 478         return 0;
 479 }
 480
 481 uint8_t*
 482 nsec_closest_encloser(uint8_t* qname, struct ub_packed_rrset_key* nsec)
 483 {
 484         uint8_t* next;
 485         size_t nlen;
 486         uint8_t* common1, *common2;
 487         if(!nsec_get_next(nsec, &next, &nlen))
 488                 return NULL;
 489         /* longest common with owner or next name */
 490         common1 = dname_get_shared_topdomain(nsec->rk.dname, qname);
 491         common2 = dname_get_shared_topdomain(next, qname);
 492         if(dname_count_labels(common1) > dname_count_labels(common2))
 493                 return common1;
 494         return common2;
 495 }
 496
 497 int val_nsec_proves_positive_wildcard(struct ub_packed_rrset_key* nsec,
 498         struct query_info* qinf, uint8_t* wc)
 499 {
 500         uint8_t* ce;
 501         /*  1) prove that qname doesn't exist and
 502          *  2) that the correct wildcard was used
 503          *  nsec has been verified already. */
 504         if(!val_nsec_proves_name_error(nsec, qinf->qname))
 505                 return 0;
 506         /* check wildcard name */
 507         ce = nsec_closest_encloser(qinf->qname, nsec);
 508         if(!ce)
 509                 return 0;
 510         if(query_dname_compare(wc, ce) != 0) {
 511                 return 0;
 512         }
 513         return 1;
 514 }
 515
 516 int
 517 val_nsec_proves_no_wc(struct ub_packed_rrset_key* nsec, uint8_t* qname,
 518         size_t qnamelen)
 519 {
 520         /* Determine if a NSEC record proves the non-existence of a
 521          * wildcard that could have produced qname. */
 522         int labs;
 523         uint8_t* ce = nsec_closest_encloser(qname, nsec);
 524         uint8_t* strip;
 525         size_t striplen;
 526         uint8_t buf[LDNS_MAX_DOMAINLEN+3];
 527         if(!ce)
 528                 return 0;
 529         /* we can subtract the closest encloser count - since that is the
 530          * largest shared topdomain with owner and next NSEC name,
 531          * because the NSEC is no proof for names shorter than the owner
 532          * and next names. */
 533         labs = dname_count_labels(qname) - dname_count_labels(ce);
 534
 535         if(labs > 0) {
 536                 /* i is number of labels to strip off qname, prepend * wild */
 537                 strip = qname;
 538                 striplen = qnamelen;
 539                 dname_remove_labels(&strip, &striplen, labs);
 540                 if(striplen > LDNS_MAX_DOMAINLEN-2)
 541                         return 0; /* too long to prepend wildcard */
 542                 buf[0] = 1;
 543                 buf[1] = (uint8_t)'*';
 544                 memmove(buf+2, strip, striplen);
 545                 if(val_nsec_proves_name_error(nsec, buf)) {
 546                         return 1;
 547                 }
 548         }
 549         return 0;
 550 }