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