1/* $NetBSD: nsec.c,v 1.10 2024/02/21 22:52:07 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 42void 43dns_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 56bool 57dns_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 67unsigned int 68dns_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 103isc_result_t 104dns_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 182isc_result_t 183dns_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 RETERR(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 207failure: 208 if (dns_rdataset_isassociated(&rdataset)) { 209 dns_rdataset_disassociate(&rdataset); 210 } 211 return (result); 212} 213 214bool 215dns_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 252isc_result_t 253dns_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_DH || 290 dnskey.algorithm == DST_ALG_DSA || 291 dnskey.algorithm == DST_ALG_RSASHA1) 292 { 293 bool deleted = false; 294 if (diff != NULL) { 295 for (dns_difftuple_t *tuple = 296 ISC_LIST_HEAD(diff->tuples); 297 tuple != NULL; 298 tuple = ISC_LIST_NEXT(tuple, link)) 299 { 300 if (tuple->rdata.type != 301 dns_rdatatype_dnskey || 302 tuple->op != DNS_DIFFOP_DEL) 303 { 304 continue; 305 } 306 307 if (dns_rdata_compare( 308 &rdata, &tuple->rdata) == 0) 309 { 310 deleted = true; 311 break; 312 } 313 } 314 } 315 316 if (!deleted) { 317 break; 318 } 319 } 320 } 321 dns_rdataset_disassociate(&rdataset); 322 if (result == ISC_R_SUCCESS) { 323 *answer = true; 324 } 325 if (result == ISC_R_NOMORE) { 326 *answer = false; 327 result = ISC_R_SUCCESS; 328 } 329 return (result); 330} 331 332/*% 333 * Return ISC_R_SUCCESS if we can determine that the name doesn't exist 334 * or we can determine whether there is data or not at the name. 335 * If the name does not exist return the wildcard name. 336 * 337 * Return ISC_R_IGNORE when the NSEC is not the appropriate one. 338 */ 339isc_result_t 340dns_nsec_noexistnodata(dns_rdatatype_t type, const dns_name_t *name, 341 const dns_name_t *nsecname, dns_rdataset_t *nsecset, 342 bool *exists, bool *data, dns_name_t *wild, 343 dns_nseclog_t logit, void *arg) { 344 int order; 345 dns_rdata_t rdata = DNS_RDATA_INIT; 346 isc_result_t result; 347 dns_namereln_t relation; 348 unsigned int olabels, nlabels, labels; 349 dns_rdata_nsec_t nsec; 350 bool atparent; 351 bool ns; 352 bool soa; 353 354 REQUIRE(exists != NULL); 355 REQUIRE(data != NULL); 356 REQUIRE(nsecset != NULL && nsecset->type == dns_rdatatype_nsec); 357 358 result = dns_rdataset_first(nsecset); 359 if (result != ISC_R_SUCCESS) { 360 (*logit)(arg, ISC_LOG_DEBUG(3), "failure processing NSEC set"); 361 return (result); 362 } 363 dns_rdataset_current(nsecset, &rdata); 364 365#ifdef notyet 366 if (!dns_nsec_typepresent(&rdata, dns_rdatatype_rrsig) || 367 !dns_nsec_typepresent(&rdata, dns_rdatatype_nsec)) 368 { 369 (*logit)(arg, ISC_LOG_DEBUG(3), 370 "NSEC missing RRSIG and/or NSEC from type map"); 371 return (ISC_R_IGNORE); 372 } 373#endif 374 375 (*logit)(arg, ISC_LOG_DEBUG(3), "looking for relevant NSEC"); 376 relation = dns_name_fullcompare(name, nsecname, &order, &olabels); 377 378 if (order < 0) { 379 /* 380 * The name is not within the NSEC range. 381 */ 382 (*logit)(arg, ISC_LOG_DEBUG(3), 383 "NSEC does not cover name, before NSEC"); 384 return (ISC_R_IGNORE); 385 } 386 387 if (order == 0) { 388 /* 389 * The names are the same. If we are validating "." 390 * then atparent should not be set as there is no parent. 391 */ 392 atparent = (olabels != 1) && dns_rdatatype_atparent(type); 393 ns = dns_nsec_typepresent(&rdata, dns_rdatatype_ns); 394 soa = dns_nsec_typepresent(&rdata, dns_rdatatype_soa); 395 if (ns && !soa) { 396 if (!atparent) { 397 /* 398 * This NSEC record is from somewhere higher in 399 * the DNS, and at the parent of a delegation. 400 * It can not be legitimately used here. 401 */ 402 (*logit)(arg, ISC_LOG_DEBUG(3), 403 "ignoring parent nsec"); 404 return (ISC_R_IGNORE); 405 } 406 } else if (atparent && ns && soa) { 407 /* 408 * This NSEC record is from the child. 409 * It can not be legitimately used here. 410 */ 411 (*logit)(arg, ISC_LOG_DEBUG(3), "ignoring child nsec"); 412 return (ISC_R_IGNORE); 413 } 414 if (type == dns_rdatatype_cname || type == dns_rdatatype_nxt || 415 type == dns_rdatatype_nsec || type == dns_rdatatype_key || 416 !dns_nsec_typepresent(&rdata, dns_rdatatype_cname)) 417 { 418 *exists = true; 419 *data = dns_nsec_typepresent(&rdata, type); 420 (*logit)(arg, ISC_LOG_DEBUG(3), 421 "nsec proves name exists (owner) data=%d", 422 *data); 423 return (ISC_R_SUCCESS); 424 } 425 (*logit)(arg, ISC_LOG_DEBUG(3), "NSEC proves CNAME exists"); 426 return (ISC_R_IGNORE); 427 } 428 429 if (relation == dns_namereln_subdomain && 430 dns_nsec_typepresent(&rdata, dns_rdatatype_ns) && 431 !dns_nsec_typepresent(&rdata, dns_rdatatype_soa)) 432 { 433 /* 434 * This NSEC record is from somewhere higher in 435 * the DNS, and at the parent of a delegation or 436 * at a DNAME. 437 * It can not be legitimately used here. 438 */ 439 (*logit)(arg, ISC_LOG_DEBUG(3), "ignoring parent nsec"); 440 return (ISC_R_IGNORE); 441 } 442 443 if (relation == dns_namereln_subdomain && 444 dns_nsec_typepresent(&rdata, dns_rdatatype_dname)) 445 { 446 (*logit)(arg, ISC_LOG_DEBUG(3), "nsec proves covered by dname"); 447 *exists = false; 448 return (DNS_R_DNAME); 449 } 450 451 result = dns_rdata_tostruct(&rdata, &nsec, NULL); 452 if (result != ISC_R_SUCCESS) { 453 return (result); 454 } 455 relation = dns_name_fullcompare(&nsec.next, name, &order, &nlabels); 456 if (order == 0) { 457 dns_rdata_freestruct(&nsec); 458 (*logit)(arg, ISC_LOG_DEBUG(3), 459 "ignoring nsec matches next name"); 460 return (ISC_R_IGNORE); 461 } 462 463 if (order < 0 && !dns_name_issubdomain(nsecname, &nsec.next)) { 464 /* 465 * The name is not within the NSEC range. 466 */ 467 dns_rdata_freestruct(&nsec); 468 (*logit)(arg, ISC_LOG_DEBUG(3), 469 "ignoring nsec because name is past end of range"); 470 return (ISC_R_IGNORE); 471 } 472 473 if (order > 0 && relation == dns_namereln_subdomain) { 474 (*logit)(arg, ISC_LOG_DEBUG(3), 475 "nsec proves name exist (empty)"); 476 dns_rdata_freestruct(&nsec); 477 *exists = true; 478 *data = false; 479 return (ISC_R_SUCCESS); 480 } 481 if (wild != NULL) { 482 dns_name_t common; 483 dns_name_init(&common, NULL); 484 if (olabels > nlabels) { 485 labels = dns_name_countlabels(nsecname); 486 dns_name_getlabelsequence(nsecname, labels - olabels, 487 olabels, &common); 488 } else { 489 labels = dns_name_countlabels(&nsec.next); 490 dns_name_getlabelsequence(&nsec.next, labels - nlabels, 491 nlabels, &common); 492 } 493 result = dns_name_concatenate(dns_wildcardname, &common, wild, 494 NULL); 495 if (result != ISC_R_SUCCESS) { 496 dns_rdata_freestruct(&nsec); 497 (*logit)(arg, ISC_LOG_DEBUG(3), 498 "failure generating wildcard name"); 499 return (result); 500 } 501 } 502 dns_rdata_freestruct(&nsec); 503 (*logit)(arg, ISC_LOG_DEBUG(3), "nsec range ok"); 504 *exists = false; 505 return (ISC_R_SUCCESS); 506} 507 508bool 509dns_nsec_requiredtypespresent(dns_rdataset_t *nsecset) { 510 dns_rdataset_t rdataset; 511 isc_result_t result; 512 bool found = false; 513 514 REQUIRE(DNS_RDATASET_VALID(nsecset)); 515 REQUIRE(nsecset->type == dns_rdatatype_nsec); 516 517 dns_rdataset_init(&rdataset); 518 dns_rdataset_clone(nsecset, &rdataset); 519 520 for (result = dns_rdataset_first(&rdataset); result == ISC_R_SUCCESS; 521 result = dns_rdataset_next(&rdataset)) 522 { 523 dns_rdata_t rdata = DNS_RDATA_INIT; 524 dns_rdataset_current(&rdataset, &rdata); 525 if (!dns_nsec_typepresent(&rdata, dns_rdatatype_nsec) || 526 !dns_nsec_typepresent(&rdata, dns_rdatatype_rrsig)) 527 { 528 dns_rdataset_disassociate(&rdataset); 529 return (false); 530 } 531 found = true; 532 } 533 dns_rdataset_disassociate(&rdataset); 534 return (found); 535} 536