1 /* 2 * nsec3.c -- nsec3 handling. 3 * 4 * Copyright (c) 2001-2006, NLnet Labs. All rights reserved. 5 * 6 * See LICENSE for the license. 7 * 8 */ 9 #include "config.h" 10 #ifdef NSEC3 11 #include <stdio.h> 12 #include <stdlib.h> 13 14 #include "nsec3.h" 15 #include "iterated_hash.h" 16 #include "namedb.h" 17 #include "nsd.h" 18 #include "answer.h" 19 #include "udbzone.h" 20 #include "options.h" 21 22 #define NSEC3_RDATA_BITMAP 5 23 24 /* compare nsec3 hashes in nsec3 tree */ 25 static int 26 cmp_hash_tree(const void* x, const void* y) 27 { 28 const domain_type* a = (const domain_type*)x; 29 const domain_type* b = (const domain_type*)y; 30 return memcmp(a->nsec3->nsec3_hash, b->nsec3->nsec3_hash, 31 NSEC3_HASH_LEN); 32 } 33 34 /* compare nsec3 hashes in nsec3 wc tree */ 35 static int 36 cmp_wchash_tree(const void* x, const void* y) 37 { 38 const domain_type* a = (const domain_type*)x; 39 const domain_type* b = (const domain_type*)y; 40 return memcmp(a->nsec3->nsec3_wc_hash, b->nsec3->nsec3_wc_hash, 41 NSEC3_HASH_LEN); 42 } 43 44 /* compare nsec3 hashes in nsec3 ds tree */ 45 static int 46 cmp_dshash_tree(const void* x, const void* y) 47 { 48 const domain_type* a = (const domain_type*)x; 49 const domain_type* b = (const domain_type*)y; 50 return memcmp(a->nsec3->nsec3_ds_parent_hash, 51 b->nsec3->nsec3_ds_parent_hash, NSEC3_HASH_LEN); 52 } 53 54 /* compare base32-encoded nsec3 hashes in nsec3 rr tree, they are 55 * stored in the domain name of the node */ 56 static int 57 cmp_nsec3_tree(const void* x, const void* y) 58 { 59 const domain_type* a = (const domain_type*)x; 60 const domain_type* b = (const domain_type*)y; 61 /* labelcount + 32long label */ 62 assert(dname_name(a->dname)[0] == 32); 63 assert(dname_name(b->dname)[0] == 32); 64 return memcmp(dname_name(a->dname), dname_name(b->dname), 33); 65 } 66 67 void nsec3_zone_trees_create(struct region* region, zone_type* zone) 68 { 69 if(!zone->nsec3tree) 70 zone->nsec3tree = rbtree_create(region, cmp_nsec3_tree); 71 if(!zone->hashtree) 72 zone->hashtree = rbtree_create(region, cmp_hash_tree); 73 if(!zone->wchashtree) 74 zone->wchashtree = rbtree_create(region, cmp_wchash_tree); 75 if(!zone->dshashtree) 76 zone->dshashtree = rbtree_create(region, cmp_dshash_tree); 77 } 78 79 void nsec3_hash_tree_clear(struct zone* zone) 80 { 81 hash_tree_clear(zone->nsec3tree); 82 hash_tree_clear(zone->hashtree); 83 hash_tree_clear(zone->wchashtree); 84 hash_tree_clear(zone->dshashtree); 85 } 86 87 static void 88 detect_nsec3_params(rr_type* nsec3_apex, 89 const unsigned char** salt, int* salt_len, int* iter) 90 { 91 assert(salt && salt_len && iter); 92 assert(nsec3_apex); 93 *salt_len = rdata_atom_data(nsec3_apex->rdatas[3])[0]; 94 *salt = (unsigned char*)(rdata_atom_data(nsec3_apex->rdatas[3])+1); 95 *iter = read_uint16(rdata_atom_data(nsec3_apex->rdatas[2])); 96 } 97 98 const dname_type * 99 nsec3_b32_create(region_type* region, zone_type* zone, unsigned char* hash) 100 { 101 const dname_type* dname; 102 char b32[SHA_DIGEST_LENGTH*2+1]; 103 b32_ntop(hash, SHA_DIGEST_LENGTH, b32, sizeof(b32)); 104 dname=dname_parse(region, b32); 105 dname=dname_concatenate(region, dname, domain_dname(zone->apex)); 106 return dname; 107 } 108 109 void 110 nsec3_hash_and_store(zone_type* zone, const dname_type* dname, uint8_t* store) 111 { 112 const unsigned char* nsec3_salt = NULL; 113 int nsec3_saltlength = 0; 114 int nsec3_iterations = 0; 115 116 detect_nsec3_params(zone->nsec3_param, &nsec3_salt, 117 &nsec3_saltlength, &nsec3_iterations); 118 iterated_hash((unsigned char*)store, nsec3_salt, nsec3_saltlength, 119 dname_name(dname), dname->name_size, nsec3_iterations); 120 } 121 122 #define STORE_HASH(x,y) memmove(domain->nsec3->x,y,NSEC3_HASH_LEN); domain->nsec3->have_##x =1; 123 124 /** find hash or create it and store it */ 125 static void 126 nsec3_lookup_hash_and_wc(zone_type* zone, const dname_type* dname, 127 domain_type* domain, region_type* tmpregion) 128 { 129 const dname_type* wcard; 130 if(domain->nsec3->have_nsec3_hash && domain->nsec3->have_nsec3_wc_hash) { 131 return; 132 } 133 /* lookup failed; disk failure or so */ 134 nsec3_hash_and_store(zone, dname, domain->nsec3->nsec3_hash); 135 domain->nsec3->have_nsec3_hash = 1; 136 wcard = dname_parse(tmpregion, "*"); 137 wcard = dname_concatenate(tmpregion, wcard, dname); 138 nsec3_hash_and_store(zone, wcard, domain->nsec3->nsec3_wc_hash); 139 domain->nsec3->have_nsec3_wc_hash = 1; 140 } 141 142 static void 143 nsec3_lookup_hash_ds(zone_type* zone, const dname_type* dname, 144 domain_type* domain) 145 { 146 if(domain->nsec3->have_nsec3_ds_parent_hash) { 147 return; 148 } 149 /* lookup failed; disk failure or so */ 150 nsec3_hash_and_store(zone, dname, domain->nsec3->nsec3_ds_parent_hash); 151 domain->nsec3->have_nsec3_ds_parent_hash = 1; 152 } 153 154 static int 155 nsec3_has_soa(rr_type* rr) 156 { 157 if(rdata_atom_size(rr->rdatas[NSEC3_RDATA_BITMAP]) >= 3 && /* has types in bitmap */ 158 rdata_atom_data(rr->rdatas[NSEC3_RDATA_BITMAP])[0] == 0 && /* first window = 0, */ 159 /* [1]: bitmap length must be >= 1 */ 160 /* [2]: bit[6] = SOA, thus mask first bitmap octet with 0x02 */ 161 rdata_atom_data(rr->rdatas[NSEC3_RDATA_BITMAP])[2]&0x02) { /* SOA bit set */ 162 return 1; 163 } 164 return 0; 165 } 166 167 static rr_type* 168 check_apex_soa(namedb_type* namedb, zone_type *zone) 169 { 170 uint8_t h[NSEC3_HASH_LEN]; 171 domain_type* domain; 172 const dname_type* hashed_apex, *dname = domain_dname(zone->apex); 173 unsigned j; 174 rrset_type* nsec3_rrset; 175 region_type* tmpregion; 176 177 nsec3_hash_and_store(zone, dname, h); 178 tmpregion = region_create(xalloc, free); 179 hashed_apex = nsec3_b32_create(tmpregion, zone, h); 180 domain = domain_table_find(namedb->domains, hashed_apex); 181 if(!domain) { 182 log_msg(LOG_ERR, "%s NSEC3PARAM entry has no hash(apex).", 183 domain_to_string(zone->apex)); 184 log_msg(LOG_ERR, "hash(apex)= %s", 185 dname_to_string(hashed_apex, NULL)); 186 region_destroy(tmpregion); 187 return NULL; 188 } 189 nsec3_rrset = domain_find_rrset(domain, zone, TYPE_NSEC3); 190 if(!nsec3_rrset) { 191 log_msg(LOG_ERR, "%s NSEC3PARAM entry: hash(apex) has no NSEC3 RRset.", 192 domain_to_string(zone->apex)); 193 log_msg(LOG_ERR, "hash(apex)= %s", 194 dname_to_string(hashed_apex, NULL)); 195 region_destroy(tmpregion); 196 return NULL; 197 } 198 for(j=0; j<nsec3_rrset->rr_count; j++) { 199 if(nsec3_has_soa(&nsec3_rrset->rrs[j])) { 200 region_destroy(tmpregion); 201 return &nsec3_rrset->rrs[j]; 202 } 203 } 204 log_msg(LOG_ERR, "%s NSEC3PARAM entry: hash(apex) NSEC3 has no SOA flag.", 205 domain_to_string(zone->apex)); 206 log_msg(LOG_ERR, "hash(apex)= %s", 207 dname_to_string(hashed_apex, NULL)); 208 region_destroy(tmpregion); 209 return NULL; 210 } 211 212 static struct rr* 213 udb_zone_find_nsec3param(udb_base* udb, udb_ptr* uz, struct zone* z) 214 { 215 udb_ptr urr; 216 unsigned i; 217 rrset_type* rrset = domain_find_rrset(z->apex, z, TYPE_NSEC3PARAM); 218 if(!rrset) /* no NSEC3PARAM in mem */ 219 return NULL; 220 udb_ptr_new(&urr, udb, &ZONE(uz)->nsec3param); 221 if(!urr.data || RR(&urr)->len < 5) { 222 /* no NSEC3PARAM in udb */ 223 udb_ptr_unlink(&urr, udb); 224 return NULL; 225 } 226 /* find matching NSEC3PARAM RR in memory */ 227 for(i=0; i<rrset->rr_count; i++) { 228 /* if this RR matches the udb RR then we are done */ 229 rdata_atom_type* rd = rrset->rrs[i].rdatas; 230 if(rrset->rrs[i].rdata_count < 4) continue; 231 if(RR(&urr)->wire[0] == rdata_atom_data(rd[0])[0] && /*alg*/ 232 RR(&urr)->wire[1] == rdata_atom_data(rd[1])[0] && /*flg*/ 233 RR(&urr)->wire[2] == rdata_atom_data(rd[2])[0] && /*iter*/ 234 RR(&urr)->wire[3] == rdata_atom_data(rd[2])[1] && 235 RR(&urr)->wire[4] == rdata_atom_data(rd[3])[0] && /*slen*/ 236 RR(&urr)->len >= 5 + RR(&urr)->wire[4] && 237 memcmp(RR(&urr)->wire+5, rdata_atom_data(rd[3])+1, 238 rdata_atom_data(rd[3])[0]) == 0) { 239 udb_ptr_unlink(&urr, udb); 240 return &rrset->rrs[i]; 241 } 242 } 243 udb_ptr_unlink(&urr, udb); 244 return NULL; 245 } 246 247 static struct rr* 248 db_find_nsec3param(struct zone* z, struct rr* avoid_rr) 249 { 250 unsigned i; 251 rrset_type* rrset = domain_find_rrset(z->apex, z, TYPE_NSEC3PARAM); 252 if(!rrset) /* no NSEC3PARAM in mem */ 253 return NULL; 254 /* find first nsec3param we can support (SHA1, no flags) */ 255 for(i=0; i<rrset->rr_count; i++) { 256 rdata_atom_type* rd = rrset->rrs[i].rdatas; 257 /* do not use the RR that is going to be deleted (in IXFR) */ 258 if(&rrset->rrs[i] == avoid_rr) continue; 259 if(rrset->rrs[i].rdata_count < 4) continue; 260 if(rdata_atom_data(rd[0])[0] == NSEC3_SHA1_HASH && 261 rdata_atom_data(rd[1])[0] == 0) { 262 if(2 <= verbosity) { 263 char str[MAX_RDLENGTH*2+16]; 264 char* p; 265 p = str+snprintf(str, sizeof(str), "%u %u %u ", 266 (unsigned)rdata_atom_data(rd[0])[0], 267 (unsigned)rdata_atom_data(rd[1])[0], 268 (unsigned)read_uint16(rdata_atom_data(rd[2]))); 269 if(rdata_atom_data(rd[3])[0] == 0) 270 *p++ = '-'; 271 else { 272 p += hex_ntop(rdata_atom_data(rd[3])+1, 273 rdata_atom_data(rd[3])[0], p, 274 sizeof(str)-strlen(str)-1); 275 } 276 *p = 0; 277 VERBOSITY(2, (LOG_INFO, "rehash of zone %s with parameters %s", 278 domain_to_string(z->apex), str)); 279 } 280 return &rrset->rrs[i]; 281 } 282 } 283 return NULL; 284 } 285 286 void 287 nsec3_find_zone_param(struct namedb* db, struct zone* zone, udb_ptr* z, 288 struct rr* avoid_rr) 289 { 290 /* get nsec3param RR from udb */ 291 if(db->udb) 292 zone->nsec3_param = udb_zone_find_nsec3param(db->udb, z, zone); 293 /* no db, get from memory, avoid using the rr that is going to be 294 * deleted, avoid_rr */ 295 else zone->nsec3_param = db_find_nsec3param(zone, avoid_rr); 296 } 297 298 /* check params ok for one RR */ 299 static int 300 nsec3_rdata_params_ok(rdata_atom_type* prd, rdata_atom_type* rd) 301 { 302 return (rdata_atom_data(rd[0])[0] == 303 rdata_atom_data(prd[0])[0] && /* hash algo */ 304 rdata_atom_data(rd[2])[0] == 305 rdata_atom_data(prd[2])[0] && /* iterations 0 */ 306 rdata_atom_data(rd[2])[1] == 307 rdata_atom_data(prd[2])[1] && /* iterations 1 */ 308 rdata_atom_data(rd[3])[0] == 309 rdata_atom_data(prd[3])[0] && /* salt length */ 310 memcmp(rdata_atom_data(rd[3])+1, 311 rdata_atom_data(prd[3])+1, rdata_atom_data(rd[3])[0]) 312 == 0 ); 313 } 314 315 int 316 nsec3_rr_uses_params(rr_type* rr, zone_type* zone) 317 { 318 if(!rr || rr->rdata_count < 4) 319 return 0; 320 return nsec3_rdata_params_ok(zone->nsec3_param->rdatas, rr->rdatas); 321 } 322 323 int 324 nsec3_in_chain_count(domain_type* domain, zone_type* zone) 325 { 326 rrset_type* rrset = domain_find_rrset(domain, zone, TYPE_NSEC3); 327 unsigned i; 328 int count = 0; 329 if(!rrset || !zone->nsec3_param) 330 return 0; /* no NSEC3s, none in the chain */ 331 for(i=0; i<rrset->rr_count; i++) { 332 if(nsec3_rr_uses_params(&rrset->rrs[i], zone)) 333 count++; 334 } 335 return count; 336 } 337 338 struct domain* 339 nsec3_chain_find_prev(struct zone* zone, struct domain* domain) 340 { 341 if(domain->nsec3 && domain->nsec3->nsec3_node.key) { 342 /* see if there is a prev */ 343 rbnode_t* r = rbtree_previous(&domain->nsec3->nsec3_node); 344 if(r != RBTREE_NULL) { 345 /* found a previous, which is not the root-node in 346 * the prehash tree (and thus points to the tree) */ 347 return (domain_type*)r->key; 348 } 349 } 350 if(zone->nsec3_last) 351 return zone->nsec3_last; 352 return NULL; 353 } 354 355 void 356 nsec3_clear_precompile(struct namedb* db, zone_type* zone) 357 { 358 domain_type* walk; 359 /* clear prehash items (there must not be items for other zones) */ 360 prehash_clear(db->domains); 361 /* clear trees */ 362 hash_tree_clear(zone->nsec3tree); 363 hash_tree_clear(zone->hashtree); 364 hash_tree_clear(zone->wchashtree); 365 hash_tree_clear(zone->dshashtree); 366 /* wipe hashes */ 367 368 /* wipe precompile */ 369 walk = zone->apex; 370 while(walk && domain_is_subdomain(walk, zone->apex)) { 371 if(walk->nsec3) { 372 if(nsec3_domain_part_of_zone(walk, zone)) { 373 walk->nsec3->nsec3_node.key = NULL; 374 walk->nsec3->nsec3_cover = NULL; 375 walk->nsec3->nsec3_wcard_child_cover = NULL; 376 walk->nsec3->nsec3_is_exact = 0; 377 walk->nsec3->have_nsec3_hash = 0; 378 walk->nsec3->have_nsec3_wc_hash = 0; 379 walk->nsec3->hash_node.key = NULL; 380 walk->nsec3->wchash_node.key = NULL; 381 } 382 if(!walk->parent || 383 nsec3_domain_part_of_zone(walk->parent, zone)) { 384 walk->nsec3->nsec3_ds_parent_cover = NULL; 385 walk->nsec3->nsec3_ds_parent_is_exact = 0; 386 walk->nsec3->have_nsec3_ds_parent_hash = 0; 387 walk->nsec3->dshash_node.key = NULL; 388 } 389 } 390 walk = domain_next(walk); 391 } 392 zone->nsec3_last = NULL; 393 } 394 395 /* see if domain name is part of (existing names in) the nsec3 zone */ 396 int 397 nsec3_domain_part_of_zone(domain_type* d, zone_type* z) 398 { 399 while(d) { 400 if(d->is_apex) 401 return (z->apex == d); /* zonecut, if right zone*/ 402 d = d->parent; 403 } 404 return 0; 405 } 406 407 /* condition when a domain is precompiled */ 408 int 409 nsec3_condition_hash(domain_type* d, zone_type* z) 410 { 411 return d->is_existing && !domain_has_only_NSEC3(d, z) && 412 nsec3_domain_part_of_zone(d, z) && !domain_is_glue(d, z); 413 } 414 415 /* condition when a domain is ds precompiled */ 416 int 417 nsec3_condition_dshash(domain_type* d, zone_type* z) 418 { 419 return d->is_existing && !domain_has_only_NSEC3(d, z) && 420 (domain_find_rrset(d, z, TYPE_DS) || 421 domain_find_rrset(d, z, TYPE_NS)) && d != z->apex; 422 } 423 424 zone_type* 425 nsec3_tree_zone(namedb_type* db, domain_type* d) 426 { 427 /* see nsec3_domain_part_of_zone; domains part of zone that has 428 * apex above them */ 429 /* this does not use the rrset->zone pointer because there may be 430 * no rrsets left at apex (no SOA), e.g. during IXFR */ 431 while(d) { 432 if(d->is_apex) { 433 /* we can try a SOA if its present (faster than tree)*/ 434 /* DNSKEY and NSEC3PARAM are also good indicators */ 435 rrset_type *rrset; 436 for (rrset = d->rrsets; rrset; rrset = rrset->next) 437 if (rrset_rrtype(rrset) == TYPE_SOA || 438 rrset_rrtype(rrset) == TYPE_DNSKEY || 439 rrset_rrtype(rrset) == TYPE_NSEC3PARAM) 440 return rrset->zone; 441 return namedb_find_zone(db, d->dname); 442 } 443 d = d->parent; 444 } 445 return NULL; 446 } 447 448 zone_type* 449 nsec3_tree_dszone(namedb_type* db, domain_type* d) 450 { 451 /* the DStree does not contain nodes with d==z->apex */ 452 if(d->is_apex) 453 d = d->parent; 454 return nsec3_tree_zone(db, d); 455 } 456 457 int 458 nsec3_find_cover(zone_type* zone, uint8_t* hash, size_t hashlen, 459 domain_type** result) 460 { 461 rbnode_t* r = NULL; 462 int exact; 463 domain_type d; 464 uint8_t n[48]; 465 466 /* nsec3tree is sorted by b32 encoded domain name of the NSEC3 */ 467 b32_ntop(hash, hashlen, (char*)(n+5), sizeof(n)-5); 468 d.dname = (dname_type*)n; 469 n[0] = 34; /* name_size */ 470 n[1] = 2; /* label_count */ 471 n[2] = 0; /* label_offset[0] */ 472 n[3] = 0; /* label_offset[1] */ 473 n[4] = 32; /* label-size[0] */ 474 475 assert(result); 476 assert(zone->nsec3_param && zone->nsec3tree); 477 478 exact = rbtree_find_less_equal(zone->nsec3tree, &d, &r); 479 if(r) { 480 *result = (domain_type*)r->key; 481 } else { 482 *result = zone->nsec3_last; 483 } 484 return exact; 485 } 486 487 void 488 nsec3_precompile_domain(struct namedb* db, struct domain* domain, 489 struct zone* zone, region_type* tmpregion) 490 { 491 domain_type* result = 0; 492 int exact; 493 allocate_domain_nsec3(db->domains, domain); 494 495 /* hash it */ 496 nsec3_lookup_hash_and_wc(zone, domain_dname(domain), domain, tmpregion); 497 498 /* add into tree */ 499 zone_add_domain_in_hash_tree(db->region, &zone->hashtree, 500 cmp_hash_tree, domain, &domain->nsec3->hash_node); 501 zone_add_domain_in_hash_tree(db->region, &zone->wchashtree, 502 cmp_wchash_tree, domain, &domain->nsec3->wchash_node); 503 504 /* lookup in tree cover ptr (or exact) */ 505 exact = nsec3_find_cover(zone, domain->nsec3->nsec3_hash, 506 sizeof(domain->nsec3->nsec3_hash), &result); 507 domain->nsec3->nsec3_cover = result; 508 if(exact) 509 domain->nsec3->nsec3_is_exact = 1; 510 else domain->nsec3->nsec3_is_exact = 0; 511 512 /* find cover for *.domain for wildcard denial */ 513 exact = nsec3_find_cover(zone, domain->nsec3->nsec3_wc_hash, 514 sizeof(domain->nsec3->nsec3_wc_hash), &result); 515 domain->nsec3->nsec3_wcard_child_cover = result; 516 } 517 518 void 519 nsec3_precompile_domain_ds(struct namedb* db, struct domain* domain, 520 struct zone* zone) 521 { 522 domain_type* result = 0; 523 int exact; 524 allocate_domain_nsec3(db->domains, domain); 525 526 /* hash it : it could have different hash parameters then the 527 other hash for this domain name */ 528 nsec3_lookup_hash_ds(zone, domain_dname(domain), domain); 529 /* lookup in tree cover ptr (or exact) */ 530 exact = nsec3_find_cover(zone, domain->nsec3->nsec3_ds_parent_hash, 531 sizeof(domain->nsec3->nsec3_ds_parent_hash), &result); 532 if(exact) 533 domain->nsec3->nsec3_ds_parent_is_exact = 1; 534 else domain->nsec3->nsec3_ds_parent_is_exact = 0; 535 domain->nsec3->nsec3_ds_parent_cover = result; 536 /* add into tree */ 537 zone_add_domain_in_hash_tree(db->region, &zone->dshashtree, 538 cmp_dshash_tree, domain, &domain->nsec3->dshash_node); 539 } 540 541 static void 542 parse_nsec3_name(const dname_type* dname, uint8_t* hash, size_t buflen) 543 { 544 /* first label must be the match, */ 545 size_t lablen = (buflen-1) * 8 / 5; 546 const uint8_t* wire = dname_name(dname); 547 assert(lablen == 32 && buflen == NSEC3_HASH_LEN+1); 548 /* labels of length 32 for SHA1, and must have space+1 for convert */ 549 if(wire[0] != lablen) { 550 /* not NSEC3 */ 551 memset(hash, 0, buflen); 552 return; 553 } 554 (void)b32_pton((char*)wire+1, hash, buflen); 555 } 556 557 void 558 nsec3_precompile_nsec3rr(namedb_type* db, struct domain* domain, 559 struct zone* zone) 560 { 561 allocate_domain_nsec3(db->domains, domain); 562 /* add into nsec3tree */ 563 zone_add_domain_in_hash_tree(db->region, &zone->nsec3tree, 564 cmp_nsec3_tree, domain, &domain->nsec3->nsec3_node); 565 /* fixup the last in the zone */ 566 if(rbtree_last(zone->nsec3tree)->key == domain) { 567 zone->nsec3_last = domain; 568 } 569 } 570 571 void 572 nsec3_precompile_newparam(namedb_type* db, zone_type* zone) 573 { 574 region_type* tmpregion = region_create(xalloc, free); 575 domain_type* walk; 576 time_t s = time(NULL); 577 unsigned long n = 0, c = 0; 578 579 /* add nsec3s of chain to nsec3tree */ 580 for(walk=zone->apex; walk && domain_is_subdomain(walk, zone->apex); 581 walk = domain_next(walk)) { 582 n++; 583 if(nsec3_in_chain_count(walk, zone) != 0) { 584 nsec3_precompile_nsec3rr(db, walk, zone); 585 } 586 } 587 /* hash and precompile zone */ 588 for(walk=zone->apex; walk && domain_is_subdomain(walk, zone->apex); 589 walk = domain_next(walk)) { 590 if(nsec3_condition_hash(walk, zone)) { 591 nsec3_precompile_domain(db, walk, zone, tmpregion); 592 region_free_all(tmpregion); 593 } 594 if(nsec3_condition_dshash(walk, zone)) 595 nsec3_precompile_domain_ds(db, walk, zone); 596 if(++c % ZONEC_PCT_COUNT == 0 && time(NULL) > s + ZONEC_PCT_TIME) { 597 s = time(NULL); 598 VERBOSITY(1, (LOG_INFO, "nsec3 %s %d %%", 599 zone->opts->name, 600 (int)(c*((unsigned long)100)/n))); 601 } 602 } 603 region_destroy(tmpregion); 604 } 605 606 void 607 prehash_zone_complete(struct namedb* db, struct zone* zone) 608 { 609 udb_ptr udbz; 610 611 /* robust clear it */ 612 nsec3_clear_precompile(db, zone); 613 /* find zone settings */ 614 615 assert(db && zone); 616 if(db->udb) { 617 if(!udb_zone_search(db->udb, &udbz, dname_name(domain_dname( 618 zone->apex)), domain_dname(zone->apex)->name_size)) { 619 udb_ptr_init(&udbz, db->udb); /* zero the ptr */ 620 } 621 } 622 nsec3_find_zone_param(db, zone, &udbz, NULL); 623 if(!zone->nsec3_param || !check_apex_soa(db, zone)) { 624 zone->nsec3_param = NULL; 625 zone->nsec3_last = NULL; 626 if(db->udb) 627 udb_ptr_unlink(&udbz, db->udb); 628 return; 629 } 630 if(db->udb) 631 udb_ptr_unlink(&udbz, db->udb); 632 nsec3_precompile_newparam(db, zone); 633 } 634 635 static void 636 init_lookup_key_hash_tree(domain_type* d, uint8_t* hash) 637 { memcpy(d->nsec3->nsec3_hash, hash, NSEC3_HASH_LEN); } 638 639 static void 640 init_lookup_key_wc_tree(domain_type* d, uint8_t* hash) 641 { memcpy(d->nsec3->nsec3_wc_hash, hash, NSEC3_HASH_LEN); } 642 643 static void 644 init_lookup_key_ds_tree(domain_type* d, uint8_t* hash) 645 { memcpy(d->nsec3->nsec3_ds_parent_hash, hash, NSEC3_HASH_LEN); } 646 647 /* find first in the tree and true if the first to process it */ 648 static int 649 process_first(rbtree_t* tree, uint8_t* hash, rbnode_t** p, 650 void (*init)(domain_type*, uint8_t*)) 651 { 652 domain_type d; 653 struct nsec3_domain_data n; 654 if(!tree) { 655 *p = RBTREE_NULL; 656 return 0; 657 } 658 d.nsec3 = &n; 659 init(&d, hash); 660 if(rbtree_find_less_equal(tree, &d, p)) { 661 /* found an exact match */ 662 return 1; 663 } 664 if(!*p) /* before first, go from first */ 665 *p = rbtree_first(tree); 666 /* the inexact, smaller, match we found, does not itself need to 667 * be edited */ 668 else 669 *p = rbtree_next(*p); /* if this becomes NULL, nothing to do */ 670 return 0; 671 } 672 673 /* set end pointer if possible */ 674 static void 675 process_end(rbtree_t* tree, uint8_t* hash, rbnode_t** p, 676 void (*init)(domain_type*, uint8_t*)) 677 { 678 domain_type d; 679 struct nsec3_domain_data n; 680 if(!tree) { 681 *p = RBTREE_NULL; 682 return; 683 } 684 d.nsec3 = &n; 685 init(&d, hash); 686 if(rbtree_find_less_equal(tree, &d, p)) { 687 /* an exact match, fine, because this one does not get 688 * processed */ 689 return; 690 } 691 /* inexact element, but if NULL, until first element in tree */ 692 if(!*p) { 693 *p = rbtree_first(tree); 694 return; 695 } 696 /* inexact match, use next element, if possible, the smaller 697 * element is part of the range */ 698 *p = rbtree_next(*p); 699 /* if next returns null, we go until the end of the tree */ 700 } 701 702 /* prehash domains in hash range start to end */ 703 static void 704 process_range(zone_type* zone, domain_type* start, 705 domain_type* end, domain_type* nsec3) 706 { 707 /* start NULL means from first in tree */ 708 /* end NULL means to last in tree */ 709 rbnode_t *p = RBTREE_NULL, *pwc = RBTREE_NULL, *pds = RBTREE_NULL; 710 rbnode_t *p_end = RBTREE_NULL, *pwc_end = RBTREE_NULL, *pds_end = RBTREE_NULL; 711 /* because the nodes are on the prehashlist, the domain->nsec3 is 712 * already allocated, and we need not allocate it here */ 713 /* set start */ 714 if(start) { 715 uint8_t hash[NSEC3_HASH_LEN+1]; 716 parse_nsec3_name(domain_dname(start), hash, sizeof(hash)); 717 /* if exact match on first, set is_exact */ 718 if(process_first(zone->hashtree, hash, &p, init_lookup_key_hash_tree)) { 719 ((domain_type*)(p->key))->nsec3->nsec3_cover = nsec3; 720 ((domain_type*)(p->key))->nsec3->nsec3_is_exact = 1; 721 p = rbtree_next(p); 722 } 723 (void)process_first(zone->wchashtree, hash, &pwc, init_lookup_key_wc_tree); 724 if(process_first(zone->dshashtree, hash, &pds, init_lookup_key_ds_tree)){ 725 ((domain_type*)(pds->key))->nsec3-> 726 nsec3_ds_parent_cover = nsec3; 727 ((domain_type*)(pds->key))->nsec3-> 728 nsec3_ds_parent_is_exact = 1; 729 pds = rbtree_next(pds); 730 } 731 } else { 732 if(zone->hashtree) 733 p = rbtree_first(zone->hashtree); 734 if(zone->wchashtree) 735 pwc = rbtree_first(zone->wchashtree); 736 if(zone->dshashtree) 737 pds = rbtree_first(zone->dshashtree); 738 } 739 /* set end */ 740 if(end) { 741 uint8_t hash[NSEC3_HASH_LEN+1]; 742 parse_nsec3_name(domain_dname(end), hash, sizeof(hash)); 743 process_end(zone->hashtree, hash, &p_end, init_lookup_key_hash_tree); 744 process_end(zone->wchashtree, hash, &pwc_end, init_lookup_key_wc_tree); 745 process_end(zone->dshashtree, hash, &pds_end, init_lookup_key_ds_tree); 746 } 747 748 /* precompile */ 749 while(p != RBTREE_NULL && p != p_end) { 750 ((domain_type*)(p->key))->nsec3->nsec3_cover = nsec3; 751 ((domain_type*)(p->key))->nsec3->nsec3_is_exact = 0; 752 p = rbtree_next(p); 753 } 754 while(pwc != RBTREE_NULL && pwc != pwc_end) { 755 ((domain_type*)(pwc->key))->nsec3-> 756 nsec3_wcard_child_cover = nsec3; 757 pwc = rbtree_next(pwc); 758 } 759 while(pds != RBTREE_NULL && pds != pds_end) { 760 ((domain_type*)(pds->key))->nsec3-> 761 nsec3_ds_parent_cover = nsec3; 762 ((domain_type*)(pds->key))->nsec3-> 763 nsec3_ds_parent_is_exact = 0; 764 pds = rbtree_next(pds); 765 } 766 } 767 768 /* prehash a domain from the prehash list */ 769 static void 770 process_prehash_domain(domain_type* domain, zone_type* zone) 771 { 772 /* in the hashtree, wchashtree, dshashtree walk through to next NSEC3 773 * and set precompile pointers to point to this domain (or is_exact), 774 * the first domain can be is_exact. If it is the last NSEC3, also 775 * process the initial part (before the first) */ 776 rbnode_t* nx; 777 778 /* this domain is part of the prehash list and therefore the 779 * domain->nsec3 is allocated and need not be allocated here */ 780 assert(domain->nsec3 && domain->nsec3->nsec3_node.key); 781 nx = rbtree_next(&domain->nsec3->nsec3_node); 782 if(nx != RBTREE_NULL) { 783 /* process until next nsec3 */ 784 domain_type* end = (domain_type*)nx->key; 785 process_range(zone, domain, end, domain); 786 } else { 787 /* first is root, but then comes the first nsec3 */ 788 domain_type* first = (domain_type*)(rbtree_first( 789 zone->nsec3tree)->key); 790 /* last in zone */ 791 process_range(zone, domain, NULL, domain); 792 /* also process before first in zone */ 793 process_range(zone, NULL, first, domain); 794 } 795 } 796 797 void prehash_zone(struct namedb* db, struct zone* zone) 798 { 799 domain_type* d; 800 if(!zone->nsec3_param) { 801 prehash_clear(db->domains); 802 return; 803 } 804 /* process prehash list */ 805 for(d = db->domains->prehash_list; d; d = d->nsec3->prehash_next) { 806 process_prehash_domain(d, zone); 807 } 808 /* clear prehash list */ 809 prehash_clear(db->domains); 810 811 if(!check_apex_soa(db, zone)) { 812 zone->nsec3_param = NULL; 813 zone->nsec3_last = NULL; 814 } 815 } 816 817 /* add the NSEC3 rrset to the query answer at the given domain */ 818 static void 819 nsec3_add_rrset(struct query* query, struct answer* answer, 820 rr_section_type section, struct domain* domain) 821 { 822 if(domain) { 823 rrset_type* rrset = domain_find_rrset(domain, query->zone, TYPE_NSEC3); 824 if(rrset) 825 answer_add_rrset(answer, section, domain, rrset); 826 } 827 } 828 829 /* this routine does hashing at query-time. slow. */ 830 static void 831 nsec3_add_nonexist_proof(struct query* query, struct answer* answer, 832 struct domain* encloser, const dname_type* qname) 833 { 834 uint8_t hash[NSEC3_HASH_LEN]; 835 const dname_type* to_prove; 836 domain_type* cover=0; 837 assert(encloser); 838 /* if query=a.b.c.d encloser=c.d. then proof needed for b.c.d. */ 839 /* if query=a.b.c.d encloser=*.c.d. then proof needed for b.c.d. */ 840 to_prove = dname_partial_copy(query->region, qname, 841 dname_label_match_count(qname, domain_dname(encloser))+1); 842 /* generate proof that one label below closest encloser does not exist */ 843 nsec3_hash_and_store(query->zone, to_prove, hash); 844 if(nsec3_find_cover(query->zone, hash, sizeof(hash), &cover)) 845 { 846 /* exact match, hash collision */ 847 /* the hashed name of the query corresponds to an existing name. */ 848 log_msg(LOG_ERR, "nsec3 hash collision for name=%s", 849 dname_to_string(to_prove, NULL)); 850 RCODE_SET(query->packet, RCODE_SERVFAIL); 851 return; 852 } 853 else 854 { 855 /* cover proves the qname does not exist */ 856 nsec3_add_rrset(query, answer, AUTHORITY_SECTION, cover); 857 } 858 } 859 860 static void 861 nsec3_add_closest_encloser_proof( 862 struct query* query, struct answer* answer, 863 struct domain* closest_encloser, const dname_type* qname) 864 { 865 if(!closest_encloser) 866 return; 867 /* prove that below closest encloser nothing exists */ 868 nsec3_add_nonexist_proof(query, answer, closest_encloser, qname); 869 /* proof that closest encloser exists */ 870 if(closest_encloser->nsec3 && closest_encloser->nsec3->nsec3_is_exact) 871 nsec3_add_rrset(query, answer, AUTHORITY_SECTION, 872 closest_encloser->nsec3->nsec3_cover); 873 } 874 875 void 876 nsec3_answer_wildcard(struct query *query, struct answer *answer, 877 struct domain *wildcard, const dname_type* qname) 878 { 879 if(!wildcard) 880 return; 881 if(!query->zone->nsec3_param) 882 return; 883 nsec3_add_nonexist_proof(query, answer, wildcard, qname); 884 } 885 886 static void 887 nsec3_add_ds_proof(struct query *query, struct answer *answer, 888 struct domain *domain, int delegpt) 889 { 890 /* assert we are above the zone cut */ 891 assert(domain != query->zone->apex); 892 if(domain->nsec3 && domain->nsec3->nsec3_ds_parent_is_exact) { 893 /* use NSEC3 record from above the zone cut. */ 894 nsec3_add_rrset(query, answer, AUTHORITY_SECTION, 895 domain->nsec3->nsec3_ds_parent_cover); 896 } else if (!delegpt && domain->nsec3 && domain->nsec3->nsec3_is_exact) { 897 nsec3_add_rrset(query, answer, AUTHORITY_SECTION, 898 domain->nsec3->nsec3_cover); 899 } else { 900 /* prove closest provable encloser */ 901 domain_type* par = domain->parent; 902 domain_type* prev_par = 0; 903 904 while(par && (!par->nsec3 || !par->nsec3->nsec3_is_exact)) 905 { 906 prev_par = par; 907 par = par->parent; 908 } 909 assert(par); /* parent zone apex must be provable, thus this ends */ 910 if(!par->nsec3) return; 911 nsec3_add_rrset(query, answer, AUTHORITY_SECTION, 912 par->nsec3->nsec3_cover); 913 /* we took several steps to go to the provable parent, so 914 the one below it has no exact nsec3, disprove it. 915 disprove is easy, it has a prehashed cover ptr. */ 916 if(prev_par && prev_par->nsec3) { 917 assert(prev_par != domain && 918 !prev_par->nsec3->nsec3_is_exact); 919 nsec3_add_rrset(query, answer, AUTHORITY_SECTION, 920 prev_par->nsec3->nsec3_cover); 921 } 922 /* add optout range from parent zone */ 923 /* note: no check of optout bit, resolver checks it */ 924 if(domain->nsec3) 925 nsec3_add_rrset(query, answer, AUTHORITY_SECTION, 926 domain->nsec3->nsec3_ds_parent_cover); 927 } 928 } 929 930 void 931 nsec3_answer_nodata(struct query* query, struct answer* answer, 932 struct domain* original) 933 { 934 if(!query->zone->nsec3_param) 935 return; 936 /* nodata when asking for secure delegation */ 937 if(query->qtype == TYPE_DS) 938 { 939 if(original == query->zone->apex) { 940 /* DS at zone apex, but server not authoritative for parent zone */ 941 /* so answer at the child zone level */ 942 if(original->nsec3 && original->nsec3->nsec3_is_exact) 943 nsec3_add_rrset(query, answer, AUTHORITY_SECTION, 944 original->nsec3->nsec3_cover); 945 return; 946 } 947 /* query->zone must be the parent zone */ 948 nsec3_add_ds_proof(query, answer, original, 0); 949 } 950 /* the nodata is result from a wildcard match */ 951 else if (original==original->wildcard_child_closest_match 952 && label_is_wildcard(dname_name(domain_dname(original)))) { 953 /* denial for wildcard is already there */ 954 955 /* add parent proof to have a closest encloser proof for wildcard parent */ 956 /* in other words: nsec3 matching closest encloser */ 957 if(original->parent && original->parent->nsec3 && 958 original->parent->nsec3->nsec3_is_exact) 959 nsec3_add_rrset(query, answer, AUTHORITY_SECTION, 960 original->parent->nsec3->nsec3_cover); 961 /* proof for wildcard itself */ 962 /* in other words: nsec3 matching source of synthesis */ 963 if(original->nsec3) 964 nsec3_add_rrset(query, answer, AUTHORITY_SECTION, 965 original->nsec3->nsec3_cover); 966 } 967 else { /* add nsec3 to prove rrset does not exist */ 968 if(original->nsec3 && original->nsec3->nsec3_is_exact) { 969 nsec3_add_rrset(query, answer, AUTHORITY_SECTION, 970 original->nsec3->nsec3_cover); 971 } 972 } 973 } 974 975 void 976 nsec3_answer_delegation(struct query *query, struct answer *answer) 977 { 978 if(!query->zone->nsec3_param) 979 return; 980 nsec3_add_ds_proof(query, answer, query->delegation_domain, 1); 981 } 982 983 int 984 domain_has_only_NSEC3(struct domain* domain, struct zone* zone) 985 { 986 /* check for only NSEC3/RRSIG */ 987 rrset_type* rrset = domain->rrsets; 988 int nsec3_seen = 0; 989 while(rrset) 990 { 991 if(!zone || rrset->zone == zone) 992 { 993 if(rrset->rrs[0].type == TYPE_NSEC3) 994 nsec3_seen = 1; 995 else if(rrset->rrs[0].type != TYPE_RRSIG) 996 return 0; 997 } 998 rrset = rrset->next; 999 } 1000 return nsec3_seen; 1001 } 1002 1003 void 1004 nsec3_answer_authoritative(struct domain** match, struct query *query, 1005 struct answer *answer, struct domain* closest_encloser, 1006 const dname_type* qname) 1007 { 1008 if(!query->zone->nsec3_param) 1009 return; 1010 assert(match); 1011 /* there is a match, this has 1 RRset, which is NSEC3, but qtype is not. */ 1012 /* !is_existing: no RR types exist at the QNAME, nor at any descendant of QNAME */ 1013 if(*match && !(*match)->is_existing && 1014 #if 0 1015 query->qtype != TYPE_NSEC3 && 1016 #endif 1017 domain_has_only_NSEC3(*match, query->zone)) 1018 { 1019 /* act as if the NSEC3 domain did not exist, name error */ 1020 *match = 0; 1021 /* all nsec3s are directly below the apex, that is closest encloser */ 1022 if(query->zone->apex->nsec3 && 1023 query->zone->apex->nsec3->nsec3_is_exact) 1024 nsec3_add_rrset(query, answer, AUTHORITY_SECTION, 1025 query->zone->apex->nsec3->nsec3_cover); 1026 /* disprove the nsec3 record. */ 1027 if(closest_encloser->nsec3) 1028 nsec3_add_rrset(query, answer, AUTHORITY_SECTION, closest_encloser->nsec3->nsec3_cover); 1029 /* disprove a wildcard */ 1030 if(query->zone->apex->nsec3) 1031 nsec3_add_rrset(query, answer, AUTHORITY_SECTION, 1032 query->zone->apex->nsec3->nsec3_wcard_child_cover); 1033 if (domain_wildcard_child(query->zone->apex)) { 1034 /* wildcard exists below the domain */ 1035 /* wildcard and nsec3 domain clash. server failure. */ 1036 RCODE_SET(query->packet, RCODE_SERVFAIL); 1037 } 1038 return; 1039 } 1040 else if(*match && (*match)->is_existing && 1041 #if 0 1042 query->qtype != TYPE_NSEC3 && 1043 #endif 1044 domain_has_only_NSEC3(*match, query->zone)) 1045 { 1046 /* this looks like a NSEC3 domain, but is actually an empty non-terminal. */ 1047 nsec3_answer_nodata(query, answer, *match); 1048 return; 1049 } 1050 if(!*match) { 1051 /* name error, domain does not exist */ 1052 nsec3_add_closest_encloser_proof(query, answer, closest_encloser, 1053 qname); 1054 if(closest_encloser->nsec3) 1055 nsec3_add_rrset(query, answer, AUTHORITY_SECTION, 1056 closest_encloser->nsec3->nsec3_wcard_child_cover); 1057 } 1058 } 1059 1060 #endif /* NSEC3 */ 1061