contrib/unbound/validator/val_nsec3.c

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