1/* $NetBSD: rpz.c,v 1.2.8.2 2012/12/15 05:39:59 riz Exp $ */ 2 3/* 4 * Copyright (C) 2011, 2012 Internet Systems Consortium, Inc. ("ISC") 5 * 6 * Permission to use, copy, modify, and/or distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH 11 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY 12 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT, 13 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM 14 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE 15 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 16 * PERFORMANCE OF THIS SOFTWARE. 17 */ 18 19/* Id */ 20 21/*! \file */ 22 23#include <config.h> 24 25#include <isc/buffer.h> 26#include <isc/mem.h> 27#include <isc/net.h> 28#include <isc/netaddr.h> 29#include <isc/print.h> 30#include <isc/stdlib.h> 31#include <isc/string.h> 32#include <isc/util.h> 33 34#include <dns/db.h> 35#include <dns/fixedname.h> 36#include <dns/log.h> 37#include <dns/rdata.h> 38#include <dns/rdataset.h> 39#include <dns/rdatastruct.h> 40#include <dns/result.h> 41#include <dns/rpz.h> 42#include <dns/view.h> 43 44 45/* 46 * Parallel radix trees for databases of response policy IP addresses 47 * 48 * The radix or Patricia trees are somewhat specialized to handle response 49 * policy addresses by representing the two test of IP IP addresses and name 50 * server IP addresses in a single tree. 51 * 52 * Each leaf indicates that an IP address is listed in the IP address or the 53 * name server IP address policy sub-zone (or both) of the corresponding 54 * response response zone. The policy data such as a CNAME or an A record 55 * is kept in the policy zone. After an IP address has been found in a radix 56 * tree, the node in the policy zone's database is found by converting 57 * the IP address to a domain name in a canonical form. 58 * 59 * The response policy zone canonical form of IPv6 addresses is one of: 60 * prefix.W.W.W.W.W.W.W.W 61 * prefix.WORDS.zz 62 * prefix.WORDS.zz.WORDS 63 * prefix.zz.WORDS 64 * where 65 * prefix is the prefix length of the IPv6 address between 1 and 128 66 * W is a number between 0 and 65535 67 * WORDS is one or more numbers W separated with "." 68 * zz corresponds to :: in the standard IPv6 text representation 69 * 70 * The canonical form of IPv4 addresses is: 71 * prefix.B.B.B.B 72 * where 73 * prefix is the prefix length of the address between 1 and 32 74 * B is a number between 0 and 255 75 * 76 * IPv4 addresses are distinguished from IPv6 addresses by having 77 * 5 labels all of which are numbers, and a prefix between 1 and 32. 78 */ 79 80 81/* 82 * Use a private definition of IPv6 addresses because s6_addr32 is not 83 * always defined and our IPv6 addresses are in non-standard byte order 84 */ 85typedef isc_uint32_t dns_rpz_cidr_word_t; 86#define DNS_RPZ_CIDR_WORD_BITS ((int)sizeof(dns_rpz_cidr_word_t)*8) 87#define DNS_RPZ_CIDR_KEY_BITS ((int)sizeof(dns_rpz_cidr_key_t)*8) 88#define DNS_RPZ_CIDR_WORDS (128/DNS_RPZ_CIDR_WORD_BITS) 89typedef struct { 90 dns_rpz_cidr_word_t w[DNS_RPZ_CIDR_WORDS]; 91} dns_rpz_cidr_key_t; 92 93#define ADDR_V4MAPPED 0xffff 94 95#define DNS_RPZ_WORD_MASK(b) \ 96 ((b) == 0 ? (dns_rpz_cidr_word_t)(-1) \ 97 : ((dns_rpz_cidr_word_t)(-1) \ 98 << (DNS_RPZ_CIDR_WORD_BITS - (b)))) 99 100#define DNS_RPZ_IP_BIT(ip, bitno) \ 101 (1 & ((ip)->w[(bitno)/DNS_RPZ_CIDR_WORD_BITS] >> \ 102 (DNS_RPZ_CIDR_WORD_BITS - 1 - ((bitno) % DNS_RPZ_CIDR_WORD_BITS)))) 103 104typedef struct dns_rpz_cidr_node dns_rpz_cidr_node_t; 105typedef isc_uint8_t dns_rpz_cidr_flags_t; 106struct dns_rpz_cidr_node { 107 dns_rpz_cidr_node_t *parent; 108 dns_rpz_cidr_node_t *child[2]; 109 dns_rpz_cidr_key_t ip; 110 dns_rpz_cidr_bits_t bits; 111 dns_rpz_cidr_flags_t flags; 112#define DNS_RPZ_CIDR_FG_IP 0x01 /* has IP data or is parent of IP */ 113#define DNS_RPZ_CIDR_FG_IP_DATA 0x02 /* has IP data */ 114#define DNS_RPZ_CIDR_FG_NSIPv4 0x04 /* has or is parent of NSIPv4 data */ 115#define DNS_RPZ_CIDR_FG_NSIPv6 0x08 /* has or is parent of NSIPv6 data */ 116#define DNS_RPZ_CIDR_FG_NSIP_DATA 0x10 /* has NSIP data */ 117}; 118 119struct dns_rpz_cidr { 120 isc_mem_t *mctx; 121 isc_boolean_t have_nsdname; /* zone has NSDNAME record */ 122 dns_rpz_cidr_node_t *root; 123 dns_name_t ip_name; /* RPZ_IP_ZONE.origin. */ 124 dns_name_t nsip_name; /* RPZ_NSIP_ZONE.origin. */ 125 dns_name_t nsdname_name; /* RPZ_NSDNAME_ZONE.origin */ 126}; 127 128static isc_boolean_t have_rpz_zones = ISC_FALSE; 129 130const char * 131dns_rpz_type2str(dns_rpz_type_t type) { 132 switch (type) { 133 case DNS_RPZ_TYPE_QNAME: 134 return ("QNAME"); 135 case DNS_RPZ_TYPE_IP: 136 return ("IP"); 137 case DNS_RPZ_TYPE_NSIP: 138 return ("NSIP"); 139 case DNS_RPZ_TYPE_NSDNAME: 140 return ("NSDNAME"); 141 case DNS_RPZ_TYPE_BAD: 142 break; 143 } 144 FATAL_ERROR(__FILE__, __LINE__, 145 "impossible rpz type %d", type); 146 return ("impossible"); 147} 148 149dns_rpz_policy_t 150dns_rpz_str2policy(const char *str) { 151 if (str == NULL) 152 return (DNS_RPZ_POLICY_ERROR); 153 if (!strcasecmp(str, "given")) 154 return (DNS_RPZ_POLICY_GIVEN); 155 if (!strcasecmp(str, "disabled")) 156 return (DNS_RPZ_POLICY_DISABLED); 157 if (!strcasecmp(str, "passthru")) 158 return (DNS_RPZ_POLICY_PASSTHRU); 159 if (!strcasecmp(str, "nxdomain")) 160 return (DNS_RPZ_POLICY_NXDOMAIN); 161 if (!strcasecmp(str, "nodata")) 162 return (DNS_RPZ_POLICY_NODATA); 163 if (!strcasecmp(str, "cname")) 164 return (DNS_RPZ_POLICY_CNAME); 165 /* 166 * Obsolete 167 */ 168 if (!strcasecmp(str, "no-op")) 169 return (DNS_RPZ_POLICY_PASSTHRU); 170 return (DNS_RPZ_POLICY_ERROR); 171} 172 173const char * 174dns_rpz_policy2str(dns_rpz_policy_t policy) { 175 const char *str; 176 177 switch (policy) { 178 case DNS_RPZ_POLICY_PASSTHRU: 179 str = "PASSTHRU"; 180 break; 181 case DNS_RPZ_POLICY_NXDOMAIN: 182 str = "NXDOMAIN"; 183 break; 184 case DNS_RPZ_POLICY_NODATA: 185 str = "NODATA"; 186 break; 187 case DNS_RPZ_POLICY_RECORD: 188 str = "Local-Data"; 189 break; 190 case DNS_RPZ_POLICY_CNAME: 191 case DNS_RPZ_POLICY_WILDCNAME: 192 str = "CNAME"; 193 break; 194 default: 195 str = ""; 196 INSIST(0); 197 } 198 return (str); 199} 200 201/* 202 * Free the radix tree of a response policy database. 203 */ 204void 205dns_rpz_cidr_free(dns_rpz_cidr_t **cidrp) { 206 dns_rpz_cidr_node_t *cur, *child, *parent; 207 dns_rpz_cidr_t *cidr; 208 209 REQUIRE(cidrp != NULL); 210 211 cidr = *cidrp; 212 if (cidr == NULL) 213 return; 214 215 cur = cidr->root; 216 while (cur != NULL) { 217 /* Depth first. */ 218 child = cur->child[0]; 219 if (child != NULL) { 220 cur = child; 221 continue; 222 } 223 child = cur->child[1]; 224 if (child != NULL) { 225 cur = child; 226 continue; 227 } 228 229 /* Delete this leaf and go up. */ 230 parent = cur->parent; 231 if (parent == NULL) 232 cidr->root = NULL; 233 else 234 parent->child[parent->child[1] == cur] = NULL; 235 isc_mem_put(cidr->mctx, cur, sizeof(*cur)); 236 cur = parent; 237 } 238 239 dns_name_free(&cidr->ip_name, cidr->mctx); 240 dns_name_free(&cidr->nsip_name, cidr->mctx); 241 dns_name_free(&cidr->nsdname_name, cidr->mctx); 242 isc_mem_put(cidr->mctx, cidr, sizeof(*cidr)); 243 *cidrp = NULL; 244} 245 246/* 247 * Forget a view's list of policy zones. 248 */ 249void 250dns_rpz_view_destroy(dns_view_t *view) { 251 dns_rpz_zone_t *zone; 252 253 REQUIRE(view != NULL); 254 255 while (!ISC_LIST_EMPTY(view->rpz_zones)) { 256 zone = ISC_LIST_HEAD(view->rpz_zones); 257 ISC_LIST_UNLINK(view->rpz_zones, zone, link); 258 if (dns_name_dynamic(&zone->origin)) 259 dns_name_free(&zone->origin, view->mctx); 260 if (dns_name_dynamic(&zone->passthru)) 261 dns_name_free(&zone->passthru, view->mctx); 262 if (dns_name_dynamic(&zone->nsdname)) 263 dns_name_free(&zone->nsdname, view->mctx); 264 if (dns_name_dynamic(&zone->cname)) 265 dns_name_free(&zone->cname, view->mctx); 266 isc_mem_put(view->mctx, zone, sizeof(*zone)); 267 } 268} 269 270/* 271 * Note that we have at least one response policy zone. 272 * It would be better for something to tell the rbtdb code that the 273 * zone is in at least one view's list of policy zones. 274 */ 275void 276dns_rpz_set_need(isc_boolean_t need) { 277 have_rpz_zones = need; 278} 279 280isc_boolean_t 281dns_rpz_needed(void) { 282 return (have_rpz_zones); 283} 284 285/* 286 * Start a new radix tree for a response policy zone. 287 */ 288isc_result_t 289dns_rpz_new_cidr(isc_mem_t *mctx, dns_name_t *origin, 290 dns_rpz_cidr_t **rbtdb_cidr) 291{ 292 isc_result_t result; 293 dns_rpz_cidr_t *cidr; 294 295 REQUIRE(rbtdb_cidr != NULL && *rbtdb_cidr == NULL); 296 297 /* 298 * Only if there is at least one response policy zone. 299 */ 300 if (!have_rpz_zones) 301 return (ISC_R_SUCCESS); 302 303 cidr = isc_mem_get(mctx, sizeof(*cidr)); 304 if (cidr == NULL) 305 return (ISC_R_NOMEMORY); 306 memset(cidr, 0, sizeof(*cidr)); 307 cidr->mctx = mctx; 308 309 dns_name_init(&cidr->ip_name, NULL); 310 result = dns_name_fromstring2(&cidr->ip_name, DNS_RPZ_IP_ZONE, origin, 311 DNS_NAME_DOWNCASE, mctx); 312 if (result != ISC_R_SUCCESS) { 313 isc_mem_put(mctx, cidr, sizeof(*cidr)); 314 return (result); 315 } 316 317 dns_name_init(&cidr->nsip_name, NULL); 318 result = dns_name_fromstring2(&cidr->nsip_name, DNS_RPZ_NSIP_ZONE, 319 origin, DNS_NAME_DOWNCASE, mctx); 320 if (result != ISC_R_SUCCESS) { 321 dns_name_free(&cidr->ip_name, mctx); 322 isc_mem_put(mctx, cidr, sizeof(*cidr)); 323 return (result); 324 } 325 326 dns_name_init(&cidr->nsdname_name, NULL); 327 result = dns_name_fromstring2(&cidr->nsdname_name, DNS_RPZ_NSDNAME_ZONE, 328 origin, DNS_NAME_DOWNCASE, mctx); 329 if (result != ISC_R_SUCCESS) { 330 dns_name_free(&cidr->nsip_name, mctx); 331 dns_name_free(&cidr->ip_name, mctx); 332 isc_mem_put(mctx, cidr, sizeof(*cidr)); 333 return (result); 334 } 335 336 *rbtdb_cidr = cidr; 337 return (ISC_R_SUCCESS); 338} 339 340/* 341 * See if a policy zone has IP, NSIP, or NSDNAME rules or records. 342 */ 343void 344dns_rpz_enabled(dns_rpz_cidr_t *cidr, dns_rpz_st_t *st) { 345 if (cidr == NULL) 346 return; 347 if (cidr->root != NULL && 348 (cidr->root->flags & DNS_RPZ_CIDR_FG_IP) != 0) 349 st->state |= DNS_RPZ_HAVE_IP; 350 if (cidr->root != NULL && 351 (cidr->root->flags & DNS_RPZ_CIDR_FG_NSIPv4) != 0) 352 st->state |= DNS_RPZ_HAVE_NSIPv4; 353 if (cidr->root != NULL && 354 (cidr->root->flags & DNS_RPZ_CIDR_FG_NSIPv6) != 0) 355 st->state |= DNS_RPZ_HAVE_NSIPv6; 356 if (cidr->have_nsdname) 357 st->state |= DNS_RPZ_HAVE_NSDNAME; 358} 359 360static inline dns_rpz_cidr_flags_t 361get_flags(const dns_rpz_cidr_key_t *ip, dns_rpz_cidr_bits_t prefix, 362 dns_rpz_type_t rpz_type) 363{ 364 if (rpz_type == DNS_RPZ_TYPE_NSIP) { 365 if (prefix >= 96 && 366 ip->w[0] == 0 && ip->w[1] == 0 && 367 ip->w[2] == ADDR_V4MAPPED) 368 return (DNS_RPZ_CIDR_FG_NSIP_DATA | 369 DNS_RPZ_CIDR_FG_NSIPv4); 370 else 371 return (DNS_RPZ_CIDR_FG_NSIP_DATA | 372 DNS_RPZ_CIDR_FG_NSIPv6); 373 } else { 374 return (DNS_RPZ_CIDR_FG_IP | DNS_RPZ_CIDR_FG_IP_DATA); 375 } 376} 377 378/* 379 * Mark a node as having IP or NSIP data and all of its parents 380 * as members of the IP or NSIP tree. 381 */ 382static void 383set_node_flags(dns_rpz_cidr_node_t *node, dns_rpz_type_t rpz_type) { 384 dns_rpz_cidr_flags_t flags; 385 386 flags = get_flags(&node->ip, node->bits, rpz_type); 387 node->flags |= flags; 388 flags &= ~(DNS_RPZ_CIDR_FG_NSIP_DATA | DNS_RPZ_CIDR_FG_IP_DATA); 389 for (;;) { 390 node = node->parent; 391 if (node == NULL) 392 return; 393 node->flags |= flags; 394 } 395} 396 397/* 398 * Make a radix tree node. 399 */ 400static dns_rpz_cidr_node_t * 401new_node(dns_rpz_cidr_t *cidr, const dns_rpz_cidr_key_t *ip, 402 dns_rpz_cidr_bits_t bits, dns_rpz_cidr_flags_t flags) 403{ 404 dns_rpz_cidr_node_t *node; 405 int i, words, wlen; 406 407 node = isc_mem_get(cidr->mctx, sizeof(*node)); 408 if (node == NULL) 409 return (NULL); 410 memset(node, 0, sizeof(*node)); 411 412 node->flags = flags & ~(DNS_RPZ_CIDR_FG_IP_DATA | 413 DNS_RPZ_CIDR_FG_NSIP_DATA); 414 415 node->bits = bits; 416 words = bits / DNS_RPZ_CIDR_WORD_BITS; 417 wlen = bits % DNS_RPZ_CIDR_WORD_BITS; 418 i = 0; 419 while (i < words) { 420 node->ip.w[i] = ip->w[i]; 421 ++i; 422 } 423 if (wlen != 0) { 424 node->ip.w[i] = ip->w[i] & DNS_RPZ_WORD_MASK(wlen); 425 ++i; 426 } 427 while (i < DNS_RPZ_CIDR_WORDS) 428 node->ip.w[i++] = 0; 429 430 return (node); 431} 432 433static void 434badname(int level, dns_name_t *name, const char *str1, const char *str2) { 435 char printname[DNS_NAME_FORMATSIZE]; 436 437 if (level < DNS_RPZ_DEBUG_QUIET 438 && isc_log_wouldlog(dns_lctx, level)) { 439 dns_name_format(name, printname, sizeof(printname)); 440 isc_log_write(dns_lctx, DNS_LOGCATEGORY_RPZ, 441 DNS_LOGMODULE_RBTDB, level, 442 "invalid rpz IP address \"%s\"%s%s", 443 printname, str1, str2); 444 } 445} 446 447/* 448 * Convert an IP address from radix tree binary (host byte order) to 449 * to its canonical response policy domain name and its name in the 450 * policy zone. 451 */ 452static isc_result_t 453ip2name(dns_rpz_cidr_t *cidr, const dns_rpz_cidr_key_t *tgt_ip, 454 dns_rpz_cidr_bits_t tgt_prefix, dns_rpz_type_t type, 455 dns_name_t *canon_name, dns_name_t *search_name) 456{ 457#ifndef INET6_ADDRSTRLEN 458#define INET6_ADDRSTRLEN 46 459#endif 460 int w[DNS_RPZ_CIDR_WORDS*2]; 461 char str[1+8+1+INET6_ADDRSTRLEN+1]; 462 isc_buffer_t buffer; 463 dns_name_t *name; 464 isc_result_t result; 465 isc_boolean_t zeros; 466 int i, n, len; 467 468 if (tgt_prefix > 96 && 469 tgt_ip->w[0] == 0 && 470 tgt_ip->w[1] == 0 && 471 tgt_ip->w[2] == ADDR_V4MAPPED) { 472 len = snprintf(str, sizeof(str), "%d.%d.%d.%d.%d", 473 tgt_prefix - 96, 474 tgt_ip->w[3] & 0xff, 475 (tgt_ip->w[3]>>8) & 0xff, 476 (tgt_ip->w[3]>>16) & 0xff, 477 (tgt_ip->w[3]>>24) & 0xff); 478 if (len == -1 || len > (int)sizeof(str)) 479 return (ISC_R_FAILURE); 480 } else { 481 for (i = 0; i < DNS_RPZ_CIDR_WORDS; i++) { 482 w[i*2+1] = ((tgt_ip->w[DNS_RPZ_CIDR_WORDS-1-i] >> 16) 483 & 0xffff); 484 w[i*2] = tgt_ip->w[DNS_RPZ_CIDR_WORDS-1-i] & 0xffff; 485 } 486 zeros = ISC_FALSE; 487 len = snprintf(str, sizeof(str), "%d", tgt_prefix); 488 if (len == -1) 489 return (ISC_R_FAILURE); 490 i = 0; 491 while (i < DNS_RPZ_CIDR_WORDS * 2) { 492 if (w[i] != 0 || zeros 493 || i >= DNS_RPZ_CIDR_WORDS * 2 - 1 494 || w[i+1] != 0) { 495 INSIST((size_t)len <= sizeof(str)); 496 n = snprintf(&str[len], sizeof(str) - len, 497 ".%x", w[i++]); 498 if (n < 0) 499 return (ISC_R_FAILURE); 500 len += n; 501 } else { 502 zeros = ISC_TRUE; 503 INSIST((size_t)len <= sizeof(str)); 504 n = snprintf(&str[len], sizeof(str) - len, 505 ".zz"); 506 if (n < 0) 507 return (ISC_R_FAILURE); 508 len += n; 509 i += 2; 510 while (i < DNS_RPZ_CIDR_WORDS * 2 && w[i] == 0) 511 ++i; 512 } 513 if (len > (int)sizeof(str)) 514 return (ISC_R_FAILURE); 515 } 516 } 517 518 if (canon_name != NULL) { 519 isc__buffer_init(&buffer, str, sizeof(str)); 520 isc__buffer_add(&buffer, len); 521 result = dns_name_fromtext(canon_name, &buffer, 522 dns_rootname, 0, NULL); 523 if (result != ISC_R_SUCCESS) 524 return (result); 525 } 526 if (search_name != NULL) { 527 isc__buffer_init(&buffer, str, sizeof(str)); 528 isc__buffer_add(&buffer, len); 529 if (type == DNS_RPZ_TYPE_NSIP) 530 name = &cidr->nsip_name; 531 else 532 name = &cidr->ip_name; 533 result = dns_name_fromtext(search_name, &buffer, name, 0, NULL); 534 if (result != ISC_R_SUCCESS) 535 return (result); 536 } 537 return (ISC_R_SUCCESS); 538} 539 540/* 541 * Decide which kind of IP address response policy zone a name is in. 542 */ 543static dns_rpz_type_t 544set_type(dns_rpz_cidr_t *cidr, dns_name_t *name) { 545 546 if (dns_name_issubdomain(name, &cidr->ip_name)) 547 return (DNS_RPZ_TYPE_IP); 548 549 /* 550 * Require `./configure --enable-rpz-nsip` and nsdname 551 * until consistency problems are resolved. 552 */ 553#ifdef ENABLE_RPZ_NSIP 554 if (dns_name_issubdomain(name, &cidr->nsip_name)) 555 return (DNS_RPZ_TYPE_NSIP); 556#endif 557 558#ifdef ENABLE_RPZ_NSDNAME 559 if (dns_name_issubdomain(name, &cidr->nsdname_name)) 560 return (DNS_RPZ_TYPE_NSDNAME); 561#endif 562 563 return (DNS_RPZ_TYPE_QNAME); 564} 565 566/* 567 * Convert an IP address from canonical response policy domain name form 568 * to radix tree binary (host byte order). 569 */ 570static isc_result_t 571name2ipkey(dns_rpz_cidr_t *cidr, int level, dns_name_t *src_name, 572 dns_rpz_type_t type, dns_rpz_cidr_key_t *tgt_ip, 573 dns_rpz_cidr_bits_t *tgt_prefix) 574{ 575 isc_result_t result; 576 dns_fixedname_t fname; 577 dns_name_t *ipname; 578 char ipstr[DNS_NAME_FORMATSIZE]; 579 const char *prefix_str, *cp, *end; 580 char *cp2; 581 int ip_labels; 582 dns_rpz_cidr_bits_t bits; 583 unsigned long prefix, l; 584 int i; 585 586 /* 587 * Need at least enough labels for the shortest name, 588 * :: or 128.*.RPZ_x_ZONE.rpz.LOCALHOST. 589 */ 590 ip_labels = dns_name_countlabels(src_name); 591 ip_labels -= dns_name_countlabels(&cidr->ip_name); 592 ip_labels--; 593 if (ip_labels < 1) { 594 badname(level, src_name, "; too short", ""); 595 return (ISC_R_FAILURE); 596 } 597 598 /* 599 * Get text for the IP address 600 */ 601 dns_fixedname_init(&fname); 602 ipname = dns_fixedname_name(&fname); 603 dns_name_split(src_name, dns_name_countlabels(&cidr->ip_name), 604 ipname, NULL); 605 dns_name_format(ipname, ipstr, sizeof(ipstr)); 606 end = &ipstr[strlen(ipstr)+1]; 607 prefix_str = ipstr; 608 609 prefix = strtoul(prefix_str, &cp2, 10); 610 if (*cp2 != '.') { 611 badname(level, src_name, 612 "; invalid leading prefix length", ""); 613 return (ISC_R_FAILURE); 614 } 615 *cp2 = '\0'; 616 if (prefix < 1U || prefix > 128U) { 617 badname(level, src_name, 618 "; invalid prefix length of ", prefix_str); 619 return (ISC_R_FAILURE); 620 } 621 cp = cp2+1; 622 623 if (ip_labels == 4 && !strchr(cp, 'z')) { 624 /* 625 * Convert an IPv4 address 626 * from the form "prefix.w.z.y.x" 627 */ 628 if (prefix > 32U) { 629 badname(level, src_name, 630 "; invalid IPv4 prefix length of ", prefix_str); 631 return (ISC_R_FAILURE); 632 } 633 prefix += 96; 634 *tgt_prefix = (dns_rpz_cidr_bits_t)prefix; 635 tgt_ip->w[0] = 0; 636 tgt_ip->w[1] = 0; 637 tgt_ip->w[2] = ADDR_V4MAPPED; 638 tgt_ip->w[3] = 0; 639 for (i = 0; i < 32; i += 8) { 640 l = strtoul(cp, &cp2, 10); 641 if (l > 255U || (*cp2 != '.' && *cp2 != '\0')) { 642 if (*cp2 == '.') 643 *cp2 = '\0'; 644 badname(level, src_name, 645 "; invalid IPv4 octet ", cp); 646 return (ISC_R_FAILURE); 647 } 648 tgt_ip->w[3] |= l << i; 649 cp = cp2 + 1; 650 } 651 } else { 652 /* 653 * Convert a text IPv6 address. 654 */ 655 *tgt_prefix = (dns_rpz_cidr_bits_t)prefix; 656 for (i = 0; 657 ip_labels > 0 && i < DNS_RPZ_CIDR_WORDS * 2; 658 ip_labels--) { 659 if (cp[0] == 'z' && cp[1] == 'z' && 660 (cp[2] == '.' || cp[2] == '\0') && 661 i <= 6) { 662 do { 663 if ((i & 1) == 0) 664 tgt_ip->w[3-i/2] = 0; 665 ++i; 666 } while (ip_labels + i <= 8); 667 cp += 3; 668 } else { 669 l = strtoul(cp, &cp2, 16); 670 if (l > 0xffffu || 671 (*cp2 != '.' && *cp2 != '\0')) { 672 if (*cp2 == '.') 673 *cp2 = '\0'; 674 badname(level, src_name, 675 "; invalid IPv6 word ", cp); 676 return (ISC_R_FAILURE); 677 } 678 if ((i & 1) == 0) 679 tgt_ip->w[3-i/2] = l; 680 else 681 tgt_ip->w[3-i/2] |= l << 16; 682 i++; 683 cp = cp2 + 1; 684 } 685 } 686 } 687 if (cp != end) { 688 badname(level, src_name, "", ""); 689 return (ISC_R_FAILURE); 690 } 691 692 /* 693 * Check for 1s after the prefix length. 694 */ 695 bits = (dns_rpz_cidr_bits_t)prefix; 696 while (bits < DNS_RPZ_CIDR_KEY_BITS) { 697 dns_rpz_cidr_word_t aword; 698 699 i = bits % DNS_RPZ_CIDR_WORD_BITS; 700 aword = tgt_ip->w[bits / DNS_RPZ_CIDR_WORD_BITS]; 701 if ((aword & ~DNS_RPZ_WORD_MASK(i)) != 0) { 702 badname(level, src_name, 703 "; too small prefix length of ", prefix_str); 704 return (ISC_R_FAILURE); 705 } 706 bits -= i; 707 bits += DNS_RPZ_CIDR_WORD_BITS; 708 } 709 710 /* 711 * Convert the address back to a canonical policy domain name 712 * to ensure that it is in canonical form. 713 */ 714 result = ip2name(cidr, tgt_ip, (dns_rpz_cidr_bits_t) prefix, 715 type, NULL, ipname); 716 if (result != ISC_R_SUCCESS || !dns_name_equal(src_name, ipname)) { 717 badname(level, src_name, "; not canonical", ""); 718 return (ISC_R_FAILURE); 719 } 720 721 return (ISC_R_SUCCESS); 722} 723 724/* 725 * Find first differing bit. 726 */ 727static int 728ffbit(dns_rpz_cidr_word_t w) { 729 int bit; 730 731 bit = DNS_RPZ_CIDR_WORD_BITS-1; 732 if ((w & 0xffff0000) != 0) { 733 w >>= 16; 734 bit -= 16; 735 } 736 if ((w & 0xff00) != 0) { 737 w >>= 8; 738 bit -= 8; 739 } 740 if ((w & 0xf0) != 0) { 741 w >>= 4; 742 bit -= 4; 743 } 744 if ((w & 0xc) != 0) { 745 w >>= 2; 746 bit -= 2; 747 } 748 if ((w & 2) != 0) 749 --bit; 750 return (bit); 751} 752 753/* 754 * Find the first differing bit in two keys. 755 */ 756static int 757diff_keys(const dns_rpz_cidr_key_t *key1, dns_rpz_cidr_bits_t bits1, 758 const dns_rpz_cidr_key_t *key2, dns_rpz_cidr_bits_t bits2) 759{ 760 dns_rpz_cidr_word_t delta; 761 dns_rpz_cidr_bits_t maxbit, bit; 762 int i; 763 764 maxbit = ISC_MIN(bits1, bits2); 765 766 /* 767 * find the first differing words 768 */ 769 for (i = 0, bit = 0; 770 bit <= maxbit; 771 i++, bit += DNS_RPZ_CIDR_WORD_BITS) { 772 delta = key1->w[i] ^ key2->w[i]; 773 if (delta != 0) { 774 bit += ffbit(delta); 775 break; 776 } 777 } 778 return (ISC_MIN(bit, maxbit)); 779} 780 781/* 782 * Search a radix tree for an IP address for ordinary lookup 783 * or for a CIDR block adding or deleting an entry 784 * The tree read (for simple search) or write lock must be held by the caller. 785 * 786 * Return ISC_R_SUCCESS, ISC_R_NOTFOUND, DNS_R_PARTIALMATCH, ISC_R_EXISTS, 787 * ISC_R_NOMEMORY 788 */ 789static isc_result_t 790search(dns_rpz_cidr_t *cidr, const dns_rpz_cidr_key_t *tgt_ip, 791 dns_rpz_cidr_bits_t tgt_prefix, dns_rpz_type_t type, 792 isc_boolean_t create, 793 dns_rpz_cidr_node_t **found) /* NULL or longest match node */ 794{ 795 dns_rpz_cidr_node_t *cur, *parent, *child, *new_parent, *sibling; 796 int cur_num, child_num; 797 dns_rpz_cidr_bits_t dbit; 798 dns_rpz_cidr_flags_t flags, data_flag; 799 isc_result_t find_result; 800 801 flags = get_flags(tgt_ip, tgt_prefix, type); 802 data_flag = flags & (DNS_RPZ_CIDR_FG_IP_DATA | 803 DNS_RPZ_CIDR_FG_NSIP_DATA); 804 805 find_result = ISC_R_NOTFOUND; 806 if (found != NULL) 807 *found = NULL; 808 cur = cidr->root; 809 parent = NULL; 810 cur_num = 0; 811 for (;;) { 812 if (cur == NULL) { 813 /* 814 * No child so we cannot go down. Fail or 815 * add the target as a child of the current parent. 816 */ 817 if (!create) 818 return (find_result); 819 child = new_node(cidr, tgt_ip, tgt_prefix, 0); 820 if (child == NULL) 821 return (ISC_R_NOMEMORY); 822 if (parent == NULL) 823 cidr->root = child; 824 else 825 parent->child[cur_num] = child; 826 child->parent = parent; 827 set_node_flags(child, type); 828 if (found != NULL) 829 *found = cur; 830 return (ISC_R_SUCCESS); 831 } 832 833 /* 834 * Pretend a node not in the correct tree does not exist 835 * if we are not adding to the tree, 836 * If we are adding, then continue down to eventually 837 * add a node and mark/put this node in the correct tree. 838 */ 839 if ((cur->flags & flags) == 0 && !create) 840 return (find_result); 841 842 dbit = diff_keys(tgt_ip, tgt_prefix, &cur->ip, cur->bits); 843 /* 844 * dbit <= tgt_prefix and dbit <= cur->bits always. 845 * We are finished searching if we matched all of the target. 846 */ 847 if (dbit == tgt_prefix) { 848 if (tgt_prefix == cur->bits) { 849 /* 850 * The current node matches the target exactly. 851 * It is the answer if it has data. 852 */ 853 if ((cur->flags & data_flag) != 0) { 854 if (create) 855 return (ISC_R_EXISTS); 856 if (found != NULL) 857 *found = cur; 858 return (ISC_R_SUCCESS); 859 } else if (create) { 860 /* 861 * The node had no data but does now. 862 */ 863 set_node_flags(cur, type); 864 if (found != NULL) 865 *found = cur; 866 return (ISC_R_SUCCESS); 867 } 868 return (find_result); 869 } 870 871 /* 872 * We know tgt_prefix < cur_bits which means that 873 * the target is shorter than the current node. 874 * Add the target as the current node's parent. 875 */ 876 if (!create) 877 return (find_result); 878 879 new_parent = new_node(cidr, tgt_ip, tgt_prefix, 880 cur->flags); 881 if (new_parent == NULL) 882 return (ISC_R_NOMEMORY); 883 new_parent->parent = parent; 884 if (parent == NULL) 885 cidr->root = new_parent; 886 else 887 parent->child[cur_num] = new_parent; 888 child_num = DNS_RPZ_IP_BIT(&cur->ip, tgt_prefix+1); 889 new_parent->child[child_num] = cur; 890 cur->parent = new_parent; 891 set_node_flags(new_parent, type); 892 if (found != NULL) 893 *found = new_parent; 894 return (ISC_R_SUCCESS); 895 } 896 897 if (dbit == cur->bits) { 898 /* 899 * We have a partial match by matching of all of the 900 * current node but only part of the target. 901 * Try to go down. 902 */ 903 if ((cur->flags & data_flag) != 0) { 904 find_result = DNS_R_PARTIALMATCH; 905 if (found != NULL) 906 *found = cur; 907 } 908 909 parent = cur; 910 cur_num = DNS_RPZ_IP_BIT(tgt_ip, dbit); 911 cur = cur->child[cur_num]; 912 continue; 913 } 914 915 916 /* 917 * dbit < tgt_prefix and dbit < cur->bits, 918 * so we failed to match both the target and the current node. 919 * Insert a fork of a parent above the current node and 920 * add the target as a sibling of the current node 921 */ 922 if (!create) 923 return (find_result); 924 925 sibling = new_node(cidr, tgt_ip, tgt_prefix, 0); 926 if (sibling == NULL) 927 return (ISC_R_NOMEMORY); 928 new_parent = new_node(cidr, tgt_ip, dbit, cur->flags); 929 if (new_parent == NULL) { 930 isc_mem_put(cidr->mctx, sibling, sizeof(*sibling)); 931 return (ISC_R_NOMEMORY); 932 } 933 new_parent->parent = parent; 934 if (parent == NULL) 935 cidr->root = new_parent; 936 else 937 parent->child[cur_num] = new_parent; 938 child_num = DNS_RPZ_IP_BIT(tgt_ip, dbit); 939 new_parent->child[child_num] = sibling; 940 new_parent->child[1-child_num] = cur; 941 cur->parent = new_parent; 942 sibling->parent = new_parent; 943 set_node_flags(sibling, type); 944 if (found != NULL) 945 *found = sibling; 946 return (ISC_R_SUCCESS); 947 } 948} 949 950/* 951 * Add an IP address to the radix tree of a response policy database. 952 * The tree write lock must be held by the caller. 953 */ 954void 955dns_rpz_cidr_addip(dns_rpz_cidr_t *cidr, dns_name_t *name) { 956 isc_result_t result; 957 dns_rpz_cidr_key_t tgt_ip; 958 dns_rpz_cidr_bits_t tgt_prefix; 959 dns_rpz_type_t type; 960 961 if (cidr == NULL) 962 return; 963 964 /* 965 * No worries if the new name is not an IP address. 966 */ 967 type = set_type(cidr, name); 968 switch (type) { 969 case DNS_RPZ_TYPE_IP: 970 case DNS_RPZ_TYPE_NSIP: 971 break; 972 case DNS_RPZ_TYPE_NSDNAME: 973 cidr->have_nsdname = ISC_TRUE; 974 return; 975 case DNS_RPZ_TYPE_QNAME: 976 case DNS_RPZ_TYPE_BAD: 977 return; 978 } 979 result = name2ipkey(cidr, DNS_RPZ_ERROR_LEVEL, name, 980 type, &tgt_ip, &tgt_prefix); 981 if (result != ISC_R_SUCCESS) 982 return; 983 984 result = search(cidr, &tgt_ip, tgt_prefix, type, ISC_TRUE, NULL); 985 if (result == ISC_R_EXISTS && 986 isc_log_wouldlog(dns_lctx, DNS_RPZ_ERROR_LEVEL)) 987 { 988 char printname[DNS_NAME_FORMATSIZE]; 989 990 dns_name_format(name, printname, sizeof(printname)); 991 isc_log_write(dns_lctx, DNS_LOGCATEGORY_RPZ, 992 DNS_LOGMODULE_RBTDB, DNS_RPZ_ERROR_LEVEL, 993 "rpz add failed; \"%s\" is a duplicate name", 994 printname); 995 } 996} 997 998/* 999 * Delete an IP address from the radix tree of a response policy database. 1000 * The tree write lock must be held by the caller. 1001 */ 1002void 1003dns_rpz_cidr_deleteip(dns_rpz_cidr_t *cidr, dns_name_t *name) { 1004 isc_result_t result; 1005 dns_rpz_cidr_key_t tgt_ip; 1006 dns_rpz_cidr_bits_t tgt_prefix; 1007 dns_rpz_type_t type; 1008 dns_rpz_cidr_node_t *tgt = NULL, *parent, *child; 1009 dns_rpz_cidr_flags_t flags, data_flag; 1010 1011 if (cidr == NULL) 1012 return; 1013 1014 /* 1015 * Decide which kind of policy zone IP address it is, if either 1016 * and then find its node. 1017 */ 1018 type = set_type(cidr, name); 1019 switch (type) { 1020 case DNS_RPZ_TYPE_IP: 1021 case DNS_RPZ_TYPE_NSIP: 1022 break; 1023 case DNS_RPZ_TYPE_NSDNAME: 1024 /* 1025 * We cannot easily count nsdnames because 1026 * internal rbt nodes get deleted. 1027 */ 1028 return; 1029 case DNS_RPZ_TYPE_QNAME: 1030 case DNS_RPZ_TYPE_BAD: 1031 return; 1032 } 1033 1034 /* 1035 * Do not get excited about the deletion of interior rbt nodes. 1036 */ 1037 result = name2ipkey(cidr, DNS_RPZ_DEBUG_QUIET, name, 1038 type, &tgt_ip, &tgt_prefix); 1039 if (result != ISC_R_SUCCESS) 1040 return; 1041 1042 result = search(cidr, &tgt_ip, tgt_prefix, type, ISC_FALSE, &tgt); 1043 if (result != ISC_R_SUCCESS) { 1044 badname(DNS_RPZ_ERROR_LEVEL, name, "; missing rpz node", ""); 1045 return; 1046 } 1047 1048 /* 1049 * Mark the node and its parents to reflect the deleted IP address. 1050 */ 1051 flags = get_flags(&tgt_ip, tgt_prefix, type); 1052 data_flag = flags & (DNS_RPZ_CIDR_FG_IP_DATA | 1053 DNS_RPZ_CIDR_FG_NSIP_DATA); 1054 tgt->flags &= ~data_flag; 1055 for (parent = tgt; parent != NULL; parent = parent->parent) { 1056 if ((parent->flags & data_flag) != 0 || 1057 (parent->child[0] != NULL && 1058 (parent->child[0]->flags & flags) != 0) || 1059 (parent->child[1] != NULL && 1060 (parent->child[1]->flags & flags) != 0)) 1061 break; 1062 parent->flags &= ~flags; 1063 } 1064 1065 /* 1066 * We might need to delete 2 nodes. 1067 */ 1068 do { 1069 /* 1070 * The node is now useless if it has no data of its own 1071 * and 0 or 1 children. We are finished if it is not useless. 1072 */ 1073 if ((child = tgt->child[0]) != NULL) { 1074 if (tgt->child[1] != NULL) 1075 return; 1076 } else { 1077 child = tgt->child[1]; 1078 } 1079 if ((tgt->flags & (DNS_RPZ_CIDR_FG_IP_DATA | 1080 DNS_RPZ_CIDR_FG_NSIP_DATA)) != 0) 1081 return; 1082 1083 /* 1084 * Replace the pointer to this node in the parent with 1085 * the remaining child or NULL. 1086 */ 1087 parent = tgt->parent; 1088 if (parent == NULL) { 1089 cidr->root = child; 1090 } else { 1091 parent->child[parent->child[1] == tgt] = child; 1092 } 1093 /* 1094 * If the child exists fix up its parent pointer. 1095 */ 1096 if (child != NULL) 1097 child->parent = parent; 1098 isc_mem_put(cidr->mctx, tgt, sizeof(*tgt)); 1099 1100 tgt = parent; 1101 } while (tgt != NULL); 1102} 1103 1104/* 1105 * Caller must hold tree lock. 1106 * Return ISC_R_NOTFOUND 1107 * or ISC_R_SUCCESS and the found entry's canonical and search names 1108 * and its prefix length 1109 */ 1110isc_result_t 1111dns_rpz_cidr_find(dns_rpz_cidr_t *cidr, const isc_netaddr_t *netaddr, 1112 dns_rpz_type_t type, dns_name_t *canon_name, 1113 dns_name_t *search_name, dns_rpz_cidr_bits_t *prefix) 1114{ 1115 dns_rpz_cidr_key_t tgt_ip; 1116 isc_result_t result; 1117 dns_rpz_cidr_node_t *found; 1118 int i; 1119 1120 /* 1121 * Convert IP address to CIDR tree key. 1122 */ 1123 if (netaddr->family == AF_INET) { 1124 tgt_ip.w[0] = 0; 1125 tgt_ip.w[1] = 0; 1126 tgt_ip.w[2] = ADDR_V4MAPPED; 1127 tgt_ip.w[3] = ntohl(netaddr->type.in.s_addr); 1128 } else if (netaddr->family == AF_INET6) { 1129 dns_rpz_cidr_key_t src_ip6; 1130 1131 /* 1132 * Given the int aligned struct in_addr member of netaddr->type 1133 * one could cast netaddr->type.in6 to dns_rpz_cidr_key_t *, 1134 * but there are objections. 1135 */ 1136 memcpy(src_ip6.w, &netaddr->type.in6, sizeof(src_ip6.w)); 1137 for (i = 0; i < 4; i++) { 1138 tgt_ip.w[i] = ntohl(src_ip6.w[i]); 1139 } 1140 } else { 1141 return (ISC_R_NOTFOUND); 1142 } 1143 1144 result = search(cidr, &tgt_ip, 128, type, ISC_FALSE, &found); 1145 if (result != ISC_R_SUCCESS && result != DNS_R_PARTIALMATCH) 1146 return (result); 1147 1148 *prefix = found->bits; 1149 return (ip2name(cidr, &found->ip, found->bits, type, 1150 canon_name, search_name)); 1151} 1152 1153/* 1154 * Translate CNAME rdata to a QNAME response policy action. 1155 */ 1156dns_rpz_policy_t 1157dns_rpz_decode_cname(dns_rpz_zone_t *rpz, dns_rdataset_t *rdataset, 1158 dns_name_t *selfname) 1159{ 1160 dns_rdata_t rdata = DNS_RDATA_INIT; 1161 dns_rdata_cname_t cname; 1162 isc_result_t result; 1163 1164 result = dns_rdataset_first(rdataset); 1165 RUNTIME_CHECK(result == ISC_R_SUCCESS); 1166 dns_rdataset_current(rdataset, &rdata); 1167 result = dns_rdata_tostruct(&rdata, &cname, NULL); 1168 RUNTIME_CHECK(result == ISC_R_SUCCESS); 1169 dns_rdata_reset(&rdata); 1170 1171 /* 1172 * CNAME . means NXDOMAIN 1173 */ 1174 if (dns_name_equal(&cname.cname, dns_rootname)) 1175 return (DNS_RPZ_POLICY_NXDOMAIN); 1176 1177 if (dns_name_iswildcard(&cname.cname)) { 1178 /* 1179 * CNAME *. means NODATA 1180 */ 1181 if (dns_name_countlabels(&cname.cname) == 2) 1182 return (DNS_RPZ_POLICY_NODATA); 1183 1184 /* 1185 * A qname of www.evil.com and a policy of 1186 * *.evil.com CNAME *.garden.net 1187 * gives a result of 1188 * evil.com CNAME evil.com.garden.net 1189 */ 1190 if (dns_name_countlabels(&cname.cname) > 2) 1191 return (DNS_RPZ_POLICY_WILDCNAME); 1192 } 1193 1194 /* 1195 * CNAME PASSTHRU.origin means "do not rewrite. 1196 */ 1197 if (dns_name_equal(&cname.cname, &rpz->passthru)) 1198 return (DNS_RPZ_POLICY_PASSTHRU); 1199 1200 /* 1201 * 128.1.0.127.rpz-ip CNAME 128.1.0.0.127. is obsolete PASSTHRU 1202 */ 1203 if (selfname != NULL && dns_name_equal(&cname.cname, selfname)) 1204 return (DNS_RPZ_POLICY_PASSTHRU); 1205 1206 /* 1207 * Any other rdata gives a response consisting of the rdata. 1208 */ 1209 return (DNS_RPZ_POLICY_RECORD); 1210} 1211