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