1 /* $NetBSD: nsec.c,v 1.11 2025/01/26 16:25:23 christos Exp $ */ 2 3 /* 4 * Copyright (C) Internet Systems Consortium, Inc. ("ISC") 5 * 6 * SPDX-License-Identifier: MPL-2.0 7 * 8 * This Source Code Form is subject to the terms of the Mozilla Public 9 * License, v. 2.0. If a copy of the MPL was not distributed with this 10 * file, you can obtain one at https://mozilla.org/MPL/2.0/. 11 * 12 * See the COPYRIGHT file distributed with this work for additional 13 * information regarding copyright ownership. 14 */ 15 16 /*! \file */ 17 18 #include <stdbool.h> 19 20 #include <isc/log.h> 21 #include <isc/result.h> 22 #include <isc/string.h> 23 #include <isc/util.h> 24 25 #include <dns/db.h> 26 #include <dns/nsec.h> 27 #include <dns/rdata.h> 28 #include <dns/rdatalist.h> 29 #include <dns/rdataset.h> 30 #include <dns/rdatasetiter.h> 31 #include <dns/rdatastruct.h> 32 33 #include <dst/dst.h> 34 35 #define RETERR(x) \ 36 do { \ 37 result = (x); \ 38 if (result != ISC_R_SUCCESS) \ 39 goto failure; \ 40 } while (0) 41 42 void 43 dns_nsec_setbit(unsigned char *array, unsigned int type, unsigned int bit) { 44 unsigned int shift, mask; 45 46 shift = 7 - (type % 8); 47 mask = 1 << shift; 48 49 if (bit != 0) { 50 array[type / 8] |= mask; 51 } else { 52 array[type / 8] &= (~mask & 0xFF); 53 } 54 } 55 56 bool 57 dns_nsec_isset(const unsigned char *array, unsigned int type) { 58 unsigned int byte, shift, mask; 59 60 byte = array[type / 8]; 61 shift = 7 - (type % 8); 62 mask = 1 << shift; 63 64 return (byte & mask) != 0; 65 } 66 67 unsigned int 68 dns_nsec_compressbitmap(unsigned char *map, const unsigned char *raw, 69 unsigned int max_type) { 70 unsigned char *start = map; 71 unsigned int window; 72 int octet; 73 74 if (raw == NULL) { 75 return 0; 76 } 77 78 for (window = 0; window < 256; window++) { 79 if (window * 256 > max_type) { 80 break; 81 } 82 for (octet = 31; octet >= 0; octet--) { 83 if (*(raw + octet) != 0) { 84 break; 85 } 86 } 87 if (octet < 0) { 88 raw += 32; 89 continue; 90 } 91 *map++ = window; 92 *map++ = octet + 1; 93 /* 94 * Note: potential overlapping move. 95 */ 96 memmove(map, raw, octet + 1); 97 map += octet + 1; 98 raw += 32; 99 } 100 return (unsigned int)(map - start); 101 } 102 103 isc_result_t 104 dns_nsec_buildrdata(dns_db_t *db, dns_dbversion_t *version, dns_dbnode_t *node, 105 const dns_name_t *target, unsigned char *buffer, 106 dns_rdata_t *rdata) { 107 isc_result_t result; 108 dns_rdataset_t rdataset; 109 isc_region_t r; 110 unsigned int i; 111 112 unsigned char *nsec_bits, *bm; 113 unsigned int max_type; 114 dns_rdatasetiter_t *rdsiter; 115 116 REQUIRE(target != NULL); 117 118 memset(buffer, 0, DNS_NSEC_BUFFERSIZE); 119 dns_name_toregion(target, &r); 120 memmove(buffer, r.base, r.length); 121 r.base = buffer; 122 /* 123 * Use the end of the space for a raw bitmap leaving enough 124 * space for the window identifiers and length octets. 125 */ 126 bm = r.base + r.length + 512; 127 nsec_bits = r.base + r.length; 128 dns_nsec_setbit(bm, dns_rdatatype_rrsig, 1); 129 dns_nsec_setbit(bm, dns_rdatatype_nsec, 1); 130 max_type = dns_rdatatype_nsec; 131 dns_rdataset_init(&rdataset); 132 rdsiter = NULL; 133 result = dns_db_allrdatasets(db, node, version, 0, 0, &rdsiter); 134 if (result != ISC_R_SUCCESS) { 135 return result; 136 } 137 for (result = dns_rdatasetiter_first(rdsiter); result == ISC_R_SUCCESS; 138 result = dns_rdatasetiter_next(rdsiter)) 139 { 140 dns_rdatasetiter_current(rdsiter, &rdataset); 141 if (rdataset.type != dns_rdatatype_nsec && 142 rdataset.type != dns_rdatatype_nsec3 && 143 rdataset.type != dns_rdatatype_rrsig) 144 { 145 if (rdataset.type > max_type) { 146 max_type = rdataset.type; 147 } 148 dns_nsec_setbit(bm, rdataset.type, 1); 149 } 150 dns_rdataset_disassociate(&rdataset); 151 } 152 153 /* 154 * At zone cuts, deny the existence of glue in the parent zone. 155 */ 156 if (dns_nsec_isset(bm, dns_rdatatype_ns) && 157 !dns_nsec_isset(bm, dns_rdatatype_soa)) 158 { 159 for (i = 0; i <= max_type; i++) { 160 if (dns_nsec_isset(bm, i) && 161 !dns_rdatatype_iszonecutauth((dns_rdatatype_t)i)) 162 { 163 dns_nsec_setbit(bm, i, 0); 164 } 165 } 166 } 167 168 dns_rdatasetiter_destroy(&rdsiter); 169 if (result != ISC_R_NOMORE) { 170 return result; 171 } 172 173 nsec_bits += dns_nsec_compressbitmap(nsec_bits, bm, max_type); 174 175 r.length = (unsigned int)(nsec_bits - r.base); 176 INSIST(r.length <= DNS_NSEC_BUFFERSIZE); 177 dns_rdata_fromregion(rdata, dns_db_class(db), dns_rdatatype_nsec, &r); 178 179 return ISC_R_SUCCESS; 180 } 181 182 isc_result_t 183 dns_nsec_build(dns_db_t *db, dns_dbversion_t *version, dns_dbnode_t *node, 184 const dns_name_t *target, dns_ttl_t ttl) { 185 isc_result_t result; 186 dns_rdata_t rdata = DNS_RDATA_INIT; 187 unsigned char data[DNS_NSEC_BUFFERSIZE]; 188 dns_rdatalist_t rdatalist; 189 dns_rdataset_t rdataset; 190 191 dns_rdataset_init(&rdataset); 192 dns_rdata_init(&rdata); 193 194 RETERR(dns_nsec_buildrdata(db, version, node, target, data, &rdata)); 195 196 dns_rdatalist_init(&rdatalist); 197 rdatalist.rdclass = dns_db_class(db); 198 rdatalist.type = dns_rdatatype_nsec; 199 rdatalist.ttl = ttl; 200 ISC_LIST_APPEND(rdatalist.rdata, &rdata, link); 201 dns_rdatalist_tordataset(&rdatalist, &rdataset); 202 result = dns_db_addrdataset(db, node, version, 0, &rdataset, 0, NULL); 203 if (result == DNS_R_UNCHANGED) { 204 result = ISC_R_SUCCESS; 205 } 206 207 failure: 208 if (dns_rdataset_isassociated(&rdataset)) { 209 dns_rdataset_disassociate(&rdataset); 210 } 211 return result; 212 } 213 214 bool 215 dns_nsec_typepresent(dns_rdata_t *nsec, dns_rdatatype_t type) { 216 dns_rdata_nsec_t nsecstruct; 217 isc_result_t result; 218 bool present; 219 unsigned int i, len, window; 220 221 REQUIRE(nsec != NULL); 222 REQUIRE(nsec->type == dns_rdatatype_nsec); 223 224 /* This should never fail */ 225 result = dns_rdata_tostruct(nsec, &nsecstruct, NULL); 226 INSIST(result == ISC_R_SUCCESS); 227 228 present = false; 229 for (i = 0; i < nsecstruct.len; i += len) { 230 INSIST(i + 2 <= nsecstruct.len); 231 window = nsecstruct.typebits[i]; 232 len = nsecstruct.typebits[i + 1]; 233 INSIST(len > 0 && len <= 32); 234 i += 2; 235 INSIST(i + len <= nsecstruct.len); 236 if (window * 256 > type) { 237 break; 238 } 239 if ((window + 1) * 256 <= type) { 240 continue; 241 } 242 if (type < (window * 256) + len * 8) { 243 present = dns_nsec_isset(&nsecstruct.typebits[i], 244 type % 256); 245 } 246 break; 247 } 248 dns_rdata_freestruct(&nsecstruct); 249 return present; 250 } 251 252 isc_result_t 253 dns_nsec_nseconly(dns_db_t *db, dns_dbversion_t *version, dns_diff_t *diff, 254 bool *answer) { 255 dns_dbnode_t *node = NULL; 256 dns_rdataset_t rdataset; 257 dns_rdata_dnskey_t dnskey; 258 isc_result_t result; 259 260 REQUIRE(answer != NULL); 261 262 dns_rdataset_init(&rdataset); 263 264 result = dns_db_getoriginnode(db, &node); 265 if (result != ISC_R_SUCCESS) { 266 return result; 267 } 268 269 result = dns_db_findrdataset(db, node, version, dns_rdatatype_dnskey, 0, 270 0, &rdataset, NULL); 271 dns_db_detachnode(db, &node); 272 273 if (result == ISC_R_NOTFOUND) { 274 *answer = false; 275 } 276 if (result != ISC_R_SUCCESS) { 277 return result; 278 } 279 for (result = dns_rdataset_first(&rdataset); result == ISC_R_SUCCESS; 280 result = dns_rdataset_next(&rdataset)) 281 { 282 dns_rdata_t rdata = DNS_RDATA_INIT; 283 284 dns_rdataset_current(&rdataset, &rdata); 285 result = dns_rdata_tostruct(&rdata, &dnskey, NULL); 286 RUNTIME_CHECK(result == ISC_R_SUCCESS); 287 288 if (dnskey.algorithm == DST_ALG_RSAMD5 || 289 dnskey.algorithm == DST_ALG_DSA || 290 dnskey.algorithm == DST_ALG_RSASHA1) 291 { 292 bool deleted = false; 293 if (diff != NULL) { 294 for (dns_difftuple_t *tuple = 295 ISC_LIST_HEAD(diff->tuples); 296 tuple != NULL; 297 tuple = ISC_LIST_NEXT(tuple, link)) 298 { 299 if (tuple->rdata.type != 300 dns_rdatatype_dnskey || 301 tuple->op != DNS_DIFFOP_DEL) 302 { 303 continue; 304 } 305 306 if (dns_rdata_compare( 307 &rdata, &tuple->rdata) == 0) 308 { 309 deleted = true; 310 break; 311 } 312 } 313 } 314 315 if (!deleted) { 316 break; 317 } 318 } 319 } 320 dns_rdataset_disassociate(&rdataset); 321 if (result == ISC_R_SUCCESS) { 322 *answer = true; 323 } 324 if (result == ISC_R_NOMORE) { 325 *answer = false; 326 result = ISC_R_SUCCESS; 327 } 328 return result; 329 } 330 331 /*% 332 * Return ISC_R_SUCCESS if we can determine that the name doesn't exist 333 * or we can determine whether there is data or not at the name. 334 * If the name does not exist return the wildcard name. 335 * 336 * Return ISC_R_IGNORE when the NSEC is not the appropriate one. 337 */ 338 isc_result_t 339 dns_nsec_noexistnodata(dns_rdatatype_t type, const dns_name_t *name, 340 const dns_name_t *nsecname, dns_rdataset_t *nsecset, 341 bool *exists, bool *data, dns_name_t *wild, 342 dns_nseclog_t logit, void *arg) { 343 int order; 344 dns_rdata_t rdata = DNS_RDATA_INIT; 345 isc_result_t result; 346 dns_namereln_t relation; 347 unsigned int olabels, nlabels, labels; 348 dns_rdata_nsec_t nsec; 349 bool atparent; 350 bool ns; 351 bool soa; 352 353 REQUIRE(exists != NULL); 354 REQUIRE(data != NULL); 355 REQUIRE(nsecset != NULL && nsecset->type == dns_rdatatype_nsec); 356 357 result = dns_rdataset_first(nsecset); 358 if (result != ISC_R_SUCCESS) { 359 (*logit)(arg, ISC_LOG_DEBUG(3), "failure processing NSEC set"); 360 return result; 361 } 362 dns_rdataset_current(nsecset, &rdata); 363 364 #ifdef notyet 365 if (!dns_nsec_typepresent(&rdata, dns_rdatatype_rrsig) || 366 !dns_nsec_typepresent(&rdata, dns_rdatatype_nsec)) 367 { 368 (*logit)(arg, ISC_LOG_DEBUG(3), 369 "NSEC missing RRSIG and/or NSEC from type map"); 370 return ISC_R_IGNORE; 371 } 372 #endif 373 374 (*logit)(arg, ISC_LOG_DEBUG(3), "looking for relevant NSEC"); 375 relation = dns_name_fullcompare(name, nsecname, &order, &olabels); 376 377 if (order < 0) { 378 /* 379 * The name is not within the NSEC range. 380 */ 381 (*logit)(arg, ISC_LOG_DEBUG(3), 382 "NSEC does not cover name, before NSEC"); 383 return ISC_R_IGNORE; 384 } 385 386 if (order == 0) { 387 /* 388 * The names are the same. If we are validating "." 389 * then atparent should not be set as there is no parent. 390 */ 391 atparent = (olabels != 1) && dns_rdatatype_atparent(type); 392 ns = dns_nsec_typepresent(&rdata, dns_rdatatype_ns); 393 soa = dns_nsec_typepresent(&rdata, dns_rdatatype_soa); 394 if (ns && !soa) { 395 if (!atparent) { 396 /* 397 * This NSEC record is from somewhere higher in 398 * the DNS, and at the parent of a delegation. 399 * It can not be legitimately used here. 400 */ 401 (*logit)(arg, ISC_LOG_DEBUG(3), 402 "ignoring parent nsec"); 403 return ISC_R_IGNORE; 404 } 405 } else if (atparent && ns && soa) { 406 /* 407 * This NSEC record is from the child. 408 * It can not be legitimately used here. 409 */ 410 (*logit)(arg, ISC_LOG_DEBUG(3), "ignoring child nsec"); 411 return ISC_R_IGNORE; 412 } 413 if (type == dns_rdatatype_cname || type == dns_rdatatype_nxt || 414 type == dns_rdatatype_nsec || type == dns_rdatatype_key || 415 !dns_nsec_typepresent(&rdata, dns_rdatatype_cname)) 416 { 417 *exists = true; 418 *data = dns_nsec_typepresent(&rdata, type); 419 (*logit)(arg, ISC_LOG_DEBUG(3), 420 "nsec proves name exists (owner) data=%d", 421 *data); 422 return ISC_R_SUCCESS; 423 } 424 (*logit)(arg, ISC_LOG_DEBUG(3), "NSEC proves CNAME exists"); 425 return ISC_R_IGNORE; 426 } 427 428 if (relation == dns_namereln_subdomain && 429 dns_nsec_typepresent(&rdata, dns_rdatatype_ns) && 430 !dns_nsec_typepresent(&rdata, dns_rdatatype_soa)) 431 { 432 /* 433 * This NSEC record is from somewhere higher in 434 * the DNS, and at the parent of a delegation or 435 * at a DNAME. 436 * It can not be legitimately used here. 437 */ 438 (*logit)(arg, ISC_LOG_DEBUG(3), "ignoring parent nsec"); 439 return ISC_R_IGNORE; 440 } 441 442 if (relation == dns_namereln_subdomain && 443 dns_nsec_typepresent(&rdata, dns_rdatatype_dname)) 444 { 445 (*logit)(arg, ISC_LOG_DEBUG(3), "nsec proves covered by dname"); 446 *exists = false; 447 return DNS_R_DNAME; 448 } 449 450 result = dns_rdata_tostruct(&rdata, &nsec, NULL); 451 if (result != ISC_R_SUCCESS) { 452 return result; 453 } 454 relation = dns_name_fullcompare(&nsec.next, name, &order, &nlabels); 455 if (order == 0) { 456 dns_rdata_freestruct(&nsec); 457 (*logit)(arg, ISC_LOG_DEBUG(3), 458 "ignoring nsec matches next name"); 459 return ISC_R_IGNORE; 460 } 461 462 if (order < 0 && !dns_name_issubdomain(nsecname, &nsec.next)) { 463 /* 464 * The name is not within the NSEC range. 465 */ 466 dns_rdata_freestruct(&nsec); 467 (*logit)(arg, ISC_LOG_DEBUG(3), 468 "ignoring nsec because name is past end of range"); 469 return ISC_R_IGNORE; 470 } 471 472 if (order > 0 && relation == dns_namereln_subdomain) { 473 (*logit)(arg, ISC_LOG_DEBUG(3), 474 "nsec proves name exist (empty)"); 475 dns_rdata_freestruct(&nsec); 476 *exists = true; 477 *data = false; 478 return ISC_R_SUCCESS; 479 } 480 if (wild != NULL) { 481 dns_name_t common; 482 dns_name_init(&common, NULL); 483 if (olabels > nlabels) { 484 labels = dns_name_countlabels(nsecname); 485 dns_name_getlabelsequence(nsecname, labels - olabels, 486 olabels, &common); 487 } else { 488 labels = dns_name_countlabels(&nsec.next); 489 dns_name_getlabelsequence(&nsec.next, labels - nlabels, 490 nlabels, &common); 491 } 492 result = dns_name_concatenate(dns_wildcardname, &common, wild, 493 NULL); 494 if (result != ISC_R_SUCCESS) { 495 dns_rdata_freestruct(&nsec); 496 (*logit)(arg, ISC_LOG_DEBUG(3), 497 "failure generating wildcard name"); 498 return result; 499 } 500 } 501 dns_rdata_freestruct(&nsec); 502 (*logit)(arg, ISC_LOG_DEBUG(3), "nsec range ok"); 503 *exists = false; 504 return ISC_R_SUCCESS; 505 } 506 507 bool 508 dns_nsec_requiredtypespresent(dns_rdataset_t *nsecset) { 509 dns_rdataset_t rdataset; 510 isc_result_t result; 511 bool found = false; 512 513 REQUIRE(DNS_RDATASET_VALID(nsecset)); 514 REQUIRE(nsecset->type == dns_rdatatype_nsec); 515 516 dns_rdataset_init(&rdataset); 517 dns_rdataset_clone(nsecset, &rdataset); 518 519 for (result = dns_rdataset_first(&rdataset); result == ISC_R_SUCCESS; 520 result = dns_rdataset_next(&rdataset)) 521 { 522 dns_rdata_t rdata = DNS_RDATA_INIT; 523 dns_rdataset_current(&rdataset, &rdata); 524 if (!dns_nsec_typepresent(&rdata, dns_rdatatype_nsec) || 525 !dns_nsec_typepresent(&rdata, dns_rdatatype_rrsig)) 526 { 527 dns_rdataset_disassociate(&rdataset); 528 return false; 529 } 530 found = true; 531 } 532 dns_rdataset_disassociate(&rdataset); 533 return found; 534 } 535