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