1238106Sdes/* 2292206Sdes * validator/val_nsec3.c - validator NSEC3 denial of existence functions. 3238106Sdes * 4238106Sdes * Copyright (c) 2007, NLnet Labs. All rights reserved. 5238106Sdes * 6238106Sdes * This software is open source. 7238106Sdes * 8238106Sdes * Redistribution and use in source and binary forms, with or without 9238106Sdes * modification, are permitted provided that the following conditions 10238106Sdes * are met: 11238106Sdes * 12238106Sdes * Redistributions of source code must retain the above copyright notice, 13238106Sdes * this list of conditions and the following disclaimer. 14238106Sdes * 15238106Sdes * Redistributions in binary form must reproduce the above copyright notice, 16238106Sdes * this list of conditions and the following disclaimer in the documentation 17238106Sdes * and/or other materials provided with the distribution. 18238106Sdes * 19238106Sdes * Neither the name of the NLNET LABS nor the names of its contributors may 20238106Sdes * be used to endorse or promote products derived from this software without 21238106Sdes * specific prior written permission. 22238106Sdes * 23238106Sdes * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24266114Sdes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25266114Sdes * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26266114Sdes * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27266114Sdes * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28266114Sdes * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29266114Sdes * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30266114Sdes * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31266114Sdes * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32266114Sdes * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33266114Sdes * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34238106Sdes */ 35238106Sdes 36238106Sdes/** 37238106Sdes * \file 38238106Sdes * 39238106Sdes * This file contains helper functions for the validator module. 40238106Sdes * The functions help with NSEC3 checking, the different NSEC3 proofs 41292206Sdes * for denial of existence, and proofs for presence of types. 42238106Sdes */ 43238106Sdes#include "config.h" 44238106Sdes#include <ctype.h> 45238106Sdes#include "validator/val_nsec3.h" 46292206Sdes#include "validator/val_secalgo.h" 47238106Sdes#include "validator/validator.h" 48238106Sdes#include "validator/val_kentry.h" 49238106Sdes#include "services/cache/rrset.h" 50238106Sdes#include "util/regional.h" 51238106Sdes#include "util/rbtree.h" 52238106Sdes#include "util/module.h" 53238106Sdes#include "util/net_help.h" 54238106Sdes#include "util/data/packed_rrset.h" 55238106Sdes#include "util/data/dname.h" 56238106Sdes#include "util/data/msgreply.h" 57238106Sdes/* we include nsec.h for the bitmap_has_type function */ 58238106Sdes#include "validator/val_nsec.h" 59287917Sdes#include "sldns/sbuffer.h" 60238106Sdes 61238106Sdes/** 62238106Sdes * This function we get from ldns-compat or from base system 63238106Sdes * it returns the number of data bytes stored at the target, or <0 on error. 64238106Sdes */ 65266114Sdesint sldns_b32_ntop_extended_hex(uint8_t const *src, size_t srclength, 66238106Sdes char *target, size_t targsize); 67238106Sdes/** 68238106Sdes * This function we get from ldns-compat or from base system 69238106Sdes * it returns the number of data bytes stored at the target, or <0 on error. 70238106Sdes */ 71266114Sdesint sldns_b32_pton_extended_hex(char const *src, size_t hashed_owner_str_len, 72238106Sdes uint8_t *target, size_t targsize); 73238106Sdes 74238106Sdes/** 75238106Sdes * Closest encloser (ce) proof results 76238106Sdes * Contains the ce and the next-closer (nc) proof. 77238106Sdes */ 78238106Sdesstruct ce_response { 79238106Sdes /** the closest encloser name */ 80238106Sdes uint8_t* ce; 81238106Sdes /** length of ce */ 82238106Sdes size_t ce_len; 83238106Sdes /** NSEC3 record that proved ce. rrset */ 84238106Sdes struct ub_packed_rrset_key* ce_rrset; 85238106Sdes /** NSEC3 record that proved ce. rr number */ 86238106Sdes int ce_rr; 87238106Sdes /** NSEC3 record that proved nc. rrset */ 88238106Sdes struct ub_packed_rrset_key* nc_rrset; 89238106Sdes /** NSEC3 record that proved nc. rr*/ 90238106Sdes int nc_rr; 91238106Sdes}; 92238106Sdes 93238106Sdes/** 94238106Sdes * Filter conditions for NSEC3 proof 95238106Sdes * Used to iterate over the applicable NSEC3 RRs. 96238106Sdes */ 97238106Sdesstruct nsec3_filter { 98238106Sdes /** Zone name, only NSEC3 records for this zone are considered */ 99238106Sdes uint8_t* zone; 100238106Sdes /** length of the zonename */ 101238106Sdes size_t zone_len; 102238106Sdes /** the list of NSEC3s to filter; array */ 103238106Sdes struct ub_packed_rrset_key** list; 104238106Sdes /** number of rrsets in list */ 105238106Sdes size_t num; 106238106Sdes /** class of records for the NSEC3, only this class applies */ 107238106Sdes uint16_t fclass; 108238106Sdes}; 109238106Sdes 110238106Sdes/** return number of rrs in an rrset */ 111238106Sdesstatic size_t 112238106Sdesrrset_get_count(struct ub_packed_rrset_key* rrset) 113238106Sdes{ 114238106Sdes struct packed_rrset_data* d = (struct packed_rrset_data*) 115238106Sdes rrset->entry.data; 116238106Sdes if(!d) return 0; 117238106Sdes return d->count; 118238106Sdes} 119238106Sdes 120238106Sdes/** return if nsec3 RR has unknown flags */ 121238106Sdesstatic int 122238106Sdesnsec3_unknown_flags(struct ub_packed_rrset_key* rrset, int r) 123238106Sdes{ 124238106Sdes struct packed_rrset_data* d = (struct packed_rrset_data*) 125238106Sdes rrset->entry.data; 126238106Sdes log_assert(d && r < (int)d->count); 127238106Sdes if(d->rr_len[r] < 2+2) 128238106Sdes return 0; /* malformed */ 129238106Sdes return (int)(d->rr_data[r][2+1] & NSEC3_UNKNOWN_FLAGS); 130238106Sdes} 131238106Sdes 132238106Sdesint 133238106Sdesnsec3_has_optout(struct ub_packed_rrset_key* rrset, int r) 134238106Sdes{ 135238106Sdes struct packed_rrset_data* d = (struct packed_rrset_data*) 136238106Sdes rrset->entry.data; 137238106Sdes log_assert(d && r < (int)d->count); 138238106Sdes if(d->rr_len[r] < 2+2) 139238106Sdes return 0; /* malformed */ 140238106Sdes return (int)(d->rr_data[r][2+1] & NSEC3_OPTOUT); 141238106Sdes} 142238106Sdes 143238106Sdes/** return nsec3 RR algorithm */ 144238106Sdesstatic int 145238106Sdesnsec3_get_algo(struct ub_packed_rrset_key* rrset, int r) 146238106Sdes{ 147238106Sdes struct packed_rrset_data* d = (struct packed_rrset_data*) 148238106Sdes rrset->entry.data; 149238106Sdes log_assert(d && r < (int)d->count); 150238106Sdes if(d->rr_len[r] < 2+1) 151238106Sdes return 0; /* malformed */ 152238106Sdes return (int)(d->rr_data[r][2+0]); 153238106Sdes} 154238106Sdes 155238106Sdes/** return if nsec3 RR has known algorithm */ 156238106Sdesstatic int 157238106Sdesnsec3_known_algo(struct ub_packed_rrset_key* rrset, int r) 158238106Sdes{ 159238106Sdes struct packed_rrset_data* d = (struct packed_rrset_data*) 160238106Sdes rrset->entry.data; 161238106Sdes log_assert(d && r < (int)d->count); 162238106Sdes if(d->rr_len[r] < 2+1) 163238106Sdes return 0; /* malformed */ 164238106Sdes switch(d->rr_data[r][2+0]) { 165238106Sdes case NSEC3_HASH_SHA1: 166238106Sdes return 1; 167238106Sdes } 168238106Sdes return 0; 169238106Sdes} 170238106Sdes 171238106Sdes/** return nsec3 RR iteration count */ 172238106Sdesstatic size_t 173238106Sdesnsec3_get_iter(struct ub_packed_rrset_key* rrset, int r) 174238106Sdes{ 175238106Sdes uint16_t i; 176238106Sdes struct packed_rrset_data* d = (struct packed_rrset_data*) 177238106Sdes rrset->entry.data; 178238106Sdes log_assert(d && r < (int)d->count); 179238106Sdes if(d->rr_len[r] < 2+4) 180238106Sdes return 0; /* malformed */ 181238106Sdes memmove(&i, d->rr_data[r]+2+2, sizeof(i)); 182238106Sdes i = ntohs(i); 183238106Sdes return (size_t)i; 184238106Sdes} 185238106Sdes 186238106Sdes/** return nsec3 RR salt */ 187238106Sdesstatic int 188238106Sdesnsec3_get_salt(struct ub_packed_rrset_key* rrset, int r, 189238106Sdes uint8_t** salt, size_t* saltlen) 190238106Sdes{ 191238106Sdes struct packed_rrset_data* d = (struct packed_rrset_data*) 192238106Sdes rrset->entry.data; 193238106Sdes log_assert(d && r < (int)d->count); 194238106Sdes if(d->rr_len[r] < 2+5) { 195238106Sdes *salt = 0; 196238106Sdes *saltlen = 0; 197238106Sdes return 0; /* malformed */ 198238106Sdes } 199238106Sdes *saltlen = (size_t)d->rr_data[r][2+4]; 200238106Sdes if(d->rr_len[r] < 2+5+(size_t)*saltlen) { 201238106Sdes *salt = 0; 202238106Sdes *saltlen = 0; 203238106Sdes return 0; /* malformed */ 204238106Sdes } 205238106Sdes *salt = d->rr_data[r]+2+5; 206238106Sdes return 1; 207238106Sdes} 208238106Sdes 209238106Sdesint nsec3_get_params(struct ub_packed_rrset_key* rrset, int r, 210238106Sdes int* algo, size_t* iter, uint8_t** salt, size_t* saltlen) 211238106Sdes{ 212238106Sdes if(!nsec3_known_algo(rrset, r) || nsec3_unknown_flags(rrset, r)) 213238106Sdes return 0; 214238106Sdes if(!nsec3_get_salt(rrset, r, salt, saltlen)) 215238106Sdes return 0; 216238106Sdes *algo = nsec3_get_algo(rrset, r); 217238106Sdes *iter = nsec3_get_iter(rrset, r); 218238106Sdes return 1; 219238106Sdes} 220238106Sdes 221238106Sdesint 222238106Sdesnsec3_get_nextowner(struct ub_packed_rrset_key* rrset, int r, 223238106Sdes uint8_t** next, size_t* nextlen) 224238106Sdes{ 225238106Sdes size_t saltlen; 226238106Sdes struct packed_rrset_data* d = (struct packed_rrset_data*) 227238106Sdes rrset->entry.data; 228238106Sdes log_assert(d && r < (int)d->count); 229238106Sdes if(d->rr_len[r] < 2+5) { 230238106Sdes *next = 0; 231238106Sdes *nextlen = 0; 232238106Sdes return 0; /* malformed */ 233238106Sdes } 234238106Sdes saltlen = (size_t)d->rr_data[r][2+4]; 235238106Sdes if(d->rr_len[r] < 2+5+saltlen+1) { 236238106Sdes *next = 0; 237238106Sdes *nextlen = 0; 238238106Sdes return 0; /* malformed */ 239238106Sdes } 240238106Sdes *nextlen = (size_t)d->rr_data[r][2+5+saltlen]; 241238106Sdes if(d->rr_len[r] < 2+5+saltlen+1+*nextlen) { 242238106Sdes *next = 0; 243238106Sdes *nextlen = 0; 244238106Sdes return 0; /* malformed */ 245238106Sdes } 246238106Sdes *next = d->rr_data[r]+2+5+saltlen+1; 247238106Sdes return 1; 248238106Sdes} 249238106Sdes 250238106Sdessize_t nsec3_hash_to_b32(uint8_t* hash, size_t hashlen, uint8_t* zone, 251238106Sdes size_t zonelen, uint8_t* buf, size_t max) 252238106Sdes{ 253238106Sdes /* write b32 of name, leave one for length */ 254238106Sdes int ret; 255238106Sdes if(max < hashlen*2+1) /* quick approx of b32, as if hexb16 */ 256238106Sdes return 0; 257266114Sdes ret = sldns_b32_ntop_extended_hex(hash, hashlen, (char*)buf+1, max-1); 258238106Sdes if(ret < 1) 259238106Sdes return 0; 260238106Sdes buf[0] = (uint8_t)ret; /* length of b32 label */ 261238106Sdes ret++; 262238106Sdes if(max - ret < zonelen) 263238106Sdes return 0; 264238106Sdes memmove(buf+ret, zone, zonelen); 265238106Sdes return zonelen+(size_t)ret; 266238106Sdes} 267238106Sdes 268238106Sdessize_t nsec3_get_nextowner_b32(struct ub_packed_rrset_key* rrset, int r, 269238106Sdes uint8_t* buf, size_t max) 270238106Sdes{ 271238106Sdes uint8_t* nm, *zone; 272238106Sdes size_t nmlen, zonelen; 273238106Sdes if(!nsec3_get_nextowner(rrset, r, &nm, &nmlen)) 274238106Sdes return 0; 275238106Sdes /* append zone name; the owner name must be <b32>.zone */ 276238106Sdes zone = rrset->rk.dname; 277238106Sdes zonelen = rrset->rk.dname_len; 278238106Sdes dname_remove_label(&zone, &zonelen); 279238106Sdes return nsec3_hash_to_b32(nm, nmlen, zone, zonelen, buf, max); 280238106Sdes} 281238106Sdes 282238106Sdesint 283238106Sdesnsec3_has_type(struct ub_packed_rrset_key* rrset, int r, uint16_t type) 284238106Sdes{ 285238106Sdes uint8_t* bitmap; 286238106Sdes size_t bitlen, skiplen; 287238106Sdes struct packed_rrset_data* d = (struct packed_rrset_data*) 288238106Sdes rrset->entry.data; 289238106Sdes log_assert(d && r < (int)d->count); 290238106Sdes skiplen = 2+4; 291238106Sdes /* skip salt */ 292238106Sdes if(d->rr_len[r] < skiplen+1) 293238106Sdes return 0; /* malformed, too short */ 294238106Sdes skiplen += 1+(size_t)d->rr_data[r][skiplen]; 295238106Sdes /* skip next hashed owner */ 296238106Sdes if(d->rr_len[r] < skiplen+1) 297238106Sdes return 0; /* malformed, too short */ 298238106Sdes skiplen += 1+(size_t)d->rr_data[r][skiplen]; 299238106Sdes if(d->rr_len[r] < skiplen) 300238106Sdes return 0; /* malformed, too short */ 301238106Sdes bitlen = d->rr_len[r] - skiplen; 302238106Sdes bitmap = d->rr_data[r]+skiplen; 303238106Sdes return nsecbitmap_has_type_rdata(bitmap, bitlen, type); 304238106Sdes} 305238106Sdes 306238106Sdes/** 307238106Sdes * Iterate through NSEC3 list, per RR 308238106Sdes * This routine gives the next RR in the list (or sets rrset null). 309238106Sdes * Usage: 310238106Sdes * 311238106Sdes * size_t rrsetnum; 312238106Sdes * int rrnum; 313238106Sdes * struct ub_packed_rrset_key* rrset; 314238106Sdes * for(rrset=filter_first(filter, &rrsetnum, &rrnum); rrset; 315238106Sdes * rrset=filter_next(filter, &rrsetnum, &rrnum)) 316238106Sdes * do_stuff; 317238106Sdes * 318238106Sdes * Also filters out 319238106Sdes * o unknown flag NSEC3s 320238106Sdes * o unknown algorithm NSEC3s. 321238106Sdes * @param filter: nsec3 filter structure. 322238106Sdes * @param rrsetnum: in/out rrset number to look at. 323238106Sdes * @param rrnum: in/out rr number in rrset to look at. 324238106Sdes * @returns ptr to the next rrset (or NULL at end). 325238106Sdes */ 326238106Sdesstatic struct ub_packed_rrset_key* 327238106Sdesfilter_next(struct nsec3_filter* filter, size_t* rrsetnum, int* rrnum) 328238106Sdes{ 329238106Sdes size_t i; 330238106Sdes int r; 331238106Sdes uint8_t* nm; 332238106Sdes size_t nmlen; 333238106Sdes if(!filter->zone) /* empty list */ 334238106Sdes return NULL; 335238106Sdes for(i=*rrsetnum; i<filter->num; i++) { 336238106Sdes /* see if RRset qualifies */ 337238106Sdes if(ntohs(filter->list[i]->rk.type) != LDNS_RR_TYPE_NSEC3 || 338238106Sdes ntohs(filter->list[i]->rk.rrset_class) != 339238106Sdes filter->fclass) 340238106Sdes continue; 341238106Sdes /* check RRset zone */ 342238106Sdes nm = filter->list[i]->rk.dname; 343238106Sdes nmlen = filter->list[i]->rk.dname_len; 344238106Sdes dname_remove_label(&nm, &nmlen); 345238106Sdes if(query_dname_compare(nm, filter->zone) != 0) 346238106Sdes continue; 347238106Sdes if(i == *rrsetnum) 348238106Sdes r = (*rrnum) + 1; /* continue at next RR */ 349238106Sdes else r = 0; /* new RRset start at first RR */ 350238106Sdes for(; r < (int)rrset_get_count(filter->list[i]); r++) { 351238106Sdes /* skip unknown flags, algo */ 352238106Sdes if(nsec3_unknown_flags(filter->list[i], r) || 353238106Sdes !nsec3_known_algo(filter->list[i], r)) 354238106Sdes continue; 355238106Sdes /* this one is a good target */ 356238106Sdes *rrsetnum = i; 357238106Sdes *rrnum = r; 358238106Sdes return filter->list[i]; 359238106Sdes } 360238106Sdes } 361238106Sdes return NULL; 362238106Sdes} 363238106Sdes 364238106Sdes/** 365238106Sdes * Start iterating over NSEC3 records. 366238106Sdes * @param filter: the filter structure, must have been filter_init-ed. 367292206Sdes * @param rrsetnum: can be undefined on call, initialised. 368292206Sdes * @param rrnum: can be undefined on call, initialised. 369238106Sdes * @return first rrset of an NSEC3, together with rrnum this points to 370238106Sdes * the first RR to examine. Is NULL on empty list. 371238106Sdes */ 372238106Sdesstatic struct ub_packed_rrset_key* 373238106Sdesfilter_first(struct nsec3_filter* filter, size_t* rrsetnum, int* rrnum) 374238106Sdes{ 375238106Sdes *rrsetnum = 0; 376238106Sdes *rrnum = -1; 377238106Sdes return filter_next(filter, rrsetnum, rrnum); 378238106Sdes} 379238106Sdes 380238106Sdes/** see if at least one RR is known (flags, algo) */ 381238106Sdesstatic int 382238106Sdesnsec3_rrset_has_known(struct ub_packed_rrset_key* s) 383238106Sdes{ 384238106Sdes int r; 385238106Sdes for(r=0; r < (int)rrset_get_count(s); r++) { 386238106Sdes if(!nsec3_unknown_flags(s, r) && nsec3_known_algo(s, r)) 387238106Sdes return 1; 388238106Sdes } 389238106Sdes return 0; 390238106Sdes} 391238106Sdes 392238106Sdes/** 393238106Sdes * Initialize the filter structure. 394238106Sdes * Finds the zone by looking at available NSEC3 records and best match. 395238106Sdes * (skips the unknown flag and unknown algo NSEC3s). 396238106Sdes * 397238106Sdes * @param filter: nsec3 filter structure. 398238106Sdes * @param list: list of rrsets, an array of them. 399238106Sdes * @param num: number of rrsets in list. 400238106Sdes * @param qinfo: 401238106Sdes * query name to match a zone for. 402238106Sdes * query type (if DS a higher zone must be chosen) 403238106Sdes * qclass, to filter NSEC3s with. 404238106Sdes */ 405238106Sdesstatic void 406238106Sdesfilter_init(struct nsec3_filter* filter, struct ub_packed_rrset_key** list, 407238106Sdes size_t num, struct query_info* qinfo) 408238106Sdes{ 409238106Sdes size_t i; 410238106Sdes uint8_t* nm; 411238106Sdes size_t nmlen; 412238106Sdes filter->zone = NULL; 413238106Sdes filter->zone_len = 0; 414238106Sdes filter->list = list; 415238106Sdes filter->num = num; 416238106Sdes filter->fclass = qinfo->qclass; 417238106Sdes for(i=0; i<num; i++) { 418238106Sdes /* ignore other stuff in the list */ 419238106Sdes if(ntohs(list[i]->rk.type) != LDNS_RR_TYPE_NSEC3 || 420238106Sdes ntohs(list[i]->rk.rrset_class) != qinfo->qclass) 421238106Sdes continue; 422238106Sdes /* skip unknown flags, algo */ 423238106Sdes if(!nsec3_rrset_has_known(list[i])) 424238106Sdes continue; 425238106Sdes 426238106Sdes /* since NSEC3s are base32.zonename, we can find the zone 427238106Sdes * name by stripping off the first label of the record */ 428238106Sdes nm = list[i]->rk.dname; 429238106Sdes nmlen = list[i]->rk.dname_len; 430238106Sdes dname_remove_label(&nm, &nmlen); 431238106Sdes /* if we find a domain that can prove about the qname, 432238106Sdes * and if this domain is closer to the qname */ 433238106Sdes if(dname_subdomain_c(qinfo->qname, nm) && (!filter->zone || 434238106Sdes dname_subdomain_c(nm, filter->zone))) { 435238106Sdes /* for a type DS do not accept a zone equal to qname*/ 436238106Sdes if(qinfo->qtype == LDNS_RR_TYPE_DS && 437238106Sdes query_dname_compare(qinfo->qname, nm) == 0 && 438238106Sdes !dname_is_root(qinfo->qname)) 439238106Sdes continue; 440238106Sdes filter->zone = nm; 441238106Sdes filter->zone_len = nmlen; 442238106Sdes } 443238106Sdes } 444238106Sdes} 445238106Sdes 446238106Sdes/** 447238106Sdes * Find max iteration count using config settings and key size 448238106Sdes * @param ve: validator environment with iteration count config settings. 449238106Sdes * @param bits: key size 450238106Sdes * @return max iteration count 451238106Sdes */ 452238106Sdesstatic size_t 453238106Sdesget_max_iter(struct val_env* ve, size_t bits) 454238106Sdes{ 455238106Sdes int i; 456238106Sdes log_assert(ve->nsec3_keyiter_count > 0); 457238106Sdes /* round up to nearest config keysize, linear search, keep it small */ 458238106Sdes for(i=0; i<ve->nsec3_keyiter_count; i++) { 459238106Sdes if(bits <= ve->nsec3_keysize[i]) 460238106Sdes return ve->nsec3_maxiter[i]; 461238106Sdes } 462238106Sdes /* else, use value for biggest key */ 463238106Sdes return ve->nsec3_maxiter[ve->nsec3_keyiter_count-1]; 464238106Sdes} 465238106Sdes 466238106Sdes/** 467238106Sdes * Determine if any of the NSEC3 rrs iteration count is too high, from key. 468238106Sdes * @param ve: validator environment with iteration count config settings. 469238106Sdes * @param filter: what NSEC3s to loop over. 470238106Sdes * @param kkey: key entry used for verification; used for iteration counts. 471238106Sdes * @return 1 if some nsec3s are above the max iteration count. 472238106Sdes */ 473238106Sdesstatic int 474238106Sdesnsec3_iteration_count_high(struct val_env* ve, struct nsec3_filter* filter, 475238106Sdes struct key_entry_key* kkey) 476238106Sdes{ 477238106Sdes size_t rrsetnum; 478238106Sdes int rrnum; 479238106Sdes struct ub_packed_rrset_key* rrset; 480238106Sdes /* first determine the max number of iterations */ 481238106Sdes size_t bits = key_entry_keysize(kkey); 482238106Sdes size_t max_iter = get_max_iter(ve, bits); 483238106Sdes verbose(VERB_ALGO, "nsec3: keysize %d bits, max iterations %d", 484238106Sdes (int)bits, (int)max_iter); 485238106Sdes 486238106Sdes for(rrset=filter_first(filter, &rrsetnum, &rrnum); rrset; 487238106Sdes rrset=filter_next(filter, &rrsetnum, &rrnum)) { 488238106Sdes if(nsec3_get_iter(rrset, rrnum) > max_iter) 489238106Sdes return 1; 490238106Sdes } 491238106Sdes return 0; 492238106Sdes} 493238106Sdes 494238106Sdes/* nsec3_cache_compare for rbtree */ 495238106Sdesint 496238106Sdesnsec3_hash_cmp(const void* c1, const void* c2) 497238106Sdes{ 498238106Sdes struct nsec3_cached_hash* h1 = (struct nsec3_cached_hash*)c1; 499238106Sdes struct nsec3_cached_hash* h2 = (struct nsec3_cached_hash*)c2; 500238106Sdes uint8_t* s1, *s2; 501238106Sdes size_t s1len, s2len; 502238106Sdes int c = query_dname_compare(h1->dname, h2->dname); 503238106Sdes if(c != 0) 504238106Sdes return c; 505238106Sdes /* compare parameters */ 506238106Sdes /* if both malformed, its equal, robustness */ 507238106Sdes if(nsec3_get_algo(h1->nsec3, h1->rr) != 508238106Sdes nsec3_get_algo(h2->nsec3, h2->rr)) { 509238106Sdes if(nsec3_get_algo(h1->nsec3, h1->rr) < 510238106Sdes nsec3_get_algo(h2->nsec3, h2->rr)) 511238106Sdes return -1; 512238106Sdes return 1; 513238106Sdes } 514238106Sdes if(nsec3_get_iter(h1->nsec3, h1->rr) != 515238106Sdes nsec3_get_iter(h2->nsec3, h2->rr)) { 516238106Sdes if(nsec3_get_iter(h1->nsec3, h1->rr) < 517238106Sdes nsec3_get_iter(h2->nsec3, h2->rr)) 518238106Sdes return -1; 519238106Sdes return 1; 520238106Sdes } 521238106Sdes (void)nsec3_get_salt(h1->nsec3, h1->rr, &s1, &s1len); 522238106Sdes (void)nsec3_get_salt(h2->nsec3, h2->rr, &s2, &s2len); 523356345Scy if(s1len == 0 && s2len == 0) 524356345Scy return 0; 525356345Scy if(!s1) return -1; 526356345Scy if(!s2) return 1; 527238106Sdes if(s1len != s2len) { 528238106Sdes if(s1len < s2len) 529238106Sdes return -1; 530238106Sdes return 1; 531238106Sdes } 532238106Sdes return memcmp(s1, s2, s1len); 533238106Sdes} 534238106Sdes 535238106Sdessize_t 536266114Sdesnsec3_get_hashed(sldns_buffer* buf, uint8_t* nm, size_t nmlen, int algo, 537238106Sdes size_t iter, uint8_t* salt, size_t saltlen, uint8_t* res, size_t max) 538238106Sdes{ 539238106Sdes size_t i, hash_len; 540238106Sdes /* prepare buffer for first iteration */ 541266114Sdes sldns_buffer_clear(buf); 542266114Sdes sldns_buffer_write(buf, nm, nmlen); 543266114Sdes query_dname_tolower(sldns_buffer_begin(buf)); 544266114Sdes sldns_buffer_write(buf, salt, saltlen); 545266114Sdes sldns_buffer_flip(buf); 546292206Sdes hash_len = nsec3_hash_algo_size_supported(algo); 547292206Sdes if(hash_len == 0) { 548292206Sdes log_err("nsec3 hash of unknown algo %d", algo); 549292206Sdes return 0; 550292206Sdes } 551292206Sdes if(hash_len > max) 552292206Sdes return 0; 553292206Sdes if(!secalgo_nsec3_hash(algo, (unsigned char*)sldns_buffer_begin(buf), 554292206Sdes sldns_buffer_limit(buf), (unsigned char*)res)) 555292206Sdes return 0; 556292206Sdes for(i=0; i<iter; i++) { 557292206Sdes sldns_buffer_clear(buf); 558292206Sdes sldns_buffer_write(buf, res, hash_len); 559292206Sdes sldns_buffer_write(buf, salt, saltlen); 560292206Sdes sldns_buffer_flip(buf); 561292206Sdes if(!secalgo_nsec3_hash(algo, 562292206Sdes (unsigned char*)sldns_buffer_begin(buf), 563292206Sdes sldns_buffer_limit(buf), (unsigned char*)res)) 564238106Sdes return 0; 565238106Sdes } 566238106Sdes return hash_len; 567238106Sdes} 568238106Sdes 569238106Sdes/** perform hash of name */ 570238106Sdesstatic int 571266114Sdesnsec3_calc_hash(struct regional* region, sldns_buffer* buf, 572238106Sdes struct nsec3_cached_hash* c) 573238106Sdes{ 574238106Sdes int algo = nsec3_get_algo(c->nsec3, c->rr); 575238106Sdes size_t iter = nsec3_get_iter(c->nsec3, c->rr); 576238106Sdes uint8_t* salt; 577238106Sdes size_t saltlen, i; 578238106Sdes if(!nsec3_get_salt(c->nsec3, c->rr, &salt, &saltlen)) 579238106Sdes return -1; 580238106Sdes /* prepare buffer for first iteration */ 581266114Sdes sldns_buffer_clear(buf); 582266114Sdes sldns_buffer_write(buf, c->dname, c->dname_len); 583266114Sdes query_dname_tolower(sldns_buffer_begin(buf)); 584266114Sdes sldns_buffer_write(buf, salt, saltlen); 585266114Sdes sldns_buffer_flip(buf); 586292206Sdes c->hash_len = nsec3_hash_algo_size_supported(algo); 587292206Sdes if(c->hash_len == 0) { 588292206Sdes log_err("nsec3 hash of unknown algo %d", algo); 589292206Sdes return -1; 590238106Sdes } 591292206Sdes c->hash = (uint8_t*)regional_alloc(region, c->hash_len); 592292206Sdes if(!c->hash) 593292206Sdes return 0; 594292206Sdes (void)secalgo_nsec3_hash(algo, (unsigned char*)sldns_buffer_begin(buf), 595292206Sdes sldns_buffer_limit(buf), (unsigned char*)c->hash); 596292206Sdes for(i=0; i<iter; i++) { 597292206Sdes sldns_buffer_clear(buf); 598292206Sdes sldns_buffer_write(buf, c->hash, c->hash_len); 599292206Sdes sldns_buffer_write(buf, salt, saltlen); 600292206Sdes sldns_buffer_flip(buf); 601292206Sdes (void)secalgo_nsec3_hash(algo, 602292206Sdes (unsigned char*)sldns_buffer_begin(buf), 603292206Sdes sldns_buffer_limit(buf), (unsigned char*)c->hash); 604292206Sdes } 605238106Sdes return 1; 606238106Sdes} 607238106Sdes 608238106Sdes/** perform b32 encoding of hash */ 609238106Sdesstatic int 610266114Sdesnsec3_calc_b32(struct regional* region, sldns_buffer* buf, 611238106Sdes struct nsec3_cached_hash* c) 612238106Sdes{ 613238106Sdes int r; 614266114Sdes sldns_buffer_clear(buf); 615266114Sdes r = sldns_b32_ntop_extended_hex(c->hash, c->hash_len, 616266114Sdes (char*)sldns_buffer_begin(buf), sldns_buffer_limit(buf)); 617238106Sdes if(r < 1) { 618238106Sdes log_err("b32_ntop_extended_hex: error in encoding: %d", r); 619238106Sdes return 0; 620238106Sdes } 621238106Sdes c->b32_len = (size_t)r; 622266114Sdes c->b32 = regional_alloc_init(region, sldns_buffer_begin(buf), 623238106Sdes c->b32_len); 624238106Sdes if(!c->b32) 625238106Sdes return 0; 626238106Sdes return 1; 627238106Sdes} 628238106Sdes 629238106Sdesint 630356345Scynsec3_hash_name(rbtree_type* table, struct regional* region, sldns_buffer* buf, 631238106Sdes struct ub_packed_rrset_key* nsec3, int rr, uint8_t* dname, 632238106Sdes size_t dname_len, struct nsec3_cached_hash** hash) 633238106Sdes{ 634238106Sdes struct nsec3_cached_hash* c; 635238106Sdes struct nsec3_cached_hash looki; 636238106Sdes#ifdef UNBOUND_DEBUG 637356345Scy rbnode_type* n; 638238106Sdes#endif 639238106Sdes int r; 640238106Sdes looki.node.key = &looki; 641238106Sdes looki.nsec3 = nsec3; 642238106Sdes looki.rr = rr; 643238106Sdes looki.dname = dname; 644238106Sdes looki.dname_len = dname_len; 645238106Sdes /* lookup first in cache */ 646238106Sdes c = (struct nsec3_cached_hash*)rbtree_search(table, &looki); 647238106Sdes if(c) { 648238106Sdes *hash = c; 649238106Sdes return 1; 650238106Sdes } 651238106Sdes /* create a new entry */ 652238106Sdes c = (struct nsec3_cached_hash*)regional_alloc(region, sizeof(*c)); 653238106Sdes if(!c) return 0; 654238106Sdes c->node.key = c; 655238106Sdes c->nsec3 = nsec3; 656238106Sdes c->rr = rr; 657238106Sdes c->dname = dname; 658238106Sdes c->dname_len = dname_len; 659238106Sdes r = nsec3_calc_hash(region, buf, c); 660238106Sdes if(r != 1) 661238106Sdes return r; 662238106Sdes r = nsec3_calc_b32(region, buf, c); 663238106Sdes if(r != 1) 664238106Sdes return r; 665238106Sdes#ifdef UNBOUND_DEBUG 666238106Sdes n = 667266114Sdes#else 668266114Sdes (void) 669238106Sdes#endif 670238106Sdes rbtree_insert(table, &c->node); 671238106Sdes log_assert(n); /* cannot be duplicate, just did lookup */ 672238106Sdes *hash = c; 673238106Sdes return 1; 674238106Sdes} 675238106Sdes 676238106Sdes/** 677238106Sdes * compare a label lowercased 678238106Sdes */ 679238106Sdesstatic int 680238106Sdeslabel_compare_lower(uint8_t* lab1, uint8_t* lab2, size_t lablen) 681238106Sdes{ 682238106Sdes size_t i; 683238106Sdes for(i=0; i<lablen; i++) { 684276605Sdes if(tolower((unsigned char)*lab1) != tolower((unsigned char)*lab2)) { 685276605Sdes if(tolower((unsigned char)*lab1) < tolower((unsigned char)*lab2)) 686238106Sdes return -1; 687238106Sdes return 1; 688238106Sdes } 689238106Sdes lab1++; 690238106Sdes lab2++; 691238106Sdes } 692238106Sdes return 0; 693238106Sdes} 694238106Sdes 695238106Sdes/** 696238106Sdes * Compare a hashed name with the owner name of an NSEC3 RRset. 697238106Sdes * @param flt: filter with zone name. 698238106Sdes * @param hash: the hashed name. 699238106Sdes * @param s: rrset with owner name. 700238106Sdes * @return true if matches exactly, false if not. 701238106Sdes */ 702238106Sdesstatic int 703238106Sdesnsec3_hash_matches_owner(struct nsec3_filter* flt, 704238106Sdes struct nsec3_cached_hash* hash, struct ub_packed_rrset_key* s) 705238106Sdes{ 706238106Sdes uint8_t* nm = s->rk.dname; 707238106Sdes /* compare, does hash of name based on params in this NSEC3 708238106Sdes * match the owner name of this NSEC3? 709238106Sdes * name must be: <hashlength>base32 . zone name 710238106Sdes * so; first label must not be root label (not zero length), 711238106Sdes * and match the b32 encoded hash length, 712238106Sdes * and the label content match the b32 encoded hash 713238106Sdes * and the rest must be the zone name. 714238106Sdes */ 715238106Sdes if(hash->b32_len != 0 && (size_t)nm[0] == hash->b32_len && 716238106Sdes label_compare_lower(nm+1, hash->b32, hash->b32_len) == 0 && 717238106Sdes query_dname_compare(nm+(size_t)nm[0]+1, flt->zone) == 0) { 718238106Sdes return 1; 719238106Sdes } 720238106Sdes return 0; 721238106Sdes} 722238106Sdes 723238106Sdes/** 724238106Sdes * Find matching NSEC3 725238106Sdes * Find the NSEC3Record that matches a hash of a name. 726238106Sdes * @param env: module environment with temporary region and buffer. 727238106Sdes * @param flt: the NSEC3 RR filter, contains zone name and RRs. 728238106Sdes * @param ct: cached hashes table. 729238106Sdes * @param nm: name to look for. 730238106Sdes * @param nmlen: length of name. 731238106Sdes * @param rrset: nsec3 that matches is returned here. 732238106Sdes * @param rr: rr number in nsec3 rrset that matches. 733238106Sdes * @return true if a matching NSEC3 is found, false if not. 734238106Sdes */ 735238106Sdesstatic int 736238106Sdesfind_matching_nsec3(struct module_env* env, struct nsec3_filter* flt, 737356345Scy rbtree_type* ct, uint8_t* nm, size_t nmlen, 738238106Sdes struct ub_packed_rrset_key** rrset, int* rr) 739238106Sdes{ 740238106Sdes size_t i_rs; 741238106Sdes int i_rr; 742238106Sdes struct ub_packed_rrset_key* s; 743356345Scy struct nsec3_cached_hash* hash = NULL; 744238106Sdes int r; 745238106Sdes 746238106Sdes /* this loop skips other-zone and unknown NSEC3s, also non-NSEC3 RRs */ 747238106Sdes for(s=filter_first(flt, &i_rs, &i_rr); s; 748238106Sdes s=filter_next(flt, &i_rs, &i_rr)) { 749238106Sdes /* get name hashed for this NSEC3 RR */ 750238106Sdes r = nsec3_hash_name(ct, env->scratch, env->scratch_buffer, 751238106Sdes s, i_rr, nm, nmlen, &hash); 752238106Sdes if(r == 0) { 753238106Sdes log_err("nsec3: malloc failure"); 754238106Sdes break; /* alloc failure */ 755356345Scy } else if(r != 1) 756238106Sdes continue; /* malformed NSEC3 */ 757238106Sdes else if(nsec3_hash_matches_owner(flt, hash, s)) { 758238106Sdes *rrset = s; /* rrset with this name */ 759238106Sdes *rr = i_rr; /* matches hash with these parameters */ 760238106Sdes return 1; 761238106Sdes } 762238106Sdes } 763238106Sdes *rrset = NULL; 764238106Sdes *rr = 0; 765238106Sdes return 0; 766238106Sdes} 767238106Sdes 768238106Sdesint 769238106Sdesnsec3_covers(uint8_t* zone, struct nsec3_cached_hash* hash, 770266114Sdes struct ub_packed_rrset_key* rrset, int rr, sldns_buffer* buf) 771238106Sdes{ 772238106Sdes uint8_t* next, *owner; 773238106Sdes size_t nextlen; 774238106Sdes int len; 775238106Sdes if(!nsec3_get_nextowner(rrset, rr, &next, &nextlen)) 776238106Sdes return 0; /* malformed RR proves nothing */ 777238106Sdes 778238106Sdes /* check the owner name is a hashed value . apex 779238106Sdes * base32 encoded values must have equal length. 780238106Sdes * hash_value and next hash value must have equal length. */ 781238106Sdes if(nextlen != hash->hash_len || hash->hash_len==0||hash->b32_len==0|| 782238106Sdes (size_t)*rrset->rk.dname != hash->b32_len || 783238106Sdes query_dname_compare(rrset->rk.dname+1+ 784238106Sdes (size_t)*rrset->rk.dname, zone) != 0) 785238106Sdes return 0; /* bad lengths or owner name */ 786238106Sdes 787238106Sdes /* This is the "normal case: owner < next and owner < hash < next */ 788238106Sdes if(label_compare_lower(rrset->rk.dname+1, hash->b32, 789238106Sdes hash->b32_len) < 0 && 790238106Sdes memcmp(hash->hash, next, nextlen) < 0) 791238106Sdes return 1; 792238106Sdes 793238106Sdes /* convert owner name from text to binary */ 794266114Sdes sldns_buffer_clear(buf); 795266114Sdes owner = sldns_buffer_begin(buf); 796266114Sdes len = sldns_b32_pton_extended_hex((char*)rrset->rk.dname+1, 797266114Sdes hash->b32_len, owner, sldns_buffer_limit(buf)); 798238106Sdes if(len<1) 799238106Sdes return 0; /* bad owner name in some way */ 800238106Sdes if((size_t)len != hash->hash_len || (size_t)len != nextlen) 801238106Sdes return 0; /* wrong length */ 802238106Sdes 803238106Sdes /* this is the end of zone case: next <= owner && 804238106Sdes * (hash > owner || hash < next) 805238106Sdes * this also covers the only-apex case of next==owner. 806238106Sdes */ 807238106Sdes if(memcmp(next, owner, nextlen) <= 0 && 808238106Sdes ( memcmp(hash->hash, owner, nextlen) > 0 || 809238106Sdes memcmp(hash->hash, next, nextlen) < 0)) { 810238106Sdes return 1; 811238106Sdes } 812238106Sdes return 0; 813238106Sdes} 814238106Sdes 815238106Sdes/** 816238106Sdes * findCoveringNSEC3 817238106Sdes * Given a name, find a covering NSEC3 from among a list of NSEC3s. 818238106Sdes * 819238106Sdes * @param env: module environment with temporary region and buffer. 820238106Sdes * @param flt: the NSEC3 RR filter, contains zone name and RRs. 821238106Sdes * @param ct: cached hashes table. 822238106Sdes * @param nm: name to check if covered. 823238106Sdes * @param nmlen: length of name. 824238106Sdes * @param rrset: covering NSEC3 rrset is returned here. 825238106Sdes * @param rr: rr of cover is returned here. 826238106Sdes * @return true if a covering NSEC3 is found, false if not. 827238106Sdes */ 828238106Sdesstatic int 829238106Sdesfind_covering_nsec3(struct module_env* env, struct nsec3_filter* flt, 830356345Scy rbtree_type* ct, uint8_t* nm, size_t nmlen, 831238106Sdes struct ub_packed_rrset_key** rrset, int* rr) 832238106Sdes{ 833238106Sdes size_t i_rs; 834238106Sdes int i_rr; 835238106Sdes struct ub_packed_rrset_key* s; 836356345Scy struct nsec3_cached_hash* hash = NULL; 837238106Sdes int r; 838238106Sdes 839238106Sdes /* this loop skips other-zone and unknown NSEC3s, also non-NSEC3 RRs */ 840238106Sdes for(s=filter_first(flt, &i_rs, &i_rr); s; 841238106Sdes s=filter_next(flt, &i_rs, &i_rr)) { 842238106Sdes /* get name hashed for this NSEC3 RR */ 843238106Sdes r = nsec3_hash_name(ct, env->scratch, env->scratch_buffer, 844238106Sdes s, i_rr, nm, nmlen, &hash); 845238106Sdes if(r == 0) { 846238106Sdes log_err("nsec3: malloc failure"); 847238106Sdes break; /* alloc failure */ 848356345Scy } else if(r != 1) 849238106Sdes continue; /* malformed NSEC3 */ 850238106Sdes else if(nsec3_covers(flt->zone, hash, s, i_rr, 851238106Sdes env->scratch_buffer)) { 852238106Sdes *rrset = s; /* rrset with this name */ 853238106Sdes *rr = i_rr; /* covers hash with these parameters */ 854238106Sdes return 1; 855238106Sdes } 856238106Sdes } 857238106Sdes *rrset = NULL; 858238106Sdes *rr = 0; 859238106Sdes return 0; 860238106Sdes} 861238106Sdes 862238106Sdes/** 863238106Sdes * findClosestEncloser 864238106Sdes * Given a name and a list of NSEC3s, find the candidate closest encloser. 865238106Sdes * This will be the first ancestor of 'name' (including itself) to have a 866238106Sdes * matching NSEC3 RR. 867238106Sdes * @param env: module environment with temporary region and buffer. 868238106Sdes * @param flt: the NSEC3 RR filter, contains zone name and RRs. 869238106Sdes * @param ct: cached hashes table. 870238106Sdes * @param qinfo: query that is verified for. 871238106Sdes * @param ce: closest encloser information is returned in here. 872238106Sdes * @return true if a closest encloser candidate is found, false if not. 873238106Sdes */ 874238106Sdesstatic int 875238106Sdesnsec3_find_closest_encloser(struct module_env* env, struct nsec3_filter* flt, 876356345Scy rbtree_type* ct, struct query_info* qinfo, struct ce_response* ce) 877238106Sdes{ 878238106Sdes uint8_t* nm = qinfo->qname; 879238106Sdes size_t nmlen = qinfo->qname_len; 880238106Sdes 881238106Sdes /* This scans from longest name to shortest, so the first match 882238106Sdes * we find is the only viable candidate. */ 883238106Sdes 884238106Sdes /* (David:) FIXME: modify so that the NSEC3 matching the zone apex need 885238106Sdes * not be present. (Mark Andrews idea). 886238106Sdes * (Wouter:) But make sure you check for DNAME bit in zone apex, 887238106Sdes * if the NSEC3 you find is the only NSEC3 in the zone, then this 888238106Sdes * may be the case. */ 889238106Sdes 890238106Sdes while(dname_subdomain_c(nm, flt->zone)) { 891238106Sdes if(find_matching_nsec3(env, flt, ct, nm, nmlen, 892238106Sdes &ce->ce_rrset, &ce->ce_rr)) { 893238106Sdes ce->ce = nm; 894238106Sdes ce->ce_len = nmlen; 895238106Sdes return 1; 896238106Sdes } 897238106Sdes dname_remove_label(&nm, &nmlen); 898238106Sdes } 899238106Sdes return 0; 900238106Sdes} 901238106Sdes 902238106Sdes/** 903238106Sdes * Given a qname and its proven closest encloser, calculate the "next 904238106Sdes * closest" name. Basically, this is the name that is one label longer than 905238106Sdes * the closest encloser that is still a subdomain of qname. 906238106Sdes * 907238106Sdes * @param qname: query name. 908238106Sdes * @param qnamelen: length of qname. 909238106Sdes * @param ce: closest encloser 910238106Sdes * @param nm: result name. 911238106Sdes * @param nmlen: length of nm. 912238106Sdes */ 913238106Sdesstatic void 914238106Sdesnext_closer(uint8_t* qname, size_t qnamelen, uint8_t* ce, 915238106Sdes uint8_t** nm, size_t* nmlen) 916238106Sdes{ 917238106Sdes int strip = dname_count_labels(qname) - dname_count_labels(ce) -1; 918238106Sdes *nm = qname; 919238106Sdes *nmlen = qnamelen; 920238106Sdes if(strip>0) 921238106Sdes dname_remove_labels(nm, nmlen, strip); 922238106Sdes} 923238106Sdes 924238106Sdes/** 925238106Sdes * proveClosestEncloser 926238106Sdes * Given a List of nsec3 RRs, find and prove the closest encloser to qname. 927238106Sdes * @param env: module environment with temporary region and buffer. 928238106Sdes * @param flt: the NSEC3 RR filter, contains zone name and RRs. 929238106Sdes * @param ct: cached hashes table. 930238106Sdes * @param qinfo: query that is verified for. 931238106Sdes * @param prove_does_not_exist: If true, then if the closest encloser 932238106Sdes * turns out to be qname, then null is returned. 933238106Sdes * If set true, and the return value is true, then you can be 934238106Sdes * certain that the ce.nc_rrset and ce.nc_rr are set properly. 935238106Sdes * @param ce: closest encloser information is returned in here. 936238106Sdes * @return bogus if no closest encloser could be proven. 937238106Sdes * secure if a closest encloser could be proven, ce is set. 938238106Sdes * insecure if the closest-encloser candidate turns out to prove 939238106Sdes * that an insecure delegation exists above the qname. 940238106Sdes */ 941238106Sdesstatic enum sec_status 942238106Sdesnsec3_prove_closest_encloser(struct module_env* env, struct nsec3_filter* flt, 943356345Scy rbtree_type* ct, struct query_info* qinfo, int prove_does_not_exist, 944238106Sdes struct ce_response* ce) 945238106Sdes{ 946238106Sdes uint8_t* nc; 947238106Sdes size_t nc_len; 948238106Sdes /* robust: clean out ce, in case it gets abused later */ 949238106Sdes memset(ce, 0, sizeof(*ce)); 950238106Sdes 951238106Sdes if(!nsec3_find_closest_encloser(env, flt, ct, qinfo, ce)) { 952238106Sdes verbose(VERB_ALGO, "nsec3 proveClosestEncloser: could " 953238106Sdes "not find a candidate for the closest encloser."); 954238106Sdes return sec_status_bogus; 955238106Sdes } 956238106Sdes log_nametypeclass(VERB_ALGO, "ce candidate", ce->ce, 0, 0); 957238106Sdes 958238106Sdes if(query_dname_compare(ce->ce, qinfo->qname) == 0) { 959238106Sdes if(prove_does_not_exist) { 960238106Sdes verbose(VERB_ALGO, "nsec3 proveClosestEncloser: " 961238106Sdes "proved that qname existed, bad"); 962238106Sdes return sec_status_bogus; 963238106Sdes } 964238106Sdes /* otherwise, we need to nothing else to prove that qname 965238106Sdes * is its own closest encloser. */ 966238106Sdes return sec_status_secure; 967238106Sdes } 968238106Sdes 969238106Sdes /* If the closest encloser is actually a delegation, then the 970238106Sdes * response should have been a referral. If it is a DNAME, then 971238106Sdes * it should have been a DNAME response. */ 972238106Sdes if(nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_NS) && 973238106Sdes !nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_SOA)) { 974238106Sdes if(!nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_DS)) { 975238106Sdes verbose(VERB_ALGO, "nsec3 proveClosestEncloser: " 976238106Sdes "closest encloser is insecure delegation"); 977238106Sdes return sec_status_insecure; 978238106Sdes } 979238106Sdes verbose(VERB_ALGO, "nsec3 proveClosestEncloser: closest " 980238106Sdes "encloser was a delegation, bad"); 981238106Sdes return sec_status_bogus; 982238106Sdes } 983238106Sdes if(nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_DNAME)) { 984238106Sdes verbose(VERB_ALGO, "nsec3 proveClosestEncloser: closest " 985238106Sdes "encloser was a DNAME, bad"); 986238106Sdes return sec_status_bogus; 987238106Sdes } 988238106Sdes 989238106Sdes /* Otherwise, we need to show that the next closer name is covered. */ 990238106Sdes next_closer(qinfo->qname, qinfo->qname_len, ce->ce, &nc, &nc_len); 991238106Sdes if(!find_covering_nsec3(env, flt, ct, nc, nc_len, 992238106Sdes &ce->nc_rrset, &ce->nc_rr)) { 993238106Sdes verbose(VERB_ALGO, "nsec3: Could not find proof that the " 994238106Sdes "candidate encloser was the closest encloser"); 995238106Sdes return sec_status_bogus; 996238106Sdes } 997238106Sdes return sec_status_secure; 998238106Sdes} 999238106Sdes 1000238106Sdes/** allocate a wildcard for the closest encloser */ 1001238106Sdesstatic uint8_t* 1002238106Sdesnsec3_ce_wildcard(struct regional* region, uint8_t* ce, size_t celen, 1003238106Sdes size_t* len) 1004238106Sdes{ 1005238106Sdes uint8_t* nm; 1006238106Sdes if(celen > LDNS_MAX_DOMAINLEN - 2) 1007238106Sdes return 0; /* too long */ 1008238106Sdes nm = (uint8_t*)regional_alloc(region, celen+2); 1009238106Sdes if(!nm) { 1010238106Sdes log_err("nsec3 wildcard: out of memory"); 1011238106Sdes return 0; /* alloc failure */ 1012238106Sdes } 1013238106Sdes nm[0] = 1; 1014238106Sdes nm[1] = (uint8_t)'*'; /* wildcard label */ 1015238106Sdes memmove(nm+2, ce, celen); 1016238106Sdes *len = celen+2; 1017238106Sdes return nm; 1018238106Sdes} 1019238106Sdes 1020238106Sdes/** Do the name error proof */ 1021238106Sdesstatic enum sec_status 1022238106Sdesnsec3_do_prove_nameerror(struct module_env* env, struct nsec3_filter* flt, 1023356345Scy rbtree_type* ct, struct query_info* qinfo) 1024238106Sdes{ 1025238106Sdes struct ce_response ce; 1026238106Sdes uint8_t* wc; 1027238106Sdes size_t wclen; 1028238106Sdes struct ub_packed_rrset_key* wc_rrset; 1029238106Sdes int wc_rr; 1030238106Sdes enum sec_status sec; 1031238106Sdes 1032238106Sdes /* First locate and prove the closest encloser to qname. We will 1033238106Sdes * use the variant that fails if the closest encloser turns out 1034238106Sdes * to be qname. */ 1035238106Sdes sec = nsec3_prove_closest_encloser(env, flt, ct, qinfo, 1, &ce); 1036238106Sdes if(sec != sec_status_secure) { 1037238106Sdes if(sec == sec_status_bogus) 1038238106Sdes verbose(VERB_ALGO, "nsec3 nameerror proof: failed " 1039238106Sdes "to prove a closest encloser"); 1040238106Sdes else verbose(VERB_ALGO, "nsec3 nameerror proof: closest " 1041238106Sdes "nsec3 is an insecure delegation"); 1042238106Sdes return sec; 1043238106Sdes } 1044356345Scy log_nametypeclass(VERB_ALGO, "nsec3 nameerror: proven ce=", ce.ce,0,0); 1045238106Sdes 1046238106Sdes /* At this point, we know that qname does not exist. Now we need 1047238106Sdes * to prove that the wildcard does not exist. */ 1048238106Sdes log_assert(ce.ce); 1049238106Sdes wc = nsec3_ce_wildcard(env->scratch, ce.ce, ce.ce_len, &wclen); 1050238106Sdes if(!wc || !find_covering_nsec3(env, flt, ct, wc, wclen, 1051238106Sdes &wc_rrset, &wc_rr)) { 1052238106Sdes verbose(VERB_ALGO, "nsec3 nameerror proof: could not prove " 1053238106Sdes "that the applicable wildcard did not exist."); 1054238106Sdes return sec_status_bogus; 1055238106Sdes } 1056238106Sdes 1057238106Sdes if(ce.nc_rrset && nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) { 1058238106Sdes verbose(VERB_ALGO, "nsec3 nameerror proof: nc has optout"); 1059238106Sdes return sec_status_insecure; 1060238106Sdes } 1061238106Sdes return sec_status_secure; 1062238106Sdes} 1063238106Sdes 1064238106Sdesenum sec_status 1065238106Sdesnsec3_prove_nameerror(struct module_env* env, struct val_env* ve, 1066238106Sdes struct ub_packed_rrset_key** list, size_t num, 1067238106Sdes struct query_info* qinfo, struct key_entry_key* kkey) 1068238106Sdes{ 1069356345Scy rbtree_type ct; 1070238106Sdes struct nsec3_filter flt; 1071238106Sdes 1072238106Sdes if(!list || num == 0 || !kkey || !key_entry_isgood(kkey)) 1073238106Sdes return sec_status_bogus; /* no valid NSEC3s, bogus */ 1074238106Sdes rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */ 1075238106Sdes filter_init(&flt, list, num, qinfo); /* init RR iterator */ 1076238106Sdes if(!flt.zone) 1077238106Sdes return sec_status_bogus; /* no RRs */ 1078238106Sdes if(nsec3_iteration_count_high(ve, &flt, kkey)) 1079238106Sdes return sec_status_insecure; /* iteration count too high */ 1080238106Sdes log_nametypeclass(VERB_ALGO, "start nsec3 nameerror proof, zone", 1081238106Sdes flt.zone, 0, 0); 1082238106Sdes return nsec3_do_prove_nameerror(env, &flt, &ct, qinfo); 1083238106Sdes} 1084238106Sdes 1085238106Sdes/* 1086238106Sdes * No code to handle qtype=NSEC3 specially. 1087238106Sdes * This existed in early drafts, but was later (-05) removed. 1088238106Sdes */ 1089238106Sdes 1090238106Sdes/** Do the nodata proof */ 1091238106Sdesstatic enum sec_status 1092238106Sdesnsec3_do_prove_nodata(struct module_env* env, struct nsec3_filter* flt, 1093356345Scy rbtree_type* ct, struct query_info* qinfo) 1094238106Sdes{ 1095238106Sdes struct ce_response ce; 1096238106Sdes uint8_t* wc; 1097238106Sdes size_t wclen; 1098238106Sdes struct ub_packed_rrset_key* rrset; 1099238106Sdes int rr; 1100238106Sdes enum sec_status sec; 1101238106Sdes 1102238106Sdes if(find_matching_nsec3(env, flt, ct, qinfo->qname, qinfo->qname_len, 1103238106Sdes &rrset, &rr)) { 1104238106Sdes /* cases 1 and 2 */ 1105238106Sdes if(nsec3_has_type(rrset, rr, qinfo->qtype)) { 1106238106Sdes verbose(VERB_ALGO, "proveNodata: Matching NSEC3 " 1107238106Sdes "proved that type existed, bogus"); 1108238106Sdes return sec_status_bogus; 1109238106Sdes } else if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_CNAME)) { 1110238106Sdes verbose(VERB_ALGO, "proveNodata: Matching NSEC3 " 1111238106Sdes "proved that a CNAME existed, bogus"); 1112238106Sdes return sec_status_bogus; 1113238106Sdes } 1114238106Sdes 1115238106Sdes /* 1116238106Sdes * If type DS: filter_init zone find already found a parent 1117238106Sdes * zone, so this nsec3 is from a parent zone. 1118238106Sdes * o can be not a delegation (unusual query for normal name, 1119238106Sdes * no DS anyway, but we can verify that). 1120238106Sdes * o can be a delegation (which is the usual DS check). 1121238106Sdes * o may not have the SOA bit set (only the top of the 1122238106Sdes * zone, which must have been above the name, has that). 1123238106Sdes * Except for the root; which is checked by itself. 1124238106Sdes * 1125238106Sdes * If not type DS: matching nsec3 must not be a delegation. 1126238106Sdes */ 1127238106Sdes if(qinfo->qtype == LDNS_RR_TYPE_DS && qinfo->qname_len != 1 1128249141Sdes && nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA) && 1129249141Sdes !dname_is_root(qinfo->qname)) { 1130238106Sdes verbose(VERB_ALGO, "proveNodata: apex NSEC3 " 1131238106Sdes "abused for no DS proof, bogus"); 1132238106Sdes return sec_status_bogus; 1133238106Sdes } else if(qinfo->qtype != LDNS_RR_TYPE_DS && 1134238106Sdes nsec3_has_type(rrset, rr, LDNS_RR_TYPE_NS) && 1135238106Sdes !nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA)) { 1136238106Sdes if(!nsec3_has_type(rrset, rr, LDNS_RR_TYPE_DS)) { 1137238106Sdes verbose(VERB_ALGO, "proveNodata: matching " 1138238106Sdes "NSEC3 is insecure delegation"); 1139238106Sdes return sec_status_insecure; 1140238106Sdes } 1141238106Sdes verbose(VERB_ALGO, "proveNodata: matching " 1142238106Sdes "NSEC3 is a delegation, bogus"); 1143238106Sdes return sec_status_bogus; 1144238106Sdes } 1145238106Sdes return sec_status_secure; 1146238106Sdes } 1147238106Sdes 1148238106Sdes /* For cases 3 - 5, we need the proven closest encloser, and it 1149238106Sdes * can't match qname. Although, at this point, we know that it 1150238106Sdes * won't since we just checked that. */ 1151238106Sdes sec = nsec3_prove_closest_encloser(env, flt, ct, qinfo, 1, &ce); 1152238106Sdes if(sec == sec_status_bogus) { 1153238106Sdes verbose(VERB_ALGO, "proveNodata: did not match qname, " 1154238106Sdes "nor found a proven closest encloser."); 1155238106Sdes return sec_status_bogus; 1156238106Sdes } else if(sec==sec_status_insecure && qinfo->qtype!=LDNS_RR_TYPE_DS){ 1157238106Sdes verbose(VERB_ALGO, "proveNodata: closest nsec3 is insecure " 1158238106Sdes "delegation."); 1159238106Sdes return sec_status_insecure; 1160238106Sdes } 1161238106Sdes 1162238106Sdes /* Case 3: removed */ 1163238106Sdes 1164238106Sdes /* Case 4: */ 1165238106Sdes log_assert(ce.ce); 1166238106Sdes wc = nsec3_ce_wildcard(env->scratch, ce.ce, ce.ce_len, &wclen); 1167238106Sdes if(wc && find_matching_nsec3(env, flt, ct, wc, wclen, &rrset, &rr)) { 1168238106Sdes /* found wildcard */ 1169238106Sdes if(nsec3_has_type(rrset, rr, qinfo->qtype)) { 1170238106Sdes verbose(VERB_ALGO, "nsec3 nodata proof: matching " 1171238106Sdes "wildcard had qtype, bogus"); 1172238106Sdes return sec_status_bogus; 1173238106Sdes } else if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_CNAME)) { 1174238106Sdes verbose(VERB_ALGO, "nsec3 nodata proof: matching " 1175238106Sdes "wildcard had a CNAME, bogus"); 1176238106Sdes return sec_status_bogus; 1177238106Sdes } 1178238106Sdes if(qinfo->qtype == LDNS_RR_TYPE_DS && qinfo->qname_len != 1 1179238106Sdes && nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA)) { 1180238106Sdes verbose(VERB_ALGO, "nsec3 nodata proof: matching " 1181238106Sdes "wildcard for no DS proof has a SOA, bogus"); 1182238106Sdes return sec_status_bogus; 1183238106Sdes } else if(qinfo->qtype != LDNS_RR_TYPE_DS && 1184238106Sdes nsec3_has_type(rrset, rr, LDNS_RR_TYPE_NS) && 1185238106Sdes !nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA)) { 1186238106Sdes verbose(VERB_ALGO, "nsec3 nodata proof: matching " 1187356345Scy "wildcard is a delegation, bogus"); 1188238106Sdes return sec_status_bogus; 1189238106Sdes } 1190238106Sdes /* everything is peachy keen, except for optout spans */ 1191238106Sdes if(ce.nc_rrset && nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) { 1192238106Sdes verbose(VERB_ALGO, "nsec3 nodata proof: matching " 1193238106Sdes "wildcard is in optout range, insecure"); 1194238106Sdes return sec_status_insecure; 1195238106Sdes } 1196238106Sdes return sec_status_secure; 1197238106Sdes } 1198238106Sdes 1199238106Sdes /* Case 5: */ 1200238106Sdes /* Due to forwarders, cnames, and other collating effects, we 1201238106Sdes * can see the ordinary unsigned data from a zone beneath an 1202238106Sdes * insecure delegation under an optout here */ 1203238106Sdes if(!ce.nc_rrset) { 1204238106Sdes verbose(VERB_ALGO, "nsec3 nodata proof: no next closer nsec3"); 1205238106Sdes return sec_status_bogus; 1206238106Sdes } 1207238106Sdes 1208238106Sdes /* We need to make sure that the covering NSEC3 is opt-out. */ 1209238106Sdes log_assert(ce.nc_rrset); 1210238106Sdes if(!nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) { 1211238106Sdes if(qinfo->qtype == LDNS_RR_TYPE_DS) 1212238106Sdes verbose(VERB_ALGO, "proveNodata: covering NSEC3 was not " 1213238106Sdes "opt-out in an opt-out DS NOERROR/NODATA case."); 1214238106Sdes else verbose(VERB_ALGO, "proveNodata: could not find matching " 1215238106Sdes "NSEC3, nor matching wildcard, nor optout NSEC3 " 1216238106Sdes "-- no more options, bogus."); 1217238106Sdes return sec_status_bogus; 1218238106Sdes } 1219238106Sdes /* RFC5155 section 9.2: if nc has optout then no AD flag set */ 1220238106Sdes return sec_status_insecure; 1221238106Sdes} 1222238106Sdes 1223238106Sdesenum sec_status 1224238106Sdesnsec3_prove_nodata(struct module_env* env, struct val_env* ve, 1225238106Sdes struct ub_packed_rrset_key** list, size_t num, 1226238106Sdes struct query_info* qinfo, struct key_entry_key* kkey) 1227238106Sdes{ 1228356345Scy rbtree_type ct; 1229238106Sdes struct nsec3_filter flt; 1230238106Sdes 1231238106Sdes if(!list || num == 0 || !kkey || !key_entry_isgood(kkey)) 1232238106Sdes return sec_status_bogus; /* no valid NSEC3s, bogus */ 1233238106Sdes rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */ 1234238106Sdes filter_init(&flt, list, num, qinfo); /* init RR iterator */ 1235238106Sdes if(!flt.zone) 1236238106Sdes return sec_status_bogus; /* no RRs */ 1237238106Sdes if(nsec3_iteration_count_high(ve, &flt, kkey)) 1238238106Sdes return sec_status_insecure; /* iteration count too high */ 1239238106Sdes return nsec3_do_prove_nodata(env, &flt, &ct, qinfo); 1240238106Sdes} 1241238106Sdes 1242238106Sdesenum sec_status 1243238106Sdesnsec3_prove_wildcard(struct module_env* env, struct val_env* ve, 1244238106Sdes struct ub_packed_rrset_key** list, size_t num, 1245238106Sdes struct query_info* qinfo, struct key_entry_key* kkey, uint8_t* wc) 1246238106Sdes{ 1247356345Scy rbtree_type ct; 1248238106Sdes struct nsec3_filter flt; 1249238106Sdes struct ce_response ce; 1250238106Sdes uint8_t* nc; 1251238106Sdes size_t nc_len; 1252238106Sdes size_t wclen; 1253238106Sdes (void)dname_count_size_labels(wc, &wclen); 1254238106Sdes 1255238106Sdes if(!list || num == 0 || !kkey || !key_entry_isgood(kkey)) 1256238106Sdes return sec_status_bogus; /* no valid NSEC3s, bogus */ 1257238106Sdes rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */ 1258238106Sdes filter_init(&flt, list, num, qinfo); /* init RR iterator */ 1259238106Sdes if(!flt.zone) 1260238106Sdes return sec_status_bogus; /* no RRs */ 1261238106Sdes if(nsec3_iteration_count_high(ve, &flt, kkey)) 1262238106Sdes return sec_status_insecure; /* iteration count too high */ 1263238106Sdes 1264238106Sdes /* We know what the (purported) closest encloser is by just 1265238106Sdes * looking at the supposed generating wildcard. 1266238106Sdes * The *. has already been removed from the wc name. 1267238106Sdes */ 1268238106Sdes memset(&ce, 0, sizeof(ce)); 1269238106Sdes ce.ce = wc; 1270238106Sdes ce.ce_len = wclen; 1271238106Sdes 1272238106Sdes /* Now we still need to prove that the original data did not exist. 1273238106Sdes * Otherwise, we need to show that the next closer name is covered. */ 1274238106Sdes next_closer(qinfo->qname, qinfo->qname_len, ce.ce, &nc, &nc_len); 1275238106Sdes if(!find_covering_nsec3(env, &flt, &ct, nc, nc_len, 1276238106Sdes &ce.nc_rrset, &ce.nc_rr)) { 1277238106Sdes verbose(VERB_ALGO, "proveWildcard: did not find a covering " 1278238106Sdes "NSEC3 that covered the next closer name."); 1279238106Sdes return sec_status_bogus; 1280238106Sdes } 1281238106Sdes if(ce.nc_rrset && nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) { 1282238106Sdes verbose(VERB_ALGO, "proveWildcard: NSEC3 optout"); 1283238106Sdes return sec_status_insecure; 1284238106Sdes } 1285238106Sdes return sec_status_secure; 1286238106Sdes} 1287238106Sdes 1288238106Sdes/** test if list is all secure */ 1289238106Sdesstatic int 1290238106Sdeslist_is_secure(struct module_env* env, struct val_env* ve, 1291238106Sdes struct ub_packed_rrset_key** list, size_t num, 1292356345Scy struct key_entry_key* kkey, char** reason, struct module_qstate* qstate) 1293238106Sdes{ 1294238106Sdes struct packed_rrset_data* d; 1295238106Sdes size_t i; 1296238106Sdes for(i=0; i<num; i++) { 1297238106Sdes d = (struct packed_rrset_data*)list[i]->entry.data; 1298238106Sdes if(list[i]->rk.type != htons(LDNS_RR_TYPE_NSEC3)) 1299238106Sdes continue; 1300238106Sdes if(d->security == sec_status_secure) 1301238106Sdes continue; 1302238106Sdes rrset_check_sec_status(env->rrset_cache, list[i], *env->now); 1303238106Sdes if(d->security == sec_status_secure) 1304238106Sdes continue; 1305238106Sdes d->security = val_verify_rrset_entry(env, ve, list[i], kkey, 1306356345Scy reason, LDNS_SECTION_AUTHORITY, qstate); 1307238106Sdes if(d->security != sec_status_secure) { 1308238106Sdes verbose(VERB_ALGO, "NSEC3 did not verify"); 1309238106Sdes return 0; 1310238106Sdes } 1311238106Sdes rrset_update_sec_status(env->rrset_cache, list[i], *env->now); 1312238106Sdes } 1313238106Sdes return 1; 1314238106Sdes} 1315238106Sdes 1316238106Sdesenum sec_status 1317238106Sdesnsec3_prove_nods(struct module_env* env, struct val_env* ve, 1318238106Sdes struct ub_packed_rrset_key** list, size_t num, 1319356345Scy struct query_info* qinfo, struct key_entry_key* kkey, char** reason, 1320356345Scy struct module_qstate* qstate) 1321238106Sdes{ 1322356345Scy rbtree_type ct; 1323238106Sdes struct nsec3_filter flt; 1324238106Sdes struct ce_response ce; 1325238106Sdes struct ub_packed_rrset_key* rrset; 1326238106Sdes int rr; 1327238106Sdes log_assert(qinfo->qtype == LDNS_RR_TYPE_DS); 1328238106Sdes 1329238106Sdes if(!list || num == 0 || !kkey || !key_entry_isgood(kkey)) { 1330238106Sdes *reason = "no valid NSEC3s"; 1331238106Sdes return sec_status_bogus; /* no valid NSEC3s, bogus */ 1332238106Sdes } 1333356345Scy if(!list_is_secure(env, ve, list, num, kkey, reason, qstate)) 1334238106Sdes return sec_status_bogus; /* not all NSEC3 records secure */ 1335238106Sdes rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */ 1336238106Sdes filter_init(&flt, list, num, qinfo); /* init RR iterator */ 1337238106Sdes if(!flt.zone) { 1338238106Sdes *reason = "no NSEC3 records"; 1339238106Sdes return sec_status_bogus; /* no RRs */ 1340238106Sdes } 1341238106Sdes if(nsec3_iteration_count_high(ve, &flt, kkey)) 1342238106Sdes return sec_status_insecure; /* iteration count too high */ 1343238106Sdes 1344238106Sdes /* Look for a matching NSEC3 to qname -- this is the normal 1345238106Sdes * NODATA case. */ 1346238106Sdes if(find_matching_nsec3(env, &flt, &ct, qinfo->qname, qinfo->qname_len, 1347238106Sdes &rrset, &rr)) { 1348238106Sdes /* If the matching NSEC3 has the SOA bit set, it is from 1349238106Sdes * the wrong zone (the child instead of the parent). If 1350238106Sdes * it has the DS bit set, then we were lied to. */ 1351238106Sdes if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA) && 1352238106Sdes qinfo->qname_len != 1) { 1353238106Sdes verbose(VERB_ALGO, "nsec3 provenods: NSEC3 is from" 1354238106Sdes " child zone, bogus"); 1355238106Sdes *reason = "NSEC3 from child zone"; 1356238106Sdes return sec_status_bogus; 1357238106Sdes } else if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_DS)) { 1358238106Sdes verbose(VERB_ALGO, "nsec3 provenods: NSEC3 has qtype" 1359238106Sdes " DS, bogus"); 1360238106Sdes *reason = "NSEC3 has DS in bitmap"; 1361238106Sdes return sec_status_bogus; 1362238106Sdes } 1363238106Sdes /* If the NSEC3 RR doesn't have the NS bit set, then 1364238106Sdes * this wasn't a delegation point. */ 1365238106Sdes if(!nsec3_has_type(rrset, rr, LDNS_RR_TYPE_NS)) 1366238106Sdes return sec_status_indeterminate; 1367238106Sdes /* Otherwise, this proves no DS. */ 1368238106Sdes return sec_status_secure; 1369238106Sdes } 1370238106Sdes 1371238106Sdes /* Otherwise, we are probably in the opt-out case. */ 1372238106Sdes if(nsec3_prove_closest_encloser(env, &flt, &ct, qinfo, 1, &ce) 1373238106Sdes != sec_status_secure) { 1374238106Sdes /* an insecure delegation *above* the qname does not prove 1375238106Sdes * anything about this qname exactly, and bogus is bogus */ 1376238106Sdes verbose(VERB_ALGO, "nsec3 provenods: did not match qname, " 1377238106Sdes "nor found a proven closest encloser."); 1378238106Sdes *reason = "no NSEC3 closest encloser"; 1379238106Sdes return sec_status_bogus; 1380238106Sdes } 1381238106Sdes 1382238106Sdes /* robust extra check */ 1383238106Sdes if(!ce.nc_rrset) { 1384238106Sdes verbose(VERB_ALGO, "nsec3 nods proof: no next closer nsec3"); 1385238106Sdes *reason = "no NSEC3 next closer"; 1386238106Sdes return sec_status_bogus; 1387238106Sdes } 1388238106Sdes 1389238106Sdes /* we had the closest encloser proof, then we need to check that the 1390238106Sdes * covering NSEC3 was opt-out -- the proveClosestEncloser step already 1391238106Sdes * checked to see if the closest encloser was a delegation or DNAME. 1392238106Sdes */ 1393238106Sdes log_assert(ce.nc_rrset); 1394238106Sdes if(!nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) { 1395238106Sdes verbose(VERB_ALGO, "nsec3 provenods: covering NSEC3 was not " 1396238106Sdes "opt-out in an opt-out DS NOERROR/NODATA case."); 1397238106Sdes *reason = "covering NSEC3 was not opt-out in an opt-out " 1398238106Sdes "DS NOERROR/NODATA case"; 1399238106Sdes return sec_status_bogus; 1400238106Sdes } 1401238106Sdes /* RFC5155 section 9.2: if nc has optout then no AD flag set */ 1402238106Sdes return sec_status_insecure; 1403238106Sdes} 1404238106Sdes 1405238106Sdesenum sec_status 1406238106Sdesnsec3_prove_nxornodata(struct module_env* env, struct val_env* ve, 1407238106Sdes struct ub_packed_rrset_key** list, size_t num, 1408238106Sdes struct query_info* qinfo, struct key_entry_key* kkey, int* nodata) 1409238106Sdes{ 1410238106Sdes enum sec_status sec, secnx; 1411356345Scy rbtree_type ct; 1412238106Sdes struct nsec3_filter flt; 1413238106Sdes *nodata = 0; 1414238106Sdes 1415238106Sdes if(!list || num == 0 || !kkey || !key_entry_isgood(kkey)) 1416238106Sdes return sec_status_bogus; /* no valid NSEC3s, bogus */ 1417238106Sdes rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */ 1418238106Sdes filter_init(&flt, list, num, qinfo); /* init RR iterator */ 1419238106Sdes if(!flt.zone) 1420238106Sdes return sec_status_bogus; /* no RRs */ 1421238106Sdes if(nsec3_iteration_count_high(ve, &flt, kkey)) 1422238106Sdes return sec_status_insecure; /* iteration count too high */ 1423238106Sdes 1424238106Sdes /* try nxdomain and nodata after another, while keeping the 1425238106Sdes * hash cache intact */ 1426238106Sdes 1427238106Sdes secnx = nsec3_do_prove_nameerror(env, &flt, &ct, qinfo); 1428238106Sdes if(secnx==sec_status_secure) 1429238106Sdes return sec_status_secure; 1430238106Sdes sec = nsec3_do_prove_nodata(env, &flt, &ct, qinfo); 1431238106Sdes if(sec==sec_status_secure) { 1432238106Sdes *nodata = 1; 1433238106Sdes } else if(sec == sec_status_insecure) { 1434238106Sdes *nodata = 1; 1435238106Sdes } else if(secnx == sec_status_insecure) { 1436238106Sdes sec = sec_status_insecure; 1437238106Sdes } 1438238106Sdes return sec; 1439238106Sdes} 1440