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