1/* 2 * validator/val_nsec.c - validator NSEC denial of existence functions. 3 * 4 * Copyright (c) 2007, NLnet Labs. All rights reserved. 5 * 6 * This software is open source. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * Redistributions of source code must retain the above copyright notice, 13 * this list of conditions and the following disclaimer. 14 * 15 * Redistributions in binary form must reproduce the above copyright notice, 16 * this list of conditions and the following disclaimer in the documentation 17 * and/or other materials provided with the distribution. 18 * 19 * Neither the name of the NLNET LABS nor the names of its contributors may 20 * be used to endorse or promote products derived from this software without 21 * specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34 */ 35 36/** 37 * \file 38 * 39 * This file contains helper functions for the validator module. 40 * The functions help with NSEC checking, the different NSEC proofs 41 * for denial of existence, and proofs for presence of types. 42 */ 43#include "config.h" 44#include "validator/val_nsec.h" 45#include "validator/val_utils.h" 46#include "util/data/msgreply.h" 47#include "util/data/dname.h" 48#include "util/net_help.h" 49#include "util/module.h" 50#include "services/cache/rrset.h" 51 52/** get ttl of rrset */ 53static uint32_t 54rrset_get_ttl(struct ub_packed_rrset_key* k) 55{ 56 struct packed_rrset_data* d = (struct packed_rrset_data*)k->entry.data; 57 return d->ttl; 58} 59 60int 61nsecbitmap_has_type_rdata(uint8_t* bitmap, size_t len, uint16_t type) 62{ 63 /* Check type present in NSEC typemap with bitmap arg */ 64 /* bitmasks for determining type-lowerbits presence */ 65 uint8_t masks[8] = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01}; 66 uint8_t type_window = type>>8; 67 uint8_t type_low = type&0xff; 68 uint8_t win, winlen; 69 /* read each of the type bitmap windows and see if the searched 70 * type is amongst it */ 71 while(len > 0) { 72 if(len < 3) /* bad window, at least window# winlen bitmap */ 73 return 0; 74 win = *bitmap++; 75 winlen = *bitmap++; 76 len -= 2; 77 if(len < winlen || winlen < 1 || winlen > 32) 78 return 0; /* bad window length */ 79 if(win == type_window) { 80 /* search window bitmap for the correct byte */ 81 /* mybyte is 0 if we need the first byte */ 82 size_t mybyte = type_low>>3; 83 if(winlen <= mybyte) 84 return 0; /* window too short */ 85 return (int)(bitmap[mybyte] & masks[type_low&0x7]); 86 } else { 87 /* not the window we are looking for */ 88 bitmap += winlen; 89 len -= winlen; 90 } 91 } 92 /* end of bitmap reached, no type found */ 93 return 0; 94} 95 96int 97nsec_has_type(struct ub_packed_rrset_key* nsec, uint16_t type) 98{ 99 struct packed_rrset_data* d = (struct packed_rrset_data*)nsec-> 100 entry.data; 101 size_t len; 102 if(!d || d->count == 0 || d->rr_len[0] < 2+1) 103 return 0; 104 len = dname_valid(d->rr_data[0]+2, d->rr_len[0]-2); 105 if(!len) 106 return 0; 107 return nsecbitmap_has_type_rdata(d->rr_data[0]+2+len, 108 d->rr_len[0]-2-len, type); 109} 110 111/** 112 * Get next owner name from nsec record 113 * @param nsec: the nsec RRset. 114 * If there are multiple RRs, then this will only return one of them. 115 * @param nm: the next name is returned. 116 * @param ln: length of nm is returned. 117 * @return false on a bad NSEC RR (too short, malformed dname). 118 */ 119static int 120nsec_get_next(struct ub_packed_rrset_key* nsec, uint8_t** nm, size_t* ln) 121{ 122 struct packed_rrset_data* d = (struct packed_rrset_data*)nsec-> 123 entry.data; 124 if(!d || d->count == 0 || d->rr_len[0] < 2+1) { 125 *nm = 0; 126 *ln = 0; 127 return 0; 128 } 129 *nm = d->rr_data[0]+2; 130 *ln = dname_valid(*nm, d->rr_len[0]-2); 131 if(!*ln) { 132 *nm = 0; 133 *ln = 0; 134 return 0; 135 } 136 return 1; 137} 138 139/** 140 * For an NSEC that matches the DS queried for, check absence of DS type. 141 * 142 * @param nsec: NSEC for proof, must be trusted. 143 * @param qinfo: what is queried for. 144 * @return if secure the nsec proves that no DS is present, or 145 * insecure if it proves it is not a delegation point. 146 * or bogus if something was wrong. 147 */ 148static enum sec_status 149val_nsec_proves_no_ds(struct ub_packed_rrset_key* nsec, 150 struct query_info* qinfo) 151{ 152 log_assert(qinfo->qtype == LDNS_RR_TYPE_DS); 153 log_assert(ntohs(nsec->rk.type) == LDNS_RR_TYPE_NSEC); 154 155 if(nsec_has_type(nsec, LDNS_RR_TYPE_SOA) && qinfo->qname_len != 1) { 156 /* SOA present means that this is the NSEC from the child, 157 * not the parent (so it is the wrong one). */ 158 return sec_status_bogus; 159 } 160 if(nsec_has_type(nsec, LDNS_RR_TYPE_DS)) { 161 /* DS present means that there should have been a positive 162 * response to the DS query, so there is something wrong. */ 163 return sec_status_bogus; 164 } 165 166 if(!nsec_has_type(nsec, LDNS_RR_TYPE_NS)) { 167 /* If there is no NS at this point at all, then this 168 * doesn't prove anything one way or the other. */ 169 return sec_status_insecure; 170 } 171 /* Otherwise, this proves no DS. */ 172 return sec_status_secure; 173} 174 175/** check security status from cache or verify rrset, returns true if secure */ 176static int 177nsec_verify_rrset(struct module_env* env, struct val_env* ve, 178 struct ub_packed_rrset_key* nsec, struct key_entry_key* kkey, 179 char** reason, sldns_ede_code* reason_bogus, 180 struct module_qstate* qstate) 181{ 182 struct packed_rrset_data* d = (struct packed_rrset_data*) 183 nsec->entry.data; 184 int verified = 0; 185 if(!d) return 0; 186 if(d->security == sec_status_secure) 187 return 1; 188 rrset_check_sec_status(env->rrset_cache, nsec, *env->now); 189 if(d->security == sec_status_secure) 190 return 1; 191 d->security = val_verify_rrset_entry(env, ve, nsec, kkey, reason, 192 reason_bogus, LDNS_SECTION_AUTHORITY, qstate, &verified); 193 if(d->security == sec_status_secure) { 194 rrset_update_sec_status(env->rrset_cache, nsec, *env->now); 195 return 1; 196 } 197 return 0; 198} 199 200enum sec_status 201val_nsec_prove_nodata_dsreply(struct module_env* env, struct val_env* ve, 202 struct query_info* qinfo, struct reply_info* rep, 203 struct key_entry_key* kkey, time_t* proof_ttl, char** reason, 204 sldns_ede_code* reason_bogus, struct module_qstate* qstate) 205{ 206 struct ub_packed_rrset_key* nsec = reply_find_rrset_section_ns( 207 rep, qinfo->qname, qinfo->qname_len, LDNS_RR_TYPE_NSEC, 208 qinfo->qclass); 209 enum sec_status sec; 210 size_t i; 211 uint8_t* wc = NULL, *ce = NULL; 212 int valid_nsec = 0; 213 struct ub_packed_rrset_key* wc_nsec = NULL; 214 215 /* If we have a NSEC at the same name, it must prove one 216 * of two things 217 * -- 218 * 1) this is a delegation point and there is no DS 219 * 2) this is not a delegation point */ 220 if(nsec) { 221 if(!nsec_verify_rrset(env, ve, nsec, kkey, reason, 222 reason_bogus, qstate)) { 223 verbose(VERB_ALGO, "NSEC RRset for the " 224 "referral did not verify."); 225 return sec_status_bogus; 226 } 227 sec = val_nsec_proves_no_ds(nsec, qinfo); 228 if(sec == sec_status_bogus) { 229 /* something was wrong. */ 230 *reason = "NSEC does not prove absence of DS"; 231 *reason_bogus = LDNS_EDE_DNSSEC_BOGUS; 232 return sec; 233 } else if(sec == sec_status_insecure) { 234 /* this wasn't a delegation point. */ 235 return sec; 236 } else if(sec == sec_status_secure) { 237 /* this proved no DS. */ 238 *proof_ttl = ub_packed_rrset_ttl(nsec); 239 return sec; 240 } 241 /* if unchecked, fall through to next proof */ 242 } 243 244 /* Otherwise, there is no NSEC at qname. This could be an ENT. 245 * (ENT=empty non terminal). If not, this is broken. */ 246 247 /* verify NSEC rrsets in auth section */ 248 for(i=rep->an_numrrsets; i < rep->an_numrrsets+rep->ns_numrrsets; 249 i++) { 250 if(rep->rrsets[i]->rk.type != htons(LDNS_RR_TYPE_NSEC)) 251 continue; 252 if(!nsec_verify_rrset(env, ve, rep->rrsets[i], kkey, reason, 253 reason_bogus, qstate)) { 254 verbose(VERB_ALGO, "NSEC for empty non-terminal " 255 "did not verify."); 256 *reason = "NSEC for empty non-terminal " 257 "did not verify."; 258 return sec_status_bogus; 259 } 260 if(nsec_proves_nodata(rep->rrsets[i], qinfo, &wc)) { 261 verbose(VERB_ALGO, "NSEC for empty non-terminal " 262 "proved no DS."); 263 *proof_ttl = rrset_get_ttl(rep->rrsets[i]); 264 if(wc && dname_is_wild(rep->rrsets[i]->rk.dname)) 265 wc_nsec = rep->rrsets[i]; 266 valid_nsec = 1; 267 } 268 if(val_nsec_proves_name_error(rep->rrsets[i], qinfo->qname)) { 269 ce = nsec_closest_encloser(qinfo->qname, 270 rep->rrsets[i]); 271 } 272 } 273 if(wc && !ce) 274 valid_nsec = 0; 275 else if(wc && ce) { 276 /* ce and wc must match */ 277 if(query_dname_compare(wc, ce) != 0) 278 valid_nsec = 0; 279 else if(!wc_nsec) 280 valid_nsec = 0; 281 } 282 if(valid_nsec) { 283 if(wc) { 284 /* check if this is a delegation */ 285 *reason = "NSEC for wildcard does not prove absence of DS"; 286 return val_nsec_proves_no_ds(wc_nsec, qinfo); 287 } 288 /* valid nsec proves empty nonterminal */ 289 return sec_status_insecure; 290 } 291 292 /* NSEC proof did not conclusively point to DS or no DS */ 293 return sec_status_unchecked; 294} 295 296int nsec_proves_nodata(struct ub_packed_rrset_key* nsec, 297 struct query_info* qinfo, uint8_t** wc) 298{ 299 log_assert(wc); 300 if(query_dname_compare(nsec->rk.dname, qinfo->qname) != 0) { 301 uint8_t* nm; 302 size_t ln; 303 304 /* empty-non-terminal checking. 305 * Done before wildcard, because this is an exact match, 306 * and would prevent a wildcard from matching. */ 307 308 /* If the nsec is proving that qname is an ENT, the nsec owner 309 * will be less than qname, and the next name will be a child 310 * domain of the qname. */ 311 if(!nsec_get_next(nsec, &nm, &ln)) 312 return 0; /* bad nsec */ 313 if(dname_strict_subdomain_c(nm, qinfo->qname) && 314 dname_canonical_compare(nsec->rk.dname, 315 qinfo->qname) < 0) { 316 return 1; /* proves ENT */ 317 } 318 319 /* wildcard checking. */ 320 321 /* If this is a wildcard NSEC, make sure that a) it was 322 * possible to have generated qname from the wildcard and 323 * b) the type map does not contain qtype. Note that this 324 * does NOT prove that this wildcard was the applicable 325 * wildcard. */ 326 if(dname_is_wild(nsec->rk.dname)) { 327 /* the purported closest encloser. */ 328 uint8_t* ce = nsec->rk.dname; 329 size_t ce_len = nsec->rk.dname_len; 330 dname_remove_label(&ce, &ce_len); 331 332 /* The qname must be a strict subdomain of the 333 * closest encloser, for the wildcard to apply 334 */ 335 if(dname_strict_subdomain_c(qinfo->qname, ce)) { 336 /* here we have a matching NSEC for the qname, 337 * perform matching NSEC checks */ 338 if(nsec_has_type(nsec, LDNS_RR_TYPE_CNAME)) { 339 /* should have gotten the wildcard CNAME */ 340 return 0; 341 } 342 if(nsec_has_type(nsec, LDNS_RR_TYPE_NS) && 343 !nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) { 344 /* wrong parentside (wildcard) NSEC used */ 345 return 0; 346 } 347 if(nsec_has_type(nsec, qinfo->qtype)) { 348 return 0; 349 } 350 *wc = ce; 351 return 1; 352 } 353 } else { 354 /* See if the next owner name covers a wildcard 355 * empty non-terminal. */ 356 while (dname_canonical_compare(nsec->rk.dname, nm) < 0) { 357 /* wildcard does not apply if qname below 358 * the name that exists under the '*' */ 359 if (dname_subdomain_c(qinfo->qname, nm)) 360 break; 361 /* but if it is a wildcard and qname is below 362 * it, then the wildcard applies. The wildcard 363 * is an empty nonterminal. nodata proven. */ 364 if (dname_is_wild(nm)) { 365 size_t ce_len = ln; 366 uint8_t* ce = nm; 367 dname_remove_label(&ce, &ce_len); 368 if(dname_strict_subdomain_c(qinfo->qname, ce)) { 369 *wc = ce; 370 return 1; 371 } 372 } 373 dname_remove_label(&nm, &ln); 374 } 375 } 376 377 /* Otherwise, this NSEC does not prove ENT and is not a 378 * wildcard, so it does not prove NODATA. */ 379 return 0; 380 } 381 382 /* If the qtype exists, then we should have gotten it. */ 383 if(nsec_has_type(nsec, qinfo->qtype)) { 384 return 0; 385 } 386 387 /* if the name is a CNAME node, then we should have gotten the CNAME*/ 388 if(nsec_has_type(nsec, LDNS_RR_TYPE_CNAME)) { 389 return 0; 390 } 391 392 /* If an NS set exists at this name, and NOT a SOA (so this is a 393 * zone cut, not a zone apex), then we should have gotten a 394 * referral (or we just got the wrong NSEC). 395 * The reverse of this check is used when qtype is DS, since that 396 * must use the NSEC from above the zone cut. */ 397 if(qinfo->qtype != LDNS_RR_TYPE_DS && 398 nsec_has_type(nsec, LDNS_RR_TYPE_NS) && 399 !nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) { 400 return 0; 401 } else if(qinfo->qtype == LDNS_RR_TYPE_DS && 402 nsec_has_type(nsec, LDNS_RR_TYPE_SOA) && 403 !dname_is_root(qinfo->qname)) { 404 return 0; 405 } 406 407 return 1; 408} 409 410int 411val_nsec_proves_name_error(struct ub_packed_rrset_key* nsec, uint8_t* qname) 412{ 413 uint8_t* owner = nsec->rk.dname; 414 uint8_t* next; 415 size_t nlen; 416 if(!nsec_get_next(nsec, &next, &nlen)) 417 return 0; 418 419 /* If NSEC owner == qname, then this NSEC proves that qname exists. */ 420 if(query_dname_compare(qname, owner) == 0) { 421 return 0; 422 } 423 424 /* If NSEC is a parent of qname, we need to check the type map 425 * If the parent name has a DNAME or is a delegation point, then 426 * this NSEC is being misused. */ 427 if(dname_subdomain_c(qname, owner) && 428 (nsec_has_type(nsec, LDNS_RR_TYPE_DNAME) || 429 (nsec_has_type(nsec, LDNS_RR_TYPE_NS) 430 && !nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) 431 )) { 432 return 0; 433 } 434 435 if(query_dname_compare(owner, next) == 0) { 436 /* this nsec is the only nsec */ 437 /* zone.name NSEC zone.name, disproves everything else */ 438 /* but only for subdomains of that zone */ 439 if(dname_strict_subdomain_c(qname, next)) 440 return 1; 441 } 442 else if(dname_canonical_compare(owner, next) > 0) { 443 /* this is the last nsec, ....(bigger) NSEC zonename(smaller) */ 444 /* the names after the last (owner) name do not exist 445 * there are no names before the zone name in the zone 446 * but the qname must be a subdomain of the zone name(next). */ 447 if(dname_canonical_compare(owner, qname) < 0 && 448 dname_strict_subdomain_c(qname, next)) 449 return 1; 450 } else { 451 /* regular NSEC, (smaller) NSEC (larger) */ 452 if(dname_canonical_compare(owner, qname) < 0 && 453 dname_canonical_compare(qname, next) < 0) { 454 return 1; 455 } 456 } 457 return 0; 458} 459 460int val_nsec_proves_insecuredelegation(struct ub_packed_rrset_key* nsec, 461 struct query_info* qinfo) 462{ 463 if(nsec_has_type(nsec, LDNS_RR_TYPE_NS) && 464 !nsec_has_type(nsec, LDNS_RR_TYPE_DS) && 465 !nsec_has_type(nsec, LDNS_RR_TYPE_SOA)) { 466 /* see if nsec signals an insecure delegation */ 467 if(qinfo->qtype == LDNS_RR_TYPE_DS) { 468 /* if type is DS and qname is equal to nsec, then it 469 * is an exact match nsec, result not insecure */ 470 if(dname_strict_subdomain_c(qinfo->qname, 471 nsec->rk.dname)) 472 return 1; 473 } else { 474 if(dname_subdomain_c(qinfo->qname, nsec->rk.dname)) 475 return 1; 476 } 477 } 478 return 0; 479} 480 481uint8_t* 482nsec_closest_encloser(uint8_t* qname, struct ub_packed_rrset_key* nsec) 483{ 484 uint8_t* next; 485 size_t nlen; 486 uint8_t* common1, *common2; 487 if(!nsec_get_next(nsec, &next, &nlen)) 488 return NULL; 489 /* longest common with owner or next name */ 490 common1 = dname_get_shared_topdomain(nsec->rk.dname, qname); 491 common2 = dname_get_shared_topdomain(next, qname); 492 if(dname_count_labels(common1) > dname_count_labels(common2)) 493 return common1; 494 return common2; 495} 496 497int val_nsec_proves_positive_wildcard(struct ub_packed_rrset_key* nsec, 498 struct query_info* qinf, uint8_t* wc) 499{ 500 uint8_t* ce; 501 /* 1) prove that qname doesn't exist and 502 * 2) that the correct wildcard was used 503 * nsec has been verified already. */ 504 if(!val_nsec_proves_name_error(nsec, qinf->qname)) 505 return 0; 506 /* check wildcard name */ 507 ce = nsec_closest_encloser(qinf->qname, nsec); 508 if(!ce) 509 return 0; 510 if(query_dname_compare(wc, ce) != 0) { 511 return 0; 512 } 513 return 1; 514} 515 516int 517val_nsec_proves_no_wc(struct ub_packed_rrset_key* nsec, uint8_t* qname, 518 size_t qnamelen) 519{ 520 /* Determine if a NSEC record proves the non-existence of a 521 * wildcard that could have produced qname. */ 522 int labs; 523 uint8_t* ce = nsec_closest_encloser(qname, nsec); 524 uint8_t* strip; 525 size_t striplen; 526 uint8_t buf[LDNS_MAX_DOMAINLEN+3]; 527 if(!ce) 528 return 0; 529 /* we can subtract the closest encloser count - since that is the 530 * largest shared topdomain with owner and next NSEC name, 531 * because the NSEC is no proof for names shorter than the owner 532 * and next names. */ 533 labs = dname_count_labels(qname) - dname_count_labels(ce); 534 535 if(labs > 0) { 536 /* i is number of labels to strip off qname, prepend * wild */ 537 strip = qname; 538 striplen = qnamelen; 539 dname_remove_labels(&strip, &striplen, labs); 540 if(striplen > LDNS_MAX_DOMAINLEN-2) 541 return 0; /* too long to prepend wildcard */ 542 buf[0] = 1; 543 buf[1] = (uint8_t)'*'; 544 memmove(buf+2, strip, striplen); 545 if(val_nsec_proves_name_error(nsec, buf)) { 546 return 1; 547 } 548 } 549 return 0; 550} 551