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