contrib/unbound/validator/val_nsec3.c

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