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