1238106Sdes/* 2294190Sdes * 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 24269257Sdes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25269257Sdes * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26269257Sdes * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27269257Sdes * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28269257Sdes * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29269257Sdes * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30269257Sdes * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31269257Sdes * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32269257Sdes * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33269257Sdes * 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 41294190Sdes * 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" 46294190Sdes#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" 59291767Sdes#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 */ 65269257Sdesint 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 */ 71269257Sdesint 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; 257269257Sdes 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. 367294190Sdes * @param rrsetnum: can be undefined on call, initialised. 368294190Sdes * @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); 523238106Sdes if(s1len != s2len) { 524238106Sdes if(s1len < s2len) 525238106Sdes return -1; 526238106Sdes return 1; 527238106Sdes } 528238106Sdes return memcmp(s1, s2, s1len); 529238106Sdes} 530238106Sdes 531238106Sdessize_t 532269257Sdesnsec3_get_hashed(sldns_buffer* buf, uint8_t* nm, size_t nmlen, int algo, 533238106Sdes size_t iter, uint8_t* salt, size_t saltlen, uint8_t* res, size_t max) 534238106Sdes{ 535238106Sdes size_t i, hash_len; 536238106Sdes /* prepare buffer for first iteration */ 537269257Sdes sldns_buffer_clear(buf); 538269257Sdes sldns_buffer_write(buf, nm, nmlen); 539269257Sdes query_dname_tolower(sldns_buffer_begin(buf)); 540269257Sdes sldns_buffer_write(buf, salt, saltlen); 541269257Sdes sldns_buffer_flip(buf); 542294190Sdes hash_len = nsec3_hash_algo_size_supported(algo); 543294190Sdes if(hash_len == 0) { 544294190Sdes log_err("nsec3 hash of unknown algo %d", algo); 545294190Sdes return 0; 546294190Sdes } 547294190Sdes if(hash_len > max) 548294190Sdes return 0; 549294190Sdes if(!secalgo_nsec3_hash(algo, (unsigned char*)sldns_buffer_begin(buf), 550294190Sdes sldns_buffer_limit(buf), (unsigned char*)res)) 551294190Sdes return 0; 552294190Sdes for(i=0; i<iter; i++) { 553294190Sdes sldns_buffer_clear(buf); 554294190Sdes sldns_buffer_write(buf, res, hash_len); 555294190Sdes sldns_buffer_write(buf, salt, saltlen); 556294190Sdes sldns_buffer_flip(buf); 557294190Sdes if(!secalgo_nsec3_hash(algo, 558294190Sdes (unsigned char*)sldns_buffer_begin(buf), 559294190Sdes sldns_buffer_limit(buf), (unsigned char*)res)) 560238106Sdes return 0; 561238106Sdes } 562238106Sdes return hash_len; 563238106Sdes} 564238106Sdes 565238106Sdes/** perform hash of name */ 566238106Sdesstatic int 567269257Sdesnsec3_calc_hash(struct regional* region, sldns_buffer* buf, 568238106Sdes struct nsec3_cached_hash* c) 569238106Sdes{ 570238106Sdes int algo = nsec3_get_algo(c->nsec3, c->rr); 571238106Sdes size_t iter = nsec3_get_iter(c->nsec3, c->rr); 572238106Sdes uint8_t* salt; 573238106Sdes size_t saltlen, i; 574238106Sdes if(!nsec3_get_salt(c->nsec3, c->rr, &salt, &saltlen)) 575238106Sdes return -1; 576238106Sdes /* prepare buffer for first iteration */ 577269257Sdes sldns_buffer_clear(buf); 578269257Sdes sldns_buffer_write(buf, c->dname, c->dname_len); 579269257Sdes query_dname_tolower(sldns_buffer_begin(buf)); 580269257Sdes sldns_buffer_write(buf, salt, saltlen); 581269257Sdes sldns_buffer_flip(buf); 582294190Sdes c->hash_len = nsec3_hash_algo_size_supported(algo); 583294190Sdes if(c->hash_len == 0) { 584294190Sdes log_err("nsec3 hash of unknown algo %d", algo); 585294190Sdes return -1; 586238106Sdes } 587294190Sdes c->hash = (uint8_t*)regional_alloc(region, c->hash_len); 588294190Sdes if(!c->hash) 589294190Sdes return 0; 590294190Sdes (void)secalgo_nsec3_hash(algo, (unsigned char*)sldns_buffer_begin(buf), 591294190Sdes sldns_buffer_limit(buf), (unsigned char*)c->hash); 592294190Sdes for(i=0; i<iter; i++) { 593294190Sdes sldns_buffer_clear(buf); 594294190Sdes sldns_buffer_write(buf, c->hash, c->hash_len); 595294190Sdes sldns_buffer_write(buf, salt, saltlen); 596294190Sdes sldns_buffer_flip(buf); 597294190Sdes (void)secalgo_nsec3_hash(algo, 598294190Sdes (unsigned char*)sldns_buffer_begin(buf), 599294190Sdes sldns_buffer_limit(buf), (unsigned char*)c->hash); 600294190Sdes } 601238106Sdes return 1; 602238106Sdes} 603238106Sdes 604238106Sdes/** perform b32 encoding of hash */ 605238106Sdesstatic int 606269257Sdesnsec3_calc_b32(struct regional* region, sldns_buffer* buf, 607238106Sdes struct nsec3_cached_hash* c) 608238106Sdes{ 609238106Sdes int r; 610269257Sdes sldns_buffer_clear(buf); 611269257Sdes r = sldns_b32_ntop_extended_hex(c->hash, c->hash_len, 612269257Sdes (char*)sldns_buffer_begin(buf), sldns_buffer_limit(buf)); 613238106Sdes if(r < 1) { 614238106Sdes log_err("b32_ntop_extended_hex: error in encoding: %d", r); 615238106Sdes return 0; 616238106Sdes } 617238106Sdes c->b32_len = (size_t)r; 618269257Sdes c->b32 = regional_alloc_init(region, sldns_buffer_begin(buf), 619238106Sdes c->b32_len); 620238106Sdes if(!c->b32) 621238106Sdes return 0; 622238106Sdes return 1; 623238106Sdes} 624238106Sdes 625238106Sdesint 626269257Sdesnsec3_hash_name(rbtree_t* table, struct regional* region, sldns_buffer* buf, 627238106Sdes struct ub_packed_rrset_key* nsec3, int rr, uint8_t* dname, 628238106Sdes size_t dname_len, struct nsec3_cached_hash** hash) 629238106Sdes{ 630238106Sdes struct nsec3_cached_hash* c; 631238106Sdes struct nsec3_cached_hash looki; 632238106Sdes#ifdef UNBOUND_DEBUG 633238106Sdes rbnode_t* n; 634238106Sdes#endif 635238106Sdes int r; 636238106Sdes looki.node.key = &looki; 637238106Sdes looki.nsec3 = nsec3; 638238106Sdes looki.rr = rr; 639238106Sdes looki.dname = dname; 640238106Sdes looki.dname_len = dname_len; 641238106Sdes /* lookup first in cache */ 642238106Sdes c = (struct nsec3_cached_hash*)rbtree_search(table, &looki); 643238106Sdes if(c) { 644238106Sdes *hash = c; 645238106Sdes return 1; 646238106Sdes } 647238106Sdes /* create a new entry */ 648238106Sdes c = (struct nsec3_cached_hash*)regional_alloc(region, sizeof(*c)); 649238106Sdes if(!c) return 0; 650238106Sdes c->node.key = c; 651238106Sdes c->nsec3 = nsec3; 652238106Sdes c->rr = rr; 653238106Sdes c->dname = dname; 654238106Sdes c->dname_len = dname_len; 655238106Sdes r = nsec3_calc_hash(region, buf, c); 656238106Sdes if(r != 1) 657238106Sdes return r; 658238106Sdes r = nsec3_calc_b32(region, buf, c); 659238106Sdes if(r != 1) 660238106Sdes return r; 661238106Sdes#ifdef UNBOUND_DEBUG 662238106Sdes n = 663269257Sdes#else 664269257Sdes (void) 665238106Sdes#endif 666238106Sdes rbtree_insert(table, &c->node); 667238106Sdes log_assert(n); /* cannot be duplicate, just did lookup */ 668238106Sdes *hash = c; 669238106Sdes return 1; 670238106Sdes} 671238106Sdes 672238106Sdes/** 673238106Sdes * compare a label lowercased 674238106Sdes */ 675238106Sdesstatic int 676238106Sdeslabel_compare_lower(uint8_t* lab1, uint8_t* lab2, size_t lablen) 677238106Sdes{ 678238106Sdes size_t i; 679238106Sdes for(i=0; i<lablen; i++) { 680285206Sdes if(tolower((unsigned char)*lab1) != tolower((unsigned char)*lab2)) { 681285206Sdes if(tolower((unsigned char)*lab1) < tolower((unsigned char)*lab2)) 682238106Sdes return -1; 683238106Sdes return 1; 684238106Sdes } 685238106Sdes lab1++; 686238106Sdes lab2++; 687238106Sdes } 688238106Sdes return 0; 689238106Sdes} 690238106Sdes 691238106Sdes/** 692238106Sdes * Compare a hashed name with the owner name of an NSEC3 RRset. 693238106Sdes * @param flt: filter with zone name. 694238106Sdes * @param hash: the hashed name. 695238106Sdes * @param s: rrset with owner name. 696238106Sdes * @return true if matches exactly, false if not. 697238106Sdes */ 698238106Sdesstatic int 699238106Sdesnsec3_hash_matches_owner(struct nsec3_filter* flt, 700238106Sdes struct nsec3_cached_hash* hash, struct ub_packed_rrset_key* s) 701238106Sdes{ 702238106Sdes uint8_t* nm = s->rk.dname; 703238106Sdes /* compare, does hash of name based on params in this NSEC3 704238106Sdes * match the owner name of this NSEC3? 705238106Sdes * name must be: <hashlength>base32 . zone name 706238106Sdes * so; first label must not be root label (not zero length), 707238106Sdes * and match the b32 encoded hash length, 708238106Sdes * and the label content match the b32 encoded hash 709238106Sdes * and the rest must be the zone name. 710238106Sdes */ 711238106Sdes if(hash->b32_len != 0 && (size_t)nm[0] == hash->b32_len && 712238106Sdes label_compare_lower(nm+1, hash->b32, hash->b32_len) == 0 && 713238106Sdes query_dname_compare(nm+(size_t)nm[0]+1, flt->zone) == 0) { 714238106Sdes return 1; 715238106Sdes } 716238106Sdes return 0; 717238106Sdes} 718238106Sdes 719238106Sdes/** 720238106Sdes * Find matching NSEC3 721238106Sdes * Find the NSEC3Record that matches a hash of a name. 722238106Sdes * @param env: module environment with temporary region and buffer. 723238106Sdes * @param flt: the NSEC3 RR filter, contains zone name and RRs. 724238106Sdes * @param ct: cached hashes table. 725238106Sdes * @param nm: name to look for. 726238106Sdes * @param nmlen: length of name. 727238106Sdes * @param rrset: nsec3 that matches is returned here. 728238106Sdes * @param rr: rr number in nsec3 rrset that matches. 729238106Sdes * @return true if a matching NSEC3 is found, false if not. 730238106Sdes */ 731238106Sdesstatic int 732238106Sdesfind_matching_nsec3(struct module_env* env, struct nsec3_filter* flt, 733238106Sdes rbtree_t* ct, uint8_t* nm, size_t nmlen, 734238106Sdes struct ub_packed_rrset_key** rrset, int* rr) 735238106Sdes{ 736238106Sdes size_t i_rs; 737238106Sdes int i_rr; 738238106Sdes struct ub_packed_rrset_key* s; 739238106Sdes struct nsec3_cached_hash* hash; 740238106Sdes int r; 741238106Sdes 742238106Sdes /* this loop skips other-zone and unknown NSEC3s, also non-NSEC3 RRs */ 743238106Sdes for(s=filter_first(flt, &i_rs, &i_rr); s; 744238106Sdes s=filter_next(flt, &i_rs, &i_rr)) { 745238106Sdes /* get name hashed for this NSEC3 RR */ 746238106Sdes r = nsec3_hash_name(ct, env->scratch, env->scratch_buffer, 747238106Sdes s, i_rr, nm, nmlen, &hash); 748238106Sdes if(r == 0) { 749238106Sdes log_err("nsec3: malloc failure"); 750238106Sdes break; /* alloc failure */ 751238106Sdes } else if(r < 0) 752238106Sdes continue; /* malformed NSEC3 */ 753238106Sdes else if(nsec3_hash_matches_owner(flt, hash, s)) { 754238106Sdes *rrset = s; /* rrset with this name */ 755238106Sdes *rr = i_rr; /* matches hash with these parameters */ 756238106Sdes return 1; 757238106Sdes } 758238106Sdes } 759238106Sdes *rrset = NULL; 760238106Sdes *rr = 0; 761238106Sdes return 0; 762238106Sdes} 763238106Sdes 764238106Sdesint 765238106Sdesnsec3_covers(uint8_t* zone, struct nsec3_cached_hash* hash, 766269257Sdes struct ub_packed_rrset_key* rrset, int rr, sldns_buffer* buf) 767238106Sdes{ 768238106Sdes uint8_t* next, *owner; 769238106Sdes size_t nextlen; 770238106Sdes int len; 771238106Sdes if(!nsec3_get_nextowner(rrset, rr, &next, &nextlen)) 772238106Sdes return 0; /* malformed RR proves nothing */ 773238106Sdes 774238106Sdes /* check the owner name is a hashed value . apex 775238106Sdes * base32 encoded values must have equal length. 776238106Sdes * hash_value and next hash value must have equal length. */ 777238106Sdes if(nextlen != hash->hash_len || hash->hash_len==0||hash->b32_len==0|| 778238106Sdes (size_t)*rrset->rk.dname != hash->b32_len || 779238106Sdes query_dname_compare(rrset->rk.dname+1+ 780238106Sdes (size_t)*rrset->rk.dname, zone) != 0) 781238106Sdes return 0; /* bad lengths or owner name */ 782238106Sdes 783238106Sdes /* This is the "normal case: owner < next and owner < hash < next */ 784238106Sdes if(label_compare_lower(rrset->rk.dname+1, hash->b32, 785238106Sdes hash->b32_len) < 0 && 786238106Sdes memcmp(hash->hash, next, nextlen) < 0) 787238106Sdes return 1; 788238106Sdes 789238106Sdes /* convert owner name from text to binary */ 790269257Sdes sldns_buffer_clear(buf); 791269257Sdes owner = sldns_buffer_begin(buf); 792269257Sdes len = sldns_b32_pton_extended_hex((char*)rrset->rk.dname+1, 793269257Sdes hash->b32_len, owner, sldns_buffer_limit(buf)); 794238106Sdes if(len<1) 795238106Sdes return 0; /* bad owner name in some way */ 796238106Sdes if((size_t)len != hash->hash_len || (size_t)len != nextlen) 797238106Sdes return 0; /* wrong length */ 798238106Sdes 799238106Sdes /* this is the end of zone case: next <= owner && 800238106Sdes * (hash > owner || hash < next) 801238106Sdes * this also covers the only-apex case of next==owner. 802238106Sdes */ 803238106Sdes if(memcmp(next, owner, nextlen) <= 0 && 804238106Sdes ( memcmp(hash->hash, owner, nextlen) > 0 || 805238106Sdes memcmp(hash->hash, next, nextlen) < 0)) { 806238106Sdes return 1; 807238106Sdes } 808238106Sdes return 0; 809238106Sdes} 810238106Sdes 811238106Sdes/** 812238106Sdes * findCoveringNSEC3 813238106Sdes * Given a name, find a covering NSEC3 from among a list of NSEC3s. 814238106Sdes * 815238106Sdes * @param env: module environment with temporary region and buffer. 816238106Sdes * @param flt: the NSEC3 RR filter, contains zone name and RRs. 817238106Sdes * @param ct: cached hashes table. 818238106Sdes * @param nm: name to check if covered. 819238106Sdes * @param nmlen: length of name. 820238106Sdes * @param rrset: covering NSEC3 rrset is returned here. 821238106Sdes * @param rr: rr of cover is returned here. 822238106Sdes * @return true if a covering NSEC3 is found, false if not. 823238106Sdes */ 824238106Sdesstatic int 825238106Sdesfind_covering_nsec3(struct module_env* env, struct nsec3_filter* flt, 826238106Sdes rbtree_t* ct, uint8_t* nm, size_t nmlen, 827238106Sdes struct ub_packed_rrset_key** rrset, int* rr) 828238106Sdes{ 829238106Sdes size_t i_rs; 830238106Sdes int i_rr; 831238106Sdes struct ub_packed_rrset_key* s; 832238106Sdes struct nsec3_cached_hash* hash; 833238106Sdes int r; 834238106Sdes 835238106Sdes /* this loop skips other-zone and unknown NSEC3s, also non-NSEC3 RRs */ 836238106Sdes for(s=filter_first(flt, &i_rs, &i_rr); s; 837238106Sdes s=filter_next(flt, &i_rs, &i_rr)) { 838238106Sdes /* get name hashed for this NSEC3 RR */ 839238106Sdes r = nsec3_hash_name(ct, env->scratch, env->scratch_buffer, 840238106Sdes s, i_rr, nm, nmlen, &hash); 841238106Sdes if(r == 0) { 842238106Sdes log_err("nsec3: malloc failure"); 843238106Sdes break; /* alloc failure */ 844238106Sdes } else if(r < 0) 845238106Sdes continue; /* malformed NSEC3 */ 846238106Sdes else if(nsec3_covers(flt->zone, hash, s, i_rr, 847238106Sdes env->scratch_buffer)) { 848238106Sdes *rrset = s; /* rrset with this name */ 849238106Sdes *rr = i_rr; /* covers hash with these parameters */ 850238106Sdes return 1; 851238106Sdes } 852238106Sdes } 853238106Sdes *rrset = NULL; 854238106Sdes *rr = 0; 855238106Sdes return 0; 856238106Sdes} 857238106Sdes 858238106Sdes/** 859238106Sdes * findClosestEncloser 860238106Sdes * Given a name and a list of NSEC3s, find the candidate closest encloser. 861238106Sdes * This will be the first ancestor of 'name' (including itself) to have a 862238106Sdes * matching NSEC3 RR. 863238106Sdes * @param env: module environment with temporary region and buffer. 864238106Sdes * @param flt: the NSEC3 RR filter, contains zone name and RRs. 865238106Sdes * @param ct: cached hashes table. 866238106Sdes * @param qinfo: query that is verified for. 867238106Sdes * @param ce: closest encloser information is returned in here. 868238106Sdes * @return true if a closest encloser candidate is found, false if not. 869238106Sdes */ 870238106Sdesstatic int 871238106Sdesnsec3_find_closest_encloser(struct module_env* env, struct nsec3_filter* flt, 872238106Sdes rbtree_t* ct, struct query_info* qinfo, struct ce_response* ce) 873238106Sdes{ 874238106Sdes uint8_t* nm = qinfo->qname; 875238106Sdes size_t nmlen = qinfo->qname_len; 876238106Sdes 877238106Sdes /* This scans from longest name to shortest, so the first match 878238106Sdes * we find is the only viable candidate. */ 879238106Sdes 880238106Sdes /* (David:) FIXME: modify so that the NSEC3 matching the zone apex need 881238106Sdes * not be present. (Mark Andrews idea). 882238106Sdes * (Wouter:) But make sure you check for DNAME bit in zone apex, 883238106Sdes * if the NSEC3 you find is the only NSEC3 in the zone, then this 884238106Sdes * may be the case. */ 885238106Sdes 886238106Sdes while(dname_subdomain_c(nm, flt->zone)) { 887238106Sdes if(find_matching_nsec3(env, flt, ct, nm, nmlen, 888238106Sdes &ce->ce_rrset, &ce->ce_rr)) { 889238106Sdes ce->ce = nm; 890238106Sdes ce->ce_len = nmlen; 891238106Sdes return 1; 892238106Sdes } 893238106Sdes dname_remove_label(&nm, &nmlen); 894238106Sdes } 895238106Sdes return 0; 896238106Sdes} 897238106Sdes 898238106Sdes/** 899238106Sdes * Given a qname and its proven closest encloser, calculate the "next 900238106Sdes * closest" name. Basically, this is the name that is one label longer than 901238106Sdes * the closest encloser that is still a subdomain of qname. 902238106Sdes * 903238106Sdes * @param qname: query name. 904238106Sdes * @param qnamelen: length of qname. 905238106Sdes * @param ce: closest encloser 906238106Sdes * @param nm: result name. 907238106Sdes * @param nmlen: length of nm. 908238106Sdes */ 909238106Sdesstatic void 910238106Sdesnext_closer(uint8_t* qname, size_t qnamelen, uint8_t* ce, 911238106Sdes uint8_t** nm, size_t* nmlen) 912238106Sdes{ 913238106Sdes int strip = dname_count_labels(qname) - dname_count_labels(ce) -1; 914238106Sdes *nm = qname; 915238106Sdes *nmlen = qnamelen; 916238106Sdes if(strip>0) 917238106Sdes dname_remove_labels(nm, nmlen, strip); 918238106Sdes} 919238106Sdes 920238106Sdes/** 921238106Sdes * proveClosestEncloser 922238106Sdes * Given a List of nsec3 RRs, find and prove the closest encloser to qname. 923238106Sdes * @param env: module environment with temporary region and buffer. 924238106Sdes * @param flt: the NSEC3 RR filter, contains zone name and RRs. 925238106Sdes * @param ct: cached hashes table. 926238106Sdes * @param qinfo: query that is verified for. 927238106Sdes * @param prove_does_not_exist: If true, then if the closest encloser 928238106Sdes * turns out to be qname, then null is returned. 929238106Sdes * If set true, and the return value is true, then you can be 930238106Sdes * certain that the ce.nc_rrset and ce.nc_rr are set properly. 931238106Sdes * @param ce: closest encloser information is returned in here. 932238106Sdes * @return bogus if no closest encloser could be proven. 933238106Sdes * secure if a closest encloser could be proven, ce is set. 934238106Sdes * insecure if the closest-encloser candidate turns out to prove 935238106Sdes * that an insecure delegation exists above the qname. 936238106Sdes */ 937238106Sdesstatic enum sec_status 938238106Sdesnsec3_prove_closest_encloser(struct module_env* env, struct nsec3_filter* flt, 939238106Sdes rbtree_t* ct, struct query_info* qinfo, int prove_does_not_exist, 940238106Sdes struct ce_response* ce) 941238106Sdes{ 942238106Sdes uint8_t* nc; 943238106Sdes size_t nc_len; 944238106Sdes /* robust: clean out ce, in case it gets abused later */ 945238106Sdes memset(ce, 0, sizeof(*ce)); 946238106Sdes 947238106Sdes if(!nsec3_find_closest_encloser(env, flt, ct, qinfo, ce)) { 948238106Sdes verbose(VERB_ALGO, "nsec3 proveClosestEncloser: could " 949238106Sdes "not find a candidate for the closest encloser."); 950238106Sdes return sec_status_bogus; 951238106Sdes } 952238106Sdes log_nametypeclass(VERB_ALGO, "ce candidate", ce->ce, 0, 0); 953238106Sdes 954238106Sdes if(query_dname_compare(ce->ce, qinfo->qname) == 0) { 955238106Sdes if(prove_does_not_exist) { 956238106Sdes verbose(VERB_ALGO, "nsec3 proveClosestEncloser: " 957238106Sdes "proved that qname existed, bad"); 958238106Sdes return sec_status_bogus; 959238106Sdes } 960238106Sdes /* otherwise, we need to nothing else to prove that qname 961238106Sdes * is its own closest encloser. */ 962238106Sdes return sec_status_secure; 963238106Sdes } 964238106Sdes 965238106Sdes /* If the closest encloser is actually a delegation, then the 966238106Sdes * response should have been a referral. If it is a DNAME, then 967238106Sdes * it should have been a DNAME response. */ 968238106Sdes if(nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_NS) && 969238106Sdes !nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_SOA)) { 970238106Sdes if(!nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_DS)) { 971238106Sdes verbose(VERB_ALGO, "nsec3 proveClosestEncloser: " 972238106Sdes "closest encloser is insecure delegation"); 973238106Sdes return sec_status_insecure; 974238106Sdes } 975238106Sdes verbose(VERB_ALGO, "nsec3 proveClosestEncloser: closest " 976238106Sdes "encloser was a delegation, bad"); 977238106Sdes return sec_status_bogus; 978238106Sdes } 979238106Sdes if(nsec3_has_type(ce->ce_rrset, ce->ce_rr, LDNS_RR_TYPE_DNAME)) { 980238106Sdes verbose(VERB_ALGO, "nsec3 proveClosestEncloser: closest " 981238106Sdes "encloser was a DNAME, bad"); 982238106Sdes return sec_status_bogus; 983238106Sdes } 984238106Sdes 985238106Sdes /* Otherwise, we need to show that the next closer name is covered. */ 986238106Sdes next_closer(qinfo->qname, qinfo->qname_len, ce->ce, &nc, &nc_len); 987238106Sdes if(!find_covering_nsec3(env, flt, ct, nc, nc_len, 988238106Sdes &ce->nc_rrset, &ce->nc_rr)) { 989238106Sdes verbose(VERB_ALGO, "nsec3: Could not find proof that the " 990238106Sdes "candidate encloser was the closest encloser"); 991238106Sdes return sec_status_bogus; 992238106Sdes } 993238106Sdes return sec_status_secure; 994238106Sdes} 995238106Sdes 996238106Sdes/** allocate a wildcard for the closest encloser */ 997238106Sdesstatic uint8_t* 998238106Sdesnsec3_ce_wildcard(struct regional* region, uint8_t* ce, size_t celen, 999238106Sdes size_t* len) 1000238106Sdes{ 1001238106Sdes uint8_t* nm; 1002238106Sdes if(celen > LDNS_MAX_DOMAINLEN - 2) 1003238106Sdes return 0; /* too long */ 1004238106Sdes nm = (uint8_t*)regional_alloc(region, celen+2); 1005238106Sdes if(!nm) { 1006238106Sdes log_err("nsec3 wildcard: out of memory"); 1007238106Sdes return 0; /* alloc failure */ 1008238106Sdes } 1009238106Sdes nm[0] = 1; 1010238106Sdes nm[1] = (uint8_t)'*'; /* wildcard label */ 1011238106Sdes memmove(nm+2, ce, celen); 1012238106Sdes *len = celen+2; 1013238106Sdes return nm; 1014238106Sdes} 1015238106Sdes 1016238106Sdes/** Do the name error proof */ 1017238106Sdesstatic enum sec_status 1018238106Sdesnsec3_do_prove_nameerror(struct module_env* env, struct nsec3_filter* flt, 1019238106Sdes rbtree_t* ct, struct query_info* qinfo) 1020238106Sdes{ 1021238106Sdes struct ce_response ce; 1022238106Sdes uint8_t* wc; 1023238106Sdes size_t wclen; 1024238106Sdes struct ub_packed_rrset_key* wc_rrset; 1025238106Sdes int wc_rr; 1026238106Sdes enum sec_status sec; 1027238106Sdes 1028238106Sdes /* First locate and prove the closest encloser to qname. We will 1029238106Sdes * use the variant that fails if the closest encloser turns out 1030238106Sdes * to be qname. */ 1031238106Sdes sec = nsec3_prove_closest_encloser(env, flt, ct, qinfo, 1, &ce); 1032238106Sdes if(sec != sec_status_secure) { 1033238106Sdes if(sec == sec_status_bogus) 1034238106Sdes verbose(VERB_ALGO, "nsec3 nameerror proof: failed " 1035238106Sdes "to prove a closest encloser"); 1036238106Sdes else verbose(VERB_ALGO, "nsec3 nameerror proof: closest " 1037238106Sdes "nsec3 is an insecure delegation"); 1038238106Sdes return sec; 1039238106Sdes } 1040238106Sdes log_nametypeclass(VERB_ALGO, "nsec3 namerror: proven ce=", ce.ce,0,0); 1041238106Sdes 1042238106Sdes /* At this point, we know that qname does not exist. Now we need 1043238106Sdes * to prove that the wildcard does not exist. */ 1044238106Sdes log_assert(ce.ce); 1045238106Sdes wc = nsec3_ce_wildcard(env->scratch, ce.ce, ce.ce_len, &wclen); 1046238106Sdes if(!wc || !find_covering_nsec3(env, flt, ct, wc, wclen, 1047238106Sdes &wc_rrset, &wc_rr)) { 1048238106Sdes verbose(VERB_ALGO, "nsec3 nameerror proof: could not prove " 1049238106Sdes "that the applicable wildcard did not exist."); 1050238106Sdes return sec_status_bogus; 1051238106Sdes } 1052238106Sdes 1053238106Sdes if(ce.nc_rrset && nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) { 1054238106Sdes verbose(VERB_ALGO, "nsec3 nameerror proof: nc has optout"); 1055238106Sdes return sec_status_insecure; 1056238106Sdes } 1057238106Sdes return sec_status_secure; 1058238106Sdes} 1059238106Sdes 1060238106Sdesenum sec_status 1061238106Sdesnsec3_prove_nameerror(struct module_env* env, struct val_env* ve, 1062238106Sdes struct ub_packed_rrset_key** list, size_t num, 1063238106Sdes struct query_info* qinfo, struct key_entry_key* kkey) 1064238106Sdes{ 1065238106Sdes rbtree_t ct; 1066238106Sdes struct nsec3_filter flt; 1067238106Sdes 1068238106Sdes if(!list || num == 0 || !kkey || !key_entry_isgood(kkey)) 1069238106Sdes return sec_status_bogus; /* no valid NSEC3s, bogus */ 1070238106Sdes rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */ 1071238106Sdes filter_init(&flt, list, num, qinfo); /* init RR iterator */ 1072238106Sdes if(!flt.zone) 1073238106Sdes return sec_status_bogus; /* no RRs */ 1074238106Sdes if(nsec3_iteration_count_high(ve, &flt, kkey)) 1075238106Sdes return sec_status_insecure; /* iteration count too high */ 1076238106Sdes log_nametypeclass(VERB_ALGO, "start nsec3 nameerror proof, zone", 1077238106Sdes flt.zone, 0, 0); 1078238106Sdes return nsec3_do_prove_nameerror(env, &flt, &ct, qinfo); 1079238106Sdes} 1080238106Sdes 1081238106Sdes/* 1082238106Sdes * No code to handle qtype=NSEC3 specially. 1083238106Sdes * This existed in early drafts, but was later (-05) removed. 1084238106Sdes */ 1085238106Sdes 1086238106Sdes/** Do the nodata proof */ 1087238106Sdesstatic enum sec_status 1088238106Sdesnsec3_do_prove_nodata(struct module_env* env, struct nsec3_filter* flt, 1089238106Sdes rbtree_t* ct, struct query_info* qinfo) 1090238106Sdes{ 1091238106Sdes struct ce_response ce; 1092238106Sdes uint8_t* wc; 1093238106Sdes size_t wclen; 1094238106Sdes struct ub_packed_rrset_key* rrset; 1095238106Sdes int rr; 1096238106Sdes enum sec_status sec; 1097238106Sdes 1098238106Sdes if(find_matching_nsec3(env, flt, ct, qinfo->qname, qinfo->qname_len, 1099238106Sdes &rrset, &rr)) { 1100238106Sdes /* cases 1 and 2 */ 1101238106Sdes if(nsec3_has_type(rrset, rr, qinfo->qtype)) { 1102238106Sdes verbose(VERB_ALGO, "proveNodata: Matching NSEC3 " 1103238106Sdes "proved that type existed, bogus"); 1104238106Sdes return sec_status_bogus; 1105238106Sdes } else if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_CNAME)) { 1106238106Sdes verbose(VERB_ALGO, "proveNodata: Matching NSEC3 " 1107238106Sdes "proved that a CNAME existed, bogus"); 1108238106Sdes return sec_status_bogus; 1109238106Sdes } 1110238106Sdes 1111238106Sdes /* 1112238106Sdes * If type DS: filter_init zone find already found a parent 1113238106Sdes * zone, so this nsec3 is from a parent zone. 1114238106Sdes * o can be not a delegation (unusual query for normal name, 1115238106Sdes * no DS anyway, but we can verify that). 1116238106Sdes * o can be a delegation (which is the usual DS check). 1117238106Sdes * o may not have the SOA bit set (only the top of the 1118238106Sdes * zone, which must have been above the name, has that). 1119238106Sdes * Except for the root; which is checked by itself. 1120238106Sdes * 1121238106Sdes * If not type DS: matching nsec3 must not be a delegation. 1122238106Sdes */ 1123238106Sdes if(qinfo->qtype == LDNS_RR_TYPE_DS && qinfo->qname_len != 1 1124249141Sdes && nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA) && 1125249141Sdes !dname_is_root(qinfo->qname)) { 1126238106Sdes verbose(VERB_ALGO, "proveNodata: apex NSEC3 " 1127238106Sdes "abused for no DS proof, bogus"); 1128238106Sdes return sec_status_bogus; 1129238106Sdes } else if(qinfo->qtype != LDNS_RR_TYPE_DS && 1130238106Sdes nsec3_has_type(rrset, rr, LDNS_RR_TYPE_NS) && 1131238106Sdes !nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA)) { 1132238106Sdes if(!nsec3_has_type(rrset, rr, LDNS_RR_TYPE_DS)) { 1133238106Sdes verbose(VERB_ALGO, "proveNodata: matching " 1134238106Sdes "NSEC3 is insecure delegation"); 1135238106Sdes return sec_status_insecure; 1136238106Sdes } 1137238106Sdes verbose(VERB_ALGO, "proveNodata: matching " 1138238106Sdes "NSEC3 is a delegation, bogus"); 1139238106Sdes return sec_status_bogus; 1140238106Sdes } 1141238106Sdes return sec_status_secure; 1142238106Sdes } 1143238106Sdes 1144238106Sdes /* For cases 3 - 5, we need the proven closest encloser, and it 1145238106Sdes * can't match qname. Although, at this point, we know that it 1146238106Sdes * won't since we just checked that. */ 1147238106Sdes sec = nsec3_prove_closest_encloser(env, flt, ct, qinfo, 1, &ce); 1148238106Sdes if(sec == sec_status_bogus) { 1149238106Sdes verbose(VERB_ALGO, "proveNodata: did not match qname, " 1150238106Sdes "nor found a proven closest encloser."); 1151238106Sdes return sec_status_bogus; 1152238106Sdes } else if(sec==sec_status_insecure && qinfo->qtype!=LDNS_RR_TYPE_DS){ 1153238106Sdes verbose(VERB_ALGO, "proveNodata: closest nsec3 is insecure " 1154238106Sdes "delegation."); 1155238106Sdes return sec_status_insecure; 1156238106Sdes } 1157238106Sdes 1158238106Sdes /* Case 3: removed */ 1159238106Sdes 1160238106Sdes /* Case 4: */ 1161238106Sdes log_assert(ce.ce); 1162238106Sdes wc = nsec3_ce_wildcard(env->scratch, ce.ce, ce.ce_len, &wclen); 1163238106Sdes if(wc && find_matching_nsec3(env, flt, ct, wc, wclen, &rrset, &rr)) { 1164238106Sdes /* found wildcard */ 1165238106Sdes if(nsec3_has_type(rrset, rr, qinfo->qtype)) { 1166238106Sdes verbose(VERB_ALGO, "nsec3 nodata proof: matching " 1167238106Sdes "wildcard had qtype, bogus"); 1168238106Sdes return sec_status_bogus; 1169238106Sdes } else if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_CNAME)) { 1170238106Sdes verbose(VERB_ALGO, "nsec3 nodata proof: matching " 1171238106Sdes "wildcard had a CNAME, bogus"); 1172238106Sdes return sec_status_bogus; 1173238106Sdes } 1174238106Sdes if(qinfo->qtype == LDNS_RR_TYPE_DS && qinfo->qname_len != 1 1175238106Sdes && nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA)) { 1176238106Sdes verbose(VERB_ALGO, "nsec3 nodata proof: matching " 1177238106Sdes "wildcard for no DS proof has a SOA, bogus"); 1178238106Sdes return sec_status_bogus; 1179238106Sdes } else if(qinfo->qtype != LDNS_RR_TYPE_DS && 1180238106Sdes nsec3_has_type(rrset, rr, LDNS_RR_TYPE_NS) && 1181238106Sdes !nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA)) { 1182238106Sdes verbose(VERB_ALGO, "nsec3 nodata proof: matching " 1183238106Sdes "wilcard is a delegation, bogus"); 1184238106Sdes return sec_status_bogus; 1185238106Sdes } 1186238106Sdes /* everything is peachy keen, except for optout spans */ 1187238106Sdes if(ce.nc_rrset && nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) { 1188238106Sdes verbose(VERB_ALGO, "nsec3 nodata proof: matching " 1189238106Sdes "wildcard is in optout range, insecure"); 1190238106Sdes return sec_status_insecure; 1191238106Sdes } 1192238106Sdes return sec_status_secure; 1193238106Sdes } 1194238106Sdes 1195238106Sdes /* Case 5: */ 1196238106Sdes /* Due to forwarders, cnames, and other collating effects, we 1197238106Sdes * can see the ordinary unsigned data from a zone beneath an 1198238106Sdes * insecure delegation under an optout here */ 1199238106Sdes if(!ce.nc_rrset) { 1200238106Sdes verbose(VERB_ALGO, "nsec3 nodata proof: no next closer nsec3"); 1201238106Sdes return sec_status_bogus; 1202238106Sdes } 1203238106Sdes 1204238106Sdes /* We need to make sure that the covering NSEC3 is opt-out. */ 1205238106Sdes log_assert(ce.nc_rrset); 1206238106Sdes if(!nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) { 1207238106Sdes if(qinfo->qtype == LDNS_RR_TYPE_DS) 1208238106Sdes verbose(VERB_ALGO, "proveNodata: covering NSEC3 was not " 1209238106Sdes "opt-out in an opt-out DS NOERROR/NODATA case."); 1210238106Sdes else verbose(VERB_ALGO, "proveNodata: could not find matching " 1211238106Sdes "NSEC3, nor matching wildcard, nor optout NSEC3 " 1212238106Sdes "-- no more options, bogus."); 1213238106Sdes return sec_status_bogus; 1214238106Sdes } 1215238106Sdes /* RFC5155 section 9.2: if nc has optout then no AD flag set */ 1216238106Sdes return sec_status_insecure; 1217238106Sdes} 1218238106Sdes 1219238106Sdesenum sec_status 1220238106Sdesnsec3_prove_nodata(struct module_env* env, struct val_env* ve, 1221238106Sdes struct ub_packed_rrset_key** list, size_t num, 1222238106Sdes struct query_info* qinfo, struct key_entry_key* kkey) 1223238106Sdes{ 1224238106Sdes rbtree_t ct; 1225238106Sdes struct nsec3_filter flt; 1226238106Sdes 1227238106Sdes if(!list || num == 0 || !kkey || !key_entry_isgood(kkey)) 1228238106Sdes return sec_status_bogus; /* no valid NSEC3s, bogus */ 1229238106Sdes rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */ 1230238106Sdes filter_init(&flt, list, num, qinfo); /* init RR iterator */ 1231238106Sdes if(!flt.zone) 1232238106Sdes return sec_status_bogus; /* no RRs */ 1233238106Sdes if(nsec3_iteration_count_high(ve, &flt, kkey)) 1234238106Sdes return sec_status_insecure; /* iteration count too high */ 1235238106Sdes return nsec3_do_prove_nodata(env, &flt, &ct, qinfo); 1236238106Sdes} 1237238106Sdes 1238238106Sdesenum sec_status 1239238106Sdesnsec3_prove_wildcard(struct module_env* env, struct val_env* ve, 1240238106Sdes struct ub_packed_rrset_key** list, size_t num, 1241238106Sdes struct query_info* qinfo, struct key_entry_key* kkey, uint8_t* wc) 1242238106Sdes{ 1243238106Sdes rbtree_t ct; 1244238106Sdes struct nsec3_filter flt; 1245238106Sdes struct ce_response ce; 1246238106Sdes uint8_t* nc; 1247238106Sdes size_t nc_len; 1248238106Sdes size_t wclen; 1249238106Sdes (void)dname_count_size_labels(wc, &wclen); 1250238106Sdes 1251238106Sdes if(!list || num == 0 || !kkey || !key_entry_isgood(kkey)) 1252238106Sdes return sec_status_bogus; /* no valid NSEC3s, bogus */ 1253238106Sdes rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */ 1254238106Sdes filter_init(&flt, list, num, qinfo); /* init RR iterator */ 1255238106Sdes if(!flt.zone) 1256238106Sdes return sec_status_bogus; /* no RRs */ 1257238106Sdes if(nsec3_iteration_count_high(ve, &flt, kkey)) 1258238106Sdes return sec_status_insecure; /* iteration count too high */ 1259238106Sdes 1260238106Sdes /* We know what the (purported) closest encloser is by just 1261238106Sdes * looking at the supposed generating wildcard. 1262238106Sdes * The *. has already been removed from the wc name. 1263238106Sdes */ 1264238106Sdes memset(&ce, 0, sizeof(ce)); 1265238106Sdes ce.ce = wc; 1266238106Sdes ce.ce_len = wclen; 1267238106Sdes 1268238106Sdes /* Now we still need to prove that the original data did not exist. 1269238106Sdes * Otherwise, we need to show that the next closer name is covered. */ 1270238106Sdes next_closer(qinfo->qname, qinfo->qname_len, ce.ce, &nc, &nc_len); 1271238106Sdes if(!find_covering_nsec3(env, &flt, &ct, nc, nc_len, 1272238106Sdes &ce.nc_rrset, &ce.nc_rr)) { 1273238106Sdes verbose(VERB_ALGO, "proveWildcard: did not find a covering " 1274238106Sdes "NSEC3 that covered the next closer name."); 1275238106Sdes return sec_status_bogus; 1276238106Sdes } 1277238106Sdes if(ce.nc_rrset && nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) { 1278238106Sdes verbose(VERB_ALGO, "proveWildcard: NSEC3 optout"); 1279238106Sdes return sec_status_insecure; 1280238106Sdes } 1281238106Sdes return sec_status_secure; 1282238106Sdes} 1283238106Sdes 1284238106Sdes/** test if list is all secure */ 1285238106Sdesstatic int 1286238106Sdeslist_is_secure(struct module_env* env, struct val_env* ve, 1287238106Sdes struct ub_packed_rrset_key** list, size_t num, 1288238106Sdes struct key_entry_key* kkey, char** reason) 1289238106Sdes{ 1290238106Sdes struct packed_rrset_data* d; 1291238106Sdes size_t i; 1292238106Sdes for(i=0; i<num; i++) { 1293238106Sdes d = (struct packed_rrset_data*)list[i]->entry.data; 1294238106Sdes if(list[i]->rk.type != htons(LDNS_RR_TYPE_NSEC3)) 1295238106Sdes continue; 1296238106Sdes if(d->security == sec_status_secure) 1297238106Sdes continue; 1298238106Sdes rrset_check_sec_status(env->rrset_cache, list[i], *env->now); 1299238106Sdes if(d->security == sec_status_secure) 1300238106Sdes continue; 1301238106Sdes d->security = val_verify_rrset_entry(env, ve, list[i], kkey, 1302238106Sdes reason); 1303238106Sdes if(d->security != sec_status_secure) { 1304238106Sdes verbose(VERB_ALGO, "NSEC3 did not verify"); 1305238106Sdes return 0; 1306238106Sdes } 1307238106Sdes rrset_update_sec_status(env->rrset_cache, list[i], *env->now); 1308238106Sdes } 1309238106Sdes return 1; 1310238106Sdes} 1311238106Sdes 1312238106Sdesenum sec_status 1313238106Sdesnsec3_prove_nods(struct module_env* env, struct val_env* ve, 1314238106Sdes struct ub_packed_rrset_key** list, size_t num, 1315238106Sdes struct query_info* qinfo, struct key_entry_key* kkey, char** reason) 1316238106Sdes{ 1317238106Sdes rbtree_t ct; 1318238106Sdes struct nsec3_filter flt; 1319238106Sdes struct ce_response ce; 1320238106Sdes struct ub_packed_rrset_key* rrset; 1321238106Sdes int rr; 1322238106Sdes log_assert(qinfo->qtype == LDNS_RR_TYPE_DS); 1323238106Sdes 1324238106Sdes if(!list || num == 0 || !kkey || !key_entry_isgood(kkey)) { 1325238106Sdes *reason = "no valid NSEC3s"; 1326238106Sdes return sec_status_bogus; /* no valid NSEC3s, bogus */ 1327238106Sdes } 1328238106Sdes if(!list_is_secure(env, ve, list, num, kkey, reason)) 1329238106Sdes return sec_status_bogus; /* not all NSEC3 records secure */ 1330238106Sdes rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */ 1331238106Sdes filter_init(&flt, list, num, qinfo); /* init RR iterator */ 1332238106Sdes if(!flt.zone) { 1333238106Sdes *reason = "no NSEC3 records"; 1334238106Sdes return sec_status_bogus; /* no RRs */ 1335238106Sdes } 1336238106Sdes if(nsec3_iteration_count_high(ve, &flt, kkey)) 1337238106Sdes return sec_status_insecure; /* iteration count too high */ 1338238106Sdes 1339238106Sdes /* Look for a matching NSEC3 to qname -- this is the normal 1340238106Sdes * NODATA case. */ 1341238106Sdes if(find_matching_nsec3(env, &flt, &ct, qinfo->qname, qinfo->qname_len, 1342238106Sdes &rrset, &rr)) { 1343238106Sdes /* If the matching NSEC3 has the SOA bit set, it is from 1344238106Sdes * the wrong zone (the child instead of the parent). If 1345238106Sdes * it has the DS bit set, then we were lied to. */ 1346238106Sdes if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_SOA) && 1347238106Sdes qinfo->qname_len != 1) { 1348238106Sdes verbose(VERB_ALGO, "nsec3 provenods: NSEC3 is from" 1349238106Sdes " child zone, bogus"); 1350238106Sdes *reason = "NSEC3 from child zone"; 1351238106Sdes return sec_status_bogus; 1352238106Sdes } else if(nsec3_has_type(rrset, rr, LDNS_RR_TYPE_DS)) { 1353238106Sdes verbose(VERB_ALGO, "nsec3 provenods: NSEC3 has qtype" 1354238106Sdes " DS, bogus"); 1355238106Sdes *reason = "NSEC3 has DS in bitmap"; 1356238106Sdes return sec_status_bogus; 1357238106Sdes } 1358238106Sdes /* If the NSEC3 RR doesn't have the NS bit set, then 1359238106Sdes * this wasn't a delegation point. */ 1360238106Sdes if(!nsec3_has_type(rrset, rr, LDNS_RR_TYPE_NS)) 1361238106Sdes return sec_status_indeterminate; 1362238106Sdes /* Otherwise, this proves no DS. */ 1363238106Sdes return sec_status_secure; 1364238106Sdes } 1365238106Sdes 1366238106Sdes /* Otherwise, we are probably in the opt-out case. */ 1367238106Sdes if(nsec3_prove_closest_encloser(env, &flt, &ct, qinfo, 1, &ce) 1368238106Sdes != sec_status_secure) { 1369238106Sdes /* an insecure delegation *above* the qname does not prove 1370238106Sdes * anything about this qname exactly, and bogus is bogus */ 1371238106Sdes verbose(VERB_ALGO, "nsec3 provenods: did not match qname, " 1372238106Sdes "nor found a proven closest encloser."); 1373238106Sdes *reason = "no NSEC3 closest encloser"; 1374238106Sdes return sec_status_bogus; 1375238106Sdes } 1376238106Sdes 1377238106Sdes /* robust extra check */ 1378238106Sdes if(!ce.nc_rrset) { 1379238106Sdes verbose(VERB_ALGO, "nsec3 nods proof: no next closer nsec3"); 1380238106Sdes *reason = "no NSEC3 next closer"; 1381238106Sdes return sec_status_bogus; 1382238106Sdes } 1383238106Sdes 1384238106Sdes /* we had the closest encloser proof, then we need to check that the 1385238106Sdes * covering NSEC3 was opt-out -- the proveClosestEncloser step already 1386238106Sdes * checked to see if the closest encloser was a delegation or DNAME. 1387238106Sdes */ 1388238106Sdes log_assert(ce.nc_rrset); 1389238106Sdes if(!nsec3_has_optout(ce.nc_rrset, ce.nc_rr)) { 1390238106Sdes verbose(VERB_ALGO, "nsec3 provenods: covering NSEC3 was not " 1391238106Sdes "opt-out in an opt-out DS NOERROR/NODATA case."); 1392238106Sdes *reason = "covering NSEC3 was not opt-out in an opt-out " 1393238106Sdes "DS NOERROR/NODATA case"; 1394238106Sdes return sec_status_bogus; 1395238106Sdes } 1396238106Sdes /* RFC5155 section 9.2: if nc has optout then no AD flag set */ 1397238106Sdes return sec_status_insecure; 1398238106Sdes} 1399238106Sdes 1400238106Sdesenum sec_status 1401238106Sdesnsec3_prove_nxornodata(struct module_env* env, struct val_env* ve, 1402238106Sdes struct ub_packed_rrset_key** list, size_t num, 1403238106Sdes struct query_info* qinfo, struct key_entry_key* kkey, int* nodata) 1404238106Sdes{ 1405238106Sdes enum sec_status sec, secnx; 1406238106Sdes rbtree_t ct; 1407238106Sdes struct nsec3_filter flt; 1408238106Sdes *nodata = 0; 1409238106Sdes 1410238106Sdes if(!list || num == 0 || !kkey || !key_entry_isgood(kkey)) 1411238106Sdes return sec_status_bogus; /* no valid NSEC3s, bogus */ 1412238106Sdes rbtree_init(&ct, &nsec3_hash_cmp); /* init names-to-hash cache */ 1413238106Sdes filter_init(&flt, list, num, qinfo); /* init RR iterator */ 1414238106Sdes if(!flt.zone) 1415238106Sdes return sec_status_bogus; /* no RRs */ 1416238106Sdes if(nsec3_iteration_count_high(ve, &flt, kkey)) 1417238106Sdes return sec_status_insecure; /* iteration count too high */ 1418238106Sdes 1419238106Sdes /* try nxdomain and nodata after another, while keeping the 1420238106Sdes * hash cache intact */ 1421238106Sdes 1422238106Sdes secnx = nsec3_do_prove_nameerror(env, &flt, &ct, qinfo); 1423238106Sdes if(secnx==sec_status_secure) 1424238106Sdes return sec_status_secure; 1425238106Sdes sec = nsec3_do_prove_nodata(env, &flt, &ct, qinfo); 1426238106Sdes if(sec==sec_status_secure) { 1427238106Sdes *nodata = 1; 1428238106Sdes } else if(sec == sec_status_insecure) { 1429238106Sdes *nodata = 1; 1430238106Sdes } else if(secnx == sec_status_insecure) { 1431238106Sdes sec = sec_status_insecure; 1432238106Sdes } 1433238106Sdes return sec; 1434238106Sdes} 1435