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