contrib/unbound/validator/val_nsec3.c

   1 /*
   2  * validator/val_nsec3.c - validator NSEC3 denial of existance 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 NSEC3 checking, the different NSEC3 proofs
  41  * for denial of existance, and proofs for presence of types.
  42  */
  43 #include "config.h"
  44 #include <ctype.h>
  45 #ifdef HAVE_OPENSSL_SSL_H
  46 #include "openssl/ssl.h"
  47 #endif
  48 #ifdef HAVE_NSS
  49 /* nss3 */
  50 #include "sechash.h"
  51 #endif
  52 #include "validator/val_nsec3.h"
  53 #include "validator/validator.h"
  54 #include "validator/val_kentry.h"
  55 #include "services/cache/rrset.h"
  56 #include "util/regional.h"
  57 #include "util/rbtree.h"
  58 #include "util/module.h"
  59 #include "util/net_help.h"
  60 #include "util/data/packed_rrset.h"
  61 #include "util/data/dname.h"
  62 #include "util/data/msgreply.h"
  63 /* we include nsec.h for the bitmap_has_type function */
  64 #include "validator/val_nsec.h"
  65 #include "ldns/sbuffer.h"
  66
  67 /**
  68  * This function we get from ldns-compat or from base system
  69  * it returns the number of data bytes stored at the target, or <0 on error.
  70  */
  71 int sldns_b32_ntop_extended_hex(uint8_t const *src, size_t srclength,
  72         char *target, size_t targsize);
  73 /**
  74  * This function we get from ldns-compat or from base system
  75  * it returns the number of data bytes stored at the target, or <0 on error.
  76  */
  77 int sldns_b32_pton_extended_hex(char const *src, size_t hashed_owner_str_len,
  78         uint8_t *target, size_t targsize);
  79
  80 /**
  81  * Closest encloser (ce) proof results
  82  * Contains the ce and the next-closer (nc) proof.
  83  */
  84 struct ce_response {
  85         /** the closest encloser name */
  86         uint8_t* ce;
  87         /** length of ce */
  88         size_t ce_len;
  89         /** NSEC3 record that proved ce. rrset */
  90         struct ub_packed_rrset_key* ce_rrset;
  91         /** NSEC3 record that proved ce. rr number */
  92         int ce_rr;
  93         /** NSEC3 record that proved nc. rrset */
  94         struct ub_packed_rrset_key* nc_rrset;
  95         /** NSEC3 record that proved nc. rr*/
  96         int nc_rr;
  97 };
  98
  99 /**
 100  * Filter conditions for NSEC3 proof
 101  * Used to iterate over the applicable NSEC3 RRs.
 102  */
 103 struct nsec3_filter {
 104         /** Zone name, only NSEC3 records for this zone are considered */
 105         uint8_t* zone;
 106         /** length of the zonename */
 107         size_t zone_len;
 108         /** the list of NSEC3s to filter; array */
 109         struct ub_packed_rrset_key** list;
 110         /** number of rrsets in list */
 111         size_t num;
 112         /** class of records for the NSEC3, only this class applies */
 113         uint16_t fclass;
 114 };
 115
 116 /** return number of rrs in an rrset */
 117 static size_t
 118 rrset_get_count(struct ub_packed_rrset_key* rrset)
 119 {
 120         struct packed_rrset_data* d = (struct packed_rrset_data*)
 121                 rrset->entry.data;
 122         if(!d) return 0;
 123         return d->count;
 124 }
 125
 126 /** return if nsec3 RR has unknown flags */
 127 static int
 128 nsec3_unknown_flags(struct ub_packed_rrset_key* rrset, int r)
 129 {
 130         struct packed_rrset_data* d = (struct packed_rrset_data*)
 131                 rrset->entry.data;
 132         log_assert(d && r < (int)d->count);
 133         if(d->rr_len[r] < 2+2)
 134                 return 0; /* malformed */
 135         return (int)(d->rr_data[r][2+1] & NSEC3_UNKNOWN_FLAGS);
 136 }
 137
 138 int
 139 nsec3_has_optout(struct ub_packed_rrset_key* rrset, int r)
 140 {
 141         struct packed_rrset_data* d = (struct packed_rrset_data*)
 142                 rrset->entry.data;
 143         log_assert(d && r < (int)d->count);
 144         if(d->rr_len[r] < 2+2)
 145                 return 0; /* malformed */
 146         return (int)(d->rr_data[r][2+1] & NSEC3_OPTOUT);
 147 }
 148
 149 /** return nsec3 RR algorithm */
 150 static int
 151 nsec3_get_algo(struct ub_packed_rrset_key* rrset, int r)
 152 {
 153         struct packed_rrset_data* d = (struct packed_rrset_data*)
 154                 rrset->entry.data;
 155         log_assert(d && r < (int)d->count);
 156         if(d->rr_len[r] < 2+1)
 157                 return 0; /* malformed */
 158         return (int)(d->rr_data[r][2+0]);
 159 }
 160
 161 /** return if nsec3 RR has known algorithm */
 162 static int
 163 nsec3_known_algo(struct ub_packed_rrset_key* rrset, int r)
 164 {
 165         struct packed_rrset_data* d = (struct packed_rrset_data*)
 166                 rrset->entry.data;
 167         log_assert(d && r < (int)d->count);
 168         if(d->rr_len[r] < 2+1)
 169                 return 0; /* malformed */
 170         switch(d->rr_data[r][2+0]) {
 171                 case NSEC3_HASH_SHA1:
 172                         return 1;
 173         }
 174         return 0;
 175 }
 176
 177 /** return nsec3 RR iteration count */
 178 static size_t
 179 nsec3_get_iter(struct ub_packed_rrset_key* rrset, int r)
 180 {
 181         uint16_t i;
 182         struct packed_rrset_data* d = (struct packed_rrset_data*)
 183                 rrset->entry.data;
 184         log_assert(d && r < (int)d->count);
 185         if(d->rr_len[r] < 2+4)
 186                 return 0; /* malformed */
 187         memmove(&i, d->rr_data[r]+2+2, sizeof(i));
 188         i = ntohs(i);
 189         return (size_t)i;
 190 }
 191
 192 /** return nsec3 RR salt */
 193 static int
 194 nsec3_get_salt(struct ub_packed_rrset_key* rrset, int r,
 195         uint8_t** salt, size_t* saltlen)
 196 {
 197         struct packed_rrset_data* d = (struct packed_rrset_data*)
 198                 rrset->entry.data;
 199         log_assert(d && r < (int)d->count);
 200         if(d->rr_len[r] < 2+5) {
 201                 *salt = 0;
 202                 *saltlen = 0;
 203                 return 0; /* malformed */
 204         }
 205         *saltlen = (size_t)d->rr_data[r][2+4];
 206         if(d->rr_len[r] < 2+5+(size_t)*saltlen) {
 207                 *salt = 0;
 208                 *saltlen = 0;
 209                 return 0; /* malformed */
 210         }
 211         *salt = d->rr_data[r]+2+5;
 212         return 1;
 213 }
 214
 215 int nsec3_get_params(struct ub_packed_rrset_key* rrset, int r,
 216         int* algo, size_t* iter, uint8_t** salt, size_t* saltlen)
 217 {
 218         if(!nsec3_known_algo(rrset, r) || nsec3_unknown_flags(rrset, r))
 219                 return 0;
 220         if(!nsec3_get_salt(rrset, r, salt, saltlen))
 221                 return 0;
 222         *algo = nsec3_get_algo(rrset, r);
 223         *iter = nsec3_get_iter(rrset, r);
 224         return 1;
 225 }
 226
 227 int
 228 nsec3_get_nextowner(struct ub_packed_rrset_key* rrset, int r,
 229         uint8_t** next, size_t* nextlen)
 230 {
 231         size_t saltlen;
 232         struct packed_rrset_data* d = (struct packed_rrset_data*)
 233                 rrset->entry.data;
 234         log_assert(d && r < (int)d->count);
 235         if(d->rr_len[r] < 2+5) {
 236                 *next = 0;
 237                 *nextlen = 0;
 238                 return 0; /* malformed */
 239         }
 240         saltlen = (size_t)d->rr_data[r][2+4];
 241         if(d->rr_len[r] < 2+5+saltlen+1) {
 242                 *next = 0;
 243                 *nextlen = 0;
 244                 return 0; /* malformed */
 245         }
 246         *nextlen = (size_t)d->rr_data[r][2+5+saltlen];
 247         if(d->rr_len[r] < 2+5+saltlen+1+*nextlen) {
 248                 *next = 0;
 249                 *nextlen = 0;
 250                 return 0; /* malformed */
 251         }
 252         *next = d->rr_data[r]+2+5+saltlen+1;
 253         return 1;
 254 }
 255
 256 size_t nsec3_hash_to_b32(uint8_t* hash, size_t hashlen, uint8_t* zone,
 257         size_t zonelen, uint8_t* buf, size_t max)
 258 {
 259         /* write b32 of name, leave one for length */
 260         int ret;
 261         if(max < hashlen*2+1) /* quick approx of b32, as if hexb16 */
 262                 return 0;
 263         ret = sldns_b32_ntop_extended_hex(hash, hashlen, (char*)buf+1, max-1);
 264         if(ret < 1)
 265                 return 0;
 266         buf[0] = (uint8_t)ret; /* length of b32 label */
 267         ret++;
 268         if(max - ret < zonelen)
 269                 return 0;
 270         memmove(buf+ret, zone, zonelen);
 271         return zonelen+(size_t)ret;
 272 }
 273
 274 size_t nsec3_get_nextowner_b32(struct ub_packed_rrset_key* rrset, int r,
 275         uint8_t* buf, size_t max)
 276 {
 277         uint8_t* nm, *zone;
 278         size_t nmlen, zonelen;
 279         if(!nsec3_get_nextowner(rrset, r, &nm, &nmlen))
 280                 return 0;
 281         /* append zone name; the owner name must be <b32>.zone */
 282         zone = rrset->rk.dname;
 283         zonelen = rrset->rk.dname_len;
 284         dname_remove_label(&zone, &zonelen);
 285         return nsec3_hash_to_b32(nm, nmlen, zone, zonelen, buf, max);
 286 }
 287
 288 int
 289 nsec3_has_type(struct ub_packed_rrset_key* rrset, int r, uint16_t type)
 290 {
 291         uint8_t* bitmap;
 292         size_t bitlen, skiplen;
 293         struct packed_rrset_data* d = (struct packed_rrset_data*)
 294                 rrset->entry.data;
 295         log_assert(d && r < (int)d->count);
 296         skiplen = 2+4;
 297         /* skip salt */
 298         if(d->rr_len[r] < skiplen+1)
 299                 return 0; /* malformed, too short */
 300         skiplen += 1+(size_t)d->rr_data[r][skiplen];
 301         /* skip next hashed owner */
 302         if(d->rr_len[r] < skiplen+1)
 303                 return 0; /* malformed, too short */
 304         skiplen += 1+(size_t)d->rr_data[r][skiplen];
 305         if(d->rr_len[r] < skiplen)
 306                 return 0; /* malformed, too short */
 307         bitlen = d->rr_len[r] - skiplen;
 308         bitmap = d->rr_data[r]+skiplen;
 309         return nsecbitmap_has_type_rdata(bitmap, bitlen, type);
 310 }
 311
 312 /**
 313  * Iterate through NSEC3 list, per RR
 314  * This routine gives the next RR in the list (or sets rrset null).
 315  * Usage:
 316  *
 317  * size_t rrsetnum;
 318  * int rrnum;
 319  * struct ub_packed_rrset_key* rrset;
 320  * for(rrset=filter_first(filter, &rrsetnum, &rrnum); rrset;
 321  *      rrset=filter_next(filter, &rrsetnum, &rrnum))
 322  *              do_stuff;
 323  *
 324  * Also filters out
 325  *      o unknown flag NSEC3s
 326  *      o unknown algorithm NSEC3s.
 327  * @param filter: nsec3 filter structure.
 328  * @param rrsetnum: in/out rrset number to look at.
 329  * @param rrnum: in/out rr number in rrset to look at.
 330  * @returns ptr to the next rrset (or NULL at end).
 331  */
 332 static struct ub_packed_rrset_key*
 333 filter_next(struct nsec3_filter* filter, size_t* rrsetnum, int* rrnum)
 334 {
 335         size_t i;
 336         int r;
 337         uint8_t* nm;
 338         size_t nmlen;
 339         if(!filter->zone) /* empty list */
 340                 return NULL;
 341         for(i=*rrsetnum; i<filter->num; i++) {
 342                 /* see if RRset qualifies */
 343                 if(ntohs(filter->list[i]->rk.type) != LDNS_RR_TYPE_NSEC3 ||
 344                         ntohs(filter->list[i]->rk.rrset_class) !=
 345                         filter->fclass)
 346                         continue;
 347                 /* check RRset zone */
 348                 nm = filter->list[i]->rk.dname;
 349                 nmlen = filter->list[i]->rk.dname_len;
 350                 dname_remove_label(&nm, &nmlen);
 351                 if(query_dname_compare(nm, filter->zone) != 0)
 352                         continue;
 353                 if(i == *rrsetnum)
 354                         r = (*rrnum) + 1; /* continue at next RR */
 355                 else    r = 0;          /* new RRset start at first RR */
 356                 for(; r < (int)rrset_get_count(filter->list[i]); r++) {
 357                         /* skip unknown flags, algo */
 358                         if(nsec3_unknown_flags(filter->list[i], r) ||
 359                                 !nsec3_known_algo(filter->list[i], r))
 360                                 continue;
 361                         /* this one is a good target */
 362                         *rrsetnum = i;
 363                         *rrnum = r;
 364                         return filter->list[i];
 365                 }
 366         }
 367         return NULL;
 368 }
 369
 370 /**
 371  * Start iterating over NSEC3 records.
 372  * @param filter: the filter structure, must have been filter_init-ed.
 373  * @param rrsetnum: can be undefined on call, inited.
 374  * @param rrnum: can be undefined on call, inited.
 375  * @return first rrset of an NSEC3, together with rrnum this points to
 376  *      the first RR to examine. Is NULL on empty list.
 377  */
 378 static struct ub_packed_rrset_key*
 379 filter_first(struct nsec3_filter* filter, size_t* rrsetnum, int* rrnum)
 380 {
 381         *rrsetnum = 0;
 382         *rrnum = -1;
 383         return filter_next(filter, rrsetnum, rrnum);
 384 }
 385
 386 /** see if at least one RR is known (flags, algo) */
 387 static int
 388 nsec3_rrset_has_known(struct ub_packed_rrset_key* s)
 389 {
 390         int r;
 391         for(r=0; r < (int)rrset_get_count(s); r++) {
 392                 if(!nsec3_unknown_flags(s, r) && nsec3_known_algo(s, r))
 393                         return 1;
 394         }
 395         return 0;
 396 }
 397
 398 /**
 399  * Initialize the filter structure.
 400  * Finds the zone by looking at available NSEC3 records and best match.
 401  *      (skips the unknown flag and unknown algo NSEC3s).
 402  *
 403  * @param filter: nsec3 filter structure.
 404  * @param list: list of rrsets, an array of them.
 405  * @param num: number of rrsets in list.
 406  * @param qinfo:
 407  *      query name to match a zone for.
 408  *      query type (if DS a higher zone must be chosen)
 409  *      qclass, to filter NSEC3s with.
 410  */
 411 static void
 412 filter_init(struct nsec3_filter* filter, struct ub_packed_rrset_key** list,
 413         size_t num, struct query_info* qinfo)
 414 {
 415         size_t i;
 416         uint8_t* nm;
 417         size_t nmlen;
 418         filter->zone = NULL;
 419         filter->zone_len = 0;
 420         filter->list = list;
 421         filter->num = num;
 422         filter->fclass = qinfo->qclass;
 423         for(i=0; i<num; i++) {
 424                 /* ignore other stuff in the list */
 425                 if(ntohs(list[i]->rk.type) != LDNS_RR_TYPE_NSEC3 ||
 426                         ntohs(list[i]->rk.rrset_class) != qinfo->qclass)
 427                         continue;
 428                 /* skip unknown flags, algo */
 429                 if(!nsec3_rrset_has_known(list[i]))
 430                         continue;
 431
 432                 /* since NSEC3s are base32.zonename, we can find the zone
 433                  * name by stripping off the first label of the record */
 434                 nm = list[i]->rk.dname;
 435                 nmlen = list[i]->rk.dname_len;
 436                 dname_remove_label(&nm, &nmlen);
 437                 /* if we find a domain that can prove about the qname,
 438                  * and if this domain is closer to the qname */
 439                 if(dname_subdomain_c(qinfo->qname, nm) && (!filter->zone ||
 440                         dname_subdomain_c(nm, filter->zone))) {
 441                         /* for a type DS do not accept a zone equal to qname*/
 442                         if(qinfo->qtype == LDNS_RR_TYPE_DS &&
 443                                 query_dname_compare(qinfo->qname, nm) == 0 &&
 444                                 !dname_is_root(qinfo->qname))
 445                                 continue;
 446                         filter->zone = nm;
 447                         filter->zone_len = nmlen;
 448                 }
 449         }
 450 }
 451
 452 /**
 453  * Find max iteration count using config settings and key size
 454  * @param ve: validator environment with iteration count config settings.
 455  * @param bits: key size
 456  * @return max iteration count
 457  */
 458 static size_t
 459 get_max_iter(struct val_env* ve, size_t bits)
 460 {
 461         int i;
 462         log_assert(ve->nsec3_keyiter_count > 0);
 463         /* round up to nearest config keysize, linear search, keep it small */
 464         for(i=0; i<ve->nsec3_keyiter_count; i++) {
 465                 if(bits <= ve->nsec3_keysize[i])
 466                         return ve->nsec3_maxiter[i];
 467         }
 468         /* else, use value for biggest key */
 469         return ve->nsec3_maxiter[ve->nsec3_keyiter_count-1];
 470 }
 471
 472 /**
 473  * Determine if any of the NSEC3 rrs iteration count is too high, from key.
 474  * @param ve: validator environment with iteration count config settings.
 475  * @param filter: what NSEC3s to loop over.
 476  * @param kkey: key entry used for verification; used for iteration counts.
 477  * @return 1 if some nsec3s are above the max iteration count.
 478  */
 479 static int
 480 nsec3_iteration_count_high(struct val_env* ve, struct nsec3_filter* filter,
 481         struct key_entry_key* kkey)
 482 {
 483         size_t rrsetnum;
 484         int rrnum;
 485         struct ub_packed_rrset_key* rrset;
 486         /* first determine the max number of iterations */
 487         size_t bits = key_entry_keysize(kkey);
 488         size_t max_iter = get_max_iter(ve, bits);
 489         verbose(VERB_ALGO, "nsec3: keysize %d bits, max iterations %d",
 490                 (int)bits, (int)max_iter);
 491
 492         for(rrset=filter_first(filter, &rrsetnum, &rrnum); rrset;
 493                 rrset=filter_next(filter, &rrsetnum, &rrnum)) {
 494                 if(nsec3_get_iter(rrset, rrnum) > max_iter)
 495                         return 1;
 496         }
 497         return 0;
 498 }
 499
 500 /* nsec3_cache_compare for rbtree */
 501 int
 502 nsec3_hash_cmp(const void* c1, const void* c2)
 503 {
 504         struct nsec3_cached_hash* h1 = (struct nsec3_cached_hash*)c1;
 505         struct nsec3_cached_hash* h2 = (struct nsec3_cached_hash*)c2;
 506         uint8_t* s1, *s2;
 507         size_t s1len, s2len;
 508         int c = query_dname_compare(h1->dname, h2->dname);
 509         if(c != 0)
 510                 return c;
 511         /* compare parameters */
 512         /* if both malformed, its equal, robustness */
 513         if(nsec3_get_algo(h1->nsec3, h1->rr) !=
 514                 nsec3_get_algo(h2->nsec3, h2->rr)) {
 515                 if(nsec3_get_algo(h1->nsec3, h1->rr) <
 516                         nsec3_get_algo(h2->nsec3, h2->rr))
 517                         return -1;
 518                 return 1;
 519         }
 520         if(nsec3_get_iter(h1->nsec3, h1->rr) !=
 521                 nsec3_get_iter(h2->nsec3, h2->rr)) {
 522                 if(nsec3_get_iter(h1->nsec3, h1->rr) <
 523                         nsec3_get_iter(h2->nsec3, h2->rr))
 524                         return -1;
 525                 return 1;
 526         }
 527         (void)nsec3_get_salt(h1->nsec3, h1->rr, &s1, &s1len);
 528         (void)nsec3_get_salt(h2->nsec3, h2->rr, &s2, &s2len);
 529         if(s1len != s2len) {
 530                 if(s1len < s2len)
 531                         return -1;
 532                 return 1;
 533         }
 534         return memcmp(s1, s2, s1len);
 535 }
 536
 537 size_t
 538 nsec3_get_hashed(sldns_buffer* buf, uint8_t* nm, size_t nmlen, int algo,
 539         size_t iter, uint8_t* salt, size_t saltlen, uint8_t* res, size_t max)
 540 {
 541         size_t i, hash_len;
 542         /* prepare buffer for first iteration */
 543         sldns_buffer_clear(buf);
 544         sldns_buffer_write(buf, nm, nmlen);
 545         query_dname_tolower(sldns_buffer_begin(buf));
 546         sldns_buffer_write(buf, salt, saltlen);
 547         sldns_buffer_flip(buf);
 548         switch(algo) {
 549 #if defined(HAVE_EVP_SHA1) || defined(HAVE_NSS)
 550                 case NSEC3_HASH_SHA1:
 551 #ifdef HAVE_SSL
 552                         hash_len = SHA_DIGEST_LENGTH;
 553 #else
 554                         hash_len = SHA1_LENGTH;
 555 #endif
 556                         if(hash_len > max)
 557                                 return 0;
 558 #  ifdef HAVE_SSL
 559                         (void)SHA1((unsigned char*)sldns_buffer_begin(buf),
 560                                 (unsigned long)sldns_buffer_limit(buf),
 561                                 (unsigned char*)res);
 562 #  else
 563                         (void)HASH_HashBuf(HASH_AlgSHA1, (unsigned char*)res,
 564                                 (unsigned char*)sldns_buffer_begin(buf),
 565                                 (unsigned long)sldns_buffer_limit(buf));
 566 #  endif
 567                         for(i=0; i<iter; i++) {
 568                                 sldns_buffer_clear(buf);
 569                                 sldns_buffer_write(buf, res, hash_len);
 570                                 sldns_buffer_write(buf, salt, saltlen);
 571                                 sldns_buffer_flip(buf);
 572 #  ifdef HAVE_SSL
 573                                 (void)SHA1(
 574                                         (unsigned char*)sldns_buffer_begin(buf),
 575                                         (unsigned long)sldns_buffer_limit(buf),
 576                                         (unsigned char*)res);
 577 #  else
 578                                 (void)HASH_HashBuf(HASH_AlgSHA1,
 579                                         (unsigned char*)res,
 580                                         (unsigned char*)sldns_buffer_begin(buf),
 581                                         (unsigned long)sldns_buffer_limit(buf));
 582 #  endif
 583                         }
 584                         break;
 585 #endif /* HAVE_EVP_SHA1 or NSS */
 586                 default:
 587                         log_err("nsec3 hash of unknown algo %d", algo);
 588                         return 0;
 589         }
 590         return hash_len;
 591 }
 592
 593 /** perform hash of name */
 594 static int
 595 nsec3_calc_hash(struct regional* region, sldns_buffer* buf,
 596         struct nsec3_cached_hash* c)
 597 {
 598         int algo = nsec3_get_algo(c->nsec3, c->rr);
 599         size_t iter = nsec3_get_iter(c->nsec3, c->rr);
 600         uint8_t* salt;
 601         size_t saltlen, i;
 602         if(!nsec3_get_salt(c->nsec3, c->rr, &salt, &saltlen))
 603                 return -1;
 604         /* prepare buffer for first iteration */
 605         sldns_buffer_clear(buf);
 606         sldns_buffer_write(buf, c->dname, c->dname_len);
 607         query_dname_tolower(sldns_buffer_begin(buf));
 608         sldns_buffer_write(buf, salt, saltlen);
 609         sldns_buffer_flip(buf);
 610         switch(algo) {
 611 #if defined(HAVE_EVP_SHA1) || defined(HAVE_NSS)
 612                 case NSEC3_HASH_SHA1:
 613 #ifdef HAVE_SSL
 614                         c->hash_len = SHA_DIGEST_LENGTH;
 615 #else
 616                         c->hash_len = SHA1_LENGTH;
 617 #endif
 618                         c->hash = (uint8_t*)regional_alloc(region,
 619                                 c->hash_len);
 620                         if(!c->hash)
 621                                 return 0;
 622 #  ifdef HAVE_SSL
 623                         (void)SHA1((unsigned char*)sldns_buffer_begin(buf),
 624                                 (unsigned long)sldns_buffer_limit(buf),
 625                                 (unsigned char*)c->hash);
 626 #  else
 627                         (void)HASH_HashBuf(HASH_AlgSHA1,
 628                                 (unsigned char*)c->hash,
 629                                 (unsigned char*)sldns_buffer_begin(buf),
 630                                 (unsigned long)sldns_buffer_limit(buf));
 631 #  endif
 632                         for(i=0; i<iter; i++) {
 633                                 sldns_buffer_clear(buf);
 634                                 sldns_buffer_write(buf, c->hash, c->hash_len);
 635                                 sldns_buffer_write(buf, salt, saltlen);
 636                                 sldns_buffer_flip(buf);
 637 #  ifdef HAVE_SSL
 638                                 (void)SHA1(
 639                                         (unsigned char*)sldns_buffer_begin(buf),
 640                                         (unsigned long)sldns_buffer_limit(buf),
 641                                         (unsigned char*)c->hash);
 642 #  else
 643                                 (void)HASH_HashBuf(HASH_AlgSHA1,
 644                                         (unsigned char*)c->hash,
 645                                         (unsigned char*)sldns_buffer_begin(buf),
 646                                         (unsigned long)sldns_buffer_limit(buf));
 647 #  endif
 648                         }
 649                         break;
 650 #endif /* HAVE_EVP_SHA1 or NSS */
 651                 default:
 652                         log_err("nsec3 hash of unknown algo %d", algo);
 653                         return -1;
 654         }
 655         return 1;
 656 }
 657
 658 /** perform b32 encoding of hash */
 659 static int
 660 nsec3_calc_b32(struct regional* region, sldns_buffer* buf,
 661         struct nsec3_cached_hash* c)
 662 {
 663         int r;
 664         sldns_buffer_clear(buf);
 665         r = sldns_b32_ntop_extended_hex(c->hash, c->hash_len,
 666                 (char*)sldns_buffer_begin(buf), sldns_buffer_limit(buf));
 667         if(r < 1) {
 668                 log_err("b32_ntop_extended_hex: error in encoding: %d", r);
 669                 return 0;
 670         }
 671         c->b32_len = (size_t)r;
 672         c->b32 = regional_alloc_init(region, sldns_buffer_begin(buf),
 673                 c->b32_len);
 674         if(!c->b32)
 675                 return 0;
 676         return 1;
 677 }
 678
 679 int
 680 nsec3_hash_name(rbtree_t* table, struct regional* region, sldns_buffer* buf,
 681         struct ub_packed_rrset_key* nsec3, int rr, uint8_t* dname,
 682         size_t dname_len, struct nsec3_cached_hash** hash)
 683 {
 684         struct nsec3_cached_hash* c;
 685         struct nsec3_cached_hash looki;
 686 #ifdef UNBOUND_DEBUG
 687         rbnode_t* n;
 688 #endif
 689         int r;
 690         looki.node.key = &looki;
 691         looki.nsec3 = nsec3;
 692         looki.rr = rr;
 693         looki.dname = dname;
 694         looki.dname_len = dname_len;
 695         /* lookup first in cache */
 696         c = (struct nsec3_cached_hash*)rbtree_search(table, &looki);
 697         if(c) {
 698                 *hash = c;
 699                 return 1;
 700         }
 701         /* create a new entry */
 702         c = (struct nsec3_cached_hash*)regional_alloc(region, sizeof(*c));
 703         if(!c) return 0;
 704         c->node.key = c;
 705         c->nsec3 = nsec3;
 706         c->rr = rr;
 707         c->dname = dname;
 708         c->dname_len = dname_len;
 709         r = nsec3_calc_hash(region, buf, c);
 710         if(r != 1)
 711                 return r;
 712         r = nsec3_calc_b32(region, buf, c);
 713         if(r != 1)
 714                 return r;
 715 #ifdef UNBOUND_DEBUG
 716         n =
 717 #else
 718         (void)
 719 #endif
 720         rbtree_insert(table, &c->node);
 721         log_assert(n); /* cannot be duplicate, just did lookup */
 722         *hash = c;
 723         return 1;
 724 }
 725
 726 /**
 727  * compare a label lowercased
 728  */
 729 static int
 730 label_compare_lower(uint8_t* lab1, uint8_t* lab2, size_t lablen)
 731 {
 732         size_t i;
 733         for(i=0; i<lablen; i++) {
 734                 if(tolower((unsigned char)*lab1) != tolower((unsigned char)*lab2)) {
 735                         if(tolower((unsigned char)*lab1) < tolower((unsigned char)*lab2))
 736                                 return -1;
 737                         return 1;
 738                 }
 739                 lab1++;
 740                 lab2++;
 741         }
 742         return 0;
 743 }
 744
 745 /**
 746  * Compare a hashed name with the owner name of an NSEC3 RRset.
 747  * @param flt: filter with zone name.
 748  * @param hash: the hashed name.
 749  * @param s: rrset with owner name.
 750  * @return true if matches exactly, false if not.
 751  */
 752 static int
 753 nsec3_hash_matches_owner(struct nsec3_filter* flt,
 754         struct nsec3_cached_hash* hash, struct ub_packed_rrset_key* s)
 755 {
 756         uint8_t* nm = s->rk.dname;
 757         /* compare, does hash of name based on params in this NSEC3
 758          * match the owner name of this NSEC3?
 759          * name must be: <hashlength>base32 . zone name
 760          * so; first label must not be root label (not zero length),
 761          * and match the b32 encoded hash length,
 762          * and the label content match the b32 encoded hash
 763          * and the rest must be the zone name.
 764          */
 765         if(hash->b32_len != 0 && (size_t)nm[0] == hash->b32_len &&
 766                 label_compare_lower(nm+1, hash->b32, hash->b32_len) == 0 &&
 767                 query_dname_compare(nm+(size_t)nm[0]+1, flt->zone) == 0) {
 768                 return 1;
 769         }
 770         return 0;
 771 }
 772
 773 /**
 774  * Find matching NSEC3
 775  * Find the NSEC3Record that matches a hash of a name.
 776  * @param env: module environment with temporary region and buffer.
 777  * @param flt: the NSEC3 RR filter, contains zone name and RRs.
 778  * @param ct: cached hashes table.
 779  * @param nm: name to look for.
 780  * @param nmlen: length of name.
 781  * @param rrset: nsec3 that matches is returned here.
 782  * @param rr: rr number in nsec3 rrset that matches.
 783  * @return true if a matching NSEC3 is found, false if not.
 784  */
 785 static int
 786 find_matching_nsec3(struct module_env* env, struct nsec3_filter* flt,
 787         rbtree_t* ct, uint8_t* nm, size_t nmlen,
 788         struct ub_packed_rrset_key** rrset, int* rr)
 789 {
 790         size_t i_rs;
 791         int i_rr;
 792         struct ub_packed_rrset_key* s;
 793         struct nsec3_cached_hash* hash;
 794         int r;
 795
 796         /* this loop skips other-zone and unknown NSEC3s, also non-NSEC3 RRs */
 797         for(s=filter_first(flt, &i_rs, &i_rr); s;
 798                 s=filter_next(flt, &i_rs, &i_rr)) {
 799                 /* get name hashed for this NSEC3 RR */
 800                 r = nsec3_hash_name(ct, env->scratch, env->scratch_buffer,
 801                         s, i_rr, nm, nmlen, &hash);
 802                 if(r == 0) {
 803                         log_err("nsec3: malloc failure");
 804                         break; /* alloc failure */
 805                 } else if(r < 0)
 806                         continue; /* malformed NSEC3 */
 807                 else if(nsec3_hash_matches_owner(flt, hash, s)) {
 808                         *rrset = s; /* rrset with this name */
 809                         *rr = i_rr; /* matches hash with these parameters */
 810                         return 1;
 811                 }
 812         }
 813         *rrset = NULL;
 814         *rr = 0;
 815         return 0;
 816 }
 817
 818 int
 819 nsec3_covers(uint8_t* zone, struct nsec3_cached_hash* hash,
 820         struct ub_packed_rrset_key* rrset, int rr, sldns_buffer* buf)
 821 {
 822         uint8_t* next, *owner;
 823         size_t nextlen;
 824         int len;
 825         if(!nsec3_get_nextowner(rrset, rr, &next, &nextlen))
 826                 return 0; /* malformed RR proves nothing */
 827
 828         /* check the owner name is a hashed value . apex
 829          * base32 encoded values must have equal length.
 830          * hash_value and next hash value must have equal length. */
 831         if(nextlen != hash->hash_len || hash->hash_len==0||hash->b32_len==0||
 832                 (size_t)*rrset->rk.dname != hash->b32_len ||
 833                 query_dname_compare(rrset->rk.dname+1+
 834                         (size_t)*rrset->rk.dname, zone) != 0)
 835                 return 0; /* bad lengths or owner name */
 836
 837         /* This is the "normal case: owner < next and owner < hash < next */
 838         if(label_compare_lower(rrset->rk.dname+1, hash->b32,
 839                 hash->b32_len) < 0 &&
 840                 memcmp(hash->hash, next, nextlen) < 0)
 841                 return 1;
 842
 843         /* convert owner name from text to binary */
 844         sldns_buffer_clear(buf);
 845         owner = sldns_buffer_begin(buf);
 846         len = sldns_b32_pton_extended_hex((char*)rrset->rk.dname+1,
 847                 hash->b32_len, owner, sldns_buffer_limit(buf));
 848         if(len<1)
 849                 return 0; /* bad owner name in some way */
 850         if((size_t)len != hash->hash_len || (size_t)len != nextlen)
 851                 return 0; /* wrong length */
 852
 853         /* this is the end of zone case: next <= owner &&
 854          *      (hash > owner || hash < next)
 855          * this also covers the only-apex case of next==owner.
 856          */
 857         if(memcmp(next, owner, nextlen) <= 0 &&
 858                 ( memcmp(hash->hash, owner, nextlen) > 0 ||
 859                   memcmp(hash->hash, next, nextlen) < 0)) {
 860                 return 1;
 861         }
 862         return 0;
 863 }
 864
 865 /**
 866  * findCoveringNSEC3
 867  * Given a name, find a covering NSEC3 from among a list of NSEC3s.
 868  *
 869  * @param env: module environment with temporary region and buffer.
 870  * @param flt: the NSEC3 RR filter, contains zone name and RRs.
 871  * @param ct: cached hashes table.
 872  * @param nm: name to check if covered.
 873  * @param nmlen: length of name.
 874  * @param rrset: covering NSEC3 rrset is returned here.
 875  * @param rr: rr of cover is returned here.
 876  * @return true if a covering NSEC3 is found, false if not.
 877  */
 878 static int
 879 find_covering_nsec3(struct module_env* env, struct nsec3_filter* flt,
 880         rbtree_t* ct, uint8_t* nm, size_t nmlen,
 881         struct ub_packed_rrset_key** rrset, int* rr)
 882 {
 883         size_t i_rs;
 884         int i_rr;
 885         struct ub_packed_rrset_key* s;
 886         struct nsec3_cached_hash* hash;
 887         int r;
 888
 889         /* this loop skips other-zone and unknown NSEC3s, also non-NSEC3 RRs */
 890         for(s=filter_first(flt, &i_rs, &i_rr); s;
 891                 s=filter_next(flt, &i_rs, &i_rr)) {
 892                 /* get name hashed for this NSEC3 RR */
 893                 r = nsec3_hash_name(ct, env->scratch, env->scratch_buffer,
 894                         s, i_rr, nm, nmlen, &hash);
 895                 if(r == 0) {
 896                         log_err("nsec3: malloc failure");
 897                         break; /* alloc failure */
 898                 } else if(r < 0)
 899                         continue; /* malformed NSEC3 */
 900                 else if(nsec3_covers(flt->zone, hash, s, i_rr,
 901                         env->scratch_buffer)) {
 902                         *rrset = s; /* rrset with this name */
 903                         *rr = i_rr; /* covers hash with these parameters */
 904                         return 1;
 905                 }
 906         }
 907         *rrset = NULL;
 908         *rr = 0;
 909         return 0;
 910 }
 911
 912 /**
 913  * findClosestEncloser
 914  * Given a name and a list of NSEC3s, find the candidate closest encloser.
 915  * This will be the first ancestor of 'name' (including itself) to have a
 916  * matching NSEC3 RR.
 917  * @param env: module environment with temporary region and buffer.
 918  * @param flt: the NSEC3 RR filter, contains zone name and RRs.
 919  * @param ct: cached hashes table.
 920  * @param qinfo: query that is verified for.
 921  * @param ce: closest encloser information is returned in here.
 922  * @return true if a closest encloser candidate is found, false if not.
 923  */
 924 static int
 925 nsec3_find_closest_encloser(struct module_env* env, struct nsec3_filter* flt,
 926         rbtree_t* ct, struct query_info* qinfo, struct ce_response* ce)
 927 {
 928         uint8_t* nm = qinfo->qname;
 929         size_t nmlen = qinfo->qname_len;
 930
 931         /* This scans from longest name to shortest, so the first match
 932          * we find is the only viable candidate. */
 933
 934         /* (David:) FIXME: modify so that the NSEC3 matching the zone apex need
 935          * not be present. (Mark Andrews idea).
 936          * (Wouter:) But make sure you check for DNAME bit in zone apex,
 937          * if the NSEC3 you find is the only NSEC3 in the zone, then this
 938          * may be the case. */
 939
 940         while(dname_subdomain_c(nm, flt->zone)) {
 941                 if(find_matching_nsec3(env, flt, ct, nm, nmlen,
 942                         &ce->ce_rrset, &ce->ce_rr)) {
 943                         ce->ce = nm;
 944                         ce->ce_len = nmlen;
 945                         return 1;
 946                 }
 947                 dname_remove_label(&nm, &nmlen);
 948         }
 949         return 0;
 950 }
 951
 952 /**
 953  * Given a qname and its proven closest encloser, calculate the "next
 954  * closest" name. Basically, this is the name that is one label longer than
 955  * the closest encloser that is still a subdomain of qname.
 956  *
 957  * @param qname: query name.
 958  * @param qnamelen: length of qname.
 959  * @param ce: closest encloser
 960  * @param nm: result name.
 961  * @param nmlen: length of nm.
 962  */
 963 static void
 964 next_closer(uint8_t* qname, size_t qnamelen, uint8_t* ce,
 965         uint8_t** nm, size_t* nmlen)
 966 {
 967         int strip = dname_count_labels(qname) - dname_count_labels(ce) -1;
 968         *nm = qname;
 969         *nmlen = qnamelen;
 970         if(strip>0)
 971                 dname_remove_labels(nm, nmlen, strip);
 972 }
 973
 974 /**
 975  * proveClosestEncloser
 976  * Given a List of nsec3 RRs, find and prove the closest encloser to qname.
 977  * @param env: module environment with temporary region and buffer.
 978  * @param flt: the NSEC3 RR filter, contains zone name and RRs.
 979  * @param ct: cached hashes table.
 980  * @param qinfo: query that is verified for.
 981  * @param prove_does_not_exist: If true, then if the closest encloser
 982  *      turns out to be qname, then null is returned.
 983  *      If set true, and the return value is true, then you can be
 984  *      certain that the ce.nc_rrset and ce.nc_rr are set properly.
 985  * @param ce: closest encloser information is returned in here.
 986  * @return bogus if no closest encloser could be proven.
 987  *      secure if a closest encloser could be proven, ce is set.
 988  *      insecure if the closest-encloser candidate turns out to prove
 989  *              that an insecure delegation exists above the qname.
 990  */
 991 static enum sec_status
 992 nsec3_prove_closest_encloser(struct module_env* env, struct nsec3_filter* flt,
 993         rbtree_t* ct, struct query_info* qinfo, int prove_does_not_exist,
 994         struct ce_response* ce)
 995 {
 996         uint8_t* nc;
 997         size_t nc_len;
 998         /* robust: clean out ce, in case it gets abused later */
 999         memset(ce, 0, sizeof(*ce));
1000
1001         if(!nsec3_find_closest_encloser(env, flt, ct, qinfo, ce)) {
1002                 verbose(VERB_ALGO, "nsec3 proveClosestEncloser: could "
1003                         "not find a candidate for the closest encloser.");
1004                 return sec_status_bogus;
1005         }
1006         log_nametypeclass(VERB_ALGO, "ce candidate", ce->ce, 0, 0);
1007
1008         if(query_dname_compare(ce->ce, qinfo->qname) == 0) {
1009                 if(prove_does_not_exist) {
1010                         verbose(VERB_ALGO, "nsec3 proveClosestEncloser: "
1011                                 "proved that qname existed, bad");
1012                         return sec_status_bogus;
1013                 }
1014                 /* otherwise, we need to nothing else to prove that qname
1015                  * is its own closest encloser. */
1016                 return sec_status_secure;
1017         }
1018
1019         /* If the closest encloser is actually a delegation, then the
1020          * response should have been a referral. If it is a DNAME, then
1021          * it should have been a DNAME response. */
1022         if(nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_NS) &&
1023                 !nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_SOA)) {
1024                 if(!nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_DS)) {
1025                         verbose(VERB_ALGO, "nsec3 proveClosestEncloser: "
1026                                 "closest encloser is insecure delegation");
1027                         return sec_status_insecure;
1028                 }
1029                 verbose(VERB_ALGO, "nsec3 proveClosestEncloser: closest "
1030                         "encloser was a delegation, bad");
1031                 return sec_status_bogus;
1032         }
1033         if(nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_DNAME)) {
1034                 verbose(VERB_ALGO, "nsec3 proveClosestEncloser: closest "
1035                         "encloser was a DNAME, bad");
1036                 return sec_status_bogus;
1037         }
1038
1039         /* Otherwise, we need to show that the next closer name is covered. */
1040         next_closer(qinfo->qname, qinfo->qname_len, ce->ce, &nc, &nc_len);
1041         if(!find_covering_nsec3(env, flt, ct, nc, nc_len,
1042                 &ce->nc_rrset, &ce->nc_rr)) {
1043                 verbose(VERB_ALGO, "nsec3: Could not find proof that the "
1044                           "candidate encloser was the closest encloser");
1045                 return sec_status_bogus;
1046         }
1047         return sec_status_secure;
1048 }
1049
1050 /** allocate a wildcard for the closest encloser */
1051 static uint8_t*
1052 nsec3_ce_wildcard(struct regional* region, uint8_t* ce, size_t celen,
1053         size_t* len)
1054 {
1055         uint8_t* nm;
1056         if(celen > LDNS_MAX_DOMAINLEN - 2)
1057                 return 0; /* too long */
1058         nm = (uint8_t*)regional_alloc(region, celen+2);
1059         if(!nm) {
1060                 log_err("nsec3 wildcard: out of memory");
1061                 return 0; /* alloc failure */
1062         }
1063         nm[0] = 1;
1064         nm[1] = (uint8_t)'*'; /* wildcard label */
1065         memmove(nm+2, ce, celen);
1066         *len = celen+2;
1067         return nm;
1068 }
1069
1070 /** Do the name error proof */
1071 static enum sec_status
1072 nsec3_do_prove_nameerror(struct module_env* env, struct nsec3_filter* flt,
1073         rbtree_t* ct, struct query_info* qinfo)
1074 {
1075         struct ce_response ce;
1076         uint8_t* wc;
1077         size_t wclen;
1078         struct ub_packed_rrset_key* wc_rrset;
1079         int wc_rr;
1080         enum sec_status sec;
1081
1082         /* First locate and prove the closest encloser to qname. We will
1083          * use the variant that fails if the closest encloser turns out
1084          * to be qname. */
1085         sec = nsec3_prove_closest_encloser(env, flt, ct, qinfo, 1, &ce);
1086         if(sec != sec_status_secure) {
1087                 if(sec == sec_status_bogus)
1088                         verbose(VERB_ALGO, "nsec3 nameerror proof: failed "
1089                                 "to prove a closest encloser");
1090                 else    verbose(VERB_ALGO, "nsec3 nameerror proof: closest "
1091                                 "nsec3 is an insecure delegation");
1092                 return sec;
1093         }
1094         log_nametypeclass(VERB_ALGO, "nsec3 namerror: proven ce=", ce.ce,0,0);
1095
1096         /* At this point, we know that qname does not exist. Now we need
1097          * to prove that the wildcard does not exist. */
1098         log_assert(ce.ce);
1099         wc = nsec3_ce_wildcard(env->scratch, ce.ce, ce.ce_len, &wclen);
1100         if(!wc || !find_covering_nsec3(env, flt, ct, wc, wclen,
1101                 &wc_rrset, &wc_rr)) {
1102                 verbose(VERB_ALGO, "nsec3 nameerror proof: could not prove "
1103                         "that the applicable wildcard did not exist.");
1104                 return sec_status_bogus;
1105         }
1106
1107         if(ce.nc_rrset && nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1108                 verbose(VERB_ALGO, "nsec3 nameerror proof: nc has optout");
1109                 return sec_status_insecure;
1110         }
1111         return sec_status_secure;
1112 }
1113
1114 enum sec_status
1115 nsec3_prove_nameerror(struct module_env* env, struct val_env* ve,
1116         struct ub_packed_rrset_key** list, size_t num,
1117         struct query_info* qinfo, struct key_entry_key* kkey)
1118 {
1119         rbtree_t ct;
1120         struct nsec3_filter flt;
1121
1122         if(!list || num == 0 || !kkey || !key_entry_isgood(kkey))
1123                 return sec_status_bogus; /* no valid NSEC3s, bogus */
1124         rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */
1125         filter_init(&flt, list, num, qinfo); /* init RR iterator */
1126         if(!flt.zone)
1127                 return sec_status_bogus; /* no RRs */
1128         if(nsec3_iteration_count_high(ve, &flt, kkey))
1129                 return sec_status_insecure; /* iteration count too high */
1130         log_nametypeclass(VERB_ALGO, "start nsec3 nameerror proof, zone",
1131                 flt.zone, 0, 0);
1132         return nsec3_do_prove_nameerror(env, &flt, &ct, qinfo);
1133 }
1134
1135 /*
1136  * No code to handle qtype=NSEC3 specially.
1137  * This existed in early drafts, but was later (-05) removed.
1138  */
1139
1140 /** Do the nodata proof */
1141 static enum sec_status
1142 nsec3_do_prove_nodata(struct module_env* env, struct nsec3_filter* flt,
1143         rbtree_t* ct, struct query_info* qinfo)
1144 {
1145         struct ce_response ce;
1146         uint8_t* wc;
1147         size_t wclen;
1148         struct ub_packed_rrset_key* rrset;
1149         int rr;
1150         enum sec_status sec;
1151
1152         if(find_matching_nsec3(env, flt, ct, qinfo->qname, qinfo->qname_len,
1153                 &rrset, &rr)) {
1154                 /* cases 1 and 2 */
1155                 if(nsec3_has_type(rrset, rr, qinfo->qtype)) {
1156                         verbose(VERB_ALGO, "proveNodata: Matching NSEC3 "
1157                                 "proved that type existed, bogus");
1158                         return sec_status_bogus;
1159                 } else if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_CNAME)) {
1160                         verbose(VERB_ALGO, "proveNodata: Matching NSEC3 "
1161                                 "proved that a CNAME existed, bogus");
1162                         return sec_status_bogus;
1163                 }
1164
1165                 /*
1166                  * If type DS: filter_init zone find already found a parent
1167                  *   zone, so this nsec3 is from a parent zone.
1168                  *   o can be not a delegation (unusual query for normal name,
1169                  *      no DS anyway, but we can verify that).
1170                  *   o can be a delegation (which is the usual DS check).
1171                  *   o may not have the SOA bit set (only the top of the
1172                  *      zone, which must have been above the name, has that).
1173                  *      Except for the root; which is checked by itself.
1174                  *
1175                  * If not type DS: matching nsec3 must not be a delegation.
1176                  */
1177                 if(qinfo->qtype == LDNS_RR_TYPE_DS && qinfo->qname_len != 1
1178                         && nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA) &&
1179                         !dname_is_root(qinfo->qname)) {
1180                         verbose(VERB_ALGO, "proveNodata: apex NSEC3 "
1181                                 "abused for no DS proof, bogus");
1182                         return sec_status_bogus;
1183                 } else if(qinfo->qtype != LDNS_RR_TYPE_DS &&
1184                         nsec3_has_type(rrset, rr, LDNS_RR_TYPE_NS) &&
1185                         !nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA)) {
1186                         if(!nsec3_has_type(rrset, rr, LDNS_RR_TYPE_DS)) {
1187                                 verbose(VERB_ALGO, "proveNodata: matching "
1188                                         "NSEC3 is insecure delegation");
1189                                 return sec_status_insecure;
1190                         }
1191                         verbose(VERB_ALGO, "proveNodata: matching "
1192                                 "NSEC3 is a delegation, bogus");
1193                         return sec_status_bogus;
1194                 }
1195                 return sec_status_secure;
1196         }
1197
1198         /* For cases 3 - 5, we need the proven closest encloser, and it
1199          * can't match qname. Although, at this point, we know that it
1200          * won't since we just checked that. */
1201         sec = nsec3_prove_closest_encloser(env, flt, ct, qinfo, 1, &ce);
1202         if(sec == sec_status_bogus) {
1203                 verbose(VERB_ALGO, "proveNodata: did not match qname, "
1204                           "nor found a proven closest encloser.");
1205                 return sec_status_bogus;
1206         } else if(sec==sec_status_insecure && qinfo->qtype!=LDNS_RR_TYPE_DS){
1207                 verbose(VERB_ALGO, "proveNodata: closest nsec3 is insecure "
1208                           "delegation.");
1209                 return sec_status_insecure;
1210         }
1211
1212         /* Case 3: removed */
1213
1214         /* Case 4: */
1215         log_assert(ce.ce);
1216         wc = nsec3_ce_wildcard(env->scratch, ce.ce, ce.ce_len, &wclen);
1217         if(wc && find_matching_nsec3(env, flt, ct, wc, wclen, &rrset, &rr)) {
1218                 /* found wildcard */
1219                 if(nsec3_has_type(rrset, rr, qinfo->qtype)) {
1220                         verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1221                                 "wildcard had qtype, bogus");
1222                         return sec_status_bogus;
1223                 } else if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_CNAME)) {
1224                         verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1225                                 "wildcard had a CNAME, bogus");
1226                         return sec_status_bogus;
1227                 }
1228                 if(qinfo->qtype == LDNS_RR_TYPE_DS && qinfo->qname_len != 1
1229                         && nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA)) {
1230                         verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1231                                 "wildcard for no DS proof has a SOA, bogus");
1232                         return sec_status_bogus;
1233                 } else if(qinfo->qtype != LDNS_RR_TYPE_DS &&
1234                         nsec3_has_type(rrset, rr, LDNS_RR_TYPE_NS) &&
1235                         !nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA)) {
1236                         verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1237                                 "wilcard is a delegation, bogus");
1238                         return sec_status_bogus;
1239                 }
1240                 /* everything is peachy keen, except for optout spans */
1241                 if(ce.nc_rrset && nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1242                         verbose(VERB_ALGO, "nsec3 nodata proof: matching "
1243                                 "wildcard is in optout range, insecure");
1244                         return sec_status_insecure;
1245                 }
1246                 return sec_status_secure;
1247         }
1248
1249         /* Case 5: */
1250         /* Due to forwarders, cnames, and other collating effects, we
1251          * can see the ordinary unsigned data from a zone beneath an
1252          * insecure delegation under an optout here */
1253         if(!ce.nc_rrset) {
1254                 verbose(VERB_ALGO, "nsec3 nodata proof: no next closer nsec3");
1255                 return sec_status_bogus;
1256         }
1257
1258         /* We need to make sure that the covering NSEC3 is opt-out. */
1259         log_assert(ce.nc_rrset);
1260         if(!nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1261                 if(qinfo->qtype == LDNS_RR_TYPE_DS)
1262                   verbose(VERB_ALGO, "proveNodata: covering NSEC3 was not "
1263                         "opt-out in an opt-out DS NOERROR/NODATA case.");
1264                 else verbose(VERB_ALGO, "proveNodata: could not find matching "
1265                         "NSEC3, nor matching wildcard, nor optout NSEC3 "
1266                         "-- no more options, bogus.");
1267                 return sec_status_bogus;
1268         }
1269         /* RFC5155 section 9.2: if nc has optout then no AD flag set */
1270         return sec_status_insecure;
1271 }
1272
1273 enum sec_status
1274 nsec3_prove_nodata(struct module_env* env, struct val_env* ve,
1275         struct ub_packed_rrset_key** list, size_t num,
1276         struct query_info* qinfo, struct key_entry_key* kkey)
1277 {
1278         rbtree_t ct;
1279         struct nsec3_filter flt;
1280
1281         if(!list || num == 0 || !kkey || !key_entry_isgood(kkey))
1282                 return sec_status_bogus; /* no valid NSEC3s, bogus */
1283         rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */
1284         filter_init(&flt, list, num, qinfo); /* init RR iterator */
1285         if(!flt.zone)
1286                 return sec_status_bogus; /* no RRs */
1287         if(nsec3_iteration_count_high(ve, &flt, kkey))
1288                 return sec_status_insecure; /* iteration count too high */
1289         return nsec3_do_prove_nodata(env, &flt, &ct, qinfo);
1290 }
1291
1292 enum sec_status
1293 nsec3_prove_wildcard(struct module_env* env, struct val_env* ve,
1294         struct ub_packed_rrset_key** list, size_t num,
1295         struct query_info* qinfo, struct key_entry_key* kkey, uint8_t* wc)
1296 {
1297         rbtree_t ct;
1298         struct nsec3_filter flt;
1299         struct ce_response ce;
1300         uint8_t* nc;
1301         size_t nc_len;
1302         size_t wclen;
1303         (void)dname_count_size_labels(wc, &wclen);
1304
1305         if(!list || num == 0 || !kkey || !key_entry_isgood(kkey))
1306                 return sec_status_bogus; /* no valid NSEC3s, bogus */
1307         rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */
1308         filter_init(&flt, list, num, qinfo); /* init RR iterator */
1309         if(!flt.zone)
1310                 return sec_status_bogus; /* no RRs */
1311         if(nsec3_iteration_count_high(ve, &flt, kkey))
1312                 return sec_status_insecure; /* iteration count too high */
1313
1314         /* We know what the (purported) closest encloser is by just
1315          * looking at the supposed generating wildcard.
1316          * The *. has already been removed from the wc name.
1317          */
1318         memset(&ce, 0, sizeof(ce));
1319         ce.ce = wc;
1320         ce.ce_len = wclen;
1321
1322         /* Now we still need to prove that the original data did not exist.
1323          * Otherwise, we need to show that the next closer name is covered. */
1324         next_closer(qinfo->qname, qinfo->qname_len, ce.ce, &nc, &nc_len);
1325         if(!find_covering_nsec3(env, &flt, &ct, nc, nc_len,
1326                 &ce.nc_rrset, &ce.nc_rr)) {
1327                 verbose(VERB_ALGO, "proveWildcard: did not find a covering "
1328                         "NSEC3 that covered the next closer name.");
1329                 return sec_status_bogus;
1330         }
1331         if(ce.nc_rrset && nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1332                 verbose(VERB_ALGO, "proveWildcard: NSEC3 optout");
1333                 return sec_status_insecure;
1334         }
1335         return sec_status_secure;
1336 }
1337
1338 /** test if list is all secure */
1339 static int
1340 list_is_secure(struct module_env* env, struct val_env* ve,
1341         struct ub_packed_rrset_key** list, size_t num,
1342         struct key_entry_key* kkey, char** reason)
1343 {
1344         struct packed_rrset_data* d;
1345         size_t i;
1346         for(i=0; i<num; i++) {
1347                 d = (struct packed_rrset_data*)list[i]->entry.data;
1348                 if(list[i]->rk.type != htons(LDNS_RR_TYPE_NSEC3))
1349                         continue;
1350                 if(d->security == sec_status_secure)
1351                         continue;
1352                 rrset_check_sec_status(env->rrset_cache, list[i], *env->now);
1353                 if(d->security == sec_status_secure)
1354                         continue;
1355                 d->security = val_verify_rrset_entry(env, ve, list[i], kkey,
1356                         reason);
1357                 if(d->security != sec_status_secure) {
1358                         verbose(VERB_ALGO, "NSEC3 did not verify");
1359                         return 0;
1360                 }
1361                 rrset_update_sec_status(env->rrset_cache, list[i], *env->now);
1362         }
1363         return 1;
1364 }
1365
1366 enum sec_status
1367 nsec3_prove_nods(struct module_env* env, struct val_env* ve,
1368         struct ub_packed_rrset_key** list, size_t num,
1369         struct query_info* qinfo, struct key_entry_key* kkey, char** reason)
1370 {
1371         rbtree_t ct;
1372         struct nsec3_filter flt;
1373         struct ce_response ce;
1374         struct ub_packed_rrset_key* rrset;
1375         int rr;
1376         log_assert(qinfo->qtype == LDNS_RR_TYPE_DS);
1377
1378         if(!list || num == 0 || !kkey || !key_entry_isgood(kkey)) {
1379                 *reason = "no valid NSEC3s";
1380                 return sec_status_bogus; /* no valid NSEC3s, bogus */
1381         }
1382         if(!list_is_secure(env, ve, list, num, kkey, reason))
1383                 return sec_status_bogus; /* not all NSEC3 records secure */
1384         rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */
1385         filter_init(&flt, list, num, qinfo); /* init RR iterator */
1386         if(!flt.zone) {
1387                 *reason = "no NSEC3 records";
1388                 return sec_status_bogus; /* no RRs */
1389         }
1390         if(nsec3_iteration_count_high(ve, &flt, kkey))
1391                 return sec_status_insecure; /* iteration count too high */
1392
1393         /* Look for a matching NSEC3 to qname -- this is the normal
1394          * NODATA case. */
1395         if(find_matching_nsec3(env, &flt, &ct, qinfo->qname, qinfo->qname_len,
1396                 &rrset, &rr)) {
1397                 /* If the matching NSEC3 has the SOA bit set, it is from
1398                  * the wrong zone (the child instead of the parent). If
1399                  * it has the DS bit set, then we were lied to. */
1400                 if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA) &&
1401                         qinfo->qname_len != 1) {
1402                         verbose(VERB_ALGO, "nsec3 provenods: NSEC3 is from"
1403                                 " child zone, bogus");
1404                         *reason = "NSEC3 from child zone";
1405                         return sec_status_bogus;
1406                 } else if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_DS)) {
1407                         verbose(VERB_ALGO, "nsec3 provenods: NSEC3 has qtype"
1408                                 " DS, bogus");
1409                         *reason = "NSEC3 has DS in bitmap";
1410                         return sec_status_bogus;
1411                 }
1412                 /* If the NSEC3 RR doesn't have the NS bit set, then
1413                  * this wasn't a delegation point. */
1414                 if(!nsec3_has_type(rrset, rr, LDNS_RR_TYPE_NS))
1415                         return sec_status_indeterminate;
1416                 /* Otherwise, this proves no DS. */
1417                 return sec_status_secure;
1418         }
1419
1420         /* Otherwise, we are probably in the opt-out case. */
1421         if(nsec3_prove_closest_encloser(env, &flt, &ct, qinfo, 1, &ce)
1422                 != sec_status_secure) {
1423                 /* an insecure delegation *above* the qname does not prove
1424                  * anything about this qname exactly, and bogus is bogus */
1425                 verbose(VERB_ALGO, "nsec3 provenods: did not match qname, "
1426                           "nor found a proven closest encloser.");
1427                 *reason = "no NSEC3 closest encloser";
1428                 return sec_status_bogus;
1429         }
1430
1431         /* robust extra check */
1432         if(!ce.nc_rrset) {
1433                 verbose(VERB_ALGO, "nsec3 nods proof: no next closer nsec3");
1434                 *reason = "no NSEC3 next closer";
1435                 return sec_status_bogus;
1436         }
1437
1438         /* we had the closest encloser proof, then we need to check that the
1439          * covering NSEC3 was opt-out -- the proveClosestEncloser step already
1440          * checked to see if the closest encloser was a delegation or DNAME.
1441          */
1442         log_assert(ce.nc_rrset);
1443         if(!nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) {
1444                 verbose(VERB_ALGO, "nsec3 provenods: covering NSEC3 was not "
1445                         "opt-out in an opt-out DS NOERROR/NODATA case.");
1446                 *reason = "covering NSEC3 was not opt-out in an opt-out "
1447                         "DS NOERROR/NODATA case";
1448                 return sec_status_bogus;
1449         }
1450         /* RFC5155 section 9.2: if nc has optout then no AD flag set */
1451         return sec_status_insecure;
1452 }
1453
1454 enum sec_status
1455 nsec3_prove_nxornodata(struct module_env* env, struct val_env* ve,
1456         struct ub_packed_rrset_key** list, size_t num,
1457         struct query_info* qinfo, struct key_entry_key* kkey, int* nodata)
1458 {
1459         enum sec_status sec, secnx;
1460         rbtree_t ct;
1461         struct nsec3_filter flt;
1462         *nodata = 0;
1463
1464         if(!list || num == 0 || !kkey || !key_entry_isgood(kkey))
1465                 return sec_status_bogus; /* no valid NSEC3s, bogus */
1466         rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */
1467         filter_init(&flt, list, num, qinfo); /* init RR iterator */
1468         if(!flt.zone)
1469                 return sec_status_bogus; /* no RRs */
1470         if(nsec3_iteration_count_high(ve, &flt, kkey))
1471                 return sec_status_insecure; /* iteration count too high */
1472
1473         /* try nxdomain and nodata after another, while keeping the
1474          * hash cache intact */
1475
1476         secnx = nsec3_do_prove_nameerror(env, &flt, &ct, qinfo);
1477         if(secnx==sec_status_secure)
1478                 return sec_status_secure;
1479         sec = nsec3_do_prove_nodata(env, &flt, &ct, qinfo);
1480         if(sec==sec_status_secure) {
1481                 *nodata = 1;
1482         } else if(sec == sec_status_insecure) {
1483                 *nodata = 1;
1484         } else if(secnx == sec_status_insecure) {
1485                 sec = sec_status_insecure;
1486         }
1487         return sec;
1488 }